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

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

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