Changeset 1618

Timestamp:

07/16/14 18:07:05 (10 years ago)

Author:

rkrimmel

Message:

Startet implementing signigicant match detection

Location:

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

Files:

• alignment/algorithms/NumberSequence.java (modified) (2 diffs)
• alignment/algorithms/SmithWatermanRepeated.java (modified) (1 diff)
• alignment/matrix/PairwiseAlignmentGenerator.java (modified) (2 diffs)
• temporalrelation/SequenceForTaskDetectionRuleAlignment.java (copied) (copied from branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/SequenceForTaskDetectionRuleAlignment.java) (1 diff)

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

@@ -1 +1 @@
 package de.ugoe.cs.autoquest.tasktrees.alignment.algorithms;
 
-
+import java.util.ArrayList;
 import java.util.Random;
 
-public class NumberSequence  {
+public class NumberSequence {
         private int[] sequence;
         private int signature;
-        
+
         public NumberSequence(int size) {
-                
+
                 sequence = new int[size];
         }
-        
+
         public int[] getSequence() {
                 return sequence;
         }
+
         public void setSequence(int[] sequence) {
                 this.sequence = sequence;
         }
+
         public int getSignature() {
                 return signature;
         }
+
         public void setSignature(int signature) {
                 this.signature = signature;
         }
-        
-        public void printSequence()
-        {       
+
+        public void printSequence() {
                 for (int i = 0; i < sequence.length; i++) {
                         System.out.format("%5d", sequence[i]);
@@ -33 +35 @@
                 System.out.println();
         }
-        
-        public NumberSequence shuffle(){
+
+        public NumberSequence shuffle() {
                 NumberSequence result = new NumberSequence(sequence.length);
                 result.setSequence(this.sequence);
                 Random rgen = new Random();
-                
-                for (int i=0; i<result.sequence.length; i++) {
-                    int randomPosition = rgen.nextInt(result.sequence.length);
-                    int temp = result.sequence[i];
-                    result.sequence[i] = result.sequence[randomPosition];
-                    result.sequence[randomPosition] = temp;
+
+                for (int i = 0; i < result.sequence.length; i++) {
+                        int randomPosition = rgen.nextInt(result.sequence.length);
+                        int temp = result.sequence[i];
+                        result.sequence[i] = result.sequence[randomPosition];
+                        result.sequence[randomPosition] = temp;
                 }
                 return result;
-                
+
+        }
+
+        // TODO: This can be done faster
+        public int containsPattern(ArrayList<NumberSequence> pattern) {
+                int i = 0;
+                int count = 0;
+                int[] pat1 = pattern.get(0).getSequence();
+                int[] pat2 = pattern.get(1).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]) {
+                                                continue notmatched;
+                                        }
+                                }
+                                count++;
+                        }
+                        i++;
+                }
+                return count;
         }
 

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

@@ -375 +375 @@
                 }
         
-
+                //Console.traceln(Level.INFO,"Generating DP Matrix");
                 buildMatrix();
+                //Console.traceln(Level.INFO,"Doing traceback");
                 traceback();
         }

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

@@ -3 +3 @@
 import java.util.ArrayList;
 import java.util.Iterator;
+import java.util.logging.Level;
 
 import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.AlignmentAlgorithm;
 import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.AlignmentAlgorithmFactory;
 import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.NumberSequence;
+import de.ugoe.cs.util.console.Console;
 
 public class PairwiseAlignmentGenerator {
@@ -22 +24 @@
 
                                 if (i != j) {
+                                        Console.traceln(Level.FINEST,"Aligning sequence " + i + " with sequence " + j);
                                         int smithWatermanThreshold = 10;
                                         AlignmentAlgorithm aa = AlignmentAlgorithmFactory.create();

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

@@ -153 +153 @@
                 SymbolMap<ITaskInstance, ITask> uniqueTasks = harmonizeEventTaskInstancesModel(appData);
 
+                Console.traceln(Level.INFO,"generating substitution matrix");
                 ObjectDistanceSubstitionMatrix submat = new ObjectDistanceSubstitionMatrix(
                                 uniqueTasks, 5);
                 submat.generate();
 
-                ArrayList<NumberSequence> matchseqs = new ArrayList<NumberSequence>();
+                Console.traceln(Level.INFO,"generating pairwise alignments");
+                ArrayList<ArrayList<NumberSequence>> matchseqs = new ArrayList<ArrayList<NumberSequence>>();
                 PairwiseAlignmentStorage alignments = PairwiseAlignmentGenerator.generate(numberseqs,submat);
                 
+                Console.traceln(Level.INFO,"retrieving significant sequence pieces");
                 for (int i=0; i< numberseqs.size();i++) {
                         for(int j=0; j< numberseqs.size();j++) {
                                 if(i != j) {
                                         ArrayList<ArrayList<NumberSequence>> tmp = alignments.get(i, j).getMatches();
-                                        int count = 0;
-                                        for(Iterator<ArrayList<NumberSequence>> it = tmp.iterator();it.hasNext();) {
-                                                System.out.println("Match number " + count);
-                                                ArrayList<NumberSequence> tmp2 = it.next();
-                                                tmp2.get(0).printSequence();
-                                                tmp2.get(1).printSequence();
-                                                System.out.println();
-                                                count++;
-                                                matchseqs.addAll(tmp2);
+                                        matchseqs.addAll(tmp);
+                                }   
+                        }
+                }
+                
+                Console.traceln(Level.INFO, "searching for patterns occuring most");
+                //search this match in every other sequence
+                for(int i=0; i < matchseqs.size();i++) {
+                        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) {
+                                                System.out.println("Found something!");
                                         }
-                                        System.out.println();
-                                }
-                        }
-                }
-                
-                AlignmentAlgorithmFactory.setDefaultAlgorithm("de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.NeedlemanWunsch");
+                                }
+                        }
+                                
+                }
                 
                 
-                PairwiseAlignmentStorage matchAlignments = PairwiseAlignmentGenerator.generate(numberseqs, submat);
-                UPGMAAligningTree guidetree = new UPGMAAligningTree(matchseqs,matchAlignments,submat);
-                System.out.println(alignments.getDistanceMatrix());
-                //UPGMAAligningTree guidetree = new UPGMAAligningTree(numberseqs, alignments,submat);
                 
-                for(Iterator<NumberSequence> it = guidetree.getRoot().getSequences().iterator();it.hasNext();) {
-                        NumberSequence tmp = (NumberSequence) it.next();
-                        tmp.printSequence();
-                }
+                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();
+                //}