net.sourceforge.suggesttree

Class SuggestTree

java.lang.Object

net.sourceforge.suggesttree.SuggestTree

public class SuggestTree
extends java.lang.Object

An autocomplete data structure that enables you to quickly look up the top k terms with a given prefix in a set of weighted terms. The structure is based on a compressed trie of the terms (implemented as a randomized ternary search tree) in which each node holds a weight-ordered list of the k highest-weighted terms in its subtree.

Note that this implementation is not synchronized. If multiple threads access a Suggest Tree concurrently, and at least one of the threads modifies the tree, it must be synchronized externally.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	SuggestTree.Entry A weighted term.
class	SuggestTree.Iterator An iterator over the terms in the tree.
static class	SuggestTree.Node A list of autocomplete suggestions, ordered from highest weight to lowest weight.

Constructor Summary

Constructors

Constructor and Description
SuggestTree(int k) Creates a Suggest Tree with the specified k-value.

Method Summary

Methods

Modifier and Type	Method and Description
SuggestTree.Node	getAutocompleteSuggestions(java.lang.String prefix) Returns the k highest-weighted terms in the tree that start with the specified prefix, or null if there is no such term.
SuggestTree.Entry	getEntry(java.lang.String term) Returns the tree entry for the specified term, or null if there is no such entry.
SuggestTree.Iterator	iterator() Returns an iterator over the terms in the tree.
void	put(java.lang.String term, int weight) Inserts the specified term with the specified weight into the tree, or reweights the term if it is already present.
void	remove(java.lang.String term) Removes the specified term from the tree.
int	size() Returns the number of terms in the tree.

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 Suggest Tree with the specified k-value.

Parameters:

k - the maximum number of autocomplete suggestions to return for a given prefix

Throws:

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

Method Detail

getAutocompleteSuggestions

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

Returns the k highest-weighted terms in the tree that start with the specified prefix, or null if there is no such term.

Parameters:

prefix - the prefix for which to return autocomplete suggestions

Returns:

the k highest-weighted terms in the tree that start with the specified prefix, or null if there is no such term

Throws:

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

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

getEntry

public SuggestTree.Entry getEntry(java.lang.String term)

Returns the tree entry for the specified term, or null if there is no such entry.

Parameters:

term - the term for which to return the corresponding tree entry

Returns:

the tree entry for the specified term, or null if there is no such entry

Throws:

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

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

iterator

public SuggestTree.Iterator iterator()

Returns an iterator over the terms in the tree.

Returns:

an iterator over the terms in the tree

size

public int size()

Returns the number of terms in the tree.

Returns:

the number of terms in the tree

put

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

Inserts the specified term with the specified weight into the tree, or reweights the term if it is already present.

Parameters:

term - the term to be inserted or reweighted

weight - the weight to be assigned to the term

Throws:

java.lang.IllegalArgumentException - if the specified term is an empty string or much too long (longer than 32767 characters)

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

remove

public void remove(java.lang.String term)

Removes the specified term from the tree.

Parameters:

term - the term to be removed

Throws:

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

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