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

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

Removing loading intermediate results from file, cause unexpected, weird behaviour
File size: 33.8 KB
Line 
1//   Copyright 2012 Georg-August-Universität Göttingen, Germany
2//
3//   Licensed under the Apache License, Version 2.0 (the "License");
4//   you may not use this file except in compliance with the License.
5//   You may obtain a copy of the License at
6//
7//       http://www.apache.org/licenses/LICENSE-2.0
8//
9//   Unless required by applicable law or agreed to in writing, software
10//   distributed under the License is distributed on an "AS IS" BASIS,
11//   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12//   See the License for the specific language governing permissions and
13//   limitations under the License.
14
15package de.ugoe.cs.autoquest.tasktrees.temporalrelation;
16
17import java.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                        appData.detectedAndReplacedTasks = false;
232                        appData.getStopWatch().start("whole loop");
233                        detectAndReplaceIterations(appData);
234                        appData.getStopWatch().start("task replacement");
235                        appData.updateSubstitutionMatrix();
236                        detectAndReplaceTasks(appData); //
237                        appData.getStopWatch().stop("task replacement");
238                        appData.getStopWatch().stop("whole loop");
239                        appData.getStopWatch().dumpStatistics(System.out);
240                        appData.getStopWatch().reset();
241
242                } while (appData.detectedAndReplacedTasks());
243
244                Console.println("created "
245                                + appData.getResult().getNewlyCreatedTasks().size()
246                                + " new tasks and "
247                                + appData.getResult().getNewlyCreatedTaskInstances().size()
248                                + " appropriate instances\n");
249
250                if ((appData.getResult().getNewlyCreatedTasks().size() > 0)
251                                || (appData.getResult().getNewlyCreatedTaskInstances().size() > 0)) {
252                        appData.getResult().setRuleApplicationStatus(
253                                        RuleApplicationStatus.FINISHED);
254                }
255
256                return appData.getResult();
257        }
258
259
260        private ArrayList<NumberSequence> createNumberSequences(
261                        RuleApplicationData appData) {
262                ArrayList<NumberSequence> result = new ArrayList<NumberSequence>();
263                for (int i = 0; i < appData.getSessions().size(); i++) {
264                        IUserSession session = appData.getSessions().get(i);
265                        NumberSequence templist = new NumberSequence(session.size());
266                        for (int j = 0; j < session.size(); j++) {
267                                ITaskInstance taskInstance = session.get(j);
268                                templist.getSequence()[j] = taskInstance.getTask().getId();
269                        }
270                        // Each NumberSequence is identified by its id, beginning to count
271                        // at zero
272                        templist.setId(i);
273                        result.add(templist);
274                }
275                return result;
276        }
277
278        /**
279         * <p>
280         * harmonizes the event task instances by unifying tasks. This is done, as
281         * initially the event tasks being equal with respect to the considered task
282         * equality are distinct objects. The comparison of these distinct objects
283         * is more time consuming than comparing the object references.
284         * </p>
285         *
286         * @param appData
287         *            the rule application data combining all data used for applying
288         *            this rule
289         * @return Returns the unique tasks symbol map
290         */
291        private void harmonizeEventTaskInstancesModel(RuleApplicationData appData) {
292                Console.traceln(Level.INFO,
293                                "harmonizing task model of event task instances");
294                appData.getStopWatch().start("harmonizing event tasks");
295                SymbolMap<ITaskInstance, ITask> uniqueTasks = preparationTaskHandlingStrategy
296                                .createSymbolMap();
297
298                TaskInstanceComparator comparator = preparationTaskHandlingStrategy
299                                .getTaskComparator();
300
301                int unifiedTasks = 0;
302                ITask task;
303                List<IUserSession> sessions = appData.getSessions();
304                for (int j = 0; j < sessions.size(); j++) {
305                        IUserSession session = sessions.get(j);
306
307                        for (int i = 0; i < session.size(); i++) {
308                                ITaskInstance taskInstance = session.get(i);
309                                task = uniqueTasks.getValue(taskInstance);
310
311                                if (task == null) {
312                                        uniqueTasks.addSymbol(taskInstance, taskInstance.getTask());
313                                        appData.getUniqueTasks().add(taskInstance.getTask());
314                                        appData.getNumber2Task().put(
315                                                        taskInstance.getTask().getId(),
316                                                        taskInstance.getTask());
317                                } else {
318                                        taskBuilder.setTask(taskInstance, task);
319                                        unifiedTasks++;
320                                }
321                        }
322                        comparator.clearBuffers();
323                }
324
325                appData.getStopWatch().stop("harmonizing event tasks");
326                Console.traceln(Level.INFO, "harmonized " + unifiedTasks
327                                + " task occurrences (still " + appData.getUniqueTasks().size()
328                                + " different tasks)");
329
330                appData.getStopWatch().dumpStatistics(System.out);
331                appData.getStopWatch().reset();
332        }
333
334        /**
335         * <p>
336         * searches for direct iterations of single tasks in all sequences and
337         * replaces them with {@link IIteration}s, respectively appropriate
338         * instances. Also all single occurrences of a task that is iterated
339         * somewhen are replaced with iterations to have again an efficient way for
340         * task comparisons.
341         * </p>
342         *
343         * @param appData
344         *            the rule application data combining all data used for applying
345         *            this rule
346         */
347        private void detectAndReplaceIterations(RuleApplicationData appData) {
348                Console.traceln(Level.FINE, "detecting iterations");
349                appData.getStopWatch().start("detecting iterations");
350
351                List<IUserSession> sessions = appData.getSessions();
352
353                Set<ITask> iteratedTasks = searchIteratedTasks(sessions);
354
355                if (iteratedTasks.size() > 0) {
356                        replaceIterationsOf(iteratedTasks, sessions, appData);
357                }
358
359                appData.getStopWatch().stop("detecting iterations");
360                Console.traceln(Level.INFO, "replaced " + iteratedTasks.size()
361                                + " iterated tasks");
362        }
363
364        /**
365         * <p>
366         * searches the provided sessions for task iterations. If a task is
367         * iterated, it is added to the returned set.
368         * </p>
369         *
370         * @param the
371         *            session to search for iterations in
372         *
373         * @return a set of tasks being iterated somewhere
374         */
375        private Set<ITask> searchIteratedTasks(List<IUserSession> sessions) {
376                Set<ITask> iteratedTasks = new HashSet<ITask>();
377                for (IUserSession session : sessions) {
378                        for (int i = 0; i < (session.size() - 1); i++) {
379                                // we prepared the task instances to refer to unique tasks, if
380                                // they are treated
381                                // as equal. Therefore, we just compare the identity of the
382                                // tasks of the task
383                                // instances
384                                if (session.get(i).getTask() == session.get(i + 1).getTask()) {
385                                        iteratedTasks.add(session.get(i).getTask());
386                                }
387                        }
388                }
389                return iteratedTasks;
390        }
391
392        /**
393         * <p>
394         * replaces all occurrences of all tasks provided in the set with iterations
395         * </p>
396         *
397         * @param iteratedTasks
398         *            the tasks to be replaced with iterations
399         * @param sessions
400         *            the sessions in which the tasks are to be replaced
401         * @param appData
402         *            the rule application data combining all data used for applying
403         *            this rule
404         */
405        private void replaceIterationsOf(Set<ITask> iteratedTasks,
406                        List<IUserSession> sessions, RuleApplicationData appData) {
407                Map<ITask, IIteration> iterations = new HashMap<ITask, IIteration>();
408                Map<IIteration, List<IIterationInstance>> iterationInstances = new HashMap<IIteration, List<IIterationInstance>>();
409
410                for (ITask iteratedTask : iteratedTasks) {
411
412                        IIteration iteration = taskFactory.createNewIteration();
413                        appData.newTaskCreated(iteration);
414                        iterations.put(iteratedTask, iteration);
415                        iterationInstances.put(iteration,
416                                        new LinkedList<IIterationInstance>());
417                }
418
419                IIterationInstance iterationInstance;
420
421                for (IUserSession session : sessions) {
422                        int index = 0;
423                        iterationInstance = null;
424
425                        while (index < session.size()) {
426                                // we prepared the task instances to refer to unique tasks, if
427                                // they are treated
428                                // as equal. Therefore, we just compare the identity of the
429                                // tasks of the task
430                                // instances
431                                ITask currentTask = session.get(index).getTask();
432                                IIteration iteration = iterations.get(currentTask);
433                                if (iteration != null) {
434                                        if ((iterationInstance == null)
435                                                        || (iterationInstance.getTask() != iteration)) {
436                                                iterationInstance = taskFactory
437                                                                .createNewTaskInstance(iteration);
438                                                iterationInstances.get(iteration)
439                                                                .add(iterationInstance);// TODO:: Don't create
440                                                                                                                // TaskInstances here,
441                                                                                                                // use a set of tasks
442                                                                                                                // instead
443                                                taskBuilder.addTaskInstance(session, index,
444                                                                iterationInstance);
445                                                index++;
446                                        }
447
448                                        taskBuilder.addChild(iterationInstance, session.get(index));
449                                        taskBuilder.removeTaskInstance(session, index);
450                                } else {
451                                        if (iterationInstance != null) {
452                                                iterationInstance = null;
453                                        }
454                                        index++;
455                                }
456                        }
457                }
458
459                for (Map.Entry<IIteration, List<IIterationInstance>> entry : iterationInstances
460                                .entrySet()) {
461                        harmonizeIterationInstancesModel(entry.getKey(), entry.getValue());
462                }
463        }
464
465        /**
466         * <p>
467         * TODO clarify why this is done
468         * </p>
469         */
470        private void harmonizeIterationInstancesModel(IIteration iteration,
471                        List<IIterationInstance> iterationInstances) {
472                List<ITask> iteratedTaskVariants = new LinkedList<ITask>();
473                TaskInstanceComparator comparator = preparationTaskHandlingStrategy
474                                .getTaskComparator();
475
476                // merge the lexically different variants of iterated task to a unique
477                // list
478                for (IIterationInstance iterationInstance : iterationInstances) {
479                        for (ITaskInstance executionVariant : iterationInstance) {
480                                ITask candidate = executionVariant.getTask();
481
482                                boolean found = false;
483                                for (ITask taskVariant : iteratedTaskVariants) {
484                                        if (comparator.areLexicallyEqual(taskVariant, candidate)) {
485                                                taskBuilder.setTask(executionVariant, taskVariant);
486                                                found = true;
487                                                break;
488                                        }
489                                }
490
491                                if (!found) {
492                                        iteratedTaskVariants.add(candidate);
493                                }
494                        }
495                }
496
497                // if there are more than one lexically different variant of iterated
498                // tasks, adapt the
499                // iteration model to be a selection of different variants. In this case
500                // also adapt
501                // the generated iteration instances to correctly contain selection
502                // instances. If there
503                // is only one variant of an iterated task, simply set this as the
504                // marked task of the
505                // iteration. In this case, the instances can be preserved as is
506                if (iteratedTaskVariants.size() > 1) {
507                        ISelection selection = taskFactory.createNewSelection();
508
509                        for (ITask variant : iteratedTaskVariants) {
510                                taskBuilder.addChild(selection, variant);
511                        }
512
513                        taskBuilder.setMarkedTask(iteration, selection);
514
515                        for (IIterationInstance instance : iterationInstances) {
516                                for (int i = 0; i < instance.size(); i++) {
517                                        ISelectionInstance selectionInstance = taskFactory
518                                                        .createNewTaskInstance(selection);
519                                        taskBuilder.setChild(selectionInstance, instance.get(i));
520                                        taskBuilder.setTaskInstance(instance, i, selectionInstance);
521                                }
522                        }
523                } else {
524                        taskBuilder.setMarkedTask(iteration, iteratedTaskVariants.get(0));
525                }
526        }
527
528        /**
529         * @param appData
530         * @param m
531         * @return
532         */
533        public ISequence matchAsSequence(RuleApplicationData appData, Match m) {       
534                ISequence sequence = taskFactory.createNewSequence();
535                appData.newTaskCreated(sequence);
536
537                int[] first = m.getFirstSequence().getSequence();
538                int[] second = m.getSecondSequence().getSequence();
539
540                // Both sequences of a match are equally long
541                for (int i = 0; i < m.getFirstSequence().size(); i++) {
542
543                        // Two gaps aligned to each other: Have not seen it happening so
544                        // far, just to handle it
545                        if (first[i] == -1 && second[i] == -1) {
546                                // Do nothing here.
547                        }
548                        // Both events are equal, we can simply add the task referring to
549                        // the number
550                        else if (first[i] == second[i]) {
551                                taskBuilder.addChild(sequence,
552                                                appData.getNumber2Task().get(first[i]));
553                        }
554                        // We have a gap in the first sequence, we need to add the task of
555                        // the second sequence as optional
556                        else if (first[i] == -1 && second[i] != -1) {
557                                IOptional optional = taskFactory.createNewOptional();
558                                appData.newTaskCreated(optional);
559                                taskBuilder.setMarkedTask(optional, appData.getNumber2Task()
560                                                .get(second[i]));
561                                taskBuilder.addChild(sequence, optional);
562                        }
563                        // We have a gap in the second sequence, we need to add the task of
564                        // the first sequence as optional
565                        else if (first[i] != -1 && second[i] == -1) {
566                                IOptional optional = taskFactory.createNewOptional();
567                                appData.newTaskCreated(optional);
568                                taskBuilder.setMarkedTask(optional, appData.getNumber2Task()
569                                                .get(first[i]));
570                                taskBuilder.addChild(sequence, optional);
571                        }
572                        // Both tasks are not equal, we need to insert a selection here.
573                        // Check if the next position is not a selection
574                        else if (i < first.length - 1) {
575
576                                if ((first[i] != second[i])
577                                                && ((first[i + 1] == second[i + 1]
578                                                                || first[i + 1] == -1 || second[i + 1] == -1))) {
579
580                                        ISelection selection = taskFactory.createNewSelection();
581                                        appData.newTaskCreated(selection);
582                                        taskBuilder.addChild(selection, appData.getNumber2Task()
583                                                        .get(first[i]));
584                                        taskBuilder.addChild(selection, appData.getNumber2Task()
585                                                        .get(second[i]));
586                                        taskBuilder.addChild(sequence, selection);
587                                } else {
588                                        boolean selectionfound = true;
589                                        ISelection selection = taskFactory.createNewSelection();
590                                        appData.newTaskCreated(selection);
591
592                                        ISequence subsequence1 = taskFactory.createNewSequence();
593                                        appData.newTaskCreated(subsequence1);
594
595                                        ISequence subsequence2 = taskFactory.createNewSequence();
596                                        appData.newTaskCreated(subsequence2);
597
598                                        taskBuilder.addChild(selection, subsequence1);
599                                        taskBuilder.addChild(selection, subsequence2);
600                                        taskBuilder.addChild(sequence,selection);
601                                        while (i < first.length - 1 && selectionfound) {
602                                                selectionfound = false;
603                                                taskBuilder.addChild(subsequence1, appData
604                                                                .getNumber2Task().get(first[i]));
605                                                taskBuilder.addChild(subsequence2, appData
606                                                                .getNumber2Task().get(second[i]));
607                                                if (first[i + 1] != second[i + 1] && first[i + 1] != -1
608                                                                && second[i + 1] != -1) {
609                                                        selectionfound = true;
610                                                }
611                                                else{
612                                                        continue;
613                                                }
614                                                i++;
615                                        }
616                                        if(i==first.length-1 && selectionfound) {
617                                                taskBuilder.addChild(subsequence1, appData
618                                                                .getNumber2Task().get(first[i]));
619                                                taskBuilder.addChild(subsequence2, appData
620                                                                .getNumber2Task().get(second[i]));
621                                        }
622                                }
623                        }
624                        else {
625                                if ((first[i] != second[i])) {
626
627                                        ISelection selection = taskFactory.createNewSelection();
628                                        appData.newTaskCreated(selection);
629                                        taskBuilder.addChild(selection, appData.getNumber2Task()
630                                                        .get(first[i]));
631                                        taskBuilder.addChild(selection, appData.getNumber2Task()
632                                                        .get(second[i]));
633                                        taskBuilder.addChild(sequence, selection);
634                                }
635                        }
636
637                }
638                return sequence;
639        }
640
641        /**
642         *
643         * @param appData
644         *            the rule application data combining all data used for applying
645         *            this rule
646         */
647        private void detectAndReplaceTasks(RuleApplicationData appData) {
648                Console.traceln(Level.FINE, "detecting and replacing tasks");
649                appData.getStopWatch().start("detecting tasks");
650
651                // Create NumberSequences
652                appData.setNumberSequences(this.createNumberSequences(appData));
653               
654                // Generate pairwise alignments
655                //appData.setMatchseqs(generatePairwiseAlignments(appData));
656                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                                        // Check if nothing has been replaced in the sequence we
691                                        // want to replace
692                                        if (replacedOccurences.get(oc.getSequenceId()) == null) {
693                                                replacedOccurences.put(oc.getSequenceId(),
694                                                                new LinkedList<MatchOccurence>());
695                                        } else {
696                                                // check if we have any replaced occurence with indexes
697                                                // smaller than ours. If so, we need to adjust our start
698                                                // and endpoints
699                                                // of the replacement.
700                                                // Also do a check if we have replaced this specific
701                                                // MatchOccurence in this sequence already. Jump to the
702                                                // next occurence if this is the case.
703                                                // This is no more neccessary once the matches are
704                                                // harmonized.
705                                                for (Iterator<MatchOccurence> jt = replacedOccurences
706                                                                .get(oc.getSequenceId()).iterator(); jt
707                                                                .hasNext();) {
708                                                        MatchOccurence tmpOC = jt.next();
709
710                                                        if (oc.getStartindex() >= tmpOC.getStartindex()
711                                                                        && oc.getStartindex() <= tmpOC
712                                                                                        .getEndindex()) {
713                                                                continue invalidOccurence;
714                                                        }
715                                                        if (oc.getEndindex() >= tmpOC.getStartindex()) {
716                                                                continue invalidOccurence;
717
718                                                        } else if (oc.getStartindex() > tmpOC.getEndindex()) {
719                                                                int diff = tmpOC.getEndindex()
720                                                                                - tmpOC.getStartindex();
721                                                                // Just to be sure.
722                                                                if (diff > 0) {
723                                                                        oc.setStartindex(oc.getStartindex() - diff
724                                                                                        + 1);
725                                                                        oc.setEndindex(oc.getEndindex() - diff + 1);
726                                                                } else {
727                                                                        Console.traceln(Level.WARNING,
728                                                                                        "End index of a Match before start. This should never happen");
729                                                                }
730                                                        }
731                                                }
732                                        }
733                                        System.out.println("Replacing in sequence" + oc.getSequenceId());
734                                        ISequenceInstance sequenceInstances = RuleUtils
735                                                        .createNewSubSequenceInRange(appData.getSessions()
736                                                                        .get(oc.getSequenceId()), oc
737                                                                        .getStartindex(), oc.getEndindex(), task,
738                                                                        taskFactory, taskBuilder);
739                                        // Adjust the length of the match regarding to the length of
740                                        // instance. (OptionalInstances may be shorter)
741                                        oc.setEndindex(oc.getStartindex()
742                                                        + sequenceInstances.size()
743                                                        - RuleUtils.missedOptionals);
744                                        replacedOccurences.get(oc.getSequenceId()).add(oc);
745                                }
746                        }
747                }
748                //appData.setMatchseqs(null);
749                appData.getStopWatch().stop("replacing tasks");
750        }
751       
752       
753       
754
755        private void searchMatchesInAllSessions(RuleApplicationData appData) {
756                Console.traceln(Level.INFO, "searching for patterns occuring most with " + nThreads + " threads");
757                //Prepare parallel search of matchseqs
758                ExecutorService executor = Executors.newFixedThreadPool(nThreads);
759                int matchSeqSize=appData.getMatchseqs().size();
760                int interval = Math.round(matchSeqSize/nThreads);
761                int rest = matchSeqSize % nThreads;
762               
763                for(int i =0;i<matchSeqSize-interval;i+=interval) {
764                        int offset =0;
765                        if(rest!=0) {
766                                offset=1;
767                                rest--;
768                        }
769                        int from = i;
770                        int to = i+interval+offset;
771                        System.out.println("Creating thread with matches from " + from + " to " + to);
772                        // search each match in every other sequence
773                        ParallelMatchOcurrencesFinder finder = new ParallelMatchOcurrencesFinder(appData,from,to);
774                        executor.execute(finder);
775                }
776                executor.shutdown();
777                try {
778                        executor.awaitTermination(2, TimeUnit.HOURS);
779                } catch (InterruptedException e) {
780                        // TODO Auto-generated catch block
781                        e.printStackTrace();
782                }
783               
784        }
785
786        //Print out the progress
787         private static void printProgressPercentage(int count, int size) {
788                if(size>100) {
789                        if((count%(size/100)==0)) {     
790                                //Console.traceln(Level.INFO,("Thread" + Thread.currentThread().getName() + ": " + Math.round((float) count/size*100))+ "%");
791                                System.out.println("Thread" + Thread.currentThread().getName() + ": " + Math.round((float) count/size*100)+ "%");
792                        }
793                }
794                else {
795                        //Console.traceln(Level.INFO,("Thread" + Thread.currentThread().getName() + ": " +Math.round((float) count/size*100))+ "%");
796                        System.out.println("Thread" + Thread.currentThread().getName() + ": " +Math.round((float) count/size*100)+ "%");
797                       
798                }
799        }
800       
801         
802         
803       
804        private class ParallelMatchOcurrencesFinder implements Runnable {
805        private final RuleApplicationData appData;
806        private final int from;
807        private final int to;
808            ParallelMatchOcurrencesFinder(RuleApplicationData appData, int from, int to) {
809            this.appData = appData;
810            this.from = from;
811            this.to = to;
812        }
813       
814        @Override
815        public void run() {
816                int count = 0;
817                int size=to-from;
818               
819                for (int i=from; i<to;i++) {
820                        Match pattern = appData.getMatchseqs().get(i);
821                        count++;
822                        printProgressPercentage(count,size);
823                        // Skip sequences with more 0 events (scrolls) than other events.
824                        // Both of the pattern sequences are equally long, so the zero
825                        // counts just need to be smaller than the length of one sequence
826                        if (pattern.getFirstSequence().eventCount(0)
827                                        + pattern.getSecondSequence().eventCount(0) + 1 > pattern
828                                        .getFirstSequence().size())
829                                continue;
830
831                        for (int j = 0; j < appData.getNumberSequences().size(); j++) {
832                                LinkedList<Integer> startpositions = appData
833                                                .getNumberSequences().get(j).containsPattern(pattern);
834                                if (startpositions.size() > 0) {
835                                        for (Iterator<Integer> jt = startpositions.iterator(); jt
836                                                        .hasNext();) {
837                                                int start = jt.next();
838                                                pattern.addOccurence(new MatchOccurence(start, start
839                                                                + pattern.size(), j));
840                                        }
841                                }
842                        }
843                } 
844        }
845        }
846       
847       
848        private class ParallelPairwiseAligner implements Runnable {
849        private final RuleApplicationData appData;
850        private final int from;
851        private final int to;
852            ParallelPairwiseAligner(RuleApplicationData appData, int from, int to) {
853            this.appData = appData;
854            this.from = from;
855            this.to = to;
856        }
857       
858        @Override
859        public void run() {
860                int count = 0;
861                int size=to-from;
862               
863                for (int i=from; i<to;i++) {
864                        NumberSequence ns1 = appData.getNumberSequences().get(i);
865                                count++;
866                                printProgressPercentage(count,size);
867                                for (int j = 0; j < appData.getNumberSequences().size(); j++) {
868                                        NumberSequence ns2 = appData.getNumberSequences().get(j);
869                                        if (i != j) {
870                                                AlignmentAlgorithm aa = AlignmentAlgorithmFactory.create();
871                                                aa.align(ns1, ns2, appData.getSubmat(),9);
872                                                synchronized(appData.getMatchseqs()) {
873                                                        appData.getMatchseqs().addAll(aa.getMatches());
874                                                }
875                                        }
876                                }
877                } 
878        }
879        }
880
881        //private LinkedList<Match> generatePairwiseAlignments(RuleApplicationData appData) {
882        private void generatePairwiseAlignments(RuleApplicationData appData) {
883                int numberSeqSize = appData.getNumberSequences().size();
884                appData.matchseqs = new LinkedList<Match>();
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 with " + nThreads + " threads");
889                        ExecutorService executor = Executors.newFixedThreadPool(nThreads);
890                        int interval = Math.round(numberSeqSize/nThreads);
891                        int rest = numberSeqSize % nThreads;
892                       
893                        for (int i = 0; i < numberSeqSize-interval; i+=interval) {
894                                int offset = 0;
895                                if(rest!=0) {
896                                        offset=1;
897                                        rest--;
898                                }
899                                int from = i;
900                                int to = i+interval+offset;
901                                System.out.println("Creating thread for sessions " + from + " till " + to);
902                                ParallelPairwiseAligner aligner = new ParallelPairwiseAligner(appData,from,to);
903                                executor.execute(aligner);
904                        }
905                        executor.shutdown();
906                        try {
907                                executor.awaitTermination(10, TimeUnit.MINUTES);
908                        } catch (InterruptedException e) {
909                                // TODO Auto-generated catch block
910                                e.printStackTrace();
911                        }
912       
913                        //GlobalDataContainer.getInstance().addData("aligned" + iteration, appData);
914                        //saveAppData("aligned" + iteration);
915                //      return result;
916                }
917                //else {
918                //      Console.traceln(Level.INFO,"loading matches from file");
919                //      appData = loadAppData("aligned"+iteration);
920                //      return appData.getMatchseqs();
921                //}
922       
923
924        /**
925     *
926     */
927        private static class RuleApplicationData implements Serializable {
928
929                /**
930                 *
931                 */
932                private static final long serialVersionUID = -7559657686755522960L;
933
934                private HashMap<Integer, ITask> number2task;
935
936                // TODO: We Actually just need number2task here, this structure can be removed in the future.
937                private HashSet<ITask> uniqueTasks;
938               
939                ObjectDistanceSubstitionMatrix submat;
940               
941                LinkedList<Match> matchseqs;
942               
943                private ArrayList<NumberSequence> numberseqs;
944
945                private LinkedList<ITask> newTasks;
946               
947                /**
948         *
949         */
950                private List<IUserSession> sessions;
951
952                /**
953         *
954         */
955                private boolean detectedAndReplacedTasks;
956
957                /**
958         *
959         */
960                private RuleApplicationResult result;
961
962                /**
963         *
964         */
965                private StopWatch stopWatch;
966
967                /**
968         *
969         */
970                private RuleApplicationData(List<IUserSession> sessions) {
971                        this.sessions = sessions;
972                        numberseqs = new ArrayList<NumberSequence>();
973                        uniqueTasks = new HashSet<ITask>();
974                        number2task = new HashMap<Integer, ITask>();
975                        stopWatch = new StopWatch();
976                        result = new RuleApplicationResult();
977                        submat= new ObjectDistanceSubstitionMatrix(6,-3,false);
978                        newTasks = new LinkedList<ITask>();
979                        this.detectedAndReplacedTasks = true;
980                }
981
982                public LinkedList<Match> getMatchseqs() {
983                        return matchseqs;
984                }
985
986
987                private ObjectDistanceSubstitionMatrix getSubmat() {
988                        return submat;
989                }
990               
991                private void resetNewlyCreatedTasks() {
992                        uniqueTasks.addAll(newTasks);
993                        newTasks.clear();
994                }
995               
996                private void newTaskCreated(ITask task) {
997                        number2task.put(task.getId(), task);
998                        newTasks.add(task);
999                }
1000
1001                /**
1002                 * @return the UserSessions as List.
1003                 */
1004                private List<IUserSession> getSessions() {
1005                        return sessions;
1006                }
1007
1008                private HashSet<ITask> getUniqueTasks() {
1009                        return uniqueTasks;
1010                }
1011
1012                private void setNumberSequences(ArrayList<NumberSequence> numberseqs) {
1013                        this.numberseqs = numberseqs;
1014                }
1015
1016                private ArrayList<NumberSequence> getNumberSequences() {
1017                        return numberseqs;
1018                }
1019
1020                private void updateSubstitutionMatrix() {
1021                        submat.update(getNewTasks());
1022                        resetNewlyCreatedTasks();
1023                }
1024
1025               
1026               
1027                /**
1028         *
1029         */
1030                private boolean detectedAndReplacedTasks() {
1031                        return detectedAndReplacedTasks;
1032                }
1033
1034                /**
1035                 * @return the result
1036                 */
1037                private RuleApplicationResult getResult() {
1038                        return result;
1039                }
1040
1041                public LinkedList<ITask> getNewTasks() {
1042                        return newTasks;
1043                }
1044               
1045                /**
1046                 * @return the stopWatch
1047                 */
1048                private StopWatch getStopWatch() {
1049                        return stopWatch;
1050                }
1051
1052                private HashMap<Integer, ITask> getNumber2Task() {
1053                        return number2task;
1054                }
1055
1056        }
1057
1058}
Note: See TracBrowser for help on using the repository browser.