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