Context Navigation

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

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

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

Download in other formats: