org.apache.lucene.search.suggest.tst
Class TSTAutocomplete
java.lang.Object
org.apache.lucene.search.suggest.tst.TSTAutocomplete
public class TSTAutocomplete
- extends Object
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 |
TSTAutocomplete
public TSTAutocomplete()
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.