0

根据DEFLATE 规范：

  1. 压缩表示概述

压缩数据集由一系列块组成，对应于输入数据的连续块。块大小是任意的，但不可压缩块限制为 65,535 字节。

每个块都使用 LZ77 算法和 Huffman 编码的组合进行压缩。每个块的霍夫曼树独立于前一个或后一个块的霍夫曼树；LZ77 算法可以使用对出现在前一个块中的重复字符串的引用，之前最多 32K 输入字节。

每个块由两部分组成：一对描述压缩数据部分表示的霍夫曼代码树，以及一个压缩数据部分。（霍夫曼树本身是使用霍夫曼编码压缩的。）压缩数据由两种类型的一系列元素组成：文字字节（在之前的 32K 输入字节中未被检测为重复的字符串）和指向重复字符串的指针，其中指针表示为一对<长度，向后距离>。“deflate”格式中使用的表示将距离限制为 32K 字节，长度限制为 258 字节，但不限制块的大小，但不可压缩块除外，如上所述受到限制。

所以指向重复字符串的指针只能返回 32 KiB，但由于块大小不受限制，Huffman 代码树是否可以将两个超过 32 KiB 的重复字符串存储为相同的代码？那么限制因素是块大小吗？

4

2 回答 2

1

距离的霍夫曼树包含代码 0 到 29（下表）；代码 29，后跟“普通”位中的 8191，表示“距离 32768”。这是 Deflate 定义中的硬性限制。块大小不受限制。实际上块大小没有存储在任何地方：块是一个无限流。如果您想停止阻止，请为此发送一个 End-Of-Block 代码。

                             Distance Codes
                             --------------
       Extra           Extra             Extra               Extra
  Code Bits Dist  Code Bits  Dist   Code Bits Distance  Code Bits Distance
  ---- ---- ----  ---- ---- ------  ---- ---- --------  ---- ---- --------
    0   0    1      8   3   17-24    16    7  257-384    24   11  4097-6144
    1   0    2      9   3   25-32    17    7  385-512    25   11  6145-8192
    2   0    3     10   4   33-48    18    8  513-768    26   12  8193-12288
    3   0    4     11   4   49-64    19    8  769-1024   27   12 12289-16384
    4   1   5,6    12   5   65-96    20    9 1025-1536   28   13 16385-24576
    5   1   7,8    13   5   97-128   21    9 1537-2048   29   13 24577-32768
    6   2   9-12   14   6  129-192   22   10 2049-3072
    7   2  13-16   15   6  193-256   23   10 3073-4096
于 2020-07-10T06:41:00.927 回答
1

为了补充 Zerte 的答案，对先前序列的引用与块或块边界无关。这样的引用可以在块内，跨块，并且被引用的序列可以跨越块边界。

于 2020-07-10T22:28:50.430 回答