Changeset 1251

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

Location:

trunk

Files:

• autoquest-core-usageprofiles-test/src/test/java/de/ugoe/cs/autoquest/usageprofiles/SymbolMapTest.java (added)
• autoquest-core-usageprofiles/src/main/java/de/ugoe/cs/autoquest/usageprofiles/DefaultSymbolComparator.java (modified) (2 diffs)
• autoquest-core-usageprofiles/src/main/java/de/ugoe/cs/autoquest/usageprofiles/SymbolComparator.java (modified) (1 diff)
• autoquest-core-usageprofiles/src/main/java/de/ugoe/cs/autoquest/usageprofiles/SymbolMap.java (added)
• autoquest-core-usageprofiles/src/main/java/de/ugoe/cs/autoquest/usageprofiles/Trie.java (modified) (9 diffs)
• autoquest-core-usageprofiles/src/main/java/de/ugoe/cs/autoquest/usageprofiles/TrieNode.java (modified) (12 diffs)

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

@@ -30 +30 @@
 
     /* (non-Javadoc)
-     * @see de.ugoe.cs.autoquest.tasktrees.temporalrelation.SymbolComparator#equals(java.lang.Object, java.lang.Object)
+     * @see de.ugoe.cs.autoquest.tasktrees.temporalrelation.SymbolComparator#equals(Object, Object)
      */
     @Override
@@ -42 +42 @@
     }
 
+    /* (non-Javadoc)
+     * @see de.ugoe.cs.autoquest.usageprofiles.SymbolComparator#getBucketSearchOrder(Object)
+     */
+    @Override
+    public int[] getBucketSearchOrder(T symbol) {
+        if (symbol != null) {
+            return new int[] { symbol.hashCode() };
+        }
+        else {
+            return null;
+        }
+    }
+
 }

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

@@ -39 +39 @@
      */
     public boolean equals(T symbol1, T symbol2);
+    
+    /**
+     * <p>
+     * returns a search order for buckets. This method can be used for optimizing a search for
+     * equal symbols. The client of this class can store symbols in buckets of similar symbols.
+     * Those buckets get an id denoted by an integer. The most appropriate bucket for a symbol is
+     * the first element in the array returned by this method. The symbol should therefore be put
+     * into that bucket.
+     * </p>
+     * <p>
+     * In case a search for an equal symbol shall be performed at the client side, the client
+     * checks the available buckets in the order given as return value of this method. All other
+     * buckets are searched afterwards. In this scenario it is ensured, that the equal symbol is
+     * found as soon as possible as the search always starts in the most appropriate bucket.
+     * However, the other buckets are searched, as well, if no equal symbol is found. Therefore,
+     * in the worst case, all buckets are searched. In the optimal case, the equal symbol is found
+     * in the first bucket.
+     * </p>
+     * <p>
+     * The returned array should contain different integers in each field. This allows a most
+     * efficient search. If an integer is repeated, it is up to the clien, if this is ignored.
+     * </p>
+     *
+     * @param symbol the symbol for which the bucket order is to be returned
+     * 
+     * @return a search order for buckets as described
+     * 
+     * @see SymbolMap
+     */
+    public int[] getBucketSearchOrder(T symbol);
 }

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());

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

@@ -67 +67 @@
      * </p>
      */
-    private Collection<TrieNode<T>> children;
-
+    private SymbolMap<T, TrieNode<T>> children;
+    
     /**
      * <p>
@@ -115 +115 @@
         this.symbol = null;
         count = 0;
-        children = new LinkedList<TrieNode<T>>();
+        children = new SymbolMap<T, TrieNode<T>>(this.comparator);
     }
 
@@ -140 +140 @@
 
         count = 0;
-        children = new LinkedList<TrieNode<T>>();
+        children = new SymbolMap<T, TrieNode<T>>(this.comparator);
     }
 
@@ -157 +157 @@
         count = other.count;
         comparator = other.comparator;
-        children = new LinkedList<TrieNode<T>>();
-        for (TrieNode<T> child : other.children) {
-            children.add(new TrieNode<T>(child));
+        children = new SymbolMap<T, TrieNode<T>>(this.comparator);
+        
+        for (TrieNode<T> child : other.children.getValues()) {
+            children.addSymbol(child.getSymbol(), new TrieNode<T>(child));
         }
     }
@@ -224 +225 @@
         if (node == null) {
             node = new TrieNode<T>(symbol, comparator);
-            children.add(node);
+            children.addSymbol(symbol, node);
         }
         return node;
@@ -240 +241 @@
      */
     protected TrieNode<T> getChild(T symbol) {
-        for (TrieNode<T> child : children) {
-            if (comparator.equals(child.getSymbol(), symbol)) {
-                return child;
-            }
-        }
-        return null;
+        return children.getValue(symbol);
     }
 
@@ -256 +252 @@
      */
     protected Collection<TrieNode<T>> getChildren() {
-        return children;
+        return children.getValues();
     }
 
@@ -296 +292 @@
     public Collection<T> getFollowingSymbols() {
         Collection<T> followingSymbols = new LinkedList<T>();
-        for (TrieNode<T> child : children) {
+        for (TrieNode<T> child : children.getValues()) {
             followingSymbols.add(child.getSymbol());
         }
@@ -346 +342 @@
             graph.addChild(new Edge(), parent, currentVertex);
         }
-        for (TrieNode<T> node : children) {
+        for (TrieNode<T> node : children.getValues()) {
             node.getGraph(currentVertex, graph);
         }
@@ -370 +366 @@
         stringBuilder.append(" " + hashCode() + " [label=\"" + thisSaneId + "\"];" +
             StringTools.ENDLINE);
-        for (TrieNode<T> childNode : children) {
+        for (TrieNode<T> childNode : children.getValues()) {
             stringBuilder.append(" " + hashCode() + " -> " + childNode.hashCode() + ";" +
                 StringTools.ENDLINE);
         }
-        for (TrieNode<T> childNode : children) {
+        for (TrieNode<T> childNode : children.getValues()) {
             childNode.appendDotRepresentation(stringBuilder);
         }
@@ -412 +408 @@
     protected void getLeafAncestors(List<TrieNode<T>> ancestors) {
         boolean isAncestor = false;
-        for (TrieNode<T> child : children) {
+        for (TrieNode<T> child : children.getValues()) {
             child.getLeafAncestors(ancestors);
             isAncestor |= child.isLeaf();
@@ -431 +427 @@
     protected int getNumLeafs() {
         int numLeafs = 0;
-        for (TrieNode<T> child : children) {
+        for (TrieNode<T> child : children.getValues()) {
             if (child.isLeaf()) {
                 numLeafs++;