Методические указания по выполнению курсовой работы по дисциплине «Информатика» (стр. 4 )

q  «соберем» символы 0 и 1 слева направо в графе 3 для каждого символа алфавита А. Получим графу 4 табл.12.

Таблица 12

Символ алфавита А	Частота символа fi	Этапы деления списка символов	Результирующие коды
1	2	3	4
I	II	III	IV	V
в	0,2	0	0	-	00
и	0,15	1	0	-	010
а	0,1	1	-	011
е	0,1	1	0	0	-	100
л	0,05		1	0	-	1010
н	0,05		1	0	10110
о	0,05		1	10111
п	0,05		1	0	0	-	1100
р	0,05		1	0	11010
с	0,05		1	11011
т	0,05		1	0	-	1110
ч	0,05		1	0	11110
ь	0,05		1	11111

1

0,55 0,45

I

0,3 0,25 0,25 0,2 (в)

II

0,15 0,15 0,15 0,1(е) 0,1 (а) 0,15 (и)

Ш

0,1 0,05(т) 0,1 0,05(п) 0,1 0,05(л)

IV

0,05(ь) 0,05(ч) 0,05(с) 0,05(р) 0,05(о) 0,05(н) V

Этапы деления списка

символов из табл. 12

Рис. 1. Двоичное дерево, изображающее деление списка частот символов

2)  для кодирования исходного текста используем табл. 12. Имеем (для простоты закодируем отдельно фамилию, имя и отчество):

петров 110 10111 00

иван (15)

васильевич0 1

Задание 7. Метод Хаффмена

Выполнить кодирование исходного текста методом Хаффмена. Частоты символов алфавита А заимствовать из задания 6.

Указания по выполнению задания 7

1)  для построения кода выполним следующие шаги:

q  используем в качестве исходных данных графы 1 и 2 табл. 12, расположив их в графах 1 и 2 табл. 13,

q  выполним последовательное объединение частот в соответствии с методом Хаффмена (графа 3 табл.13),

Таблица 13

Символ алфавита А	Часто­та сим­вола fi	Этапы объединения частот
1	2	3
I	II	III	IV	V	VI	VII	VIII	IX	X	XI	XII
в	0,2	0,2	0,2	0,2	0,2	0,2	0,2	0,2	0,25	0,35	0,4	0,6	1
и	0,15	0,15	0,15	0,15	0,15	0,15	0,2	0,2	0,2	0,25	0,35	0,4	-
а	0,1	0,1	0,1	0,1	0,1	0,15	0,15	0,2	0,2	0,2	0,25	-	-
е	0,1	0,1	0,1	0,1	0,1	0,1	0,15	0,15	0,2	0,2	-	-	-
л	0,05	0,1	0,1	0,1	0,1	0,1	0,1	0,15	0,15	-	-	-	-
н	0,05	0,05	0,1	0,1	0,1	0,1	0,1	0,1	-	-	-	-	-
о	0,05	0,05	0,05	0,1	0,1	0,1	0,1	-	-	-	-	-	-
п	0,05	0,05	0,05	0,05	0,1	0,1	-	-	-	-	-	-	-
р	0,05	0,05	0,05	0,05	0,05	-	-	-	-	-	-	-	-
с	0,05	0,05	0,05	0,05	-	-	-	-	-	-	-	-	-
т	0,05	0,05	0,05	-	-	-	-	-	-	-	-	-	-
ч	0,05	0,05	-	-	-	-	-	-	-	-	-	-	-
ь	0,05	-	-	-	-	-	-	-	-	-	-	-	-

q  построим бинарное дерево и закодируем его ребра (рис. 2, коды ребер заключены в окружности),