net.sourceforge.suggesttree
Class SuggestTree

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

public class SuggestTree
extends java.lang.Object

A data structure for rank-sensitive autocomplete. It provides O(log n) time for the basic operations such as searching for the top k highest weighted autocomplete suggestions for a given prefix, modifying the weight of a suggestion, inserting a new suggestion, or removing a suggestion. The structure is based on a compressed ternary search tree of the suggestions, where nodes (prefixes) with the same completions are merged into one node, and where each node that corresponds to a suggestion stores the weight of the suggestion and a reference to the suggestion string. In addition, each node in the tree holds a rank-ordered array of references to the nodes of the top k suggestions that start with the corresponding prefix.

The space consumption of the tree is determined by the number of nodes in the tree and the average length of the array held by each node (the length of the character sequence of a node does not affect space consumption because only the first character is stored explicitly; the other characters are read from the corresponding suggestion or a suggestion that is referenced instead). 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. A tree with n suggestions has thus less than 2n nodes. In the worst case, when the tree has 2n - 1 nodes, each internal node of the corresponding trie (prefix tree) has exactly two child nodes. If all leaf nodes of the trie are at the same depth, i.e. if the height of the trie is log₂n, the tree has n nodes with an array of length 1, n/2 nodes with an array of length 2, n/4 nodes with an array of length 4, and so on until the maximum length of k is reached. Assuming k is a power of two, this gives a total array length of n + 2(n/2) + 4(n/4) + ... + k(n/k) + k(n/k - 1), which is approximately n(log₂k + 2).

Ternary search trees are robust. Even in the worst case, when the suggestions are inserted into the tree in lexicographic order, performance is usually only slightly degraded. The reason for this is that not the entire tree degenerates into a linked list, only each of the small binary search trees within the ternary search tree does. However, for best performance, the suggestions should be inserted or removed in a random order. This usually produces a balanced tree where the search space is cut more or less in half each time the search goes left or right.

This implementation is not synchronized. If multiple threads access a tree concurrently, and at least one of the threads modifies the tree, it must be synchronized externally. This is typically accomplished by synchronizing on some object that naturally encapsulates the tree.

SuggestTree

public SuggestTree(int k)

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

Throws:

java.lang.IllegalArgumentException - if the specified k value is less than 1

size

public int size()

Returns the number of suggestions in this tree.

getSuggestions

public SuggestTree.Node getSuggestions(java.lang.String prefix)

Returns a list of the highest weighted suggestions in this tree that start with the specified prefix, or returns null if the tree contains no suggestion with the prefix.

Throws:

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

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

weightOf

public int weightOf(java.lang.String suggestion)

Returns the weight of the specified suggestion in this tree, or -1 if the tree does not contain the suggestion.

Throws:

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

put

public void put(java.lang.String suggestion,
                int weight)

Inserts the specified suggestion with the specified weight into this tree, or assigns the specified new weight to the suggestion if it is already present.

Throws:

java.lang.IllegalArgumentException - if the specified suggestion is an empty string or the specified weight is negative

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

remove

public void remove(java.lang.String suggestion)

Removes the specified suggestion from this tree, if present. The algorithm is symmetric, preserving the balance of the tree.

Throws:

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

clear

public void clear()

Removes all of the suggestions from this tree.

iterator

public SuggestTree.Iterator iterator()

Returns an iterator over the suggestions in this tree.