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

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

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