压缩稀疏位数组
Compressing a sparse bit array
我有 1024 字节（8192 位）的数组，其中大部分为零。
将设置 0.01% 到 10% 的位（随机，无模式）。
鉴于缺乏结构和相对较小的尺寸，如何压缩这些文件？
(我的第一个想法是存储设置位之间的距离。每个距离需要 13 位，但在最坏的情况下，10% 的占用率需要 13 * 816 / 8 = 1326 字节，这是没有改善。）
这适用于超低带宽通信，因此每个字节都很重要。
我已经深入处理过类似的问题，但我的集合要大得多（3000 万个可能的值，每个集合中有 1 到 3000 万个元素），所以它们都从压缩和压缩元数据中获得更多与数据的大小相比是微不足道的。我从来没有把东西压缩成小于 uint16_t 的单位，所以如果你开始将 13 位值分割成碎片，我在下面写的东西可能不适用。感觉应该可以，但买者自负。
我发现有效的方法是根据我们拥有的特定数据采用多种策略。好消息是每个集合中的元素数量是一个很好的指标，表明哪种压缩策略最适合特定集合。因此，您需要的所有元数据都是集合中元素的计数。在我的数据格式中，第一个也是唯一的元数据值（我将不具体，只是称它为 "value"，你可以按字节、16 位值或 13 位值压缩内容，但是你觉得）是元素的计数集合，剩下的只是集合元素的编码。
策略是：
如果集合中的元素非常少，你不能比数组“1, 4711, 8140”做得更好，所以在这种情况下数据被编码为：[3 , 1, 4711, 8140]
如果几乎所有元素都在集合中，您可以只跟踪不在集合中的元素。例如 [8190, 17, 42].
如果大约一半的元素在集合中，你几乎不能比位图做得更好，所以你得到 [4000, {bitmap}]，这是唯一的情况您的数据最终比严格未压缩的要长。
如果设置了多于"a few"但少于"around half"的元素，我找到了另一种策略。将集合中可能值的位分成两半。假设我们有 2^16 个（描述起来更容易，它可能适用于 2^13 个）可能的值。这些值分为 256 个范围，每个范围有 256 个可能的值。然后我们有一个 256 字节的数组，这些字节中的每一个都描述了每个范围内有多少个值（所以字节 0 告诉我们有多少元素是 [0,255]，字节 1 给我们 [256,511]，等等）紧跟在数组之后每个范围内的值 mod 256。这里的技巧是，虽然编码为数组（策略 1）的集合中的每个元素都是 2 个字节，但在这个方案中每个元素只有 1 个字节 + 256 个静态字节对于元素的计数。这意味着一旦集合中的元素超过 256 个，就可以通过从策略 1 切换到策略 4 来节省我们 space。
策略 4 可以改进（如果你的数据像你提到的那样是随机的，可能没有意义，但我的数据有时有更多的模式，所以它对我有用）。由于在之前的编码中每个元素仍然需要 8 位，所以只要元素的子数组超过 32 个元素（256 字节），我们就可以将其存储为位图。这也是在 4/5 和 3 之间切换策略的一个很好的断点。如果这个策略中的所有数组都只是位图，那么我们应该只使用策略 3（它比这更复杂，但是策略之间的断点可以预先计算得很好准确地说，您最终每次都会选择最可能有效的策略）。
我只是模糊地尝试过保存集合中数字之间的增量。快速实验表明它们并不比我上面提到的策略更有效，有不可预测的退化情况，但最重要的是，我使用的应用程序真的喜欢不必反序列化其数据，只需直接从磁盘使用原始数据(mmap).
我有 1024 字节（8192 位）的数组，其中大部分为零。
将设置 0.01% 到 10% 的位（随机，无模式）。
鉴于缺乏结构和相对较小的尺寸，如何压缩这些文件？
(我的第一个想法是存储设置位之间的距离。每个距离需要 13 位，但在最坏的情况下，10% 的占用率需要 13 * 816 / 8 = 1326 字节，这是没有改善。）
这适用于超低带宽通信，因此每个字节都很重要。
我已经深入处理过类似的问题，但我的集合要大得多（3000 万个可能的值，每个集合中有 1 到 3000 万个元素），所以它们都从压缩和压缩元数据中获得更多与数据的大小相比是微不足道的。我从来没有把东西压缩成小于 uint16_t 的单位，所以如果你开始将 13 位值分割成碎片，我在下面写的东西可能不适用。感觉应该可以，但买者自负。
我发现有效的方法是根据我们拥有的特定数据采用多种策略。好消息是每个集合中的元素数量是一个很好的指标，表明哪种压缩策略最适合特定集合。因此，您需要的所有元数据都是集合中元素的计数。在我的数据格式中，第一个也是唯一的元数据值（我将不具体，只是称它为 "value"，你可以按字节、16 位值或 13 位值压缩内容，但是你觉得）是元素的计数集合，剩下的只是集合元素的编码。
策略是：
如果集合中的元素非常少，你不能比数组“1, 4711, 8140”做得更好，所以在这种情况下数据被编码为：[3 , 1, 4711, 8140]
如果几乎所有元素都在集合中，您可以只跟踪不在集合中的元素。例如 [8190, 17, 42].
如果大约一半的元素在集合中，你几乎不能比位图做得更好，所以你得到 [4000, {bitmap}]，这是唯一的情况您的数据最终比严格未压缩的要长。
如果设置了多于"a few"但少于"around half"的元素，我找到了另一种策略。将集合中可能值的位分成两半。假设我们有 2^16 个（描述起来更容易，它可能适用于 2^13 个）可能的值。这些值分为 256 个范围，每个范围有 256 个可能的值。然后我们有一个 256 字节的数组，这些字节中的每一个都描述了每个范围内有多少个值（所以字节 0 告诉我们有多少元素是 [0,255]，字节 1 给我们 [256,511]，等等）紧跟在数组之后每个范围内的值 mod 256。这里的技巧是，虽然编码为数组（策略 1）的集合中的每个元素都是 2 个字节，但在这个方案中每个元素只有 1 个字节 + 256 个静态字节对于元素的计数。这意味着一旦集合中的元素超过 256 个，就可以通过从策略 1 切换到策略 4 来节省我们 space。
策略 4 可以改进（如果你的数据像你提到的那样是随机的，可能没有意义，但我的数据有时有更多的模式，所以它对我有用）。由于在之前的编码中每个元素仍然需要 8 位，所以只要元素的子数组超过 32 个元素（256 字节），我们就可以将其存储为位图。这也是在 4/5 和 3 之间切换策略的一个很好的断点。如果这个策略中的所有数组都只是位图，那么我们应该只使用策略 3（它比这更复杂，但是策略之间的断点可以预先计算得很好准确地说，您最终每次都会选择最可能有效的策略）。
我只是模糊地尝试过保存集合中数字之间的增量。快速实验表明它们并不比我上面提到的策略更有效，有不可预测的退化情况，但最重要的是，我使用的应用程序真的喜欢不必反序列化其数据，只需直接从磁盘使用原始数据(mmap).