Метод Хаффмана

План отчета

Введение 3
Метод Хаффмана – это адаптивный алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью, разработанный в 1952 году Дэвидом Хаффманом. Данный метод применяется во многих архиваторах и форматах фалов. Этот метод основан на том, что различные символы любого алфавита имеют разную вероятность появления в тексте. Для примера - в русском языке буква "А" встречается намного чаще, чем "Ъ". Итак, раз разные символы имеют разные вероятности появления, следовательно, если кодировать их не все по 8 бит, как они хранятся в ASCII формате, а длину кода наиболее часто встречаемых уменьшить за счёт увеличения длины кода редких символов - можно сжать исходный текст. 6
Рассмотрим алгоритм кодирования информации, применяемый в методе Хаффмана на примере фразы «beep boop beer!». Прежде всего формируется алфавит символов с частотой появления каждого символа в тексте. Далее символы сортируются по убыванию частоты появления: 6
“e” - 4, “b” - 3, “ “ - 2, “o” – 2, “p” – 2, “r” – 1, “!” – 1 6
Далее формируется так называемое дерево Хаффмана. Для его построения применяется следующий алгоритм: 6
1.Из списка выбирается два узла с наименьшей частотой появления 6
2.Формируется новый узел и присоединяется к нему, в качестве дочерних, два узла выбранных из списка. При этом частоту появления сформированного узла положим равной сумме частот дочерних узлов. 6
3.Добавим сформированный узел к списку. 6
4.Если в списке больше одного узла, то повторить 1-3. 6
Метод RLE (Run Length Encoding) является одним из самых быстрых и простых и понятных алгоритмов сжатия информации. В некоторых случаях он является достаточно эффективным. Данный метод применяется для сжатия изображений в формате PCX. Принцип работы этого алгоритма можно описать так: последовательность повторяющихся символов заменяется последовательностью из трёх байт – байта prefix, указывающего, что встретилась последовательность повторяющихся символов, байта length, указывающего длину последовательности и байта symbol, указывающего собственно символ, из которых состоит последовательность. 6
Рассмотрим работу данного алгоритма на примере конкретной: шестнадцатеричной последовательности 7
05 05 05 05 05 01 01 03 03 03 03 03 03 05 03 FF FF FF FF 7
из 20 байт. Выберем в качестве префикса байт FF. Тогда на выходе архиватора мы получим последовательность 7
FF 05 05 FF 02 01 FF 06 03 FF 01 05 FF 01 03 FF 04 FF 7
Длина выходной последовательности - 18 байт, соответственно достигнуто некоторое сжатие. Однако, нетрудно заметить, что при кодировании некоторых символов размер выходного кода возрастает (например, вместо 01 01 - FF 02 01). Очевидно, что последовательности повторяющиеся символов длиною менее четырёх кодировать бессмысленно - их надо записывать в явном виде. Получим новую последовательность: 7
FF 06 05 01 01 FF 06 03 05 03 FF 04 FF 7