压缩排序的整数

我正在构建一个索引,它只是在二进制文件中连续存储的几组有序32位整数.问题是这个文件变得非常大.我一直在考虑添加一些压缩方案,但这有点超出我的专业知识.所以我想知道,在这种情况下哪种压缩算法效果最好？此外,解压缩必须很快,因为该索引将用于进行查找.

如果你存储的是紧密相连的整数(例如:1,3,4,5,9,10等......)而不是一些随机的32位整数(982346 ...,3487623412 ..等),你可以做一件事:

找出相邻数字之间的差异,如2,1,1,4,1 ...等(在我们的例子中),然后霍夫曼编码这个数字.

如果你直接将它们应用到你拥有的原始数字列表中,我认为霍夫曼编码不会起作用.

但是如果你有一个近似数字的排序列表,你可以通过对数字差异进行霍夫曼编码来获得非常好的压缩比,这可能比使用Zip库中使用的LZW算法更好.

无论如何,感谢发布这个有趣的问题.

整数是以密集方式还是以稀疏方式分组的？

密集的我指的是:

[1, 2, 3, 4, 42, 43, 78, 79, 80, 81]

稀疏我指的是:

[1, 4, 7, 9, 19, 42, 53, 55, 78, 80]

如果整数以密集方式分组,则可以压缩第一个向量以包含三个范围:

[(1, 4), (42, 43), (78, 81)]

这是40%的压缩.当然,该算法在稀疏数据上不能很好地工作,因为压缩数据占用的空间比原始数据多100%.

正如您所发现的,N 32位整数的排序序列没有32*N位数据.这并不奇怪.假设没有重复,每个排序的序列都有N!未排序的seqeuences包含相同的整数.

现在,您如何利用排序序列中的有限信息？许多压缩算法的基础是使用较短的位串来实现常见的输入值(Huffman只使用这种技巧).几张海报已经建议计算数字之间的差异,并压缩这些差异.他们假设它将是一系列小数字,其中许多将是相同的.在这种情况下,差异序列将被大多数算法很好地压缩.

但是,采取斐波纳契数列.这肯定是排序整数.F(n)和F(n + 1)之间的差异是F(n-1).因此,压缩差异序列等同于压缩序列本身 - 它根本没有帮助!

所以,我们真正需要的是输入数据的统计模型.给定序列N [0] ... N [x],N [x + 1]的概率分布是多少？我们知道P(N [x + 1]