Методические указания для выполнения курсовой работы по информатике для студентов специальностей 220100 Вычислительные машины, комплексы, системы и сети (стр. 4 из 10)

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. Имеем (для простоты закодируем отдельно фамилию, имя и отчество):

петров 1100 100 1110 11010 10111 00

иван 010 00 011 10110 (15)

васильевич 00 011 11011 010 1010 11111 100 00 010 11110

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

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

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

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

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

- выполним последовательное объединение частот в соответствии с методом Хаффмена (графа 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	-	-	-	-	-	-	-	-	-	-	-	-

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

- начиная с корня дерева, «соберем» коды ребер и сформируем коды символов исходного алфавита (табл. 14),

Таблица 14

Символ алфавита А	в	и	а	е	л	н	о	п	р	с	т	ч	ь
Код	01	111	100	1101	1010	10111	10110	0001	0000	0011	0010	11001	11000

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