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

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

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