Changeset 1119

Timestamp:

03/06/13 23:39:45 (12 years ago)

Author:

pharms

Message:

• improved and corrected task detection

Location:

trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation

Files:

• DefaultTaskSequenceDetectionRule.java (modified) (10 diffs)
• StopWatch.java (added)
• TreeScopeWrapperRule.java (added)

trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/DefaultTaskSequenceDetectionRule.java

@@ -15 +15 @@
 package de.ugoe.cs.autoquest.tasktrees.temporalrelation;
 
-import java.util.Collection;
 import java.util.Iterator;
 import java.util.LinkedList;
@@ -28 +27 @@
 import de.ugoe.cs.autoquest.usageprofiles.SymbolComparator;
 import de.ugoe.cs.autoquest.usageprofiles.Trie;
+import de.ugoe.cs.autoquest.usageprofiles.TrieProcessor;
 
 /**
@@ -78 +78 @@
     }
 
+    /* (non-Javadoc)
+     * @see java.lang.Object#toString()
+     */
+    @Override
+    public String toString() {
+        return "DefaultTaskSequenceDetectionRule";
+    }
+
     /*
      * (non-Javadoc)
@@ -97 +105 @@
         }
 
-        long timestamp1;
-        long timestamp2 = System.currentTimeMillis();
-        long ms1 = 0;
-        long ms2 = 0;
-        long ms3 = 0;
-        long ms4 = 0;
-        
-        List<ISequence> createdSequences = new LinkedList<ISequence>();
-        
-        int evisagedNoOfOccurrences = 0;
+        RuleApplicationData<ITaskTreeNode> appData = new RuleApplicationData<ITaskTreeNode>(parent);
+        
+        appData.getStopWatch().start("whole rule application");
         
         do {
-            timestamp1 = timestamp2;
-            Trie<ITaskTreeNode> trie = new Trie<ITaskTreeNode>(nodeComparator);
-        
-            System.out.println("training trie");
-            trainTrie(trie, parent, createdSequences);
-
-            timestamp2 = System.currentTimeMillis();
-            ms1 += timestamp2 - timestamp1;
-            timestamp1 = timestamp2;
-
-            System.out.println("determining most prominent tasks");
-            Collection<List<ITaskTreeNode>> tasks =
-                trie.getSequencesWithOccurrenceCount(2, evisagedNoOfOccurrences);
-            
-            tasks = sortAndRemovePermutationsOfShorterTasks(tasks); 
-        
-            timestamp2 = System.currentTimeMillis();
-            ms2 += timestamp2 - timestamp1;
-            timestamp1 = timestamp2;
-
-            if ((tasks != null) && (tasks.size() > 0)) {
-                Iterator<List<ITaskTreeNode>> tasksIterator = tasks.iterator();
-                
-                while (tasksIterator.hasNext()) {
-                    List<ITaskTreeNode> task = tasksIterator.next();
-                    evisagedNoOfOccurrences = trie.getCount(task);
-
+            getSequencesOccuringMostOften(appData);
+            
+            if ((appData.getLastFoundSequences().size() > 0) &&
+                (appData.getLastFoundSequences().getOccurrenceCount() > 1))
+            {
+                System.out.println("found " + appData.getLastFoundSequences().size() +
+                                   " tasks occurring " +
+                                   appData.getLastFoundSequences().getOccurrenceCount() + " times");
+
+                for (List<ITaskTreeNode> task : appData.getLastFoundSequences()) {
                     // only tasks occurring more often than once are of interest
-                    if (evisagedNoOfOccurrences > 1) {
-                        timestamp2 = System.currentTimeMillis();
-                        ms3 += timestamp2 - timestamp1;
-                        timestamp1 = timestamp2;
-
-                        String taskId = "task " + RuleUtils.getNewId();
-                        System.out.println("creating sequences for task " + taskId + ": " + task);
-                        createSequenceForTaskOccurrences(taskId, task, parent, createdSequences);
-
-                        timestamp2 = System.currentTimeMillis();
-                        ms4 += timestamp2 - timestamp1;
-                        timestamp1 = timestamp2;
+                    appData.stopWatch.start("creating task sequences");
+
+                    String taskId = "task " + RuleUtils.getNewId();
+                    System.out.println(taskId + ": " + task);
+                    
+                    appData.resetReplacementCounter();
+                    createSequenceForTaskOccurrences(taskId, task, parent, appData);
+                    
+                    if (appData.getReplacementCounter() <
+                        appData.getLastFoundSequences().getOccurrenceCount())
+                    {
+                        System.out.println(taskId + ": replaced task only " +
+                                           appData.getReplacementCounter() +
+                                           " times instead of expected " +
+                                           appData.getLastFoundSequences().getOccurrenceCount());
+                        
                     }
-                }
-            }
-            
-            evisagedNoOfOccurrences--;
-        }
-        while (evisagedNoOfOccurrences > 1);
-        
-        System.out.println(ms1 + "   " + ms2 + "   " + ms3 + "   " + ms4);
-        RuleApplicationResult result = new RuleApplicationResult();
-        
-        if (createdSequences.size() > 0) {
-            for (ISequence sequence : createdSequences) {
-                result.addNewlyCreatedParentNode(sequence);
-            }
-            
-            result.setRuleApplicationStatus(RuleApplicationStatus.RULE_APPLICATION_FINISHED);
-        }
-
-        
-        return result;
+
+                    appData.stopWatch.stop("creating task sequences");
+                }
+            }
+            
+        }
+        while (appData.getLastFoundSequences().getOccurrenceCount() > 2);
+        
+        appData.getStopWatch().stop("whole rule application");
+        appData.getStopWatch().dumpStatistics(System.out);
+        
+        if (appData.getResult().getNewlyCreatedParentNodes().size() > 0) {
+            appData.getResult().setRuleApplicationStatus
+                (RuleApplicationStatus.RULE_APPLICATION_FINISHED);
+        }
+        
+        System.out.println(appData.getResult().getNewlyCreatedParentNodes().size());
+        
+        for (ITaskTreeNode node : appData.getResult().getNewlyCreatedParentNodes()) {
+            for (ITaskTreeNode child : node.getChildren()) {
+                System.out.println(child);
+            }
+            System.out.println();
+        }
+        
+        return appData.getResult();
+    }
+
+    /**
+     * <p>
+     * TODO: comment
+     * </p>
+     *
+     * @param i
+     * @return
+     */
+    private void getSequencesOccuringMostOften(RuleApplicationData<ITaskTreeNode> appData) {
+        System.out.println("determining most prominent tasks with a maximum of " +
+                           (appData.getLastFoundSequences().getOccurrenceCount() - 1) +
+                           " occurrences");
+
+        Sequences<ITaskTreeNode> sequences;
+        boolean createNewTrie = (appData.getLastTrie() == null) ||
+            appData.getReplacementCounter() > 0; // tree has changed
+        
+        do {
+            if (createNewTrie) {
+                createNewTrie(appData);
+            }
+            
+            /*PathDumper dumper = new PathDumper();
+            trie.process(dumper);
+        
+            dumper.dump();*/
+        
+            appData.getStopWatch().start("determining tasks");
+
+            MaxCountAndLongestSequenceFinder finder = new MaxCountAndLongestSequenceFinder
+                  (appData.getLastFoundSequences().getOccurrenceCount() - 1);
+            appData.getLastTrie().process(finder);
+        
+            sequences = finder.getFoundSequences();
+            
+            createNewTrie = false;
+            
+            for (List<ITaskTreeNode> task : sequences) {
+                if (task.size() >= appData.getTrainedSequenceLength()) {
+                    // Trie must be recreated with a longer sequence length to be sure that
+                    // the found sequences occurring most often are found in their whole length
+                    appData.setTrainedSequenceLength(appData.getTrainedSequenceLength() + 1);
+                    createNewTrie = true;
+                    break;
+                }
+            }
+            
+            appData.getStopWatch().stop("determining tasks");
+        }
+        while (createNewTrie);
+        
+        appData.setLastFoundSequences(sequences);
+    }
+
+    /**
+     * <p>
+     * TODO: comment
+     * </p>
+     *
+     * @param parent
+     * @return
+     */
+    private void createNewTrie(RuleApplicationData<ITaskTreeNode> appData) {
+        System.out.println("training trie with a maximum sequence length of " +
+                           appData.getTrainedSequenceLength());
+
+        appData.getStopWatch().start("training trie");
+        appData.setLastTrie(new Trie<ITaskTreeNode>(nodeComparator));
+    
+        trainTrie(appData.getTree(), appData);
+        appData.getStopWatch().stop("training trie");
     }
 
@@ -180 +247 @@
      * @param parent
      */
-    private void trainTrie(Trie<ITaskTreeNode> trie,
-                           ITaskTreeNode       parent,
-                           List<ISequence>     createdSequences)
-    {
-        List<ITaskTreeNode> children = parent.getChildren();
-        
-        if ((children != null) && (children.size() > 0)) {
-            trie.train(children, children.size());
-            
-            for (ITaskTreeNode child : children) {
-                trainTrie(trie, child, createdSequences);
-            }
-        }
-    }
-
-    /**
-     *
-     */
-    private List<List<ITaskTreeNode>>
-        sortAndRemovePermutationsOfShorterTasks(Collection<List<ITaskTreeNode>> tasks)
-    {
-        // first of all create a sorted list of the tasks with the longest first
-        List<List<ITaskTreeNode>> sortedTasks = new LinkedList<List<ITaskTreeNode>>();
-        
-        boolean added;
-        for (List<ITaskTreeNode> task : tasks) {
-            added = false;
-            for (int i = 0; i < sortedTasks.size(); i++) {
-                if (sortedTasks.get(i).size() < task.size()) {
-                    sortedTasks.add(i, task);
-                    added = true;
-                    break;
-                }
-            }
-            
-            if (!added) {
-                sortedTasks.add(task);
-            }
-        }
-        
-        // now iterate the sorted list and for each task remove all other tasks that are shorter
-        // (i.e. come later in the sorted list) and that represent a subpart of the task
-        for (int i = 0; i < sortedTasks.size(); i++) {
-            for (int j = i + 1; j < sortedTasks.size();) {
-                if (sortedTasks.get(j).size() < sortedTasks.get(i).size()) {
-                    // found a task that is a potential subtask. Check for this and remove the
-                    // subtask if needed
-                    List<ITaskTreeNode> longTask = sortedTasks.get(i);
-                    List<ITaskTreeNode> shortTask = sortedTasks.get(j);
-                    
-                    if (getSubListIndex(longTask, shortTask, 0) > -1) {
-                        sortedTasks.remove(j);
-                    }
-                    else {
-                        j++;
-                    }
-                }
-                else {
-                    j++;
-                }
-            }
-        }
-        
-        return sortedTasks;
+    private void trainTrie(ITaskTreeNode parent, RuleApplicationData<ITaskTreeNode> appData) {
+        // prevent training of already replaces sequences as those shall not be replaced anymore
+        if (!appData.getResult().getNewlyCreatedParentNodes().contains(parent)) {
+            List<ITaskTreeNode> children = parent.getChildren();
+        
+            if ((children != null) && (children.size() > 0)) {
+                
+                /*System.out.println();
+                for (int i = 0; i < children.size(); i++) {
+                    System.out.println(children.get(i));
+                }*/
+                
+                appData.getLastTrie().train(children, appData.getTrainedSequenceLength());
+            
+                for (ITaskTreeNode child : children) {
+                    trainTrie(child, appData);
+                }
+            }
+        }
     }
 
@@ -257 +279 @@
      * @param result
      */
-    private void createSequenceForTaskOccurrences(String              taskId,
-                                                  List<ITaskTreeNode> task,
-                                                  ITaskTreeNode       parent,
-                                                  List<ISequence>     createdSequences)
+    private void createSequenceForTaskOccurrences(String                             taskId,
+                                                  List<ITaskTreeNode>                task,
+                                                  ITaskTreeNode                      parent,
+                                                  RuleApplicationData<ITaskTreeNode> appData)
     {
         List<ITaskTreeNode> children = parent.getChildren();
@@ -270 +292 @@
         // first traverse the children
         for (ITaskTreeNode child : children) {
-            createSequenceForTaskOccurrences(taskId, task, child, createdSequences);
+            createSequenceForTaskOccurrences(taskId, task, child, appData);
         }
         
@@ -285 +307 @@
                          taskTreeNodeFactory, taskTreeBuilder);
                     
-                    createdSequences.add(sequence);
+                    appData.getResult().addNewlyCreatedParentNode(sequence);
+                    appData.incrementReplacementCounter();
                  
                     children = parent.getChildren();
@@ -333 +356 @@
                     break;
                 }
+                else if (!nodeComparator.equals(subList.get(j), list.get(i + j))){
+                    throw new RuntimeException("comparator not commutative");
+                }
             }
             
@@ -344 +370 @@
     }
     
+    /**
+     * <p>
+     * TODO comment
+     * </p>
+     * 
+     * @author Patrick Harms
+     */
+    private class MaxCountAndLongestSequenceFinder implements TrieProcessor<ITaskTreeNode> {
+        
+        /**
+         * 
+         */
+        private int maxCount;
+        
+        /**
+         * 
+         */
+        private int currentCount;
+        
+        /**
+         * 
+         */
+        private List<List<ITaskTreeNode>> foundSequences = new LinkedList<List<ITaskTreeNode>>();
+
+        /**
+         * <p>
+         * TODO: comment
+         * </p>
+         *
+         * @param maxCount
+         */
+        public MaxCountAndLongestSequenceFinder(int maxCount) {
+            super();
+            this.maxCount = maxCount;
+            this.currentCount = 0;
+        }
+
+        /* (non-Javadoc)
+         * @see de.ugoe.cs.autoquest.usageprofiles.TrieProcessor#process(java.util.List, int)
+         */
+        @Override
+        public TrieProcessor.Result process(List<ITaskTreeNode> sequence, int count) {
+            if (sequence.size() < 2) {
+                // ignore single nodes
+                return TrieProcessor.Result.CONTINUE;
+            }
+            
+            if (count < 2) {
+                // ignore singular occurrences
+                return TrieProcessor.Result.SKIP_NODE;
+            }
+
+            if (count > this.maxCount) {
+                // ignore sequences that occur too often
+                return TrieProcessor.Result.CONTINUE;
+            }
+            
+            if (this.currentCount > count) {
+                // ignore this children of this node, as they may have only smaller counts than
+                // the already found sequences
+                return TrieProcessor.Result.SKIP_NODE;
+            }
+            
+            if (this.currentCount < count) {
+                // the provided sequence occurs more often that all sequences found so far.
+                // clear all found sequences and use the new count as the one searched for
+                foundSequences.clear();
+                this.currentCount = count;
+            }
+            
+            if (this.currentCount == count) {
+                // the sequence is of interest. Sort it into the other found sequences so that
+                // the longest come first
+                boolean added = false;
+                for (int i = 0; i < foundSequences.size(); i++) {
+                    if (foundSequences.get(i).size() < sequence.size()) {
+                        // defensive copy
+                        foundSequences.add(i, new LinkedList<ITaskTreeNode>(sequence)); // defensive copy
+                        added = true;
+                        break;
+                    }
+                }
+                
+                if (!added) {
+                    foundSequences.add(new LinkedList<ITaskTreeNode>(sequence)); // defensive copy
+                }
+            }
+            
+            return TrieProcessor.Result.CONTINUE;
+        }
+
+        /**
+         * <p>
+         * TODO: comment
+         * </p>
+         *
+         * @return
+         */
+        public Sequences<ITaskTreeNode> getFoundSequences() {
+            removePermutationsOfShorterTasks();
+            return new Sequences<ITaskTreeNode>(currentCount, foundSequences);
+        }
+
+        /**
+         * <p>
+         * TODO: comment
+         * </p>
+         *
+         */
+        private void removePermutationsOfShorterTasks() {
+            // now iterate the sorted list and for each task remove all other tasks that are shorter
+            // (i.e. come later in the sorted list) and that represent a subpart of the task
+            for (int i = 0; i < foundSequences.size(); i++) {
+                for (int j = i + 1; j < foundSequences.size();) {
+                    if (foundSequences.get(j).size() < foundSequences.get(i).size()) {
+                        // found a task that is a potential subtask. Check for this and remove the
+                        // subtask if needed
+                        List<ITaskTreeNode> longTask = foundSequences.get(i);
+                        List<ITaskTreeNode> shortTask = foundSequences.get(j);
+                        
+                        if (getSubListIndex(longTask, shortTask, 0) > -1) {
+                            foundSequences.remove(j);
+                        }
+                        else {
+                            j++;
+                        }
+                    }
+                    else {
+                        j++;
+                    }
+                }
+            }
+        }
+
+    }
+    
+    /**
+     * 
+     */
+    private class RuleApplicationData<T> {
+        
+        /**
+         * 
+         */
+        private T tree;
+        
+        /**
+         * 
+         */
+        private RuleApplicationResult result = new RuleApplicationResult();
+        
+        /**
+         * 
+         */
+        private Sequences<T> lastFoundSequences = new Sequences<T>(Integer.MAX_VALUE, null);
+        
+        /**
+         * 
+         */
+        private Trie<T> lastTrie;
+        
+        /**
+         * default and minimum trained sequence length is 3
+         */
+        private int trainedSequenceLength = 3;
+        
+        /**
+         * 
+         */
+        private int replacementCounter;
+        
+        /**
+         * 
+         */
+        private StopWatch stopWatch = new StopWatch();
+        
+        /**
+         * 
+         */
+        private RuleApplicationData(T tree) {
+            this.tree = tree;
+        }
+
+        /**
+         * @return the lastFoundSequences
+         */
+        private Sequences<T> getLastFoundSequences() {
+            return lastFoundSequences;
+        }
+
+        /**
+         * @param lastFoundSequences the lastFoundSequences to set
+         */
+        private void setLastFoundSequences(Sequences<T> lastFoundSequences) {
+            this.lastFoundSequences = lastFoundSequences;
+        }
+
+        /**
+         * @return the lastTrie
+         */
+        private Trie<T> getLastTrie() {
+            return lastTrie;
+        }
+
+        /**
+         * @return the trainedSequenceLength
+         */
+        private int getTrainedSequenceLength() {
+            return trainedSequenceLength;
+        }
+
+        /**
+         * @param trainedSequenceLength the trainedSequenceLength to set
+         */
+        private void setTrainedSequenceLength(int trainedSequenceLength) {
+            this.trainedSequenceLength = trainedSequenceLength;
+        }
+
+        /**
+         * @param lastTrie the lastTrie to set
+         */
+        private void setLastTrie(Trie<T> lastTrie) {
+            this.lastTrie = lastTrie;
+        }
+
+        /**
+         * @return the tree
+         */
+        private T getTree() {
+            return tree;
+        }
+
+        /**
+         * @return the result
+         */
+        private RuleApplicationResult getResult() {
+            return result;
+        }
+
+        /**
+         * @return the stopWatch
+         */
+        private StopWatch getStopWatch() {
+            return stopWatch;
+        }
+
+        /**
+         *
+         */
+        private void resetReplacementCounter() {
+            replacementCounter = 0;
+        }
+
+        /**
+         *
+         */
+        private void incrementReplacementCounter() {
+            replacementCounter++;
+        }
+
+        /**
+         *
+         */
+        private int getReplacementCounter() {
+            return replacementCounter;
+        }
+    }
+    
+
+    /**
+     * <p>
+     * TODO comment
+     * </p>
+     * 
+     * @author Patrick Harms
+     */
+    private class Sequences<T> implements Iterable<List<T>> {
+        
+        /**
+         * 
+         */
+        private int occurrenceCount;
+        
+        /**
+         * 
+         */
+        private List<List<T>> sequences;
+
+        /**
+         * <p>
+         * TODO: comment
+         * </p>
+         *
+         * @param occurrenceCount
+         * @param sequences
+         */
+        private Sequences(int occurrenceCount, List<List<T>> sequences) {
+            super();
+            this.occurrenceCount = occurrenceCount;
+            this.sequences = sequences;
+        }
+
+        /**
+         * <p>
+         * TODO: comment
+         * </p>
+         *
+         * @return
+         */
+        private int getOccurrenceCount() {
+            return occurrenceCount;
+        }
+
+        /**
+         * <p>
+         * TODO: comment
+         * </p>
+         *
+         * @return
+         */
+        private int size() {
+            return this.sequences.size();
+        }
+
+        /**
+         * 
+         */
+
+        /* (non-Javadoc)
+         * @see java.lang.Iterable#iterator()
+         */
+        @Override
+        public Iterator<List<T>> iterator() {
+            return this.sequences.iterator();
+        }
+
+    }
+
 }