 |
|
МЕТОДЫ СЖАТИЯ ПО ШЕННОНУ И ХАФФМЕНУ
Цель работы: ознакомление со статистическими принципами сжатия информации с использованием методов Шеннона - Фано и Хаффмена.
Примечание. Для выполнения лабораторной работы на компьютере необходимо установить файл Shannon-Hulfman.exe, который находится в архиве Методы сжатия по Шеннону и Хаффмену.rar.
Описание лабораторной работы. Работа выполняется на персональном компьютере с использованием программы Shannon-Huffinan.exe. Программа предназначена для демонстрации методов сжатия информации по алгоритмам Шеннона - Фано и Хаффмена (рис. 3.8).
Рис. 3.8. Главное окно программы
Для работы с программ ой пользователь выбирает требуемый метод сжатия (см. рис. 3.8).
В окне программы ИСХОДНЫЙ ТЕКСТ записывается сообщение произвольной длины (или загружается сообщение из заранее подготовленного файла в формате .txt). Затем необходимо указать число символов, кодируемых за один раз.
Для подсчета вероятности появления букв во введенном сообщении Р, определения энтропии источника сообщений Н, среднего числа символов при кодировании одной буквы сообщения L необходимо выбрать закладку АНАЛИЗ.
Для определения эффективности кодирования рассчитывается избыточность кода (L - Н).
Кратко ознакомиться со сведениями о программе вы можете, выбрав закладку ПОМОЩЬ (рис. 3.9).
Чтобы выйти из программы, достаточно выбрать закладку ФАЙЛ и далее выход.
Пример 3.12. Исходное сообщение аббвввггггдддддеееее, состоящее из символов шестибуквенного алфавита А = {а, б, в, г, д, е}, закодируем методом Хаффмена.
Определяем вероятность появления символа в исходном сообщении:
P=n/N,
где n - число повторов символа в сообщении; N - длина сообщения.
Выпишем в столбец все символы алфавита в порядке убывания вероятности их появления в тексте (табл. 3.15).
Рис. 3.9. Просмотр сведений о программе
Таблица 3.15
| Символ | Число повторений символов в данном сообщении | Вероятность появления символов |
| д | 0,25 | |
| е | 0,25 | |
| г | 0,20 | |
| в | 0,15 | |
| б | 0,10 | |
| а | 0,05 |
Последовательно объединяя два символа с наименьшими вероятностями появления символов новый составной символ, вероятность появления которого полагается равной сумме вероятностей составляющих его символов, построим дерево, каждый узел которого имеет суммарную вероятность всех узлов, находящихся ниже него. Проследим путь к каждому листу дерева, помечая направление к каждому узлу (например, направо - 0, налево-l):
Среднее количество символов на букву сообщения:
где n(i) - количество знаков в кодовой комбинации i-гo символа алфавита; Р(i) - вероятность появления i-гo символа алфавита.
Энтропия:
3. Выполнить следующие задания:
1) число символов алфавита k=m (m - номер варианта). Составить такое исходное сообщение, чтобы:
а) символы алфавита встречались в сообщении с равными вероятностями,
б) символы алфавита встречались в сообщении с разными вероятностями;
2) ввести произвольный связный текст на русском языке. Это может быть пословица, стихотворение или произвольный текст. Используя результаты работы программы, следует проанализировать алфавит введенного сообщения: подсчитать количество символов алфавита, значение энтропии Н, среднее количество символов на знак L при целочисленном кодировании.
4. Сохранить в отчете экранные формы, демонстрирующие процесс сжатия информации.
5. Отчет по лабораторной работе должен содержать результаты анализа программы Shannon-Huffman.exe при кодировании; алгоритм построения кода Хаффмена и Шеннона с применением знаний по данной тематике; результаты сравнения различных методов кодирования; выводы об эффективности используемых методов сжатия.
6. Привести в отчете ответы на контрольные вопросы в соответствии с номером варианта, указанным преподавателем (табл. 3.17).
Включить в отчет о лабораторной работе выполненные задания № 1-3.
Таблица 3.17
| Номер варианта | Контрольные вопросы |
| 1, 5, 7, 3, 9, 18, 28 | Какие коды позволяют производить однозначное декодирование даже без использования разделительного символа? Приведите примеры таких кодов |
| 2, 4, 6, 8, 20, 22, 24, 26, 30 | Назовите условия построения оптимальных кодов |
| 11, 13, 15, 10, 17, 19, 27 | С какой целью используются эффективные коды и какие из них вам известны? |
| 12, 14, 16, 21, 23, 25, 29 | Перечислите основные методы сжатия информации без потерь |
Варианты заданий
Задание 1. Сообщение состоит из последовательности двух букв А и В, вероятности появления каждой из которых не зависят от того, какая была передана раньше, и равны 0,8 и 0,2 соответственно. Произведите кодирование по методу Шеннона: а) отдельных букв; б) блоков, состоящих из двухбуквенных сочетаний; в) блоков, состоящих из трехбуквенных сочетаний. Сравните полученные коды по их эффективности.
Задание 2. Составьте текст, который бы соответствовал данным, приведенным в табл. 3.18. Используя программу Shannon-Huffinan.exe, закодируйте текст методом Хаффмена.
Таблица 3.18
| Номер варианта | Вероятность появления символов | Символ | Число символов |
| 1, 5, 7, 3, 9, 12, 14, 18, 28 | 0,333333333 | о | |
| 0,166666667 | г | ||
| 0,166666667 | . р | ||
| 0, 166666667 | д | ||
| 0,166666667 | а | ||
| 2,4,6,8, 16,21,20, 22,24,30 | 0,25 | е | |
| 0,25 | т | ||
| 0,125 | о | ||
| 0,125 | . п | ||
| 0,125 | р | ||
| 0,125 | а | ||
| 11, 13, 15, 10,17,19, 23,25 | 0,25 | р | |
| 0,25 | а | ||
| 0,25 | с | ||
| 0,125 | т | ||
| 0,125 | е |
Задание З. Для вариантов а, б, в, приведенных на рис. 3.12 и в табл. 3.19, составьте код Хаффмена, Рассчитайте среднее количество символов на знак L; избыточности (L - Н) и относительной избыточности полученного кода (L .: Ну/Е. Сравните полученные значения с L, Н, (L - Н) для кода Шеннона, сделайте выводы.
Таблица 3.19
| Номер варианта | Задание |
| 1,5,7,3,9,12,14,18,28 | Задание 3. Вариант а |
| 2,4,6,8,20,22,23,24,25,30 | Задание 3. Вариант б |
| 11,13,15,16,21,10,17,19 | Задание 3. Вариант в |
Рис. 3.12. Варианты заданий