Алгоритм Хаффмана. Практическое занятие № 10

1.

Дисциплина: Теория информации, данные, знания
Практическое занятие № 10
Алгоритм Хаффмана
Применение алгоритма к символьной строке «beep boop beer!»
Vи = 15*8 = [120 бит]
Суть метода:
Символ, который встречается в последовательности чаще всего,
получает новый очень маленький код, а символ, который
встречается реже всего, получает, наоборот, очень длинный код.
1

2.

Сначала построим частоты символов:
Символ
“b”
“e”
“p”
“_“
“o”
“r”
“!”
Частота
3
4
2
2
2
1
1
Создадим узлы бинарного дерева для каждого знака и добавим их
в очередь, используя частоту в качестве приоритета:
“r”
“!”
“p”
“o”
“_“
“b”
“e”
1
1
2
2
2
3
4
2

3.

Создаем новый узел дерева, в котором левые два узла будут
потомками, а приоритет нового узла будет равен сумме их
приоритетов:
2
“r”
“!”
1
1
“p”
“o”
“_“
“b”
“e”
2
2
2
3
4
3

4.

Повторяем предыдущую процедуру:
“o”
“_“
“b”
2
2
3
“e”
4
4
“p”
“r”
“!”
4

5.

“b”
“e”
4
3
“o”
4
“_”
4
“p”
“r”
“!”
5

6.

“e”
4
“p”
“r”
7
4
“b”
“o”
“!”
“_”
8
7
“e”
“b”
“p”
“o”
“_”
“r”
“!”
6

7.

Построение итогового дерева:
0
0
1
1
“b”
0
“o”
1
0
1
1
0
“_”
“e”
“p”
0
1
“r”
“!”
7

8.

Построение таблицы кодов:
Символ
“b”
“e”
“p”
“_“
“o”
“r”
“!”
Код
00
11
101
011
010
1000
1001
Входная строка:
0110 0010 0110 0101 0110 0101 0111 0000 0010 0000 0110 0010
0110 1111 0110 1111 0111 0000 0010 0000 0110 0010 0110 0101
0110 0101 0111 0010 0010 000
= 120 бит
Закодированная строка:
0011 1110 1011 0001 0010 1010 1100 1111 1000 1001
= 40 бит
8

9.

Задание для самостоятельной работы
Используя метод Хаффмана, выполните сжатие следующего
сообщения:
мама мыла раму
Определите коэффициент сжатия сообщения.
9

10.

Спасибо за внимание
10