31

为了纪念Hutter 奖，文本压缩的顶级算法（以及每种算法的简要说明）是什么？

注意：这个问题的目的是了解压缩算法，而不是压缩程序。

4

3 回答 3

28

边界推动压缩器结合了疯狂结果的算法。常用算法包括：

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

最大压缩是一个非常酷的文本和通用压缩基准站点。Matt Mahoney 发布了另一个基准。Mahoney's 可能特别有趣，因为它列出了每个条目使用的主要算法。

于 2008-10-26T18:37:57.790 回答
7

总是有lzip。

开个玩笑：

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

如果您想将 PAQ 用作程序，您可以在zpaq基于 debian 的系统上安装该软件包。用法是（另见man zpaq）

zpaq c archivename.zpaq file1 file2 file3

压缩到大约zip 文件大小的 1/10。（1.9M 对 15M）

于 2018-01-21T10:53:35.503 回答