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

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

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

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

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

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

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

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

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

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

$(p, \ell, c)$$p$$\ell$$c$

$\log n$$n$

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

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

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

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

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

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

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

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