4

我一直在研究 RFC 1951（DEFLATE 压缩算法），发现了 Mark Adler 的有趣的“学习”源文件，名字很可爱——puff.c。虽然通过合理地遵循 RFC-1951 规范，大脑解析该文件是一种启发性的体验，但作者做了一些我不太清楚的事情——他改变了索引长度数组的顺序。

代码注释中的解释有点模糊：

码长码长按置换顺序接收（参见下面的 order[] 数组），以便更可能生成短码长码长列表。事实证明，在动态代码描述中不太可能看到非常短和非常长的代码，因此最初可能看起来是一种特殊的顺序。

这是楼上描述的排列数组：

static const short order[19] =      /* permutation of code length codes */
        {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};

所以，我的问题是：

  • 为什么在 RFC-1951 中没有提到这一点？
  • 他们如何决定 中列出的确切排列order？
  • 它是如何工作的？由于顺序已更改，为什么解码过程不会失败？

非常感谢。这不是作业，我也不是为了学习经验而试图超越原始算法。我搜索了这个网站，谷歌是我的朋友，但无济于事。

4

1 回答 1

3

它在RFC 1951中：

       (HCLEN + 4) x 3 bits: code lengths for the code length
          alphabet given just above, in the order: 16, 17, 18,
          0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15

如果您尝试更改它，解码过程将失败（在放气端也不更改它，在这种情况下，它不能再称为放气）。

最可能使用的代码长度代码在列表的前面，最不可能在列表的后面。这允许列表在大多数情况下更短，因此HCLEN更小，每个不存在的列表项节省三位。

于 2013-05-25T14:46:55.577 回答