代码之家 › 专栏 › 技术社区 › James McMahon

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

compression algorithm

James McMahon · 技术社区 · 16 年前

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

最小压缩大小
最快的去/压缩
权衡最优(权衡曲线的拐点)

我的数据如下:

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

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

6 回复 | 直到 13 年前

schnaader 13 年前

因为“时间”整数可以彼此接近,所以尝试只存储第一个整数,然后将差异保存到之前的整数(增量编码)。第二个int也可以尝试相同的方法。

您可以尝试的另一件事是重新组织来自[int1,int2,double],[int1,int2,double]的数据。到[int1,int1…],[int2,int2…],[双,双…]。

为了找出结果所处的压缩范围,您可以将数据写入文件并从Christian Martelok下载压缩器CCM。 here . 我发现对于这种数据收集来说,它的性能非常好。它用得相当快 context mixing 算法。您还可以将其与其他压缩器(如winzip)进行比较,或者使用zlib这样的压缩库来查看是否值得这样做。

ididak 16 年前

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

这不会给您最好的压缩比,但通常是最快的编码/解码吞吐量。

Marc Gravell 16 年前

如果我正确地阅读了这个问题,您只需要高效地存储数据。显然,像压缩XML这样的简单选项很简单,但是有更多直接的二进制序列化方法。一个是谷歌的 protocol buffers .

例如,在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类[de]序列化列表或foo[]等。

我不是说会 相当地 空间效率和你自己滚动一样高,但它会非常接近。协议缓冲区规范很好地利用了空间(例如,对整数使用base-128,这样小数字占用的空间就更少)。但是尝试它很简单,不需要自己编写所有的序列化代码。

这种方法不仅易于实现,而且还具有其他体系结构易于使用的优点,因为有针对 various languages . 它还比常规的[de]压缩(gzip/deflate/etc)和/或基于XML的序列化使用更少的CPU。

Gilles 16 年前

按已建议排序,然后存储

(第一批) (第二批) (双打)

转置矩阵。然后压缩

Stephan Leclercq 16 年前

大多数压缩算法在这类数据上也会同样糟糕。但是,在将数据提供给gzip或deflate-like算法之前,您可以做一些事情(“预处理”)来增加数据的可压缩性。尝试以下操作:

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

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

然后,假设测量值在时间上是稳定的,用之前相同传感器读数的增量替换所有读数。同样,大多数值将接近于零,因此更具可压缩性。

另外,由于浮点值的内部表示,它们是非常不好的压缩候选者。尝试将它们转换为整数。例如,温度读数最有可能不需要超过两位小数。将值乘以100,然后四舍五入到最接近的整数。

community wiki 4 revs, 2 users 83% Hanno Fietz 7 年前

很好的答案,据我所知,我将把那些我投赞成票的合并到我最终使用的方法中:

对数据进行排序和重新组织,使相似的数字相邻,即先按ID排序,然后按时间戳排序,然后按 (<int1>, <int2>, <double>), ... 到 ([<int1>, <int1> ...], [<int2>, <int2> ... ], [<double>, <double> ...]) (根据建议 schnaader 和 Stephan Leclercq
按照建议,在时间戳(可能在其他值上)上使用增量编码施纳德和 ididak
使用协议缓冲区进行序列化(我无论如何都要在应用程序中使用它们,这样就不会添加依赖项或任何内容)。多亏了 Marc Gravell 因为我指了指。