[1107] | 1 | package de.ugoe.cs.autoquest.tasktrees.temporalrelation; |
---|
| 2 | |
---|
| 3 | import java.util.Collection; |
---|
| 4 | import java.util.Iterator; |
---|
| 5 | import java.util.LinkedList; |
---|
| 6 | import java.util.List; |
---|
| 7 | |
---|
| 8 | import de.ugoe.cs.autoquest.tasktrees.nodeequality.NodeEquality; |
---|
| 9 | import de.ugoe.cs.autoquest.tasktrees.nodeequality.NodeEqualityRuleManager; |
---|
| 10 | import de.ugoe.cs.autoquest.tasktrees.treeifc.ISequence; |
---|
| 11 | import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskTreeBuilder; |
---|
| 12 | import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskTreeNode; |
---|
| 13 | import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskTreeNodeFactory; |
---|
| 14 | import de.ugoe.cs.autoquest.usageprofiles.SymbolComparator; |
---|
| 15 | import de.ugoe.cs.autoquest.usageprofiles.Trie; |
---|
| 16 | |
---|
| 17 | /** |
---|
| 18 | * <p> |
---|
| 19 | * TODO comment |
---|
| 20 | * </p> |
---|
| 21 | * |
---|
| 22 | * @author Patrick Harms |
---|
| 23 | */ |
---|
| 24 | class DefaultTaskSequenceDetectionRule implements TemporalRelationshipRule { |
---|
| 25 | |
---|
| 26 | /** |
---|
| 27 | * <p> |
---|
| 28 | * the task tree node factory to be used for creating substructures for the temporal |
---|
| 29 | * relationships identified during rule |
---|
| 30 | * </p> |
---|
| 31 | */ |
---|
| 32 | private ITaskTreeNodeFactory taskTreeNodeFactory; |
---|
| 33 | /** |
---|
| 34 | * <p> |
---|
| 35 | * the task tree builder to be used for creating substructures for the temporal relationships |
---|
| 36 | * identified during rule application |
---|
| 37 | * </p> |
---|
| 38 | */ |
---|
| 39 | private ITaskTreeBuilder taskTreeBuilder; |
---|
| 40 | |
---|
| 41 | /** |
---|
| 42 | * <p> |
---|
| 43 | * the node comparator to be used for comparing task tree nodes |
---|
| 44 | * </p> |
---|
| 45 | */ |
---|
| 46 | private SymbolComparator<ITaskTreeNode> nodeComparator; |
---|
| 47 | |
---|
| 48 | /** |
---|
| 49 | * <p> |
---|
| 50 | * instantiates the rule and initializes it with a node equality rule manager and the minimal |
---|
| 51 | * node equality identified sublist must have to consider them as iterated. |
---|
| 52 | * </p> |
---|
| 53 | */ |
---|
| 54 | DefaultTaskSequenceDetectionRule(NodeEqualityRuleManager nodeEqualityRuleManager, |
---|
| 55 | NodeEquality minimalNodeEquality, |
---|
| 56 | ITaskTreeNodeFactory taskTreeNodeFactory, |
---|
| 57 | ITaskTreeBuilder taskTreeBuilder) |
---|
| 58 | { |
---|
| 59 | this.taskTreeNodeFactory = taskTreeNodeFactory; |
---|
| 60 | this.taskTreeBuilder = taskTreeBuilder; |
---|
| 61 | |
---|
| 62 | this.nodeComparator = |
---|
| 63 | new TaskTreeNodeComparator(nodeEqualityRuleManager, minimalNodeEquality); |
---|
| 64 | } |
---|
| 65 | |
---|
| 66 | /* |
---|
| 67 | * (non-Javadoc) |
---|
| 68 | * |
---|
| 69 | * @see de.ugoe.cs.tasktree.temporalrelation.TemporalRelationshipRule#apply(TaskTreeNode, |
---|
| 70 | * boolean) |
---|
| 71 | */ |
---|
| 72 | @Override |
---|
| 73 | public RuleApplicationResult apply(ITaskTreeNode parent, boolean finalize) { |
---|
| 74 | if (!(parent instanceof ISequence)) { |
---|
| 75 | return null; |
---|
| 76 | } |
---|
| 77 | |
---|
| 78 | if (!finalize) { |
---|
| 79 | // the rule is always feasible as tasks may occur at any time |
---|
| 80 | RuleApplicationResult result = new RuleApplicationResult(); |
---|
| 81 | result.setRuleApplicationStatus(RuleApplicationStatus.RULE_APPLICATION_FEASIBLE); |
---|
| 82 | return result; |
---|
| 83 | } |
---|
| 84 | |
---|
| 85 | long timestamp1; |
---|
| 86 | long timestamp2 = System.currentTimeMillis(); |
---|
| 87 | long ms1 = 0; |
---|
| 88 | long ms2 = 0; |
---|
| 89 | long ms3 = 0; |
---|
| 90 | long ms4 = 0; |
---|
| 91 | |
---|
| 92 | List<ISequence> createdSequences = new LinkedList<ISequence>(); |
---|
| 93 | |
---|
| 94 | int evisagedNoOfOccurrences = 0; |
---|
| 95 | |
---|
| 96 | do { |
---|
| 97 | timestamp1 = timestamp2; |
---|
| 98 | Trie<ITaskTreeNode> trie = new Trie<ITaskTreeNode>(nodeComparator); |
---|
| 99 | |
---|
| 100 | System.out.println("training trie"); |
---|
| 101 | trainTrie(trie, parent, createdSequences); |
---|
| 102 | |
---|
| 103 | timestamp2 = System.currentTimeMillis(); |
---|
| 104 | ms1 += timestamp2 - timestamp1; |
---|
| 105 | timestamp1 = timestamp2; |
---|
| 106 | |
---|
| 107 | System.out.println("determining most prominent tasks"); |
---|
| 108 | Collection<List<ITaskTreeNode>> tasks = |
---|
| 109 | trie.getSequencesWithOccurrenceCount(2, evisagedNoOfOccurrences); |
---|
| 110 | |
---|
| 111 | tasks = sortAndRemovePermutationsOfShorterTasks(tasks); |
---|
| 112 | |
---|
| 113 | timestamp2 = System.currentTimeMillis(); |
---|
| 114 | ms2 += timestamp2 - timestamp1; |
---|
| 115 | timestamp1 = timestamp2; |
---|
| 116 | |
---|
| 117 | if ((tasks != null) && (tasks.size() > 0)) { |
---|
| 118 | Iterator<List<ITaskTreeNode>> tasksIterator = tasks.iterator(); |
---|
| 119 | |
---|
| 120 | while (tasksIterator.hasNext()) { |
---|
| 121 | List<ITaskTreeNode> task = tasksIterator.next(); |
---|
| 122 | evisagedNoOfOccurrences = trie.getCount(task); |
---|
| 123 | |
---|
| 124 | // only tasks occurring more often than once are of interest |
---|
| 125 | if (evisagedNoOfOccurrences > 1) { |
---|
| 126 | timestamp2 = System.currentTimeMillis(); |
---|
| 127 | ms3 += timestamp2 - timestamp1; |
---|
| 128 | timestamp1 = timestamp2; |
---|
| 129 | |
---|
| 130 | String taskId = "task " + RuleUtils.getNewId(); |
---|
| 131 | System.out.println("creating sequences for task " + taskId + ": " + task); |
---|
| 132 | createSequenceForTaskOccurrences(taskId, task, parent, createdSequences); |
---|
| 133 | |
---|
| 134 | timestamp2 = System.currentTimeMillis(); |
---|
| 135 | ms4 += timestamp2 - timestamp1; |
---|
| 136 | timestamp1 = timestamp2; |
---|
| 137 | } |
---|
| 138 | } |
---|
| 139 | } |
---|
| 140 | |
---|
| 141 | evisagedNoOfOccurrences--; |
---|
| 142 | } |
---|
| 143 | while (evisagedNoOfOccurrences > 1); |
---|
| 144 | |
---|
| 145 | System.out.println(ms1 + " " + ms2 + " " + ms3 + " " + ms4); |
---|
| 146 | RuleApplicationResult result = new RuleApplicationResult(); |
---|
| 147 | |
---|
| 148 | if (createdSequences.size() > 0) { |
---|
| 149 | for (ISequence sequence : createdSequences) { |
---|
| 150 | result.addNewlyCreatedParentNode(sequence); |
---|
| 151 | } |
---|
| 152 | |
---|
| 153 | result.setRuleApplicationStatus(RuleApplicationStatus.RULE_APPLICATION_FINISHED); |
---|
| 154 | } |
---|
| 155 | |
---|
| 156 | |
---|
| 157 | return result; |
---|
| 158 | } |
---|
| 159 | |
---|
| 160 | /** |
---|
| 161 | * <p> |
---|
| 162 | * TODO: comment |
---|
| 163 | * </p> |
---|
| 164 | * |
---|
| 165 | * @param trie |
---|
| 166 | * @param parent |
---|
| 167 | */ |
---|
| 168 | private void trainTrie(Trie<ITaskTreeNode> trie, |
---|
| 169 | ITaskTreeNode parent, |
---|
| 170 | List<ISequence> createdSequences) |
---|
| 171 | { |
---|
| 172 | List<ITaskTreeNode> children = parent.getChildren(); |
---|
| 173 | |
---|
| 174 | if ((children != null) && (children.size() > 0)) { |
---|
| 175 | trie.train(children, children.size()); |
---|
| 176 | |
---|
| 177 | for (ITaskTreeNode child : children) { |
---|
| 178 | trainTrie(trie, child, createdSequences); |
---|
| 179 | } |
---|
| 180 | } |
---|
| 181 | } |
---|
| 182 | |
---|
| 183 | /** |
---|
| 184 | * |
---|
| 185 | */ |
---|
| 186 | private List<List<ITaskTreeNode>> |
---|
| 187 | sortAndRemovePermutationsOfShorterTasks(Collection<List<ITaskTreeNode>> tasks) |
---|
| 188 | { |
---|
| 189 | // first of all create a sorted list of the tasks with the longest first |
---|
| 190 | List<List<ITaskTreeNode>> sortedTasks = new LinkedList<List<ITaskTreeNode>>(); |
---|
| 191 | |
---|
| 192 | boolean added; |
---|
| 193 | for (List<ITaskTreeNode> task : tasks) { |
---|
| 194 | added = false; |
---|
| 195 | for (int i = 0; i < sortedTasks.size(); i++) { |
---|
| 196 | if (sortedTasks.get(i).size() < task.size()) { |
---|
| 197 | sortedTasks.add(i, task); |
---|
| 198 | added = true; |
---|
| 199 | break; |
---|
| 200 | } |
---|
| 201 | } |
---|
| 202 | |
---|
| 203 | if (!added) { |
---|
| 204 | sortedTasks.add(task); |
---|
| 205 | } |
---|
| 206 | } |
---|
| 207 | |
---|
| 208 | // now iterate the sorted list and for each task remove all other tasks that are shorter |
---|
| 209 | // (i.e. come later in the sorted list) and that represent a subpart of the task |
---|
| 210 | for (int i = 0; i < sortedTasks.size(); i++) { |
---|
| 211 | for (int j = i + 1; j < sortedTasks.size();) { |
---|
| 212 | if (sortedTasks.get(j).size() < sortedTasks.get(i).size()) { |
---|
| 213 | // found a task that is a potential subtask. Check for this and remove the |
---|
| 214 | // subtask if needed |
---|
| 215 | List<ITaskTreeNode> longTask = sortedTasks.get(i); |
---|
| 216 | List<ITaskTreeNode> shortTask = sortedTasks.get(j); |
---|
| 217 | |
---|
| 218 | if (getSubListIndex(longTask, shortTask, 0) > -1) { |
---|
| 219 | sortedTasks.remove(j); |
---|
| 220 | } |
---|
| 221 | else { |
---|
| 222 | j++; |
---|
| 223 | } |
---|
| 224 | } |
---|
| 225 | else { |
---|
| 226 | j++; |
---|
| 227 | } |
---|
| 228 | } |
---|
| 229 | } |
---|
| 230 | |
---|
| 231 | return sortedTasks; |
---|
| 232 | } |
---|
| 233 | |
---|
| 234 | /** |
---|
| 235 | * <p> |
---|
| 236 | * TODO: comment |
---|
| 237 | * </p> |
---|
| 238 | * |
---|
| 239 | * @param task |
---|
| 240 | * @param parent |
---|
| 241 | * @param treeBuilder |
---|
| 242 | * @param nodeFactory |
---|
| 243 | * @param result |
---|
| 244 | */ |
---|
| 245 | private void createSequenceForTaskOccurrences(String taskId, |
---|
| 246 | List<ITaskTreeNode> task, |
---|
| 247 | ITaskTreeNode parent, |
---|
| 248 | List<ISequence> createdSequences) |
---|
| 249 | { |
---|
| 250 | List<ITaskTreeNode> children = parent.getChildren(); |
---|
| 251 | |
---|
| 252 | if ((children == null) || (children.size() == 0)) { |
---|
| 253 | return; |
---|
| 254 | } |
---|
| 255 | |
---|
| 256 | // first traverse the children |
---|
| 257 | for (ITaskTreeNode child : children) { |
---|
| 258 | createSequenceForTaskOccurrences(taskId, task, child, createdSequences); |
---|
| 259 | } |
---|
| 260 | |
---|
| 261 | // now check the children themselves for an occurrence of the task |
---|
| 262 | int index = -1; |
---|
| 263 | |
---|
| 264 | do { |
---|
| 265 | index = getSubListIndex(children, task, ++index); |
---|
| 266 | |
---|
| 267 | if (index > -1) { |
---|
| 268 | if (task.size() < children.size()) { |
---|
| 269 | ISequence sequence = RuleUtils.createNewSubSequenceInRange |
---|
| 270 | (parent, index, index + task.size() - 1, taskId, |
---|
| 271 | taskTreeNodeFactory, taskTreeBuilder); |
---|
| 272 | |
---|
| 273 | createdSequences.add(sequence); |
---|
| 274 | |
---|
| 275 | children = parent.getChildren(); |
---|
| 276 | } |
---|
| 277 | else { |
---|
| 278 | // the whole list of children is an occurrence of this task. Just set the |
---|
| 279 | // description of the parent and break up |
---|
| 280 | String description = parent.getDescription(); |
---|
| 281 | |
---|
| 282 | if ((description != null) && (description.length() > 0)) { |
---|
| 283 | description += "; " + taskId; |
---|
| 284 | } |
---|
| 285 | else { |
---|
| 286 | description = taskId; |
---|
| 287 | } |
---|
| 288 | |
---|
| 289 | taskTreeBuilder.setDescription(parent, description); |
---|
| 290 | break; |
---|
| 291 | } |
---|
| 292 | } |
---|
| 293 | } |
---|
| 294 | while (index > -1); |
---|
| 295 | } |
---|
| 296 | |
---|
| 297 | /** |
---|
| 298 | * <p> |
---|
| 299 | * TODO: comment |
---|
| 300 | * </p> |
---|
| 301 | * |
---|
| 302 | * @param trie |
---|
| 303 | * @param object |
---|
| 304 | * @return |
---|
| 305 | */ |
---|
| 306 | private int getSubListIndex(List<ITaskTreeNode> list, |
---|
| 307 | List<ITaskTreeNode> subList, |
---|
| 308 | int startIndex) |
---|
| 309 | { |
---|
| 310 | boolean matchFound; |
---|
| 311 | int result = -1; |
---|
| 312 | |
---|
| 313 | for (int i = startIndex; i <= list.size() - subList.size(); i++) { |
---|
| 314 | matchFound = true; |
---|
| 315 | |
---|
| 316 | for (int j = 0; j < subList.size(); j++) { |
---|
| 317 | if (!nodeComparator.equals(list.get(i + j), subList.get(j))) { |
---|
| 318 | matchFound = false; |
---|
| 319 | break; |
---|
| 320 | } |
---|
| 321 | } |
---|
| 322 | |
---|
| 323 | if (matchFound) { |
---|
| 324 | result = i; |
---|
| 325 | break; |
---|
| 326 | } |
---|
| 327 | } |
---|
| 328 | |
---|
| 329 | return result; |
---|
| 330 | } |
---|
| 331 | |
---|
| 332 | } |
---|