Class JaspellTernarySearchTrie

Implementation of a Ternary Search Trie, a data structure for storing System.Strings that combines the compact size of a binary search tree with the speed of a digital search trie, and is therefore ideal for practical use in sorting and searching data.

This data structure is faster than hashing for many typical search problems, and supports a broader range of useful problems and operations. Ternary searches are faster than hashing and more powerful, too.

The theory of ternary search trees was described at a symposium in 1997 (see "Fast Algorithms for Sorting and Searching Strings," by J.L. Bentley and R. Sedgewick, Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms, January 1997). Algorithms in C, Third Edition, by Robert Sedgewick (Addison-Wesley, 1998) provides yet another view of ternary search trees.

Inheritance

System.Object

JaspellTernarySearchTrie

Inherited Members

System.Object.Equals(System.Object)

System.Object.Equals(System.Object, System.Object)

System.Object.GetHashCode()

System.Object.GetType()

System.Object.MemberwiseClone()

System.Object.ReferenceEquals(System.Object, System.Object)

System.Object.ToString()

Namespace: Lucene.Net.Search.Suggest.Jaspell

Assembly: Lucene.Net.Suggest.dll

Syntax

public class JaspellTernarySearchTrie

Constructors

JaspellTernarySearchTrie()

Constructs an empty Ternary Search Trie.

Declaration

public JaspellTernarySearchTrie()

JaspellTernarySearchTrie(CultureInfo)

Constructs an empty Ternary Search Trie, specifying the System.Globalization.CultureInfo used for lowercasing.

Declaration

public JaspellTernarySearchTrie(CultureInfo culture)

Parameters

Type	Name	Description
System.Globalization.CultureInfo	culture

JaspellTernarySearchTrie(FileInfo)

Constructs a Ternary Search Trie and loads data from a System.IO.FileInfo into the Trie. The file is a normal text document, where each line is of the form word TAB float.

Uses the culture of the current thread to lowercase words before comparing.

Declaration

public JaspellTernarySearchTrie(FileInfo file)

Parameters

Type	Name	Description
System.IO.FileInfo	file	The System.IO.FileInfo with the data to load into the Trie.

Exceptions

Type	Condition
System.IO.IOException	A problem occured while reading the data.

JaspellTernarySearchTrie(FileInfo, Boolean)

Constructs a Ternary Search Trie and loads data from a System.IO.FileInfo into the Trie. The file is a normal text document, where each line is of the form "word TAB float".

Uses the culture of the current thread to lowercase words before comparing.

Declaration

public JaspellTernarySearchTrie(FileInfo file, bool compression)

Parameters

Type	Name	Description
System.IO.FileInfo	file	The System.IO.FileInfo with the data to load into the Trie.
System.Boolean	compression	If true, the file is compressed with the GZIP algorithm, and if false, the file is a normal text document.

Exceptions

Type	Condition
System.IO.IOException	A problem occured while reading the data.

JaspellTernarySearchTrie(FileInfo, Boolean, CultureInfo)

Constructs a Ternary Search Trie and loads data from a System.IO.FileInfo into the Trie. The file is a normal text document, where each line is of the form "word TAB float".

Uses the supplied culture to lowercase words before comparing.

Declaration

public JaspellTernarySearchTrie(FileInfo file, bool compression, CultureInfo culture)

Parameters

Type	Name	Description
System.IO.FileInfo	file	The System.IO.FileInfo with the data to load into the Trie.
System.Boolean	compression	If true, the file is compressed with the GZIP algorithm, and if false, the file is a normal text document.
System.Globalization.CultureInfo	culture	The culture used for lowercasing.

Exceptions

Type	Condition
System.IO.IOException	A problem occured while reading the data.

JaspellTernarySearchTrie(FileInfo, CultureInfo)

Constructs a Ternary Search Trie and loads data from a System.IO.FileInfo into the Trie. The file is a normal text document, where each line is of the form word TAB float.

Uses the supplied culture to lowercase words before comparing.

Declaration

public JaspellTernarySearchTrie(FileInfo file, CultureInfo culture)

Parameters

Type	Name	Description
System.IO.FileInfo	file	The System.IO.FileInfo with the data to load into the Trie.
System.Globalization.CultureInfo	culture	The culture used for lowercasing.

Exceptions

Type	Condition
System.IO.IOException	A problem occured while reading the data.

Properties

MatchAlmostDiff

Sets the number of characters by which words can differ from target word when calling the MatchAlmost(String, Int32) method.

Arguments less than 0 will set the char difference to 0, and arguments greater than 3 will set the char difference to 3.

Declaration

public virtual int MatchAlmostDiff { get; set; }

Property Value

Type	Description
System.Int32

NumReturnValues

Sets the default maximum number of values returned from the MatchPrefix(String, Int32) and MatchAlmost(String, Int32) methods.

The value should be set this to -1 to get an unlimited number of return values. note that the methods mentioned above provide overloaded versions that allow you to specify the maximum number of return values, in which case this value is temporarily overridden.

Declaration

public virtual int NumReturnValues { get; set; }

Property Value

Type	Description
System.Int32

Methods

Get(String)

Retrieve the object indexed by a key.

Declaration

public virtual object Get(string key)

Parameters

Type	Name	Description
System.String	key	A System.String index.

Returns

Type	Description
System.Object	The object retrieved from the Ternary Search Trie.

GetAndIncrement(String)

Retrieve the indexed by key, increment it by one unit and store the new .

Declaration

public virtual float? GetAndIncrement(string key)

Parameters

Type	Name	Description
System.String	key	A System.String index.

Returns

Type	Description
System.Nullable<System.Single>	The retrieved from the Ternary Search Trie.

GetKey(JaspellTernarySearchTrie.TSTNode)

Returns the key that indexes the node argument.

Declaration

protected virtual string GetKey(JaspellTernarySearchTrie.TSTNode node)

Parameters

Type	Name	Description
JaspellTernarySearchTrie.TSTNode	node	The node whose index is to be calculated.

Returns

Type	Description
System.String	The System.String that indexes the node argument.

GetNode(String)

Returns the node indexed by key, or null if that node doesn't exist. Search begins at root node.

Declaration

public virtual JaspellTernarySearchTrie.TSTNode GetNode(string key)

Parameters

Type	Name	Description
System.String	key	A System.String that indexes the node that is returned.

Returns

Type	Description
JaspellTernarySearchTrie.TSTNode	The node object indexed by key. This object is an instance of an inner class named JaspellTernarySearchTrie.TSTNode.

GetNode(String, JaspellTernarySearchTrie.TSTNode)

Returns the node indexed by key, or null if that node doesn't exist. The search begins at root node.

Declaration

protected virtual JaspellTernarySearchTrie.TSTNode GetNode(string key, JaspellTernarySearchTrie.TSTNode startNode)

Parameters

Type	Name	Description
System.String	key	A System.String that indexes the node that is returned.
JaspellTernarySearchTrie.TSTNode	startNode	The top node defining the subtrie to be searched.

Returns

Type	Description
JaspellTernarySearchTrie.TSTNode	The node object indexed by key. This object is an instance of an inner class named JaspellTernarySearchTrie.TSTNode.

GetOrCreateNode(String)

Returns the node indexed by key, creating that node if it doesn't exist, and creating any required intermediate nodes if they don't exist.

Declaration

protected virtual JaspellTernarySearchTrie.TSTNode GetOrCreateNode(string key)

Parameters

Type	Name	Description
System.String	key	A System.String that indexes the node that is returned.

Returns

Type	Description
JaspellTernarySearchTrie.TSTNode	The node object indexed by key. This object is an instance of an inner class named JaspellTernarySearchTrie.TSTNode.

Exceptions

Type	Condition
System.NullReferenceException	If the key is null.
System.ArgumentException	If the key is an empty System.String.

GetSizeInBytes()

Return an approximate memory usage for this trie.

Declaration

public virtual long GetSizeInBytes()

Returns

Type	Description
System.Int64

MatchAlmost(String)

Returns a System.Collections.Generic.IList<T> of keys that almost match the argument key. Keys returned will have exactly diff characters that do not match the target key, where diff is equal to the last value set to the MatchAlmostDiff property.

If the MatchAlmost(String, Int32) method is called before the MatchAlmostDiff property has been called for the first time, then diff = 0.

Declaration

public virtual IList<string> MatchAlmost(string key)

Parameters

Type	Name	Description
System.String	key	The target key.

Returns

Type	Description
System.Collections.Generic.IList<System.String>	A System.Collections.Generic.IList<T> with the results.

MatchAlmost(String, Int32)

Returns a System.Collections.Generic.IList<T> of keys that almost match the argument key. Keys returned will have exactly diff characters that do not match the target key, where diff is equal to the last value set to the MatchAlmostDiff property.

If the MatchAlmost(String, Int32) method is called before the MatchAlmostDiff property has been called for the first time, then diff = 0.

Declaration

public virtual IList<string> MatchAlmost(string key, int numReturnValues)

Parameters

Type	Name	Description
System.String	key	The target key.
System.Int32	numReturnValues	The maximum number of values returned by this method.

Returns

Type	Description
System.Collections.Generic.IList<System.String>	A System.Collections.Generic.IList<T> with the results

MatchPrefix(String)

Returns an alphabetical System.Collections.Generic.IList<T> of all keys in the trie that begin with a given prefix. Only keys for nodes having non-null data are included in the System.Collections.Generic.IList<T>.

Declaration

public virtual IList<string> MatchPrefix(string prefix)

Parameters

Type	Name	Description
System.String	prefix	Each key returned from this method will begin with the characters in prefix.

Returns

Type	Description
System.Collections.Generic.IList<System.String>	A System.Collections.Generic.IList<T> with the results.

MatchPrefix(String, Int32)

Returns an alphabetical System.Collections.Generic.IList<T> of all keys in the trie that begin with a given prefix. Only keys for nodes having non-null data are included in the System.Collections.Generic.IList<T>.

Declaration

public virtual IList<string> MatchPrefix(string prefix, int numReturnValues)

Parameters

Type	Name	Description
System.String	prefix	Each key returned from this method will begin with the characters in prefix.
System.Int32	numReturnValues	The maximum number of values returned from this method.

Returns

Type	Description
System.Collections.Generic.IList<System.String>	A System.Collections.Generic.IList<T> with the results

NumDataNodes()

Returns the number of nodes in the trie that have non-null data.

Declaration

public virtual int NumDataNodes()

Returns

Type	Description
System.Int32	The number of nodes in the trie that have non-null data.

NumDataNodes(JaspellTernarySearchTrie.TSTNode)

Returns the number of nodes in the subtrie below and including the starting node. The method counts only nodes that have non-null data.

Declaration

protected virtual int NumDataNodes(JaspellTernarySearchTrie.TSTNode startingNode)

Parameters

Type	Name	Description
JaspellTernarySearchTrie.TSTNode	startingNode	The top node of the subtrie. the node that defines the subtrie.

Returns

Type	Description
System.Int32	The total number of nodes in the subtrie.

NumNodes()

Returns the total number of nodes in the trie. The method counts nodes whether or not they have data.

Declaration

public virtual int NumNodes()

Returns

Type	Description
System.Int32	The total number of nodes in the trie.

NumNodes(JaspellTernarySearchTrie.TSTNode)

Returns the total number of nodes in the subtrie below and including the starting Node. The method counts nodes whether or not they have data.

Declaration

protected virtual int NumNodes(JaspellTernarySearchTrie.TSTNode startingNode)

Parameters

Type	Name	Description
JaspellTernarySearchTrie.TSTNode	startingNode	The top node of the subtrie. The node that defines the subtrie.

Returns

Type	Description
System.Int32	The total number of nodes in the subtrie.

Put(String, Object)

Stores a value in the trie. The value may be retrieved using the key.

Declaration

public virtual void Put(string key, object value)

Parameters

Type	Name	Description
System.String	key	A System.String that indexes the object to be stored.
System.Object	value	The object to be stored in the Trie.

Remove(String)

Removes the value indexed by key. Also removes all nodes that are rendered unnecessary by the removal of this data.

Declaration

public virtual void Remove(string key)

Parameters

Type	Name	Description
System.String	key	A System.String that indexes the object to be removed from the Trie.

SortKeys(JaspellTernarySearchTrie.TSTNode, Int32)

Returns keys sorted in alphabetical order. This includes the start Node and all nodes connected to the start Node.

The number of keys returned is limited to numReturnValues. To get a list that isn't limited in size, set numReturnValues to -1.

Declaration

protected virtual IList<string> SortKeys(JaspellTernarySearchTrie.TSTNode startNode, int numReturnValues)

Parameters

Type	Name	Description
JaspellTernarySearchTrie.TSTNode	startNode	The top node defining the subtrie to be searched.
System.Int32	numReturnValues	The maximum number of values returned from this method.

Returns

Type	Description
System.Collections.Generic.IList<System.String>	A System.Collections.Generic.IList<T> with the results.