Changeset 1620

Timestamp:

07/23/14 18:18:11 (10 years ago)

Author:

rkrimmel

Message:

More intelligent match finding and creation

Location:

branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees

Files:

• alignment/algorithms/AlignmentAlgorithm.java (modified) (2 diffs)
• alignment/algorithms/GenerateTask.java (added)
• alignment/algorithms/Match.java (added)
• alignment/algorithms/MatchOccurence.java (added)
• alignment/algorithms/NeedlemanWunsch.java (modified) (2 diffs)
• alignment/algorithms/NumberSequence.java (modified) (6 diffs)
• alignment/algorithms/SmithWaterman.java (modified) (2 diffs)
• alignment/algorithms/SmithWatermanRepeated.java (modified) (6 diffs)
• alignment/matrix/ObjectDistanceSubstitionMatrix.java (modified) (1 diff)
• alignment/matrix/PairwiseAlignmentGenerator.java (modified) (3 diffs)
• alignment/pal/tree/UPGMAAligningTree.java (modified) (5 diffs)
• temporalrelation/SequenceForTaskDetectionRuleAlignment.java (modified) (5 diffs)

branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/AlignmentAlgorithm.java

@@ -6 +6 @@
 
 public interface AlignmentAlgorithm {
-
-        public abstract void align(int[] input1, int[] input2, SubstitutionMatrix submat,float threshold);
         
         /**
@@ -20 +18 @@
         public abstract void printAlignment();
 
-        public abstract ArrayList<ArrayList<NumberSequence>> getMatches();
+        public abstract ArrayList<Match> getMatches();
+
+        void align(NumberSequence input1, NumberSequence input2,
+                        SubstitutionMatrix submat, float threshold);
 
 }

branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/NeedlemanWunsch.java

@@ -260 +260 @@
 
         @Override
-        public ArrayList<ArrayList<NumberSequence>> getMatches() {
+        public ArrayList<Match> getMatches() {
                 // TODO Auto-generated method stub
                 return null;
@@ -266 +266 @@
 
         @Override
-        public void align(int[] input1, int[] input2, SubstitutionMatrix submat,
+        public void align(NumberSequence input1, NumberSequence input2, SubstitutionMatrix submat,
                         float threshold) {
-                this.input1 = input1;
-                this.input2 = input2;
-                length1 = input1.length;
-                length2 = input2.length;
+                this.input1 = input1.getSequence();
+                this.input2 = input2.getSequence();
+                length1 = input1.size();
+                length2 = input2.size();
                 this.submat = submat;
 

branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/NumberSequence.java

@@ -6 +6 @@
 public class NumberSequence {
         private int[] sequence;
-        private int signature;
+        private int id;
+
+        public ArrayList<Match> getMatches() {
+                return matches;
+        }
+
+
+        public void setMatches(ArrayList<Match> matches) {
+                this.matches = matches;
+        }
+        
+        public void addMatches(ArrayList<Match> matches) {
+                this.matches.addAll(matches);
+        }
+
+        private ArrayList<Match> matches;
 
         public NumberSequence(int size) {
@@ -12 +27 @@
                 sequence = new int[size];
         }
-
+        
         public int[] getSequence() {
                 return sequence;
@@ -21 +36 @@
         }
 
-        public int getSignature() {
-                return signature;
-        }
-
-        public void setSignature(int signature) {
-                this.signature = signature;
-        }
+        
 
         public void printSequence() {
@@ -38 +47 @@
         public NumberSequence shuffle() {
                 NumberSequence result = new NumberSequence(sequence.length);
+                result.setId(getId());
                 result.setSequence(this.sequence);
                 Random rgen = new Random();
@@ -51 +61 @@
         }
 
-        // TODO: This can be done faster
-        public int containsPattern(ArrayList<NumberSequence> pattern) {
+
+        public int containsPattern(Match pattern) {
                 int i = 0;
                 int count = 0;
-                int[] pat1 = pattern.get(0).getSequence();
-                int[] pat2 = pattern.get(1).getSequence();
+                int[] pat1 = pattern.getFirstSequence().getSequence();
+                int[] pat2 = pattern.getSecondSequence().getSequence();
                 notmatched: while (i < sequence.length - pat1.length) {
                         if (sequence[i] == pat1[0] || sequence[i] == pat2[0]) {
-                                for (int j = 0; j < pat1.length; j++) {
-                                        if (sequence[i + j] != pat1[j]
-                                                        && sequence[i + j] != pat2[j]) {
+                                int ipat1 =0;
+                                int ipat2 =0;
+                                while(ipat1 < pat1.length && ipat2<pat2.length) {
+                                        if(pat1[ipat1]==-1) {
+                                                ipat1++;
+                                                continue;
+                                        }
+                                        if(pat2[ipat2]==-1) {
+                                                ipat2++;
+                                                continue;
+                                        }
+                                        if (sequence[i + ipat1] != pat1[ipat1]
+                                                        && sequence[i + ipat2] != pat2[ipat2]) {
                                                 i++;
                                                 continue notmatched;
                                         }
+                                        ipat1++;
+                                        ipat2++;
                                 }
                                 count++;
@@ -72 +94 @@
                 return count;
         }
+        
+        //Returns the number of times event occurs in this sequence
+        public int eventCount(int event) {
+                int count = 0;
+                for(int i=0;i<sequence.length;i++) {
+                        if(sequence[i] == event) {
+                                count++;
+                        }
+                }
+                return count;
+        }
 
         public int size() {
                 return sequence.length;
         }
+
+
+        public int getId() {
+                return id;
+        }
+
+
+        public void setId(int id) {
+                this.id = id;
+        }
 }

branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/SmithWaterman.java

@@ -265 +265 @@
 
         @Override
-        public ArrayList<ArrayList<NumberSequence>> getMatches() {
+        public ArrayList<Match> getMatches() {
                 // TODO Auto-generated method stub
                 return null;
@@ -271 +271 @@
 
         @Override
-        public void align(int[] input1, int[] input2, SubstitutionMatrix submat,
+        public void align(NumberSequence input1, NumberSequence input2, SubstitutionMatrix submat,
                         float threshold) {
-                this.input1 = input1;
-                this.input2 = input2;
-                length1 = input1.length;
-                length2 = input2.length;
+                this.input1 = input1.getSequence();
+                this.input2 = input2.getSequence();
+                length1 = input1.size();
+                length2 = input2.size();
                 this.submat = submat;
 

branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/algorithms/SmithWatermanRepeated.java

@@ -231 +231 @@
                 ns1.setSequence(reversed1);
                 ns2.setSequence(reversed2);
-
-                alignment.add(ns1);
-                alignment.add(ns2);
+                ns1.setId(alignment.get(0).getId());
+                ns2.setId(alignment.get(1).getId());
+                
+                alignment.set(0, ns1);
+                alignment.set(1, ns2);
         }
         
@@ -272 +274 @@
         }
         
-        public ArrayList<ArrayList<NumberSequence>> getMatches() {
-                ArrayList<ArrayList<NumberSequence>> result = new ArrayList<ArrayList<NumberSequence>>();
+        public ArrayList<Match> getMatches() {
+                ArrayList<Match> result = new ArrayList<Match>();
                 
                 //both alignment sequences should be equally long
@@ -288 +290 @@
                                         count++;
                                 }
-                                //I am really missing memcpy here 
+                                //I am really missing memcpy here? How does one do this better in java? 
                                 int[] tmp1 = new int[count];
                                 int[] tmp2 = new int[count];
@@ -299 +301 @@
                                 tmpns1.setSequence(tmp1);
                                 tmpns2.setSequence(tmp2);
-                                ArrayList<NumberSequence> tmpal = new ArrayList<NumberSequence>();
-                                tmpal.add(tmpns1);
-                                tmpal.add(tmpns2);
+                                Match tmpal = new Match();
+                                tmpal.setFirstSequence(tmpns1);
+                                tmpal.setSecondSequence(tmpns2);
+                                tmpal.addOccurence(new MatchOccurence(start,alignment.get(0).getId()));
+                                tmpal.addOccurence(new MatchOccurence(start,alignment.get(1).getId()));
                                 result.add(tmpal);
                         }
                         i++;
                 }
-                
-                
-                
-                
-                
-                
                 return result;
-                
         }
         
@@ -354 +351 @@
 
         @Override
-        public void align(int[] input1, int[] input2, SubstitutionMatrix submat,
+        public void align(NumberSequence input1, NumberSequence input2, SubstitutionMatrix submat,
                         float threshold) {
-                this.input1 = input1;
-                this.input2 = input2;
-                length1 = input1.length;
-                length2 = input2.length;
+                
+                alignment = new ArrayList<NumberSequence>();
+                alignment.add(input1);
+                alignment.add(input2);
+                
+                this.input1=input1.getSequence();
+                this.input2=input2.getSequence();
+                
+                length1 = input1.size();
+                length2 = input2.size();
                 this.submat = submat;
 
@@ -367 +370 @@
                 
                 matrix = new MatrixEntry[length1+2][length2+1];
-                alignment = new ArrayList<NumberSequence>();
+                
                 
                 for (int i = 0; i <= length1+1; i++) {

branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/matrix/ObjectDistanceSubstitionMatrix.java

@@ -25 +25 @@
         
         public ObjectDistanceSubstitionMatrix(
-                        SymbolMap<ITaskInstance, ITask> uniqueTasks,float positiveThreshold) {
+                        SymbolMap<ITaskInstance, ITask> uniqueTasks,float positiveThreshold, int gapPenalty) {
                 this.uniqueTasks = uniqueTasks;
                 this.positiveThreshold = positiveThreshold;
                 idmapping = new HashMap<Integer, Integer>();
                 matrix = new TriangleMatrix(uniqueTasks.size()+1);
-                gapPenalty = -3;
+                this.gapPenalty = gapPenalty;
                 
         }

branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/matrix/PairwiseAlignmentGenerator.java

@@ -14 +14 @@
         public static PairwiseAlignmentStorage generate(
                         ArrayList<NumberSequence> numberseqs,
-                        ObjectDistanceSubstitionMatrix submat) {
+                        ObjectDistanceSubstitionMatrix submat, 
+                        int threshold) {
                 PairwiseAlignmentStorage alignments = new PairwiseAlignmentStorage(
                                 numberseqs.size(), numberseqs.size());
+                int smithWatermanThreshold = threshold;
 
                 for (int i = 0; i < numberseqs.size(); i++) {
@@ -25 +27 @@
                                 if (i != j) {
                                         Console.traceln(Level.FINEST,"Aligning sequence " + i + " with sequence " + j);
-                                        int smithWatermanThreshold = 10;
+                                
                                         AlignmentAlgorithm aa = AlignmentAlgorithmFactory.create();
-                                        aa.align(ns1.getSequence(), ns2.getSequence(), submat,
+                                        aa.align(ns1, ns2, submat,
                                                         smithWatermanThreshold);
                                         alignments.set(i, j, aa);
@@ -33 +35 @@
                                         AlignmentAlgorithm sameSequence1 = AlignmentAlgorithmFactory
                                                         .create();
-                                        sameSequence1.align(ns1.getSequence(), ns1.getSequence(),
+                                        sameSequence1.align(ns1, ns1,
                                                         submat, smithWatermanThreshold);
                                         AlignmentAlgorithm sameSequence2 = AlignmentAlgorithmFactory
                                                         .create();
-                                        sameSequence2.align(ns2.getSequence(), ns2.getSequence(),
+                                        sameSequence2.align(ns2, ns2,
                                                         submat, smithWatermanThreshold);
                                         AlignmentAlgorithm randomSequence = AlignmentAlgorithmFactory
                                                         .create();
-                                        randomSequence.align(ns1.shuffle().getSequence(), ns2
-                                                        .shuffle().getSequence(), submat,
+                                        randomSequence.align(ns1.shuffle(), ns2
+                                                        .shuffle(), submat,
                                                         smithWatermanThreshold);
 

branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/UPGMAAligningTree.java

@@ -223 +223 @@
                         if(seqCount1 == 1 && seqCount2 == 1) {
                                 AlignmentAlgorithm aa = AlignmentAlgorithmFactory.create();
-                                aa.align(node1.getSequence(0).getSequence(), node2.getSequence(0).getSequence(), submat, 5);
+                                aa.align(node1.getSequence(0), node2.getSequence(0), submat, 5);
                                 alignment = aa.getAlignment();
                                 
@@ -236 +236 @@
                                 for(int i=0;i<seqCount1;i++){
                                         AlignmentAlgorithm aa = AlignmentAlgorithmFactory.create();
-                                        aa.align(node1.getSequence(i).getSequence(), node2.getSequence(0).getSequence() , submat, 5);
+                                        aa.align(node1.getSequence(i), node2.getSequence(0) , submat, 5);
                                         tempStorage.set(i, 1, aa);
                                         
@@ -256 +256 @@
                                 for(int i=0;i<seqCount2;i++) {
                                         AlignmentAlgorithm aa = AlignmentAlgorithmFactory.create();
-                                        aa.align(node2.getSequence(i).getSequence(), node1.getSequence(0).getSequence() , submat, 5);
+                                        aa.align(node2.getSequence(i), node1.getSequence(0) , submat, 5);
                                         tempStorage.set(1, i, aa);
                                         if(maxScore < tempStorage.get(1, i).getAlignmentScore()) {
@@ -278 +278 @@
                                                 for(int j=0;j<seqCount2;j++) {
                                                         AlignmentAlgorithm aa =AlignmentAlgorithmFactory.create();
-                                                        aa.align(node1.getSequence(i).getSequence(), node2.getSequence(j).getSequence() , submat, 5);
+                                                        aa.align(node1.getSequence(i), node2.getSequence(j), submat, 5);
                                                         tempStorage1.set(j, 0, aa);
                                                         if(maxScore1 < tempStorage1.get(j, 0).getAlignmentScore()) {
@@ -291 +291 @@
                                                 for (int j=0;j<seqCount1;j++) {
                                                         AlignmentAlgorithm aa =AlignmentAlgorithmFactory.create();
-                                                        aa.align(node2.getSequence(i).getSequence(),node1.getSequence(j).getSequence(),submat,5);
+                                                        aa.align(node2.getSequence(i),node1.getSequence(j),submat,5);
                                                         tempStorage2.set(j, 0, aa);
                                                         if(maxScore2 < tempStorage2.get(j, 0).getAlignmentScore()) {

branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/SequenceForTaskDetectionRuleAlignment.java

@@ -26 +26 @@
 
 import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.AlignmentAlgorithmFactory;
+import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.Match;
 import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.NumberSequence;
 import de.ugoe.cs.autoquest.tasktrees.alignment.matrix.PairwiseAlignmentGenerator;
@@ -155 +156 @@
                 Console.traceln(Level.INFO,"generating substitution matrix");
                 ObjectDistanceSubstitionMatrix submat = new ObjectDistanceSubstitionMatrix(
-                                uniqueTasks, 5);
+                                uniqueTasks, 6,-3);
                 submat.generate();
 
                 Console.traceln(Level.INFO,"generating pairwise alignments");
-                ArrayList<ArrayList<NumberSequence>> matchseqs = new ArrayList<ArrayList<NumberSequence>>();
-                PairwiseAlignmentStorage alignments = PairwiseAlignmentGenerator.generate(numberseqs,submat);
+                ArrayList<Match> matchseqs = new ArrayList<Match>();
+                PairwiseAlignmentStorage alignments = PairwiseAlignmentGenerator.generate(numberseqs,submat,9);
                 
                 Console.traceln(Level.INFO,"retrieving significant sequence pieces");
@@ -167 +168 @@
                         for(int j=0; j< numberseqs.size();j++) {
                                 if(i != j) {
-                                        ArrayList<ArrayList<NumberSequence>> tmp = alignments.get(i, j).getMatches();
-                                        matchseqs.addAll(tmp);
+                                        matchseqs.addAll(alignments.get(i, j).getMatches());
                                 }   
                         }
@@ -178 +178 @@
                 //search this match in every other sequence
                 for(int i=0; i < matchseqs.size();i++) {
-                        int occurencecount = 0;
+                        int sequencecount = 0;
+                        int totalcount = 0;
+                        Match pattern = matchseqs.get(i);
+                        
+                
+                        
+                        //Skip sequences with more 0 events (scrolls) than other events. Both of the pattern sequences are equally long, so the added 0 counts 
+                        //just need to be smaller than the length of one sequence 
+                        if(pattern.getFirstSequence().eventCount(0) + pattern.getSecondSequence().eventCount(0) +1 > pattern.getFirstSequence().size())
+                                continue;
                         Console.traceln(Level.FINEST, "searching for patterns occuring most: " + Math.round((float)i/(float)matchseqs.size()*100) + "%");
-                        for(int j=0; j < matchseqs.size();j++) {
-                                if(i>j) {
-                                        if(matchseqs.get(j).get(0).containsPattern(matchseqs.get(i)) > 0 || matchseqs.get(j).get(1).containsPattern(matchseqs.get(i)) > 0) {
-                                                occurencecount++;
+                        for(int j=0; j < numberseqs.size();j++) {
+                                        int tmpcount = numberseqs.get(j).containsPattern(pattern);
+                                        if(tmpcount > 0) {
+                                                sequencecount++;
+                                                totalcount+=tmpcount;
                                         }
-                                }
-                        }
-                        if(occurencecount > 1) {
-                                System.out.println("Found pattern \n "); 
-                                matchseqs.get(i).get(0).printSequence(); 
-                                matchseqs.get(i).get(1).printSequence(); 
-                                System.out.println(occurencecount + " times");
+                        }
+                        
+                        if(totalcount > 1) {
+                                matchseqs.get(i).getFirstSequence().printSequence(); 
+                                matchseqs.get(i).getFirstSequence().printSequence();
+                                System.out.println("Found pattern in " + sequencecount +"/" + numberseqs.size() + " sequences, total of " + totalcount + " occurences");
                                 System.out.println();
                         }
                 }
-                
-                
-                
                 alignments = null;
                 
@@ -290 +296 @@
                                 }
                         }
+                        templist.setId(numberseqs.size());
                         numberseqs.add(templist);
                         comparator.clearBuffers();