ab-radix-trie

Radix-Trie

Radix-trie implementation i.e. compressed prefix-trie

https://en.wikipedia.org/wiki/Radix_tree

Some nice features:

• Compressed nodes
• Fuzzy matching - match on whitespace, replacing characters, etc.
• Supports all unicode characters
• Arbitrarily associate values to text (i.e. map strings to values)
• Serializable with serde

Performance

Approximately:

• insertion O(depth of trie)
• retrieval O(depth of trie)
• deletion O(depth of trie)
• Space - I don't know really, but it will behave according to ~O(entropy of text) - Similar texts are compressed together - i.e. "ABC", "ABCD" will occupy O("ABCD") space split into "ABC" and "D"

Usage:

I suggest checking out the examples and the tests for some patterns

The basic usage is along these lines

let mut trie: Trie<i32> = Trie::new();
trie.insert("romanus", None);
trie.insert("romulus", Some(10));
trie.insert("rubens", None);
trie.insert("ruber", None);
trie.insert("rubicon", None);
trie.insert("rubicundus", None);