Алгоритм Хаффмана. 
Алгоритм Хаффмана

Алгоритм Хаффмана основывается на том, что символы в текстах как правило встречаются с различной частотой.

При обычном кодировании мы каждый символ записываем в фиксированном количестве бит, например каждый символ в одном байте, или в двух.

Однако, т.к. некоторые символы встречаются чаще, а некоторые реже? можно записать часто встречающиеся символы в небольшом количестве бит, а для редко встречающихся символов использовать более длинные коды. Тогда суммарная длина закодированного текста может стать меньше.

Алгоритм Хаффмана на примере

Закодируем строку «Сжатие Хаффмана» .

Вначале нужно подсчитать количество вхождений каждого символа в тексте.

Эта таблица называется «таблица частот» .

Теперь будем строить дерево Узел дерева будет образован набором символов и числом — суммарным количеством вхождений данных символов в тексте. Назовем указанное число — весом узла.

Листьями дерева будут узлы, образованные одним символом:

Теперь будем циклически делать следующее:

• 1) Ищем среди узлов, не имеющих родителя, два узла, имеющих в сумме наименьший вес.
• 2) Создаем новый узел, его потомками будут два выбранных узла. Его весом будет сумма весов выбранных улов. Его набор символов будет образован в результате объединения наборов символов выбранных узлов.

Создаем первый узел.

Создаем еще один узел Создаем еще один узел Создаем еще один узел Создаем еще один узел Создаем еще один узел.

Создаем еще один узел декодирование алгоритм хоффман символ.

Создаем еще один узел Создаем еще один узел Создаем еще один узел.

Теперь для каждого узла, имеющего потомков, пометим дуги, идущие вниз, на одной дуге напишем 0, на другой 1.

Теперь, чтобы получить код символа, надо, начиная с корня дерева идти вниз до листа соответствующего данному символу. При этом следует записывать те значения, которые написаны на тех дугах, которые мы проходим.

Получаются следующие коды.

Заметим, что код является префиксным, т. е. ни один код символа не является префиксом кода другого символа. Также видно, что для часто встречающихся символов коды короче.

Как будет выглядеть закодированная строка:

Т.е.

Декодирование

Для декодирования можно воспользоваться построенным деревом. Начинаем с корня дерева и в качестве текущего бита берем начало текста.

В цикле делаем следующее.

• 1) Смотрим, какое значение у текущего бита, и идем в низ по дереву по дуге, на которой указано такое же значение.
• 2) Переходим к следующему биту.
• 3) Если сейчас находимся в листе дерева: читаем символ находящийся в этом листе и записываем его в результат декодирования, переходим снова в корень дерева.

Передача закодированного текста

Примечание: при передаче закодированных данных требуется также передавать дерево или таблицу частот, чтобы можно было восстановить дерево.

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

Чтобы передавать таблицу частот нужно всегда помечать левую дугу 1, а правую 0 (или наоборот), чтобы можно было восстановить дерево по таблице.

Виды алгоритма Хаффмана

• 1) статический
• 2) динамический
• 3) адаптивный

Рассмотренный пример относится к динамическому алгоритму Хаффмана.

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

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

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

Адаптивный алгоритм мы не рассматриваем здесь. Вкратце можно сказать, что в этом алгоритме также используется один проход, но при этом дерево постоянно перестраивается, т. е. меняются коды символов.

Замечание: в литературе часто рассматривают только два алгоритма Хаффмана, например

• 1) статический и динамический.
• 2) динамический и адаптивный.

При этом, когда рассматривают только динамический и адаптивный алгоритмы, часто называют тот алгоритм, который мы здесь называем динамическим как «Статический», а тот, который мы занимаем адаптивным? «Динамическим». В результате возникает путаница в терминологии? в разной литературе авторы называют одинаково разные алгоритмы.

Постановка задачи для курса «JScript»

Вход программы: некоторый текст.

Результаты работы программы:

• 1) таблица частот.
• 2) код каждого символа.
• 3) закодированный текст (без кодирования таблицы частот).
• 4) декодированный текст (с использованием дерева).

Пример Вход программы: Сжатие Хаффмана Результат работы программы:

Таблица частот:

С=1.

ж=1.

а=4.

т=1.

и=1.

е=1.

=1.

Х=1.

ф=2.

м=1.

н=1.

Коды символов:

С=0001.

ж=0000.

а=01.

т=0010.

и=0011.

е=1011.

=1010.

Х=111.

ф=110.

м=1000.

н=1001.

Закодированный текст:

Декодированный текст:

Сжатие Хаффмана.

Пример создания дерева на Jscript

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

В примере создается и выводится на экран следующее дерево.

Пример кода:

Node = new Object ().

Node. Text = «AB» .

Node. Count = 5.

Left = new Object ().

Left. Text = «A» .

Left. Count = 2.

Node. Left = Left.

Right = new Object ().

Right. Text = «B» .

Right. Count = 3.

Node. Right = Right.

function WriteTree (Prefix, N).

{.

if (N == undefined).

return.

WScript. Echo (Prefix + «text: «+N. Text+», count: «+N. Count).

WriteTree (Prefix+" «, N. Left).

WriteTree (Prefix+" «, N. Right).

}.

WriteTree (««, Node).

Данный пример выводит на экран:

text: AB, count: 5.

text: A, count: 2.

text: B, count: 3.

Еще один пример (делает то же самое):

function TreeNode (Text, Count).

{.

this. Text = Text.

this. Count = Count.

}.

TreeNode. prototype. WriteTree = function (Prefix).

{.

if (Prefix == undefined).

Prefix = ««.

WScript. Echo (Prefix + «text: «+.

this. Text+", count: «+this. Count).

if (this. Left! = undefined).

this. Left. WriteTree (Prefix+" «).

if (this. Right! = undefined).

this. Right. WriteTree (Prefix+" «).

}.

Node = new TreeNode («AB», 5).

Node. Left = new TreeNode («A», 2).

Node. Right = new TreeNode («B», 3).

Node. WriteTree ().