Блог

Должно ли дерево кода Хаффмана в алгоритме Deflate быть полным деревом? Под полным деревом я подразумеваю, что каждый конечный узел всегда должен представлять один символ. Другими словами, последнему символу с самым длинным кодом будут присвоены все единицы.

Возьмем, к примеру, крайний случай: для 286 символов каждый символ кодируется 15-битным кодом, что возможно при общем кодировании дерева Хаффмана. Однако в этом случае существует 2 ^ 15 — 286 конечных узлов, которые не назначаются / не используются. Разрешено ли это в Deflate? У меня сложилось впечатление, что это не разрешено в Deflate, и дерево должно быть полным. Это правда?

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

Единственное исключение состоит в том, что если используется только один символ расстояния, он кодируется одним битом (нулем), а не нулевыми битами, оставляя один неиспользованный код (единственный бит равен единице).