trie

trie copied to clipboard

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 – trie

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

The library provides four implementations of the trie data structure:

• TrieSet<T>
• Trie<TKey, TValue>
• StringTrieSet
• StringTrie<TValue>

Tutorial

Trie<TValue> implements IDictionary<string, TValue> interface.

Trie initialization:

var trie = new StringTrie<TValue>();

or using constructor which accepts IEqualityComparer<char> comparer interface:

var trie = new StringTrie<TValue>(comparer);

To add items to trie:

trie.Add("key", value);
trie.AddRange(trieEntries);

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

The main advantage of trie is really fast prefix lookup. To find all items of StringTrie<TValue> which have keys with given prefix use GetByPrefix method which returns IEnumerable<StringEntry<TValue>>:

var result = trie.GetByPrefix("ABC");

Benchmark tests

For performance tests I used 58110 English words of length from 2 to 22 chars. The table below shows prefix lookup time comparing to the Linq Where and string.StartsWith. Number of prefixes: 10

© Kirill Polishchuk