Рассматриваются алгоритмХаффмана в двоичной и троичной системе, производится анализ эффективности, описываются особенности реализации.

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

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

Например, при экономном кодировании символьной информации часто встречаемые символы кодируются короткими кодами, в то время как редко встречающиеся — длинными.

Префиксные коды и алгоритмы их получения подробно описаны в монографии Семенюка В. В. «Экономное кодирование дискретной информации» [1].

Алгоритм Хаффмана для двоичной системы

  1. Вычисляем вероятность появления каждого символа в информации
  2. Каждому символу присваивается значение равное его частоте вхождения
  3. Полученный список элементов (пара символ — значение) сортируетсяпо убыванию: от часто встречаемых к менее встречаемым
  4. Два последних элемента списка объединяются в новый элемент, значение которого равно сумме значений вошедших в него элементов, т.е. вместо двухпоследнихэлементов записывается новый
  5. Новый список сортируется по убыванию
  6. Операции 4, 5 выполняются до тех пор? пока не останется один элемент
  7. Выписывается последний оставшейся элемент
  8. От него откладывают две ветви с элементами, которые его составляют
  9. От каждого элемента, если он не является символом, откладываются такие же две ветви с входящими в него элементами
  10. Процесс выполняется до тех пор, пока все элементы не будут выписаны
  11. Каждому ребру назначается коды 0 и 1
  12. Для каждого символа(не элемента)в дереве выписывается префиксный код, как последовательность кодов рёбер идущих от вершины к символу

Особенности алгоритма Хаффмана для троичной системы

Алгоритмы Хаффмана для двоичной и троичной системы аналогичны.

Однако есть ряд отличий и особенностей.

Так, вместо объедения двух последних элементов, при кодировании в троичной системе объединяются три.

Так как объединяется нечётное количество элементов, в некоторых случаях может оказаться, что при последнем объедении будут объединяться не три, а только два элемента, что повлечёт серьёзные потери в эффективности. Это связано с тем одна из самых верхней ветвей окажется пустой. Существует способ переместить пустую ветвь на самый низкий уровень, что позволит полностью избежать потери в эффективности. Для этого необходимо учитывать количество элементов в первоначальном списке. В случае если количество элементов чётное, то на первом шаге необходимо объединять не три, а два элемента (на следующих шаг объединяются три). Таким образом, пустая ветвь будет на самом низком уровне, где находятся самые редко встречаемые элементы. В случае если количество элементов в первоначальном списке нечётно, то и на первом шаге объединяется три элемента.

Доказательство.Так как при объединении трех элементов одним получаем список меньше предыдущего на два элемента и, учитывая условие, что на последнем этапе необходимо, чтобы объединилось три элемента, получим, что эффективно будет кодироваться список 3+2·k элементами, т.е. с нечётным количеством элементов. Поэтому при четном количестве элементов — 3 + 2k + 1 — первоначально объединяются два элемента, т.е. получаем список с (3 + 2k) элементов — с нечетным количеством элементов.

Алгоритм Хаффмана для троичной системы

  1. Вычисляем вероятность появления каждого символа в информации
  2. Каждому символу присваивается значение равное его частоте вхождения
  3. Полученный список элементов (пара символ — значение) сортируетсяпо убыванию:от часто встречаемых к менее встречаемым
  4. Определяется количество элементов в списке
  5. Если количество элементов чётно, тов новый элементобъединяютсядва последних элемента списка, если количество нечётно — объединяются три элемента, значение нового элемента равно сумме значений вошедших в него элементов
  6. Новый список сортируется по убыванию
  7. Три последних элемента объединяются в новый
  8. Новый список сортируется по убыванию
  9. Операции 7,8 выполняются до тех пор, пока не останется один элемент
  10. Выписывается последний оставшейся элемент
  11. От него откладывают три ветви с элементами, которые его составляют
  12. От каждого элемента, если он не является символом, откладываются такие же три ветви с входящими в него элементами.
  13. Процесс выполняется до тех пор, пока все элементы не будут выписаны
  14. Каждому ребру назначается коды -, 0 и +
  15. Для каждого символа(не элемента)в дереве выписывается префиксный код, как последовательность кодов рёбер идущих от вершины к символу

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

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

Кодируемое сообщение: «ГОЛОГРАММА».

Статистика появления символов в сообщении: Г(2), О(2), Л(1), Р(1), A(2), М(2).

Упорядоченный список: A(2), Г(2), М(2), О(2), Л(1), Р(1).

Кодирование в двоичной системе Кодирование в троичной системе

Двоичное дерево Хаффмана

Троичное дерево Хаффмана

Примечание.Список состоит из 6 элементов — количество четное — на первом шаге объединяем только два последних элемента.
Символ Частота Двоичная система Троичная система
Префиксный код Длина кода Сумма Префиксный код Длина кода Сумма
А 2 10 2 4 0 1 2
Г 2 11 2 4 -- 2 4
М 2 000 3 6 -0 2 4
О 2 001 3 6 -+ 2 4
Л 1 010 3 3 +- 2 2
Р 1 011 3 3 +0 2 2
Итого: 26 Итого: 18

Сравнение алгоритма для двоичной и троичной систем

Оценим количество шагов для построения деревьев.

Кодирование в двоичной системе Кодирование в троичной системе
Пусть L = 2n (n — натуральное число) — количество элементов в первоначальном списке, K — количество шагов (K — натуральное число). На каждом шаге происходит объединение 2-х элементов в 1, — список с каждым шагом уменьшается на 1 элемент. Таким образом, на предпоследнем шаге останется 2 элемента, т.е. L-(K-1) = 2. Таким образом, K = L – 1 = 2n -1. Первоначально рассмотрим случай, когда количество элементов в первоначальном списке чётно, L = 2n (n — натуральное число) — количество элементов в первоначальном списке, K — количество шагов (K — натуральное число). На каждом шаге происходит объединение 3-х элементов в 1, т.е. список с каждым шагом уменьшается на 1 элемент. Однако в соответствии с оптимальным алгоритмом на первом шаге необходимо объединять в один элемент 2, а не 3. Будем считать, что первый шаг выполнен, было объединено только 2 элемента в 1 (L-1). Таким образом, на предпоследнем шаге останется 3 элемента, т.е. L-2*(K-2) - 1= 3. Таким образом, K = L – 1 = 2n -1.

Оценим эффективность построения деревьев.

Кодирование в двоичной системе Кодирование в троичной системе
Каждый уровень дерева может содержать до 2nэлементов, где n― номер уровня, т.е. 1-ый уровень содержит 2 элемента, 2-ой ― 4, 3-ий ― 8, 10-ый уровень может содержать уже 210, т.е 1024 элементов. Каждый уровень дерева может содержать до 3nэлементов. Таким образом, 10-ый уровень может содержать 310, т.е 59049 элементов.

Порядок уровня определяет длину префиксного кода. Например, длина префиксных кодов элементов 1-го уровня равна 1, 7-ого― 7. Соответственно, чем меньше уровней будет в дереве, тем более экономичным будет кодирование.

Рассмотрим случай, когда все кодируемые элементы располагаются на последнем уровне, случай, когда первоначально все элементы имеют одинаковый вес.

Так на 9-й уровень при кодировании в троичной системе может содержать до 19683 элементов, при кодировании в двоичной системе 9-й уровень может содержать только 512. Лишь 14-й уровень будет содержать примерно такое же количество элементов (15-й уровень будет уже содержать большее, чем 9-й при троичном кодировании). Относительную эффективность можно оценить по соотношению уровней. Из приведённой ниже таблицы видно, что, в среднем, кодирование в троичной системе эффективнее в 1,5 раза чем в двоичной.

Кодирование в троичной системе Кодирование в двоичной системе Соотношение
Уровень Максимальное количество элементов Уровень Максимальное количество элементов
1 3 1 2 1.000
2 9 3 8 1.500
3 27 4 16 1.333
4 81 6 64 1.500
5 243 7 128 1.400
6 729 9 512 1.500
7 2187 11 2048 1.571
8 6561 12 4096 1.500
9 19683 14 16384 1.556
10 59049 15 32768 1.500
11 177147 17 131072 1.545
12 531441 19 524288 1.583
13 1594323 20 1048576 1.538
14 4782969 22 4194304 1.571
15 14348907 23 8388608 1.533
16 43046721 25 33554432 1.562
17 129140163 26 67108864 1.529
18 387420489 28 268435456 1.556
19 1162261467 30 1073741824 1.579
20 3486784401 31 2147483648 1.550
21 10460353203 33 8589934592 1.571
22 31381059609 34 17179869184 1.545
23 94143178827 36 68719476736 1.565
24 282429536481 38 274877906944 1.583
25 847288609443 39 549755813888 1.560
26 2541865828329 41 2199023255552 1.577
27 7625597484987 42 4398046511104 1.556
28 22876792454961 44 17592186044416 1.571
29 68630377364883 45 35184372088832 1.552

Выводы

Построение троичного дерева в два раза быстрее (по количеству шагов) и в полтора раза эффективнее (по длине кодов), чем двоичное дерево.

Источники

  1. Семенюк В. В. Экономное кодирование дискретной информации. – СПб.: СПбГИТМО (ТУ), 2001. – 115 с.
    УДК 621.391:519.726
    ISBN 5–7577–0076–9
  2. http://www.compression.ru