Changeset 1060 for trunk/autoquest-core-usageprofiles/src/main/java/de/ugoe/cs/autoquest/usageprofiles/Trie.java

Timestamp:

02/07/13 17:57:07 (11 years ago)

Author:

pharms

Message:

• extended Trie implementation to be able to use different compare strategies
• implemented a method to determine subsequences of a minimal length that occur most often

File:

• trunk/autoquest-core-usageprofiles/src/main/java/de/ugoe/cs/autoquest/usageprofiles/Trie.java (modified) (9 diffs)

trunk/autoquest-core-usageprofiles/src/main/java/de/ugoe/cs/autoquest/usageprofiles/Trie.java

@@ -34 +34 @@
  * </p>
  * 
- * @author Steffen Herbold
+ * @author Steffen Herbold, Patrick Harms
  * 
  * @param <T>
@@ -66 +66 @@
     /**
      * <p>
-     * Contructor. Creates a new Trie.
+     * Comparator to be used for comparing the symbols with each other
+     * </p>
+     */
+    private SymbolComparator<T> comparator;
+
+    /**
+     * <p>
+     * Contructor. Creates a new Trie with a {@link DefaultSymbolComparator}.
      * </p>
      */
     public Trie() {
-        rootNode = new TrieNode<T>();
+        this(new DefaultSymbolComparator<T>());
+    }
+
+    /**
+     * <p>
+     * Contructor. Creates a new Trie with that uses a specific {@link SymbolComparator}.
+     * </p>
+     */
+    public Trie(SymbolComparator<T> comparator) {
+        this.comparator = comparator;
+        rootNode = new TrieNode<T>(comparator);
         knownSymbols = new LinkedHashSet<T>();
     }
@@ -76 +93 @@
     /**
      * <p>
-     * Copy-Constructor. Creates a new Trie as the copy of other. The other trie must noch be null.
+     * Copy-Constructor. Creates a new Trie as the copy of other. The other trie must not be null.
      * </p>
      * 
@@ -88 +105 @@
         rootNode = new TrieNode<T>(other.rootNode);
         knownSymbols = new LinkedHashSet<T>(other.knownSymbols);
+        comparator = other.comparator;
     }
 
@@ -120 +138 @@
         for (T currentEvent : sequence) {
             latestActions.add(currentEvent);
-            knownSymbols.add(currentEvent);
+            addToKnownSymbols(currentEvent);
             i++;
             if (i >= maxOrder) {
@@ -143 +161 @@
     protected void add(List<T> subsequence) {
         if (subsequence != null && !subsequence.isEmpty()) {
-            knownSymbols.addAll(subsequence);
+            addToKnownSymbols(subsequence);
             subsequence = new LinkedList<T>(subsequence); // defensive copy!
             T firstSymbol = subsequence.get(0);
@@ -306 +324 @@
     /**
      * <p>
+     * returns a list of symbol sequences which have a minimal length and that occurred most often
+     * with the same number of occurrences. The resulting list is empty, if there is no symbol
+     * sequence with the minimal length.
+     * </p>
+     *
+     * @param minimalLength the minimal length of the returned sequences
+     * 
+     * @return as described
+     */
+    public Collection<List<T>> getSequencesWithMostOccurrences(int minimalLength) {
+        LinkedList<TrieNode<T>> context = new LinkedList<TrieNode<T>>();
+        Collection<List<TrieNode<T>>> paths = new LinkedList<List<TrieNode<T>>>();
+        
+        context.push(rootNode);
+        
+        // traverse the trie and determine all sequences, which have the maximum number of
+        // occurrences and a minimal length.
+        
+        // minimalLength + 1 because we denote the depth including the root node
+        determineLongPathsWithMostOccurrences(minimalLength + 1, paths, context);
+        
+        Collection<List<T>> resultingPaths = new LinkedList<List<T>>();
+        List<T> resultingPath;
+        
+        if (paths.size() > 0) {
+            
+            for (List<TrieNode<T>> path : paths) {
+                resultingPath = new LinkedList<T>();
+                
+                for (TrieNode<T> node : path) {
+                    if (node.getSymbol() != null) {
+                        resultingPath.add(node.getSymbol());
+                    }
+                }
+                
+                resultingPaths.add(resultingPath);
+            }
+        }
+        
+        return resultingPaths;
+    }
+
+    /**
+     * <p>
+     * Traverses the trie to collect all sequences with a maximum number of occurrences and with
+     * a minimal length. The length is encoded in the provided recursion depth.
+     * </p>
+     *
+     * @param minimalDepth the minimal recursion depth to be done
+     * @param paths        the paths through the trie that all occurred with the same amount and
+     *                     that have the so far found maximum of occurrences (is updated each
+     *                     time a further path with the same number of occurrences is found; is
+     *                     replaced if a path with more occurrences is found)
+     * @param context      the path through the trie, that is analyzed by the recursive call
+     */
+    private void determineLongPathsWithMostOccurrences(int                           minimalDepth,
+                                                       Collection<List<TrieNode<T>>> paths,
+                                                       LinkedList<TrieNode<T>>       context)
+    {
+        int maxCount = 0;
+
+        // only if we already reached the depth to be achieved, we check if the paths have the
+        // maximum number of occurrences
+        if (context.size() >= minimalDepth) {
+            
+            // try to determine the maximum number of occurrences so far, if any
+            if (paths.size() > 0) {
+                List<TrieNode<T>> path = paths.iterator().next();
+                maxCount = path.get(path.size() - 1).getCount();
+            }
+
+            // if the current path has a higher number of occurrences than all so far, clear
+            // the paths collected so far and set the new number of occurrences as new maximum
+            if (context.getLast().getCount() > maxCount) {
+                paths.clear();
+                maxCount = context.getLast().getCount();
+            }
+            
+            // if the path matches the current maximal number of occurrences, add it to the list
+            // of collected paths with these number of occurrences
+            if (context.getLast().getCount() == maxCount) {
+                paths.add(new LinkedList<TrieNode<T>>(context));
+            }
+        }
+        
+        // perform the trie traversal
+        for (TrieNode<T> child : context.getLast().getChildren()) {
+            if (child.getCount() >= maxCount) {
+                context.add(child);
+                determineLongPathsWithMostOccurrences(minimalDepth, paths, context);
+                context.removeLast();
+            }
+        }
+    }
+    
+    /**
+     * <p>
+     * adds a new symbol to the collection of known symbols if this symbol is not already
+     * contained. The symbols are compared using the comparator.
+     * </p>
+     *
+     * @param symbol the symbol to be added to the known symbols
+     */
+    private void addToKnownSymbols(T symbol) {
+        for (T knownSymbol : knownSymbols) {
+            if (comparator.equals(knownSymbol, symbol)) {
+                return;
+            }
+        }
+        
+        knownSymbols.add(symbol);
+    }
+
+    /**
+     * <p>
+     * adds a list of new symbols to the collection of known symbols. Uses the
+     * {@link #addToKnownSymbols(Object)} method for each element of the provided list.
+     * </p>
+     *
+     * @param symbols the list of symbols to be added to the known symbols
+     */
+    private void addToKnownSymbols(List<T> symbols) {
+        for (T symbol : symbols) {
+            addToKnownSymbols(symbol);
+        }
+    }
+
+    /**
+     * <p>
      * Helper class for graph visualization of a trie.
      * </p>
@@ -441 +588 @@
         knownSymbols = new HashSet<T>();
         for (TrieNode<T> node : rootNode.getChildren()) {
-            knownSymbols.add(node.getSymbol());
+            addToKnownSymbols(node.getSymbol());
         }
     }
@@ -478 +625 @@
         return hash;
     }
+
 }