Class TSTAutocomplete

Ternary Search Trie implementation.

Inheritance

System.Object

TSTAutocomplete

Namespace: Lucene.Net.Search.Suggest.Tst

Assembly: Lucene.Net.Suggest.dll

Syntax

public class TSTAutocomplete : object

Methods

BalancedTree(Object[], Object[], Int32, Int32, TernaryTreeNode)

Inserting keys in TST in the order middle,small,big (lexicographic measure) recursively creates a balanced tree which reduces insertion and search times significantly.

Declaration

public virtual void BalancedTree(object[] tokens, object[] vals, int lo, int hi, TernaryTreeNode root)

Parameters

Type	Name	Description
System.Object[]	tokens	Sorted list of keys to be inserted in TST.
System.Object[]	vals
System.Int32	lo	stores the lower index of current list.
System.Int32	hi	stores the higher index of current list.
TernaryTreeNode	root	a reference object to root of TST.

Insert(TernaryTreeNode, String, Object, Int32)

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.

Declaration

public virtual TernaryTreeNode Insert(TernaryTreeNode currentNode, string s, object val, int x)

Parameters

Type	Name	Description
TernaryTreeNode	currentNode	a reference node where the insertion will take currently.
System.String	s	key to be inserted in TST.
System.Object	val
System.Int32	x	index of character in key to be inserted currently.

Returns

Type	Description
TernaryTreeNode	The new reference to root node of TST

PrefixCompletion(TernaryTreeNode, String, Int32)

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.

Declaration

public virtual IList<TernaryTreeNode> PrefixCompletion(TernaryTreeNode root, string s, int x)

Parameters

Type	Name	Description
TernaryTreeNode	root	a reference to root node of TST.
System.String	s	prefix query to be auto-completed.
System.Int32	x	index of current character to be searched while traversing through the prefix in TST.

Returns

Type	Description
IList<TernaryTreeNode>	suggest list of auto-completed keys for the given prefix query.

See Also

TernaryTreeNode