Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Построение эффективных кодов методом Хаффмена и кодирование дискретного сигнала
|
|
Задание к работе: выполнить кодирование исходного текста методом Хаффмена. Частоты символов алфавита заимствовать из задания 7.
Решение задачи:
1) для построения кода выполним следующие шаги:
q используем в качестве исходных данных графы 1 и 2 таблицы 7.2, расположив их в графах 1 и 2 таблицы 8.1,
q выполним последовательное объединение частот в соответствии с методом Хаффмена (графа 3 таблицы 8.1, красным цветом показана объединенная частота),
Таблица 8.1
| Символ алфавита | Частота символа fi | Этапы объединения частот | |||||||||||
| 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 | |
| и | 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 построим бинарное дерево и закодируем его ребра (рисунок 8.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. Кодовое бинарное дерево для задания
q начиная с корня дерева, «соберем» коды ребер и сформируем коды символов исходного алфавита (таблица 8.2):
Таблица 8.2
| Символ алфавита | в | и | а | е | л | н | о | п | р | с | т | ч | ь |
| Код |
2) для кодирования исходного текста используем таблицу 8.2. Имеем (для простоты закодируем отдельно фамилию, имя и отчество):
петров 0001 1111 0010 0000 10110 01
иван 110 01 100 10111
васильевич 01 100 0011 110 1010 11100 1111 01 110 11101