source: branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/SequenceForTaskDetectionRuleAlignment.java @ 1568

Last change on this file since 1568 was 1568, checked in by rkrimmel, 10 years ago

Building distance matrix between sequences
File size: 37.1 KB
Line 
1//   Copyright 2012 Georg-August-Universität Göttingen, Germany
2//
3//   Licensed under the Apache License, Version 2.0 (the "License");
4//   you may not use this file except in compliance with the License.
5//   You may obtain a copy of the License at
6//
7//       http://www.apache.org/licenses/LICENSE-2.0
8//
9//   Unless required by applicable law or agreed to in writing, software
10//   distributed under the License is distributed on an "AS IS" BASIS,
11//   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12//   See the License for the specific language governing permissions and
13//   limitations under the License.
14
15package de.ugoe.cs.autoquest.tasktrees.temporalrelation;
16
17import java.util.ArrayList;
18import java.util.HashMap;
19import java.util.HashSet;
20import java.util.Iterator;
21import java.util.LinkedList;
22import java.util.List;
23import java.util.Map;
24import java.util.Set;
25import java.util.logging.Level;
26
27import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.FengDoolittle;
28import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.NumberSequence;
29import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.SmithWaterman;
30import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.SmithWatermanRepeated;
31import de.ugoe.cs.autoquest.tasktrees.alignment.substitution.ObjectDistanceSubstitionMatrix;
32import de.ugoe.cs.autoquest.tasktrees.alignment.substitution.TriangleMatrix;
33import de.ugoe.cs.autoquest.tasktrees.taskequality.TaskEquality;
34import de.ugoe.cs.autoquest.tasktrees.treeifc.IIteration;
35import de.ugoe.cs.autoquest.tasktrees.treeifc.IIterationInstance;
36import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelection;
37import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelectionInstance;
38import de.ugoe.cs.autoquest.tasktrees.treeifc.ISequence;
39import de.ugoe.cs.autoquest.tasktrees.treeifc.ISequenceInstance;
40import de.ugoe.cs.autoquest.tasktrees.treeifc.ITask;
41import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskBuilder;
42import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskFactory;
43import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskInstance;
44import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskInstanceList;
45import de.ugoe.cs.autoquest.tasktrees.treeifc.IUserSession;
46import de.ugoe.cs.autoquest.usageprofiles.SymbolMap;
47import de.ugoe.cs.autoquest.usageprofiles.Trie;
48import de.ugoe.cs.autoquest.usageprofiles.TrieProcessor;
49import de.ugoe.cs.util.StopWatch;
50import de.ugoe.cs.util.console.Console;
51
52/**
53 * <p>
54 * This class implements the major rule for creating task trees based on a set
55 * of recorded user sessions. For this, it first harmonizes all tasks. This
56 * eases later comparison. Then it searches the sessions for iterations and
57 * replaces them accordingly. Then it searches for sub sequences being the
58 * longest and occurring most often. For each found sub sequence, it replaces
59 * the occurrences by creating appropriate {@link ISequence}s. Afterwards, again
60 * searches for iterations and then again for sub sequences until no more
61 * replacements are done.
62 * </p>
63 * <p>
64 * For determining the longest sequence occurring most often, the implementation
65 * uses a {@link Trie}. The depth of the tree is initially 3. If the algorithm
66 * has a longest sequence occurring most often whose length is equal to the
67 * depth of the trie, it recalculates the trie with an increased depth.
68 * </p>
69 *
70 * @author Patrick Harms
71 */
72class SequenceForTaskDetectionRuleAlignment implements ISessionScopeRule {
73
74        /**
75         * <p>
76         * the task factory to be used for creating substructures for the temporal
77         * relationships identified during rul application
78         * </p>
79         */
80        private ITaskFactory taskFactory;
81        /**
82         * <p>
83         * the task builder to be used for creating substructures for the temporal
84         * relationships identified during rule application
85         * </p>
86         */
87        private ITaskBuilder taskBuilder;
88
89        /**
90         * <p>
91         * the task handling strategy to be used for comparing tasks for
92         * preparation, i.e., before the tasks are harmonized
93         * </p>
94         */
95        private TaskHandlingStrategy preparationTaskHandlingStrategy;
96
97        /**
98         * <p>
99         * the task handling strategy to be used for comparing tasks during
100         * iteration detection an trie generation, i.e., after the tasks are
101         * harmonized
102         * </p>
103         */
104        private TaskHandlingStrategy identityTaskHandlingStrategy;;
105
106        private ArrayList<NumberSequence> numberseqs;
107
108        /**
109         * <p>
110         * instantiates the rule and initializes it with a task equality to be
111         * considered when comparing tasks as well as a task factory and builder to
112         * be used for creating task structures.
113         * </p>
114         *
115         * @param minimalTaskEquality
116         *            the task equality to be considered when comparing tasks
117         * @param taskFactory
118         *            the task factory to be used for creating substructures
119         * @param taskBuilder
120         *            the task builder to be used for creating substructures
121         */
122
123        SequenceForTaskDetectionRuleAlignment(TaskEquality minimalTaskEquality,
124                        ITaskFactory taskFactory, ITaskBuilder taskBuilder) {
125                this.taskFactory = taskFactory;
126                this.taskBuilder = taskBuilder;
127
128                this.preparationTaskHandlingStrategy = new TaskHandlingStrategy(
129                                minimalTaskEquality);
130                this.identityTaskHandlingStrategy = new TaskHandlingStrategy(
131                                TaskEquality.IDENTICAL);
132                numberseqs = new ArrayList<NumberSequence>();
133
134        }
135
136        /*
137         * (non-Javadoc)
138         *
139         * @see java.lang.Object#toString()
140         */
141        @Override
142        public String toString() {
143                return "SequenceForTaskDetectionRuleAlignment";
144        }
145
146        /*
147         * (non-Javadoc)
148         *
149         * @see
150         * de.ugoe.cs.autoquest.tasktrees.temporalrelation.ISessionScopeRule#apply
151         * (java.util.List)
152         */
153        @Override
154        public RuleApplicationResult apply(List<IUserSession> sessions) {
155                RuleApplicationData appData = new RuleApplicationData(sessions);
156
157                // this is the real rule application. Loop while something is replaced.
158                SymbolMap<ITaskInstance, ITask> uniqueTasks = harmonizeEventTaskInstancesModel(appData);
159
160                ObjectDistanceSubstitionMatrix submat = new ObjectDistanceSubstitionMatrix(
161                                uniqueTasks, 5);
162                submat.generate();
163
164                TriangleMatrix sequenceDistances = new TriangleMatrix(numberseqs.size());
165
166                for (int i = 0; i < numberseqs.size(); i++) {
167                        NumberSequence ns1 = numberseqs.get(i);
168                        //System.out.print("Sequence " + i + ": ");
169                        //ns1.printSequence();
170                        for (int j = 0; j < numberseqs.size(); j++) {
171                                NumberSequence ns2 = numberseqs.get(j);
172
173                                if (i != j) {
174                                        int smithWatermanThreshold = 10;
175
176                                        SmithWatermanRepeated twoSequences = new SmithWatermanRepeated(
177                                                        ns1.getSequence(), ns2.getSequence(), submat,
178                                                        smithWatermanThreshold);
179                                        SmithWatermanRepeated sameSequence1 = new SmithWatermanRepeated(
180                                                        ns1.getSequence(), ns1.getSequence(), submat,
181                                                        smithWatermanThreshold);
182                                        SmithWatermanRepeated sameSequence2 = new SmithWatermanRepeated(
183                                                        ns2.getSequence(), ns2.getSequence(), submat,
184                                                        smithWatermanThreshold);
185                                       
186                                        SmithWatermanRepeated randomSequence = new SmithWatermanRepeated(
187                                                        ns1.shuffle().getSequence(),ns2.shuffle().getSequence(),submat,smithWatermanThreshold);
188                                        //randomSequence.printDPMatrix();
189                                        //randomSequence.traceback();
190                                       
191                                        double score = twoSequences.getAlignmentScore();
192                                        // Scores of the sequence beeing aligned to itself
193                                        double sSelf1 = sameSequence1.getAlignmentScore();
194                                        double sSelf2 = sameSequence2.getAlignmentScore();
195
196                                        double sRand = randomSequence.getAlignmentScore();
197
198                                        double sMax = (sSelf1 + sSelf2) / 2;
199                                        double sEff = (score - sRand)/ (sMax - sRand);
200                                        double distance = -Math.log(sEff);
201                               
202                                        System.out.println("Score: " + score + " sRand: " + sRand + " sMax: " + sMax + " sEff: " + sEff + " distance: " + distance);
203                                       
204                                        sequenceDistances.set(i,j,distance );
205
206                                        if (score > 0) {
207                                                /*
208                                                 * System.out.println(
209                                                 * "=================================================");
210                                                 * System.out.println("| Sequence " +
211                                                 * String.format("%3d", i) +" Sequence " +
212                                                 * String.format("%3d", j) + "                     |");
213                                                 * System.out.println(
214                                                 * "=================================================");
215                                                 * System.out.print("Sequence " + i + ": ");
216                                                 * ns1.printSequence(); System.out.print("Sequence " + j
217                                                 * + ": "); ns2.printSequence(); System.out.println();
218                                                 * //System.out.println("Max Scrore: " +
219                                                 * sw.getMaxScore());
220                                                 * System.out.println("Alignment Score: " +
221                                                 * sw.getAlignmentScore()); //sw.printDPMatrix();
222                                                 * sw.traceback(); System.out.println();
223                                                 * System.out.println();
224                                                 */
225                                        }
226                                }
227                        }
228                }
229                //System.out.println(sequenceDistances.toString());
230               
231                do {
232                        System.out.println();
233                        FengDoolittle fd = new FengDoolittle();
234
235                        // appData.getStopWatch().start("whole loop");
236                        // detectAndReplaceIterations(appData);
237
238                        // appData.getStopWatch().start("task replacement");
239                        // detectAndReplaceTasks(appData);
240                        // appData.getStopWatch().stop("task replacement");
241                        // appData.getStopWatch().stop("whole loop");
242
243                        // appData.getStopWatch().dumpStatistics(System.out);
244                        // appData.getStopWatch().reset();
245
246                } while (appData.detectedAndReplacedTasks());
247
248                Console.println("created "
249                                + appData.getResult().getNewlyCreatedTasks().size()
250                                + " new tasks and "
251                                + appData.getResult().getNewlyCreatedTaskInstances().size()
252                                + " appropriate instances\n");
253
254                if ((appData.getResult().getNewlyCreatedTasks().size() > 0)
255                                || (appData.getResult().getNewlyCreatedTaskInstances().size() > 0)) {
256                        appData.getResult().setRuleApplicationStatus(
257                                        RuleApplicationStatus.FINISHED);
258                }
259
260                return appData.getResult();
261        }
262
263        /**
264         * <p>
265         * harmonizes the event task instances by unifying tasks. This is done, as
266         * initially the event tasks being equal with respect to the considered task
267         * equality are distinct objects. The comparison of these distinct objects
268         * is more time consuming than comparing the object references.
269         * </p>
270         *
271         * @param appData
272         *            the rule application data combining all data used for applying
273         *            this rule
274         * @return Returns the unique tasks symbol map
275         */
276        private SymbolMap<ITaskInstance, ITask> harmonizeEventTaskInstancesModel(
277                        RuleApplicationData appData) {
278                Console.traceln(Level.INFO,
279                                "harmonizing task model of event task instances");
280                appData.getStopWatch().start("harmonizing event tasks");
281
282                SymbolMap<ITaskInstance, ITask> uniqueTasks = preparationTaskHandlingStrategy
283                                .createSymbolMap();
284                TaskInstanceComparator comparator = preparationTaskHandlingStrategy
285                                .getTaskComparator();
286
287                int unifiedTasks = 0;
288                ITask task;
289                List<IUserSession> sessions = appData.getSessions();
290                int sessionNo = 0;
291                numberseqs = new ArrayList<NumberSequence>();
292                for (IUserSession session : sessions) {
293                        Console.traceln(Level.FINE, "handling " + (++sessionNo) + ". "
294                                        + session);
295                        NumberSequence templist = new NumberSequence(session.size());
296
297                        for (int i = 0; i < session.size(); i++) {
298                                ITaskInstance taskInstance = session.get(i);
299                                task = uniqueTasks.getValue(taskInstance);
300
301                                if (task == null) {
302                                        uniqueTasks.addSymbol(taskInstance, taskInstance.getTask());
303                                        templist.getSequence()[i] = taskInstance.getTask().getId();
304                                } else {
305                                        taskBuilder.setTask(taskInstance, task);
306                                        templist.getSequence()[i] = task.getId();
307                                        unifiedTasks++;
308                                }
309                        }
310                        numberseqs.add(templist);
311                        comparator.clearBuffers();
312                }
313
314                appData.getStopWatch().stop("harmonizing event tasks");
315                Console.traceln(Level.INFO, "harmonized " + unifiedTasks
316                                + " task occurrences (still " + uniqueTasks.size()
317                                + " different tasks)");
318
319                appData.getStopWatch().dumpStatistics(System.out);
320                appData.getStopWatch().reset();
321                return uniqueTasks;
322        }
323
324        /**
325         * <p>
326         * searches for direct iterations of single tasks in all sequences and
327         * replaces them with {@link IIteration}s, respectively appropriate
328         * instances. Also all single occurrences of a task that is iterated
329         * somewhen are replaced with iterations to have again an efficient way for
330         * task comparisons.
331         * </p>
332         *
333         * @param appData
334         *            the rule application data combining all data used for applying
335         *            this rule
336         */
337        private void detectAndReplaceIterations(RuleApplicationData appData) {
338                Console.traceln(Level.FINE, "detecting iterations");
339                appData.getStopWatch().start("detecting iterations");
340
341                List<IUserSession> sessions = appData.getSessions();
342
343                Set<ITask> iteratedTasks = searchIteratedTasks(sessions);
344
345                if (iteratedTasks.size() > 0) {
346                        replaceIterationsOf(iteratedTasks, sessions, appData);
347                }
348
349                appData.getStopWatch().stop("detecting iterations");
350                Console.traceln(Level.INFO, "replaced " + iteratedTasks.size()
351                                + " iterated tasks");
352        }
353
354        /**
355         * <p>
356         * searches the provided sessions for task iterations. If a task is
357         * iterated, it is added to the returned set.
358         * </p>
359         *
360         * @param the
361         *            session to search for iterations in
362         *
363         * @return a set of tasks being iterated somewhere
364         */
365        private Set<ITask> searchIteratedTasks(List<IUserSession> sessions) {
366                Set<ITask> iteratedTasks = new HashSet<ITask>();
367                for (IUserSession session : sessions) {
368                        for (int i = 0; i < (session.size() - 1); i++) {
369                                // we prepared the task instances to refer to unique tasks, if
370                                // they are treated
371                                // as equal. Therefore, we just compare the identity of the
372                                // tasks of the task
373                                // instances
374                                if (session.get(i).getTask() == session.get(i + 1).getTask()) {
375                                        iteratedTasks.add(session.get(i).getTask());
376                                }
377                        }
378                }
379
380                return iteratedTasks;
381        }
382
383        /**
384         * <p>
385         * replaces all occurrences of all tasks provided in the set with iterations
386         * </p>
387         *
388         * @param iteratedTasks
389         *            the tasks to be replaced with iterations
390         * @param sessions
391         *            the sessions in which the tasks are to be replaced
392         * @param appData
393         *            the rule application data combining all data used for applying
394         *            this rule
395         */
396        private void replaceIterationsOf(Set<ITask> iteratedTasks,
397                        List<IUserSession> sessions, RuleApplicationData appData) {
398                Map<ITask, IIteration> iterations = new HashMap<ITask, IIteration>();
399                Map<IIteration, List<IIterationInstance>> iterationInstances = new HashMap<IIteration, List<IIterationInstance>>();
400
401                for (ITask iteratedTask : iteratedTasks) {
402                        IIteration iteration = taskFactory.createNewIteration();
403                        iterations.put(iteratedTask, iteration);
404                        iterationInstances.put(iteration,
405                                        new LinkedList<IIterationInstance>());
406                }
407
408                IIterationInstance iterationInstance;
409
410                for (IUserSession session : sessions) {
411                        int index = 0;
412                        iterationInstance = null;
413
414                        while (index < session.size()) {
415                                // we prepared the task instances to refer to unique tasks, if
416                                // they are treated
417                                // as equal. Therefore, we just compare the identity of the
418                                // tasks of the task
419                                // instances
420                                ITask currentTask = session.get(index).getTask();
421                                IIteration iteration = iterations.get(currentTask);
422                                if (iteration != null) {
423                                        if ((iterationInstance == null)
424                                                        || (iterationInstance.getTask() != iteration)) {
425                                                iterationInstance = taskFactory
426                                                                .createNewTaskInstance(iteration);
427                                                iterationInstances.get(iteration)
428                                                                .add(iterationInstance);
429                                                taskBuilder.addTaskInstance(session, index,
430                                                                iterationInstance);
431                                                index++;
432                                        }
433
434                                        taskBuilder.addChild(iterationInstance, session.get(index));
435                                        taskBuilder.removeTaskInstance(session, index);
436                                } else {
437                                        if (iterationInstance != null) {
438                                                iterationInstance = null;
439                                        }
440                                        index++;
441                                }
442                        }
443                }
444
445                for (Map.Entry<IIteration, List<IIterationInstance>> entry : iterationInstances
446                                .entrySet()) {
447                        harmonizeIterationInstancesModel(entry.getKey(), entry.getValue());
448                }
449        }
450
451        /**
452         * <p>
453         * TODO clarify why this is done
454         * </p>
455         */
456        private void harmonizeIterationInstancesModel(IIteration iteration,
457                        List<IIterationInstance> iterationInstances) {
458                List<ITask> iteratedTaskVariants = new LinkedList<ITask>();
459                TaskInstanceComparator comparator = preparationTaskHandlingStrategy
460                                .getTaskComparator();
461
462                // merge the lexically different variants of iterated task to a unique
463                // list
464                for (IIterationInstance iterationInstance : iterationInstances) {
465                        for (ITaskInstance executionVariant : iterationInstance) {
466                                ITask candidate = executionVariant.getTask();
467
468                                boolean found = false;
469                                for (ITask taskVariant : iteratedTaskVariants) {
470                                        if (comparator.areLexicallyEqual(taskVariant, candidate)) {
471                                                taskBuilder.setTask(executionVariant, taskVariant);
472                                                found = true;
473                                                break;
474                                        }
475                                }
476
477                                if (!found) {
478                                        iteratedTaskVariants.add(candidate);
479                                }
480                        }
481                }
482
483                // if there are more than one lexically different variant of iterated
484                // tasks, adapt the
485                // iteration model to be a selection of different variants. In this case
486                // also adapt
487                // the generated iteration instances to correctly contain selection
488                // instances. If there
489                // is only one variant of an iterated task, simply set this as the
490                // marked task of the
491                // iteration. In this case, the instances can be preserved as is
492                if (iteratedTaskVariants.size() > 1) {
493                        ISelection selection = taskFactory.createNewSelection();
494
495                        for (ITask variant : iteratedTaskVariants) {
496                                taskBuilder.addChild(selection, variant);
497                        }
498
499                        taskBuilder.setMarkedTask(iteration, selection);
500
501                        for (IIterationInstance instance : iterationInstances) {
502                                for (int i = 0; i < instance.size(); i++) {
503                                        ISelectionInstance selectionInstance = taskFactory
504                                                        .createNewTaskInstance(selection);
505                                        taskBuilder.setChild(selectionInstance, instance.get(i));
506                                        taskBuilder.setTaskInstance(instance, i, selectionInstance);
507                                }
508                        }
509                } else {
510                        taskBuilder.setMarkedTask(iteration, iteratedTaskVariants.get(0));
511                }
512        }
513
514        /**
515         * TODO go on commenting
516         *
517         * @param appData
518         *            the rule application data combining all data used for applying
519         *            this rule
520         */
521        private void detectAndReplaceTasks(RuleApplicationData appData) {
522                Console.traceln(Level.FINE, "detecting and replacing tasks");
523                appData.getStopWatch().start("detecting tasks");
524
525                getSequencesOccuringMostOften(appData);
526
527                appData.getStopWatch().stop("detecting tasks");
528                appData.getStopWatch().start("replacing tasks");
529
530                replaceSequencesOccurringMostOften(appData);
531
532                appData.getStopWatch().stop("replacing tasks");
533                Console.traceln(Level.INFO, "detected and replaced "
534                                + appData.getLastFoundTasks().size() + " tasks occuring "
535                                + appData.getLastFoundTasks().getOccurrenceCount() + " times");
536        }
537
538        /**
539         * @param appData
540         *            the rule application data combining all data used for applying
541         *            this rule
542         */
543        private void getSequencesOccuringMostOften(RuleApplicationData appData) {
544                Console.traceln(Level.FINE, "determining most prominent tasks");
545
546                Tasks tasks;
547                boolean createNewTrie = (appData.getLastTrie() == null)
548                                || appData.detectedAndReplacedTasks(); // tree has changed
549
550                do {
551                        if (createNewTrie) {
552                                createNewTrie(appData);
553                        }
554
555                        MaxCountAndLongestTasksFinder finder = new MaxCountAndLongestTasksFinder();
556                        appData.getLastTrie().process(finder);
557
558                        tasks = finder.getFoundTasks();
559
560                        createNewTrie = false;
561
562                        for (List<ITaskInstance> task : tasks) {
563                                if (task.size() >= appData.getTrainedSequenceLength()) {
564                                        // Trie must be recreated with a longer sequence length to
565                                        // be sure that
566                                        // the found sequences occurring most often are found in
567                                        // their whole length
568                                        appData.setTrainedSequenceLength(appData
569                                                        .getTrainedSequenceLength() + 1);
570                                        createNewTrie = true;
571                                        break;
572                                }
573                        }
574                } while (createNewTrie);
575
576                // create a normal trie for comparison
577                /*
578                 * System.out.println("creating test trie for comparison");
579                 *
580                 * appData.getStopWatch().start("testtrie"); Trie<ITaskInstance> trie =
581                 * new Trie<ITaskInstance>(identityTaskComparator);
582                 *
583                 * for (IUserSession session : appData.getSessions()) {
584                 * trie.train(session.getExecutedTasks(),
585                 * appData.getTrainedSequenceLength()); }
586                 *
587                 * appData.getStopWatch().stop("testtrie");
588                 *
589                 * MaxCountAndLongestTasksFinder finder = new
590                 * MaxCountAndLongestTasksFinder(); trie.process(finder);
591                 *
592                 * boolean allTasksEqual = finder.getFoundTasks().size() ==
593                 * tasks.size();
594                 *
595                 * allTasksEqual &= finder.getFoundTasks().occurrenceCount ==
596                 * tasks.occurrenceCount;
597                 *
598                 * for (List<ITaskInstance> task1 : finder.getFoundTasks()) { boolean
599                 * foundTask = false; for (List<ITaskInstance> task2 : tasks) { boolean
600                 * tasksEqual = false; if (task1.size() == task2.size()) { tasksEqual =
601                 * true; for (int i = 0; i < task1.size(); i++) { if
602                 * (!identityTaskComparator.equals(task1.get(i).getTask(),
603                 * task2.get(i).getTask())) { tasksEqual = false; } } }
604                 *
605                 * if (tasksEqual) { foundTask = true; break; } }
606                 *
607                 * if (!foundTask) { System.out.println("different is " + task1);
608                 * allTasksEqual = false; break; } }
609                 *
610                 * if (!allTasksEqual) { System.out.println(finder.getFoundTasks());
611                 * System.out.println(tasks);
612                 *
613                 * throw new
614                 * IllegalArgumentException("both tries calculated different subsequences"
615                 * ); }
616                 *
617                 * /*TrieStatisticsDumper dumper = new TrieStatisticsDumper();
618                 * appData.getLastTrie().process(dumper); dumper.dumpCounters();
619                 */
620
621                appData.setLastFoundTasks(tasks);
622
623                Console.traceln(Level.FINE, "found "
624                                + appData.getLastFoundTasks().size() + " tasks " + "occurring "
625                                + appData.getLastFoundTasks().getOccurrenceCount() + " times");
626        }
627
628        /**
629         * @param appData
630         *            the rule application data combining all data used for applying
631         *            this rule
632         */
633        private void createNewTrie(RuleApplicationData appData) {
634                Console.traceln(
635                                Level.FINER,
636                                "training trie with a maximum sequence length of "
637                                                + appData.getTrainedSequenceLength());
638
639                appData.getStopWatch().start("training trie");
640
641                // we prepared the task instances to refer to unique tasks, if they are
642                // treated
643                // as equal. Therefore, we just compare the identity of the tasks of the
644                // task
645                // instances
646                appData.setLastTrie(new TaskInstanceTrie(identityTaskHandlingStrategy));
647
648                appData.getLastTrie().trainSessions(appData.getSessions(),
649                                appData.getTrainedSequenceLength());
650
651                appData.getStopWatch().stop("training trie");
652        }
653
654        /**
655         * @param appData
656         *            the rule application data combining all data used for applying
657         *            this rule
658         */
659        private void replaceSequencesOccurringMostOften(RuleApplicationData appData) {
660                appData.detectedAndReplacedTasks(false);
661
662                if ((appData.getLastFoundTasks().size() > 0)
663                                && (appData.getLastFoundTasks().getOccurrenceCount() > 1)) {
664                        Console.traceln(Level.FINER, "replacing tasks occurrences");
665
666                        for (List<ITaskInstance> task : appData.getLastFoundTasks()) {
667                                ISequence sequence = taskFactory.createNewSequence();
668
669                                Console.traceln(Level.FINEST, "replacing " + sequence.getId()
670                                                + ": " + task);
671
672                                List<ISequenceInstance> sequenceInstances = replaceTaskOccurrences(
673                                                task, appData.getSessions(), sequence);
674
675                                harmonizeSequenceInstancesModel(sequence, sequenceInstances,
676                                                task.size());
677                                appData.detectedAndReplacedTasks(appData
678                                                .detectedAndReplacedTasks()
679                                                || (sequenceInstances.size() > 0));
680
681                                if (sequenceInstances.size() < appData.getLastFoundTasks()
682                                                .getOccurrenceCount()) {
683                                        Console.traceln(Level.FINE,
684                                                        sequence.getId()
685                                                                        + ": replaced task only "
686                                                                        + sequenceInstances.size()
687                                                                        + " times instead of expected "
688                                                                        + appData.getLastFoundTasks()
689                                                                                        .getOccurrenceCount());
690                                }
691                        }
692                }
693
694        }
695
696        /**
697     *
698     */
699        private void harmonizeSequenceInstancesModel(ISequence sequence,
700                        List<ISequenceInstance> sequenceInstances, int sequenceLength) {
701                TaskInstanceComparator comparator = preparationTaskHandlingStrategy
702                                .getTaskComparator();
703
704                // ensure for each subtask that lexically different variants are
705                // preserved
706                for (int subTaskIndex = 0; subTaskIndex < sequenceLength; subTaskIndex++) {
707                        List<ITask> subTaskVariants = new LinkedList<ITask>();
708
709                        for (ISequenceInstance sequenceInstance : sequenceInstances) {
710                                ITask candidate = sequenceInstance.get(subTaskIndex).getTask();
711
712                                boolean found = false;
713
714                                for (int i = 0; i < subTaskVariants.size(); i++) {
715                                        if (comparator.areLexicallyEqual(subTaskVariants.get(i),
716                                                        candidate)) {
717                                                taskBuilder.setTask(sequenceInstance.get(subTaskIndex),
718                                                                subTaskVariants.get(i));
719
720                                                found = true;
721                                                break;
722                                        }
723                                }
724
725                                if (!found) {
726                                        subTaskVariants.add(candidate);
727                                }
728                        }
729
730                        // if there are more than one lexically different variant of the sub
731                        // task at
732                        // the considered position, adapt the sequence model at that
733                        // position to have
734                        // a selection of the different variants. In this case also adapt
735                        // the
736                        // generated sequence instances to correctly contain selection
737                        // instances. If
738                        // there is only one variant of sub tasks at the given position,
739                        // simply set
740                        // this variant as the sub task of the selection. In this case, the
741                        // instances
742                        // can be preserved as is
743                        if (subTaskVariants.size() > 1) {
744                                ISelection selection = taskFactory.createNewSelection();
745
746                                for (ITask variant : subTaskVariants) {
747                                        taskBuilder.addChild(selection, variant);
748                                }
749
750                                taskBuilder.addChild(sequence, selection);
751
752                                for (ISequenceInstance instance : sequenceInstances) {
753                                        ISelectionInstance selectionInstance = taskFactory
754                                                        .createNewTaskInstance(selection);
755                                        taskBuilder.setChild(selectionInstance,
756                                                        instance.get(subTaskIndex));
757                                        taskBuilder.setTaskInstance(instance, subTaskIndex,
758                                                        selectionInstance);
759                                }
760                        } else if (subTaskVariants.size() == 1) {
761                                taskBuilder.addChild(sequence, subTaskVariants.get(0));
762                        }
763                }
764        }
765
766        /**
767         * @param tree
768         */
769        private List<ISequenceInstance> replaceTaskOccurrences(
770                        List<ITaskInstance> task, List<IUserSession> sessions,
771                        ISequence temporalTaskModel) {
772                List<ISequenceInstance> sequenceInstances = new LinkedList<ISequenceInstance>();
773
774                for (IUserSession session : sessions) {
775                        int index = -1;
776
777                        do {
778                                index = getSubListIndex(session, task, ++index);
779
780                                if (index > -1) {
781                                        sequenceInstances.add(RuleUtils
782                                                        .createNewSubSequenceInRange(session, index, index
783                                                                        + task.size() - 1, temporalTaskModel,
784                                                                        taskFactory, taskBuilder));
785                                }
786                        } while (index > -1);
787                }
788
789                return sequenceInstances;
790        }
791
792        /**
793         * @param trie
794         * @param object
795         * @return
796         */
797        private int getSubListIndex(ITaskInstanceList list,
798                        List<ITaskInstance> subList, int startIndex) {
799                boolean matchFound;
800                int result = -1;
801
802                for (int i = startIndex; i <= list.size() - subList.size(); i++) {
803                        matchFound = true;
804
805                        for (int j = 0; j < subList.size(); j++) {
806                                // we prepared the task instances to refer to unique tasks, if
807                                // they are treated
808                                // as equal. Therefore, we just compare the identity of the
809                                // tasks of the task
810                                // instances
811                                if (list.get(i + j).getTask() != subList.get(j).getTask()) {
812                                        matchFound = false;
813                                        break;
814                                }
815                        }
816
817                        if (matchFound) {
818                                result = i;
819                                break;
820                        }
821                }
822
823                return result;
824        }
825
826        /**
827         * @param trie
828         * @param object
829         * @return
830         */
831        private int getSubListIndex(List<ITaskInstance> list,
832                        List<ITaskInstance> subList, int startIndex) {
833                boolean matchFound;
834                int result = -1;
835
836                for (int i = startIndex; i <= list.size() - subList.size(); i++) {
837                        matchFound = true;
838
839                        for (int j = 0; j < subList.size(); j++) {
840                                // we prepared the task instances to refer to unique tasks, if
841                                // they are treated
842                                // as equal. Therefore, we just compare the identity of the
843                                // tasks of the task
844                                // instances
845                                if (list.get(i + j) != subList.get(j)) {
846                                        matchFound = false;
847                                        break;
848                                }
849                        }
850
851                        if (matchFound) {
852                                result = i;
853                                break;
854                        }
855                }
856
857                return result;
858        }
859
860        /**
861         * @author Patrick Harms
862         */
863        private class MaxCountAndLongestTasksFinder implements
864                        TrieProcessor<ITaskInstance> {
865
866                /**
867         *
868         */
869                private int currentCount;
870
871                /**
872         *
873         */
874                private List<List<ITaskInstance>> foundTasks = new LinkedList<List<ITaskInstance>>();
875
876                /**
877         *
878         */
879                public MaxCountAndLongestTasksFinder() {
880                        super();
881                        this.currentCount = 0;
882                }
883
884                /*
885                 * (non-Javadoc)
886                 *
887                 * @see
888                 * de.ugoe.cs.autoquest.usageprofiles.TrieProcessor#process(java.util
889                 * .List, int)
890                 */
891                @Override
892                public TrieProcessor.Result process(List<ITaskInstance> foundTask,
893                                int count) {
894                        if (foundTask.size() < 2) {
895                                // ignore single tasks
896                                return TrieProcessor.Result.CONTINUE;
897                        }
898
899                        if (count < 2) {
900                                // ignore singular occurrences
901                                return TrieProcessor.Result.SKIP_NODE;
902                        }
903
904                        if (this.currentCount > count) {
905                                // ignore this children of this task, as they may have only
906                                // smaller counts than
907                                // the already found tasks
908                                return TrieProcessor.Result.SKIP_NODE;
909                        }
910
911                        if (this.currentCount < count) {
912                                // the provided task occurs more often that all tasks found so
913                                // far.
914                                // clear all found tasks and use the new count as the one
915                                // searched for
916                                foundTasks.clear();
917                                this.currentCount = count;
918                        }
919
920                        if (this.currentCount == count) {
921                                // the task is of interest. Sort it into the other found tasks
922                                // so that
923                                // the longest come first
924                                boolean added = false;
925                                for (int i = 0; i < foundTasks.size(); i++) {
926                                        if (foundTasks.get(i).size() < foundTask.size()) {
927                                                // defensive copy
928                                                foundTasks.add(i, new LinkedList<ITaskInstance>(
929                                                                foundTask)); // defensive copy
930                                                added = true;
931                                                break;
932                                        }
933                                }
934
935                                if (!added) {
936                                        foundTasks.add(new LinkedList<ITaskInstance>(foundTask)); // defensive
937                                                                                                                                                                // copy
938                                }
939                        }
940
941                        return TrieProcessor.Result.CONTINUE;
942                }
943
944                /**
945                 * @return
946                 */
947                public Tasks getFoundTasks() {
948                        removePermutationsOfShorterTasks();
949                        return new Tasks(currentCount, foundTasks);
950                }
951
952                /**
953         *
954         */
955                private void removePermutationsOfShorterTasks() {
956                        // now iterate the sorted list and for each task remove all other
957                        // tasks that are shorter
958                        // (i.e. come later in the sorted list) and that represent a subpart
959                        // of the task
960                        for (int i = 0; i < foundTasks.size(); i++) {
961                                for (int j = i + 1; j < foundTasks.size();) {
962                                        if (foundTasks.get(j).size() < foundTasks.get(i).size()) {
963                                                // found a task that is a potential subtask. Check for
964                                                // this and remove the
965                                                // subtask if needed
966                                                List<ITaskInstance> longTask = foundTasks.get(i);
967                                                List<ITaskInstance> shortTask = foundTasks.get(j);
968
969                                                if (getSubListIndex(longTask, shortTask, 0) > -1) {
970                                                        foundTasks.remove(j);
971                                                } else {
972                                                        j++;
973                                                }
974                                        } else {
975                                                j++;
976                                        }
977                                }
978                        }
979                }
980
981        }
982
983        // /**
984        // * @author Patrick Harms
985        // */
986        // private class TrieStatisticsDumper implements
987        // TrieProcessor<ITaskInstance> {
988        //
989        // /**
990        // *
991        // */
992        // private Map<Integer, Integer> counters = new HashMap<Integer, Integer>();
993        //
994        // /* (non-Javadoc)
995        // * @see
996        // de.ugoe.cs.autoquest.usageprofiles.TrieProcessor#process(java.util.List,
997        // int)
998        // */
999        // @Override
1000        // public TrieProcessor.Result process(List<ITaskInstance> subsequence, int
1001        // count) {
1002        // if (subsequence.size() == 1) {
1003        // Integer value = counters.get(count);
1004        //
1005        // if (value == null) {
1006        // value = 0;
1007        // }
1008        //
1009        // counters.put(count, value + 1);
1010        //
1011        // return TrieProcessor.Result.CONTINUE;
1012        // }
1013        // else {
1014        // // ignore singular occurrences
1015        // return TrieProcessor.Result.SKIP_NODE;
1016        // }
1017        // }
1018        //
1019        // /**
1020        // * @return
1021        // */
1022        // public void dumpCounters() {
1023        // int dumpedCounters = 0;
1024        //
1025        // int count = 1;
1026        // while (dumpedCounters < counters.size()) {
1027        // Integer value = counters.get(count++);
1028        // if (value != null) {
1029        // System.out.println(value + " symbols occurred " + count + " times");
1030        // dumpedCounters++;
1031        // }
1032        // }
1033        // }
1034        //
1035        // }
1036
1037        /**
1038     *
1039     */
1040        private static class RuleApplicationData {
1041
1042                /**
1043         *
1044         */
1045                private List<IUserSession> sessions;
1046
1047                /**
1048         *
1049         */
1050                private TaskInstanceTrie lastTrie;
1051
1052                /**
1053                 * default and minimum trained sequence length is 3
1054                 */
1055                private int trainedSequenceLength = 3;
1056
1057                /**
1058         *
1059         */
1060                private Tasks lastFoundTasks = new Tasks(Integer.MAX_VALUE, null);
1061
1062                /**
1063         *
1064         */
1065                private boolean detectedAndReplacedTasks;
1066
1067                /**
1068         *
1069         */
1070                private RuleApplicationResult result = new RuleApplicationResult();
1071
1072                /**
1073         *
1074         */
1075                private StopWatch stopWatch = new StopWatch();
1076
1077                /**
1078         *
1079         */
1080                private RuleApplicationData(List<IUserSession> sessions) {
1081                        this.sessions = sessions;
1082                }
1083
1084                /**
1085                 * @return the tree
1086                 */
1087                private List<IUserSession> getSessions() {
1088                        return sessions;
1089                }
1090
1091                /**
1092                 * @param lastTrie
1093                 *            the lastTrie to set
1094                 */
1095                private void setLastTrie(TaskInstanceTrie lastTrie) {
1096                        this.lastTrie = lastTrie;
1097                }
1098
1099                /**
1100                 * @return the lastTrie
1101                 */
1102                private TaskInstanceTrie getLastTrie() {
1103                        return lastTrie;
1104                }
1105
1106                /**
1107                 * @param trainedSequenceLength
1108                 *            the trainedSequenceLength to set
1109                 */
1110                private void setTrainedSequenceLength(int trainedSequenceLength) {
1111                        this.trainedSequenceLength = trainedSequenceLength;
1112                }
1113
1114                /**
1115                 * @return the trainedSequenceLength
1116                 */
1117                private int getTrainedSequenceLength() {
1118                        return trainedSequenceLength;
1119                }
1120
1121                /**
1122                 * @param lastFoundSequences
1123                 *            the lastFoundSequences to set
1124                 */
1125                private void setLastFoundTasks(Tasks lastFoundSequences) {
1126                        this.lastFoundTasks = lastFoundSequences;
1127                }
1128
1129                /**
1130                 * @return the lastFoundSequences
1131                 */
1132                private Tasks getLastFoundTasks() {
1133                        return lastFoundTasks;
1134                }
1135
1136                /**
1137         *
1138         */
1139                private void detectedAndReplacedTasks(boolean detectedAndReplacedTasks) {
1140                        this.detectedAndReplacedTasks = detectedAndReplacedTasks;
1141                }
1142
1143                /**
1144         *
1145         */
1146                private boolean detectedAndReplacedTasks() {
1147                        return detectedAndReplacedTasks;
1148                }
1149
1150                /**
1151                 * @return the result
1152                 */
1153                private RuleApplicationResult getResult() {
1154                        return result;
1155                }
1156
1157                /**
1158                 * @return the stopWatch
1159                 */
1160                private StopWatch getStopWatch() {
1161                        return stopWatch;
1162                }
1163
1164        }
1165
1166        /**
1167         * @author Patrick Harms
1168         */
1169        private static class Tasks implements Iterable<List<ITaskInstance>> {
1170
1171                /**
1172         *
1173         */
1174                private int occurrenceCount;
1175
1176                /**
1177         *
1178         */
1179                private List<List<ITaskInstance>> sequences;
1180
1181                /**
1182                 * @param occurrenceCount
1183                 * @param sequences
1184                 */
1185                private Tasks(int occurrenceCount, List<List<ITaskInstance>> sequences) {
1186                        super();
1187                        this.occurrenceCount = occurrenceCount;
1188                        this.sequences = sequences;
1189                }
1190
1191                /**
1192                 * @return
1193                 */
1194                private int getOccurrenceCount() {
1195                        return occurrenceCount;
1196                }
1197
1198                /**
1199                 * @return
1200                 */
1201                private int size() {
1202                        return this.sequences.size();
1203                }
1204
1205                /**
1206         *
1207         */
1208
1209                /*
1210                 * (non-Javadoc)
1211                 *
1212                 * @see java.lang.Iterable#iterator()
1213                 */
1214                @Override
1215                public Iterator<List<ITaskInstance>> iterator() {
1216                        return this.sequences.iterator();
1217                }
1218
1219                /*
1220                 * (non-Javadoc)
1221                 *
1222                 * @see java.lang.Object#toString()
1223                 */
1224                @Override
1225                public String toString() {
1226                        StringBuffer result = new StringBuffer();
1227                        result.append(this.occurrenceCount);
1228                        result.append(" occurrences:\n");
1229
1230                        for (List<ITaskInstance> task : sequences) {
1231                                result.append(task);
1232                                result.append("\n");
1233                        }
1234
1235                        return result.toString();
1236                }
1237
1238        }
1239
1240        // methods for internal testing
1241        // private void checkMatchingOfSessions(List<List<Event>> flattenedSessions,
1242        // List<IUserSession> sessions,
1243        // String when)
1244        // {
1245        // List<List<Event>> currentFlattenedSessions = flattenSessions(sessions);
1246        // if (flattenedSessions.size() != currentFlattenedSessions.size()) {
1247        // System.out.println("################## number of sessions changed after "
1248        // + when);
1249        // }
1250        // else {
1251        // for (int i = 0; i < flattenedSessions.size(); i++) {
1252        // List<Event> expected = flattenedSessions.get(i);
1253        // List<Event> current = currentFlattenedSessions.get(i);
1254        //
1255        // if (expected.size() != current.size()) {
1256        // System.out.println
1257        // ("################## length of session " + i + " changed after " + when);
1258        // }
1259        // else {
1260        // for (int j = 0; j < expected.size(); j++) {
1261        // if (!expected.get(j).equals(current.get(j))) {
1262        // System.out.println("################## event " + j + " of session " +
1263        // i + " changed after " + when);
1264        // }
1265        // }
1266        // }
1267        // }
1268        // }
1269        // }
1270        //
1271        // private List<List<Event>> flattenSessions(List<IUserSession> sessions) {
1272        // List<List<Event>> flattenedSessions = new ArrayList<List<Event>>();
1273        // for (IUserSession session : sessions) {
1274        // List<Event> flattenedUserSession = new ArrayList<Event>();
1275        // flatten(session, flattenedUserSession);
1276        // flattenedSessions.add(flattenedUserSession);
1277        // }
1278        //
1279        // return flattenedSessions;
1280        // }
1281        //
1282        // private void flatten(IUserSession iUserSession, List<Event>
1283        // flattenedUserSession) {
1284        // for (ITaskInstance instance : iUserSession) {
1285        // flatten(instance, flattenedUserSession);
1286        // }
1287        // }
1288        //
1289        // private void flatten(ITaskInstance instance, List<Event>
1290        // flattenedUserSession) {
1291        // if (instance instanceof ITaskInstanceList) {
1292        // for (ITaskInstance child : (ITaskInstanceList) instance) {
1293        // flatten(child, flattenedUserSession);
1294        // }
1295        // }
1296        // else if (instance instanceof ISelectionInstance) {
1297        // flatten(((ISelectionInstance) instance).getChild(),
1298        // flattenedUserSession);
1299        // }
1300        // else if (instance instanceof IOptionalInstance) {
1301        // flatten(((IOptionalInstance) instance).getChild(), flattenedUserSession);
1302        // }
1303        // else if (instance instanceof IEventTaskInstance) {
1304        // flattenedUserSession.add(((IEventTaskInstance) instance).getEvent());
1305        // }
1306        // }
1307
1308}
Note: See TracBrowser for help on using the repository browser.