Changeset 1621 for branches/ralph/src/main/java/de/ugoe/cs

Timestamp:

07/27/14 20:28:19 (10 years ago)

Author:

rkrimmel

Message:

Harmonizing matches

Location:

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

Files:

• alignment/algorithms/Match.java (modified) (2 diffs)
• alignment/algorithms/NumberSequence.java (modified) (4 diffs)
• temporalrelation/SequenceForTaskDetectionRuleAlignment.java (modified) (3 diffs)

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

@@ -2 +2 @@
 
 import java.util.ArrayList;
+import java.util.Iterator;
 import java.util.LinkedList;
 
 public class Match {
         private ArrayList<NumberSequence> matchseqs;
-        
-        private LinkedList<MatchOccurence> occurences; 
-        
-        
-        Match(){
+
+        private LinkedList<MatchOccurence> occurences;
+
+        Match() {
                 matchseqs = new ArrayList<NumberSequence>(2);
                 occurences = new LinkedList<MatchOccurence>();
@@ -16 +16 @@
                 matchseqs.add(null);
         }
-        
+
         public NumberSequence getFirstSequence() {
                 return matchseqs.get(0);
         }
-        
+
         public NumberSequence getSecondSequence() {
                 return matchseqs.get(1);
         }
-        
+
         public void setFirstSequence(NumberSequence seq) {
                 matchseqs.set(0, seq);
         }
-        
+
         public void setSecondSequence(NumberSequence seq) {
                 matchseqs.set(1, seq);
         }
-        
+
         public void addOccurence(MatchOccurence occurence) {
                 occurences.add(occurence);
         }
-        
+
         public int occurenceCount() {
                 return occurences.size();
-        }       
+        }
+
+        public boolean equals(Match m) {
+                if ((m.getFirstSequence().equals(this.getFirstSequence()) || m
+                                .getFirstSequence().equals(this.getSecondSequence()))
+                                && (m.getSecondSequence().equals(this.getFirstSequence()) || m
+                                                .getSecondSequence().equals(this.getSecondSequence()))) {
+                        return true;
+                }
+                return false;
+        }
+
+        public LinkedList<MatchOccurence> getOccurences() {
+                return occurences;
+        }
+
+        public void setOccurences(LinkedList<MatchOccurence> occurences) {
+                this.occurences = occurences;
+        }
+
+        
+        public void addOccurencesOf(Match m) {
+                LinkedList<MatchOccurence> occ = m.getOccurences();
+                occurences.addAll(occ);
+        }
 
 }

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

@@ -2 +2 @@
 
 import java.util.ArrayList;
+import java.util.LinkedList;
 import java.util.Random;
 
@@ -61 +62 @@
         }
 
-
-        public int containsPattern(Match pattern) {
+        //Searching occurences of 
+        public LinkedList<Integer> containsPattern(Match pattern) {
+                LinkedList<Integer> result = new LinkedList<Integer>();
                 int i = 0;
-                int count = 0;
                 int[] pat1 = pattern.getFirstSequence().getSequence();
                 int[] pat2 = pattern.getSecondSequence().getSequence();
@@ -88 +89 @@
                                         ipat2++;
                                 }
-                                count++;
+                                result.add(i);
                         }
                         i++;
                 }
-                return count;
+                return result;
         }
         
@@ -119 +120 @@
                 this.id = id;
         }
+        
+        public boolean equals(NumberSequence n) {
+                int[] seq = n.getSequence();
+                if(n.size() !=this.size()) {
+                        return false; 
+                }
+                for (int i=0; i<n.size();i++) {
+                        if(seq[i] != this.sequence[i]) {
+                                return false;
+                        }
+                }
+                return true;
+        }
+        
+        
 }

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

@@ -16 +16 @@
 
 import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Comparator;
 import java.util.HashMap;
 import java.util.HashSet;
@@ -27 +29 @@
 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.MatchOccurence;
 import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.NumberSequence;
 import de.ugoe.cs.autoquest.tasktrees.alignment.matrix.PairwiseAlignmentGenerator;
@@ -154 +157 @@
                 SymbolMap<ITaskInstance, ITask> uniqueTasks = harmonizeEventTaskInstancesModel(appData);
 
-                Console.traceln(Level.INFO,"generating substitution matrix");
+                // Generate a substitution matrix between all occuring events.
+                Console.traceln(Level.INFO, "generating substitution matrix");
                 ObjectDistanceSubstitionMatrix submat = new ObjectDistanceSubstitionMatrix(
-                                uniqueTasks, 6,-3);
+                                uniqueTasks, 6, -3);
                 submat.generate();
 
-                Console.traceln(Level.INFO,"generating pairwise alignments");
-                ArrayList<Match> matchseqs = new ArrayList<Match>();
-                PairwiseAlignmentStorage alignments = PairwiseAlignmentGenerator.generate(numberseqs,submat,9);
-                
-                Console.traceln(Level.INFO,"retrieving significant sequence pieces");
-                for (int i=0; i< numberseqs.size();i++) {
-                        Console.traceln(Level.FINEST,"retrieving significant sequence pieces:  " + Math.round((float)i/(float)numberseqs.size()*100) + "%");
-                        for(int j=0; j< numberseqs.size();j++) {
-                                if(i != j) {
+                // Generate pairwise alignments
+                Console.traceln(Level.INFO, "generating pairwise alignments");
+                LinkedList<Match> matchseqs = new LinkedList<Match>();
+                PairwiseAlignmentStorage alignments = PairwiseAlignmentGenerator
+                                .generate(numberseqs, submat, 9);
+
+                // Retrieve all matches reached a specific threshold
+                Console.traceln(Level.INFO, "retrieving significant sequence pieces");
+                for (int i = 0; i < numberseqs.size(); i++) {
+                        Console.traceln(
+                                        Level.FINEST,
+                                        "retrieving significant sequence pieces:  "
+                                                        + Math.round((float) i / (float) numberseqs.size()
+                                                                        * 100) + "%");
+                        for (int j = 0; j < numberseqs.size(); j++) {
+                                if (i != j) {
                                         matchseqs.addAll(alignments.get(i, j).getMatches());
-                                }   
-                        }
-                }
-                Console.traceln(Level.FINEST,"retrieving significant sequence pieces:  100%");
-                
+                                }
+                        }
+                }
+                Console.traceln(Level.FINEST,
+                                "retrieving significant sequence pieces:  100%");
                 Console.traceln(Level.INFO, "searching for patterns occuring most");
 
-                //search this match in every other sequence
-                for(int i=0; i < matchseqs.size();i++) {
+                // search each match in every other sequence
+                for (Iterator<Match> it = matchseqs.iterator(); it.hasNext();) {
                         int sequencecount = 0;
                         int totalcount = 0;
-                        Match pattern = matchseqs.get(i);
+                        Match pattern = it.next();
+
+                        // 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;
+        
+                        for (int j = 0; j < numberseqs.size(); j++) {
+                                LinkedList<Integer> startpositions = numberseqs.get(j)
+                                                .containsPattern(pattern);
+                                if (startpositions.size() > 0) {
+                                        sequencecount++;
+                                        totalcount += startpositions.size();
+                                        for (Iterator<Integer> jt = startpositions.iterator(); jt
+                                                        .hasNext();) {
+                                                pattern.addOccurence(
+                                                                new MatchOccurence(jt.next(), j));
+                                        }
+
+                                }
+                        }
+                }
+
+                Console.traceln(Level.INFO, "sorting results");
+                // Sort results to get the most occuring results
+                Comparator<Match> comparator = new Comparator<Match>() {
+                        public int compare(Match m1, Match m2) {
+                                return m2.occurenceCount() - m1.occurenceCount(); // use your
+                                                                                                                                        // logic
+                        }
+                };
+                Collections.sort(matchseqs, comparator);
+                
+
+                
+                
+                // Harmonize matches: finding double matches and merge them
+                /*
+                Console.traceln(Level.INFO, "harmonizing matches");
+                int i=0;
+                
+                while(i<matchseqs.size()) {
+                        int j=i;
+                        while(j<matchseqs.size()) {
+                                if(i!=j) {
+                                        if(matchseqs.get(i).equals(matchseqs.get(j))) {
+                                                matchseqs.get(i).addOccurencesOf(matchseqs.get(j));
+                                                matchseqs.remove(j);
+                                        
+                                                //System.out.println("Sequence " + i);
+                                                //matchseqs.get(i).getFirstSequence().printSequence();
+                                                //matchseqs.get(i).getSecondSequence().printSequence();
+                                                //System.out.println("is equal to sequence " + j);
+                                                //matchseqs.get(j).getFirstSequence().printSequence();
+                                                //matchseqs.get(j).getSecondSequence().printSequence();
+                                                continue;
+                                        }
+                                }
+                                j++;
+                        }
+                        i++;
+                }
+                Collections.sort(matchseqs, comparator);
+                */ 
+        
+                                        
                         
                 
-                        
-                        //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 < numberseqs.size();j++) {
-                                        int tmpcount = numberseqs.get(j).containsPattern(pattern);
-                                        if(tmpcount > 0) {
-                                                sequencecount++;
-                                                totalcount+=tmpcount;
-                                        }
-                        }
-                        
-                        if(totalcount > 1) {
-                                matchseqs.get(i).getFirstSequence().printSequence(); 
+                
+                
+                
+                // Just printing the results out
+                for (int i = 0; i < matchseqs.size(); i++) {
+                        // Every pattern consists of 2 sequences, therefore the minimum
+                        // occurences here is 2.
+                        // We just need the sequences also occuring in other sequences as
+                        // well
+                        if (matchseqs.get(i).occurenceCount() > 2) {
                                 matchseqs.get(i).getFirstSequence().printSequence();
-                                System.out.println("Found pattern in " + sequencecount +"/" + numberseqs.size() + " sequences, total of " + totalcount + " occurences");
+                                matchseqs.get(i).getSecondSequence().printSequence();
+                                System.out.println("Found pattern "
+                                                + matchseqs.get(i).occurenceCount() + " times");
                                 System.out.println();
                         }
                 }
+                
+
                 alignments = null;
-                
-                //
-                //AlignmentAlgorithmFactory.setDefaultAlgorithm("de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.NeedlemanWunsch");
-                //PairwiseAlignmentStorage matchAlignments = PairwiseAlignmentGenerator.generate(matchseqs, submat);
-                //UPGMAAligningTree guidetree = new UPGMAAligningTree(matchseqs,matchAlignments,submat);
-                //System.out.println(alignments.getDistanceMatrix());
-                
-                //for(Iterator<NumberSequence> it = guidetree.getRoot().getSequences().iterator();it.hasNext();) {
-                //      NumberSequence tmp = (NumberSequence) it.next();
-                //      tmp.printSequence();
-                //}
-                
-        
+
                 /*
-                do {
-
-                        // appData.getStopWatch().start("whole loop");
-                        // detectAndReplaceIterations(appData);
-
-                        // appData.getStopWatch().start("task replacement");
-                        // detectAndReplaceTasks(appData);
-                        // appData.getStopWatch().stop("task replacement");
-                        // appData.getStopWatch().stop("whole loop");
-
-                        // appData.getStopWatch().dumpStatistics(System.out);
-                        // appData.getStopWatch().reset();
-
-                } while (appData.detectedAndReplacedTasks()); */
+                 * do {
+                 * 
+                 * // appData.getStopWatch().start("whole loop"); //
+                 * detectAndReplaceIterations(appData);
+                 * 
+                 * // appData.getStopWatch().start("task replacement"); //
+                 * detectAndReplaceTasks(appData); //
+                 * appData.getStopWatch().stop("task replacement"); //
+                 * appData.getStopWatch().stop("whole loop");
+                 * 
+                 * // appData.getStopWatch().dumpStatistics(System.out); //
+                 * appData.getStopWatch().reset();
+                 * 
+                 * } while (appData.detectedAndReplacedTasks());
+                 */
 
                 Console.println("created "