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

Это алгоритм архивации без потери качества. В рассмотренных выше примерах предполагалось, что, либо исходный файл состоит в основном из однородных цепочек байтов, либо количество используемых символов довольно мало (т.е. файл состоит из небольшого подмножества элементов таблицы ASCII). Представим себе самый общий случай, когда в файле представлена бОльшая часть таблицы ASCII и почти нет однородных последовательностей. В таком случае выгоду можно получить только если разные байты (символы) встречаются в данном файле с различной частотой. Тогда наиболее часто встречающиеся символы могут быть закодированы меньшим числом бит, а те, что встречаются довольно редко наоборот большим числом бит. В итоге результирующий файл с большой вероятностью будет меньшего объема, чем исходный.

Прежде чем описать алгоритм перекодировки, позволяющий наиболее часто встречающиеся символы (байты) кодировать не восемью, а гораздо меньшим числом бит, следует указать на ограничения, свойственные любому, даже самому эффективному алгоритму без потери качества.

Можно представить, что все файлы - это тексты, написанные в алфавите, состоящем из 256 букв (так оно на самом деле и есть). Рассмотрим все множество файлов, размер которых не превышает n byte (где n произвольное число). И допустим, что существует некий алгоритм кодирования, который любой из этих файлов сжимает с "положительной" эффективностью. Тогда множество всех их архивов содержится во множестве всех файлов, размер которых МЕНЬШЕ n byte. Согласно нашему предположению существует взаимно-однозначное (биективное, как сказали бы математики) соответствие между двумя конечными множествами, число элементов в которых не совпадает. Чего быть не может (так называемый принцип Дирихле; да, сказывается математическое образование). Отсюда можно сделать довольно значимые выводы: 1) не существует архиватора, который бы одинаково хорошо паковал любые файлы, 2) для любого архиватора найдутся файлы, в результате сжатия которых будут получаться архивы в лучшем случае не меньшего размера, чем исходные файлы.

Теперь приступим к описанию алгоритма Хаффмана. Рассмотрим его на примере следующего файла:

cccacbcdaaabdcdcddcddccccccccccc{End of file}

Распишем частоты каждого из символов:

a - 4,
b - 2,
c - 19,
d - 7.

Весь файл занимает 32 byte. Каждый из символов в исходном файле кодируется согласно таблице ASCII восемью битами:

a - 01100001,
b - 01100010,
c - 01100011,
d - 01100100.

Шаг №1. Расположим эти четыре символа в порядке убывания их частот:
{(c,19), (d,7), (a,4), (b,2)}

Шаг №2. На следующей строке запишем набор, полученный из предыдущего следующим образом:

• вместо двух последних символов с их частотами запишем новый элемент, у которого вместо названия символа будет запись "Вершина #n", а вместо частоты - сумма частот последних двух элементов предыдущего набора;
• отсортируем полученный набор по убыванию.
  {(c, 19), (d, 7), ("вершина #1", 6)}

Шаг №3. Переходим на шаг №2 до тех пор, пока набор не будет состоять только из одного элемента: ("вершина #last_number", summa_vseh_chastot):
{(c, 19), ("вершина #2", 13)}
{("вершина #3", 32)}

Что же в итоге? Посмотрите на рисунок. Вы видите дерево, растущее с листьев! Если соединять чертой каждый из элементов "вершина #x" с теми элементами предшествующих наборов, сумма частот которых хранится во второй части элемента "вершина #x", то мы получим своего рода дерево (в программировании подобные структуры называются бинарными деревьями).

Смысл этой древесной структуры состоит в том, чтобы каждому из символов сопоставить различное число бит в зависимости от его частоты (как мы уже говорили, в несжатом файле символы хранятся в виде групп по восемь бит). Если внимательно всмотреться в следующий рисунок, вы увидите, что каждая из ветвей помечена либо нулем, либо единицей. Таким образом, если мысленно пройтись по дереву от корня до какой-либо вершины, содержащей символ, то последовательность нулей и единиц, встречающихся у вас на пути, и будет новой комбинацией бит для этого символа. Например, символ "c" как наиболее часто встречающийся будет кодироваться одним битом "0", символ "d" двумя битами "10" и т.д.

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

ddddddaaaaaabbbbbbccccdffffffffffdddd{37 byte, end of file}

В двоичном виде файл будет выглядеть так:

01100100 01100100 01100100 01100100 01100100 01100100 01100001 01100001 01100001 01100001 01100001 01100001 01100010 01100010 01100010 01100010 01100010 01100010 01100011 01100011 01100011 01100011 01100100 01100110 01100110 01100110 01100110 01100110 01100110 01100110 01100110 01100110 01100110 01100100 01100100 01100100 01100100{296 bit, end of file}

Распишем частоты каждого из символов:

a – 6 b – 6 c – 4 d – 11 f - 10

Весь файл занимает 37 byte. Каждый из символов в исходном файле кодируется согласно таблице ASCII восемью битами. Посмотрим, как будут кодироваться эти символы в сжатом файле. Для этого построим соответствующее дерево (не забываем сортировать полученный набор):

1. {(d,11), (f,10), (a,6), (b,6), (c,4)};
2. {(d,11), (f,10), (вершина #1, 10), (a,6)} (заметьте, сортировка по убыванию частот обязательна!);
3. {(вершина #2, 16), (d,11), (f,10)};
4. {(вершина #3, 21), (вершина #2, 16)};
5. {(вершина #4, 37)}

Анализируя полученное дерево, расписываем, как будет кодироваться каждый из символов после сжатия:

a - "11"

b - "100"

c - "101"

d - "00"
f - "01".

В двоичном виде файл будет выглядеть так:

00000000 00001111 11111111 10010010 01001001 00101101 10110100 01010101 01010101 01010000 0000хххх{88 bit, end of file}

Сжатый файл занял 11 байт (последние четыре бита xxxx записываются произвольно, ведь весь файл на самом деле умещается в 84 бита, что не кратно восьми). Коэффициент сжатия при таком кодировании равен 3,5.

Поиск по сайту: