Почему LZ77 DEFLATE использует кодировку Хаффмана для своего второго прохода вместо LZW? Есть ли что-то в оптимальной комбинации? Если да, какова природа вывода LZ77, что делает его более подходящим для сжатия Хаффмана, чем LZW или каким-либо другим методом?DEFLATE метод рассуждения
LZW пытается использовать повторяющиеся строки, как и первый «этап», как вы его называете, LZ77. Затем он плохо справляется с энтропией, кодирующей эту информацию. LZW был полностью вытеснен более современными подходами. (За исключением его устаревшего использования в формате GIF.) Как только LZ77 генерирует список литералов и совпадений, LZW не сможет воспользоваться, и тогда он сделает почти полностью неэффективный энтропийный кодер для этой информации.
Существуют ли другие методы сжатия, которые будут выполнять ту же роль, что и кодировка Хаффмана, что означает использование высоких частот символов? Действительно ли кодировка Хаффмана оказалась оптимальной? –
Да, есть еще несколько. Например. арифметическое кодирование, кодирование диапазона и энтропия конечного состояния обеспечивают лучшее сжатие за счет скорости. –
Почему производительность сжатия более ценна, чем размер сжатия? Отлична ли разница в производительности? Кроме того, спасибо, я рассмотрю эти другие методы. –
Mark Adler could best answer this question.
Детали того, как LZ77 и Хаффмана работать вместе нуждаются в более тщательного изучения. После того как необработанные данные были преобразованы в строку символов и специальную длину, пары расстояний, эти элементы должны быть представлены кодами Хаффмана.
Хотя это НЕ, повторите, НЕ стандартную терминологию, вызовите точку, в которой мы начинаем считывать в битах «гудок». В конце концов, по нашей аналогии, тональный сигнал ответа - это то, где вы можете начать указывать серию чисел, которые будут отображаться на определенном телефоне. Поэтому назовите самое начало «гудка». При этом тональном сигнале может следовать одна из трех: символ, пара длины или конец блока. Поскольку мы должны быть в состоянии сказать, что это такое, все возможные символы («литералы»), элементы, которые указывают диапазоны возможных длин («длины») и специальный индикатор конца блока, объединены в один алфавит , Тогда этот алфавит становится основой дерева Хаффмана. Расстояния не обязательно должны быть включены в этот алфавит, так как они могут появляться только после длин. Как только литерал был декодирован или парная длина-длина декодирована, мы находимся в другой точке «тонального набора», и мы снова начинаем читать. Если мы получили символ конца блока, конечно, мы либо находимся в начале другого блока, либо в конце сжатых данных.
Коды длины или коды расстояний могут фактически быть кодом, который представляет базовое значение, за которым следуют дополнительные биты, которые образуют целое число, добавляемое к базовому значению.
...
Длинная короткая история. LZ77 обеспечивает дублирование. Кодировка Хаффмана обеспечивает сокращение бит. It's also on the wiki.
Они могли бы пойти для кодировщика диапазона как бэкэнд (но он медленнее, и было бы немного раздражать, чтобы поместить эти биты расширения внутри потока битов), или сегодня, вероятно, ANS. – harold