压缩稀疏位数组

Question

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

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

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

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

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

Answer 1

我已经深入地处理了一个类似的问题，但是我的集合要大得多(每个集合中有3000万个可能的值，每个集合中有1到3000万个元素)，所以它们都从压缩中获得了更多的好处，而且压缩元数据与数据的大小相比是微不足道的。我从来没有把东西压缩成比uint16_t小的单位，所以如果你开始把13位值切成碎片，我在下面写的东西可能就不适用了。感觉它应该有效，但请注意。

我所发现的工作是采用几种依赖于我们所拥有的特定数据的策略。好消息是，每组中的元素数是一个非常好的指示符，可以很好地指示哪种压缩策略对特定的集合最有效。因此，您需要的所有元数据都是集合中元素的计数。在我的数据格式中，第一个也是唯一的元数据值(我将不具体地称之为“值”，您可以按字节、16位值或13位值压缩数据)是集合中元素的计数，其余的只是set元素的编码。

这些战略是：

1. 如果集合中只有极少数元素，则不能比数组"1,4711,8140“更好，因此在本例中，数据编码为: 3，1,4711,8140。
2. 如果几乎所有元素都在集合中，那么您可以只跟踪那些不是的元素，例如8190、17、42。
3. 如果大约一半的元素在集合中，那么您几乎不能比位图做得更好，所以您得到了4000，{位图}，这是数据最后超过严格解压缩的唯一情况。
4. 如果设置的元素超过“少数”但少于“大约一半”，我发现了另一种策略。将集合中可能值的部分分成两部分。假设我们有2^16 (更容易描述，它可能适用于2^13)可能的值。这些值被划分为256个范围，每个范围都有256个可能的值。然后我们有一个256字节的数组，每个字节描述每个范围内有多少值(所以字节0告诉我们有多少元素是0,255，字节1给我们256,511等等)。紧随其后的数组与每个范围内的值mod 256。这里的诀窍是，虽然集合中的每个元素编码为数组(策略1)将是2个字节，但在此方案中，每个元素仅为1字节+256个静态字节用于元素计数。这意味着，一旦集合中有超过256个元素，就可以通过从策略1切换到策略4来节省空间。
5. 可以对策略4进行细化(如果您提到的数据是随机的，那么可能没有意义，但是我的数据有时会有更多的模式，所以它对我来说是有效的)。由于上一次编码中的每个元素仍然需要8位，所以只要元素的子数组超过32个元素(256个字节)，我们就可以将其存储为位图。对于在4/5到3之间切换策略来说，这也是一个很好的断点。如果这个策略中的所有数组都是位图，那么我们应该只使用策略3(它比策略3更复杂，但是策略之间的断点可以相当精确地计算出来，这样每次都会选择最有可能的有效策略)。

我只是含糊其辞地尝试在集合中保存数字之间的差值。快速实验表明，它们实际上并不比我提到的策略有效得多，存在不可预测的退化情况，但最重要的是，我所使用的应用程序实际上不需要反序列化其数据，只需直接从磁盘(mmap)使用它。