4.8. Коды Хаффмена

Сначала (предположим, что заданы вероятности различных передаваемых символов. Как и в коде Морзе, желательно сопоставлять наиболее частым символам наиболее короткие последовательности. Если вероятность символа равна а длина соответствующего кодового слова то средняя длина кодового слова

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

Переставляя кодовые слова, соответствующие символам получаем новые члены:

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

Из сделанных выше предположений следует, что это число отрицательно; переставляя кодовые слова, соответствующие символам уменьшаем среднюю длину кода. Таким образом, приходим к заключению, что выполнены указанные две цепочки неравенства.

Рассмотрение кодов Хаффмена начнем с кодирования в двоичном алфавите. Случай -ичного алфавита рассмотрен в разд. 4.11. Термин символ источника, применяется здесь для обозначения входов а кодовый алфавит — для обозначения алфавита, в который происходит кодирование.

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

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

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

удаляя соответствующим двоичныи символ из всех концевых вершин, путь к которым проходит через эту бесполезную точку.)

Если в дереве есть только два слова максимальной длины, то они должны иметь общую последнюю вершину ветвления и соответствовать двум наименее вероятным символам. До редукции дерева эти два символа дают вклад а после редукции так что средняя длина кода уменьшается на

Рис. 48.1. Процесс редукции

Рис. 4.8.2. Процесс разделения

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

Итак, в любом случае можно укоротить код и уменьшить среднюю длину кода на одну и ту же величину.

Применим эту процедуру к двум сравниваемым деревьям декодирования. Поскольку обе средние длины уменьшились на одну и ту же величину, неравенство между средними длинами сохранится. Повторное применение этой процедуры сводит оба дерева к двум символам. Для кода Хаффмена средняя длина равна 1; для другого кода она должна быть меньше 1, что невозможно. Таким образом, код Хаффмена является самым коротким из возможных кодов.

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

Для двух различных кодов Хаффмена рассмотрим вероятности

Если помещать склеенные состояния 1 как можно ниже, то, в соответствии с рис. 4.8.2, получаем длины (I, 2, 3, 4, 4) и средняя длина равна

Если, с другой стороны, ставить склеенные состояния как можно выше (рис. 4.8.3), то получим длины (2, 2, 2, 3, 3) и средняя длина равна

Оба кода имеют одинаковую эффективность (среднюю длину), но разные наборы длин кодовых слов.

Рис. 4.8.3. Другой метод кодирования

Какой из этих двух кодов следует выбрать? Более разумным выбором является тот, при котором длина меньше меняется по ансамблю сообщений. Поэтому следует вычислить дисперсию длины для каждого из этих двух случаев:

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

Задачи

4.8.1. Построить код Хаффмена для

4.8.2. Постройте код Хаффмена для

4.8.3. Построить код Хаффмена для

4.8.4. Построить код Хаффмена для