Changeset 1620 for branches/ralph


Ignore:
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:
3 added
9 edited

Legend:

Unmodified
Added
Removed

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

    r1612 r1620  
    66 
    77public interface AlignmentAlgorithm { 
    8  
    9         public abstract void align(int[] input1, int[] input2, SubstitutionMatrix submat,float threshold); 
    108         
    119        /** 
    … …  
    2018        public abstract void printAlignment(); 
    2119 
    22         public abstract ArrayList<ArrayList<NumberSequence>> getMatches(); 
     20        public abstract ArrayList<Match> getMatches(); 
     21 
     22        void align(NumberSequence input1, NumberSequence input2, 
     23                        SubstitutionMatrix submat, float threshold); 
    2324 
    2425} 

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

    r1616 r1620  
    260260 
    261261        @Override 
    262         public ArrayList<ArrayList<NumberSequence>> getMatches() { 
     262        public ArrayList<Match> getMatches() { 
    263263                // TODO Auto-generated method stub 
    264264                return null; 
    … …  
    266266 
    267267        @Override 
    268         public void align(int[] input1, int[] input2, SubstitutionMatrix submat, 
     268        public void align(NumberSequence input1, NumberSequence input2, SubstitutionMatrix submat, 
    269269                        float threshold) { 
    270                 this.input1 = input1; 
    271                 this.input2 = input2; 
    272                 length1 = input1.length; 
    273                 length2 = input2.length; 
     270                this.input1 = input1.getSequence(); 
     271                this.input2 = input2.getSequence(); 
     272                length1 = input1.size(); 
     273                length2 = input2.size(); 
    274274                this.submat = submat; 
    275275 

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

    r1619 r1620  
    66public class NumberSequence { 
    77        private int[] sequence; 
    8         private int signature; 
     8        private int id; 
     9 
     10        public ArrayList<Match> getMatches() { 
     11                return matches; 
     12        } 
     13 
     14 
     15        public void setMatches(ArrayList<Match> matches) { 
     16                this.matches = matches; 
     17        } 
     18         
     19        public void addMatches(ArrayList<Match> matches) { 
     20                this.matches.addAll(matches); 
     21        } 
     22 
     23        private ArrayList<Match> matches; 
    924 
    1025        public NumberSequence(int size) { 
    … …  
    1227                sequence = new int[size]; 
    1328        } 
    14  
     29         
    1530        public int[] getSequence() { 
    1631                return sequence; 
    … …  
    2136        } 
    2237 
    23         public int getSignature() { 
    24                 return signature; 
    25         } 
    26  
    27         public void setSignature(int signature) { 
    28                 this.signature = signature; 
    29         } 
     38         
    3039 
    3140        public void printSequence() { 
    … …  
    3847        public NumberSequence shuffle() { 
    3948                NumberSequence result = new NumberSequence(sequence.length); 
     49                result.setId(getId()); 
    4050                result.setSequence(this.sequence); 
    4151                Random rgen = new Random(); 
    … …  
    5161        } 
    5262 
    53         // TODO: This can be done faster 
    54         public int containsPattern(ArrayList<NumberSequence> pattern) { 
     63 
     64        public int containsPattern(Match pattern) { 
    5565                int i = 0; 
    5666                int count = 0; 
    57                 int[] pat1 = pattern.get(0).getSequence(); 
    58                 int[] pat2 = pattern.get(1).getSequence(); 
     67                int[] pat1 = pattern.getFirstSequence().getSequence(); 
     68                int[] pat2 = pattern.getSecondSequence().getSequence(); 
    5969                notmatched: while (i < sequence.length - pat1.length) { 
    6070                        if (sequence[i] == pat1[0] || sequence[i] == pat2[0]) { 
    61                                 for (int j = 0; j < pat1.length; j++) { 
    62                                         if (sequence[i + j] != pat1[j] 
    63                                                         && sequence[i + j] != pat2[j]) { 
     71                                int ipat1 =0; 
     72                                int ipat2 =0; 
     73                                while(ipat1 < pat1.length && ipat2<pat2.length) { 
     74                                        if(pat1[ipat1]==-1) { 
     75                                                ipat1++; 
     76                                                continue; 
     77                                        } 
     78                                        if(pat2[ipat2]==-1) { 
     79                                                ipat2++; 
     80                                                continue; 
     81                                        } 
     82                                        if (sequence[i + ipat1] != pat1[ipat1] 
     83                                                        && sequence[i + ipat2] != pat2[ipat2]) { 
    6484                                                i++; 
    6585                                                continue notmatched; 
    6686                                        } 
     87                                        ipat1++; 
     88                                        ipat2++; 
    6789                                } 
    6890                                count++; 
    … …  
    7294                return count; 
    7395        } 
     96         
     97        //Returns the number of times event occurs in this sequence 
     98        public int eventCount(int event) { 
     99                int count = 0; 
     100                for(int i=0;i<sequence.length;i++) { 
     101                        if(sequence[i] == event) { 
     102                                count++; 
     103                        } 
     104                } 
     105                return count; 
     106        } 
    74107 
    75108        public int size() { 
    76109                return sequence.length; 
    77110        } 
     111 
     112 
     113        public int getId() { 
     114                return id; 
     115        } 
     116 
     117 
     118        public void setId(int id) { 
     119                this.id = id; 
     120        } 
    78121} 

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

    r1612 r1620  
    265265 
    266266        @Override 
    267         public ArrayList<ArrayList<NumberSequence>> getMatches() { 
     267        public ArrayList<Match> getMatches() { 
    268268                // TODO Auto-generated method stub 
    269269                return null; 
    … …  
    271271 
    272272        @Override 
    273         public void align(int[] input1, int[] input2, SubstitutionMatrix submat, 
     273        public void align(NumberSequence input1, NumberSequence input2, SubstitutionMatrix submat, 
    274274                        float threshold) { 
    275                 this.input1 = input1; 
    276                 this.input2 = input2; 
    277                 length1 = input1.length; 
    278                 length2 = input2.length; 
     275                this.input1 = input1.getSequence(); 
     276                this.input2 = input2.getSequence(); 
     277                length1 = input1.size(); 
     278                length2 = input2.size(); 
    279279                this.submat = submat; 
    280280 

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

    r1619 r1620  
    231231                ns1.setSequence(reversed1); 
    232232                ns2.setSequence(reversed2); 
    233  
    234                 alignment.add(ns1); 
    235                 alignment.add(ns2); 
     233                ns1.setId(alignment.get(0).getId()); 
     234                ns2.setId(alignment.get(1).getId()); 
     235                 
     236                alignment.set(0, ns1); 
     237                alignment.set(1, ns2); 
    236238        } 
    237239         
    … …  
    272274        } 
    273275         
    274         public ArrayList<ArrayList<NumberSequence>> getMatches() { 
    275                 ArrayList<ArrayList<NumberSequence>> result = new ArrayList<ArrayList<NumberSequence>>(); 
     276        public ArrayList<Match> getMatches() { 
     277                ArrayList<Match> result = new ArrayList<Match>(); 
    276278                 
    277279                //both alignment sequences should be equally long 
    … …  
    288290                                        count++; 
    289291                                } 
    290                                 //I am really missing memcpy here  
     292                                //I am really missing memcpy here? How does one do this better in java?  
    291293                                int[] tmp1 = new int[count]; 
    292294                                int[] tmp2 = new int[count]; 
    … …  
    299301                                tmpns1.setSequence(tmp1); 
    300302                                tmpns2.setSequence(tmp2); 
    301                                 ArrayList<NumberSequence> tmpal = new ArrayList<NumberSequence>(); 
    302                                 tmpal.add(tmpns1); 
    303                                 tmpal.add(tmpns2); 
     303                                Match tmpal = new Match(); 
     304                                tmpal.setFirstSequence(tmpns1); 
     305                                tmpal.setSecondSequence(tmpns2); 
     306                                tmpal.addOccurence(new MatchOccurence(start,alignment.get(0).getId())); 
     307                                tmpal.addOccurence(new MatchOccurence(start,alignment.get(1).getId())); 
    304308                                result.add(tmpal); 
    305309                        } 
    306310                        i++; 
    307311                } 
    308                  
    309                  
    310                  
    311                  
    312                  
    313                  
    314312                return result; 
    315                  
    316313        } 
    317314         
    … …  
    354351 
    355352        @Override 
    356         public void align(int[] input1, int[] input2, SubstitutionMatrix submat, 
     353        public void align(NumberSequence input1, NumberSequence input2, SubstitutionMatrix submat, 
    357354                        float threshold) { 
    358                 this.input1 = input1; 
    359                 this.input2 = input2; 
    360                 length1 = input1.length; 
    361                 length2 = input2.length; 
     355                 
     356                alignment = new ArrayList<NumberSequence>(); 
     357                alignment.add(input1); 
     358                alignment.add(input2); 
     359                 
     360                this.input1=input1.getSequence(); 
     361                this.input2=input2.getSequence(); 
     362                 
     363                length1 = input1.size(); 
     364                length2 = input2.size(); 
    362365                this.submat = submat; 
    363366 
    … …  
    367370                 
    368371                matrix = new MatrixEntry[length1+2][length2+1]; 
    369                 alignment = new ArrayList<NumberSequence>(); 
     372                 
    370373                 
    371374                for (int i = 0; i <= length1+1; i++) { 

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

    r1615 r1620  
    2525         
    2626        public ObjectDistanceSubstitionMatrix( 
    27                         SymbolMap<ITaskInstance, ITask> uniqueTasks,float positiveThreshold) { 
     27                        SymbolMap<ITaskInstance, ITask> uniqueTasks,float positiveThreshold, int gapPenalty) { 
    2828                this.uniqueTasks = uniqueTasks; 
    2929                this.positiveThreshold = positiveThreshold; 
    3030                idmapping = new HashMap<Integer, Integer>(); 
    3131                matrix = new TriangleMatrix(uniqueTasks.size()+1); 
    32                 gapPenalty = -3; 
     32                this.gapPenalty = gapPenalty; 
    3333                 
    3434        } 

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

    r1618 r1620  
    1414        public static PairwiseAlignmentStorage generate( 
    1515                        ArrayList<NumberSequence> numberseqs, 
    16                         ObjectDistanceSubstitionMatrix submat) { 
     16                        ObjectDistanceSubstitionMatrix submat,  
     17                        int threshold) { 
    1718                PairwiseAlignmentStorage alignments = new PairwiseAlignmentStorage( 
    1819                                numberseqs.size(), numberseqs.size()); 
     20                int smithWatermanThreshold = threshold; 
    1921 
    2022                for (int i = 0; i < numberseqs.size(); i++) { 
    … …  
    2527                                if (i != j) { 
    2628                                        Console.traceln(Level.FINEST,"Aligning sequence " + i + " with sequence " + j); 
    27                                         int smithWatermanThreshold = 10; 
     29                                 
    2830                                        AlignmentAlgorithm aa = AlignmentAlgorithmFactory.create(); 
    29                                         aa.align(ns1.getSequence(), ns2.getSequence(), submat, 
     31                                        aa.align(ns1, ns2, submat, 
    3032                                                        smithWatermanThreshold); 
    3133                                        alignments.set(i, j, aa); 
    … …  
    3335                                        AlignmentAlgorithm sameSequence1 = AlignmentAlgorithmFactory 
    3436                                                        .create(); 
    35                                         sameSequence1.align(ns1.getSequence(), ns1.getSequence(), 
     37                                        sameSequence1.align(ns1, ns1, 
    3638                                                        submat, smithWatermanThreshold); 
    3739                                        AlignmentAlgorithm sameSequence2 = AlignmentAlgorithmFactory 
    3840                                                        .create(); 
    39                                         sameSequence2.align(ns2.getSequence(), ns2.getSequence(), 
     41                                        sameSequence2.align(ns2, ns2, 
    4042                                                        submat, smithWatermanThreshold); 
    4143                                        AlignmentAlgorithm randomSequence = AlignmentAlgorithmFactory 
    4244                                                        .create(); 
    43                                         randomSequence.align(ns1.shuffle().getSequence(), ns2 
    44                                                         .shuffle().getSequence(), submat, 
     45                                        randomSequence.align(ns1.shuffle(), ns2 
     46                                                        .shuffle(), submat, 
    4547                                                        smithWatermanThreshold); 
    4648 

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

    r1612 r1620  
    223223                        if(seqCount1 == 1 && seqCount2 == 1) { 
    224224                                AlignmentAlgorithm aa = AlignmentAlgorithmFactory.create(); 
    225                                 aa.align(node1.getSequence(0).getSequence(), node2.getSequence(0).getSequence(), submat, 5); 
     225                                aa.align(node1.getSequence(0), node2.getSequence(0), submat, 5); 
    226226                                alignment = aa.getAlignment(); 
    227227                                 
    … …  
    236236                                for(int i=0;i<seqCount1;i++){ 
    237237                                        AlignmentAlgorithm aa = AlignmentAlgorithmFactory.create(); 
    238                                         aa.align(node1.getSequence(i).getSequence(), node2.getSequence(0).getSequence() , submat, 5); 
     238                                        aa.align(node1.getSequence(i), node2.getSequence(0) , submat, 5); 
    239239                                        tempStorage.set(i, 1, aa); 
    240240                                         
    … …  
    256256                                for(int i=0;i<seqCount2;i++) { 
    257257                                        AlignmentAlgorithm aa = AlignmentAlgorithmFactory.create(); 
    258                                         aa.align(node2.getSequence(i).getSequence(), node1.getSequence(0).getSequence() , submat, 5); 
     258                                        aa.align(node2.getSequence(i), node1.getSequence(0) , submat, 5); 
    259259                                        tempStorage.set(1, i, aa); 
    260260                                        if(maxScore < tempStorage.get(1, i).getAlignmentScore()) { 
    … …  
    278278                                                for(int j=0;j<seqCount2;j++) { 
    279279                                                        AlignmentAlgorithm aa =AlignmentAlgorithmFactory.create(); 
    280                                                         aa.align(node1.getSequence(i).getSequence(), node2.getSequence(j).getSequence() , submat, 5); 
     280                                                        aa.align(node1.getSequence(i), node2.getSequence(j), submat, 5); 
    281281                                                        tempStorage1.set(j, 0, aa); 
    282282                                                        if(maxScore1 < tempStorage1.get(j, 0).getAlignmentScore()) { 
    … …  
    291291                                                for (int j=0;j<seqCount1;j++) { 
    292292                                                        AlignmentAlgorithm aa =AlignmentAlgorithmFactory.create(); 
    293                                                         aa.align(node2.getSequence(i).getSequence(),node1.getSequence(j).getSequence(),submat,5); 
     293                                                        aa.align(node2.getSequence(i),node1.getSequence(j),submat,5); 
    294294                                                        tempStorage2.set(j, 0, aa); 
    295295                                                        if(maxScore2 < tempStorage2.get(j, 0).getAlignmentScore()) { 

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

    r1619 r1620  
    2626 
    2727import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.AlignmentAlgorithmFactory; 
     28import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.Match; 
    2829import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.NumberSequence; 
    2930import de.ugoe.cs.autoquest.tasktrees.alignment.matrix.PairwiseAlignmentGenerator; 
    … …  
    155156                Console.traceln(Level.INFO,"generating substitution matrix"); 
    156157                ObjectDistanceSubstitionMatrix submat = new ObjectDistanceSubstitionMatrix( 
    157                                 uniqueTasks, 5); 
     158                                uniqueTasks, 6,-3); 
    158159                submat.generate(); 
    159160 
    160161                Console.traceln(Level.INFO,"generating pairwise alignments"); 
    161                 ArrayList<ArrayList<NumberSequence>> matchseqs = new ArrayList<ArrayList<NumberSequence>>(); 
    162                 PairwiseAlignmentStorage alignments = PairwiseAlignmentGenerator.generate(numberseqs,submat); 
     162                ArrayList<Match> matchseqs = new ArrayList<Match>(); 
     163                PairwiseAlignmentStorage alignments = PairwiseAlignmentGenerator.generate(numberseqs,submat,9); 
    163164                 
    164165                Console.traceln(Level.INFO,"retrieving significant sequence pieces"); 
    … …  
    167168                        for(int j=0; j< numberseqs.size();j++) { 
    168169                                if(i != j) { 
    169                                         ArrayList<ArrayList<NumberSequence>> tmp = alignments.get(i, j).getMatches(); 
    170                                         matchseqs.addAll(tmp); 
     170                                        matchseqs.addAll(alignments.get(i, j).getMatches()); 
    171171                                }    
    172172                        } 
    … …  
    178178                //search this match in every other sequence 
    179179                for(int i=0; i < matchseqs.size();i++) { 
    180                         int occurencecount = 0; 
     180                        int sequencecount = 0; 
     181                        int totalcount = 0; 
     182                        Match pattern = matchseqs.get(i); 
     183                         
     184                 
     185                         
     186                        //Skip sequences with more 0 events (scrolls) than other events. Both of the pattern sequences are equally long, so the added 0 counts  
     187                        //just need to be smaller than the length of one sequence  
     188                        if(pattern.getFirstSequence().eventCount(0) + pattern.getSecondSequence().eventCount(0) +1 > pattern.getFirstSequence().size()) 
     189                                continue; 
    181190                        Console.traceln(Level.FINEST, "searching for patterns occuring most: " + Math.round((float)i/(float)matchseqs.size()*100) + "%"); 
    182                         for(int j=0; j < matchseqs.size();j++) { 
    183                                 if(i>j) { 
    184                                         if(matchseqs.get(j).get(0).containsPattern(matchseqs.get(i)) > 0 || matchseqs.get(j).get(1).containsPattern(matchseqs.get(i)) > 0) { 
    185                                                 occurencecount++; 
     191                        for(int j=0; j < numberseqs.size();j++) { 
     192                                        int tmpcount = numberseqs.get(j).containsPattern(pattern); 
     193                                        if(tmpcount > 0) { 
     194                                                sequencecount++; 
     195                                                totalcount+=tmpcount; 
    186196                                        } 
    187                                 } 
    188                         } 
    189                         if(occurencecount > 1) { 
    190                                 System.out.println("Found pattern \n ");  
    191                                 matchseqs.get(i).get(0).printSequence();  
    192                                 matchseqs.get(i).get(1).printSequence();  
    193                                 System.out.println(occurencecount + " times"); 
     197                        } 
     198                         
     199                        if(totalcount > 1) { 
     200                                matchseqs.get(i).getFirstSequence().printSequence();  
     201                                matchseqs.get(i).getFirstSequence().printSequence(); 
     202                                System.out.println("Found pattern in " + sequencecount +"/" + numberseqs.size() + " sequences, total of " + totalcount + " occurences"); 
    194203                                System.out.println(); 
    195204                        } 
    196205                } 
    197                  
    198                  
    199                  
    200206                alignments = null; 
    201207                 
    … …  
    290296                                } 
    291297                        } 
     298                        templist.setId(numberseqs.size()); 
    292299                        numberseqs.add(templist); 
    293300                        comparator.clearBuffers(); 
Note: See TracChangeset for help on using the changeset viewer.