8. Построение эффективных кодов методом Хаффмена и кодирование дискретного сигнала

Задание к работе: выполнить кодированиеисходного текста методом Хаффмена. Частоты символов алфавита заимствовать из задания 7.

Решение задачи:

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

• используем в качестве исходных данных графы 1 и 2 таблицы 7.2, расположив их в графах 1 и 2 таблицы 8.1,

• выполним последовательное объединение частот в соответствии с методом Хаффмена (графа 3 таблицы 8.1, красным цветом показана объединенная частота),

Таблица 8.1

Символ алфавита	Частота символа 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	-	-	-	-	-	-	-	-	-	-	-	-

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

1

0,6 0,4

0,35 0,25 0,2(в) 0,2

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

0,1(е) 0,1 0,1 0,05(л) 0,05(с) 0,05(т) 0,05(п) 0,05(р)

0,05(ч) 0,05(ь) 0,05(н) 0,05(о)

Рисунок 8.1. Кодовое бинарное дерево для задания

• начиная с корня дерева, «соберем» коды ребер и сформируем коды символов исходного алфавита (таблица 8.2):

Таблица 8.2

Символ алфавита	в	и	а	е	л	н	о	п	р	с	т	ч	ь
Код	01	110	100	1111	1010	10111	10110	0001	0000	0011	0010	11101	11100

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

петров0001 1111 0010 0000 10110 01

иван110 01 100 10111

васильевич01 100 0011 110 1010 11100 1111 01 110 11101