Get SuggestTree at SourceForge.net. Fast, secure and Free Open Source software downloads
Source Code

net.sourceforge.suggesttree
Class SuggestTree

java.lang.Object
  extended by 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 log2n, 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(log2k + 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.


Nested Class Summary
 class SuggestTree.Iterator
          An iterator over the suggestions in the tree.
static class SuggestTree.Node
          A rank-ordered list of autocomplete suggestions.
 
Constructor Summary
SuggestTree(int k)
          Creates a tree that returns the top k highest weighted autocomplete suggestions for a given prefix.
 
Method Summary
 void clear()
          Removes all of the suggestions from this tree.
 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.
 SuggestTree.Iterator iterator()
          Returns an iterator over the suggestions in this tree.
 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.
 void remove(java.lang.String suggestion)
          Removes the specified suggestion from this tree, if present.
 int size()
          Returns the number of suggestions in this tree.
 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.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

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
Method Detail

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.