KTrie 2.5.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 : ICollection<string>, this is a set which stores unique strings
• TrieDictionary<TValue> : IDictionary<string, TValue>, this is a key-value-pair collection

Tutorial

TrieDictionary initialization:

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

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

Adding items to trie

trie.Add("key", 17);

The Add method throws ArgumentNullException if a value with the specified key already exists, however setting the Item property overwrites the old value. In other words, TrieDictionary<TValue> has the same behavior as Dictionary<TKey, TValue>.

The main advantage of trie is really fast prefix lookup. To find all items of TrieDictionary<TValue> which have keys with given prefix use StartsWith method which returns IEnumerable<KeyValuePair<string, TValue>>:

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

Another handy method is Matches(IReadOnlyList<Character> pattern)

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

which will return all words that match this regex: ^.c.{2}t$, e.g.: octet, scout, scoot.

There are two overloads of the StartsWith method:

• StartsWith(string value)
• StartsWith(IReadOnlyList<Character> pattern)

Benchmark tests

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

© Kirill Polishchuk