Source File

net.sourceforge.suggesttree
Class SuggestTree<V>

java.lang.Object
  net.sourceforge.suggesttree.SuggestTree<V>

Type Parameters:

V - the type of rank values by which the suggestions are ordered

public class SuggestTree<V>
extends java.lang.Object

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 log₂(n) + p character comparisons. Roughly speaking, each comparison either consumes one character of the prefix or cuts the search space in half.

SuggestTree

public SuggestTree(int k,
                   java.util.Comparator<V> comparator)

Creates a tree that returns the top 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.

Parameters:

k - the maximum number of autocomplete suggestions that will be returned for a given prefix

comparator - the comparator that will be used by the build method to compare the rank values of the suggestions

Throws:

java.lang.IllegalArgumentException - if k is less than 1 or the specified comparator is null

size

public int[] size()

Returns the number of nodes in this tree, the number of arrays in this tree, and the total length of the arrays.

Returns:

the number of nodes in this tree, the number of arrays in this tree, and the total length of the arrays

getBestSuggestions

public 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. If called while the tree is rebuilt, an empty list is returned.

Parameters:

prefix - the prefix for which to return the best-ranking autocomplete suggestions

Returns:

a rank-ordered list of the top k suggestions in this tree that start with the specified prefix

Throws:

java.lang.IllegalArgumentException - if the specified prefix is an empty string

java.lang.NullPointerException - if the specified prefix is null

build

public 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. If the map is modified while this operation is in progress, the behavior of the tree is undefined.

Parameters:

map - the map of suggestion strings and associated rank values

Throws:

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

Source File