GTrie

Trie是一个实现trie的库。

Trie是一种泛型数据结构，写作Trie<T, U>其中T是节点键类型，而U是值类型。

动机

在某些情况下，Trie可能比其他数据结构更快。

例如，在字典中，如果字典中的单词数量远小于输入中的不同单词数量，并且匹配概率较低，则可以使用Trie作为std::HashMap的替代品。

使用方法

use gtrie::Trie;

let mut t = Trie::new();

t.insert("this".chars(), 1);
t.insert("trie".chars(), 2);
t.insert("contains".chars(), 3);
t.insert("a".chars(), 4);
t.insert("number".chars(), 5);
t.insert("of".chars(), 6);
t.insert("words".chars(), 7);

assert_eq!(t.contains_key("number".chars()), true);
assert_eq!(t.contains_key("not_existing_key".chars()), false);
assert_eq!(t.get_value("words".chars()), Some(7));
assert_eq!(t.get_value("none".chars()), None);

基准测试

基准测试std::HashMap<String, String>与gtrie::Trie显示，在键不匹配的情况下，Trie要快得多，但在匹配键的情况下要慢得多。

$ cargo bench
test hash_map_massive_match                        ... bench:     150,127 ns/iter (+/- 12,986)
test hash_map_massive_mismatch_on_0                ... bench:      93,246 ns/iter (+/- 5,108)
test hash_map_massive_mismatch_on_0_one_symbol_key ... bench:      93,706 ns/iter (+/- 5,908)
test hash_map_match                                ... bench:          24 ns/iter (+/- 3)
test hash_map_mismatch                             ... bench:          20 ns/iter (+/- 0)
test trie_massive_match                            ... bench:     231,343 ns/iter (+/- 4,940)
test trie_massive_mismatch_on_0                    ... bench:      28,743 ns/iter (+/- 8,401)
test trie_massive_mismatch_on_1                    ... bench:      28,734 ns/iter (+/- 1,839)
test trie_massive_mismatch_on_2                    ... bench:      28,760 ns/iter (+/- 2,582)
test trie_massive_mismatch_on_3                    ... bench:      28,829 ns/iter (+/- 2,504)
test trie_match                                    ... bench:          10 ns/iter (+/- 1)
test trie_mismatch                                 ... bench:           5 ns/iter (+/- 0)

重要

搜索性能高度依赖于存储在Trie中的数据，并且可能比std::HashMap快得多，也可能慢得多。

贡献

源代码和问题托管在GitHub上

https://github.com/aserebryakov/trie-rs

许可证

MIT许可证

变更日志

0.4.0

• 由于转换为面向数据模型，性能显著提高

0.3.0

• 键不匹配的情况性能显著提高
• API已更新，使其更接近std::HashMap

0.2.1

• 基准测试已改进

0.2.0

• API已更新，使其更接近std::HashMap

0.1.1

• 基本的Trie实现