Skip to content
Trie (a.k.a. prefix tree) C# implementation. Has constant-time string prefix lookup.
Branch: master
Clone or download
Latest commit 3331f84 Apr 16, 2018
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
AlgoLib Refactoring Feb 27, 2018
.gitignore Refactoring Feb 27, 2018
README.md Update README.md Apr 16, 2018

README.md

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

Build status

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 IEqualityComparer<char> comparer interface:

var trie = new Trie<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, 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<StringEntry<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
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

© Kirill Polishchuk

You can’t perform that action at this time.