Почему кодирование Хаффмана устраняет энтропию, чего не делает Лемпель-Зив?

13

Популярный алгоритм DEFLATE использует кодирование Хаффмана поверх Lempel-Ziv.

В общем, если у нас есть случайный источник данных (= 1 бит энтропии / бит), никакое кодирование, включая Хаффмана, скорее всего не сожмет его в среднем. Если бы Лемпель-Зив был «идеальным» (что подходит для большинства классов источников, поскольку длина уходит в бесконечность), пост-кодирование с Хаффманом не помогло бы. Конечно, Лемпель-Зив не идеален, по крайней мере, с конечной длиной, и поэтому сохраняется некоторая избыточность.

Именно эта оставшаяся избыточность частично устраняет кодирование Хаффмана и тем самым улучшает сжатие.

Мой вопрос: почему эта оставшаяся избыточность успешно устранена кодированием Хаффмана, а не LZ? Какие свойства Хаффмана против LZ делают это возможным? Будет ли простой запуск LZ (то есть кодирование сжатых данных LZ с помощью LZ во второй раз) завершить что-то подобное? Если нет, то почему нет? Аналогично, сначала будет работать сжатие с Хаффманом, а затем - с помощью LZ, а если нет, то почему?

ОБНОВЛЕНИЕ: Понятно, что даже после LZ некоторая избыточность сохранится. Несколько человек высказали это мнение. Что неясно: почему Хаффман лучше обращается к этой оставшейся избыточности, чем к LZ? Что в этом уникального по сравнению с оригинальной избыточностью источника, где LZ работает лучше, чем Хаффман?

SRobertJames
источник

Ответы:

13

Первоначально это был комментарий, но он стал слишком длинным.

Если вы посмотрите на DEFLATE, то, что сжимает Хаффман, является выводом LZ77; LZ77 работает (когда это занимает меньше битов, чем необработанные данные), отправляя указатель ранее в сжатую строку, и соответствует длине совпадения, которая указывает, сколько символов нужно взять после указателя. Теория показывает, что даже без дополнительного сжатия этот метод в конечном итоге сходится к энтропии источника. Тем не менее, при сжатии данных, каждый раз, когда у вас есть распределение, которое не является полностью случайным, вы также можете сжать его. Нет оснований полагать, что выходные данные LZ77 - указатели и длины совпадений - абсолютно случайны. Они должны сходиться к полной случайности в асимптотическом пределе, поскольку LZ77 асимптотически оптимален, но на практике вы используете только конечный словарь, таким образом, они, по-видимому, остаются достаточно далеко от того, чтобы быть абсолютно случайными, чтобы вы выиграли, сделав для них дальнейшее сжатие. Естественно, вы используете один код Хаффмана для указателей, а другой - для длин совпадений, поскольку эти два процесса имеют разную статистику.

Зачем использовать Хаффман, а не LZ для второго раунда сжатия? Большое преимущество LZ перед Хаффманом заключается в обработке зависимостей между символами. В английском языке, если одна буква является буквой «q», следующая, скорее всего, будет буквой «u» и так далее. Если символы являются независимыми событиями, то Хаффман проще и работает так же хорошо или лучше для коротких строк. Для вывода LZ77 моя интуиция заключается в том, что символы должны быть достаточно независимыми, поэтому Хаффман должен работать лучше.

Питер Шор
источник
Я с вами о вашем первом абзаце: LZ все еще оставляет некоторую избыточность для дальнейшего сжатия. Но твой 2-й абзац все еще, кажется, прыгает, если не машет рукой. Есть два утверждения: 1. Избыточность, остающаяся после LZ, имеет нулевой порядок (то есть p (X_n) приблизительно не зависит от x_n-1; я использую термин нулевой порядок, как в модели нулевого порядка, например, data-compression.com/theory.shtml ) и 2. При избыточности нулевого порядка Хаффман работает лучше, чем LZ; При избыточности высшего порядка LZ работает лучше. Возможно, оба эти утверждения верны, но вы тоже не оправдали себя
SRobertJames
2
@ Роберт: корреляции высшего порядка никак не влияют на кодирование Хаффмана. LZ работает асимптотически оптимально для избыточности более высокого порядка, но требуемые дополнительные издержки означают, что это не так хорошо для источников нулевого порядка конечной длины. Это должно быть где-то экспериментально изучено в литературе; может быть, кто-то еще может дать указатель на ссылку. Что касается пункта 1, моя интуиция заключается в том, что любая избыточность высшего порядка, остающаяся после LZ, слишком сложна, чтобы использовать ее в любой простой схеме кодирования, но у меня нет хорошего способа оправдать это.
Питер Шор
10

Сжатие данных на самом деле о двух вещах: моделирование и кодирование. Алгоритмы семейства LZ моделируют текст как совокупность точных повторений, которая асимптотически оптимальна для многих случайных источников и достаточно хороша для многих реальных текстов. Однако для некоторых входов эта модель может быть довольно плохой. Например, вы не можете использовать LZ для непосредственного сжатия массива суффиксов, даже если массив суффиксов сжимается так же, как и исходный текст.

(п,,с)пс

журналNN

Короче говоря, Хаффман выигрывает у LZ при сжатии кортежей, поскольку его модель (фиксированное распределение и точное повторение) лучше подходит для данных.

Джуни Сирен
источник
Спасибо, Джуни. Похоже, что основная оставшаяся избыточность заключается в том, что длины повторений обычно меньше, чем больше (неравномерно распределены по [0,2 ^ n]). Хаффман хорошо справляется с этой асимметрией нулевого порядка, тогда как LZ действительно нуждается в больших функциях, чтобы хорошо работать. Это верно? И почему бы не использовать Huffman для начала - зачем вообще беспокоиться о LZ?
SRobertJames
3
Если мы сжимаем текст непосредственно с помощью Хаффмана, мы не можем получить лучшее сжатие, чем энтропия нулевого порядка. Однако большинство реальных текстов имеют значительные источники избыточности, которые не могут быть адекватно смоделированы с помощью энтропии нулевого порядка. Во многих случаях использование LZ до Huffman позволяет нам сжимать эту избыточность.
Джуни Сирен
2

Я верю, что ответ заключается в размере словаря поиска.

У данных есть ощущение локальности (то есть, если часть данных была использована, скорее всего, она скоро будет использована снова), и алгоритм LZ использует это в конструкции словаря поиска. Он генерирует дерево с конечным количеством возможных узлов для быстрого поиска . Когда он достигает предела по размеру, он делает еще одну попытку, забывая о предыдущей. Таким образом, он должен построить заново таблицу поиска для более простых символов, но если некоторые слова больше не используются, они больше не сохраняются в памяти, поэтому можно использовать меньшую кодировку.

Следовательно, выход LZ может быть дополнительно уменьшен с помощью кодирования Хаффмана, поскольку эта избыточность при создании попыток поиска может быть обнаружена статистическим анализом.

Мануэль Феррерия
источник
Я принимаю первый абзац: вы объясняете, почему LZ оставляет избыточность. Но второй абзац кажется довольно резким: почему Хаффман ловит эту избыточность? Почему бы не LZ снова? И, если Хаффман более всеобъемлющий, почему бы не начать с него?
SRobertJames
2

Возможно, я не в курсе, но кодирование Хаффмана просматривает весь ввод, чтобы построить свою таблицу кодирования (дерево), тогда как Lempel-Ziv кодирует по мере продвижения. Это и преимущество, и недостаток для Хаффмана. Разочарование очевидно, а именно, что мы должны увидеть весь вклад, прежде чем мы сможем начать. Преимущество состоит в том, что Хаффман будет учитывать статистику, которая происходит в любом месте ввода, тогда как Лемпель-Зив должен постепенно наращивать ее. Или, другими словами, у Лемпеля-Зива есть «направление», которого нет у Хаффмана.

Но все это только мой наивный способ представить, как обстоят дела. Нам нужно настоящее доказательство, чтобы увидеть, как именно Хаффман превосходит Лемпеля-Зива.

Андрей Бауэр
источник
2
Люди определили адаптивное кодирование Хаффмана, которое смотрит на вход только один раз. Для целей этого обсуждения адаптивное и неадаптивное кодирование Хаффмана будет вести себя примерно одинаково.
Питер Шор
2

Краткий ответ: LZ - это «универсальный» алгоритм, в котором ему не нужно знать точное распределение источника (просто нужно допустить, что источник является стационарным и эргодическим). Но Хаффман нет; ему нужно знать точное распределение, из которого выбирается источник (для создания дерева Хаффмана). Эта дополнительная информация позволяет Хаффману получить строгие гарантии сжатия. Однако для практических алгоритмов сжатия файлов Хаффман может оказаться менее благоприятным, поскольку сначала ему нужно будет собрать эмпирическую статистику файла, а затем выполнить фактическое сжатие во второй половине, в то время как LZ может быть реализован онлайн.

Более подробную информацию можно найти в стандартных текстах теории информации, например, «Элементы теории информации» Коверса и Томаса.

MCH
источник
Я думаю, что стационарный эргодический источник - это просто предположение, которое облегчает анализ LZ. В конце концов, сжатие основано на комбинаторных свойствах входных данных, которые во многих случаях просто совпадают со статистическими свойствами. Рассмотрим, например, набор текстов на английском языке в текстовом формате, за которыми следуют те же тексты в формате HTML. LZ довольно хорошо сжимает эту коллекцию, даже если она не выглядит как нечто, сгенерированное стационарным эргодическим источником.
Джуни Сирен
@Jouni: я бы не согласился с этим комментарием; Я думаю, что в некотором смысле простой текстовый английский язык очень похож на стационарный эргодический источник, и это сходство - именно то, чем пользуется LZ.
Питер Шор
@Peter: Но в этом случае источник сначала генерирует некоторые тексты в текстовом формате, а затем точно такие же тексты в формате HTML. Это изменение от простого текста к HTML в некоторой произвольной точке, кажется, нарушает эргодическое стационарное свойство. С другой стороны, результаты сжатия намного лучше, чем при сжатии простых текстов и текстов HTML по отдельности, поскольку существует много взаимной информации между текстом в текстовом формате и тем же текстом в формате HTML.
Джуни Сирен