Адаптивный алгоритм Хаффмана

Адаптивное кодирование Хаффмана (также называемое динамическое кодирование Хаффмана) — адаптивный метод, основанный на кодировании Хаффмана. Он позволяет строить кодовую схему в поточном режиме (без предварительного сканирования данных), не имея никаких начальных знаний из исходного распределения, что позволяет за один проход сжать данные. Преимуществом этого способа является возможность кодировать на лету.

Алгоритмы

Существует несколько реализаций этого метода, наиболее примечательными являются «FGK» (ФГК: Фоллер, Галлагер и Кнут) и алгоритм Виттера.

ФГК алгоритм

Он позволяет динамически регулировать дерево Хаффмана, не имея начальных частот. В ФГК дереве Хаффмана есть особый внешний узел, называемый 0-узел, используемый для идентификации входящих символов. То есть, всякий раз, когда встречается новый символ — его путь в дереве начинается с нулевого узла. Самое важное — то, что нужно усекать и балансировать ФГК дерево Хаффмана при необходимости, и обновлять частоту связанных узлов. Как только частота символа увеличивается, частота всех его родителей должна быть тоже увеличена. Это достигается путём последовательной перестановки узлов, поддеревьев или и тех и других.

Важной особенностью ФГК дерева является принцип братства (или соперничества): каждый узел имеет два потомка (узлы без потомков называются листами) и веса идут в порядке убывания. Благодаря этому свойству дерево можно хранить в обычном массиве, что увеличивает производительность.

Алгоритм Виттера

Код представляется в виде древовидной структуры, в которой каждый узел имеет соответствующий вес и уникальный номер.

Цифры идут вниз, и справа налево.

Веса должны удовлетворять принципу братства. Таким образом, если А является родительским узлом B и C является потомком B, то <math>W(A) > W(B) > W(C)</math>.

Вес — это всего лишь количество символов, встреченных ранее.

Набор узлов с одинаковыми весами представляют собой блок.

Чтобы получить код для каждого узла, в случае двоичного дерева мы могли бы просто пройти все пути от корня к узлу, записывая, например, «1» если мы идем направо, и «0» если мы пойдем налево.

Также в этом алгоритме используется специальный лист (узел без потомков), NYT (от англ. not yet transmitted — ещё не переданный символ), из которого «растут» новые, ранее не встречавшиеся, символы.

Кодер и декодер начинают только с корневого узла, который имеет максимальный вес. В начале это и есть наш NYT узел.

Когда мы передаем NYT символ, мы должны передать вначале код самого узла, а затем данные.

Для каждого символа, который уже находится в дереве, мы должны только передавать код конечных узлов (листов).

Для каждого передающегося символа передатчик и приёмник выполняют процедуру обновления:

1. Если текущий символ является не встречавшимся — добавить к NYT два дочерних узла: один для следующего NYT, другой для символа. Увеличить вес нового листа и старого NYT и переходить к шагу 4. Если текущий символ является не NYT, перейти к листу символа.
2. Если этот узел не имеет наибольший вес в блоке, поменять его с узлом, имеющим наибольшее число, за исключением, если этот узел является родительским элементом
3. Увеличение веса для текущего узла
4. Если это не корневой узел зайти в родительский узел затем перейдите к шагу 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, который отражает их частоту.

Литература

• Vitter’s original paper: J. S. Vitter, «[www.cs.duke.edu/~jsv/Papers/Vit87.jacmACMversion.pdf Проектирование и анализ динамических кодов Хаффмана]», журнал 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. [www.nist.gov/dads/HTML/adaptiveHuffman.html Адаптивное кодирование Хаффмана]. Словарь алгоритмов и структур данных. НИСТ.

• [www.ics.uci.edu/~dan/pubs/DC-Sec4.html University of California Dan Hirschberg site]
• [www.cs.cf.ac.uk/Dave/Multimedia/node212.html Cardiff University Dr. David Marshall site]
• [code.google.com/p/compression-code/downloads/list C implementation of Vitter algorithm]
• [www.cs.duke.edu/csed/curious/compression/adaptivehuff.html Excellent description from Duke University]

Отрывок, характеризующий Адаптивный алгоритм Хаффмана

На другой день после совета Наполеон, рано утром, притворяясь, что хочет осматривать войска и поле прошедшего и будущего сражения, с свитой маршалов и конвоя ехал по середине линии расположения войск. Казаки, шнырявшие около добычи, наткнулись на самого императора и чуть чуть не поймали его. Ежели казаки не поймали в этот раз Наполеона, то спасло его то же, что губило французов: добыча, на которую и в Тарутине и здесь, оставляя людей, бросались казаки. Они, не обращая внимания на Наполеона, бросились на добычу, и Наполеон успел уйти.
Когда вот вот les enfants du Don [сыны Дона] могли поймать самого императора в середине его армии, ясно было, что нечего больше делать, как только бежать как можно скорее по ближайшей знакомой дороге. Наполеон, с своим сорокалетним брюшком, не чувствуя в себе уже прежней поворотливости и смелости, понял этот намек. И под влиянием страха, которого он набрался от казаков, тотчас же согласился с Мутоном и отдал, как говорят историки, приказание об отступлении назад на Смоленскую дорогу.
То, что Наполеон согласился с Мутоном и что войска пошли назад, не доказывает того, что он приказал это, но что силы, действовавшие на всю армию, в смысле направления ее по Можайской дороге, одновременно действовали и на Наполеона.


Когда человек находится в движении, он всегда придумывает себе цель этого движения. Для того чтобы идти тысячу верст, человеку необходимо думать, что что то хорошее есть за этими тысячью верст. Нужно представление об обетованной земле для того, чтобы иметь силы двигаться.
Обетованная земля при наступлении французов была Москва, при отступлении была родина. Но родина была слишком далеко, и для человека, идущего тысячу верст, непременно нужно сказать себе, забыв о конечной цели: «Нынче я приду за сорок верст на место отдыха и ночлега», и в первый переход это место отдыха заслоняет конечную цель и сосредоточивает на себе все желанья и надежды. Те стремления, которые выражаются в отдельном человеке, всегда увеличиваются в толпе.
Для французов, пошедших назад по старой Смоленской дороге, конечная цель родины была слишком отдалена, и ближайшая цель, та, к которой, в огромной пропорции усиливаясь в толпе, стремились все желанья и надежды, – была Смоленск. Не потому, чтобы люди знала, что в Смоленске было много провианту и свежих войск, не потому, чтобы им говорили это (напротив, высшие чины армии и сам Наполеон знали, что там мало провианта), но потому, что это одно могло им дать силу двигаться и переносить настоящие лишения. Они, и те, которые знали, и те, которые не знали, одинаково обманывая себя, как к обетованной земле, стремились к Смоленску.
Выйдя на большую дорогу, французы с поразительной энергией, с быстротою неслыханной побежали к своей выдуманной цели. Кроме этой причины общего стремления, связывавшей в одно целое толпы французов и придававшей им некоторую энергию, была еще другая причина, связывавшая их. Причина эта состояла в их количестве. Сама огромная масса их, как в физическом законе притяжения, притягивала к себе отдельные атомы людей. Они двигались своей стотысячной массой как целым государством.
Каждый человек из них желал только одного – отдаться в плен, избавиться от всех ужасов и несчастий. Но, с одной стороны, сила общего стремления к цели Смоленска увлекала каждою в одном и том же направлении; с другой стороны – нельзя было корпусу отдаться в плен роте, и, несмотря на то, что французы пользовались всяким удобным случаем для того, чтобы отделаться друг от друга и при малейшем приличном предлоге отдаваться в плен, предлоги эти не всегда случались. Самое число их и тесное, быстрое движение лишало их этой возможности и делало для русских не только трудным, но невозможным остановить это движение, на которое направлена была вся энергия массы французов. Механическое разрывание тела не могло ускорить дальше известного предела совершавшийся процесс разложения.
Ком снега невозможно растопить мгновенно. Существует известный предел времени, ранее которого никакие усилия тепла не могут растопить снега. Напротив, чем больше тепла, тем более крепнет остающийся снег.
Из русских военачальников никто, кроме Кутузова, не понимал этого. Когда определилось направление бегства французской армии по Смоленской дороге, тогда то, что предвидел Коновницын в ночь 11 го октября, начало сбываться. Все высшие чины армии хотели отличиться, отрезать, перехватить, полонить, опрокинуть французов, и все требовали наступления.
Кутузов один все силы свои (силы эти очень невелики у каждого главнокомандующего) употреблял на то, чтобы противодействовать наступлению.
Он не мог им сказать то, что мы говорим теперь: зачем сраженье, и загораживанье дороги, и потеря своих людей, и бесчеловечное добиванье несчастных? Зачем все это, когда от Москвы до Вязьмы без сражения растаяла одна треть этого войска? Но он говорил им, выводя из своей старческой мудрости то, что они могли бы понять, – он говорил им про золотой мост, и они смеялись над ним, клеветали его, и рвали, и метали, и куражились над убитым зверем.