Рассуждение метода DEFLATE
Почему LZ77 DEFLATE использует кодировку Хаффмана для второго прохода вместо LZW? Есть ли в их комбинации что-то оптимальное? Если да, то каков характер вывода LZ77, который делает его более подходящим для сжатия Хаффмана, чем LZW или какой-либо другой метод полностью?
2 ответа
LZW пытается использовать преимущества повторяющихся строк, как первая "сцена", как вы ее называете LZ77. Затем он плохо справляется с энтропийным кодированием этой информации. LZW был полностью вытеснен более современными подходами. (За исключением его унаследованного использования в формате GIF.) Как только LZ77 сгенерирует список литералов и совпадений, для LZW ничего не останется, чтобы воспользоваться этим, и тогда он сделает почти полностью неэффективный энтропийный кодер для этой информации.
Детали того, как LZ77 и Хаффман работают вместе, требуют более тщательного изучения. После того, как необработанные данные были превращены в строку символов и пар особой длины, расстояния, эти элементы должны быть представлены кодами Хаффмана.
Хотя это НЕ, повторяю, НЕ стандартная терминология, назовите точку, в которой мы начинаем читать в битах, "тональный сигнал". В конце концов, по нашей аналогии, тональный сигнал готовности - это место, где вы можете начать указывать серию номеров, которые в конечном итоге будут привязаны к конкретному телефону. Так что назовите самое начало "тональным сигналом". При этом тональном сигнале может следовать одно из трех: символ, пара длина-расстояние или конец блока. Поскольку мы должны знать, что это, все возможные символы ("литералы"), элементы, указывающие диапазоны возможных длин ("длины"), и специальный индикатор конца блока объединены в один алфавит, Этот алфавит становится основой дерева Хаффмана. Расстояния не должны быть включены в этот алфавит, так как они могут появляться только после длин. После того, как литерал был декодирован или пара длина-расстояние декодирована, мы находимся в другой точке "тонального сигнала" и начинаем читать снова. Если мы получили символ конца блока, конечно, мы либо в начале другого блока, либо в конце сжатых данных.
Коды длины или коды расстояния могут фактически быть кодом, который представляет базовое значение, за которым следуют дополнительные биты, которые образуют целое число, которое будет добавлено к базовому значению.
...
Короче. LZ77 обеспечивает удаление дубликатов. Кодирование Хаффмана обеспечивает уменьшение битов. Это также в вики.