k2_tree

一个用于高效压缩稀疏位矩阵的集合。

查看原始提案此处。

注意：此库高度依赖bitvec来最优地存储其数据，如果没有优化编译，这将非常慢！

用法

将k2_tree添加到您的项目依赖中

[dependencies]
k2_tree = "0.5.2"

当K2Tree有用时

K2Tree在表示可以编码为二维位矩阵的数据时非常高效，尤其是如果该矩阵是稀疏的。

以一个现实世界的例子来说明：表示Web-Graphs。

网页之间的超链接可以编码为一个二维位矩阵，其中每一列/行对应一个特定的页面，每个位表示两个页面是否通过超链接连接；是则为1，否则为0。

这些邻接矩阵通常非常稀疏（大多数时候），使K2Tree成为编码它们的完美结构！

另一个例子是表示Triple-Stores，这个仓库演示了其有效性。

示例

原始位矩阵

00|00||10|10
00|00||00|11
------------
00|00||00|00
00|00||00|10
============
10|10||00|11
10|00||00|00
------------
00|00||00|00
00|00||00|00

位表示

[0111; 1101, 1100, 0100; 1000, 1011, 0010, 1010, 1000, 1100]

(其中;分隔层，,分隔块)

最终的K2Tree

K2Tree {
  stem_k: 2, // usize
  leaf_k: 2, // usize
  max_slayers: 2, // usize
  stems: [0111110111000100], // BitVec
  leaves: [100010110010101010001100], // BitVec
}

有关压缩过程的更深入解释，请查看此处。

通往1.0的道路

• 使K2Tree能够在任何K值上工作。
• 将k字段分为两个独立的字段：stem_k，leaf_k。
• 通过删除stem_to_leaf和slayer_starts字段来提高压缩比，同时不牺牲操作复杂性。
• 实现serde的Serialize和Deserialize特征。
• 对所有内容进行单元测试。
• 稳定API。

- GGabi