Package 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 Description protected TernaryTree
tree
Ternary tree used for searching.
-
Constructor Summary
Constructors Constructor 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 suppliedWordList
.TernaryTreeDictionary(WordList wordList, boolean useMedian)
Creates a new dictionary instance from the givenWordList
.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method 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
-
-
-
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 suppliedWordList
. This constructor creates a balanced tree by inserting from the median of the word list, which may require additional work depending on theWordList
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 internalTernaryTree
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 givenWordList
.- Parameters:
wordList
- list of words used to back the dictionary. This list is used exclusively to initialize the internalTernaryTree
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 theWordList
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 interfaceDictionary
- 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 interfaceDictionary
- 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. SeeTernaryTree.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. SeeTernaryTree.nearSearch(java.lang.String, int)
.- Parameters:
word
- to search fordistance
- for valid match- Returns:
- array of matching words
-
getTernaryTree
public TernaryTree getTernaryTree()
Returns the underlying ternary tree used by this dictionary.- Returns:
- ternary tree
-
-