在数据库字段和信息检索中，存在一个非常常见的场景。我有一个我想要存储的（分类）整数的列表，我希望尽可能高效地这样做。有几十种方法这样做，这是一个研究的热门话题。这是如此有用，因为您可以在排序的整数列表中运行这么多的地方，并获得大量优势。与通用压缩例程不同，我们通常可以利用我们理解我们试图与之合作的数据并获得更好结果的事实。
我需要压缩整数的原因（实际上，Int64值）是我试图跟踪一些数据的匹配，因此我跟踪的整数实际上是用户在Voron内部的数据偏移量。这导致了一些不同的场景，我必须处理：
我正在尝试弄清楚以尽可能高效的方式存储后面的两个选项的最佳方法。
第一个停止是Daniel Lemire的博客，自然地，因为他已经广泛写了这篇文章。我看了以下方案：FastPFOR和StreamVByte。它们具有稍微不同的目的，但基本上，FastP将使用位流，而StreamVbyte使用的字节导向模式。从理论上讲，您可以从Fastp for获得更好的压缩率，但StreamVByte应该更快。另一个整数压缩系统来自Facebook的大猩猩纸，这是一个更大的方案，包括时间序列值压缩。但是，该方案的一部分会谈论如何压缩整数（它们使用它来存储特定操作的刻度）。我们实际上是在RavendB内部的时间序列支持。
我不会覆盖深度，这里是大猩猩压缩的论文，相关描述在4.1.1节。足以说他们正在使用比特流和Deltas计算的三角洲。基本上，如果保持相同距离的值，则无需录制所有值，您可以自然地计算。在最佳情况下，Gorilla压缩需要每个值的单个比特，假设结果类似地间隔。
为我的目的，我希望尽可能高的压缩率，我需要只存储整数列表。大猩猩压缩的问题是，如果我们没有获得相同距离的数字，我们需要记录它们不同的金额。这意味着，至少，我们每张值至少需要9位。这令人遗憾地增加了。
另一方面，对于POR，有一个不同的系统。 PFOR计算批量整数所需的最大位数，然后录制这些值。我发现本文中的二进制包装部分（2.6）是最明确的解释，这是如何完成的。但是，POR的问题是，如果您有一个大的异常值，则会不必要地浪费大量的比特。
我决定看看我是否可以为此做点什么，并创建一个在一次批量的128个整数上工作的编码器。这个编码器将：
检查录制整数的增量所需的最大位数。沿着已经拯救了我们很多。
然后我们检查批处理的顶部和底部半数，看看我们是否会获得单独录制它们的好处。在这种情况下，将独立地记录到批处理中的一部分的单个大值（或其中一组）。
最后，如果我们还会分析我们进一步的批次，而不是仅记录有意义的位范围。这个想法是尝试在批处理中找到具有相同距离彼此相同的范围。我们可以将这些产品编码为重复而不是每个独立值。这最终可以节省令人惊讶的空间。
您可以在此处查看研究结果。我会注意你这是原始的，但结果很有希望。我能够通过一点击败（在压缩率方面）标准PFOR实现，代码较少。
我也在查看逼真的数据集的压缩率为30％ - 40％。如果数据正确设置，我能够利用重复的三角形优化，我可以紧紧包装。
目前，据说我可以在8KB缓冲区中向上推出10,000 int64值，而没有任何重复的Δ。如果我可以充分利用Deltas，它可以在8KB缓冲区中进入500,000 int64值。
我经常提及三角洲的原因，我很可能会录制大小相同的值，因此我们将获得彼此相同的空间的抵消。 在这种情况下，我的编码器进入镇，压缩率基本上是疯狂的。 这是一小部分更大的工作，但这是我第一次在Voron的水平上代码。 这很好玩。