Yada: 另一种双数组

Yada 是一个旨在实现快速搜索和紧凑数据表示的另一种双数组 trie 库。

特性

• 构建静态双数组 trie
  • Yada 采用类似 Darts-clone 的双数组节点的紧凑二进制表示。
• 公共前缀搜索
  • 该方法返回一个 Iterator，这是一种有效的方法，可以在不进行堆分配的情况下找到多个值。
• 精确匹配搜索
  • 该方法通过 Option 找到与精确匹配键关联的值。

要求

• Rust 版本 >= 1.46.0

用法

有关详细信息，请参阅 示例代码。

构建双数组 trie

use yada::builder::DoubleArrayBuilder;

// make a keyset which have key-value pairs
let keyset = &[
    ("a".as_bytes(), 0),
    ("ab".as_bytes(), 1),
    ("abc".as_bytes(), 2),
    ("b".as_bytes(), 3),
    ("bc".as_bytes(), 4),
    ("c".as_bytes(), 5),
];

// build a double-array trie binary
let da_bytes: Option<Vec<u8>> = DoubleArrayBuilder::build(keyset);

通过键搜索条目

use yada::DoubleArray;

// create a double-array trie instance
let da = DoubleArray::new(da_bytes.unwrap());

// exact match search
for (key, value) in keyset {
    assert_eq!(da.exact_match_search(key), Some(*value as u32));
}
assert_eq!(da.exact_match_search("abc".as_bytes()), Some(2));
assert_eq!(da.exact_match_search("abcd".as_bytes()), None);

// common prefix search
assert_eq!(
    da.common_prefix_search("abcd".as_bytes())
        .collect::<Vec<_>>(),
    vec![(0, 1), (1, 2), (2, 3)] // match "a", "ab", "abc", value and key length
);
assert_eq!(
    da.common_prefix_search("d".as_bytes()).collect::<Vec<_>>(),
    vec![] // don't match
);

限制

• 值必须表示为 31 位无符号整数，类型为 u32。
  • Yada 使用最高位（MSB）作为标志来区分值节点和其他节点。
• 双数组节点的偏移量为 29 位宽，因此可以表示高达 ~536M 个节点。
  • 这意味着这个限制导致双数组的最大大小约为 ~2GB。

许可

许可方式之一

• Apache 许可证 2.0 版 (LICENSE-APACHE)
• MIT 许可证 (LICENSE-MIT)

任选其一。

贡献

除非您明确声明，否则您提交给工作的任何有意贡献，根据 Apache-2.0 许可证的定义，应按上述方式双许可，不得添加任何额外的条款或条件。

参考文献

• Aoe, J. 使用双数组结构的高效数字搜索算法。IEEE 软件工程 Transactions。第 15 卷，第 9 期（1989 年 9 月）。第 1066-1077 页。
• Darts: 双数组 trie 系统
• Darts-clone: Darts（双数组 trie 系统）的克隆