org.apache.lucene.search.suggest.tst
Class TSTAutocomplete

java.lang.Object
  extended by org.apache.lucene.search.suggest.tst.TSTAutocomplete

public class TSTAutocomplete
extends Object


Constructor Summary
TSTAutocomplete()
           
 
Method Summary
 void balancedTree(Object[] tokens, 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, String s, Object val, int x)
          Inserts a key in TST creating a series of Binary Search Trees at each node.
 ArrayList<TernaryTreeNode> prefixCompletion(TernaryTreeNode root, String 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
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

TSTAutocomplete

public TSTAutocomplete()
Method Detail

balancedTree

public void balancedTree(Object[] tokens,
                         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,
                              String s,
                              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 ArrayList<TernaryTreeNode> prefixCompletion(TernaryTreeNode root,
                                                   String 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.


Copyright © 2000-2011 Apache Software Foundation. All Rights Reserved.