DEFLATE (RFC1951) динамическая неполная длина Хаффмана

Я изучал RFC1951 и 'puff.c', и у меня возник вопрос по поводу "неполной длины".

Насколько я могу судить, определение «динамической» кодовой таблицы Хаффмана, которая позволяет использовать больше кодов, чем указано в HLIT+257, приведет к ошибке, по крайней мере, для puff.c. Например, 'puff.c' выдает ошибку, если в качестве простого отладочного теста я должен использовать таблицу Хаффмана всех 9-битных кодов, чтобы определить только 257 lit/lens. Является ли этот результат преднамеренным или ошибкой? И могу ли я предположить, что любой "инфлятор" на основе библиотеки "zlib" будет выдавать такую ​​же ошибку?

Я не могу найти в RFC 1951 никакой спецификации, которая ТРЕБУЕТ использования достаточно строгого кода Хаффмана. Конечно, я вижу, что использование таблицы Хаффмана с «недостаточной подпиской» может быть неэффективным с точки зрения сжатия, но я не уверен, почему такую ​​таблицу следует запрещать использовать.

Мой интерес не просто гипотетический. Я действительно хочу использовать буквальный код Хаффмана с недостаточной подпиской (но НЕ приведенный выше пример) для сжатия некоторых изображений, специфичных для приложения, в файлы PNG. Но я хочу убедиться, что он будет работать с любым средством просмотра изображений PNG.


compression deflate data-compression
person codechimp    schedule 14.03.2016    source источник

Ответы (1)


arrow_upward
0
arrow_downward

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

zlib отклонит неполные или превышенные коды, за исключением особого случая, указанного в RFC:

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

Там разрешен неполный код 0 для одиночного символа с неиспользованным кодом 1.

(В этом, кстати, нет необходимости. Если есть только один символ расстояния, то вам не нужны никакие биты для его указания. Вы знаете, что этот символ расстояния должен использоваться любой длины. Если для этого символа нужны дополнительные биты, тогда эти дополнительные биты сразу следуют за длиной. Ну да ладно — в этом случае Фил Кац добавил лишний нулевой бит в каждое совпадение, и теперь мы застряли с ним.)

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

В дефляции есть еще одно исключение, заключающееся в том, что код с фиксированным литералом/длиной неполный, с двумя неиспользуемыми кодами в конце.

Суть в том, что нет, вы не сможете использовать неполный код в динамическом заголовке (за исключением особого случая) и ожидать, что zlib или любой совместимый декодер deflate сможет его декодировать.

Что касается того, почему эта строгость полезна, ограничения на динамические заголовки позволяют быстро обнаруживать потоки без дефляции или поврежденные потоки дефляции. Точно так же динамический заголовок без конечного кода не разрешен zlib, чтобы избежать случая фиктивного динамического заголовка, позволяющего декодировать любые последующие случайные биты навсегда, никогда не обнаруживая ошибки. Неиспользуемые фиксированные коды также помогают в этом отношении, поскольку в конечном итоге они вызывают ошибку при случайном вводе.

Кстати, если вы хотите определить фиксированный, полный код Хаффмана для вашего случая, это очень просто и уменьшит размер почти всех ваших кодов на один бит. Просто закодируйте восемь битов для символов 0..253, используя этот номер символа непосредственно в качестве кода (конечно, инвертируя биты), и девять битов для символов 254..257, используя коды 508..511 (биты инвертированы).

person Mark Adler    schedule 16.03.2016
comment
благодаря. Я согласен с вашей точкой зрения о формулировке спецификации и принимаю реальность. Но при всем уважении, что касается полезности, я не вижу аргументов в пользу БЫСТРОГО обнаружения коррупции. С полным кодом ЛЮБАЯ комбинация битовой последовательности создаст, казалось бы, действительный символ (символы). Обнаружение ошибки происходит только по преждевременному EOB или его отсутствию... или вашей контрольной сумме согласно RFC1950. С другой стороны, неполный код ДОЛЖЕН обеспечить быстрое обнаружение ошибок: быстрота пропорциональна неполноте. Действительно, ограниченное обнаружение ошибки в вашем puff.c иллюстрирует мою точку зрения. - person codechimp; 16.03.2016
comment
Но чтобы получить полный код, динамический заголовок должен удовлетворять ограничениям, которые почти никогда не будут выполняться для случайных данных. Таким образом, случайный ввод будет обнаружен в заголовке, и вы никогда не доберетесь до кодов. Гораздо быстрее. - person Mark Adler; 17.03.2016