纯文本压缩算法的当前状态是什么？

Question

为了纪念Hutter奖,文本压缩的顶级算法(以及每个算法的快速描述)是什么？

注意:这个问题的目的是获得压缩算法的描述,而不是压缩程序的描述.

Answer 1

边界推动压缩机结合了疯狂结果的算法.常用算法包括:

• 在Burrows-Wheeler变换和此处 -洗牌字符(或其他比特块)与可预测的算法,以增加重复块这使得源更容易压缩.解压缩正常发生,结果与反向变换无混淆.注意:仅BWT实际上并不压缩任何东西.它只是使源更容易压缩.
• 部分匹配预测(PPM) - 算术编码的演变,其中预测模型(上下文)是通过处理源的统计信息与使用静态概率来创建的.尽管它的根源是算术编码,但结果可以用霍夫曼编码或字典以及算术编码来表示.
• 上下文混合 - 算术编码使用静态上下文进行预测,PPM动态选择单个上下文,上下文混合使用许多上下文并权衡其结果.PAQ使用上下文混合.这是一个高级概述.
• 动态马尔可夫压缩 - 与PPM相关但使用位级上下文与字节或更长时间.
• 此外,Hutter奖项参赛者可以用来自外部词典的小字节条目替换普通文本,并使用特殊符号区分大小写文本,而不是使用两个不同的条目.这就是为什么他们擅长压缩文本(特别是ASCII文本)而不是一般压缩的价值.

Maximum Compression是一个非常酷的文本和通用压缩基准站点.Matt Mahoney发布了另一个基准.Mahoney可能特别感兴趣,因为它列出了每个条目使用的主要算法.

Answer 2

总是有lzip。

除了开玩笑：

• 在考虑兼容性的情况下，PKZIP（DEFLATE算法）仍然是赢家。
• bzip2是享受相对广泛的安装基础和相当不错的压缩率之间的最佳折衷方案，但是需要单独的存档器。
• 7-Zip（LZMA算法）压缩效果非常好，可用于LGPL。但是，很少有带有内置支持的操作系统。
• rzip是bzip2的变体，我认为值得更多关注。对于需要长期归档的大型日志文件而言，这可能特别有趣。它还需要一个单独的存档器。