Алгоритм Хаффмана


Избавиться от нерационального кодирования нам поможет алгоритм Хаффмана (Haffman), формирующий код с наименьшей средней длиной. Суть его в следующем: все содержащиеся в файле символы записываются в список по возрастанию числа повторов. Два последних объединяются в новый составной узел, число повторов которого равно сумме повторов исходных символов. Формируется новый список, и вновь два последних значения повторов объединяются в новый узел. Данные манипуляции повторяются до тех пор, пока не останется единственное значение. И оно будет равно числу повторов всех символов, из которых состоит файл. В результате мы построим дерево, каждый узел которого имеет суммарное значение числа повторов всех узлов, находящихся ниже.
Процесс эффективного кодирования Haffman'a отображен в Таблице 1. Чтобы сформировать код для любого символа, проследите его "путь" по колонкам и строкам от начала до конца. 
 c	22	22	22	22	32	42	58	100	
 e	20	20	20	22	26	32	42		
 h	16	16	16	20	22	26			
 l	16	16	16	16	20		
 a	10	10	16	16					
 k	10	10	10						
 m	4	6						
 b	2
Таблица 1. Вспомогательная таблица количества повторов символов

c 01
e 00
h 111
l 110
a 100
k 1011
m 10101
b 10100
Таблица 2
В созданном дереве от ячейки, в которой указана сумма всех повторов (в данном случае она равна 100), мы ведем две ветки. Ветке с большим значением повторов мы назначаем код длиной 1, а ветке с меньшим - 2. Двигаясь по дереву сверху вниз, присваиваем каждому символу собственный уникальный код:
Именно алгоритм Хаффмана применяется для создания таких типов архивов, как PKZIP, LHA, ZOO, ARJ.
Теперь ты наверняка понял , как осуществляется сжатие файла. Если кратко, то это достигается так: назначайте самые короткие коды наиболее повторяющимся символам. А более длинные коды присваиваются символам, реже встречающимся в файле. В итоге мы получаем следующее: разные символы имеют различную длину кода, что может значительно затруднить распаковку архива. Неплохо было бы ввести разделительный символ, он будет сигнализировать о начале следующего кода. Но это невозможно по двум причинам. Во-первых, в нашем случае комбинации кодов объединяются в байты, а выбранный разделительный символ может нарушить целостность частей кода - то есть все закончится большой путаницей. Во-вторых, такой метод увеличит размер архива еще на один байт, и пользы от работы не будет.
Получается, наиболее эффективно - обеспечить синонимичное кодирование без каких-либо дополнительных символов. Итак, от нас требуется найти такой код, чтобы ни одна из его комбинаций не могла породить более длинную комбинацию, - он называется префиксным.
Например, у нас есть следующие символы и такие коды:
a 0
b 10
с 110
d 111
Таблица 3
Тогда строка 0011011111101010 может быть интерпретирована как
0 0 110 111 111 0 10 10
a a c d d a b b
Таблица 4
Но если бы у нас был такой код:
a 00
b 01
с 101
d 010
Таблица 5
Где код символа "b" может быть воспринят как начало кода символа "d", то есть три возможных варианта раскодирования строки 000101010101:
00 01 01 01 010 101
a b B b d c
Таблица 6
00 010 101 010 101
a d c d c
Таблица 7
00 01 010 101 01 01
a b d c b b
Таблица 8

Упражнения.
1. В чем заключается алгоритм Хаффмана? Где он используется?
2. С помощью таблицы 1 закодировать: а-2, в-5, с-7, п-16, е-21 (количество повторов).
3. Придумайте пример префиксного кода.
4. Раскодируйте сами строку: 0011101001111010100, если известно, что есть 4 буквы. Напишите количество их повторов.