信息压缩修复了霍夫曼效率低下的问题



例如,考虑一个由 7 个换行符组成的文件(字节 [0x0A、0x0A、0x0A、0x0A、0x0A、0x0A、0x0A](。 使用 zip 的 Info-ZIP 实现(随 OSX 和其他操作系统一起提供(创建 zip 文件,该文件以固定的霍夫曼模式(模式 01(存储。 文件数据块中的字节为:

0xE3 0xE2 0x02 0x03 0x00

根据位,有一个块(第一个标头将最后一个块位设置为 true(。

块中的第一个代码是文字0x0A(接下来的 7 位编码0x5C,下面是 0(。 块中的第二个代码是文字0x0A,块中的第三个代码表示距离为 1 的 5 个字节的副本。

如果我正确理解操作,则不会复制第一个文字。 逐个字节,使用 * 标记要复制到末尾的字节,操作是:

[0x0A *0x0A]                          ->  [0x0A  0x0A  0x0A]
[0x0A  0x0A *0x0A]                    ->  [0x0A  0x0A  0x0A *0x0A]
[0x0A  0x0A  0x0A *0x0A]              ->  [0x0A  0x0A  0x0A  0x0A *0x0A]
[0x0A  0x0A  0x0A  0x0A *0x0A]        ->  [0x0A  0x0A  0x0A  0x0A  0x0A *0x0A]
[0x0A  0x0A  0x0A  0x0A  0x0A *0x0A]  ->  [0x0A  0x0A  0x0A  0x0A  0x0A  0x0A *0x0A]

问题:从图中应该清楚地看出第一个字节没有被复制。 最有效的编码只需要两个代码:文字0x0A和距离为 1 的 6 个字节的副本。 是否有原因(例如另一个实现中的错误(为什么不应该使用更有效的编码?

deflate.c

/* Stop when cur_match becomes <= limit. To simplify the code,
 * we prevent matches with the string of window index 0.
 */

相关内容

  • 没有找到相关文章

最新更新