Context Navigation

SequenceForTaskDetectionRule.java @ 1735

Last change on this file since 1735 was 1734, checked in by rkrimmel, 10 years ago
Added automatically created javadoc, still needs to be commented properly though
File size: 35.4 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.util.HashMap;
18	import java.util.HashSet;
19	import java.util.Iterator;
20	import java.util.LinkedList;
21	import java.util.List;
22	import java.util.Map;
23	import java.util.Set;
24	import java.util.logging.Level;
25
26	import de.ugoe.cs.autoquest.tasktrees.taskequality.TaskEquality;
27	import de.ugoe.cs.autoquest.tasktrees.treeifc.IIteration;
28	import de.ugoe.cs.autoquest.tasktrees.treeifc.IIterationInstance;
29	import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelection;
30	import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelectionInstance;
31	import de.ugoe.cs.autoquest.tasktrees.treeifc.ISequence;
32	import de.ugoe.cs.autoquest.tasktrees.treeifc.ISequenceInstance;
33	import de.ugoe.cs.autoquest.tasktrees.treeifc.ITask;
34	import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskBuilder;
35	import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskFactory;
36	import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskInstance;
37	import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskInstanceList;
38	import de.ugoe.cs.autoquest.tasktrees.treeifc.IUserSession;
39	import de.ugoe.cs.autoquest.usageprofiles.SymbolMap;
40	import de.ugoe.cs.autoquest.usageprofiles.Trie;
41	import de.ugoe.cs.autoquest.usageprofiles.TrieProcessor;
42	import de.ugoe.cs.util.StopWatch;
43	import de.ugoe.cs.util.console.Console;
44
45	// TODO: Auto-generated Javadoc
46	/**
47	* <p>
48	* This class implements the major rule for creating task trees based on a set
49	* of recorded user sessions. For this, it first harmonizes all tasks. This
50	* eases later comparison. Then it searches the sessions for iterations and
51	* replaces them accordingly. Then it searches for sub sequences being the
52	* longest and occurring most often. For each found sub sequence, it replaces
53	* the occurrences by creating appropriate {@link ISequence}s. Afterwards, again
54	* searches for iterations and then again for sub sequences until no more
55	* replacements are done.
56	* </p>
57	* <p>
58	* For determining the longest sequence occurring most often, the implementation
59	* uses a {@link Trie}. The depth of the tree is initially 3. If the algorithm
60	* has a longest sequence occurring most often whose length is equal to the
61	* depth of the trie, it recalculates the trie with an increased depth.
62	* </p>
63	*
64	* @author Patrick Harms
65	*/
66	class SequenceForTaskDetectionRule implements ISessionScopeRule {
67
68	/**
69	* The Class MaxCountAndLongestTasksFinder.
70	*
71	* @author Patrick Harms
72	*/
73	private class MaxCountAndLongestTasksFinder implements
74	TrieProcessor<ITaskInstance> {
75
76	/** The current count. */
77	private int currentCount;
78
79	/** The found tasks. */
80	private final List<List<ITaskInstance>> foundTasks = new LinkedList<List<ITaskInstance>>();
81
82	/**
83	* Instantiates a new max count and longest tasks finder.
84	*/
85	public MaxCountAndLongestTasksFinder() {
86	super();
87	this.currentCount = 0;
88	}
89
90	/**
91	* Gets the found tasks.
92	*
93	* @return the found tasks
94	*/
95	public Tasks getFoundTasks() {
96	removePermutationsOfShorterTasks();
97	return new Tasks(currentCount, foundTasks);
98	}
99
100	/*
101	* (non-Javadoc)
102	*
103	* @see
104	* de.ugoe.cs.autoquest.usageprofiles.TrieProcessor#process(java.util
105	* .List, int)
106	*/
107	@Override
108	public TrieProcessor.Result process(List<ITaskInstance> foundTask,
109	int count) {
110	if (foundTask.size() < 2) {
111	// ignore single tasks
112	return TrieProcessor.Result.CONTINUE;
113	}
114
115	if (count < 2) {
116	// ignore singular occurrences
117	return TrieProcessor.Result.SKIP_NODE;
118	}
119
120	if (this.currentCount > count) {
121	// ignore this children of this task, as they may have only
122	// smaller counts than
123	// the already found tasks
124	return TrieProcessor.Result.SKIP_NODE;
125	}
126
127	if (this.currentCount < count) {
128	// the provided task occurs more often that all tasks found so
129	// far.
130	// clear all found tasks and use the new count as the one
131	// searched for
132	foundTasks.clear();
133	this.currentCount = count;
134	}
135
136	if (this.currentCount == count) {
137	// the task is of interest. Sort it into the other found tasks
138	// so that
139	// the longest come first
140	boolean added = false;
141	for (int i = 0; i < foundTasks.size(); i++) {
142	if (foundTasks.get(i).size() < foundTask.size()) {
143	// defensive copy
144	foundTasks.add(i, new LinkedList<ITaskInstance>(
145	foundTask)); // defensive copy
146	added = true;
147	break;
148	}
149	}
150
151	if (!added) {
152	foundTasks.add(new LinkedList<ITaskInstance>(foundTask)); // defensive
153	// copy
154	}
155	}
156
157	return TrieProcessor.Result.CONTINUE;
158	}
159
160	/**
161	* Removes the permutations of shorter tasks.
162	*/
163	private void removePermutationsOfShorterTasks() {
164	// now iterate the sorted list and for each task remove all other
165	// tasks that are shorter
166	// (i.e. come later in the sorted list) and that represent a subpart
167	// of the task
168	for (int i = 0; i < foundTasks.size(); i++) {
169	for (int j = i + 1; j < foundTasks.size();) {
170	if (foundTasks.get(j).size() < foundTasks.get(i).size()) {
171	// found a task that is a potential subtask. Check for
172	// this and remove the
173	// subtask if needed
174	final List<ITaskInstance> longTask = foundTasks.get(i);
175	final List<ITaskInstance> shortTask = foundTasks.get(j);
176
177	if (getSubListIndex(longTask, shortTask, 0) > -1) {
178	foundTasks.remove(j);
179	} else {
180	j++;
181	}
182	} else {
183	j++;
184	}
185	}
186	}
187	}
188
189	}
190
191	/**
192	* The Class RuleApplicationData.
193	*/
194	private static class RuleApplicationData {
195
196	/** The sessions. */
197	private final List<IUserSession> sessions;
198
199	/** The last trie. */
200	private TaskInstanceTrie lastTrie;
201
202	/** default and minimum trained sequence length is 3. */
203	private int trainedSequenceLength = 3;
204
205	/** The last found tasks. */
206	private Tasks lastFoundTasks = new Tasks(Integer.MAX_VALUE, null);
207
208	/** The detected and replaced tasks. */
209	private boolean detectedAndReplacedTasks;
210
211	/** The result. */
212	private final RuleApplicationResult result = new RuleApplicationResult();
213
214	/** The stop watch. */
215	private final StopWatch stopWatch = new StopWatch();
216
217	/**
218	* Instantiates a new rule application data.
219	*
220	* @param sessions the sessions
221	*/
222	private RuleApplicationData(List<IUserSession> sessions) {
223	this.sessions = sessions;
224	}
225
226	/**
227	* Detected and replaced tasks.
228	*
229	* @return true, if successful
230	*/
231	private boolean detectedAndReplacedTasks() {
232	return detectedAndReplacedTasks;
233	}
234
235	/**
236	* Detected and replaced tasks.
237	*
238	* @param detectedAndReplacedTasks the detected and replaced tasks
239	*/
240	private void detectedAndReplacedTasks(boolean detectedAndReplacedTasks) {
241	this.detectedAndReplacedTasks = detectedAndReplacedTasks;
242	}
243
244	/**
245	* Gets the last found tasks.
246	*
247	* @return the lastFoundSequences
248	*/
249	private Tasks getLastFoundTasks() {
250	return lastFoundTasks;
251	}
252
253	/**
254	* Gets the last trie.
255	*
256	* @return the lastTrie
257	*/
258	private TaskInstanceTrie getLastTrie() {
259	return lastTrie;
260	}
261
262	/**
263	* Gets the result.
264	*
265	* @return the result
266	*/
267	private RuleApplicationResult getResult() {
268	return result;
269	}
270
271	/**
272	* Gets the sessions.
273	*
274	* @return the tree
275	*/
276	private List<IUserSession> getSessions() {
277	return sessions;
278	}
279
280	/**
281	* Gets the stop watch.
282	*
283	* @return the stopWatch
284	*/
285	private StopWatch getStopWatch() {
286	return stopWatch;
287	}
288
289	/**
290	* Gets the trained sequence length.
291	*
292	* @return the trainedSequenceLength
293	*/
294	private int getTrainedSequenceLength() {
295	return trainedSequenceLength;
296	}
297
298	/**
299	* Sets the last found tasks.
300	*
301	* @param lastFoundSequences the lastFoundSequences to set
302	*/
303	private void setLastFoundTasks(Tasks lastFoundSequences) {
304	this.lastFoundTasks = lastFoundSequences;
305	}
306
307	/**
308	* Sets the last trie.
309	*
310	* @param lastTrie the lastTrie to set
311	*/
312	private void setLastTrie(TaskInstanceTrie lastTrie) {
313	this.lastTrie = lastTrie;
314	}
315
316	/**
317	* Sets the trained sequence length.
318	*
319	* @param trainedSequenceLength the trainedSequenceLength to set
320	*/
321	private void setTrainedSequenceLength(int trainedSequenceLength) {
322	this.trainedSequenceLength = trainedSequenceLength;
323	}
324
325	}
326
327	/**
328	* The Class Tasks.
329	*
330	* @author Patrick Harms
331	*/
332	private static class Tasks implements Iterable<List<ITaskInstance>> {
333
334	/** The occurrence count. */
335	private final int occurrenceCount;
336
337	/** The sequences. */
338	private final List<List<ITaskInstance>> sequences;
339
340	/**
341	* Instantiates a new tasks.
342	*
343	* @param occurrenceCount the occurrence count
344	* @param sequences the sequences
345	*/
346	private Tasks(int occurrenceCount, List<List<ITaskInstance>> sequences) {
347	super();
348	this.occurrenceCount = occurrenceCount;
349	this.sequences = sequences;
350	}
351
352	/**
353	* Gets the occurrence count.
354	*
355	* @return the occurrence count
356	*/
357	private int getOccurrenceCount() {
358	return occurrenceCount;
359	}
360
361	/**
362	*
363	*/
364
365	/*
366	* (non-Javadoc)
367	*
368	* @see java.lang.Iterable#iterator()
369	*/
370	@Override
371	public Iterator<List<ITaskInstance>> iterator() {
372	return this.sequences.iterator();
373	}
374
375	/**
376	* Size.
377	*
378	* @return the int
379	*/
380	private int size() {
381	return this.sequences.size();
382	}
383
384	/*
385	* (non-Javadoc)
386	*
387	* @see java.lang.Object#toString()
388	*/
389	@Override
390	public String toString() {
391	final StringBuffer result = new StringBuffer();
392	result.append(this.occurrenceCount);
393	result.append(" occurrences:\n");
394
395	for (final List<ITaskInstance> task : sequences) {
396	result.append(task);
397	result.append("\n");
398	}
399
400	return result.toString();
401	}
402
403	}
404
405	/** <p> the task factory to be used for creating substructures for the temporal relationships identified during rul application </p>. */
406	private final ITaskFactory taskFactory;;
407
408	/** <p> the task builder to be used for creating substructures for the temporal relationships identified during rule application </p>. */
409	private final ITaskBuilder taskBuilder;
410
411	/**
412	* <p>
413	* the task handling strategy to be used for comparing tasks for
414	* preparation, i.e., before the tasks are harmonized
415	* </p>
416	*/
417	private final TaskHandlingStrategy preparationTaskHandlingStrategy;
418
419	/**
420	* <p>
421	* the task handling strategy to be used for comparing tasks during
422	* iteration detection an trie generation, i.e., after the tasks are
423	* harmonized
424	* </p>
425	*/
426	private final TaskHandlingStrategy identityTaskHandlingStrategy;
427
428	/**
429	* <p>
430	* instantiates the rule and initializes it with a task equality to be
431	* considered when comparing tasks as well as a task factory and builder to
432	* be used for creating task structures.
433	* </p>
434	*
435	* @param minimalTaskEquality
436	* the task equality to be considered when comparing tasks
437	* @param taskFactory
438	* the task factory to be used for creating substructures
439	* @param taskBuilder
440	* the task builder to be used for creating substructures
441	*/
442	SequenceForTaskDetectionRule(TaskEquality minimalTaskEquality,
443	ITaskFactory taskFactory, ITaskBuilder taskBuilder) {
444	this.taskFactory = taskFactory;
445	this.taskBuilder = taskBuilder;
446
447	this.preparationTaskHandlingStrategy = new TaskHandlingStrategy(
448	minimalTaskEquality);
449	this.identityTaskHandlingStrategy = new TaskHandlingStrategy(
450	TaskEquality.IDENTICAL);
451	}
452
453	/*
454	* (non-Javadoc)
455	*
456	* @see
457	* de.ugoe.cs.autoquest.tasktrees.temporalrelation.ISessionScopeRule#apply
458	* (java.util.List)
459	*/
460	@Override
461	public RuleApplicationResult apply(List<IUserSession> sessions) {
462	final RuleApplicationData appData = new RuleApplicationData(sessions);
463
464	// this is the real rule application. Loop while something is replaced.
465	harmonizeEventTaskInstancesModel(appData);
466	do {
467	System.out.println();
468
469	appData.getStopWatch().start("whole loop");
470	detectAndReplaceIterations(appData);
471
472	appData.getStopWatch().start("task replacement");
473	detectAndReplaceTasks(appData);
474	appData.getStopWatch().stop("task replacement");
475	appData.getStopWatch().stop("whole loop");
476
477	// ((TaskTreeNodeComparator)
478	// taskComparator).getStopWatch().dumpStatistics(System.out);
479	// ((TaskTreeNodeComparator) taskComparator).getStopWatch().reset();
480
481	appData.getStopWatch().dumpStatistics(System.out);
482	appData.getStopWatch().reset();
483
484	} while (appData.detectedAndReplacedTasks());
485
486	Console.println("created "
487	+ appData.getResult().getNewlyCreatedTasks().size()
488	+ " new tasks and "
489	+ appData.getResult().getNewlyCreatedTaskInstances().size()
490	+ " appropriate instances\n");
491
492	if ((appData.getResult().getNewlyCreatedTasks().size() > 0)
493	\|\| (appData.getResult().getNewlyCreatedTaskInstances().size() > 0)) {
494	appData.getResult().setRuleApplicationStatus(
495	RuleApplicationStatus.FINISHED);
496	}
497
498	return appData.getResult();
499	}
500
501	/**
502	* Creates the new trie.
503	*
504	* @param appData the rule application data combining all data used for applying
505	* this rule
506	*/
507	private void createNewTrie(RuleApplicationData appData) {
508	Console.traceln(
509	Level.FINER,
510	"training trie with a maximum sequence length of "
511	+ appData.getTrainedSequenceLength());
512
513	appData.getStopWatch().start("training trie");
514
515	// we prepared the task instances to refer to unique tasks, if they are
516	// treated
517	// as equal. Therefore, we just compare the identity of the tasks of the
518	// task
519	// instances
520	appData.setLastTrie(new TaskInstanceTrie(identityTaskHandlingStrategy));
521
522	appData.getLastTrie().trainSessions(appData.getSessions(),
523	appData.getTrainedSequenceLength());
524
525	appData.getStopWatch().stop("training trie");
526	}
527
528	/**
529	* <p>
530	* searches for direct iterations of single tasks in all sequences and
531	* replaces them with {@link IIteration}s, respectively appropriate
532	* instances. Also all single occurrences of a task that is iterated
533	* somewhen are replaced with iterations to have again an efficient way for
534	* task comparisons.
535	* </p>
536	*
537	* @param appData
538	* the rule application data combining all data used for applying
539	* this rule
540	*/
541	private void detectAndReplaceIterations(RuleApplicationData appData) {
542	Console.traceln(Level.FINE, "detecting iterations");
543	appData.getStopWatch().start("detecting iterations");
544
545	final List<IUserSession> sessions = appData.getSessions();
546
547	final Set<ITask> iteratedTasks = searchIteratedTasks(sessions);
548
549	if (iteratedTasks.size() > 0) {
550	replaceIterationsOf(iteratedTasks, sessions, appData);
551	}
552
553	appData.getStopWatch().stop("detecting iterations");
554	Console.traceln(Level.INFO, "replaced " + iteratedTasks.size()
555	+ " iterated tasks");
556	}
557
558	/**
559	* TODO go on commenting.
560	*
561	* @param appData the rule application data combining all data used for applying
562	* this rule
563	*/
564	private void detectAndReplaceTasks(RuleApplicationData appData) {
565	Console.traceln(Level.FINE, "detecting and replacing tasks");
566	appData.getStopWatch().start("detecting tasks");
567
568	getSequencesOccuringMostOften(appData);
569
570	appData.getStopWatch().stop("detecting tasks");
571	appData.getStopWatch().start("replacing tasks");
572
573	replaceSequencesOccurringMostOften(appData);
574
575	appData.getStopWatch().stop("replacing tasks");
576	Console.traceln(Level.INFO, "detected and replaced "
577	+ appData.getLastFoundTasks().size() + " tasks occuring "
578	+ appData.getLastFoundTasks().getOccurrenceCount() + " times");
579	}
580
581	/**
582	* Gets the sequences occuring most often.
583	*
584	* @param appData the rule application data combining all data used for applying
585	* this rule
586	* @return the sequences occuring most often
587	*/
588	private void getSequencesOccuringMostOften(RuleApplicationData appData) {
589	Console.traceln(Level.FINE, "determining most prominent tasks");
590
591	Tasks tasks;
592	boolean createNewTrie = (appData.getLastTrie() == null)
593	\|\| appData.detectedAndReplacedTasks(); // tree has changed
594
595	do {
596	if (createNewTrie) {
597	createNewTrie(appData);
598	}
599
600	final MaxCountAndLongestTasksFinder finder = new MaxCountAndLongestTasksFinder();
601	appData.getLastTrie().process(finder);
602
603	tasks = finder.getFoundTasks();
604
605	createNewTrie = false;
606
607	for (final List<ITaskInstance> task : tasks) {
608	if (task.size() >= appData.getTrainedSequenceLength()) {
609	// Trie must be recreated with a longer sequence length to
610	// be sure that
611	// the found sequences occurring most often are found in
612	// their whole length
613	appData.setTrainedSequenceLength(appData
614	.getTrainedSequenceLength() + 1);
615	createNewTrie = true;
616	break;
617	}
618	}
619	} while (createNewTrie);
620
621	// create a normal trie for comparison
622	/*
623	* System.out.println("creating test trie for comparison");
624	*
625	* appData.getStopWatch().start("testtrie"); Trie<ITaskInstance> trie =
626	* new Trie<ITaskInstance>(identityTaskComparator);
627	*
628	* for (IUserSession session : appData.getSessions()) {
629	* trie.train(session.getExecutedTasks(),
630	* appData.getTrainedSequenceLength()); }
631	*
632	* appData.getStopWatch().stop("testtrie");
633	*
634	* MaxCountAndLongestTasksFinder finder = new
635	* MaxCountAndLongestTasksFinder(); trie.process(finder);
636	*
637	* boolean allTasksEqual = finder.getFoundTasks().size() ==
638	* tasks.size();
639	*
640	* allTasksEqual &= finder.getFoundTasks().occurrenceCount ==
641	* tasks.occurrenceCount;
642	*
643	* for (List<ITaskInstance> task1 : finder.getFoundTasks()) { boolean
644	* foundTask = false; for (List<ITaskInstance> task2 : tasks) { boolean
645	* tasksEqual = false; if (task1.size() == task2.size()) { tasksEqual =
646	* true; for (int i = 0; i < task1.size(); i++) { if
647	* (!identityTaskComparator.equals(task1.get(i).getTask(),
648	* task2.get(i).getTask())) { tasksEqual = false; } } }
649	*
650	* if (tasksEqual) { foundTask = true; break; } }
651	*
652	* if (!foundTask) { System.out.println("different is " + task1);
653	* allTasksEqual = false; break; } }
654	*
655	* if (!allTasksEqual) { System.out.println(finder.getFoundTasks());
656	* System.out.println(tasks);
657	*
658	* throw new
659	* IllegalArgumentException("both tries calculated different subsequences"
660	* ); }
661	*
662	* /*TrieStatisticsDumper dumper = new TrieStatisticsDumper();
663	* appData.getLastTrie().process(dumper); dumper.dumpCounters();
664	*/
665
666	appData.setLastFoundTasks(tasks);
667
668	Console.traceln(Level.FINE, "found "
669	+ appData.getLastFoundTasks().size() + " tasks " + "occurring "
670	+ appData.getLastFoundTasks().getOccurrenceCount() + " times");
671	}
672
673	/**
674	* Gets the sub list index.
675	*
676	* @param list the list
677	* @param subList the sub list
678	* @param startIndex the start index
679	* @return the sub list index
680	*/
681	private int getSubListIndex(ITaskInstanceList list,
682	List<ITaskInstance> subList, int startIndex) {
683	boolean matchFound;
684	int result = -1;
685
686	for (int i = startIndex; i <= (list.size() - subList.size()); i++) {
687	matchFound = true;
688
689	for (int j = 0; j < subList.size(); j++) {
690	// we prepared the task instances to refer to unique tasks, if
691	// they are treated
692	// as equal. Therefore, we just compare the identity of the
693	// tasks of the task
694	// instances
695	if (list.get(i + j).getTask() != subList.get(j).getTask()) {
696	matchFound = false;
697	break;
698	}
699	}
700
701	if (matchFound) {
702	result = i;
703	break;
704	}
705	}
706
707	return result;
708	}
709
710	/**
711	* Gets the sub list index.
712	*
713	* @param list the list
714	* @param subList the sub list
715	* @param startIndex the start index
716	* @return the sub list index
717	*/
718	private int getSubListIndex(List<ITaskInstance> list,
719	List<ITaskInstance> subList, int startIndex) {
720	boolean matchFound;
721	int result = -1;
722
723	for (int i = startIndex; i <= (list.size() - subList.size()); i++) {
724	matchFound = true;
725
726	for (int j = 0; j < subList.size(); j++) {
727	// we prepared the task instances to refer to unique tasks, if
728	// they are treated
729	// as equal. Therefore, we just compare the identity of the
730	// tasks of the task
731	// instances
732	if (list.get(i + j) != subList.get(j)) {
733	matchFound = false;
734	break;
735	}
736	}
737
738	if (matchFound) {
739	result = i;
740	break;
741	}
742	}
743
744	return result;
745	}
746
747	/**
748	* <p>
749	* harmonizes the event task instances by unifying tasks. This is done, as
750	* initially the event tasks being equal with respect to the considered task
751	* equality are distinct objects. The comparison of these distinct objects
752	* is more time consuming than comparing the object references.
753	* </p>
754	*
755	* @param appData
756	* the rule application data combining all data used for applying
757	* this rule
758	*/
759	private void harmonizeEventTaskInstancesModel(RuleApplicationData appData) {
760	Console.traceln(Level.INFO,
761	"harmonizing task model of event task instances");
762	appData.getStopWatch().start("harmonizing event tasks");
763
764	final SymbolMap<ITaskInstance, ITask> uniqueTasks = preparationTaskHandlingStrategy
765	.createSymbolMap();
766	final TaskInstanceComparator comparator = preparationTaskHandlingStrategy
767	.getTaskComparator();
768
769	int unifiedTasks = 0;
770	ITask task;
771	final List<IUserSession> sessions = appData.getSessions();
772	int sessionNo = 0;
773	for (final IUserSession session : sessions) {
774	Console.traceln(Level.FINE, "handling " + (++sessionNo) + ". "
775	+ session);
776	for (final ITaskInstance taskInstance : session) {
777	task = uniqueTasks.getValue(taskInstance);
778
779	if (task == null) {
780	uniqueTasks.addSymbol(taskInstance, taskInstance.getTask());
781	} else {
782	taskBuilder.setTask(taskInstance, task);
783	unifiedTasks++;
784	}
785	}
786
787	comparator.clearBuffers();
788	}
789
790	appData.getStopWatch().stop("harmonizing event tasks");
791	Console.traceln(Level.INFO, "harmonized " + unifiedTasks
792	+ " task occurrences (still " + uniqueTasks.size()
793	+ " different tasks)");
794
795	appData.getStopWatch().dumpStatistics(System.out);
796	appData.getStopWatch().reset();
797	}
798
799	/**
800	* <p>
801	* TODO clarify why this is done
802	* </p>.
803	*
804	* @param iteration the iteration
805	* @param iterationInstances the iteration instances
806	*/
807	private void harmonizeIterationInstancesModel(IIteration iteration,
808	List<IIterationInstance> iterationInstances) {
809	final List<ITask> iteratedTaskVariants = new LinkedList<ITask>();
810	final TaskInstanceComparator comparator = preparationTaskHandlingStrategy
811	.getTaskComparator();
812
813	// merge the lexically different variants of iterated task to a unique
814	// list
815	for (final IIterationInstance iterationInstance : iterationInstances) {
816	for (final ITaskInstance executionVariant : iterationInstance) {
817	final ITask candidate = executionVariant.getTask();
818
819	boolean found = false;
820	for (final ITask taskVariant : iteratedTaskVariants) {
821	if (comparator.areLexicallyEqual(taskVariant, candidate)) {
822	taskBuilder.setTask(executionVariant, taskVariant);
823	found = true;
824	break;
825	}
826	}
827
828	if (!found) {
829	iteratedTaskVariants.add(candidate);
830	}
831	}
832	}
833
834	// if there are more than one lexically different variant of iterated
835	// tasks, adapt the
836	// iteration model to be a selection of different variants. In this case
837	// also adapt
838	// the generated iteration instances to correctly contain selection
839	// instances. If there
840	// is only one variant of an iterated task, simply set this as the
841	// marked task of the
842	// iteration. In this case, the instances can be preserved as is
843	if (iteratedTaskVariants.size() > 1) {
844	final ISelection selection = taskFactory.createNewSelection();
845
846	for (final ITask variant : iteratedTaskVariants) {
847	taskBuilder.addChild(selection, variant);
848	}
849
850	taskBuilder.setMarkedTask(iteration, selection);
851
852	for (final IIterationInstance instance : iterationInstances) {
853	for (int i = 0; i < instance.size(); i++) {
854	final ISelectionInstance selectionInstance = taskFactory
855	.createNewTaskInstance(selection);
856	taskBuilder.setChild(selectionInstance, instance.get(i));
857	taskBuilder.setTaskInstance(instance, i, selectionInstance);
858	}
859	}
860	} else {
861	taskBuilder.setMarkedTask(iteration, iteratedTaskVariants.get(0));
862	}
863	}
864
865	/**
866	* Harmonize sequence instances model.
867	*
868	* @param sequence the sequence
869	* @param sequenceInstances the sequence instances
870	* @param sequenceLength the sequence length
871	*/
872	private void harmonizeSequenceInstancesModel(ISequence sequence,
873	List<ISequenceInstance> sequenceInstances, int sequenceLength) {
874	final TaskInstanceComparator comparator = preparationTaskHandlingStrategy
875	.getTaskComparator();
876
877	// ensure for each subtask that lexically different variants are
878	// preserved
879	for (int subTaskIndex = 0; subTaskIndex < sequenceLength; subTaskIndex++) {
880	final List<ITask> subTaskVariants = new LinkedList<ITask>();
881
882	for (final ISequenceInstance sequenceInstance : sequenceInstances) {
883	final ITask candidate = sequenceInstance.get(subTaskIndex)
884	.getTask();
885
886	boolean found = false;
887
888	for (int i = 0; i < subTaskVariants.size(); i++) {
889	if (comparator.areLexicallyEqual(subTaskVariants.get(i),
890	candidate)) {
891	taskBuilder.setTask(sequenceInstance.get(subTaskIndex),
892	subTaskVariants.get(i));
893
894	found = true;
895	break;
896	}
897	}
898
899	if (!found) {
900	subTaskVariants.add(candidate);
901	}
902	}
903
904	// if there are more than one lexically different variant of the sub
905	// task at
906	// the considered position, adapt the sequence model at that
907	// position to have
908	// a selection of the different variants. In this case also adapt
909	// the
910	// generated sequence instances to correctly contain selection
911	// instances. If
912	// there is only one variant of sub tasks at the given position,
913	// simply set
914	// this variant as the sub task of the selection. In this case, the
915	// instances
916	// can be preserved as is
917	if (subTaskVariants.size() > 1) {
918	final ISelection selection = taskFactory.createNewSelection();
919
920	for (final ITask variant : subTaskVariants) {
921	taskBuilder.addChild(selection, variant);
922	}
923
924	taskBuilder.addChild(sequence, selection);
925
926	for (final ISequenceInstance instance : sequenceInstances) {
927	final ISelectionInstance selectionInstance = taskFactory
928	.createNewTaskInstance(selection);
929	taskBuilder.setChild(selectionInstance,
930	instance.get(subTaskIndex));
931	taskBuilder.setTaskInstance(instance, subTaskIndex,
932	selectionInstance);
933	}
934	} else if (subTaskVariants.size() == 1) {
935	taskBuilder.addChild(sequence, subTaskVariants.get(0));
936	}
937	}
938	}
939
940	/**
941	* <p>
942	* replaces all occurrences of all tasks provided in the set with iterations
943	* </p>.
944	*
945	* @param iteratedTasks the tasks to be replaced with iterations
946	* @param sessions the sessions in which the tasks are to be replaced
947	* @param appData the rule application data combining all data used for applying
948	* this rule
949	*/
950	private void replaceIterationsOf(Set<ITask> iteratedTasks,
951	List<IUserSession> sessions, RuleApplicationData appData) {
952	final Map<ITask, IIteration> iterations = new HashMap<ITask, IIteration>();
953	final Map<IIteration, List<IIterationInstance>> iterationInstances = new HashMap<IIteration, List<IIterationInstance>>();
954
955	for (final ITask iteratedTask : iteratedTasks) {
956	final IIteration iteration = taskFactory.createNewIteration();
957	iterations.put(iteratedTask, iteration);
958	iterationInstances.put(iteration,
959	new LinkedList<IIterationInstance>());
960	}
961
962	IIterationInstance iterationInstance;
963
964	for (final IUserSession session : sessions) {
965	int index = 0;
966	iterationInstance = null;
967
968	while (index < session.size()) {
969	// we prepared the task instances to refer to unique tasks, if
970	// they are treated
971	// as equal. Therefore, we just compare the identity of the
972	// tasks of the task
973	// instances
974	final ITask currentTask = session.get(index).getTask();
975	final IIteration iteration = iterations.get(currentTask);
976	if (iteration != null) {
977	if ((iterationInstance == null)
978	\|\| (iterationInstance.getTask() != iteration)) {
979	iterationInstance = taskFactory
980	.createNewTaskInstance(iteration);
981	iterationInstances.get(iteration)
982	.add(iterationInstance);
983	taskBuilder.addTaskInstance(session, index,
984	iterationInstance);
985	index++;
986	}
987
988	taskBuilder.addChild(iterationInstance, session.get(index));
989	taskBuilder.removeTaskInstance(session, index);
990	} else {
991	if (iterationInstance != null) {
992	iterationInstance = null;
993	}
994	index++;
995	}
996	}
997	}
998
999	for (final Map.Entry<IIteration, List<IIterationInstance>> entry : iterationInstances
1000	.entrySet()) {
1001	harmonizeIterationInstancesModel(entry.getKey(), entry.getValue());
1002	}
1003	}
1004
1005	/**
1006	* Replace sequences occurring most often.
1007	*
1008	* @param appData the rule application data combining all data used for applying
1009	* this rule
1010	*/
1011	private void replaceSequencesOccurringMostOften(RuleApplicationData appData) {
1012	appData.detectedAndReplacedTasks(false);
1013
1014	if ((appData.getLastFoundTasks().size() > 0)
1015	&& (appData.getLastFoundTasks().getOccurrenceCount() > 1)) {
1016	Console.traceln(Level.FINER, "replacing tasks occurrences");
1017
1018	for (final List<ITaskInstance> task : appData.getLastFoundTasks()) {
1019	final ISequence sequence = taskFactory.createNewSequence();
1020
1021	Console.traceln(Level.FINEST, "replacing " + sequence.getId()
1022	+ ": " + task);
1023
1024	final List<ISequenceInstance> sequenceInstances = replaceTaskOccurrences(
1025	task, appData.getSessions(), sequence);
1026
1027	harmonizeSequenceInstancesModel(sequence, sequenceInstances,
1028	task.size());
1029	appData.detectedAndReplacedTasks(appData
1030	.detectedAndReplacedTasks()
1031	\|\| (sequenceInstances.size() > 0));
1032
1033	if (sequenceInstances.size() < appData.getLastFoundTasks()
1034	.getOccurrenceCount()) {
1035	Console.traceln(Level.FINE,
1036	sequence.getId()
1037	+ ": replaced task only "
1038	+ sequenceInstances.size()
1039	+ " times instead of expected "
1040	+ appData.getLastFoundTasks()
1041	.getOccurrenceCount());
1042	}
1043	}
1044	}
1045
1046	}
1047
1048	/**
1049	* Replace task occurrences.
1050	*
1051	* @param task the task
1052	* @param sessions the sessions
1053	* @param temporalTaskModel the temporal task model
1054	* @return the list
1055	*/
1056	private List<ISequenceInstance> replaceTaskOccurrences(
1057	List<ITaskInstance> task, List<IUserSession> sessions,
1058	ISequence temporalTaskModel) {
1059	final List<ISequenceInstance> sequenceInstances = new LinkedList<ISequenceInstance>();
1060
1061	for (final IUserSession session : sessions) {
1062	int index = -1;
1063
1064	do {
1065	index = getSubListIndex(session, task, ++index);
1066
1067	if (index > -1) {
1068	sequenceInstances
1069	.add(RuleUtils.createNewSubSequenceInRange(session,
1070	index, (index + task.size()) - 1,
1071	temporalTaskModel, taskFactory, taskBuilder));
1072	}
1073	} while (index > -1);
1074	}
1075
1076	return sequenceInstances;
1077	}
1078
1079	// /**
1080	// * @author Patrick Harms
1081	// */
1082	// private class TrieStatisticsDumper implements
1083	// TrieProcessor<ITaskInstance> {
1084	//
1085	// /**
1086	// *
1087	// */
1088	// private Map<Integer, Integer> counters = new HashMap<Integer, Integer>();
1089	//
1090	// /* (non-Javadoc)
1091	// * @see
1092	// de.ugoe.cs.autoquest.usageprofiles.TrieProcessor#process(java.util.List,
1093	// int)
1094	// */
1095	// @Override
1096	// public TrieProcessor.Result process(List<ITaskInstance> subsequence, int
1097	// count) {
1098	// if (subsequence.size() == 1) {
1099	// Integer value = counters.get(count);
1100	//
1101	// if (value == null) {
1102	// value = 0;
1103	// }
1104	//
1105	// counters.put(count, value + 1);
1106	//
1107	// return TrieProcessor.Result.CONTINUE;
1108	// }
1109	// else {
1110	// // ignore singular occurrences
1111	// return TrieProcessor.Result.SKIP_NODE;
1112	// }
1113	// }
1114	//
1115	// /**
1116	// * @return
1117	// */
1118	// public void dumpCounters() {
1119	// int dumpedCounters = 0;
1120	//
1121	// int count = 1;
1122	// while (dumpedCounters < counters.size()) {
1123	// Integer value = counters.get(count++);
1124	// if (value != null) {
1125	// System.out.println(value + " symbols occurred " + count + " times");
1126	// dumpedCounters++;
1127	// }
1128	// }
1129	// }
1130	//
1131	// }
1132
1133	/**
1134	* <p>
1135	* searches the provided sessions for task iterations. If a task is
1136	* iterated, it is added to the returned set.
1137	* </p>
1138	*
1139	* @param sessions the sessions
1140	* @return a set of tasks being iterated somewhere
1141	*/
1142	private Set<ITask> searchIteratedTasks(List<IUserSession> sessions) {
1143	final Set<ITask> iteratedTasks = new HashSet<ITask>();
1144	for (final IUserSession session : sessions) {
1145	for (int i = 0; i < (session.size() - 1); i++) {
1146	// we prepared the task instances to refer to unique tasks, if
1147	// they are treated
1148	// as equal. Therefore, we just compare the identity of the
1149	// tasks of the task
1150	// instances
1151	if (session.get(i).getTask() == session.get(i + 1).getTask()) {
1152	iteratedTasks.add(session.get(i).getTask());
1153	}
1154	}
1155	}
1156
1157	return iteratedTasks;
1158	}
1159
1160	/*
1161	* (non-Javadoc)
1162	*
1163	* @see java.lang.Object#toString()
1164	*/
1165	@Override
1166	public String toString() {
1167	return "SequenceForTaskDetectionRule";
1168	}
1169
1170	// methods for internal testing
1171	// private void checkMatchingOfSessions(List<List<Event>> flattenedSessions,
1172	// List<IUserSession> sessions,
1173	// String when)
1174	// {
1175	// List<List<Event>> currentFlattenedSessions = flattenSessions(sessions);
1176	// if (flattenedSessions.size() != currentFlattenedSessions.size()) {
1177	// System.out.println("################## number of sessions changed after "
1178	// + when);
1179	// }
1180	// else {
1181	// for (int i = 0; i < flattenedSessions.size(); i++) {
1182	// List<Event> expected = flattenedSessions.get(i);
1183	// List<Event> current = currentFlattenedSessions.get(i);
1184	//
1185	// if (expected.size() != current.size()) {
1186	// System.out.println
1187	// ("################## length of session " + i + " changed after " + when);
1188	// }
1189	// else {
1190	// for (int j = 0; j < expected.size(); j++) {
1191	// if (!expected.get(j).equals(current.get(j))) {
1192	// System.out.println("################## event " + j + " of session " +
1193	// i + " changed after " + when);
1194	// }
1195	// }
1196	// }
1197	// }
1198	// }
1199	// }
1200	//
1201	// private List<List<Event>> flattenSessions(List<IUserSession> sessions) {
1202	// List<List<Event>> flattenedSessions = new ArrayList<List<Event>>();
1203	// for (IUserSession session : sessions) {
1204	// List<Event> flattenedUserSession = new ArrayList<Event>();
1205	// flatten(session, flattenedUserSession);
1206	// flattenedSessions.add(flattenedUserSession);
1207	// }
1208	//
1209	// return flattenedSessions;
1210	// }
1211	//
1212	// private void flatten(IUserSession iUserSession, List<Event>
1213	// flattenedUserSession) {
1214	// for (ITaskInstance instance : iUserSession) {
1215	// flatten(instance, flattenedUserSession);
1216	// }
1217	// }
1218	//
1219	// private void flatten(ITaskInstance instance, List<Event>
1220	// flattenedUserSession) {
1221	// if (instance instanceof ITaskInstanceList) {
1222	// for (ITaskInstance child : (ITaskInstanceList) instance) {
1223	// flatten(child, flattenedUserSession);
1224	// }
1225	// }
1226	// else if (instance instanceof ISelectionInstance) {
1227	// flatten(((ISelectionInstance) instance).getChild(),
1228	// flattenedUserSession);
1229	// }
1230	// else if (instance instanceof IOptionalInstance) {
1231	// flatten(((IOptionalInstance) instance).getChild(), flattenedUserSession);
1232	// }
1233	// else if (instance instanceof IEventTaskInstance) {
1234	// flattenedUserSession.add(((IEventTaskInstance) instance).getEvent());
1235	// }
1236	// }
1237
1238	}

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

Context Navigation

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

Download in other formats: