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

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

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