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
- 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<TValue>
implements IDictionary<string, TValue>
interface.
Trie initialization:
var trie = new Trie<TValue>();
or using constructor which accepts IComparer<char>
interface:
var trie = new Trie<TValue>(comparer);
To add items to trie:
trie.Add("key", value);
trie.Add(new TrieEntry<TValue>("key2", value));
trie.AddRange(trieEntries);
The Add
, AddRange
methods throw ArgumentException
if a value with the specified key already exists, however setting the Item
property overwrites the old value. In other words, Trie<TValue>
has the same behavior as Dictionary<TKey, TValue>
.
The main advantage of trie is really fast prefix lookup. To find all items of Trie<TValue>
which have keys with given prefix use GetByPrefix
method which returns IEnumerable<TrieEntry<TValue>>
:
var result = trie.GetByPrefix("ABC");
For performance tests I have used vocabulary with 58110 English words with length from 2 to 22 chars. On my PC loading all words to trie takes: 140 ms.
In following table are presented results of searching items by prefix:
Prefixes count: | Time, ms | |
---|---|---|
LINQ – StartsWith | Trie – GetByPrefix | |
30 | 338 | 57 |
60 | 669 | 100 |
90 | 1001 | 193 |
120 | 1342 | 265 |
150 | 1678 | 251 |
180 | 2023 | 336 |
210 | 2380 | 383 |
240 | 2724 | 408 |
270 | 2995 | 453 |
300 | 3405 | 521 |
1500 | 16473 | 2366 |
3000 | 33263 | 4162 |
Tests using brute-force prefix generator.
Prefix length: | Prefixes count: | Time, ms | |
---|---|---|---|
LINQ – StartsWith | Trie – GetByPrefix | ||
1 | 26 | 307 | 167 |
2 | 676 | 7675 | 163 |
3 | 17576 | 197057 | 168 |
4 | 456976 | — | 267 |
5 | 11881376 | — | 4632 |