source: branches/autoquest-core-tasktrees-alignment/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/SequenceForTaskDetectionRuleAlignment.java @ 1732

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

Parallel processing done
File size: 35.0 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.FileInputStream;
19import java.io.FileOutputStream;
20import java.io.IOException;
21import java.io.ObjectInputStream;
22import java.io.ObjectOutputStream;
23import java.io.Serializable;
24import java.util.ArrayList;
25import java.util.Collections;
26import java.util.Comparator;
27import java.util.HashMap;
28import java.util.HashSet;
29import java.util.Iterator;
30import java.util.LinkedList;
31import java.util.List;
32import java.util.Map;
33import java.util.Set;
34import java.util.concurrent.ExecutorService;
35import java.util.concurrent.Executors;
36import java.util.concurrent.TimeUnit;
37import java.util.logging.Level;
38
39import de.ugoe.cs.autoquest.CommandHelpers;
40import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.AlignmentAlgorithm;
41import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.AlignmentAlgorithmFactory;
42import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.Match;
43import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.MatchOccurence;
44import de.ugoe.cs.autoquest.tasktrees.alignment.algorithms.NumberSequence;
45import de.ugoe.cs.autoquest.tasktrees.alignment.matrix.ObjectDistanceSubstitionMatrix;
46import de.ugoe.cs.autoquest.tasktrees.taskequality.TaskEquality;
47import de.ugoe.cs.autoquest.tasktrees.treeifc.IIteration;
48import de.ugoe.cs.autoquest.tasktrees.treeifc.IIterationInstance;
49import de.ugoe.cs.autoquest.tasktrees.treeifc.IOptional;
50import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelection;
51import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelectionInstance;
52import de.ugoe.cs.autoquest.tasktrees.treeifc.ISequence;
53import de.ugoe.cs.autoquest.tasktrees.treeifc.ISequenceInstance;
54import de.ugoe.cs.autoquest.tasktrees.treeifc.ITask;
55import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskBuilder;
56import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskFactory;
57import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskInstance;
58import de.ugoe.cs.autoquest.tasktrees.treeifc.IUserSession;
59import de.ugoe.cs.autoquest.usageprofiles.SymbolMap;
60import de.ugoe.cs.util.StopWatch;
61import de.ugoe.cs.util.console.Console;
62import de.ugoe.cs.util.console.GlobalDataContainer;
63
64/**
65 * <p>
66 * This class implements the major rule for creating task trees based on a set
67 * of recorded user sessions. For this, it first harmonizes all tasks. This
68 * eases later comparison. Then it searches the sessions for iterations and
69 * replaces them accordingly. Then it searches for sub sequences being the
70 * longest and occurring most often. For each found sub sequence, it replaces
71 * the occurrences by creating appropriate {@link ISequence}s. Afterwards, again
72 * searches for iterations and then again for sub sequences until no more
73 * replacements are done.
74 * </p>
75 * <p>
76 *
77 *
78 * @author Patrick Harms
79 */
80public class SequenceForTaskDetectionRuleAlignment implements ISessionScopeRule {
81
82        public static int nThreads = Runtime.getRuntime().availableProcessors() - 1;
83
84        private int iteration = 0;
85        /**
86         * <p>
87         * the task factory to be used for creating substructures for the temporal
88         * relationships identified during rul application
89         * </p>
90         */
91        private ITaskFactory taskFactory;
92        /**
93         * <p>
94         * the task builder to be used for creating substructures for the temporal
95         * relationships identified during rule application
96         * </p>
97         */
98        private ITaskBuilder taskBuilder;
99
100        /**
101         * <p>
102         * the task handling strategy to be used for comparing tasks for
103         * preparation, i.e., before the tasks are harmonized
104         * </p>
105         */
106        private TaskHandlingStrategy preparationTaskHandlingStrategy;
107
108        /**
109         * <p>
110         * instantiates the rule and initializes it with a task equality to be
111         * considered when comparing tasks as well as a task factory and builder to
112         * be used for creating task structures.
113         * </p>
114         *
115         * @param minimalTaskEquality
116         *            the task equality to be considered when comparing tasks
117         * @param taskFactory
118         *            the task factory to be used for creating substructures
119         * @param taskBuilder
120         *            the task builder to be used for creating substructures
121         */
122
123        SequenceForTaskDetectionRuleAlignment(TaskEquality minimalTaskEquality,
124                        ITaskFactory taskFactory, ITaskBuilder taskBuilder) {
125                this.taskFactory = taskFactory;
126                this.taskBuilder = taskBuilder;
127
128                this.preparationTaskHandlingStrategy = new TaskHandlingStrategy(
129                                minimalTaskEquality);
130        }
131
132        /*
133         * (non-Javadoc)
134         *
135         * @see java.lang.Object#toString()
136         */
137        @Override
138        public String toString() {
139                return "SequenceForTaskDetectionRuleAlignment";
140        }
141
142        public void saveAppData(String name) {
143                String objectName = name;
144                String filename = name + ".dat";
145                Object dataObject = GlobalDataContainer.getInstance().getData(
146                                objectName);
147                if (dataObject == null) {
148                        CommandHelpers.objectNotFoundMessage(objectName);
149                }
150                FileOutputStream fos = null;
151                ObjectOutputStream out = null;
152                try {
153                        fos = new FileOutputStream(filename);
154                        out = new ObjectOutputStream(fos);
155                        out.writeObject(dataObject);
156                        out.close();
157                } catch (IOException ex) {
158                        Console.logException(ex);
159                }
160        }
161
162        public RuleApplicationData loadAppData(String name) {
163                String objectName = name;
164                String filename = name + ".dat";
165
166                Object data = null;
167                FileInputStream fis = null;
168                ObjectInputStream in = null;
169                try {
170                        fis = new FileInputStream(filename);
171                        in = new ObjectInputStream(fis);
172                        data = in.readObject();
173                        in.close();
174                } catch (IOException ex) {
175                        Console.logException(ex);
176                } catch (ClassNotFoundException ex) {
177                        Console.logException(ex);
178                }
179                if (GlobalDataContainer.getInstance().addData(objectName, data)) {
180                        CommandHelpers.dataOverwritten(objectName);
181                }
182                return (RuleApplicationData) GlobalDataContainer.getInstance().getData(
183                                name);
184        }
185
186        /*
187         * (non-Javadoc)
188         *
189         * @see
190         * de.ugoe.cs.autoquest.tasktrees.temporalrelation.ISessionScopeRule#apply
191         * (java.util.List)
192         */
193        @Override
194        public RuleApplicationResult apply(List<IUserSession> sessions) {
195                RuleApplicationData appData = new RuleApplicationData(sessions);
196                // File harmonized = new File("harmonized.dat");
197                // if(harmonized.exists() && !harmonized.isDirectory()) {
198                // Console.traceln(Level.INFO,"loading harmonized sessions from file");
199                // appData = loadAppData("harmonized");
200                // }
201                // else {
202                // appData.getStopWatch().start("harmonization");
203                harmonizeEventTaskInstancesModel(appData);
204                // appData.getStopWatch().stop("harmonization");
205                GlobalDataContainer.getInstance().addData("harmonized", appData);
206                // Saving intermediate results to file
207                Console.traceln(Level.INFO, "saving substitution matrix to file");
208                // saveAppData("harmonized");
209                // }
210
211                // File substitution = new File("substitution.dat");
212                // if(!(substitution.exists() && !substitution.isDirectory())) {
213                Console.traceln(Level.INFO, "generating substitution matrix from "
214                                + appData.getUniqueTasks().size() + " unique tasks");
215                appData.getStopWatch().start("substitution matrix");
216                appData.getSubmat().generate(appData.getUniqueTasks());
217                appData.getStopWatch().stop("substitution matrix");
218                // GlobalDataContainer.getInstance().addData("substitution", appData);
219                // saveAppData("substitution");
220                // }
221                // else {
222                // Console.traceln(Level.INFO,"loading substitution matrix from file");
223                // appData = loadAppData("substitution");
224                // }
225
226                Console.traceln(Level.INFO, "Starting main loop");
227                do {
228                        Console.traceln(Level.INFO, "Iteration Number: " + iteration);
229                        iteration++;
230                        appData.detectedAndReplacedTasks = false;
231                        appData.getStopWatch().start("whole loop");
232                        detectAndReplaceIterations(appData);
233                        appData.getStopWatch().start("task replacement");
234                        //appData.updateSubstitutionMatrix();
235                        detectAndReplaceTasks(appData); //
236                        appData.getStopWatch().stop("task replacement");
237                        appData.getStopWatch().stop("whole loop");
238                        appData.getStopWatch().dumpStatistics(System.out);
239                        appData.getStopWatch().reset();
240
241                } while (appData.detectedAndReplacedTasks());
242
243                Console.println("created "
244                                + appData.getResult().getNewlyCreatedTasks().size()
245                                + " new tasks and "
246                                + appData.getResult().getNewlyCreatedTaskInstances().size()
247                                + " appropriate instances\n");
248
249                if ((appData.getResult().getNewlyCreatedTasks().size() > 0)
250                                || (appData.getResult().getNewlyCreatedTaskInstances().size() > 0)) {
251                        appData.getResult().setRuleApplicationStatus(
252                                        RuleApplicationStatus.FINISHED);
253                }
254
255                return appData.getResult();
256        }
257
258        private ArrayList<NumberSequence> createNumberSequences(
259                        RuleApplicationData appData) {
260                ArrayList<NumberSequence> result = new ArrayList<NumberSequence>();
261                for (int i = 0; i < appData.getSessions().size(); i++) {
262                        IUserSession session = appData.getSessions().get(i);
263                        NumberSequence templist = new NumberSequence(session.size());
264                        for (int j = 0; j < session.size(); j++) {
265                                ITaskInstance taskInstance = session.get(j);
266                                templist.getSequence()[j] = taskInstance.getTask().getId();
267                        }
268                        // Each NumberSequence is identified by its id, beginning to count
269                        // at zero
270                        templist.setId(i);
271                        result.add(templist);
272                }
273                return result;
274        }
275
276        /**
277         * <p>
278         * harmonizes the event task instances by unifying tasks. This is done, as
279         * initially the event tasks being equal with respect to the considered task
280         * equality are distinct objects. The comparison of these distinct objects
281         * is more time consuming than comparing the object references.
282         * </p>
283         *
284         * @param appData
285         *            the rule application data combining all data used for applying
286         *            this rule
287         * @return Returns the unique tasks symbol map
288         */
289        private void harmonizeEventTaskInstancesModel(RuleApplicationData appData) {
290                Console.traceln(Level.INFO,
291                                "harmonizing task model of event task instances");
292                appData.getStopWatch().start("harmonizing event tasks");
293                SymbolMap<ITaskInstance, ITask> uniqueTasks = preparationTaskHandlingStrategy
294                                .createSymbolMap();
295
296                TaskInstanceComparator comparator = preparationTaskHandlingStrategy
297                                .getTaskComparator();
298
299                int unifiedTasks = 0;
300                ITask task;
301                List<IUserSession> sessions = appData.getSessions();
302                for (int j = 0; j < sessions.size(); j++) {
303                        IUserSession session = sessions.get(j);
304
305                        for (int i = 0; i < session.size(); i++) {
306                                ITaskInstance taskInstance = session.get(i);
307                                task = uniqueTasks.getValue(taskInstance);
308
309                                if (task == null) {
310                                        uniqueTasks.addSymbol(taskInstance, taskInstance.getTask());
311                                        appData.getUniqueTasks().add(taskInstance.getTask());
312                                        appData.getNumber2Task().put(
313                                                        taskInstance.getTask().getId(),
314                                                        taskInstance.getTask());
315                                } else {
316                                        taskBuilder.setTask(taskInstance, task);
317                                        unifiedTasks++;
318                                }
319                        }
320                        comparator.clearBuffers();
321                }
322
323                appData.getStopWatch().stop("harmonizing event tasks");
324                Console.traceln(Level.INFO, "harmonized " + unifiedTasks
325                                + " task occurrences (still " + appData.getUniqueTasks().size()
326                                + " different tasks)");
327
328                appData.getStopWatch().dumpStatistics(System.out);
329                appData.getStopWatch().reset();
330        }
331
332        /**
333         * <p>
334         * searches for direct iterations of single tasks in all sequences and
335         * replaces them with {@link IIteration}s, respectively appropriate
336         * instances. Also all single occurrences of a task that is iterated
337         * somewhen are replaced with iterations to have again an efficient way for
338         * task comparisons.
339         * </p>
340         *
341         * @param appData
342         *            the rule application data combining all data used for applying
343         *            this rule
344         */
345        private void detectAndReplaceIterations(RuleApplicationData appData) {
346                Console.traceln(Level.FINE, "detecting iterations");
347                appData.getStopWatch().start("detecting iterations");
348
349                List<IUserSession> sessions = appData.getSessions();
350
351                Set<ITask> iteratedTasks = searchIteratedTasks(sessions);
352
353                if (iteratedTasks.size() > 0) {
354                        replaceIterationsOf(iteratedTasks, sessions, appData);
355                }
356
357                appData.getStopWatch().stop("detecting iterations");
358                Console.traceln(Level.INFO, "replaced " + iteratedTasks.size()
359                                + " iterated tasks");
360        }
361
362        /**
363         * <p>
364         * searches the provided sessions for task iterations. If a task is
365         * iterated, it is added to the returned set.
366         * </p>
367         *
368         * @param the
369         *            session to search for iterations in
370         *
371         * @return a set of tasks being iterated somewhere
372         */
373        private Set<ITask> searchIteratedTasks(List<IUserSession> sessions) {
374                Set<ITask> iteratedTasks = new HashSet<ITask>();
375                for (IUserSession session : sessions) {
376                        for (int i = 0; i < (session.size() - 1); i++) {
377                                // we prepared the task instances to refer to unique tasks, if
378                                // they are treated
379                                // as equal. Therefore, we just compare the identity of the
380                                // tasks of the task
381                                // instances
382                                if (session.get(i).getTask() == session.get(i + 1).getTask()) {
383                                        iteratedTasks.add(session.get(i).getTask());
384                                }
385                        }
386                }
387                return iteratedTasks;
388        }
389
390        /**
391         * <p>
392         * replaces all occurrences of all tasks provided in the set with iterations
393         * </p>
394         *
395         * @param iteratedTasks
396         *            the tasks to be replaced with iterations
397         * @param sessions
398         *            the sessions in which the tasks are to be replaced
399         * @param appData
400         *            the rule application data combining all data used for applying
401         *            this rule
402         */
403        private void replaceIterationsOf(Set<ITask> iteratedTasks,
404                        List<IUserSession> sessions, RuleApplicationData appData) {
405                Map<ITask, IIteration> iterations = new HashMap<ITask, IIteration>();
406                Map<IIteration, List<IIterationInstance>> iterationInstances = new HashMap<IIteration, List<IIterationInstance>>();
407
408                for (ITask iteratedTask : iteratedTasks) {
409
410                        IIteration iteration = taskFactory.createNewIteration();
411                        appData.newTaskCreated(iteration);
412                        iterations.put(iteratedTask, iteration);
413                        iterationInstances.put(iteration,
414                                        new LinkedList<IIterationInstance>());
415                }
416
417                IIterationInstance iterationInstance;
418
419                for (IUserSession session : sessions) {
420                        int index = 0;
421                        iterationInstance = null;
422
423                        while (index < session.size()) {
424                                // we prepared the task instances to refer to unique tasks, if
425                                // they are treated
426                                // as equal. Therefore, we just compare the identity of the
427                                // tasks of the task
428                                // instances
429                                ITask currentTask = session.get(index).getTask();
430                                IIteration iteration = iterations.get(currentTask);
431                                if (iteration != null) {
432                                        if ((iterationInstance == null)
433                                                        || (iterationInstance.getTask() != iteration)) {
434                                                iterationInstance = taskFactory
435                                                                .createNewTaskInstance(iteration);
436                                                iterationInstances.get(iteration)
437                                                                .add(iterationInstance);// TODO:: Don't create
438                                                                                                                // TaskInstances here,
439                                                                                                                // use a set of tasks
440                                                                                                                // instead
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         * @param appData
528         * @param m
529         * @return
530         */
531        synchronized public ISequence matchAsSequence(RuleApplicationData appData, Match m) {
532                ISequence sequence = taskFactory.createNewSequence();
533                appData.newTaskCreated(sequence);
534
535                int[] first = m.getFirstSequence().getSequence();
536                int[] second = m.getSecondSequence().getSequence();
537
538                // Both sequences of a match are equally long
539                for (int i = 0; i < m.getFirstSequence().size(); i++) {
540
541                        // Two gaps aligned to each other: Have not seen it happening so
542                        // far, just to handle it
543                        if (first[i] == -1 && second[i] == -1) {
544                                // Do nothing here.
545                        }
546                        // Both events are equal, we can simply add the task referring to
547                        // the number
548                        else if (first[i] == second[i]) {
549                                taskBuilder.addChild(sequence,
550                                                appData.getNumber2Task().get(first[i]));
551                        }
552                        // We have a gap in the first sequence, we need to add the task of
553                        // the second sequence as optional
554                        else if (first[i] == -1 && second[i] != -1) {
555                                IOptional optional = taskFactory.createNewOptional();
556                                appData.newTaskCreated(optional);
557                                taskBuilder.setMarkedTask(optional, appData.getNumber2Task()
558                                                .get(second[i]));
559                                taskBuilder.addChild(sequence, optional);
560                        }
561                        // We have a gap in the second sequence, we need to add the task of
562                        // the first sequence as optional
563                        else if (first[i] != -1 && second[i] == -1) {
564                                IOptional optional = taskFactory.createNewOptional();
565                                appData.newTaskCreated(optional);
566                                taskBuilder.setMarkedTask(optional, appData.getNumber2Task()
567                                                .get(first[i]));
568                                taskBuilder.addChild(sequence, optional);
569                        }
570                        // Both tasks are not equal, we need to insert a selection here.
571                        // Check if the next position is not a selection
572                        else if (i < first.length - 1) {
573
574                                if ((first[i] != second[i])
575                                                && ((first[i + 1] == second[i + 1]
576                                                                || first[i + 1] == -1 || second[i + 1] == -1))) {
577
578                                        ISelection selection = taskFactory.createNewSelection();
579                                        appData.newTaskCreated(selection);
580                                        taskBuilder.addChild(selection, appData.getNumber2Task()
581                                                        .get(first[i]));
582                                        taskBuilder.addChild(selection, appData.getNumber2Task()
583                                                        .get(second[i]));
584                                        taskBuilder.addChild(sequence, selection);
585                                } else {
586                                        boolean selectionfound = true;
587                                        ISelection selection = taskFactory.createNewSelection();
588                                        appData.newTaskCreated(selection);
589
590                                        ISequence subsequence1 = taskFactory.createNewSequence();
591                                        appData.newTaskCreated(subsequence1);
592
593                                        ISequence subsequence2 = taskFactory.createNewSequence();
594                                        appData.newTaskCreated(subsequence2);
595
596                                        taskBuilder.addChild(selection, subsequence1);
597                                        taskBuilder.addChild(selection, subsequence2);
598                                        taskBuilder.addChild(sequence, selection);
599                                        while (i < first.length - 1 && selectionfound) {
600                                                selectionfound = false;
601                                                taskBuilder.addChild(subsequence1, appData
602                                                                .getNumber2Task().get(first[i]));
603                                                taskBuilder.addChild(subsequence2, appData
604                                                                .getNumber2Task().get(second[i]));
605                                                if (first[i + 1] != second[i + 1] && first[i + 1] != -1
606                                                                && second[i + 1] != -1) {
607                                                        selectionfound = true;
608                                                } else {
609                                                        continue;
610                                                }
611                                                i++;
612                                        }
613                                        if (i == first.length - 1 && selectionfound) {
614                                                taskBuilder.addChild(subsequence1, appData
615                                                                .getNumber2Task().get(first[i]));
616                                                taskBuilder.addChild(subsequence2, appData
617                                                                .getNumber2Task().get(second[i]));
618                                        }
619                                }
620                        } else {
621                                if ((first[i] != second[i])) {
622
623                                        ISelection selection = taskFactory.createNewSelection();
624                                        appData.newTaskCreated(selection);
625                                        taskBuilder.addChild(selection, appData.getNumber2Task()
626                                                        .get(first[i]));
627                                        taskBuilder.addChild(selection, appData.getNumber2Task()
628                                                        .get(second[i]));
629                                        taskBuilder.addChild(sequence, selection);
630                                }
631                        }
632
633                }
634                return sequence;
635        }
636
637        /**
638         *
639         * @param appData
640         *            the rule application data combining all data used for applying
641         *            this rule
642         */
643        private void detectAndReplaceTasks(RuleApplicationData appData) {
644                Console.traceln(Level.FINE, "detecting and replacing tasks");
645                appData.getStopWatch().start("detecting tasks");
646
647                // Create NumberSequences
648                appData.setNumberSequences(this.createNumberSequences(appData));
649
650                // Generate pairwise alignments
651                // appData.setMatchseqs(generatePairwiseAlignments(appData));
652                generatePairwiseAlignments(appData);
653
654                // Searching each match in all other sessions, counting its occurences
655                searchMatchesInAllSessions(appData);
656
657                // Sort results to get the most occurring results
658                Console.traceln(Level.INFO, "sorting " + appData.getMatchseqs().size()
659                                + " results");
660                Comparator<Match> comparator = new Comparator<Match>() {
661                        public int compare(Match m1, Match m2) {
662                                return m2.occurenceCount() - m1.occurenceCount();
663
664                        }
665                };
666
667                Collections.sort(appData.getMatchseqs(), comparator);
668                appData.getStopWatch().stop("detecting tasks");
669
670                // Replace matches in the sessions
671                Console.traceln(Level.INFO, "Replacing matches in sessions");
672                replaceMatches(appData);
673                appData.getStopWatch().start("replacing tasks");
674               
675                // appData.setMatchseqs(null);
676                appData.getStopWatch().stop("replacing tasks");
677        }
678
679        private void replaceMatches(RuleApplicationData appData) {
680                appData.replacedOccurences = new HashMap<Integer, List<MatchOccurence>>();
681               
682                int matchSeqSize = appData.getMatchseqs().size();
683                int newThreads = nThreads;
684                if (matchSeqSize < nThreads) {
685                        newThreads = matchSeqSize;
686                }
687                ExecutorService executor = Executors.newFixedThreadPool(newThreads);
688                int interval = matchSeqSize / newThreads;
689                int rest = matchSeqSize % newThreads;
690               
691                for (int i = 0; i < matchSeqSize - interval; i += interval) {
692                        int offset = 0;
693                        if (rest != 0) {
694                                offset = 1;
695                                rest--;
696                        }
697                        int from = i;
698                        int to = i + interval + offset;
699                        System.out.println("Replacement: Creating thread with matches from " + from
700                                        + " to " + to);
701                        // search each match in every other sequence
702                        ParallelMatchReplacer replacer = new ParallelMatchReplacer(
703                                        appData, from, to);
704                        executor.execute(replacer);
705                }
706                executor.shutdown();
707                try {
708                        executor.awaitTermination(2, TimeUnit.HOURS);
709                } catch (InterruptedException e) {
710                        // TODO Auto-generated catch block
711                        e.printStackTrace();
712                }
713        }
714
715        private void searchMatchesInAllSessions(RuleApplicationData appData) {
716                Console.traceln(Level.INFO,
717                                "searching for patterns occuring most with " + nThreads
718                                                + " threads");
719                // Prepare parallel search of matchseqs
720               
721                int matchSeqSize = appData.getMatchseqs().size();
722                int newThreads = nThreads;
723                if (matchSeqSize < nThreads) {
724                        newThreads = matchSeqSize;
725                }
726                int interval = matchSeqSize / newThreads;
727                int rest = matchSeqSize % newThreads;
728                ExecutorService executor = Executors.newFixedThreadPool(nThreads);
729               
730                for (int i = 0; i < matchSeqSize - interval; i += interval) {
731                        int offset = 0;
732                        if (rest != 0) {
733                                offset = 1;
734                                rest--;
735                        }
736                        int from = i;
737                        int to = i + interval + offset;
738                        System.out.println("Match finding: Creating thread with matches from " + from
739                                        + " to " + to);
740                        // search each match in every other sequence
741                        ParallelMatchOcurrencesFinder finder = new ParallelMatchOcurrencesFinder(
742                                        appData, from, to);
743                        executor.execute(finder);
744                }
745                executor.shutdown();
746                try {
747                        executor.awaitTermination(2, TimeUnit.HOURS);
748                } catch (InterruptedException e) {
749                        // TODO Auto-generated catch block
750                        e.printStackTrace();
751                }
752
753        }
754
755
756        private class ParallelMatchReplacer implements Runnable {
757
758                private final RuleApplicationData appData;
759                private final int from;
760                private final int to;
761
762                ParallelMatchReplacer(RuleApplicationData appData, int from,
763                                int to) {
764                        this.appData = appData;
765                        this.from = from;
766                        this.to = to;
767                }
768                @Override
769                public void run() {
770                        int count = 0;
771                        int size = to - from;
772                        for (int i = from; i < to; i++) {
773                        count++;
774                        // Every pattern consists of 2 sequences, therefore the minimum
775                        // occurrences here is 2.
776                        // We just need the sequences also occurring in other sequences as well
777                        if (appData.getMatchseqs().get(i).occurenceCount() > 2) {
778                               
779                                ISequence task = matchAsSequence(appData, appData.getMatchseqs().get(i));
780                                                        invalidOccurence: for (Iterator<MatchOccurence> it = appData
781                                                                        .getMatchseqs().get(i).getOccurences().iterator(); it
782                                                                        .hasNext();) {
783                                                                MatchOccurence oc = it.next();
784
785                                                                // Check if nothing has been replaced in the sequence we
786                                                                // want to replace now
787                                                               
788                                                                synchronized (appData.getReplacedOccurences()) {
789                                                                if (appData.getReplacedOccurences().get(oc.getSequenceId()) == null) {
790                                                                        appData.getReplacedOccurences().put(oc.getSequenceId(),
791                                                                                        new LinkedList<MatchOccurence>());
792                                                                } else {
793                                                                        // check if we have any replaced occurence with indexes
794                                                                        // smaller than ours. If so, we need to adjust our start
795                                                                        // and endpoints
796                                                                        // of the replacement.
797                                                                        // Also do a check if we have replaced this specific
798                                                                        // MatchOccurence in this sequence already. Jump to the
799                                                                        // next occurence if this is the case.
800                                                                        // This is no more neccessary once the matches are
801                                                                        // harmonized.
802                                                                        for (Iterator<MatchOccurence> jt = appData.getReplacedOccurences()
803                                                                                        .get(oc.getSequenceId()).iterator(); jt
804                                                                                        .hasNext();) {
805                                                                                MatchOccurence tmpOC = jt.next();
806
807                                                                                if (oc.getStartindex() >= tmpOC.getStartindex()
808                                                                                                && oc.getStartindex() <= tmpOC
809                                                                                                                .getEndindex()) {
810                                                                                        continue invalidOccurence;
811                                                                                }
812                                                                                if (oc.getEndindex() >= tmpOC.getStartindex()) {
813                                                                                        continue invalidOccurence;
814
815                                                                                } else if (oc.getStartindex() > tmpOC.getEndindex()) {
816                                                                                        int diff = tmpOC.getEndindex()
817                                                                                                        - tmpOC.getStartindex();
818                                                                                        // Just to be sure.
819                                                                                        if (diff > 0) {
820                                                                                                oc.setStartindex(oc.getStartindex() - diff
821                                                                                                                + 1);
822                                                                                                oc.setEndindex(oc.getEndindex() - diff + 1);
823                                                                                        } else {
824                                                                                                Console.traceln(Level.WARNING,
825                                                                                                                "End index of a Match before start. This should never happen");
826                                                                                        }
827                                                                                }
828                                                                        }
829                                                                }
830                                                                System.out.println("Replacing in sequence"
831                                                                                + oc.getSequenceId());
832                                                                synchronized(appData) {
833                                                                        appData.detectedAndReplacedTasks = true;
834                                                                }
835                                                                synchronized (appData.getSessions().get(oc.getSequenceId())) {
836                                                                        ISequenceInstance sequenceInstances = RuleUtils
837                                                                                        .createNewSubSequenceInRange(appData.getSessions()
838                                                                                                        .get(oc.getSequenceId()), oc
839                                                                                                        .getStartindex(), oc.getEndindex(), task,
840                                                                                                        taskFactory, taskBuilder);
841                                                                        oc.setEndindex(oc.getStartindex()
842                                                                                        + sequenceInstances.size()
843                                                                                        - RuleUtils.missedOptionals);
844                                                                        }
845                                                                }
846                                                                // Adjust the length of the match regarding to the length of
847                                                                // instance. (OptionalInstances may be shorter)
848                                                               
849                                                                synchronized(appData.getReplacedOccurences().get(oc.getSequenceId())) {
850                                                                        appData.getReplacedOccurences().get(oc.getSequenceId()).add(oc);
851                                                                }
852                                                        }
853                                                }
854                                        }
855                                }       
856                        }
857               
858       
859
860        private class ParallelMatchOcurrencesFinder implements Runnable {
861                private final RuleApplicationData appData;
862                private final int from;
863                private final int to;
864
865                ParallelMatchOcurrencesFinder(RuleApplicationData appData, int from,
866                                int to) {
867                        this.appData = appData;
868                        this.from = from;
869                        this.to = to;
870                }
871
872                @Override
873                public void run() {
874                        int count = 0;
875                        int size = to - from;
876
877                        for (int i = from; i < to; i++) {
878                                Match pattern = appData.getMatchseqs().get(i);
879                                count++;
880                                RuleUtils.printProgressPercentage("Match finding progress",count, size);
881                                // Skip sequences with more 0 events (scrolls) than other
882                                // events.
883                                // Both of the pattern sequences are equally long, so the zero
884                                // counts just need to be smaller than the length of one
885                                // sequence
886                                if (pattern.getFirstSequence().eventCount(0)
887                                                + pattern.getSecondSequence().eventCount(0) + 1 > pattern
888                                                .getFirstSequence().size())
889                                        continue;
890
891                                for (int j = 0; j < appData.getNumberSequences().size(); j++) {
892                                        LinkedList<Integer> startpositions = appData
893                                                        .getNumberSequences().get(j)
894                                                        .containsPattern(pattern);
895                                        if (startpositions.size() > 0) {
896                                                for (Iterator<Integer> jt = startpositions.iterator(); jt
897                                                                .hasNext();) {
898                                                        int start = jt.next();
899                                                        pattern.addOccurence(new MatchOccurence(start,
900                                                                        start + pattern.size(), j));
901                                                }
902                                        }
903                                }
904                        }
905                }
906        }
907
908        private class ParallelPairwiseAligner implements Runnable {
909                private final RuleApplicationData appData;
910                private final int from;
911                private final int to;
912
913                ParallelPairwiseAligner(RuleApplicationData appData, int from, int to) {
914                        this.appData = appData;
915                        this.from = from;
916                        this.to = to;
917                }
918
919                @Override
920                public void run() {
921                        int count = 0;
922                        int size = to - from;
923
924                        for (int i = from; i < to; i++) {
925                                NumberSequence ns1 = appData.getNumberSequences().get(i);
926                                count++;
927                                RuleUtils.printProgressPercentage("Aligning Progress",count, size);
928                                for (int j = 0; j < appData.getNumberSequences().size(); j++) {
929                                        NumberSequence ns2 = appData.getNumberSequences().get(j);
930                                        if (i != j) {
931                                                AlignmentAlgorithm aa = AlignmentAlgorithmFactory
932                                                                .create();
933                                                aa.align(ns1, ns2, appData.getSubmat(), 9);
934                                                synchronized (appData.getMatchseqs()) {
935                                                        appData.getMatchseqs().addAll(aa.getMatches());
936                                                }
937                                        }
938                                }
939                        }
940                }
941        }
942
943        // private LinkedList<Match> generatePairwiseAlignments(RuleApplicationData
944        // appData) {
945        private void generatePairwiseAlignments(RuleApplicationData appData) {
946                int numberSeqSize = appData.getNumberSequences().size();
947                appData.matchseqs = new LinkedList<Match>();
948                Console.traceln(Level.INFO, "generating pairwise alignments from "
949                                + numberSeqSize + " sessions with " + nThreads + " threads");
950               
951                int newThreads = nThreads;
952                if (numberSeqSize < nThreads) {
953                        newThreads = numberSeqSize;
954                }
955               
956                ExecutorService executor = Executors.newFixedThreadPool(newThreads);
957                int interval = numberSeqSize / newThreads;
958                int rest = numberSeqSize % newThreads;
959
960                for (int i = 0; i < numberSeqSize - interval; i += interval) {
961                        int offset = 0;
962                        if (rest != 0) {
963                                offset = 1;
964                                rest--;
965                        }
966                        int from = i;
967                        int to = i + interval + offset;
968                        System.out.println("Creating thread for sessions " + from
969                                        + " till " + to);
970                        ParallelPairwiseAligner aligner = new ParallelPairwiseAligner(
971                                        appData, from, to);
972                        executor.execute(aligner);
973                }
974                executor.shutdown();
975                try {
976                        executor.awaitTermination(2, TimeUnit.HOURS);
977                } catch (InterruptedException e) {
978                        // TODO Auto-generated catch block
979                        e.printStackTrace();
980                }
981        }
982
983        /**
984     *
985     */
986        private static class RuleApplicationData implements Serializable {
987
988                /**
989                 *
990                 */
991                private static final long serialVersionUID = -7559657686755522960L;
992
993                private HashMap<Integer, ITask> number2task;
994
995                // TODO: We Actually just need number2task here, this structure can be
996                // removed in the future.
997                private HashSet<ITask> uniqueTasks;
998
999                private ObjectDistanceSubstitionMatrix submat;
1000               
1001                public HashMap<Integer, List<MatchOccurence>> replacedOccurences;
1002               
1003       
1004                public LinkedList<Match> matchseqs;
1005
1006                private ArrayList<NumberSequence> numberseqs;
1007
1008                private LinkedList<ITask> newTasks;
1009
1010                /**
1011         *
1012         */
1013                private List<IUserSession> sessions;
1014
1015                /**
1016         *
1017         */
1018                private boolean detectedAndReplacedTasks;
1019
1020                /**
1021         *
1022         */
1023                private RuleApplicationResult result;
1024
1025                /**
1026         *
1027         */
1028                private StopWatch stopWatch;
1029
1030                /**
1031         *
1032         */
1033                private RuleApplicationData(List<IUserSession> sessions) {
1034                        this.sessions = sessions;
1035                        numberseqs = new ArrayList<NumberSequence>();
1036                        uniqueTasks = new HashSet<ITask>();
1037                        number2task = new HashMap<Integer, ITask>();
1038                        stopWatch = new StopWatch();
1039                        result = new RuleApplicationResult();
1040                        submat = new ObjectDistanceSubstitionMatrix(6, -3, false);
1041                        newTasks = new LinkedList<ITask>();
1042                        this.detectedAndReplacedTasks = true;
1043                }
1044
1045                public LinkedList<Match> getMatchseqs() {
1046                        return matchseqs;
1047                }
1048
1049                private ObjectDistanceSubstitionMatrix getSubmat() {
1050                        return submat;
1051                }
1052
1053                synchronized private void resetNewlyCreatedTasks() {
1054                        uniqueTasks.addAll(newTasks);
1055                        newTasks.clear();
1056                }
1057
1058                private void newTaskCreated(ITask task) {
1059                        number2task.put(task.getId(), task);
1060                        newTasks.add(task);
1061                }
1062
1063                /**
1064                 * @return the UserSessions as List.
1065                 */
1066                private List<IUserSession> getSessions() {
1067                        return sessions;
1068                }
1069               
1070
1071                public HashMap<Integer, List<MatchOccurence>> getReplacedOccurences() {
1072                        return replacedOccurences;
1073                }
1074
1075                public void setReplacedOccurences(
1076                                HashMap<Integer, List<MatchOccurence>> replacedOccurences) {
1077                        this.replacedOccurences = replacedOccurences;
1078                }
1079
1080
1081                private HashSet<ITask> getUniqueTasks() {
1082                        return uniqueTasks;
1083                }
1084
1085                private void setNumberSequences(ArrayList<NumberSequence> numberseqs) {
1086                        this.numberseqs = numberseqs;
1087                }
1088
1089                private ArrayList<NumberSequence> getNumberSequences() {
1090                        return numberseqs;
1091                }
1092
1093                private void updateSubstitutionMatrix() {
1094                        submat.update(getNewTasks());
1095                        resetNewlyCreatedTasks();
1096                }
1097
1098                /**
1099         *
1100         */
1101                private boolean detectedAndReplacedTasks() {
1102                        return detectedAndReplacedTasks;
1103                }
1104
1105                /**
1106                 * @return the result
1107                 */
1108                private RuleApplicationResult getResult() {
1109                        return result;
1110                }
1111
1112                public LinkedList<ITask> getNewTasks() {
1113                        return newTasks;
1114                }
1115
1116                /**
1117                 * @return the stopWatch
1118                 */
1119                private StopWatch getStopWatch() {
1120                        return stopWatch;
1121                }
1122
1123                private HashMap<Integer, ITask> getNumber2Task() {
1124                        return number2task;
1125                }
1126
1127        }
1128
1129}
Note: See TracBrowser for help on using the repository browser.