谁能建议一种二进制压缩算法？

Question

我正在制作一个加壳器（运行时压缩）来研究Windows PE格式文件。我知道一些数据压缩算法，例如 RLE、LZW、霍夫曼编码等。但是哪种算法最适合压缩二进制数据（例如文件）.exe？谁能建议哪种算法是压缩二进制数据的最佳算法？

Answer 1

对于初学者，您应该从LZ77 或 LZ78 算法开始，它们提供相当好的压缩比和一个小的解压存根（显然，一个小的解压存根是加壳器的必备条件）。

LZ7x 算法之后是LZMA算法，它（通常）提供比 LZ7x 算法更好的压缩。

如果您以前从未编写过打包程序，我建议您主要使用低级语言（C 是事实上的语言）以 PIC（位置无关代码）风格编写解压存根，并在编写时使用汇编语言编写一些小部分需要。这样做的好处是让编译器为您完成大部分自相矛盾的工作（至少是第 1 点和第 2 点）：

1. 解压存根代码长度必须最小
2. 解压存根代码的速度必须是最佳的
3. 压缩和解压缩的内存使用必须保持在合理的范围内

然后，您可以根据需要调整输出组件，以便在上述各点之间取得良好的权衡。

一旦您对压缩理论有了很好的理解，您就应该明确地寻求实现PAQ派生的压缩器。

遵循 PAQ 领先优势有多种优势：

• 众所周知，它是多个领域（文本、图像和可执行文件，尽管每次都有不同的建模上下文）中最好的压缩器。请参阅此处和此处的各种基准。

• 它是开源的（并遵循 GPL 许可证）。

首先尝试特别关注 PAQ8PX 变体。不过，在生成的压缩 PE 文件中注入最小（长度）且快速的解压存根将是这项工作中最困难的部分。

PAQ 算法也被用在kkrunchy中，这是 Farbrausch demoscene 小组的著名 PE 压缩器。这里解释了对其内部结构的很好的了解。

最后，如果您不习惯数据压缩理论，我建议您首先阅读Matt Mahoney（PAQ 的作者）撰写的非常好的介绍性数据压缩解释以及有关数据压缩理论的 wiki 书籍。

请记住，压缩始终是一种权衡：最佳压缩比并不总是最终用户想要的。如果您需要 256 GB 内存或等待 5 分钟或需要解压 10 MB 字节的解压存根，这显然不是正确的路径...