Код Хаффмана

Слайд 2

Некоторое сообщение содержит только буквы А, Б, В, Г, Д, причём известно

Некоторое сообщение содержит только буквы А, Б, В, Г, Д, причём известно
их количество: А — 179, Б — 89, В — 72, Г — 53 и Д — 50.
Сколько бит содержит оптимальный префиксный код данного сообщения?
Решение.
В 1952 году создал алгоритм префиксного кодирования с минимальной избыточностью (известный как алгоритм или код Хаффмана).
Эффективное кодирование по Хаффману состоит в представлении наиболее вероятных (часто встречающихся) букв двоичными кодами наименьшей длины, а менее вероятных -- кодами большей длины (если все кодовые слова меньшей длины уже исчерпаны). Это делается таким образом, чтобы средняя длина кода на букву исходного сообщения была минимальной.

Слайд 3

Сначала расположим буквы по увеличению
их количества в сообщении.
Затем берём две

Сначала расположим буквы по увеличению их количества в сообщении. Затем берём две
первые – это листья дерева, а в узел, с которым
они связаны, записываем сумму их количества.

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

Слайд 4

Снова располагаем буквы по возрастанию, но
для букв «Д» и «Г»

Снова располагаем буквы по возрастанию, но для букв «Д» и «Г» используем
используем их сумму

Повторяем ту же процедуру для букв «В» и «Б»,
и снова располагаем в порядке возрастания.

Слайд 5

Объединяем пары и снова сортируем.

Объединяем букву «А» с деревом.

У стрелок, которые идут

Объединяем пары и снова сортируем. Объединяем букву «А» с деревом. У стрелок,

влево от узла, пишем код 0,
а у идущих вправо – код 1.

Слайд 6

Считаем сумму: 1*179 + 3*264 = 179+792 = 971

ОТВЕТ: 971

Считаем сумму: 1*179 + 3*264 = 179+792 = 971 ОТВЕТ: 971

Слайд 7

Некоторое сообщение содержит только буквы Ю, В, Е, Л, И, Р,
известно их

Некоторое сообщение содержит только буквы Ю, В, Е, Л, И, Р, известно
количество: Ю—9, В—15, Е—21, Л—17, И—20, Р—18.
Сколько бит содержит оптимальный префиксный код данного сообщения?
Некоторое сообщение содержит только буквы Л, А, Ф, Е, Т,
известно их количество: Л—18, А—26, Ф—1, Е—31, Т—24.
Сколько бит содержит оптимальный префиксный код данного сообщения?

Самостоятельно

Имя файла: Код-Хаффмана.pptx
Количество просмотров: 53
Количество скачиваний: 0