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

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

Some refactoring for storing the initial alignments so we don't need to do them again.
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
28import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.NumberSequence;
29import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.SmithWatermanRepeated;
30import de.ugoe.cs.autoquest.tasktrees.alignment.matrix.BinaryAlignmentStorage;
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.UPGMAAligningTree;
34import de.ugoe.cs.autoquest.tasktrees.taskequality.TaskEquality;
35import de.ugoe.cs.autoquest.tasktrees.treeifc.IIteration;
36import de.ugoe.cs.autoquest.tasktrees.treeifc.IIterationInstance;
37import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelection;
38import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelectionInstance;
39import de.ugoe.cs.autoquest.tasktrees.treeifc.ISequence;
40import de.ugoe.cs.autoquest.tasktrees.treeifc.ISequenceInstance;
41import de.ugoe.cs.autoquest.tasktrees.treeifc.ITask;
42import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskBuilder;
43import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskFactory;
44import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskInstance;
45import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskInstanceList;
46import de.ugoe.cs.autoquest.tasktrees.treeifc.IUserSession;
47import de.ugoe.cs.autoquest.usageprofiles.SymbolMap;
48import de.ugoe.cs.autoquest.usageprofiles.TrieProcessor;
49import de.ugoe.cs.util.StopWatch;
50import de.ugoe.cs.util.console.Console;
51
52/**
53 * <p>
54 * This class implements the major rule for creating task trees based on a set
55 * of recorded user sessions. For this, it first harmonizes all tasks. This
56 * eases later comparison. Then it searches the sessions for iterations and
57 * replaces them accordingly. Then it searches for sub sequences being the
58 * longest and occurring most often. For each found sub sequence, it replaces
59 * the occurrences by creating appropriate {@link ISequence}s. Afterwards, again
60 * searches for iterations and then again for sub sequences until no more
61 * replacements are done.
62 * </p>
63 * <p>
64
65 *
66 * @author Patrick Harms
67 */
68class SequenceForTaskDetectionRuleAlignment implements ISessionScopeRule {
69
70        /**
71         * <p>
72         * the task factory to be used for creating substructures for the temporal
73         * relationships identified during rul application
74         * </p>
75         */
76        private ITaskFactory taskFactory;
77        /**
78         * <p>
79         * the task builder to be used for creating substructures for the temporal
80         * relationships identified during rule application
81         * </p>
82         */
83        private ITaskBuilder taskBuilder;
84
85        /**
86         * <p>
87         * the task handling strategy to be used for comparing tasks for
88         * preparation, i.e., before the tasks are harmonized
89         * </p>
90         */
91        private TaskHandlingStrategy preparationTaskHandlingStrategy;
92
93        /**
94         * <p>
95         * the task handling strategy to be used for comparing tasks during
96         * iteration detection an trie generation, i.e., after the tasks are
97         * harmonized
98         * </p>
99         */
100        private TaskHandlingStrategy identityTaskHandlingStrategy;;
101
102        private ArrayList<NumberSequence> numberseqs;
103
104        /**
105         * <p>
106         * instantiates the rule and initializes it with a task equality to be
107         * considered when comparing tasks as well as a task factory and builder to
108         * be used for creating task structures.
109         * </p>
110         *
111         * @param minimalTaskEquality
112         *            the task equality to be considered when comparing tasks
113         * @param taskFactory
114         *            the task factory to be used for creating substructures
115         * @param taskBuilder
116         *            the task builder to be used for creating substructures
117         */
118
119        SequenceForTaskDetectionRuleAlignment(TaskEquality minimalTaskEquality,
120                        ITaskFactory taskFactory, ITaskBuilder taskBuilder) {
121                this.taskFactory = taskFactory;
122                this.taskBuilder = taskBuilder;
123
124                this.preparationTaskHandlingStrategy = new TaskHandlingStrategy(
125                                minimalTaskEquality);
126                this.identityTaskHandlingStrategy = new TaskHandlingStrategy(
127                                TaskEquality.IDENTICAL);
128                numberseqs = new ArrayList<NumberSequence>();
129
130        }
131
132        /*
133         * (non-Javadoc)
134         *
135         * @see java.lang.Object#toString()
136         */
137        @Override
138        public String toString() {
139                return "SequenceForTaskDetectionRuleAlignment";
140        }
141
142        /*
143         * (non-Javadoc)
144         *
145         * @see
146         * de.ugoe.cs.autoquest.tasktrees.temporalrelation.ISessionScopeRule#apply
147         * (java.util.List)
148         */
149        @Override
150        public RuleApplicationResult apply(List<IUserSession> sessions) {
151                RuleApplicationData appData = new RuleApplicationData(sessions);
152
153                // this is the real rule application. Loop while something is replaced.
154                SymbolMap<ITaskInstance, ITask> uniqueTasks = harmonizeEventTaskInstancesModel(appData);
155
156                ObjectDistanceSubstitionMatrix submat = new ObjectDistanceSubstitionMatrix(
157                                uniqueTasks, 5);
158                submat.generate();
159
160       
161                BinaryAlignmentStorage alignments = new BinaryAlignmentStorage(numberseqs.size());
162
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                                        alignments.set(i, j,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 = alignments.get(i,j).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 < alignments.getDistance(i, j)) {   
202                                                        alignments.setDistance(i,j,distance );
203                                                }
204                                        }
205                                }
206                        }
207                }
208                //System.out.println(sequenceDistances.toString());
209                UPGMAAligningTree guidetree = new UPGMAAligningTree(numberseqs, alignments);
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.