KTrie 3.0.0

Trie

Trie (a.k.a. prefix tree) is an ordered tree data structure that is used to store an associative array where the keys are usually strings. All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string.
Reference: Wikipedia

Advantages

• Looking up keys is faster. Looking up a key of length key takes O(|key|) time
• Looking up prefixes is faster. Looking up a prefix takes O(|prefix|) time
• Removing takes O(|key|) time

Trie trie = ["star", "start", "stack", "stop", "stay", "key"];

          {root}
            /\
           s  k
          /    \
         t      e
        / \      \
      a    o     [y]
    / | \    \
  [r][y] c   [p]
  /       \
[t]       [k]

where [char] -- is end of word

The library provides two implementations of the trie data structure:

• Trie — implements ICollection<string> for storing unique strings.
• TrieDictionary<TValue> — implements IDictionary<string, TValue> for key-value pairs.

Usage

Initialization

// Initialization
TrieDictionary<int> trie = [];

// or using constructor with comparer
IEqualityComparer<char> comparer = ...; // specify the comparer
TrieDictionary<int> trieWithComparer = new(comparer);

Adding items to the trie

trie.Add("key", 17);

• Add throws an ArgumentNullException if the key is null, and ArgumentException if the key already exists.
• You can overwrite existing values using the indexer:

trie["key"] = 42;

(similar to Dictionary<TKey, TValue>)

Prefix Lookup

The main benefit of a Trie is extremely fast prefix lookup.

var result = trie.EnumerateByPrefix("abc");

This returns all key-value pairs where the key starts with the prefix "abc".

There are multiple overloads of the EnumerateByPrefix method.

• EnumerateByPrefix(string prefix)
• EnumerateByPrefix(IReadOnlyList<Character> pattern)
• EnumerateByPrefix(ReadOnlySpan<char> prefix)

Pattern Matching

The EnumerateMatches method supports character pattern-based search:

var result = trie.EnumerateMatches([Character.Any, 'c', Character.Any, Character.Any, 't']);

This matches words like octet, scout, or scoot using the regex-like pattern: ^.c.{2}t$.

API Methods

The API methods support efficient, allocation-free prefix matching with ReadOnlySpan<char>

string? LongestPrefixMatch(string input)

Returns the longest prefix of the specified input that exists as a full key in the trie. This is useful for IP routing, token parsing, or search suggestion scenarios where the longest valid prefix match is needed.

string? matched = trie.LongestPrefixMatch("starting");

For example, if the trie contains "start", "star", and "stack", calling LongestPrefixMatch("starting") will return "start".

bool TryAdd(string key, TValue value)

Attempts to add the specified key and value to the TrieDictionary.
Returns true if the key/value pair was added successfully; false if the key already exists.

bool success = trie.TryAdd("alpha", 1);

bool Remove(string key)

Removes the value with the specified key from the TrieDictionary.
Returns true if the element is successfully removed; false if the key was not found.

bool removed = trie.Remove("key");

bool ContainsKey(string key)

Determines whether the TrieDictionary contains the specified key.

bool containsKey = trie.ContainsKey("key");

bool TryGetValue(string key, out TValue value)

Attempts to get the value associated with the specified key.
Returns true if the key is found; otherwise, false.

bool keyFound = trie.TryGetValue("key", out int value);

Benchmark tests

For performance tests I used 370105 English words (from: https://github.com/dwyl/english-words).

© Kirill Polishchuk