Package org.apache.lucene.search.suggest.tst

Class TSTAutocomplete

  • public class TSTAutocomplete
extends java.lang.Object
    Ternary Search Trie implementation.
    See Also:
    TernaryTreeNode

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void balancedTree​(java.lang.Object[] tokens, java.lang.Object[] vals, int lo, int hi, TernaryTreeNode root)
      Inserting keys in TST in the order middle,small,big (lexicographic measure) recursively creates a balanced tree which reduces insertion and search times significantly.
      TernaryTreeNode insert​(TernaryTreeNode currentNode, java.lang.CharSequence s, java.lang.Object val, int x)
      Inserts a key in TST creating a series of Binary Search Trees at each node.
      java.util.ArrayList<TernaryTreeNode> prefixCompletion​(TernaryTreeNode root, java.lang.CharSequence s, int x)
      Auto-completes a given prefix query using Depth-First Search with the end of prefix as source node each time finding a new leaf to get a complete key to be added in the suggest list.

      • Methods inherited from class java.lang.Object

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

    • Method Detail

      • balancedTree

        public void balancedTree​(java.lang.Object[] tokens,
                         java.lang.Object[] vals,
                         int lo,
                         int hi,
                         TernaryTreeNode root)
        Inserting keys in TST in the order middle,small,big (lexicographic measure) recursively creates a balanced tree which reduces insertion and search times significantly.
        Parameters:
        tokens - Sorted list of keys to be inserted in TST.
        lo - stores the lower index of current list.
        hi - stores the higher index of current list.
        root - a reference object to root of TST.

      • insert

        public TernaryTreeNode insert​(TernaryTreeNode currentNode,
                              java.lang.CharSequence s,
                              java.lang.Object val,
                              int x)
        Inserts a key in TST creating a series of Binary Search Trees at each node. The key is actually stored across the eqKid of each node in a successive manner.
        Parameters:
        currentNode - a reference node where the insertion will take currently.
        s - key to be inserted in TST.
        x - index of character in key to be inserted currently.
        Returns:
        currentNode The new reference to root node of TST

      • prefixCompletion

        public java.util.ArrayList<TernaryTreeNode> prefixCompletion​(TernaryTreeNode root,
                                                             java.lang.CharSequence s,
                                                             int x)
        Auto-completes a given prefix query using Depth-First Search with the end of prefix as source node each time finding a new leaf to get a complete key to be added in the suggest list.
        Parameters:
        root - a reference to root node of TST.
        s - prefix query to be auto-completed.
        x - index of current character to be searched while traversing through the prefix in TST.
        Returns:
        suggest list of auto-completed keys for the given prefix query.