Задача №3

ЗАДАЧА №3

Задача:

Закодировать методом Хаффмена и методом Шеннона-Фано блоки:

“Мы все учились понемногу чему-нибудь и как-нибудь”

Найти - средняя длина кодовых слов.

Дано:

Вероятности Появления

Блок	Вероятность блока
Мы	0,37
Все	0,13
Учились	0,125
Понемногу	0,08
Чему	0,06
-	0,05
Нибудь	0,05
И	0,023
Как	0,11
Нибудь	0,002

Решение:

1. Метод Шеннона-Фано:

Блок	Вероятность блока	Двоичные знаки	Кодовое обозначение
		1 2 3 4 5 6 7 8 9 10 0 0 0 1 1 0 0 1 0 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1
Мы	0,37		00
Все	0,13		01
Учились	0,125		100
Как	0,11		101
Понемногу	0,08		1100
Чему	0,06		1101
Нибудь	0,05		1110
-	0,05		11110
И	0,023		111110
Нибудь	0,002		111111

(дв. ед.) – средняя длина кодовых слов

2. Метод Хаффмена:

Кодовое обозначение	Блок	Вероятность блока	Упорядоченные группировки
11	Мы	0,37	0,37	0,37	0,37	0,37	0,37	0,37	0,375	0,625	1
101	Все	0,13	0,13	0,13	0,13	0,155	0,22	0,255	0,37	0,375
100	Учились	0,125	0,125	0,125	0,125	0,13	0,155	0,22	0,255
011	Как	0,11	0,11	0,11	0,11	0,125	0,13	0,155
001	Понемногу	0,08	0,08	0,08	0,11	0,11	0,125
0101	Чему	0,06	0,06	0,075	0,08	0,11
0100	Нибудь	0,05	0,05	0,06	0,075
0001	-	0,05	0,05	0,05
00001	И	0,023	0,025
00000	Нибудь	0,002

(дв. ед.) – средняя длина кодовых слов