8

我想以压缩格式存储以下元组的列表，我想知道哪种算法给了我

  • 最小压缩尺寸
  • 最快的解压/压缩
  • 权衡最优（权衡曲线的“拐点”）

我的数据如下所示：

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

两个整数之一指的是一个时间点，很可能最终出现在一个列表中的数字彼此接近。另一个 int 表示一个抽象 id，并且这些值不太可能接近，尽管它们也不会是完全随机的。double 表示传感器读数，虽然这些值之间存在一些相关性，但它可能没有多大用处。

4

6 回答 6

4

由于“时间”整数可以彼此接近，因此请尝试仅存储第一个整数，然后将差异保存到之前的整数（增量编码）。您也可以对第二个 int 尝试相同的操作。

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

要找出结果的压缩范围，您可以将数据写入文件并从 Christian Martelock 下载压缩器CCM。我发现它对于此类数据收集表现得非常好。它使用了一种非常快速的上下文混合算法。您还可以将其与 WinZIP 等其他压缩器进行比较，或使用 zLib 等压缩库来查看是否值得。

于 2008-11-10T09:39:49.973 回答
2

如果我正确阅读了这个问题，那么您只是想有效地存储数据。显然压缩 xml 之类的简单选项很简单，但还有更直接的二进制序列化方法。想到的一个飞跃是 Google 的协议缓冲区。

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

[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 类 [de] 序列化 List 或 Foo[] 等。

我并不是说它会像滚动你自己的那样节省空间，但它会非常接近。协议缓冲区规范很好地利用了空间（例如，对整数使用 base-128，这样小的数字占用更少的空间）。但是尝试一下会很简单，不需要自己编写所有的序列化代码。

这种方法不仅易于实现，还具有易于从其他架构中使用的优点，因为有各种语言的协议缓冲区实现。它还使用比常规 [de] 压缩 (GZip/DEFLATE/etc) 和/或基于 xml 的序列化更少的 CPU。

于 2008-11-10T09:42:25.040 回答
2

大多数压缩算法对此类数据的效果同样糟糕。但是，您可以做一些事情（“预处理”）来增加数据的可压缩性，然后再将其提供给 gzip 或类似算法的 deflate。尝试以下操作：

首先，如果可能，按升序对元组进行排序。首先使用抽象 ID，然后使用时间戳。假设您有许多来自同一个传感器的读数，相似的 id 将被放在一起。

接下来，如果定期采取措施，则将时间戳替换为与前一个时间戳的差异（当然，传感器的第一个元组除外。）例如，如果所有措施都以 5 分钟的间隔进行，则两个时间戳之间的差值通常接近 300 秒。因此，时间戳字段将更加可压缩，因为大多数值都是相等的。

然后，假设测量值及时稳定，将所有读数替换为同一传感器先前读数的增量。同样，大多数值将接近于零，因此更可压缩。

此外，浮点值是非常糟糕的压缩候选，因为它们的内部表示。尝试将它们转换为整数。例如，温度读数很可能不需要超过两位小数。将值乘以 100 并四舍五入到最接近的整数。

于 2008-11-10T09:47:37.087 回答
2

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

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

于 2008-11-10T09:51:26.940 回答
2

按照已经提出的排序，然后存储

（第一个整数）（第二个整数）（双打）

转置矩阵。然后压缩

于 2008-11-10T10:30:46.440 回答
0

很好的答案，记录在案，我将把我赞成的答案合并到我最终使用的方法中：

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

  2. 按照schnaader和ididak的建议，对时间戳（可能还有其他值）使用增量编码

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

于 2008-11-10T10:35:35.540 回答