Ограничения размера на DEFLATE деревья Хаффмана

Question

Чтение через RF C 1951, кажется, что это действительный динамический c Дерево Хаффмана не обязательно является полным двоичным деревом - например, дерево, указанное длиной в битах (2, 2, 2), имеет узел с одним дочерним элементом:

    ____
   /    \
  0      1
 / \    /
0   1  0

Это вызывает проблему при попытке выделить достаточно памяти для всего дерева за одно выделение, так как не обязательно существует верхняя граница количества узлов в произвольном двоичном дереве .

Подразумевают ли ограничения в стандарте DEFLATE верхнюю границу размера динамического c дерева Хаффмана?

Answer 1

RF C 1951 определяет «код Хаффмана» как то, что вырабатывается при построении оптимального префиксного кода. Следовательно, коды Хаффмана, используемые в допустимом потоке спуска, должны быть полными, чтобы быть оптимальными. В вашем примере нет, с неиспользованным кодом 11. Код 1-2-2 будет полным, без неиспользованных кодов.

Есть одно исключение из этого правила в RF C 1951, которое состоит в том, что одиночный дистанционный код кодируется как однобитный, ненулевые биты:

Если используется только один дистанционный код, он кодируется с использованием одного бита, а не нулевых битов; в этом случае длина кода равна единице, с одним неиспользованным кодом.

inflate zlib отклоняет любой поток deflate с недопустимым кодом Хаффмана.

Есть еще одна тонкость, то есть коды Хаффмана в deflate ограничены по длине до 15 битов, что принудительно применяется при кодировании кодов. Это не меняет того факта, что коды должны быть полными.

Для полного префиксного кода количество внутренних узлов составляет n-1 , где n - количество закодированных символов.

Из-за тонкости ограничения длины существует ограничение на количество узлов даже для неоптимальных префиксных кодов. В худшем случае всем символам будет назначено максимальное количество битов. Затем просто постройте дерево и посчитайте узлы. В итоге вы получите плоское кодовое дерево для символов, основание которого подключено к root с линией узлов с одной ветвью к root. Так что на самом деле не намного больше узлов, чем для оптимального префиксного кода, из-за способа построения канонического кода.

Например, если все 30 кодов расстояния имеют длину 15, каноническое дерево выглядит следующим образом:

дерево с длинным стволом

Вместо 29 внутренних узлов для оптимального кода префикса у этого есть 40 внутренних узлов.