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

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

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