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

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

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