hat_trie

根据Nikolas Askitis和Ranjan Sinha的研究实现的帽Trie。

部分代码受到C99编写的帽Trie的启发。关于帽Trie的简介可以在这里找到。

简短描述

帽Trie是一种缓存感知的Trie。这个包实现了一种“混合”帽Trie。它比纯“哈希表”消耗更少的存储空间，因为许多公共前缀将被提取到Trie的公共节点中，但这仅在条目数量足够大时才会发生，因此对于少量条目，它实际上是“哈希表”，而对于大量条目，它则是“哈希表”和Trie的混合。

如何使用

作为字典

use htrie::{DenseVecTrieNode, TrieNode};
let mut dvtn = DenseVecTrieNode::new();
assert!(dvtn.get("".as_bytes()).is_none());
assert_eq!(dvtn.put("Yo".as_bytes(), 1), None);
assert_eq!(dvtn.get("Yo".as_bytes()), Some(&1));
assert_eq!(dvtn.put("Yes".as_bytes(), 2), None);
assert_eq!(dvtn.get("Yes".as_bytes()), Some(&2));

作为前缀查找数据结构

use htrie::{DenseVecTrieNode, TrieNode};

let mut dvtn: DenseVecTrieNode<u8, u8> = DenseVecTrieNode::new();
dvtn.put(&[1u8], 1u8);
dvtn.put(&[1u8, 2, 3], 2u8);
dvtn.put(&[1u8, 2, 3, 4], 3u8);

assert_eq!(dvtn.prefix(&[0u8, 1]).map(|(key, _)| {key}).collect::<Vec<&[u8]>>().len(), 0);
let key = &[1u8, 1];
let pf = dvtn.prefix(key).map(|(key, _)| {key}).collect::<Vec<&[u8]>>();
assert_eq!(pf.len(), 1);
assert_eq!(pf[0], &key[..1]);

let key = &[1u8, 2, 3, 5, 6];
let pf = dvtn.prefix(key).map(|(key, _)| {key}).collect::<Vec<&[u8]>>();

assert_eq!(pf.len(), 2);
for k in pf {
    assert_eq!(&key[..k.len()], k);
}

注意事项

当前的实现与论文中的实现非常相似。在初始化DenseVecTrieNode时，它预先分配至少等于键元素位数的2^bits大小的内存。所以，在第一个例子中，它是8位，因此预先分配了大约2^8 * usize大小的内存。在64位系统上，这需要1024字节加上一些ahtable和值的大小开销。然而，如果你的数据是u32（Unicode码点的尺寸），你将需要至少2^32 * usize大小的内存，因此在64位系统上，对于一个空的DenseVecTrieNode，它将超过16GB。

这就是为什么在上面的示例代码中，我们在将其放入Trie之前将数据编码为字节的原因。如果你的数据是UTF-16编码的，也可以将其编码为u16。然而，为了简化示例，我们使用了u8。这是因为Rust默认使用UTF-8编码。