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~п*<. . .,