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

Tutorial

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");

Benchmark tests

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
Prefixes count:	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
Prefix length:	Prefixes count:	LINQ – StartsWith	Trie – GetByPrefix
1	26	307	167
2	676	7675	163
3	17576	197057	168
4	456976	—	267
5	11881376	—	4632

------ © Kirill Polishchuk

adisong/trie

ErrorLooks like something went wrong!

About

Resources

Uh oh!

Stars

Watchers

Forks

Releases

Packages 0

Languages

Error
Looks like something went wrong!

Packages