Index: /trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/SequenceForTaskDetectionRule.java
===================================================================
--- /trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/SequenceForTaskDetectionRule.java (revision 2130)
+++ /trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/SequenceForTaskDetectionRule.java (revision 2131)
@@ -29,4 +29,6 @@
import de.ugoe.cs.autoquest.tasktrees.taskequality.TaskEquality;
import de.ugoe.cs.autoquest.tasktrees.temporalrelation.utils.DebuggingHelper;
+import de.ugoe.cs.autoquest.tasktrees.treeifc.DefaultTaskInstanceTraversingVisitor;
+import de.ugoe.cs.autoquest.tasktrees.treeifc.IEventTaskInstance;
import de.ugoe.cs.autoquest.tasktrees.treeifc.IIteration;
import de.ugoe.cs.autoquest.tasktrees.treeifc.IIterationInstance;
@@ -102,4 +104,12 @@
/**
*
+ * the minimum number of event task instances a sequence must cover to still detect it as a
+ * representative task
+ *
+ */
+ private int minimumSequenceCoverage;;
+
+ /**
+ *
* instantiates the rule and initializes it with a task equality to be considered when
* comparing tasks as well as a task factory and builder to be used for creating task
@@ -107,14 +117,18 @@
*
*
- * @param minimalTaskEquality the task equality to be considered when comparing tasks
- * @param taskFactory the task factory to be used for creating substructures
- * @param taskBuilder the task builder to be used for creating substructures
+ * @param minimalTaskEquality the task equality to be considered when comparing tasks
+ * @param taskFactory the task factory to be used for creating substructures
+ * @param taskBuilder the task builder to be used for creating substructures
+ * @param minimumSequenceCoverage the minimum number of event task instances a sequence must
+ * cover to still detect it as a representative task
*/
SequenceForTaskDetectionRule(TaskEquality minimalTaskEquality,
ITaskFactory taskFactory,
- ITaskBuilder taskBuilder)
+ ITaskBuilder taskBuilder,
+ int minimumSequenceCoverage)
{
this.taskFactory = taskFactory;
this.taskBuilder = taskBuilder;
+ this.minimumSequenceCoverage = minimumSequenceCoverage;
this.preparationTaskHandlingStrategy = new TaskHandlingStrategy(minimalTaskEquality);
@@ -468,8 +482,16 @@
}
+ appData.getStopWatch().start("applying finder");
MaxCountAndLongestSubsequencesFinder finder = new MaxCountAndLongestSubsequencesFinder();
appData.getLastTrie().process(finder);
-
+ appData.getStopWatch().stop("applying finder");
+
+ appData.getStopWatch().start("remove permutations");
subsequences = finder.getFoundSubsequences();
+ appData.getStopWatch().stop("remove permutations");
+
+ appData.getStopWatch().start("drop unrepresentative");
+ dropUnrepresentative(subsequences, appData);
+ appData.getStopWatch().stop("drop unrepresentative");
createNewTrie = false;
@@ -549,4 +571,35 @@
" tasks occurring " +
appData.getLastFoundSubsequences().getOccurrenceCount() + " times");
+ }
+
+ /**
+ *
+ * TODO: comment
+ *
+ *
+ * @param subsequences
+ */
+ private void dropUnrepresentative(Subsequences subsequences, RuleApplicationData appData) {
+ Map> locations = getLocations(subsequences, appData);
+
+ for (Map.Entry> entry : locations.entrySet()) {
+ final int[] coveredActionInstances = new int[1];
+ for (SubsequenceLocation loc : entry.getValue()) {
+ for (int i = loc.getIndex(); i < loc.getIndex() + entry.getKey().size(); i++) {
+ ITaskInstance taskInstance = loc.getSession().get(i);
+
+ taskInstance.accept(new DefaultTaskInstanceTraversingVisitor() {
+ @Override
+ public void visit(IEventTaskInstance eventTaskInstance) {
+ coveredActionInstances[0]++;
+ }
+ });
+ }
+ }
+
+ if (coveredActionInstances[0] < minimumSequenceCoverage) {
+ subsequences.remove(entry.getKey());
+ }
+ }
}
@@ -1102,4 +1155,32 @@
}
+ // the remaining subsequences are interleaving the same amount of times, are
+ // used the same amount of times as successors and predecessors by all other
+ // detected interleaving subsequences, and their sum of the indexes of collisions
+ // is smallest or their collision index in all sessions is the smallest. This may
+ // happen for a subsequence aba for which there is an occurrence ababa. That is,
+ // the subsequence interleaves with itself. We can try to solve this by shortening
+ // the detected subsequence by one. Let us see, what happens.
+ /*boolean changedSubsequence = false;
+ for (InterleavingSubsequence interleaving : interleavings) {
+ if (interleaving.getSubsequence().size() > 2) {
+ appData.getLastFoundSubsequences().remove(interleaving.getSubsequence());
+ List shortenedSubsequence = new LinkedList<>();
+ for (int i = 0; i < interleaving.getSubsequence().size() - 1; i++) {
+ shortenedSubsequence.add(interleaving.getSubsequence().get(i));
+ }
+ appData.getLastFoundSubsequences().subsequences.add
+ (new Subsequence(interleaving.getSubsequence().occurrenceCount,
+ shortenedSubsequence));
+
+ changedSubsequence = true;
+ }
+ }
+
+ if (changedSubsequence) {
+ continue;
+ }*/
+
+
// At this point, we can not decide anymore. But it should also not
// happen. Even if two subsequences ab and ba one of them should be
@@ -1131,10 +1212,13 @@
RuleApplicationData appData)
{
+ appData.getStopWatch().start("determine interleavings");
List interleavings = new LinkedList();
List potentialPredecessors = new LinkedList();
List potentialSuccessors = new LinkedList();
+ appData.getStopWatch().start("determine locations");
Map> allLocations =
getLocations(subsequences, appData);
+ appData.getStopWatch().stop("determine locations");
for (Subsequence subsequence : subsequences) {
@@ -1154,11 +1238,10 @@
// subsequence is interleaving. First, determine its locations in the user sessions.
- List locations = allLocations.get(subsequence);
List precedingCollisions =
- getPrecedingCollisions(subsequence, locations, potentialPredecessors, appData);
+ getPrecedingCollisions(subsequence, potentialPredecessors, allLocations, appData);
List succeedingCollisions =
- getSucceedingCollisions(subsequence, locations, potentialSuccessors, appData);
+ getSucceedingCollisions(subsequence, potentialSuccessors, allLocations, appData);
if ((precedingCollisions.size() <= 0) && (succeedingCollisions.size() <= 0)) {
@@ -1171,4 +1254,5 @@
}
+ appData.getStopWatch().stop("determine interleavings");
return interleavings;
}
@@ -1219,4 +1303,5 @@
}
+ /*
LinkedList> candidates = new LinkedList>();
@@ -1266,4 +1351,76 @@
}
}
+ }*/
+
+ /*
+ for (IUserSession session : appData.getSessions()) {
+ LinkedList> candidateIterators = new LinkedList<>();
+ LinkedList candidates = new LinkedList<>();
+
+ for (int i = 0; i < session.size(); i++) {
+ ITask currentTask = session.get(i).getTask();
+
+ // create a list of candidates that may start here
+ for (Subsequence candidate : subsequences) {
+ if (candidate.get(0) == currentTask) {
+ candidates.add(candidate);
+ candidateIterators.add(candidate.iterator());
+ }
+ }
+
+ // check which candidates continue/end here.
+ ListIterator> candidateItsIt = candidateIterators.listIterator();
+ ListIterator candidatesIt = candidates.listIterator();
+ while (candidateItsIt.hasNext()) {
+ Iterator candidateIterator = candidateItsIt.next();
+ Subsequence candidate = candidatesIt.next();
+ if (candidateIterator.hasNext()) {
+ ITask expectedTask = candidateIterator.next();
+ if (expectedTask != currentTask) {
+ // remove the iterator and the candidate from both lists.
+ candidatesIt.remove();
+ candidateItsIt.remove();
+ }
+ // else leave iterator as is and continue
+ }
+ else {
+ // the candidate belonging to the iterator fully matched. Hence, store the
+ // location and drop the candidate and its iterator
+ candidatesIt.remove();
+ candidateItsIt.remove();
+
+ result.get(candidate).add
+ (new SubsequenceLocation(session, i - candidate.size()));
+ }
+ }
+ }
+
+ // check, which further iterators match with the session end.
+ ListIterator> candidateItsIt = candidateIterators.listIterator();
+ ListIterator candidatesIt = candidates.listIterator();
+ while (candidatesIt.hasNext()) {
+ Iterator candidateIterator = candidateItsIt.next();
+ Subsequence candidate = candidatesIt.next();
+ if (!candidateIterator.hasNext()) {
+ // the candidate belonging to the iterator fully matched. Hence, store the
+ // location and drop the candidate and its iterator
+ result.get(candidate).add
+ (new SubsequenceLocation(session, session.size() - candidate.size()));
+ }
+ }
+ }*/
+
+ for (IUserSession session : appData.getSessions()) {
+ for (Subsequence candidate : subsequences) {
+ int index = -1;
+ do {
+ index = getSubListIndex(session, candidate, index + 1);
+
+ if (index > -1) {
+ result.get(candidate).add(new SubsequenceLocation(session, index));
+ }
+ }
+ while (index > -1);
+ }
}
@@ -1274,23 +1431,18 @@
*
*/
- private List getPrecedingCollisions(Subsequence subsequence,
- List locations,
- List potentialPredecessors,
- RuleApplicationData appData)
+ private List getPrecedingCollisions
+ (Subsequence subsequence,
+ List potentialPredecessors,
+ Map> allLocations,
+ RuleApplicationData appData)
{
List precedingCollisions = new LinkedList();
- int interleavingStartIndex;
- int interleavingEndIndex;
-
- for (SubsequenceLocation location : locations) {
+
+ for (SubsequenceLocation location : allLocations.get(subsequence)) {
for (Subsequence predecessor : potentialPredecessors) {
- // start where the interleaving would start
- interleavingStartIndex = location.getIndex() - predecessor.size() + 1;
-
- if (interleavingStartIndex >= 0) {
- interleavingEndIndex =
- getSubListIndex(location.getSession(), predecessor, interleavingStartIndex);
-
- if (interleavingStartIndex == interleavingEndIndex) {
+ for (SubsequenceLocation predecessorLocation : allLocations.get(predecessor)) {
+ if ((location.getSession() == predecessorLocation.getSession()) &&
+ (location.getIndex() - predecessor.size() + 1 == predecessorLocation.getIndex()))
+ {
precedingCollisions.add(new Collision(location, subsequence, predecessor));
}
@@ -1305,21 +1457,20 @@
*
*/
- private List getSucceedingCollisions(Subsequence subsequence,
- List locations,
- List potentialPredecessors,
- RuleApplicationData appData)
+ private List getSucceedingCollisions
+ (Subsequence subsequence,
+ List potentialSuccessors,
+ Map> allLocations,
+ RuleApplicationData appData)
{
List succeedingCollisions = new LinkedList();
- int interleavingStartIndex;
- int interleavingEndIndex;
-
- for (SubsequenceLocation location : locations) {
- for (Subsequence successor : potentialPredecessors) {
- interleavingStartIndex = location.getIndex() + subsequence.size() - 1;
- interleavingEndIndex =
- getSubListIndex(location.getSession(), successor, interleavingStartIndex);
-
- if (interleavingStartIndex == interleavingEndIndex) {
- succeedingCollisions.add(new Collision(location, subsequence, successor));
+
+ for (SubsequenceLocation location : allLocations.get(subsequence)) {
+ for (Subsequence successor : potentialSuccessors) {
+ for (SubsequenceLocation successorLocation : allLocations.get(successor)) {
+ if ((location.getSession() == successorLocation.getSession()) &&
+ (location.getIndex() + subsequence.size() - 1 == successorLocation.getIndex()))
+ {
+ succeedingCollisions.add(new Collision(location, subsequence, successor));
+ }
}
}
@@ -1789,9 +1940,20 @@
if (this.currentCount == count) {
+ /*
+ // this is a potential performance improvement:
+ // the task is of interest. Ensure that only the longest remain
+ if ((foundSubsequences.size() > 0) &&
+ (foundSubsequences.get(0).size() < foundTask.size()))
+ {
+ foundSubsequences.clear();
+ }
+
+ foundSubsequences.add(new Subsequence(currentCount, foundTask));*/
+
// the task is of interest. Sort it into the other found tasks so that
// the longest come first
boolean added = false;
for (int i = 0; i < foundSubsequences.size(); i++) {
- if (foundSubsequences.get(i).size() < foundTask.size()) {
+ if (foundSubsequences.get(i).size() <= foundTask.size()) {
foundSubsequences.add(i, new Subsequence(currentCount, foundTask));
added = true;
@@ -1823,18 +1985,22 @@
// (i.e. come later in the sorted list) and that represent a subpart of the task
- boolean removeI;
-
- for (int i = 0; i < foundSubsequences.size();) {
- removeI = false;
- boolean removeJ;
-
- for (int j = i + 1; j < foundSubsequences.size();) {
- removeJ = false;
+ boolean removeFirst;
+ ListIterator iterator1 = foundSubsequences.listIterator();
+
+ while (iterator1.hasNext()) {
+ removeFirst = false;
+ boolean removeSecond;
+ Subsequence longTask = iterator1.next();
+
+ ListIterator iterator2 =
+ foundSubsequences.listIterator(iterator1.nextIndex());
+
+ while (iterator2.hasNext()) {
+ removeSecond = false;
+ Subsequence shortTask = iterator2.next();
- if (foundSubsequences.get(j).size() < foundSubsequences.get(i).size()) {
+ if (shortTask.size() < longTask.size()) {
// found a task that is a potential subtask. Check for this and remove the
// subtask if needed
- Subsequence longTask = foundSubsequences.get(i);
- Subsequence shortTask = foundSubsequences.get(j);
int index = getSubListIndex(longTask, shortTask, 0);
@@ -1860,5 +2026,5 @@
// Console.traceln(Level.FINEST, "short: " + toPlainStr(shortTask));
// Console.traceln(Level.FINEST, "long: " + toPlainStr(longTask));
- removeI = true;
+ removeFirst = true;
}
else {
@@ -1866,5 +2032,5 @@
// Console.traceln(Level.FINEST, "short: " + toPlainStr(shortTask));
// Console.traceln(Level.FINEST, "long: " + toPlainStr(longTask));
- removeJ = true;
+ removeSecond = true;
}
}
@@ -1873,22 +2039,22 @@
// Console.traceln(Level.FINEST, "short: " + toPlainStr(shortTask));
// Console.traceln(Level.FINEST, "long: " + toPlainStr(longTask));
- removeJ = true;
+ removeSecond = true;
}
}
}
- if (removeJ) {
- foundSubsequences.remove(j);
- }
- else {
- j++;
- }
- }
-
- if (removeI) {
- foundSubsequences.remove(i);
- }
- else {
- i++;
+ if (removeSecond) {
+ // unfortunately, this invalidates the first iterator. So recreate it after
+ // the removal. As the removed element will be after the current position of
+ // the first iterator, it is sufficient to remember its location
+ int indexOf1 = iterator1.nextIndex() - 1;
+ iterator2.remove();
+ iterator1 = foundSubsequences.listIterator(indexOf1);
+ iterator1.next();
+ }
+ }
+
+ if (removeFirst) {
+ iterator1.remove();
}
}