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

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

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