Class 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 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