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

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

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