Meziantou.FrameworkPruningRadixTree Class
Represents a case-sensitive radix-compressed trie optimized for ranked prefix autocomplete.
public sealed class PruningRadixTree : IEnumerable<KeyValuePair<string, long>>, IEnumerableRemarks
This collection stores terms with a frequency score and can efficiently retrieve the top-k completions for a prefix. It augments each node with the maximum frequency in its subtree so low-ranking branches can be pruned during lookup.
Typical use cases include search-box suggestions, query completion, and dictionary-backed command palettes.
The structure is case-sensitive. If you need case-insensitive behavior, normalize input before adding or querying.
Example:
var tree = new PruningRadixTree();
tree.Add("car", 10);
tree.Add("cart", 5);
tree.Add("cat", 7);
var suggestions = tree.GetTopTermsByPrefix("ca", topK: 2, out _);
Assert.Equal([KeyValuePair.Create("car", 10L), KeyValuePair.Create("cat", 7L)], suggestions);Constructors
| Name | Description |
|---|---|
| PruningRadixTree() | Initializes a new instance of PruningRadixTree. |
PruningRadixTree()
PruningRadixTree.csInitializes a new instance of PruningRadixTree.
public PruningRadixTree()Properties
| Name | Description |
|---|---|
| Count | Gets the number of stored terms. |
Count
PruningRadixTree.csMethods
| Name | Description |
|---|---|
| Add(string, long) | Adds a term and its frequency to the tree. |
| AddRange(IEnumerable<KeyValuePair<string, long>>) | Adds a sequence of terms and frequencies to the tree. |
| ContainsKey(ReadOnlySpan<char>) | Determines whether the tree contains a specific term. |
| GetEnumerator() | Returns an enumerator that iterates through all terms in the tree. |
| GetTopTermsByPrefix(ReadOnlySpan<char>, int, long, bool) | Gets the top terms for a given prefix, sorted by frequency descending. |
| Remove(ReadOnlySpan<char>) | Removes a term from the tree. |
| System.Collections.IEnumerable.GetEnumerator() | |
| TryGetValue(ReadOnlySpan<char>, long) | Gets the frequency associated with a term. |
Add(string, long)
PruningRadixTree.csAdds a term and its frequency to the tree.
Parameters
Exceptions
ArgumentNullExceptiontermisnull.ArgumentOutOfRangeExceptionfrequencyis less than or equal to 0.
Remarks
If the term already exists, frequency is added to the existing value.
AddRange(IEnumerable<KeyValuePair<string, long>>)
PruningRadixTree.csAdds a sequence of terms and frequencies to the tree.
public void AddRange(IEnumerable<KeyValuePair<string, long>> terms)Parameters
termsIEnumerable<KeyValuePair<string, long>>- The terms to add.
Exceptions
ArgumentNullExceptiontermsisnull.ArgumentNullException- One of the term keys is
null. ArgumentOutOfRangeException- One of the frequencies is less than or equal to 0.
Remarks
This method is optimized for bulk loading by aggregating duplicate keys and building the radix tree from sorted entries. When the tree already contains more terms than the sequence, the terms are added one by one instead of rebuilding the tree.
ContainsKey(ReadOnlySpan<char>)
PruningRadixTree.csDetermines whether the tree contains a specific term.
public bool ContainsKey(ReadOnlySpan<char> term)Parameters
termReadOnlySpan<char>- The term to locate.
Returns
bool true if the term exists; otherwise, false.
GetEnumerator()
PruningRadixTree.csReturns an enumerator that iterates through all terms in the tree.
public IEnumerator<KeyValuePair<string, long>> GetEnumerator()Returns
IEnumerator<KeyValuePair<string, long>> An enumerator for all stored terms and frequencies.
GetTopTermsByPrefix(ReadOnlySpan<char>, int, long, bool)
PruningRadixTree.csGets the top terms for a given prefix, sorted by frequency descending.
public IReadOnlyList<KeyValuePair<string, long>> GetTopTermsByPrefix(ReadOnlySpan<char> prefix, int topK, out long prefixFrequency, bool pruning = true)Parameters
prefixReadOnlySpan<char>- The prefix to search.
topKint- The maximum number of suggestions to return.
prefixFrequencylong- When this method returns, contains the exact frequency of
prefixif it is a stored term; otherwise, 0. pruningbooltrueto prune non-promising branches using subtree metadata; otherwise,false.
Returns
IReadOnlyList<KeyValuePair<string, long>> A ranked list of matching terms.
Exceptions
ArgumentOutOfRangeExceptiontopKis negative.
Remove(ReadOnlySpan<char>)
PruningRadixTree.csRemoves a term from the tree.
public bool Remove(ReadOnlySpan<char> term)Parameters
termReadOnlySpan<char>- The term to remove.
Returns
bool true when the term existed and was removed; otherwise, false.
System.Collections.IEnumerable.GetEnumerator()
PruningRadixTree.csTryGetValue(ReadOnlySpan<char>, long)
PruningRadixTree.csGets the frequency associated with a term.
public bool TryGetValue(ReadOnlySpan<char> term, out long frequency)Parameters
termReadOnlySpan<char>- The term to find.
frequencylong- When this method returns, contains the associated frequency if found; otherwise, 0.
Returns
bool true if the term exists; otherwise, false.