Как использовать алгоритм Хаффмана для кодирования фразы мама мыла раму?
Для кодирования и декодирования фразы или сообщения сначала необходимо построить двоичное дерево по которому определяются коды символов.
Двоичное дерево строится по таблице вероятностей распределения символов или по таблице частот распределения символов.
Составляем таблицу частот, для этого надо просто посчитать сколько раз каждый символ встречается в тексе сообщения: МАМА_МЫЛА_РАМУ
- М встречается 4 раза
- А встречается 4 раза
- _ встречается 2 раза
- Ы встречается 1 раз
- Л встречается 1 раз
- Р встречается 1 раз
- У встречается 1 раза
Каждый символ является листом (конечным узлом) двоичного дерева
добавим каждый лист в список нераспределенных узлов назначив ему вес, равный его частоте и запишем в порядке возрастания весов:
попарно объединяем узлы с наименьшим весом в один родительский узел, вес которого равен сумме весов этих узлов и добавляем в список нераспределенных узлов вместо объединенных узлов в соответствии с весом нового узла.
Левому узлу ставим ребро, добавляющее к к коду символа 0, а правому ребро, добавляющее к коду символа 1, поскольку дерево строится снизу код образуется с конца, сначала добавляется последний символ,потом предпоследний и так далее.
После объединения узлов "Ы" и "Л" в узел 1 список нераспределенных узлов примет вид:
на шаге 2 объединения узлов "Р" и "У" в узел 2 получим
на шаге 3 объединяем узлы 1 и 2 в узел 3 и получаем
на шаге 4 объединяем узлы "_" и 3 в узел 4
Теперь на шаге 6 объединяем узлы "М" и "А" в узел 5
На шаге 7 объединяем узлы 4 и 5 в узел 6 и дерево готово
проходя по дереву от корня до каждого листа получаем коды символов:
"А" код равен 11
"М" код равен 10
"_" код равен 00
"У" код равен 0101
"Р" код равен 0100
"Л" код равен 0111
"Ы" код равен 0110
Чем чаще встречается символ, тем короче его код, это позволяет увеличить сжатие, по сравнению с равномерным кодированием.
Каждый код не является началом другого кода т.е. выполняется условие Фано.
Длина закодированного сообщения равна сумме произведений длины кода на частоту символа в сообщении:
1*4+1*4+1*4+1*4+2*2+
Длина кодированного сообщения 36 бит:
10111011001001100111
Длина исходного сообщения 14 символов или 14 байт (112 бит) в ASCII:
при использовании сжатия по алгоритму Хаффмана коэффициэнт сжатия равен 112/36=3.11
Равномерное кодирование:
сообщение содержит 7 различных символов. Длина кода одного символа при равна log₂(7)=3 бит
длина кодированного текста равна 14*3=42 бит
коэффициэнт сжатия равен по сравнению с несжатым текстом 112/36=2.66
коэффициэнт сжатия по сравнению с равномерно сжатым текстом равен 42/36=1.17
