二进制集成压缩 (BEN)

此库作为 PCompress 的类似物构建，旨在帮助改善选区计划的通用集成存储。

更具体地说，这个包旨在接受规范化的 JSONL 文件，这些文件使用以下形式的行存储集成

    {"assignment": <assignment_vector>, "sample": <sample_number_indexed_from_1>}

并将它们压缩成纯二进制文件。

用法

您可以使用 cargo 包管理器安装 binary-ensemble 包

cargo install binary-ensemble

这里 是一个小示例文件的链接，您可以使用它来查看 binary-ensemble 包的功能。

然后，您可以在以下模式之一中运行该包（假设 ~/.cargo/bin 已添加到您的路径）

• 编码

ben -m encode small_example.jsonl # Outputs small_example.jsonl.ben

• 解码

ben -m x-encode small_example.jsonl # Outputs small_example.jsonl.xben

• 解码

ben -m decode small_example.jsonl.ben -o re_small_example.jsonl # Outputs re_small_example.jsonl

• 解码

ben -m x-decode -p small_example.jsonl.xben # Prints decoding to the console

• 读取

ben -m read -n 4 small_example.jsonl  # Outputs [1,1,1,2,2,2,3,2,3,1,4,4,4,3,3,4]

• 压缩

ben -m xz-compress small_example.jsonl # Outputs small_example.jsonl.xz

• 解压缩

ben -m xz-decompress small_example.jsonl.xz # Outputs small_example.jsonl

还有另一个通过此包提供的 reben CLI 工具，但有关此工具的更多信息可以在 重命名 部分中找到

工作原理

我们采用的算法实际上并没有太多的复杂性；压缩的强大之处在于我们使用了一些关于分配向量的预期信息来大幅度缩小压缩向量的尺寸。

BEN 压缩格式是一种位级压缩算法（与大多数压缩应用程序中看到的字节级压缩相比），它分两个阶段工作

1. 运行长度编码 (RLE)
2. 位压缩

第一步很简单：给定一个类似于

[1,1,1,2,2,2,2,3,1,3,3,3]

的分配，我们可以使用有序对 $(value,, length)$ 来编码此向量，以获得向量

[(1,3), (2,4), (3,1), (1,1), (3,3)]

虽然在上述示例中效率不高，但在大多数选区计划中，如果我们根据地理信息（例如 GEOID）对分配向量中的节点进行排序，那么节省可以非常显著。

BEN 标准然后将此向量压缩成以下一系列字节

00000010_  <- the maximum number of bits needed to store the assignment values (2)
00000011_  <- the maximum number of bits needed to store the length values (3)
00000000
00000000
00000000
00000100_  <- the number of bytes needed to store the entire vector (4)
01011_101
00_11001_0
1001_1101
1_0000000 <- the bit-packed assignment vector

为小文件重命名

由于ben在底层使用RLE（行程长度编码），因此，任何能够提高输出赋值向量中相同赋值长序列概率的做法都将大大提高压缩效果。一般来说，这意味着我们需要以这种方式对JSON文件中的节点进行排序，以便它们在最终的赋值中很可能被分组在一起。当然，没有一种“最佳”方法来做这件事，但一般来说，按照地理标记对JSON文件进行排序是一个不错的选择。

例如，考虑这个科罗拉多州的二分图文件。这是一个块级二分图文件，包含约14万个节点，没有任何特定的顺序。如果我们使用这个二分图文件生成10万个示例计划并将结果存储在XBEN文件中，我们最终得到类似这个的文件。

虽然这个文件比原始的JSONL文件（高达27GB）小得多，但它仍然不是我们想要的那么小。然而，我们可以通过一点重新标记来改善这些文件的大小。

在我们能够看到重新标记带来的好处之前，我们需要将XBEN文件提取回BEN文件，以便我们可以处理它（警告：这将生成的BEN文件约为7GB，但我们将很快解决这个问题），因此我们需要运行以下命令

ben -m decode 100k_CO_chain.jsonl.xben

我们可以做的第一件事是改变我们计划的标记，使地区按照它们在赋值向量中出现的顺序进行标记。例如，如果我们有以下的赋值向量

[2,2,3,3,1,1,4,4]
[2,2,3,3,4,4,1,1]

作为人类，我们可以看到这些只是交换了一些数字的相同赋值。然而，使用LZMA2进行压缩的XBEN压缩器并没有我们拥有的上下文，因此，我们需要稍微帮助它。

在这里，我们可以使用reben（即重新标记BEN）命令行工具来完成这项工作

reben -m ben 100k_CO_chain.jsonl.ben

这通常会在不改变底层数据（除重新标记外）的情况下提高XBEN压缩效果，因此通常建议在压缩到XBEN格式之前运行reben。在我们的示例中，然后我们可以使用以下命令将此文件压缩回XBEN格式

ben -m x-encode 100k_CO_chain_canonicalized_assignments.jsonl.ben

实际上不要这样做，这将需要超过一个小时！！！

注意：解码很快，但使用高压缩进行编码确实需要时间（由于这个集合的大小，可能需要1小时或2小时，但这仅仅是因为这个文件在普查区。具有VTD的文件通常只需要10分钟或更少的时间。）

然而，这并不是我们使文件变小的唯一方法。一种更有效的策略是在运行链之前使用一些地理信息对文件进行排序。由于相邻的地理区域往往会放入彼此相同的地区，根据某种类似GEOID的东西对原始JSON文件中的节点进行排序通常会产生非常短的行程长度编码（因此，产生异常小的BEN文件）。然而，我们并不总是有先见之明来做这件事，所以问题变成了“我们是否可以在运行模拟之后对向量进行排序？”答案是“当然！”

这就是reben的另一个方面发挥作用的地方。如果我们想要为我们的二分图文件生成一个新的映射，以便它们按照某个键值进行排序，则可以使用以下命令

reben -m ben -s <dual-graph-file-name> -k <key-name>  <ben-file-name>

在我们的例子中，CO_small.json文件包含我们想要排序的GEOID20键，因此我们调用以下命令

reben -m ben -s CO_small.json -k GEOID20 100k_CO_chain_canonicalized_assignments.jsonl.ben

这将生成以下文件

• 100k_CO_chain_canonicalized_assignments_sorted_by_GEOID20.jsonl.ben (~550Mb)
• CO_small_sorted_by_GEOID20_map.json (包含新数据的映射文件)
• CO_small_sorted_by_GEOID20.json (节点位置调整的双图文件)

请注意，我们的BEN文件现在从约7Gb缩小到约0.5Gb，这相当不错！现在，我们可以使用x-encode模式对ben CLI进行进一步压缩。

ben -m x-encode 100k_CO_chain_canonicalized_assignments_sorted_by_GEOID20.jsonl.ben

这将生成文件100k_CO_chain_canonicalized_assignments_sorted_by_GEOID20.jsonl.xben，大小仅为约6Mb！这比原始BEN文件提高了1000倍，比JSONL文件提高了4500倍！

假设

BEN压缩器对用户应了解的数据做出了一些假设

• 当使用ben CLI工具时，假设分配向量中的分配以与某些JSON双图文件中的节点相同的顺序存储。虽然这似乎是标准，但用户有责任确保他们知道哪个双图文件/节点标记产生了这些分配向量。

• 当样本被编码为BEN格式时，解码的样本始终从1开始。

• 任何分配值的最大值假设为65535（16位可以存储的最大数字），同样，单个分配运行长度假设为65535。在所有实际应用中，这不应引起任何问题，除非用户正在专门寻找将爱达荷州在2010-2020年间的普查街区级别划分为国会选区的办法，并决定根据国会分配对双图文件进行排序（如果您这样做，1.为什么？2.也许可以先使用reben以更有意义的方式对双图文件进行排序）。其他州都不会对任何州级赛事造成问题。

• 应用BEN和XBEN编码和解码算法的计算机假设有足够的内存来存储整个分配向量。这不应成为问题，因为任何试图从这些文件中提取信息的计算机可能也在进行计划集的分析，但值得一提。

关于XBEN格式的更多信息

XBEN（即eXtreme-BEN）格式是用于大型数据存储和用户间传输集合的理想格式。与BEN相比，XBEN使用LZMA2的实现，进一步利用红istricting计划集中通常存在的重复性，进一步减小文件大小。

正如其名所示，Lempel-Ziv马尔可夫算法（之所以命名为马尔可夫算法，是因为它底层使用了马尔可夫算法，而不是因为它擅长压缩马尔可夫过程产生的数据），特别擅长提高由GerryChain或Forest Recom等马尔可夫方法生成的集合的压缩比率。它还可以在一般情况下提高BEN文件的压缩效果。LZMA2算法基于LZ-77算法，该算法用数据流中早先出现的数据的单个副本来替换数据的重复出现。然后，LZMA2使用马尔可夫过程动态确定可以分配给数据流中最频繁出现的顺序字节的数据的最佳变长编码（VLE），然后使用这些编码来编码数据（关于这里发生的事情的简化想法，请参见Huffman编码）。

当然，为了让LZMA2工作，我们需要使用字节而不是BEN使用位打包方法来编码数据，因此，在将BEN文件转换为XBEN文件（位打包通常会产生看起来像随机位序列的数据，这通常是不可压缩的）时，我们实际上会将每个赋值向量解包为一种称为BEN32的中间格式，这是一种使用32位来编码每个赋值向量的RLE（使用大端格式的u16作为值，使用大端格式的u16作为长度，以及一个null u32作为分隔符）。然后，LZMA2算法可以利用BEN32文件中字节的重复来显著提高压缩效果。

注意：从BEN到BEN32格式的解压缩只处理一次RLE赋值向量，所以使用LZMA2进行额外压缩的内存需求并不大。

何时使用ben和xben

BEN文件格式旨在成为一种可用于处理计划集合的可用格式。也就是说，它附带了一些辅助功能，使用户可以轻松读取特定样本数的赋值向量，因此可以用来“回放”来自马尔可夫链的集合。

XBEN文件格式旨在用于存储。ben CLI工具的设计重点是快速解压缩，因此任何存储为XBEN文件的文件都可以快速（在5分钟内）提取为可用的BEN格式。当然，这种权衡的代价是压缩本身相当慢，如果不重新标记以提高效率，有时可能需要几个小时才能完成。然而，考虑到任何创建计划集合的方法都可能需要几个小时，因此获取一个小型XBEN文件的额外压缩时间在总体上应该微不足道。

限制

由于BEN格式和CLI工具旨在与一般的区划计划集合一起工作，因此它确实存在一些限制。首先，虽然BEN在存储基于人口普查块的计划集合方面表现出色，但在考虑诸如VTDs或Tracts的计划集合时，压缩比率通常较小。在实践中，由于这些计划的赋值向量通常不是很长（大约10-20k），这并不是一个大问题，但值得注意。

如果需要特别小的文件来压缩由马尔可夫链蒙特卡洛方法（例如Recom或Forest Recom）在较大的子单元（如Tracts）上生成的区划集合，则使用字节级差分编码的PCompress格式是一个不错的选择。