1

我正在对 Gameboy Advance 的游戏进行逆向工程，我注意到原始开发人员编写的代码有两个系统调用来使用 Huffman 和 lz77（按此顺序）解压缩关卡。

但是为什么要使用霍夫曼+ lzZ7？这种方法有什么好处？

4

1 回答 1

3

使用可用的库

开发人员可能正在使用 DEFLATE（或一些类似的算法），只是为了能够重复使用经过测试和调试的软件，而不是从头开始编写新的东西（并且花费不知道多长时间来测试和修复所有古怪的边缘情况）。

为什么是霍夫曼和 LZ77？

但为什么 DEFLATE、Zstandard、LZHAM、LZHUF、LZH 等同时使用 Huffman 和 LZ77？

因为这两种算法检测并消除了许多数据文件（视频游戏关卡、英语和其他自然语言文本等）共有的两种不同类型的冗余，并且它们可以结合使用以获得比单独使用任何一种更好的网络压缩。（不幸的是，大多数数据压缩算法不能这样组合）。

细节

在英语中，两个最常见的字母（通常）是“e”，然后是“t”。那么最常见的一对是什么？您可能会猜到“ee”、“et”或“te”——不，是“th”。

LZ77 擅长检测和压缩这些常见单词和音节，这些单词和音节出现的频率远远超过您仅从字母频率所猜测的频率。

面向字母的 Huffman 擅长仅使用字母频率检测和压缩文件，但无法检测连续字母（常用词和音节）之间的相关性。

LZ77 将原始文件压缩成文字字母和“复制项”的中间序列。然后霍夫曼进一步压缩该中间序列。通常，如果我们跳过 LZ77 步骤并简单地 Huffman 压缩原始文件，这些“复制项”已经比原始子字符串短得多。霍夫曼在压缩中间序列中的文字字母的效果与压缩原始文件中的相同字母效果一样好。

所以这个两步过程已经创建了比单独的算法更小的文件。作为奖励，副本项目通常也经过 Huffman 压缩，以节省更多存储空间。

一般来说，大多数数据压缩软件都是由这两部分组成的。首先，他们通过“变换”或多次变换（也称为“去相关器”）运行原始数据，通常高度调整到正在压缩的特定类型数据中的特定类型冗余（JPEG 的 DCT 变换、MPEG 的运动补偿等。 ) 或调整到人类感知的限制（MP3 的听觉掩蔽等）。接下来，他们通过单个“熵编码器”（算术编码、霍夫曼编码或非对称数字系统编码）运行中间数据，这对于每种数据几乎都是相同的。

于 2019-10-24T21:24:42.363 回答