Введение
Техника сжатия данных. Адаптивное кодирование Хаффмана (также называемое динамическим кодированием Хаффмана) — это адаптивная техника кодирования, основанная на кодировании Хаффмана. Оно позволяет строить код по мере передачи символов, не имея предварительных знаний о распределении источника, что обеспечивает однопроходное кодирование и адаптацию к изменяющимся условиям в данных. Преимущество однопроходной процедуры заключается в возможности кодирования источника в реальном времени, однако это делает метод более чувствительным к ошибкам передачи, поскольку даже одна потеря пакета данных может привести к разрушению всего кода, что требует обнаружения и исправления ошибок.
Adaptive Huffman coding (also called Dynamic Huffman coding) is an adaptive coding technique based on Huffman coding. It permits building the code as the symbols are being transmitted, having no initial knowledge of source distribution, that allows one pass encoding and adaptation to changing conditions in data. The benefit of one pass procedure is that the source can be encoded in real time, though it becomes more sensitive to transmission errors, since just a single loss ruins the whole code, requiring error detection and correction.
Алгоритмы
Существует несколько реализаций этого метода, наиболее известными являются FGK (Faller Gallager Knuth) и алгоритм Виттера.
Алгоритм FGK
Это онлайн-техника кодирования, основанная на кодировании Хаффмана. Не имея предварительных знаний о частотах появления символов, она позволяет динамически корректировать дерево Хаффмана по мере передачи данных. В дереве FGK Хаффмана используется специальный внешний узел, называемый узлом 0, для идентификации нового символа. То есть, при обнаружении новых данных выводится путь к узлу 0, за которым следуют сами данные. Для символа, который уже встречался, выводится путь к этому символу в текущем дереве Хаффмана. Важно, что при необходимости дерево FGK Хаффмана должно быть скорректировано, а затем обновлены частоты соответствующих узлов. Увеличение частоты символа может нарушить свойство порядка братьев и сестер в дереве Хаффмана. Корректировка выполняется по этой причине и заключается в последовательной перестановке узлов, поддеревьев или и того, и другого. Узел, представляющий символ, меняется местами с узлом с наивысшим номером того же порядка частоты в дереве Хаффмана (или с поддеревом, корнем которого является этот узел). Также необходимо аналогичным образом обработать все предковые узлы этого узла. Поскольку алгоритм FGK имеет некоторые недостатки, связанные с перестановкой узлов или поддеревьев, Виттер предложил другой алгоритм для его улучшения.