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

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

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