Лабораторная работа № Коды Хаффмана

Задания к лабораторной работе.
Выполните приведенные ниже задания.

• 
  В качестве исходной строки текста выбрать «Фамилия Имя Отчество» студента.
  
• 
  Сформировать алфавит фразы, посчитать количество вхождений символов и их вероятности появления (см. табл. 1.1).
  
• 
  Отсортировать алфавит в порядке убывания вероятности появления символов (табл. 1.2).
  
• 
  Построить дерево кодирования (см. рис. 1).
  
• 
  Упорядочить построенное дерево слева-направо (при необходимости). Присвоить ветвям коды. Определить коды символов (см. рис. 2).
  
• 
  Закодировать исходную строку.
  
• 
  Рассчитать коэффициент сжатия относительно кодировки ASCII
  

Практическая часть.

В качестве исходной строки текста выбрать «Фамилия Имя Отчество» студентка: ОМОНОВ ШОХИЖАХОН ОДИЛЖОН УГЛИ

1. 
   Сформировать алфавит фразы, посчитать количество вхождений символов и их вероятности появления.
   

Шаг – 1. Для начала посчитаем частоты всех символов

О - 7
М - 1
Н - 3
В - 1
< >-3


Ш – 1
Х - 2
И - 3
Ж -2
А - 1


Д - 1
Л - 2
У – 1
Г - 1

Можно видеть, что фраза состоит из L = 14 символов.

Алфавит	О	М	Н	В	< >	Ш	Н
Кол. вх	7	1	3	1	3	1	2
Вероятн.	0,04	0,2	0,04	0,08	0,04	0,08	0,08

Алфавит	И	Ж	А	Д	Л	У	Г
Кол. вх	3	2	1	1	2	1	1
Вероятн.	0,04	0,04	0,08	0,04	0,04	0,04	0,04

2. 
   Отсортировать алфавит в порядке убывания вероятности появления символов.
   

Шаг-2. Выстраиваем таблицу, размещая повторяющиеся символы в порядке убывания

Алфавит	О	И	Н	< >	Ж	Л	Х
Кол. вх	7	3	3	3	2	2	2
Вероятн.	0,32	0,12	0,12	0,12	0,08	0,08	0,08
Алфавит	А	В	Г	Д	М	У	Ш
Кол. вх	1	1	1	1	1	1	1
Вероятн.	0,04	0,04	0,04	0,04	0,04	0,04	0,04

Построить дерево кодирования (см. рис. 1).

Шаг-3. Объединяем символы в группы, начиная с меньших значенией (по есть справа налево). Определяем значения x_n

Рис. 1. Дерево кодирования Хаффмана

3. 
   Для удобства перерисуем построенное дерево, упорядочив его слева на право, начиная с корня. Каждой ветви дерева присвоим свой код. При этом, ветвь, идущая выше, будет иметь код «0», а ветвь, идущая ниже — «1». Упорядоченное дерево показано на рис. 2.
   

Рис. 2. Упорядоченное дерево кодирования Хаффмана

4. 
   Закодировать исходную строку.
   

В итоге получается, что символам с большей вероятностью появления соответствуют более короткие коды.
Теперь можно закодировать исходную строку. Она будет иметь вид: ОМОНОВ ШОХИЖАХОН ОДИЛЖОН УГЛИ

О	М	О	Н	О	В	< >	Ш	O	Х		И
00	11101	00	011	00	11010	1000	11111	00	1011		010
Ж	А	Х	О	Н	< >	О	Д	И	Л		Ж
1001	1100	1011	00	011	1000	00	11100	010	1010		1001
О	Н	< >	У	Г	Л	И
00	011	1000	11110	11011	0110	010

5. 
   Рассчитать коэффициент сжатия относительно кодировки ASCII
   

L_ASCII= 8*29 = 232 бит.

L_HUFF =7*2+3*3+3*3+3*4+2*4+2*4+2*4+4+5+5+5+5+5+5=102

Следовательно, коэффициент сжатия будет равен

= 232 / 102 ≈ 2,27

Контрольные вопросы

1. 
   При кодировании каких данных можно использовать сжатие данных с потерями? Ответ обоснуйте.
   

Ответ: Сжатие с потерями применяется в основном для графики (JPEG), звука (MP3), видео (MPEG), то есть там, где в силу огромных размеров файлов степень сжатия очень важна, и можно пожертвовать деталями, не существенными для восприятия этой информации человеком.

2. 
   В чем преимущества и недостатки статических методов и словарного сжатия?
   

Ответ: Самая большая проблема с кодами — это необходимость иметь таблицу вероятностей для каждого типа сжатых данных, как видно из предыдущего обсуждения. Это не проблема, если известно, что английские или русские тексты сжаты; мы предоставляем кодировщику и декодеру только подходящее кодовое дерево для английских или русских текстов. В общем, статические коды Хаффмана работают неэффективно, когда вероятность появления символов для входных данных неизвестна.

3. 
   Каким образом кодирование по алгоритму Хаффмана через префиксный код гарантирует минимальную длину кода?
   

Ответ: Объедините два символа с наименьшими типами встречаемости нового композитора, вероятность того, что его символы равны вероятности того, что вероятности компонентов равны. В итоге мы строим дерево, каждый узел которого имеет меньшую вероятность каждого узла.

4. 
   За счет чего в методе Хаффмана поддерживается однозначность соответствия кода кодируемому символу?
   

Ответ: Коды Хаффмана имеют уникальный префикс, что и позволяет однозначно их декодировать, несмотря на их переменную длину.

5. 
   Почему алгоритм Хаффмана малоэффективен для файлов маленьких размеров?
   

Ответ: Это единственный алгоритм, который не увеличивает размер исходных данных в худшем случае (если не считать необходимости хранить таблицу перекодировки вместе с файлом).

6. 
   Выполните кодирование по методу Хаффмана через префиксный код символов, которые встречаются с вероятностями 0,3; 0,2; 0,1; 0,1; 0,1; 0,05; 0,05; 0,04; 0,03; 0,03. Сравните полученный результат с данными программной реализации.
   
7. 
   Докажите, что метод Хаффмана кодирует информацию без потерь.
   

Ответ: Идея алгоритма Хаффмана состоит в следующем: зная вероятности вхождения символов в исходный текст, можно описать процедуру построения кодов переменной длины, состоящих из целого количества битов.