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

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

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