Yada：另一种双数组

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

特性

• 构建静态双数组Trie
  • Yada采用了类似于Darts-clone的双数组节点的紧凑二进制表示。
• 公共前缀搜索
  • 该方法返回一个迭代器，这是一种在不进行堆分配的情况下查找多个值的有效方法。
• 精确匹配搜索
  • 该方法以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 License，版本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系统）的克隆