6. ОПТИМАЛЬНЫЙ КОД
Как уже говорилось, общее правило при построении экономного кода следующее: чаще встречающиеся сообщения нужно кодировать более короткими кодовыми словами, а более длинные слова использовать для кодирования редких сообщений. Это правило и было реализовано в рассмотренном выше методе кодирования Фано. Но всегда ли метод Фано приводит к наиболее экономному коду? Ока-зывается, нет. Способ построения оптимального кода, который мы здесь изложим, потребует от нас более тонких рассуждений.
Пусть сообщения Аг, А $ Аы имеют вероятности ри
Да, ... , РN (Ри^Р^-'-^Рк) И кодируются ДВОИЧНЫМИ СЛО- вами Й1, 02 ЯлТ, имеющими длины !и /2, ... , Постараемся выяснить, какими свойствами должен обладать двоичный код, если он оптимален.
1. В оптимальном коде менее вероятное сообщение не может кодироваться более коротким словом, т. е. если рь<. <Р), го
Действительно, в противном случае поменяем ролями кодовые обозначения для Аь и А}. При этом средняя длина кодовых слов изменится на величину т. е. уменьшится, что противоречит определению оптимального кода.
2. Если код оптимален, то всегда можно так перенумеровать сообщения и соответствующие им кодовые слова, что Рь^Рь^'-^Рк и ПРИ этом
В самом деле, если р{>р-г+ь то из свойства 1 следует, что Если же р1=р1+и но /«>/,-+1, то переставим сообщения АI и и соответствующие им кодовые слова. Повторяя эту процедуру нужное число раз, мы и получим требуемую нумерацию.
Из неравенств (1) следует, что сообщение А кодируется словом а^ наибольшей длины 1ц.
3. В оптимальном двоичном коде всегда найдется, по крайней мере, два слова наибольшей длины, равной и таких, что они отличаются друг от друга лишь в последнем символе.
Действительно, если бы это было не так, то можно было бы просто откинуть последний символ кодового слова не нарушая свойстьа префиксности кода. При этом мы, очевидно, уменьшили бы среднюю длину кодового слова.
Пусть слово <2( имеет ту же длину, что и ау и отличается от него лишь в последнем знаке. Согласно свойствам 1 и 2 можно считать, что Если 1ФЫ—I,
то можно поменять ролями кодовые обозначения а1 и и не нарушая при этом неравенств (1).
Итак, всегда существует такой оптимальный код, в котором кодовые обозначения двух (наименее вероятных)сообщений и отличаются лишь в последнем сим
воле.
Отмеченное обстоятельство позволяет для решения за- дачи рассматривать только такие двоичные коды, у которых кодовые обозначения и для двух наименее вероятных сообщений 1 и имеют наибольшую длину,
отличаясь лишь в последнем символе. Это значит, что концевые вершины и кодо- ' вого дерева искомого кода должны быть соединены с одной и той же вершиной а предыдущего «этажа» (см. рис. 12).
Пусть для Лш построена некоторая система кодовых обозначений иными словами,
указано некоторое кодовое дерево с концевыми вершинами аи аг, ... , г, а. Этой системе можно сопоставить код для исходного множества сообщении, в котором слова и получаются из слова
Рассмотрим новое множество сообщений: вероятностями Оно получается
из множества {АЛ2, ... , г, Ам_и Л^} объединением двух наименее вероятных сообщений А!Я в одно сообщение А. Будем говорить, что Л(1) получается ежа-\
а добавлением соответственно I) и 1. Процедуру перехода от Кш к К назовем расщеплением.
Справедливо следующее утверждение, открывающее путь для построения оптимального кода:
Если код /Сц) для множества сообщений Л(1) является оптимальным, то оптимален также и код К для исходного множества сообщений. I
Для доказательства установим связь между средними длинами I и Г слов кодов К и Кш. Она, очевидно, такова:
Предположим, что код К не является оптимальным, т. е. существует код Кг со средней длиной ГХ<Л Как отмечалось,! можно считать, что концевые вершины и его кодового дерева (см. рис. 13) соответствуют кодовым обозначениям для наименее вероятных сообщений Ан_гиАк. Тогда зти обозначения отличаются лишь в последнем символе, рассмотрим код (аи ... , ск_2, а}, в котором слово а получается из ал_х и ал отбрасыванием последнего симБОла. Средние длины 1ц и 1[ связаны соотношением, аналогичным (2):
Из неравенства /,</ следует 1{<Х', что противоречит оптимальности кода К(1). Утверждение доказано.
Теперь ясно, что для построения оптимального кода можно использовать последовательные сжатия исходного множества сообщений.
Проиллюстрируем процесс последовательных сжатий и расщеплений на примере множества из пяти сообщений с вероятностями рц=0,4; Процесс этот
отражен в следующей таблице:
Каждое из множеств Л111, Л<2), Л<3) получается сжатием предыдущего множества. Множество Л<3) состоит из двух сообщений, поэтому оптимальный код Ю3) содержит два кодовых обозначения — 0 и 1. Последовательное расщепление К{3) дает оптимальный код для исходной системы сообщений.
Средняя длина! кодовых слов, равная 0,44-4x3x0,15= = 2,2, является, как это следует из предыдущего, минимально возможной для данного множества сообщений.
Описанный метод кодирования был предложен в 1952 г. американским математиком Д. А. Хаффменом и называется его именем. Сравним теперь оптимальный код из таблицы 12 с кодом Фано для того же множества сообщений, который строится ниже.
Подсчитаем среднюю длину 1Р кодовых слов в этом случае:
Следовательно, метод кодирования Фано не всегда приводит к оптимальному коду.
Как и метод Фано, метод кодирования Хаффмена может быть распространен на случай кодового алфавита, состоя^ щего из произвольного числа символов. Этот вопрос рас-1 смотрен в книге [2].
Задачи и дополнения
I. Доказать, что всякий оптимальный код являете нИ
полным.
2. Закодировать двоичным кодом Хаффмена множество сообщений,]! имгю111их вепоятиости:
Построить соответствующее кодовое дерево.
Основываясь на алгоритме Хаффмена, найти способ непосредг) ственного построения кодового дерева оптимального кода.
Указание. Построение дерева надо начинать не с корня, аЧ с концевых вершин.
В некоторых случаях результаты двоичного кодирования пЛ методу Фано те же, что и по методу Хаффмена, в том смысле, что длн"ь| соответствующих кодовых слов для обоих методов совпадают. Так| например, обстоит дело для множества сообщений с вероятностям^
На самом деле справедливо следующее утверждение: еелн р/=2~"1| (т. е. если вероятности являются степенями двойки), то длины соотШ ветствующих кодовых слов в кодах Фако и Хаффмена одинаковы ■ равны щ. Щ
5. Не всегда полный код является оптимальным для данного мнЛ местеа сообщений, Можно доказать, однако, что всякий полный к <1 является оптимальным для некоторого множества сообщений с подходящим образом подобранными вероятностями. Так, если кодовые слова полного кода с основанием й имеют длины и*, п2, . . ., Пдг, то он оптимален для множества сообщений с вероятностями с1~п*<. . .,