org.passay.dictionary

Class TernaryTreeDictionary

java.lang.Object

org.passay.dictionary.TernaryTreeDictionary

All Implemented Interfaces:

Dictionary

public class TernaryTreeDictionary
extends Object
implements Dictionary

Provides fast searching for dictionary words using a ternary tree. The entire dictionary is stored in memory, so heap size may need to be adjusted to accommodate large dictionaries. It is highly recommended that sorted word lists be inserted using their median. This helps to produce a balanced ternary tree which improves search time. This class inherits the lower case property of the supplied word list.

Author:

Middleware Services

Field Summary

Fields

Modifier and Type	Field and Description
protected TernaryTree	tree Ternary tree used for searching.

Constructor Summary

Constructors

Constructor and Description
TernaryTreeDictionary(TernaryTree tt) Creates a dictionary that uses the supplied ternary tree for dictionary searches.
TernaryTreeDictionary(WordList wordList) Creates a new balanced tree dictionary from the supplied WordList.
TernaryTreeDictionary(WordList wordList, boolean useMedian) Creates a new dictionary instance from the given WordList.

Method Summary

Modifier and Type	Method and Description
TernaryTree	getTernaryTree() Returns the underlying ternary tree used by this dictionary.
static void	main(String[] args) Provides command line access to a ternary tree dictionary.
String[]	nearSearch(String word, int distance) Returns an array of strings which are near to the supplied word by the supplied distance.
String[]	partialSearch(String word) Returns an array of strings which partially match the supplied word.
boolean	search(String word) Returns whether the supplied word exists in the dictionary.
long	size() Returns the number of words in this dictionary

Methods inherited from class java.lang.Object

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

Field Detail

tree

protected final TernaryTree tree

Ternary tree used for searching.

Constructor Detail

TernaryTreeDictionary

public TernaryTreeDictionary(WordList wordList)

Creates a new balanced tree dictionary from the supplied WordList. This constructor creates a balanced tree by inserting from the median of the word list, which may require additional work depending on the WordList implementation.

NOTE While using an unsorted word list produces correct results, it may dramatically reduce search efficiency. Using a sorted word list is recommended.

Parameters:

wordList - list of words used to back the dictionary. This list is used exclusively to initialize the internal TernaryTree used by the dictionary, and may be safely discarded after dictionary creation.

TernaryTreeDictionary

public TernaryTreeDictionary(WordList wordList,
                             boolean useMedian)

Creates a new dictionary instance from the given WordList.

Parameters:

wordList - list of words used to back the dictionary. This list is used exclusively to initialize the internal TernaryTree used by the dictionary, and may be safely discarded after dictionary creation.

NOTE While using an unsorted word list produces correct results, it may dramatically reduce search efficiency. Using a sorted word list is recommended.

useMedian - set to true to force creation of a balanced tree by inserting into the tree from the median of the WordList outward. Depending on the word list implementation, this may require additional work to access the median element on each insert.

TernaryTreeDictionary

public TernaryTreeDictionary(TernaryTree tt)

Creates a dictionary that uses the supplied ternary tree for dictionary searches.

Parameters:

tt - ternary tree used to back dictionary.

Method Detail

size

public long size()

Description copied from interface: Dictionary

Returns the number of words in this dictionary

Specified by:

size in interface Dictionary

Returns:

total number of words to search

search

public boolean search(String word)

Description copied from interface: Dictionary

Returns whether the supplied word exists in the dictionary.

Specified by:

search in interface Dictionary

Parameters:

word - to search for

Returns:

whether word was found

partialSearch

public String[] partialSearch(String word)

Returns an array of strings which partially match the supplied word. This search is case sensitive by default. See TernaryTree.partialSearch(java.lang.String).

Parameters:

word - to search for

Returns:

array of matching words

nearSearch

public String[] nearSearch(String word,
                           int distance)

Returns an array of strings which are near to the supplied word by the supplied distance. This search is case sensitive by default. See TernaryTree.nearSearch(java.lang.String, int).

Parameters:

word - to search for

distance - for valid match

Returns:

array of matching words

getTernaryTree

public TernaryTree getTernaryTree()

Returns the underlying ternary tree used by this dictionary.

Returns:

ternary tree

main

public static void main(String[] args)
                 throws Exception

Provides command line access to a ternary tree dictionary.

Parameters:

args - command line arguments

Throws:

Exception - if an error occurs