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

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

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