您可以实现的随机二进制数据的最佳文件压缩是什么？

Question

具体来说,那里有哪些程序以及压缩率最高的程序？我试过谷歌搜索它,但似乎经验会胜过搜索结果,所以我问.

Answer 1

如果可以精确地指定文件大小,对于任何文件大小N,将精确地存在N ^或更小的2 ^(N + 1)-1个可能文件.为了将大小为X的文件映射到某个较小的大小Y,必须将一些大小为Y或更小的文件映射到大小为X或更大的文件.无损压缩可以起作用的唯一方法是,可以识别某些可能的文件比其他文件更可能; 在那种情况下,可能的文件将缩小,不太可能的文件将会增长.

举一个简单的例子,假设有人希望无损地存储一个文件,其中这些位是随机且独立的,但是不是50%的位被设置,只有33%是.如果两个位都清零,则可以通过取每对位来写压缩这样的文件,如果第一位被设置则为"10"而第二位不是,如果第二位被设置则为"110",第一次没有,如果两个位都已设置,则为"111".结果是每对比特将在44%的时间内成为一位,在22%的时间内成为两位,在33%的时间内成为三位.虽然一些数据串会增长,但其他数据会缩小; 收缩的对 - 如果概率分布如预期的那样 - 超过那些增长的那些(4/9文件会缩小一点,2/9会保持不变,3/9会增长,所以对将会平均缩小1/9位,文件平均缩小1/18 [因为1/9数字是每对比特数].

注意,如果这些位实际上具有50%的分布,那么只有25%的对将成为一位,25%将保持两位,50%将成为三位.因此,25%的比特会缩小,50%会增长,因此平均成对率将增长25%,文件将增长12.5%.盈亏平衡点将是约38.2%的比特被设定(两个减去黄金均值),这将使38.2%的比特对收缩并且增长百分比相同.

Answer 2

没有一种通用的最佳压缩算法.已经发明了不同的算法来处理不同的数据.

例如,JPEG压缩允许您压缩图像非常多,因为如果图像中的红色为0xFF或0xFE(通常),则无关紧要.但是,如果您尝试压缩文本文档,则此类更改将是灾难性的.

此外,即使在两种旨在处理相同类型数据的压缩算法之间,您的结果也会因您的数据而异.

示例:有时使用gzip tarball较小,有时使用bzip tarball较小.

最后,对于足够长度的真正随机数据,您的数据可能与原始数据的大小几乎相同(甚至更大).