edu.northwestern.at.utils

Class TernaryTrie

java.lang.Object

edu.northwestern.at.utils.TernaryTrie

All Implemented Interfaces:

TaggedStrings

public class TernaryTrie
extends java.lang.Object
implements TaggedStrings

TernaryTrie is an implementation of a ternary tree. Methods are provided for inserting strings and searching for strings. The algorithms in this class are all recursive, and have not been optimized for any particular purpose. Data which is inserted is not sorted before insertion, however data can be inserted beginning with the median of the supplied data.

Version:

$Revision: 2134 $ $Date: 2005-03-28 14:48:04 -0500 (Mon, 28 Mar 2005) $

Author:

Daniel Fisher

Field Summary

Fields

Modifier and Type	Field and Description
protected int	maxKeyLength Maximum key length.
protected int	nodeCount Count of nodes in tree.
protected TernaryTrieNode	root root node of the ternary tree

Constructor Summary

Constructors

Constructor and Description
TernaryTrie() Construct empty ternary trie.
TernaryTrie(java.util.List<java.lang.String> stringsList) Construct a ternary trie from values in a list.
TernaryTrie(java.util.Map<java.lang.String,java.lang.String> stringsMap, boolean addValuesAsKeys) Construct a ternary trie from keys and values in a map.
TernaryTrie(java.util.Set<java.lang.String> stringsSet) Construct a ternary trie from values in a set.
TernaryTrie(TaggedStrings stringsList, boolean addValuesAsKeys) Construct a ternary trie from values in a tagged strings list.

Method Summary

Methods

Modifier and Type	Method and Description
void	addCollection(java.util.Collection<java.lang.String> collection) Add words from a collection.
boolean	containsKey(java.lang.String word) Check if trie contains a specified key.
boolean	containsString(java.lang.String string) See if specified string exists.
protected TernaryTrieNode	findNode(TernaryTrieNode node, java.lang.String word, int index)
java.lang.Object	get(java.lang.String word) Get associated value for word.
java.util.Set<java.lang.String>	getAllStrings() Get set of all unique string values.
java.util.Set<java.lang.String>	getAllTags() Get set of all unique tag values as strings.
int	getStringCount() Get number of strings.
java.lang.String	getTag(java.lang.String string) Get the tag value associated with a string.
java.util.List<java.lang.String>	getWords() This will return an array of all the words in this TernaryTrie.
protected TernaryTrieNode	insertNode(TernaryTrieNode node, java.lang.String word, int index, java.lang.Object value) This will recursively insert a word into the TernaryTrie one node at a time beginning at the supplied node.
java.util.List<java.lang.String>	nearSearch(java.lang.String word, int distance) This will return an array of strings which are near to the supplied word by the supplied distance.
protected java.util.List<java.lang.String>	nearSearchNode(TernaryTrieNode node, int distance, java.util.List<java.lang.String> matches, java.lang.String match, java.lang.String word, int index) This will recursively search for a near match word in the TernaryTrie one node at a time beginning at the supplied node.
java.util.List<java.lang.String>	partialSearch(java.lang.String word) This will return an array of strings which partially match the supplied word.
protected java.util.List<java.lang.String>	partialSearchNode(TernaryTrieNode node, java.util.List<java.lang.String> matches, java.lang.String match, java.lang.String word, int index) This will recursively search for a partial word in the TernaryTrie one node at a time beginning at the supplied node.
java.util.List<java.lang.String>	prefixSearch(java.lang.String prefix)
protected java.util.List<java.lang.String>	prefixSearchNode(TernaryTrieNode node, java.util.List<java.lang.String> matches, java.lang.String match, java.lang.String prefix, java.lang.String prefixPattern, int index)
java.lang.Object	put(java.lang.String word, java.lang.Object value) Add word and associated value to trie.
void	putTag(java.lang.String string, java.lang.String tag) Set the tag value associated with a string.
protected boolean	searchNode(TernaryTrieNode node, java.lang.String word, int index) This will recursively search for a word in the TernaryTrie one node at a time beginning at the supplied node.
int	size() Return size of trie (# of terminal nodes)
protected java.util.List<java.lang.String>	traverseNode(TernaryTrieNode node, java.lang.String s, java.util.List<java.lang.String> words) This will recursively traverse every node in the TernaryTrie one node at a time beginning at the supplied node.

Methods inherited from class java.lang.Object

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

Field Detail

root

protected TernaryTrieNode root

root node of the ternary tree

nodeCount

protected int nodeCount

Count of nodes in tree.

maxKeyLength

protected int maxKeyLength

Maximum key length.

Constructor Detail

TernaryTrie

public TernaryTrie()

Construct empty ternary trie.

TernaryTrie

public TernaryTrie(java.util.Map<java.lang.String,java.lang.String> stringsMap,
           boolean addValuesAsKeys)

Construct a ternary trie from keys and values in a map.

Parameters:

stringsMap - The map whose keys and values are to be added to the trie.

addValuesAsKeys - True to add each value as a key as well.

TernaryTrie

public TernaryTrie(java.util.Set<java.lang.String> stringsSet)

Construct a ternary trie from values in a set.

Parameters:

stringsSet - The set whose values are to be added to the trie.

TernaryTrie

public TernaryTrie(java.util.List<java.lang.String> stringsList)

Construct a ternary trie from values in a list.

Parameters:

stringsList - The list whose values are to be added to the trie.

TernaryTrie

public TernaryTrie(TaggedStrings stringsList,
           boolean addValuesAsKeys)

Construct a ternary trie from values in a tagged strings list.

Parameters:

stringsList - The tagged strings list whose values are to be added to the trie.

addValuesAsKeys - True to add each value as a key as well.

Method Detail

addCollection

public void addCollection(java.util.Collection<java.lang.String> collection)

Add words from a collection.

Parameters:

collection - Collection whose values are to be inserted into trie.

put

public java.lang.Object put(java.lang.String word,
                   java.lang.Object value)

Add word and associated value to trie.

Parameters:

word - String to insert.

value - Object value.

Returns:

Previous value, if any, for word.

get

public java.lang.Object get(java.lang.String word)

Get associated value for word.

Parameters:

word - String whose associated value we want.

Returns:

Associated value.

containsKey

public boolean containsKey(java.lang.String word)

Check if trie contains a specified key.

Parameters:

word - The key to look up.

Returns:

true if trie contains specified key.

partialSearch

public java.util.List<java.lang.String> partialSearch(java.lang.String word)

This will return an array of strings which partially match the supplied word. word should be of the format '.e.e.e' Where the '.' character represents any valid character. Possible results from this query include: Helene, delete, or severe Note that no substring matching occurs, results only include strings of the same length. If the supplied word does not contain the '.' character, then a regular search is preformed.

Parameters:

word - String to search for

Returns:

String[] - of matching words

prefixSearch

public java.util.List<java.lang.String> prefixSearch(java.lang.String prefix)

prefixSearchNode

protected java.util.List<java.lang.String> prefixSearchNode(TernaryTrieNode node,
                                                java.util.List<java.lang.String> matches,
                                                java.lang.String match,
                                                java.lang.String prefix,
                                                java.lang.String prefixPattern,
                                                int index)

nearSearch

public java.util.List<java.lang.String> nearSearch(java.lang.String word,
                                          int distance)

This will return an array of strings which are near to the supplied word by the supplied distance. For the query nearSearch("fisher", 2): Possible results include: cipher, either, fishery, kosher, sister. If the supplied distance is not > 0, then a regular search is preformed.

Parameters:

word - String to search for

distance - int for valid match

Returns:

String[] - of matching words

getWords

public java.util.List<java.lang.String> getWords()

This will return an array of all the words in this TernaryTrie. This is a very expensive operation, every node in the tree is traversed.

Returns:

String[] - of words

insertNode

protected TernaryTrieNode insertNode(TernaryTrieNode node,
                         java.lang.String word,
                         int index,
                         java.lang.Object value)

This will recursively insert a word into the TernaryTrie one node at a time beginning at the supplied node.

Parameters:

node - TernaryTrieNode to put character in

word - String to be inserted

index - int of character in word

Returns:

TernaryTrieNode - to insert

searchNode

protected boolean searchNode(TernaryTrieNode node,
                 java.lang.String word,
                 int index)

This will recursively search for a word in the TernaryTrie one node at a time beginning at the supplied node.

Parameters:

node - TernaryTrieNode to search in

word - String to search for

index - int of character in word

Returns:

boolean - whether or not word was found

findNode

protected TernaryTrieNode findNode(TernaryTrieNode node,
                       java.lang.String word,
                       int index)

partialSearchNode

protected java.util.List<java.lang.String> partialSearchNode(TernaryTrieNode node,
                                                 java.util.List<java.lang.String> matches,
                                                 java.lang.String match,
                                                 java.lang.String word,
                                                 int index)

This will recursively search for a partial word in the TernaryTrie one node at a time beginning at the supplied node.

Parameters:

node - TernaryTrieNode to search in

matches - ArrayList of partial matches

match - String the current word being examined

word - String to search for

index - int of character in word

Returns:

ArrayList - of matches

nearSearchNode

protected java.util.List<java.lang.String> nearSearchNode(TernaryTrieNode node,
                                              int distance,
                                              java.util.List<java.lang.String> matches,
                                              java.lang.String match,
                                              java.lang.String word,
                                              int index)

This will recursively search for a near match word in the TernaryTrie one node at a time beginning at the supplied node.

Parameters:

node - TernaryTrieNode to search in

distance - int of a valid match, must be > 0

matches - ArrayList of near matches

match - String the current word being examined

word - String to search for

index - int of character in word

Returns:

ArrayList - of matches

traverseNode

protected java.util.List<java.lang.String> traverseNode(TernaryTrieNode node,
                                            java.lang.String s,
                                            java.util.List<java.lang.String> words)

This will recursively traverse every node in the TernaryTrie one node at a time beginning at the supplied node. The result is a string representing every word, which is delimited by the LINE_SEPARATOR character.

Parameters:

node - TernaryTrieNode to begin traversing

s - String of words found at the supplied node

words - ArrayList which will be returned (recursive function)

Returns:

String - containing all words from the supplied node

size

public int size()

Return size of trie (# of terminal nodes)

Returns:

Number of terminal nodes (nodes with data values).

containsString

public boolean containsString(java.lang.String string)

See if specified string exists.

Specified by:

containsString in interface TaggedStrings

Parameters:

string - The string.

Returns:

True if specified string exists.

getTag

public java.lang.String getTag(java.lang.String string)

Get the tag value associated with a string.

Specified by:

getTag in interface TaggedStrings

Parameters:

string - The string.

Returns:

The tag value associated with the string. May be null.

putTag

public void putTag(java.lang.String string,
          java.lang.String tag)

Set the tag value associated with a string.

Specified by:

putTag in interface TaggedStrings

Parameters:

string - The string.

tag - The tag.

getStringCount

public int getStringCount()

Get number of strings.

Specified by:

getStringCount in interface TaggedStrings

Returns:

Number of strings.

getAllStrings

public java.util.Set<java.lang.String> getAllStrings()

Get set of all unique string values.

Specified by:

getAllStrings in interface TaggedStrings

Returns:

Set of all unique string values.

getAllTags

public java.util.Set<java.lang.String> getAllTags()

Get set of all unique tag values as strings.

Specified by:

getAllTags in interface TaggedStrings

Returns:

Set of all unique string tag values.