Адаптивный алгоритм Хаффмана (G;ghmnfudw glikjnmb }gssbgug)
Адаптивное кодирование Хаффмана (также называемое динамическое кодирование Хаффмана) — адаптивный метод, основанный на кодировании Хаффмана. Он позволяет строить кодовую схему в поточном режиме (без предварительного сканирования данных), не имея никаких начальных знаний из исходного распределения, что позволяет за один проход сжать данные. Преимуществом этого способа является возможность кодировать на лету.
Алгоритмы
[править | править код]Существует несколько реализаций этого метода, наиболее примечательными являются «FGK» (ФГК: Фоллер, Галлагер и Кнут) и алгоритм Виттера.
ФГК алгоритм
[править | править код]Он позволяет динамически регулировать дерево Хаффмана, не имея начальных частот. В ФГК дереве Хаффмана есть особый внешний узел, называемый 0-узел, используемый для идентификации входящих символов. То есть, всякий раз, когда встречается новый символ — его путь в дереве начинается с нулевого узла. Самое важное — то, что нужно усекать и балансировать ФГК дерево Хаффмана при необходимости, и обновлять частоту связанных узлов. Как только частота символа увеличивается, частота всех его родителей должна быть тоже увеличена. Это достигается путём последовательной перестановки узлов, поддеревьев или и тех и других.
Важной особенностью ФГК дерева является принцип братства (или соперничества): каждый узел имеет два потомка (узлы без потомков называются листами) и веса идут в порядке убывания. Благодаря этому свойству дерево можно хранить в обычном массиве, что увеличивает производительность.[1][2]
Алгоритм Виттера
[править | править код]Код представляется в виде древовидной структуры, в которой каждый узел имеет соответствующий вес и уникальный номер.
Цифры идут вниз, и справа налево.
Веса должны удовлетворять принципу братства. Таким образом, если А является родительским узлом B и C является потомком B, то .
Вес — это всего лишь количество символов, встреченных ранее.
Набор узлов с одинаковыми весами представляют собой блок.
Чтобы получить код для каждого узла, в случае двоичного дерева мы могли бы просто пройти все пути от корня к узлу, записывая, например, «1» если мы идем направо, и «0» если мы пойдем налево.
Также в этом алгоритме используется специальный лист (узел без потомков), NYT (от англ. not yet transmitted — ещё не переданный символ), из которого «растут» новые, ранее не встречавшиеся, символы.
Кодер и декодер начинают только с корневого узла, который имеет максимальный вес. В начале это и есть наш NYT узел.
Когда мы передаем NYT символ, мы должны передать вначале код самого узла, а затем данные.
Для каждого символа, который уже находится в дереве, мы должны только передавать код конечных узлов (листов).
Для каждого передающегося символа передатчик и приёмник выполняют процедуру обновления:
- Если текущий символ является не встречавшимся — добавить к NYT два дочерних узла: один для следующего NYT, другой для символа. Увеличить вес нового листа и старого NYT и переходить к шагу 4. Если текущий символ является не NYT, перейти к листу символа.
- Если этот узел не имеет наибольший вес в блоке, поменять его с узлом, имеющим наибольшее число, за исключением, если этот узел является родительским элементом[3]
- Увеличение веса для текущего узла
- Если это не корневой узел зайти в родительский узел затем перейдите к шагу 2. Если это корень, окончание.
Примечание: замена узлов означает замену весов и соответствующих символов, но не чисел.
Пример
[править | править код]Начинаем с пустого дерева.
Для «a» передаём его двоичный код.
NYT порождает два дочерних узла: 254 и 255. Увеличиваем вес корня. Код «a», связанный с узлом 255, становится 1.
Для «b» передавать 0 (код NYT узла), затем его двоичный код.
NYT порождает два дочерних узла: 252 для NYT и 253 для b. Увеличиваем веса 253, 254 и корня. Код для «b» равен 01.
Для следующего «b» передаётся 01.
Идём в лист 253. У нас есть блок весов в 1 и наибольшее число в блоке 255, так что меняем веса и символы узлов 253 и 255, увеличиваем вес, идём в корень и увеличиваем вес корня.
В будущем код «b» — это 1, а для «a» — это теперь 01, который отражает их частоту.
Примечания
[править | править код]- ↑ [1] Архивная копия от 24 сентября 2016 на Wayback Machine, ФГК алгоритм
- ↑ [2] Архивная копия от 21 сентября 2016 на Wayback Machine, адаптивное кодирование Хаффмана
- ↑ Adaptive Huffman Coding . Cs.duke.edu. Дата обращения: 26 февраля 2012. Архивировано 12 февраля 2012 года.
Литература
[править | править код]- Vitter’s original paper: J. S. Vitter, «Проектирование и анализ динамических кодов Хаффмана», журнал ACM, 34(4), октябрь 1987 г., стр. 825—845.
- J. S. Vitter, «ALGORITHM 673 Dynamic Huffman Coding», ACM Transactions on Mathematical Software, 15(2), June 1989, pp 158–167. Also appears in Collected Algorithms of ACM.
- Donald E. Knuth, «Dynamic Huffman Coding», Journal of Algorithm, 6(2), 1985, pp 163–180.
Ссылки
[править | править код]- Paul E. Black. Адаптивное кодирование Хаффмана . Словарь алгоритмов и структур данных. НИСТ.