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

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

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