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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Т. е.
0001000001001000111011101011101110110100001100101

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

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

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

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
Закодированный текст:
0001000001001000111011101011101110110100001100101
Декодированный текст:
Сжатие Хаффмана

Пример создания дерева на 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()

жүктеу/скачать 157.5 Kb.

Достарыңызбен бөлісу: