Class TSTAutocomplete
java.lang.Object
org.apache.lucene.search.suggest.tst.TSTAutocomplete
Ternary Search Trie implementation.
- See Also:
-
Method Summary
Modifier and TypeMethodDescriptionvoid
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.insert
(TernaryTreeNode currentNode, CharSequence s, Object val, int x) Inserts a key in TST creating a series of Binary Search Trees at each node.prefixCompletion
(TernaryTreeNode root, 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.
-
Method Details
-
balancedTree
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
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
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.
-