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

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

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