Similar presentations:
Алгоритм Хаффмана. Практическое занятие № 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