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

Timestamp:

07/12/13 16:45:53 (11 years ago)

Author:

pharms

Message:

• improved performance of the trie for large alphabets by using the symbol map. This is an improved list of symbols that allows a more efficient lookup for symbols using buckets of symbol as an initial search order

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

@@ -17 +17 @@
 import java.io.Serializable;
 import java.util.Collection;
-import java.util.HashSet;
 import java.util.LinkedHashSet;
 import java.util.LinkedList;
@@ -55 +54 @@
      * </p>
      */
-    private Collection<T> knownSymbols;
+    private SymbolMap<T, T> knownSymbols;
 
     /**
@@ -88 +87 @@
         this.comparator = comparator;
         rootNode = new TrieNode<T>(comparator);
-        knownSymbols = new LinkedHashSet<T>();
+        knownSymbols = new SymbolMap<T, T>(this.comparator);
     }
 
@@ -104 +103 @@
         }
         rootNode = new TrieNode<T>(other.rootNode);
-        knownSymbols = new LinkedHashSet<T>(other.knownSymbols);
+        knownSymbols = new SymbolMap<T, T>(other.knownSymbols);
         comparator = other.comparator;
     }
@@ -116 +115 @@
      */
     public Collection<T> getKnownSymbols() {
-        return new LinkedHashSet<T>(knownSymbols);
+        return new LinkedHashSet<T>(knownSymbols.getSymbols());
     }
 
@@ -153 +152 @@
     /**
      * <p>
-     * Adds a given subsequence to the trie and increases the counters accordingly.
+     * Adds a given subsequence to the trie and increases the counters accordingly. NOTE: This
+     * method does not add the symbols to the list of known symbols. This is only ensured using
+     * the method {@link #train(List, int)}.
      * </p>
      * 
@@ -162 +163 @@
     protected void add(List<T> subsequence) {
         if (subsequence != null && !subsequence.isEmpty()) {
-            addToKnownSymbols(subsequence);
             subsequence = new LinkedList<T>(subsequence); // defensive copy!
             T firstSymbol = subsequence.get(0);
@@ -495 +495 @@
      */
     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);
+        if (!knownSymbols.containsSymbol(symbol)) {
+            knownSymbols.addSymbol(symbol, symbol);
         }
     }
@@ -653 +635 @@
      */
     public void updateKnownSymbols() {
-        knownSymbols = new HashSet<T>();
+        knownSymbols = new SymbolMap<T, T>(this.comparator);
         for (TrieNode<T> node : rootNode.getChildren()) {
             addToKnownSymbols(node.getSymbol());