Context Navigation

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

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

Note: See TracBrowser for help on using the repository browser.

Download in other formats: