Первая страница / Теория / Сжатие данных /

Адаптивное кодирование Хаффмена

Голосование: 20, 1

Введение

Данная статья посвящена кодированию текста с помощью алгоритма Хаффмана (David Huffman) [1952]. Как многие другие алгоритмы, метод Хаффмана можно реализовать в двух вариантах – статическом (применяется в JPEG, ARJ) и динамическом (утилита compact в UNIX). Именно динамический вариант алгоритма будет подробно рассмотрен в этой статье, поэтому предполагается, что читатель знаком с принципами сжатия данных при помощи алгоритма Хаффмана.

Динамическое (или адаптивное) кодирование методом Хаффмана было предложено независимо Фоллером (Newton Faller) [1973] и Галлагером (Robert Gallager) [1978]. В 1985 Кнут (Donald Knuth) разработал окончательный усовершенствованный вариант алгоритма, вследствие чего алгоритм получил название FGK (Faller, Gallager, Knuth) алгоритма.

Суть алгоритма Хаффмана заключается в том, что символы почти любого алфавита имеют разную вероятность появления в тексте. Итак, раз разные символы имеют разные вероятности появления, следовательно, если кодировать их не все по 8 бит, как они хранятся в ASCII формате, а длину кода наиболее часто встречаемых уменьшить за счёт увеличения длины кода редких символов, можно хорошо сжать исходный текст.

Отличия динамического и статического вариантов алгоритма

Введем несколько определений.

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

Код переменной длины (переменный код в дереве Хаффмана) символа – последовательность бит, которая получается при проходе по ребрам от корня к вершине с этим символом, если сопоставить каждому ребру значение 1 или 0. В дереве Хаффмана ребрам, выходящим из вершины к ее детям сопоставлены разные значения (будем считать ниже, что ребро с 1 – левое, а с 0 – правое).

Статический метод Хаффмана  предполагает, что частоты символов алфавита изначально известны. Для этого, перед тем как начать сжатие файла программа пробегается по самому файлу и подсчитывает, какой символ сколько раз встречается. Затем, в соответствии с вероятностями появлений символов, строится двоичное дерево Хаффмана - откуда извлекаются соответствующие каждому символу коды переменной длины. Наконец, снова осуществляется проход по исходному файлу, при этом каждый символ заменяется на свой код в дереве. Таким образом, статическому алгоритму требуется два прохода по файлу источнику, чтобы закодировать данные.

Динамический алгоритм позволяет реализовать однопроходную модель сжатия. Не зная реальных вероятностей появлений символов в исходном файле, программа постепенно изменяет двоичное дерево, с каждым встречаемым символом увеличивая частоту его появления в дереве и перестраивая в связи с этим само дерево. Однако становится очевидным, что, выиграв в количестве проходов по исходному файлу, мы теряем в качестве сжатия, так как в статическом алгоритме реальные частоты встречаемости символов были известны с самого начала и длины кодов этих символов более близки к оптимальным, в то время как динамический метод, изучая источник, постепенно доходит до его реальных частотных характеристик. Но так как динамическое двоичное дерево постоянно модифицируется новыми символами - нам нет необходимости запоминать их частоты заранее - при разархивировании, программа, получив из архива код символа, точно так же восстановит дерево, как она это делала при сжатии, и увеличит на единичку частоту его встречаемости. В статическом алгоритме с этим делом немного сложнее - в самом начале сжатого файла требуется хранить информацию о встречаемых в файле источнике символах и их частотах. Это обусловлено тем, что ещё до начала разархивирования нам необходимо знать, какие символы будут встречаться и каков будет их код.

Описание динамического варианта алгоритма Хаффмана

Приведем псевдокод данного алгоритма:


 1 Initialize                                 // Инициализируем дерево и массив символов.
 2 while (not Eof(Файл источник))             // Запускаем проход файла.
 3    Get Файл источник, C                    // Считываем очередной символ.
 4    if (C нет в дереве)                     // Проверяем, встречался ли этот символ раньше.
 5    then
 6       Code = Код escape-символа + ASCII(C) // Если нет, запоминаем переменный код escape-символа и ASCII-код текущего символа.
 7       AddToTree(C)                         // Добавляем новый символ в дерево.
 8    else
 9       Code = Код C в дереве                // Если да, запоминаем переменный код символа в дереве.
10    end if
11    Put Файл приемник, Code                 // Записываем последовательность бит в файл.
12    UpdateTree(C)                           // Обновляем двоичное дерево символом.
13 end while

Первоначально двоичное дерево Хаффмана является пустым, и процедура Initialize добавляет только лист, содержащий escape-символ (такой лист будем называть «пустым» листом). Этот символ необходим для преодоления двусмысленности, так как декодер должен знать, является ли считываемая битовая последовательность несжатым символом (обычно это 8-битный код ASCII) или же это код переменной длины. Таким образом, если символ впервые появился на входе, кодер запишет код переменной длины escape-символа (escape-код), а за ним 8 бит кода ASCII нового символа, иначе будет записан код этого символа в дереве Хаффмана. При этом декодер всегда будет знать, читает ли он код переменной длины для уже находящегося в дереве символа или ASCII-код для нового символа.

Основным принципом FGK алгоритма является свойство соперничества. Двоичное дерево обладает данным свойством, если каждый его узел (за исключением корневого) имеет в дереве узла брата, и при расположении всех узлов в списке в порядке неувеличения их весов узлы братья находятся по соседству. Братьями назовём два узла, которые имеют общего родителя.

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

Номер вершины

1 2 3 4 5 6 7

Вес

6 3 3 2 1 1 0

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

Добавление символа в дерево

Процедура добавления нового символа AddToTree состоит в том, что в хвост упорядоченного списка, коим является наше дерево кодов, добавляются два новых элемента: первый из них становится листом для нового символа, а второй - дополнительным узлом. Только что созданный дополнительный узел становится родителем для нового и «пустого» листов. Дополнительный узел необходим, так как общее количество узлов дерева должно быть равным количеству листьев - 1.

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

Модификация дерева

Процедура UpdateTree обновляет дерево в соответствии со считанным символом C.

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

Приведем псевдокод данной процедуры:


 1 procedure UpdateTree(C)                          // C - считанный символ.
 2 X = Номер вершины(C)                             // Находим в дереве лист, соответствующий символу.
 3 while (X не корень)                              // Запускаем цикл обновления.
 4    if (вес(X - 1) = вес(X))                      // Проверяем, будет ли нарушена упорядоченность.
 5       i = 1
 6       while (вес(X - i - 1) = вес(X)) i = i + 1  // Ищем минимальную вершину с таким же весом.
 7       Exchange(X, X - i)                         // Обмениваем поддеревья.
 8    end if
 9    вес(X) = вес(X) + 1                           // Инкрементируем вес вершины.
10    X = родитель(X)                               // Переходим к родителю текущей вершины.
11 end while

Для рассмотренного вначале дерева упорядоченный список вершин представлял собой:

Номер вершины

1 2 3 4 5 6 7

Вес

6 3 3 2 1 1 0

Теперь, если очередным символом во входящем потоке будет символ ‘X’, тогда увеличиваем его вес на 1. Далее цикл пройдет до корня дерева, увеличив веса вершин 5, 2 и 1 на единичку, так как упорядоченность не нарушается. Новый список теперь будет иметь вид:

Номер вершины

1 2 3 4 5 6 7

Вес

7 4 3 2 2 2 0

А дерево примет вид:

Нам потребовалось всего четыре действия, чтоб изменить дерево. В общем случае необходимо увеличить на 1 вес листа поступившего на вход символа, а затем инкрементировать веса всех его родителей вплоть до корня дерева. То есть среднее число операций будет равняться среднему количеству битов (или средней длине пути от листа к корню дерева), необходимых для того, чтобы закодировать символ.

Однако возможен вариант, когда упорядоченность списка нарушается. Например, если для полученного дерева следующий символ снова будет ‘X’, видно, что предшествующие вершины с номерами 4 и 5 имеют тоже вес 2. Значит, после увеличения веса листа, соответствующего символу ‘X’, нарушилась бы упорядоченность:

Номер вершины

1 2 3 4 5 6 7

Вес

7 4 3 2 2 3 0

Поэтому находим минимальную по номеру вершину, равную по весу вершине 6, и делаем обмен этих вершин. В данном случае это вершина с номером 4. Затем инкрементируем веса вершин на пути к корню дерева, так как упорядоченность больше не нарушается. Тогда дерево примет вид:

И дерево сохраняет свойство соперничества:

Номер вершины

1 2 3 4 5 6 7

Вес

8 5 3 3 2 2 0

Проблемы

  1. Кодовое переполнение.
    Если в дерево поступит слишком много символов, и оно станет слишком высоким, может возникнуть проблема. Сами коды не хранятся, так как они меняются все время, и компрессор должен вычислять код символа каждый раз заново при его появлении. Этот код выстраивается бит за битом при проходе от листа до корня. Эту последовательность битов надо где-то хранить, поскольку она будет записываться в обратном порядке. Когда дерево станет высоким, коды тоже удлинятся. Если они накапливаются в виде 16-ти разрядного целого, то коды длиннее 16 бит вызовут сбой программы. Правильное решение может заключаться в накоплении битов кода в связанном списке, к которому можно добавлять новые узлы.
  2. Обмен с родителем.
    Вторая проблема появляется из-за «пустого» листа. Поскольку вес «пустого» листа равен нулю, его брат может стать «тяжелее» родителя в самом начале процесса обновления. Однако обмен между ребенком и родителем алгоритмически неверен, так как ребенок входит в поддерево с корнем в вершине-родителе. К счастью, запрещение любого обмена между ребенком и родителем решает проблему.
  3. Определение конца передачи.
    Наконец, для декомпрессора не существует ни одного способа определения конца передачи. Есть два способа решения проблемы. Компрессор может добавить к началу сжатых данных длину файла, делая их на пару байт длиннее. Либо можно в начале кодирования добавить в дерево помимо листа с escape-символом еще один вспомогательный лист с нулевой частотой, код которого сообщит декомпрессору о конце передачи данных.

Источники

  1. Сэломон Д. Сжатие данных, изображений и звука. — М.: Техносфера, 2004.
  2. http://www.compression.ru/download/articles/huff/yankovoy_2004_huffman/dynamic_huffman.html
  3. http://www.ics.uci.edu/~dan/pubs/DC-Sec4.html#Sec_4
  4. http://www.avhohlov.narod.ru/p2600ru.htm

Визуализатор

  1. Лагунов И. Адаптивное кодирование Хаффмана (2006)

Лагунов Иван


Ваше имя
Email
Текущий день недели (строчными буквами)
Комментарий