Глава 4. Теория сжатия текстовой информации.

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

Общие положения

К. Шеннон и Р. Фано предложили в наиболее чистом виде конструк­цию кода переменной длины. В этом коде у каждого символа своя длина кодовой последовательности, как в азбуке Морзе. Но в от­личие от азбуки Морзе, где конец кодовой последовательности опре­деляется "третьим символом" — паузой, здесь нужно побеспокоиться о том, как определять завершение кода отдельного символа. Предла­гается такое ограничение на код: никакая кодовая последователь­ность не является началом другой кодовой последовательности. Это свойство называется свойством префикса, а код, обладающий таким свойством, называется префиксным кодом.

В предположении, что кодируемые символы появляются в тексте независимо нужно стремиться уменьшать среднее число битов на один символ, т.е. математическое ожидание длины кодовой комбина­ции случайно выбранного символа, которое равно

где p_i — вероятность, а s_i — длина кодовой последовательности i -го символа.

Получается экстремальная задача.

Задача о префиксном коде. Минимизировать математическое ожи­дание  по всем наборам длин { s_i }, удовлетворяющим неравенству Крафта.

Теорема Крафта: Для того, чтобы набор целых чисел , мог быть набором длин путей поиска в схеме с  исходами, необходимо и достаточно, чтобы

.

Набор, для которого  минимально, называется оптимальным. Шеннон и Фано предложили строить код, близкий к оптимальному, следующим способом: разбить все символы на две группы с прибли­зительно равными суммарными вероятностями, коды первой группы начать с 0, а второй группы — с 1; внутри каждой группы делать то же самое, пока в каждой группе не останется только по одному символу.

Элегантный алгоритм для точного решения этой задачи предложил Д. Хаффмен. Алгоритм основывается на нескольких очевидных свой­ствах оптимального набора {s_j}.

Лемма 1. Пусть {р _i} — набор вероятностей символов и {s _i} — длины оптимальных кодовых комбинаций. Если p₁ > р ₂ >•••> р_п, то s₁ < s₂ < ••• <s_n.

Доказательство. Здесь достаточно сослаться на уже встречав­шуюся нам задачу о перестановке, минимизирующей скалярное произ­ведение двух векторов.

Задача о минимуме скалярного произведения Пусть заданы т чи­сел х₁ х₂,.., х_m и еще т чисел у₁, у₂,..., y_m. Составим пары (х, у), включив каждое х _i, и каждое у _j ровно в одну пару Затем перемножим числа каждой пары и сложим получившиеся произведения. Требуется найти такое разбиение чисел на пары, при котором значение получив­шейся суммы будет наименьшим.

Теорема. Наименьшее значение суммы попарных произведений до­стигается при сопоставлении возрастающей последовательности x, убывающей последовательности у.

Доказательство Покажем, что если найдутся две пары чисел  и , такие что  и , то значение суммы попарных произведений можно уменьшить, заменив эти две пары парами  и  Действительно, так как

, то

.

Поскольку число возможных расположении равно т!, т.е. конечное число, то начиная с любого расположения за конечное число шагов мы закончим процесс улучшений на расположении, которое дальше улучшить невозможно. На нем и достигается минимум.

Лемма 2. В обозначениях и предположении леммы 1 две самые длинные кодовые комбинации имеют одинаковую длину, т.е. .

Доказательство. Действительно, пусть  и, следова­тельно, п-я кодовая комбинация — самая длинная. Так как никакая ко­довая комбинация не является началом никакой другой, то, сократив n-ю комбинацию до длины (n - 1)-й, мы получим снова уникальную кодовую комбинацию и более короткую, чем раньше, что невозможно для оптимальной кодировки.

Лемма 3. Рассмотрим наравне с исходной задачей Р сокращенную задачу Р', которая получается объединением двух самых редких сим­волов в один символ, — в предположении леммы 1 это два последних символа с суммарной вероятностью . Минимальное значение целевой функции в задаче Р' отличается от значения в зада­че Р на , а оптимальный кодовый набор для задачи Р получается из решения для задачи Р' удлинением на один бит кодовой последова­тельности для объединенного символа.

Доказательство. Действительно, каждому кодовому набору для задачи Р' можно так, как сказано в утверждении леммы, сопоставить кодовый набор для задачи Р с равными длинами самых редких сим­волов. Это удлинение и приводит к приращению целевой функции на .

Теперь можно рассуждать так: в задаче Р мы ищем минимум на множестве кодов, которое мы обозначим через С_n , а в задаче Р' — аналогично на множестве C_n-1. В соответствии с леммой 2 в зада­че Р можно искать минимум на множестве С' _n, собственном подмно­жестве С_n , состоящем из таких наборов, в которых две самые длинные кодовые последовательности имеют одинаковую длину. Имеется вза­имнооднозначное соответствие между C_n-1 и С' _n, и значения целевых функций на соответствующих элементах двух множеств отличаются на постоянное слагаемое. Следовательно, и минимумы отличаются на это же постоянное слагаемое, так что минимуму в задаче Р' соответствует минимум на С' _n, а он будет минимумом и для задачи Р.

Алгоритм, основанный на этих леммах, описывается в несколько строк: если в алфавите два символа, то нужно закодировать их 0 и 1, а если больше, то соединить два самых редких символа в один новый символ, решить получившуюся задачу и вновь разделить этот новый символ, приписав 0 и 1 к его кодовой последовательности.