压缩稀疏位数组

Question

我有 1024 字节(8192 位)的数组，它们大多为零。

将设置 0.01% 和 10% 之间的位(随机，无模式)。

鉴于缺乏结构和相对较小的尺寸，如何压缩这些？

(我的第一个想法是存储设置位之间的距离。每个距离我需要 13 位，但在最坏的情况下，10% 的占用率需要 13 * 816 / 8 = 1326 字节，这不是改进。)

这是用于超低带宽通信，因此每个字节都很重要。

Answer 1

我已经深入处理了一个类似的问题，但是我的集合要大得多(每组中有 3000 万个可能的值，每个集合中有 1 到 3000 万个元素)，因此它们都从压缩中获得了更多，并且与压缩元数据相比，压缩元数据无关紧要数据的大小。我从来没有把东西压缩成小于 uint16_t 的单位。 ，所以如果您开始将 13 位值切碎，我在下面写的内容可能不适用。感觉它应该工作，但警告空客。

我发现有效的是采用几种取决于我们拥有的特定数据的策略。好消息是，每个集合中元素的数量是一个非常好的指标，表明哪种压缩策略最适合特定集合。因此，您需要的所有元数据都是集合中元素的计数。在我的数据格式中，第一个也是唯一的元数据值(我将不具体，只是称其为“值”，您可以将内容压缩为字节、16 位值或 13 位值，但是您觉得)是集合中元素的计数，剩下的只是集合元素的编码。

这些策略是:

如果集合中的元素很少，你不能比一个写着“1, 4711, 8140”的数组做得更好，所以在这种情况下，数据被编码为:[3, 1, 4711, 8140]

如果几乎所有元素都在集合中，您可以只跟踪不在集合中的元素。例如 [8190, 17, 42]。

如果大约一半的元素在集合中，你几乎不能比位图做得更好，所以你得到 [4000, {bitmap}]，这是你的数据最终比严格未压缩更长的唯一情况。

如果设置了多于“几个”但少于“大约一半”的元素，我找到了另一种策略。将集合中可能值的位分成两半。假设我们有 2^16 个(更容易描述，它可能适用于 2^13 个)可能的值。这些值分为 256 个范围，每个范围有 256 个可能的值。然后我们有一个 256 字节的数组，每个字节描述了每个范围中有多少个值(所以字节 0 告诉我们有多少元素是 [0,255]，字节 1 给我们 [256,511]，等等)紧跟在跟随数组之后使用每个范围内的值 mod 256。这里的技巧是，虽然编码为数组(策略 1)的集合中的每个元素都是 2 个字节，但在这个方案中，每个元素只有 1 个字节 + 256 个静态字节，用于计数元素。这意味着只要集合中有超过 256 个元素，就可以通过从策略 1 切换到策略 4 来节省空间。

策略 4 可以改进(如果你提到的数据是随机的，可能没有意义，但我的数据有时有更多的模式，所以它对我有用)。由于在之前的编码中我们仍然需要为每个元素分配 8 位，因此只要元素子数组超过 32 个元素(256 字节)，我们就可以将其存储为位图。这也是4/5到3之间切换策略的一个很好的断点。如果这个策略中的所有数组都只是位图，那么我们应该只使用策略3(它比那个更复杂，但是策略之间的断点可以预先计算相当准确地说，您每次最终都会选择最可能的有效策略)。

我只是模糊地尝试在集合中的数字之间保存增量。快速实验表明，它们并不比我上面提到的策略更有效，具有不可预测的退化情况，但最重要的是，我使用的应用程序真的很喜欢不必反序列化其数据，只需直接从磁盘中使用它( map )。