Декомпрессия Хаффмана с использованием таблиц: максимальная длина кода?

Question

Я знаю, что zlib использует двухуровневую таблицу для поиска кодов Хаффмана при распаковке файла.Это имеет основополагающее предположение, что код Хаффмана для любого символа не будет длиннее 18 (9 + 9) бит ... Есть ли математическая причина для этого предположения?

Answer 1

Формат deflate ограничивает максимальную длину кода Хаффмана 15 битами.

Answer 2

Они должны каким-то образом ограничивать его во время сжатия.

Для прямого кодирования Хаффмана такого ограничения нет.

Патологический случай - это когда один символ встречается чаще, чем все остальные объединенные символы, а затем, для оставшихся символов, один символ встречается чаще, чем остальные объединенные, и так далее.Для символов размером в байт этот тип (крайне маловероятный) распределения даст длину кода Хаффмана 255 битов для двух наименее распространенных кодов.

(Расчет минимальной длины ввода, который имеет указанное выше свойство,оставлено как упражнение для читателя).