prefuse.data.search
Class Trie

java.lang.Object
  prefuse.data.search.Trie

public class Trie
extends java.lang.Object

A trie data structure for fast-lookup of words based on their prefixes. The name "Trie" is a play on the words "tree" and "retrieval". This class builds a tree structure representing a set of words by their prefixes. It is useful for performing prefix-based searches over large amounts of text in an efficient manner.

Version:

1.0

Author:

jeffrey heer

See Also:

PrefixSearchTupleSet

Nested Class Summary

class	Trie.TrieBranch A TrieNode implementation representing a branch in the tree.
class	Trie.TrieIterator An iterator for traversing a subtree of the Trie.
class	Trie.TrieLeaf A TrieNode implementation representing a leaf in the tree.
class	Trie.TrieNode Base class for nodes in the trie structure.

Constructor Summary

Trie(boolean caseSensitive)
Create a new Trie with the specified case-sensitivity.

Method Summary

void	addString(java.lang.String word, Tuple t) Add a new word to the trie, associated with the given Tuple.
Trie.TrieNode	find(java.lang.String word) Look up the given word in this Trie.
boolean	isCaseSensitive() Indicates if this Trie's index takes the case of letters into account.
void	removeString(java.lang.String word, Tuple t) Remove a word/Tuple pair from the trie.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

Trie

public Trie(boolean caseSensitive)

Create a new Trie with the specified case-sensitivity.

Parameters:

caseSensitive - true if the index should be case sensitive for indexed words, false otherwise.

Method Detail

isCaseSensitive

public boolean isCaseSensitive()

Indicates if this Trie's index takes the case of letters into account.

Returns:

true if the index is case-sensitive, false otherwise

addString

public void addString(java.lang.String word,
                      Tuple t)

Add a new word to the trie, associated with the given Tuple.

Parameters:

word - the word to add to the Trie

t - the Tuple associated with the word

removeString

public void removeString(java.lang.String word,
                         Tuple t)

Remove a word/Tuple pair from the trie.

Parameters:

word - the word to remove

t - the associate Tuple to remove

find

public Trie.TrieNode find(java.lang.String word)

Look up the given word in this Trie. If a match is found, a TrieNode is returned. This node is the root of a subtree containing all the matches to the query.

Parameters:

word - the word to lookup

Returns:

the TrieNode root of the subtree containing all matches. A null value is returned if no match is found.