Download Source Code

net.sourceforge.suggesttree
Class SuggestTree

java.lang.Object
  net.sourceforge.suggesttree.SuggestTree

public class SuggestTree
extends java.lang.Object

An efficient index structure for rank-ordered autocomplete suggestions. For each prefix, it provides a rank-ordered list of the top k suggestions that start with that prefix.

The structure is based on a compressed ternary search tree of the suggestions, where each node holds a rank-ordered array of references to the top k suggestions that start with the prefix or prefixes represented by the node. Unlike in a standard ternary search tree, the characters of the nodes are not stored explicitly at the nodes, but are read from the referenced suggestions. For this, each node simply stores the length of the longest prefix represented by it.

Searching for the suggestion list for a prefix of length m in a tree with n suggestions requires at most m + log₂(n) character comparisons. Roughly speaking, each comparison either consumes one character of the prefix or cuts the search space in half.

The number of nodes in the tree is less than twice the number of suggestions. For each suggestion that is inserted into the tree, at most one new node is added and at most one existing node is split into two nodes. And since most of the nodes are at the bottom of the tree (if the root is at the top), the average length of the suggestion lists in the tree is very small.

SuggestTree

public SuggestTree(int k)

Creates a tree that returns the top k autocomplete suggestions for a given prefix.

Parameters:

k - maximum length of the suggestion lists to return

Throws:

java.lang.IllegalArgumentException - if k is less than 1

build

public void build(java.util.List<java.lang.String> suggestions)

Builds or rebuilds this tree with the specified rank-ordered suggestions. A concurrent call to getBestSuggestions will return null.

Parameters:

suggestions - a rank-ordered list of all suggestions that are to be contained in this tree

Throws:

java.lang.RuntimeException - if the specified suggestion list is null or contains a null element or an empty string

getBestSuggestions

public SuggestTree.List getBestSuggestions(java.lang.String prefix)

Returns a rank-ordered list of the best ranking suggestions with the specified prefix, or null if this tree contains no suggestion that starts with the prefix.

Parameters:

prefix - the prefix for which a list of autocomplete suggestions is to be returned

Returns:

a rank-ordered list of the best ranking suggestions with the specified prefix, or null if this tree contains no suggestion that starts with the prefix

Throws:

java.lang.RuntimeException - if the specified prefix is null or an empty string

Download Source Code