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

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

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