java.lang.Objectnet.sourceforge.suggesttree.SuggestTree<V>
V - the type of rank values by which the suggestions are orderedpublic class SuggestTree<V>
A space-efficient index data structure for rank-ordered autocomplete suggestions. For any given prefix, it provides fast access to the top k suggestions that start with that prefix.
The structure is based on a balanced ternary search tree of suggestions where nodes (prefixes) with the same completions are compressed into one node and where each node holds a rank-ordered list of references to the top k suggestions that start with the corresponding prefix or prefixes. Since most of the nodes are at the bottom of the tree, the average length of the suggestion list held by each node is very small. And because for each suggestion inserted into the tree at most one new node is added and at most one existing node is split into two nodes, the number of nodes in the tree is always less than twice the number of suggestions.
The character sequence of a node is not stored explicitly at the node, but is read (up to a stored end index) from the first suggestion in the suggestion list of the node. This first suggestion is stored at the node itself while the other suggestions in the list, if existing, are stored in an array.
Searching for the suggestion list for a prefix of length p in a tree with n suggestions requires at most log2(n) + p character comparisons. Roughly speaking, each comparison either consumes one character of the prefix or cuts the search space in half.
| Nested Class Summary | |
|---|---|
static interface |
SuggestTree.SuggestionList
A list of autocomplete suggestions. |
| Constructor Summary | |
|---|---|
SuggestTree(int k,
java.util.Comparator<V> comparator)
Creates a tree that returns the top k autocomplete suggestions
according to the specified comparator. |
|
| Method Summary | |
|---|---|
void |
build(java.util.Map<java.lang.String,V> map)
Builds or rebuilds this tree from the specified map of suggestion strings and associated rank values. |
SuggestTree.SuggestionList |
getBestSuggestions(java.lang.String prefix)
Returns a rank-ordered list of the top k suggestions in this tree that start with the specified prefix. |
int[] |
size()
Returns the number of nodes in this tree, the number of arrays in this tree, and the total length of the arrays. |
| Methods inherited from class java.lang.Object |
|---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
| Constructor Detail |
|---|
public SuggestTree(int k,
java.util.Comparator<V> comparator)
k autocomplete suggestions
according to the specified comparator. The best-ranking suggestion is the
one with the least rank value with respect to the ordering
imposed by the comparator.
k - the maximum number of autocomplete suggestions that will be
returned for a given prefixcomparator - the comparator that will be used by the build
method to compare the rank values of the suggestions
java.lang.IllegalArgumentException - if k is less than 1 or the
specified comparator is null| Method Detail |
|---|
public int[] size()
public SuggestTree.SuggestionList getBestSuggestions(java.lang.String prefix)
prefix - the prefix for which to return the best-ranking
autocomplete suggestions
java.lang.IllegalArgumentException - if the specified prefix is an empty
string
java.lang.NullPointerException - if the specified prefix is nullpublic void build(java.util.Map<java.lang.String,V> map)
map - the map of suggestion strings and associated rank values
java.lang.ClassCastException - if any of the suggestions are not a string or
the type of a rank value is incompatible with the tree's comparator
java.lang.IllegalArgumentException - if any of the suggestions are an empty
string
java.lang.NullPointerException - if the map or any of the suggestions are
null, or if any of the rank values are null and the
tree's comparator does not permit null values