Context Navigation

source: branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/SequenceForTaskDetectionRuleAlignment.java @ 1615

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

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

Download in other formats: