Коды и математика (рассказы о кодировании) - Аршинов М.Н.
Скачать (прямая ссылка):
35 Таблица 13
Сообщения Вероятности Кодовые слова
A1 0,4 0 0 00
A2 0,15 1 01
А, 0,15 0 10
А4 0,15 1 1 0 110
Ab 0,15 1 111
Подсчитаем среднюю длину If кодовых слов в этом случае:
Tf=2 X 0,4+2x2 X 0,15+2 X 3x0,15=2,3.
Следовательно, метод кодирования Фано не всегда приводит к оптимальному коду.
Как и метод Фано, метод кодирования Хаффмена может быть распространен на случай кодового алфавита, состоящего из произвольного числа символов. Этот вопрос рассмотрен в книге [2].
Задачи и дополнения
1. Доказать, что всякий оптимальный код является
полным.
2. Закодировать двоичным кодом Хаффмена множество сообщений, имеющих вероятности:
P1=0,25; р2= 0,2; ^3=P4=P5= 0,15; р„=0,1.
Построить соответствующее кодовое дерево.
3. Основываясь на алгоритме Хаффмена, найти способ непосредственного построения кодового дерева оптимального кода.
Указание. Построение дерева надо начинать не с корня, а с концевых вершин.
4. В некоторых случаях результаты двоичного кодирования по методу Фано те же, что и по методу Хаффмена, в том смысле, что длины соответствующих кодовых слов для обоих методов совпадают. Так, например, обстоит дело для множества сообщений с вероятностями:
Pi= 1/4; P2=P3=Pt=Py= 1/8; P6=P7=P8=P9= 1/16.
На самом деле справедливо следующее утверждение: если р,-=2~';/ (т. е. если вероятности являются степенями двойки), то длины соответствующих кодовых слов в кодах Фано и Хаффмена одинаковы и равны г.,-.
5. Не всегда полный код является оптимальным для данного множества сообщений, Можно доказать, однако, что всякий полный код
36 является оптимальным для некоторого множества сообщений с ПОДХОДЯЩИМ образом подобранными вероятностями. Так, если кодовые слова полного кода с основанием d имеют длины tti, п2.....tiN, то он оптимален для множества сообщений с вероятностями d~d~n*, , , ,, d
7. ОБ ИЗБЫТОЧНОСТИ, ШУМАХ
И КРИПТОГРАММЕ, КОТОРУЮ НЕЛЬЗЯ
РАСШИФРОВАТЬ
Напомним читателю, что при кодировании сообщений нужно заботиться о том, чтобы их передача была достаточно быстрой, удобной и надежной. До сих пор мы интересовались лишь требованием быстроты. В этой связи были рассмотрены различные эффективные методы кодирования: коды Фано, Шеннона, Хаффмена. Последний, как было выяснено, является даже оптимальным при заданном множестве сообщений с заданными вероятностями. Указанные методы можно рассматривать как своего рода искусственные языки, предназначенные для экономной передачи информации. Оказывается, что привычные нам естественные языки (русский, английский и т. д.) являются в этом плане слишком расточительными и не выдерживают конкуренции с искусственными языками. Подтвердим это следующим мысленным экспериментом. Произвольный русский текст разобьем на куски одинаковой длины п (промежуток между словами можно по желанию либо игнорировать, либо считать отдельным символом). Получающиеся при этом различные буквосочетания из п букв будут встречаться, как это отмечалось прежде, не одинаково часто. Представим себе, что мы располагаем таблицей, в которой указаны всевозможные re-буквенные сочетания и их вероятности в русском тексте. Применяя метод Фано, закодируем их кодовыми словами, также использующими русский алфавит. Возвращаясь к исходному тексту, заменим каждый его кусок длины п соответствующим ему кодовым словом. Расчеты показывают, что действуя таким образом, мы смогли бы при достаточно большом п сократить исходный текст более, чем наполовину, сохранив при этом всю содержащуюся в нем информацию.
Было бы однако неосторожным на основе сказанного обвинить русский язык или другие естественные языки в несовершенстве. В теории информации имеется понятие, именуемое избыточностью языка или текста. Избыточность, точного определения которой мы не приводим, можно представлять себе как долю тех символов текста, которые
37 могут быть искажены или стерты без ущерба для его понимания, или иначе, как степень возможного «сжатия» текста в случае применения к нему методов оптимального кодирования. Мы вправе сказать поэтому, что естественные языки обладают высокой избыточностью (более 50%). Напротив, оптимально закодированные тексты имеют избыточность, близкую к нулю. Но именно высокая избыточность естественных языков позволяет с легкостью пользоваться ими в письменной и устной речи, например, свободно вникать в смысл написанного, несмотря на содержащиеся в тексте сокращения или опечатки, без особого труда понимать человека, говорящего с акцентом или на каком-нибудь диалекте и т. д. Герои известного романа Жюля Верна «Дети капитана Гранта» счастливой развязкой своих приключений также во многом обязаны избыточности языка.
Одним словом, избыточность позволяет языку противостоять влиянию всякого рода мешающих воздействий, в то время как оптимально закодированные тексты, оказывается, перед ними совершенно беззащитны. Подтвердим это приведенным в таблице 13 примером текста, закодированного двоичным кодом Фано.
Возьмем последовательность сообщений AiA3AsA6AiA4 и отвечающий ей кодовый текст 011011111100110. Пусть произошло искажение одного только первого символа. Получившаяся тогда кодовая последовательность 111011111100110 после расшифровки будет воспринята как последовательность сообщений A5A2A5A4A2An.
