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

Timestamp:

02/21/13 18:41:04 (11 years ago)

Author:

pharms

Message:

• allowed to search for all sub sequences with a dedicated number of occurrence

File:

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

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

@@ -324 +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.
+     * returns a list of symbol sequences which have a minimal length and that occurred as often
+     * as defined by the given occurrence count. If the given occurrence count is smaller 1 then
+     * those sequences are returned, that occur most often. The resulting list is empty, if there
+     * is no symbol sequence with the minimal length or the provided number of occurrences.
      * </p>
      *
-     * @param minimalLength the minimal length of the returned sequences
+     * @param minimalLength   the minimal length of the returned sequences
+     * @param occurrenceCount the number of occurrences of the returned sequences
      * 
      * @return as described
      */
-    public Collection<List<T>> getSequencesWithMostOccurrences(int minimalLength) {
+    public Collection<List<T>> getSequencesWithOccurrenceCount(int minimalLength,
+                                                               int occurrenceCount)
+    {
         LinkedList<TrieNode<T>> context = new LinkedList<TrieNode<T>>();
         Collection<List<TrieNode<T>>> paths = new LinkedList<List<TrieNode<T>>>();
@@ -339 +343 @@
         context.push(rootNode);
         
-        // traverse the trie and determine all sequences, which have the maximum number of
+        // traverse the trie and determine all sequences, which have the provided number of
         // occurrences and a minimal length.
         
         // minimalLength + 1 because we denote the depth including the root node
-        determineLongPathsWithMostOccurrences(minimalLength + 1, paths, context);
+        determineLongPathsWithMostOccurrences(minimalLength + 1, occurrenceCount, paths, context);
         
         Collection<List<T>> resultingPaths = new LinkedList<List<T>>();
@@ -368 +372 @@
     /**
      * <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.
+     * Traverses the trie to collect all sequences with a defined number of occurrences and with
+     * a minimal length. If the given occurrence count is smaller 1 then those sequences are
+     * searched that occur most often. The length of the sequences 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
+     * @param minimalDepth    the minimal recursion depth to be done
+     * @param occurrenceCount the number of occurrences of the returned sequences
+     * @param paths           the paths through the trie that all occurred with the same amount
+     *                        (if occurrence count is smaller 1, the paths which occurred most
+     *                        often) and that have the so far found matching number of occurrences
+     *                        (is updated each time a further path with the same number of
+     *                        occurrences is found; if occurrence count is smaller 1
+     *                        it 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,
+                                                       int                           occurrenceCount,
                                                        Collection<List<TrieNode<T>>> paths,
                                                        LinkedList<TrieNode<T>>       context)
     {
-        int maxCount = 0;
+        int envisagedCount = occurrenceCount;
 
         // only if we already reached the depth to be achieved, we check if the paths have the
-        // maximum number of occurrences
+        // required 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 (envisagedCount < 1) {
+                // try to determine the maximum number of occurrences so far, if any
+                if (paths.size() > 0) {
+                    List<TrieNode<T>> path = paths.iterator().next();
+                    envisagedCount = 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() > envisagedCount) {
+                    paths.clear();
+                    envisagedCount = 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) {
+            if (context.getLast().getCount() == envisagedCount) {
                 paths.add(new LinkedList<TrieNode<T>>(context));
             }
@@ -411 +423 @@
         // perform the trie traversal
         for (TrieNode<T> child : context.getLast().getChildren()) {
-            if (child.getCount() >= maxCount) {
+            if (child.getCount() >= envisagedCount) {
                 context.add(child);
-                determineLongPathsWithMostOccurrences(minimalDepth, paths, context);
+                determineLongPathsWithMostOccurrences
+                    (minimalDepth, occurrenceCount, paths, context);
                 context.removeLast();
             }