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

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

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