Как работает адаптивное кодирование Хаффмана?

Кодирование Хаффмана - широко используемый метод энтропийного кодирования, используемый для сжатия данных. Предполагается, что мы полностью знаем статистику сигнала. Тем не менее, существуют версии кодирования Хаффмана, которые используются с потоковым мультимедиа и не могут знать все о статистике сигнала. Как работают эти адаптивные кодеры Хаффмана ?

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

Дерево упорядочено по уменьшению веса или вероятности появления во входной последовательности; Листовые узлы в верхней части представляют наиболее вероятные символы, которые поэтому получают кратчайшие представления в потоке сжатых данных. Затем дерево сохраняется вместе со сжатыми данными и впоследствии используется декомпрессором для повторной генерации (несжатой) входной последовательности. Как одна из ранних реализаций энтропийного кода, стандартное кодирование Хаффмана довольно просто.

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

Алгоритм Vitter является одним из способов достижения этого; по мере обработки каждого входного символа дерево обновляется, сохраняя свою характеристику уменьшения вероятности появления символа при перемещении по дереву. Алгоритм определяет набор правил для того, как дерево обновляется с течением времени, и как результирующие сжатые данные кодируются в выходном потоке. Поскольку входная последовательность используется, структура дерева должна представлять все более и более точное описание распределения вероятностей входа. В отличие от стандартного подхода кодирования Хаффмана, декомпрессор не имеет статического дерева для использования для декодирования; он должен выполнять одни и те же функции поддержки дерева непрерывно во время процесса распаковки.

Итак, адаптивный кодер Хаффмана работает очень похоже на стандартный алгоритм; однако вместо статического измерения всей статистики входной последовательности (дерева Хаффмана) для кодирования (и декодирования) каждого символа используется динамическая кумулятивная (т.е. от первого символа до текущего символа) оценка вероятности последовательности , В отличие от стандартного подхода кодирования Хаффмана, адаптивный алгоритм Хаффмана требует этого статистического анализа как в кодере, так и в декодере.