一个文件可以压缩多less次?
我正在考虑压缩,看起来好像对可以应用它的压缩有一些限制,否则就是单个字节。
所以我的问题是,我可以在多less次压缩文件:
- 它没有变小?
- 该文件变得腐败?
这两点是相同还是不同?
收益递减点出现在哪里?
这些点怎么能find?
一般来说,我不是在谈论任何特定的algorithm或特定的文件。
对于无损压缩,只有通过重新压缩文件才能知道你能获得多less次的方法是尝试。 这将取决于压缩algorithm和您正在压缩的文件。
两个文件永远不会压缩到相同的输出,所以你不能下降到一个字节。 一个字节怎么能代表你可以解压到的所有文件?
第二次压缩有时起作用的原因是压缩algorithm不能做无所不知的完美压缩。 它需要做的工作和做它的时间之间有一个权衡。 您的文件正在从所有数据更改为关于您的数据和数据本身的数据的组合。
例
以游程编码(可能是最简单有用的压缩)为例。
04 04 04 04 43 43 43 43 51 52 11字节
该系列的字节可以压缩为:
[4] 04 [4] 43 [-2] 51 52 7字节(我把元数据放在括号内)
括号中的正数是重复计数,括号中的负数是发现下一个-n个字符的命令。
在这种情况下,我们可以尝试多一个压缩:
[3] 04 [-4] 43 fe 51 52 7字节(fe是你的-2被看作二补数据)
我们一无所获,我们将在下一次迭代中开始发展:
[-7] 03 04 fc 43 fe 51 52 8字节
一段时间我们会增长一个字节,但实际上会变得更糟。 一个字节只能将负数保存到-128。 当文件长度超过128字节时,我们将开始增长两个字节。 随着档案越来越大,增长会变得更糟。
对压缩程序 – 元数据有一个阻碍。 而且,对于真正的压缩机来说,这个标题还附在文件的开头。 这意味着最终文件将随着每个额外的压缩而开始增长。
RLE是一个起点。 如果您想了解更多信息,请参阅LZ77 (它回顾文件以查找模式)和LZ78 (它构build字典)。 像zip这样的压缩器通常会尝试多种algorithm,并使用最好的algorithm。
这里有一些我可以想到多个压缩工作的情况。
- 我在一个附带磁盘的Amiga杂志上工作。 当然,我们把盘子装到鳃上。 我们使用的工具之一,让你打包一个可执行文件,当它运行时,它解压缩并自行运行。 由于解压缩algorithm必须位于每个可执行文件中,因此必须小而简单。 我们经常通过压缩两次获得额外的收益。 在RAM中完成解压缩。 由于读取软盘的速度很慢,所以我们也经常增加速度!
- Microsoft支持对bmp文件进行RLE压缩。 而且,许多文字处理器都做了RLE编码。 通过更好的压缩机,RLE文件几乎总是可压缩的。
- 我工作的很多游戏都使用了一个小巧,快速的LZ77解压缩器。 如果你压缩一个大矩形的像素(特别是如果它有很多的背景颜色,或者如果它是一个animation),你可以经常压缩两次,效果很好。 (原因是什么?你只有很多位来指定回溯距离和长度,所以一个大的重复模式被编码成几块,这些块是高度可压缩的。)
通常这个限制是一个压缩。 一些algorithm导致较高的压缩比,而使用较差的algorithm和较好的algorithm通常会导致改进。 但首先使用好的algorithm是正确的做法。
对于一组给定的数据可以被压缩多less是有理论上的限制的。 要了解更多关于这个,你将不得不学习信息理论 。
通常对于大多数algorithm来说,压缩不止一次是没有用的。 不过有一个特例。
如果您有大量的重复文件,则zip格式将独立压缩,然后您可以压缩第一个zip文件以删除重复的zip信息。 具体来说,对于大小为108kb的7个相同的Excel文件,使用7-zip压缩它们会产生120kb的归档。 再次压缩导致18kb的档案。 过去你收益递减。
假设我们有一个N比特长的文件,我们想要无损压缩,以便恢复原始文件。 有2 ^ N个可能的文件长度为N位,所以我们的压缩algorithm必须将这些文件中的一个改为2 ^ N个可能的文件之一。 但是,我们不能用小于N的比特来表示2 ^ N个不同的文件。
因此,如果我们可以把一些文件压缩起来,那么我们必须有一些长度在压缩下的文件来平衡缩短的文件。
这意味着一个压缩algorithm只能压缩某些文件,而实际上却要延长一些。 这意味着,平均来说,压缩随机文件不能缩短它,但可能会延长它。
实际的压缩algorithm是可行的,因为我们通常不使用随机文件。 我们使用的大多数文件具有某种结构或其他属性,无论它们是文本或程序可执行文件还是有意义的图像。 通过使用一个好的压缩algorithm,我们可以大大缩短我们通常使用的types的文件。
但是,压缩文件不是这些types之一。 如果压缩algorithm好,大部分的结构和冗余都被挤掉了,剩下的就像是随机性。
正如我们所看到的,没有任何压缩algorithm可以有效地压缩随机文件,而且这也适用于随机文件。 因此,尝试重新压缩压缩文件不会显着缩短,并且可能会延长一些。
所以,一个压缩algorithm可以有效运行的正常次数是1次。
腐败只发生在我们谈论有损压缩时。 例如,您无法从JPEG文件中精确恢复图像。 这意味着JPEG压缩器可以可靠地缩短图像文件,但只能以不能完全恢复的代价。 我们通常愿意为图像做这个,但不是为了文本,特别是不可执行的文件。
在这种情况下,腐败就没有发生。 它开始时,你开始压缩它,并越来越糟糕,因为你压缩更多。 这就是为什么好的image processing程序可以让您指定在制作JPEG时需要多less压缩:所以您可以平衡图像质量和文件大小。 通过考虑文件大小(对于networking连接来说比networking连接更重要)的成本与通常降低的质量成本之间的关系,可以find停止点。 没有明显的正确答案。
如果algorithm好,通常压缩一次就足够了。
实际上,压缩多次可能会导致大小的增加
你的两点是不同的。
- 压缩重复进行,并没有减less尺寸的改善
是一个预期的理论条件 - 反复压缩导致腐败
很可能是实现中的错误(或者algorithm本身)
现在让我们看看一些例外或变化,
- 可以重复应用 encryption而不减小尺寸
(实际上有时会增加尺寸) 以增加安全性 - 图像,video或audio文件日益压缩
将会丢失数据 (从某种意义上讲,实际上会被“损坏”)
您可以根据需要多次压缩文件。 但是对于大多数压缩algorithm来说,第二次产生的压缩将是可以忽略的。
压缩(我认为无损)基本上意味着更简洁地expression一些东西。 例如
111111111111111
可以更精确地expression为
15 X '1'
这被称为游程编码。 计算机可以使用的另一种方法是在文件中查找定期重复的模式。
显然这些技术可以使用的数量是有限制的,例如游程编码不会受到影响
15 X '1'
因为没有重复的模式。 类似地,如果模式replace方法将长模式转换为3个char模式,重新应用它将几乎没有效果,因为剩余的重复模式将是3或更短。 通常,对已经压缩的文件应用压缩使得它稍微大一点,因为有各种开销。 对压缩比较差的文件应用良好的压缩效果通常不如仅应用好的压缩效果。
在文件没有变小之前,我可以压缩多less次?
一般来说, 甚至没有一个 。 无论使用哪种压缩algorithm,都必须始终存在一个根本不压缩的文件,否则通过相同的参数,您总是可以反复压缩,直到达到1个字节。
在文件损坏之前,我可以压缩多less次?
如果你用来压缩文件的程序完成了它的工作,文件永远不会损坏(当然我正在考虑无损压缩)。
这里是最终的压缩algorithm(在Python中),通过重复使用将压缩任何string的数字到0(这是留给读者如何应用这个字节的string)。
def compress(digitString): if digitString=="": raise "already as small as possible" currentLen=len(digitString) if digitString=="0"*currentLen: return "9"*(currentLen-1) n=str(long(digitString)-1); #convert to number and decrement newLen=len(n); return ("0"*(currentLen-newLen))+n; # add zeros to keep same length #test it x="12"; while not x=="": print x; x=compress(x)
程序输出12 11 10 09 08 07 06 05 04 03 02 01 00 9 8 7 6 5 4 3 2 1 0然后是空string。 它不会在每次传递时压缩string,但是只要足够的传递将任何数字string压缩到长度为零的string。 确保你写下你通过压缩机发送多less次,否则你将无法取回它。
你可以压缩无限的时间。 但是,第二次和以后的压缩通常只会产生比前一个大的文件。 所以压缩不止一次是没有意义的。
这是一个很好的问题。 您可以从不同的angular度查看文件。 也许你知道这个文件包含算术系列。 可以将其视为“字节”,“符号”或“样本”的数据stream。
有些答案可以给你“信息论”和“数理统计”请检查研究人员的专着是否有全面的了解:
A. Kolmogorov
S. Kullback
С. 香农
N. Wiener
信息论中的一个主要概念是熵 。 如果你有一个“字节”stream….该字节的熵不依赖于你的“字节”,或“采样”的值…如果仅由字节回收不同值的频率定义。 最大熵有地方是完全随机的数据stream。 当你的“字节”具有相同的值时,最小熵等于零。
它没有变小?
因此,熵是每个“字节”的最小位数,在向磁盘写入信息时需要使用这些位。 当然,如果你使用上帝的algorithm是这样的。 现实生活中的压缩无损启发式algorithm并非如此。
该文件变得腐败?
我不明白这个问题的意义。 您可以不写入位到磁盘,您将写入大小等于0位的磁盘损坏的文件。 当然,这是损坏的,但他的大小是零位。
使用“双表格或交叉matrix”的更高级的压缩技术的例子也消除了algorithm中的大量的不整齐的符号
[上一个例子]以游程编码(可能是最简单的有用压缩)为例。
04 04 04 04 43 43 43 43 51 52 11字节
该系列的字节可以压缩为:
[4] 04 [4] 43 [-2] 51 52 7字节(我把元数据放在括号内)
[转入] 04.43.51.52值4.4。** – 2压缩
使用Additonal Symbols作为替代值的进一步压缩
04.ABC值4.4。** – 2压缩
理论上,我们永远不会知道,这是一个永无止境的事情:
在计算机科学和math中,“完全就业定理”这个词已经被用来指一个定理,表示没有一个algorithm可以最佳地执行某些专业人员完成的特定任务。 这个名字的产生是因为这样一个定理确保了无止境的发现新技术来改善至less一些具体任务的完成方式。 例如,编译器编写者的完整就业定理指出,不存在像可certificate的完美尺寸优化编译器这样的事情,因为编译器的这种certificate必须检测非终止计算并将其减less到单指令无限循环。 因此,一个可certificate的完美尺寸优化编译器的存在将意味着解决暂停问题的一个解决scheme,而这个问题是不可能存在的 ,这使得certificate本身成为一个不可确定的问题。
(资源)
这一切都取决于algorithm。 换句话说,问题可以是一个文件可以使用这个algorithm先压缩多less次,然后这个下一个…