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


Проще всего рассмотреть алгоритм Хаффмана на простейшем примере представленном на рисунке 1. Предположим, что нам надо заархивировать следующую символьную последовательность: "AAABCCD". Без архивации эта последовательность занимает 7 байт. С архивацией по методу RLE она бы выглядела бы так:
3,"A",1,"B",2,"C",1,"D"
то есть возросла бы до 8-ми байтов. А алгоритм Хаффмана может сократить ее почти до двух байтов, и вот как это происходит.
Прежде всего, отметим, что разные символы встречаются в нашем тексте по-разному. Чаще всего присутствует буква "A". Можно составить таблицу частот:
Символ 'A','B','C,'D'
Количество повторений '3','1','2','3'
Затем эта таблица используется для построения так называемого двоичного дерева (рис 1). Именно это дерево используется для генерации нового сжатого кода.
Левые ветви дерева помечены кодом 0,а правые-1. Имея такое дерево, легко найти любого символа, если идти от вершины к нужному символу. Итак в нашем случае алгоритм выглядит так:
Если символ равен "A" то ему присваивается двоичный ноль, в противном случае - единица и рассматривается следующий бит, если символ - "C", то он получит код 10, в противном случае 11. Если символ "D", то его код - 110, в противном случае-111.
Обратите внимание на то, что в алгоритме Хаффмана разные символы будут иметь разную битовую длину, и не надо иметь ни какого разделителя между символами. Например, если вы попробуете декодировать с помощью рисунка 1 последовательность:
0001111111010110
то получите текст:"AAABBCCD"
0 0 0 111 111 10 10 110
A A A B B C C D
а, рассмотренным нами выше текст "AAABCCD" займет всего 13 бит (а это меньше двух байтов).
A A A B C C D
0 0 0 111 10 10 110
Как видно, результат довольно впечатляющий, но рано радоваться, не все проблемы еще исчерпаны.
Замечание 1.
Первая проблема состоит в том, что на разных файлах метод может генерировать различные двоичные деревья. И действительно, например в русских текстах чаще всего встречается буква "А" и она будет стоять у вершины дерева и ей будет присвоен код равный двоичному нулю. А вот в англоязычных текстах, например самая частая буква - это "E" и этот код будет присвоен ей. А если ваш файл - не текст, а какая-нибудь арифметическая таблица, то там чаще встречается цифра "0", а в файлах графики чаще встречаются коды "0" и "255". Представляете, что будет если программа декомпрессор ничего не будет знать об исходном двоичном дереве. То естественно она ваш файл не разархивирует, так как не знает какие коды сопоставляются последовательностям 0, 10, 110, 1110 и т. д.
Первое решение приходит сразу, в самом начале архивированного файла надо записывать само дерево с помощью которого проходила архивация. Но тут вот где "собака порылась", ведь если мы архивировали файл длиной 8 байтов и получили 2 байта, а теперь к нему приложим таблицу длиной 8- 10 байтов, то ценность нашей архивации будет отрицательной. Таким образом на коротких файлах такой метод Хаффмана ничего не даст и чем длиннее файл, тем лучше будет эффект.
Второе решение может быть например, таким. Мы можем иметь несколько "стандартных" деревьев, первое например, для текста на русском языке, второе для текста на английском языке, третье для графических файлов (BMP, PCX), четвертое для блоков машинного кода и т. д. и т. п. Если эти деревья (таблицы соответствия) достаточно стандартны, то можно таблицу к файлу не прикладывать, а перед сжатым файлом давать один байт, в котором записан номер стандартной таблицы.
В этом случае компрессирующая программа может проверить на вашем файле несколько разных методов, посмотреть, какой будет эффективнее, припишет к выходному файлу префиксный байт и потом осуществит саму архивацию. А декомпрессирующая программа по первому байту определит каким методом была произведена компрессия, и поскольку таблицы стандартны произведет декодирование.
Замечание-2
В описанном мною алгоритме очень большая проблема связана с определением конца файла. Как декомпрессирующая программа поймет, что файл закончен? какой маркер поставить в финале?.Первый вариант связан опять же с возможностью создания специального хедера, который записывается перед файлом и в котором указано количество бит в файле. Декомпрессирующая программа работает только с этим числом и не одним битом больше.
Второй вариант изящнее, в качестве маркера используется символ, которого не может быть в исходном файле, поэтому любой такой символ будет считаться маркером конца файла. Но к сожалению, очень редко можно заранее знать точно, что таких-то или таких-то символов не может быть в файле. Например, если вы делаете компрессор общего назначения, то он должен работать с чем угодно. В этом случае вводят дополнительный фальшсимвол 256-ой. Он будет самым редко встречающимся в файле, и может быть встречен в нем только один раз, и как самый редко встречающийся символ, он будет самым длинным, и для его записи будет использована довольно длинная битовая последовательность, но по скольку это происходит только один раз, в этом нет ни чего страшного. Хотя старый принцип остается в действии: "На коротких файлах алгоритм теряет эффективность.
Замечание-3.
Рассмотрим дерево на рисунке 1. В соответствии с ним, мы можем составить следующую таблицу соответствия:
A 0
B 10
C 110
..................
252 символ 1111…10
253 символ 1111…110
254 символ 1111…1110
255 символ 1111…11110
Не трудно посчитать, что 255 символ занимал бы 256 бит, а это 32 байта, (не слабо да!), а это свело-бы на нет все преимущества компрессии.
С этой проблемой нужно справляться применением какой либо иной системой двоичного кодирования (А их может быть не мало).
В своей работе я рассмотрю два варианта, один простой и один сложный.

Приложенные файлы

  • docx 15794720
    Размер файла: 17 kB Загрузок: 0

Добавить комментарий