Index: trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/DefaultTaskSequenceDetectionRule.java =================================================================== --- trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/DefaultTaskSequenceDetectionRule.java (revision 1117) +++ trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/DefaultTaskSequenceDetectionRule.java (revision 1119) @@ -15,5 +15,4 @@ package de.ugoe.cs.autoquest.tasktrees.temporalrelation; -import java.util.Collection; import java.util.Iterator; import java.util.LinkedList; @@ -28,4 +27,5 @@ import de.ugoe.cs.autoquest.usageprofiles.SymbolComparator; import de.ugoe.cs.autoquest.usageprofiles.Trie; +import de.ugoe.cs.autoquest.usageprofiles.TrieProcessor; /** @@ -78,4 +78,12 @@ } + /* (non-Javadoc) + * @see java.lang.Object#toString() + */ + @Override + public String toString() { + return "DefaultTaskSequenceDetectionRule"; + } + /* * (non-Javadoc) @@ -97,77 +105,136 @@ } - long timestamp1; - long timestamp2 = System.currentTimeMillis(); - long ms1 = 0; - long ms2 = 0; - long ms3 = 0; - long ms4 = 0; - - List createdSequences = new LinkedList(); - - int evisagedNoOfOccurrences = 0; + RuleApplicationData appData = new RuleApplicationData(parent); + + appData.getStopWatch().start("whole rule application"); do { - timestamp1 = timestamp2; - Trie trie = new Trie(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> tasks = - trie.getSequencesWithOccurrenceCount(2, evisagedNoOfOccurrences); - - tasks = sortAndRemovePermutationsOfShorterTasks(tasks); - - timestamp2 = System.currentTimeMillis(); - ms2 += timestamp2 - timestamp1; - timestamp1 = timestamp2; - - if ((tasks != null) && (tasks.size() > 0)) { - Iterator> tasksIterator = tasks.iterator(); - - while (tasksIterator.hasNext()) { - List 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 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(); + } + + /** + *

+ * TODO: comment + *

+ * + * @param i + * @return + */ + private void getSequencesOccuringMostOften(RuleApplicationData appData) { + System.out.println("determining most prominent tasks with a maximum of " + + (appData.getLastFoundSequences().getOccurrenceCount() - 1) + + " occurrences"); + + Sequences 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 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); + } + + /** + *

+ * TODO: comment + *

+ * + * @param parent + * @return + */ + private void createNewTrie(RuleApplicationData appData) { + System.out.println("training trie with a maximum sequence length of " + + appData.getTrainedSequenceLength()); + + appData.getStopWatch().start("training trie"); + appData.setLastTrie(new Trie(nodeComparator)); + + trainTrie(appData.getTree(), appData); + appData.getStopWatch().stop("training trie"); } @@ -180,68 +247,23 @@ * @param parent */ - private void trainTrie(Trie trie, - ITaskTreeNode parent, - List createdSequences) - { - List children = parent.getChildren(); - - if ((children != null) && (children.size() > 0)) { - trie.train(children, children.size()); - - for (ITaskTreeNode child : children) { - trainTrie(trie, child, createdSequences); - } - } - } - - /** - * - */ - private List> - sortAndRemovePermutationsOfShorterTasks(Collection> tasks) - { - // first of all create a sorted list of the tasks with the longest first - List> sortedTasks = new LinkedList>(); - - boolean added; - for (List 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 longTask = sortedTasks.get(i); - List 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 appData) { + // prevent training of already replaces sequences as those shall not be replaced anymore + if (!appData.getResult().getNewlyCreatedParentNodes().contains(parent)) { + List 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,8 +279,8 @@ * @param result */ - private void createSequenceForTaskOccurrences(String taskId, - List task, - ITaskTreeNode parent, - List createdSequences) + private void createSequenceForTaskOccurrences(String taskId, + List task, + ITaskTreeNode parent, + RuleApplicationData appData) { List children = parent.getChildren(); @@ -270,5 +292,5 @@ // first traverse the children for (ITaskTreeNode child : children) { - createSequenceForTaskOccurrences(taskId, task, child, createdSequences); + createSequenceForTaskOccurrences(taskId, task, child, appData); } @@ -285,5 +307,6 @@ taskTreeNodeFactory, taskTreeBuilder); - createdSequences.add(sequence); + appData.getResult().addNewlyCreatedParentNode(sequence); + appData.incrementReplacementCounter(); children = parent.getChildren(); @@ -333,4 +356,7 @@ break; } + else if (!nodeComparator.equals(subList.get(j), list.get(i + j))){ + throw new RuntimeException("comparator not commutative"); + } } @@ -344,3 +370,341 @@ } + /** + *

+ * TODO comment + *

+ * + * @author Patrick Harms + */ + private class MaxCountAndLongestSequenceFinder implements TrieProcessor { + + /** + * + */ + private int maxCount; + + /** + * + */ + private int currentCount; + + /** + * + */ + private List> foundSequences = new LinkedList>(); + + /** + *

+ * TODO: comment + *

+ * + * @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 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(sequence)); // defensive copy + added = true; + break; + } + } + + if (!added) { + foundSequences.add(new LinkedList(sequence)); // defensive copy + } + } + + return TrieProcessor.Result.CONTINUE; + } + + /** + *

+ * TODO: comment + *

+ * + * @return + */ + public Sequences getFoundSequences() { + removePermutationsOfShorterTasks(); + return new Sequences(currentCount, foundSequences); + } + + /** + *

+ * TODO: comment + *

+ * + */ + 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 longTask = foundSequences.get(i); + List shortTask = foundSequences.get(j); + + if (getSubListIndex(longTask, shortTask, 0) > -1) { + foundSequences.remove(j); + } + else { + j++; + } + } + else { + j++; + } + } + } + } + + } + + /** + * + */ + private class RuleApplicationData { + + /** + * + */ + private T tree; + + /** + * + */ + private RuleApplicationResult result = new RuleApplicationResult(); + + /** + * + */ + private Sequences lastFoundSequences = new Sequences(Integer.MAX_VALUE, null); + + /** + * + */ + private Trie 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 getLastFoundSequences() { + return lastFoundSequences; + } + + /** + * @param lastFoundSequences the lastFoundSequences to set + */ + private void setLastFoundSequences(Sequences lastFoundSequences) { + this.lastFoundSequences = lastFoundSequences; + } + + /** + * @return the lastTrie + */ + private Trie 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 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; + } + } + + + /** + *

+ * TODO comment + *

+ * + * @author Patrick Harms + */ + private class Sequences implements Iterable> { + + /** + * + */ + private int occurrenceCount; + + /** + * + */ + private List> sequences; + + /** + *

+ * TODO: comment + *

+ * + * @param occurrenceCount + * @param sequences + */ + private Sequences(int occurrenceCount, List> sequences) { + super(); + this.occurrenceCount = occurrenceCount; + this.sequences = sequences; + } + + /** + *

+ * TODO: comment + *

+ * + * @return + */ + private int getOccurrenceCount() { + return occurrenceCount; + } + + /** + *

+ * TODO: comment + *

+ * + * @return + */ + private int size() { + return this.sequences.size(); + } + + /** + * + */ + + /* (non-Javadoc) + * @see java.lang.Iterable#iterator() + */ + @Override + public Iterator> iterator() { + return this.sequences.iterator(); + } + + } + } Index: trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/StopWatch.java =================================================================== --- trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/StopWatch.java (revision 1119) +++ trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/StopWatch.java (revision 1119) @@ -0,0 +1,191 @@ +// Copyright 2012 Georg-August-Universität Göttingen, Germany +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +package de.ugoe.cs.autoquest.tasktrees.temporalrelation; + +import java.io.PrintStream; +import java.text.DecimalFormat; +import java.util.HashMap; +import java.util.LinkedList; +import java.util.List; +import java.util.Map; + +/** + *

+ * TODO comment + *

+ * + * @author Patrick Harms + */ +public class StopWatch { + + /** + * + */ + private Map> mWatches = new HashMap>(); + + /** + * + * + * @param id + */ + public void start(String id) { + List timeStamps = mWatches.get(id); + + if (timeStamps == null) { + timeStamps = new LinkedList(); + mWatches.put(id, timeStamps); + } + + if (timeStamps.size() % 2 == 0) { + timeStamps.add(System.currentTimeMillis()); + } + else { + throw new IllegalStateException("watch with id " + id + " already running"); + } + } + + /** + * + * + * @param id + */ + public void stop(String id) { + List timeStamps = mWatches.get(id); + + if (timeStamps == null) { + throw new IllegalArgumentException("watch with id " + id + " does not exist"); + } + + if (timeStamps.size() % 2 == 0) { + throw new IllegalStateException("watch with id " + id + " already stopped"); + } + else { + timeStamps.add(System.currentTimeMillis()); + } + } + + /** + * + * + * @param id + */ + public long getDuration(String id) { + List timeStamps = mWatches.get(id); + + if (timeStamps == null) { + throw new IllegalArgumentException("watch with id " + id + " does not exist"); + } + + if (timeStamps.size() % 2 != 0) { + stop(id); + } + + long result = 0; + for (long timeStamp : timeStamps) { + if (result >= 0) { + result -= timeStamp; + } + else { + result += timeStamp; + } + } + + return result; + } + + /** + * + * @param out + */ + public void dumpStatistics(PrintStream out) { + if (mWatches.size() <= 0) { + throw new IllegalStateException("no watches registered that could be dumped"); + } + + Map durations = new HashMap(); + + // get durations + for (String id : mWatches.keySet()) { + durations.put(id, getDuration(id)); + } + + // sort by duration + List sortedIds = new LinkedList(); + int maxIdLength = 0; + + for (Map.Entry entry : durations.entrySet()) { + boolean added = false; + for (int i = 0; i < sortedIds.size(); i++) { + if (durations.get(sortedIds.get(i)) >= entry.getValue()) { + sortedIds.add(i, entry.getKey()); + added = true; + break; + } + } + + if (!added) { + sortedIds.add(entry.getKey()); + } + + maxIdLength = Math.max(maxIdLength, entry.getKey().length()); + } + + // get longest duration and check whether it spans all other entries + String id = sortedIds.get(sortedIds.size() - 1); + List timeStamps = mWatches.get(id); + long firstTimeStamp = timeStamps.get(0); + long lastTimeStamp = timeStamps.get(timeStamps.size() - 1); + long longestDuration = durations.get(id); + boolean longestDurationCoversOthers = true; + + for (Map.Entry> watch : mWatches.entrySet()) { + if ((watch.getValue().get(0) < firstTimeStamp) || + (watch.getValue().get(watch.getValue().size() - 1) > lastTimeStamp)) + { + longestDurationCoversOthers = false; + break; + } + } + + // no finally start the dumping + out.println(); + out.println("Watch Statistics"); + out.println("================"); + + for (String sortedId : sortedIds) { + out.print(sortedId); + + for (int i = sortedId.length(); i <= maxIdLength; i++) { + out.print(' '); + } + + out.print(':'); + out.print(' '); + + out.print(durations.get(sortedId)); + out.print(" ms"); + + if (longestDurationCoversOthers) { + out.print(" ("); + out.print(DecimalFormat.getPercentInstance().format + ((double) durations.get(sortedId) / longestDuration)); + out.print(" of overall duration)"); + } + out.println(); + } + + out.println(); + } +} Index: trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/TreeScopeWrapperRule.java =================================================================== --- trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/TreeScopeWrapperRule.java (revision 1119) +++ trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/TreeScopeWrapperRule.java (revision 1119) @@ -0,0 +1,111 @@ +// Copyright 2012 Georg-August-Universität Göttingen, Germany +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +package de.ugoe.cs.autoquest.tasktrees.temporalrelation; + +import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskTreeNode; + +/** + * This rule applies a node scope rule (working only in the scope of the provided parent node) + * as a tree scope rule, i.e. it applies the provided wrapped rule recursively on the subtree + * provided by the parent node. It traverses the nodes in post order. + * + * @author 2013, last modified by $Author: patrick$ + */ +class TreeScopeWrapperRule implements TemporalRelationshipRule { + + /** + *

+ * the node scope rule wrapped by this wrapper + *

+ */ + private TemporalRelationshipRule rule; + + /** + *

+ * instantiates the wrapper with the rule to be wrapped + *

+ * + * @param rule the rule to be wrapped and applied recursively + */ + TreeScopeWrapperRule(TemporalRelationshipRule rule) { + if (rule == null) { + throw new IllegalArgumentException("rule must not be null"); + } + + this.rule = rule; + } + + /* (non-Javadoc) + * @see java.lang.Object#toString() + */ + @Override + public String toString() { + return this.rule.toString() + " (tree scope)"; + } + + /* + * (non-Javadoc) + * + * @see de.ugoe.cs.tasktree.temporalrelation.TemporalRelationshipRule#apply(TaskTreeNode, + * boolean) + */ + @Override + public RuleApplicationResult apply(ITaskTreeNode parent, boolean finalize) { + RuleApplicationResult result = null; + + if (parent != null) { + result = new RuleApplicationResult(); + + if (parent.getChildren() != null) { + for (ITaskTreeNode child : parent.getChildren()) { + merge(result, apply(child, finalize)); + } + } + + merge(result, rule.apply(parent, finalize)); + } + + return result; + } + + /** + *

+ * merges the overall rule application result with an intermediate result + *

+ * + * @param overallResult the current overall result + * @param intermediate the intermediate result to be merged into the overall result + */ + private void merge(RuleApplicationResult overallResult, RuleApplicationResult intermediate) { + if (intermediate == null) { + return; + } + + RuleApplicationStatus overallStatus = overallResult.getRuleApplicationStatus(); + RuleApplicationStatus intermediateStatus = intermediate.getRuleApplicationStatus(); + + if ((intermediateStatus == RuleApplicationStatus.RULE_APPLICATION_FINISHED) || + ((intermediateStatus == RuleApplicationStatus.RULE_APPLICATION_FEASIBLE) && + (overallStatus == RuleApplicationStatus.RULE_NOT_APPLIED))) + { + overallResult.setRuleApplicationStatus(intermediateStatus); + } + + for (ITaskTreeNode newlyCreatedNode : intermediate.getNewlyCreatedParentNodes()) { + overallResult.addNewlyCreatedParentNode(newlyCreatedNode); + } + } + +}