最佳压缩算法是什么？（下面有“最佳”定义）

Question

我希望以压缩格式存储以下元组列表，并想知道哪个算法可以给我：

• 最小的压缩大小
• 最快的解/压缩速度
• 权衡最优（“折线图”的拐点）

我的数据看起来像这样：

(<int>, <int>, <double>), 
(<int>, <int>, <double>), 
...
(<int>, <int>, <double>)

两个整数中的一个表示时间点，很可能在一个列表中的数字都比较接近。另一个整数代表一个抽象的ID，其值不太可能靠近，尽管它们也不是完全随机的。双精度浮点数表示传感器读数，虽然这些值之间存在一定的相关性，但可能没有太大用处。

- Hanno

Answer 1

由于“时间”int可能彼此接近，尝试仅存储第一个int，并在此之后将差异保存到前面的int中（delta编码）。您也可以尝试对第二个int执行相同的操作。

另一件可以尝试的事情是重新组织数据，从[int1，int2，double]，[int1，int2，double]...到[int1，int1...]，[int2，int2...]，[double，double...]。

要找出压缩范围，您可以将数据写入文件，然后从Christian Martelock下载压缩器CCM （这里）。我发现它对这样的数据集表现非常好。它使用了相当快速的上下文混合算法。您还可以将其与其他压缩程序（如WinZIP）进行比较，或使用压缩库（例如zLib）来确定是否值得努力。

- schnaader

Answer 2

大多数压缩算法对这样的数据效果都不佳。但是，在将其馈送给gzip或deflate类似算法之前，有一些事情（“预处理”）可以做以增加数据的可压缩性。请尝试以下操作：

首先，如果可能的话，请按升序对元组进行排序。首先使用抽象ID，然后再使用时间戳。假设您从同一个传感器中获得了许多读数，那么相似的id将被放置在一起。

接下来，如果测量是以固定间隔进行的，请用与上一个时间戳的差替换时间戳（当然，对于传感器的第一个元组除外）。例如，如果所有测量都以5分钟的间隔进行，则两个时间戳之间的差通常接近300秒。因此，时间戳字段将更易于压缩，因为大多数值都相等。

然后，假设测量值在时间上是稳定的，请将所有读数替换为与同一传感器的上一个读数的差。同样，大多数值将接近零，因此更易于压缩。

另外，由于其内部表示方式，浮点数非常不适合压缩。请尝试将它们转换为整数。例如，温度读数很可能不需要超过两个小数位。将值乘以100并四舍五入到最近的整数。

- Stephan Leclercq

Answer 3

这是大多数搜索引擎中使用的常见方案：存储值的增量并使用可变字节编码方案对增量进行编码，即如果增量小于128，则可以仅使用1个字节进行编码。有关详细信息，请参见Lucene和Protocol buffers中的vint。

这不会给您最佳压缩比，但通常会提供最快的编码/解码吞吐量。

- ididak

Answer 4

按照已经提出的排序方式进行排序，然后存储

(第一组整数) (第二组整数) (浮点数)

转置矩阵。然后压缩

- Gilles

Answer 5

如果我理解问题正确，您只是想高效地存储数据。显然，像压缩的XML之类的简单选项很简单，但还有更直接的二进制序列化方法。其中一个跳跃到脑海中的是Google的协议缓冲区。

例如，在C#中使用protobuf-net，您可以简单地创建一个类来保存数据：

[ProtoContract]
public class Foo {
    [ProtoMember(1)]
    public int Value1 {get;set;}
    [ProtoMember(2)]
    public int Value2 {get;set;}
    [ProtoMember(3)]
    public double Value3 {get;set;}
}

然后，只需通过 ProtoBuf.Serializer 类对 List 或 Foo[] 等进行序列化/反序列化。

我并不认为它的空间效率会像自己编写的代码一样高，但它会非常接近。协议缓冲区规范相当节省空间（例如，使用基于 128 位的整数表示，使得小数字占用更少的空间）。但是，你可以简单地尝试它，而无需编写所有序列化代码。

这种方法不仅易于实现，而且在其他架构中使用也很容易，因为有 各种语言 的协议缓冲实现。它还比常规压缩（GZip/DEFLATE 等）和基于 XML 的序列化少得多的 CPU 使用率。

- Marc Gravell

---

谢谢指出，我无论如何都会使用pb来序列化东西，所以在我的情况下这是一个自然的选择。你知道他们是否使用较短的序列压缩重复模式吗？如果不行的话，我也可以查看RTF规范。;-) - Hanno Fietz

不，它不能这样做。但是，如果您有特定的需求，可以创建一个 bytes 成员来存储使用 GZip 或其他方法压缩的数据。这超出了规范范围，因此客户端/服务器纯粹需要在细节上达成协议。 - Marc Gravell

好的，这意味着重新排列数据以获取每个元组成员的三个排序列表而不是一个3元组列表对我没有任何好处？ - Hanno Fietz

Answer 6

非常好的答案，记录一下，我将把我点赞的那些合并到我最终使用的方法中：

1. 对数据进行排序和重新组织，使相似的数字彼此相邻，即首先按id排序，然后按时间戳排序，并从(<int1>, <int2>, <double>), ...重新排列为([<int1>, <int1> ...], [<int2>, <int2> ... ], [<double>, <double> ...])（如schnaader和Stephan Leclercq所建议的）。

2. 像schnaader和ididak建议的那样，在时间戳上（也许在其他值上）使用增量编码。

3. 使用协议缓冲区进行序列化（我将在应用程序中使用它们，因此不会添加任何依赖项或其他内容）。感谢Marc Gravell指引我使用它。

- Hanno