3 unstable releases
0.2.1 | Mar 27, 2024 |
---|---|
0.2.0 | Dec 26, 2023 |
0.1.0 | Dec 25, 2023 |
#1106 in Text processing
28 downloads per month
Used in icann-rdap-srv
36KB
683 lines
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);
Dependencies
~3.5–6MB
~105K SLoC