最佳压缩算法？(最佳的定义见下文)

Question

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

• 最小压缩尺寸
• 最快脱模/压缩
• 权衡最佳(折中曲线的“膝盖”)

我的数据如下：

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

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

Answer 1

由于“时间”int可以彼此接近，所以尝试只存储第一个和之后的差异，将差异保存到int之前(增量编码)。对于第二个int，您也可以尝试同样的方法。

您可以尝试的另一件事是重新组织来自int1，int2，double，int1，int2，double.int1，int1.，int2，int2.，double，double.

为了找出结果的压缩范围，您可以将数据写入文件并从Christian Martelock 这里下载压缩器CCM。我发现它对于这样的数据收集非常好。它使用了相当快的语境混合算法。您还可以将其与其他压缩器(如WinZIP )进行比较，也可以使用像zLib这样的压缩库来确定是否值得。

Answer 2

如果我正确地阅读了这个问题，你只需要有效地存储数据。显然，像压缩xml这样的简单选项很简单，但是有更直接的二进制序列化方法。谷歌的协议缓冲器是其中一个突飞猛进的概念。

例如，在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;}
}

然后，通过Foo[]类反序列化一个列表或ProtoBuf.Serializer等。

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

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

Answer 3

大多数压缩算法在这类数据上同样不起作用。但是，在将数据输入gzip或类似于算法之前，您可以做一些事情(“预处理”)来增加数据的可压缩性。尝试以下几点：

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

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

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

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