Ignore:
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:
1 edited

Legend:

Unmodified
Added
Removed

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

    r1196 r1251  
    3939     */ 
    4040    public boolean equals(T symbol1, T symbol2); 
     41     
     42    /** 
     43     * <p> 
     44     * returns a search order for buckets. This method can be used for optimizing a search for 
     45     * equal symbols. The client of this class can store symbols in buckets of similar symbols. 
     46     * Those buckets get an id denoted by an integer. The most appropriate bucket for a symbol is 
     47     * the first element in the array returned by this method. The symbol should therefore be put 
     48     * into that bucket. 
     49     * </p> 
     50     * <p> 
     51     * In case a search for an equal symbol shall be performed at the client side, the client 
     52     * checks the available buckets in the order given as return value of this method. All other 
     53     * buckets are searched afterwards. In this scenario it is ensured, that the equal symbol is 
     54     * found as soon as possible as the search always starts in the most appropriate bucket. 
     55     * However, the other buckets are searched, as well, if no equal symbol is found. Therefore, 
     56     * in the worst case, all buckets are searched. In the optimal case, the equal symbol is found 
     57     * in the first bucket. 
     58     * </p> 
     59     * <p> 
     60     * The returned array should contain different integers in each field. This allows a most 
     61     * efficient search. If an integer is repeated, it is up to the clien, if this is ignored. 
     62     * </p> 
     63     * 
     64     * @param symbol the symbol for which the bucket order is to be returned 
     65     *  
     66     * @return a search order for buckets as described 
     67     *  
     68     * @see SymbolMap 
     69     */ 
     70    public int[] getBucketSearchOrder(T symbol); 
    4171} 
Note: See TracChangeset for help on using the changeset viewer.