1. Вычисляем вероятность появления каждого символа в информации
2. Каждому символу присваивается значение равное его частоте вхождения
3. Полученный список элементов (пара: символ — значение) сортируется по убыванию: от часто встречаемых к менее встречаемым
4. Два последних элемента списка объединяются в новый элемент, значение которого равно сумме значений вошедших в него элементов, т.е. вместо двух последних элементов записывается новый
5. Новый список сортируется по убыванию
6. Операции 4, 5 выполняются до тех пор, пока не останется один элемент
7. Выписывается последний оставшийся элемент
8. От него откладывают две ветви с элементами, которые его составляют
9. От каждого элемента, если он не является символом, откладываются такие же две ветви с входящими в него элементами
10. Процесс выполняется до тех пор, пока все элементы не будут выписаны
11. Каждому ребру назначается коды 0 и 1
12. Для каждого символа (не элемента) в дереве выписывается префиксный код, как последовательность кодов рёбер идущих от вершины к символу
Рассмотрим построения двоичного и троичного кодовых деревьев по алгоритму Хаффмана.
Кодируемое сообщение: «ГОЛОГРАММА».
Статистика появления символов в сообщении: Г(2), О(2), Л(1), Р(1), A(2), М(2).
Код Хаффмена 1. Для заданного текста определить число вхождений каждого символа. 2. Схематически изобразить процесс выполнения алгоритма Хаффмена. 2. Построить упорядоченное дерево Хаффмена, имеющее минимальную высоту из всех деревьев Хаффмена. Надписать узлы дерева (символ(ы), число вхождений). 3. Выписать код Хаффмена для всех символов, входящих в текст. 4. Подсчитать длину закодированного полученным кодом текста.
Динамическое кодирование по Хаффмену. Для заданного текста (последовательности символов) схематически изобразить процесс работы кодировщика по методу динамического кодирования по Хаффмену. Для этого: 1. На каждом шагу указать очередной обработанный символ входной последовательности и его код, а также полученное после обработки этого символа кодовое дерево. 2. Первые вхождения символов кодировать с учетом следующих соображений:
а) «русский» алфавит состоит из символов (исключены символы «ё» и «й», добавлен символ «!» конца последовательности):
а б в г д е ж з и к л м н о п р с т у ф х ц ч ш щ ъ ы ь э ю я ! 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
б) кодом символа алфавита считать двоичное представление номера этого символа в алфавите (от 0 до 31), дополненное, если необходимо, слева нулями до 5-битного кода. Например, код(«а»)=00000, код(«б»)=00001, код(«р»)=01111, код(«!»)=11111. 3.3. Выписать итоговое закодированное сообщение и его длину в битах.
rj