DEFLATE: структура динамического блока

Question

Я пытаюсь построить явный пример динамического блока.Пожалуйста, дайте мне знать, если это не так.

Рассматривая этот пример букв алфавита:

A (0), B (0), C (1), D (0),E (2), F (2), G (2), H (2) и остальные символы, имеющие нулевую длину кода.

Последовательность (SQ) длин кода будет 0 ..., 0,0,1,0,2,2,2,2, ... 0.

Тогда мыпридется сжимать его дальше с кодированием по длине прогона.Таким образом, мы должны вычислить количество повторений и либо использовать флаг 16, чтобы скопировать предыдущую длину кода, либо 17 или 18, чтобы повторить длину кода 0 (используя дополнительные биты).

Моя проблема в этом.После отправки информации заголовка и последовательности длин кода в правильном порядке 16, 17, 18, ... следующая последовательность информации будет выглядеть примерно так:

18, значение некоторых дополнительных битов1,0,2,16, некоторые дополнительные биты имеют значение 0,18, некоторые дополнительные биты имеют значение.(Вероятно, будет еще 18 флагов, поскольку максимальное число повторов равно 138.)

Затем мы имеем то же самое с алфавитом расстояния и, наконец, входными данными, закодированными с помощью канонического Хаффмана, и дополнительными битами, если необходимо.

1. Нужно ли отправлять коды длиной 0?Если да, то почему?

2. Если да, то почему необходимо иметь hclit и hcdist, а не только hclen, зная, что длины последовательностей равны 286 для lit / len и 30 длярасстояния?

3. Если нет, то каким будет реальное решение?

Еще одна проблема:

В этом случае у нас есть коддлина 2 с повторениями (3) значение дополнительных битов 0.

Включено ли это последнее число в конструкцию дерева длины кода?

Если да, я не могу понять, как: флаг 18 имеет следующее максимально возможное значение дополнительных битов 127 (1111111), представляющее138 повторений, и оно не может быть включено в символы алфавита 0-18.

PS Когда я говорю дополнительные биты в этом случае, я имею в виду фактор, который используется, чтобы знать, сколько повторений предыдущей длиныиспользуются.

Точнее 0 - 15 у нас 0-битный коэффициент повторения, для 16,17,18 у нас 2,3,7-битный коэффициент повторения.Значение этих битов - это то, что я имею в виду, имея значение дополнительных битов.

Я думаю, что мне чего-то не хватает в том, что коды Хаффмана генерируются алфавитом длины кода Хаффмана.

Answer 1

Во-первых, ваш пример кода недействителен, так как он переподписывает доступные битовые комбинации.2,2,2,2 будет использовать все битовые комбинации, так как существует только четыре возможных двухбитовых схемы.Вы не можете иметь еще один код любой длины.Возможные допустимые коды для пяти символов: 1,2,3,4,4 или 2,2,2,3,3.

. Чтобы ответить на ваши вопросы по порядку:

1. Вам нужно отправить начальные нули, но вам не нужно отправлять конечные нули.Счетчики HLIT и HDIST определяют, сколько длин каждого типа кода находится в заголовке, где любая из них считается равной нулю.Вам необходимо отправить нули, так как длины кода связаны с соответствующим символом по их позиции в списке.

2. Это экономит место в заголовке, чтобы иметь счетчики HLIT и HDIST, поэтомучто вам не нужно указывать длины для всех 316 кодов в каждом заголовке.

3. Я не понимаю этого вопроса, но, полагаю, он не применим.

4. Если я понимаю ваш вопрос, дополнительные биты не имеют никакого отношения к описаниям кодов Хаффмана в заголовках.Дополнительные биты подразумеваются символом.В любом случае повторяющаяся длина кодируется кодом 16, а не кодом 18. Таким образом, четыре двойки будут закодированы как 2, 16 (0), где (0) представляет два дополнительных бита, которые являются нулями.