4. СВОЙСТВО ПРЕФИКСА, ИЛИ КУДА ИДТИ РОБОТУ

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

Но пусть, к примеру, данные сообщения — это команды) выдаваемые электронному роботу: Ах — идти прямо, Л 2 повернуть назад, Л3 — свернуть влево, Л4 — сверн; тй вправо. Предположим, что программа поведения робота задается следующей последовательностью:

 

 

(1)

В результате кодирования эта последовательность про Iобразуется в такой двоичный текст:

 

 

Легко вообразить себе, в какое недоумение привели бы мы робота, снабдив его подобной инструкцией. Куда же ему идти? Ясно, что сначала надо идти прямо. А дальше - свернуть влево или повернуть назад, потом еще раз назад? Впереди же еще большая путаница...

Естественно возразить, что следовало бы отделить одн»] кодовое слово от другого. Разумеется, это можно сделать, но лишь используя либо паузу между словами, либо спеН циальный разделительный знак, для которого необходим^ особое кодовое обозначение. И тот и другой путь приведе! к значительному удлинению кодового текста, сводя на не* наше предыдущее «усовершенствование».

Другое дело, если мы будем пользоваться прежними кодовыми обозначениями для сообщений А(. Тогда после­довательность (1) будет закодирована так:

 

 

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

Итак, суть проблемы в том, что нужно уметь в любом кодовом тексте выделять отдельные кодовые слова без использования специальных разделительных знаков. Иначе говоря, мы хотим, чтобы код удовлетворял следующему требованию: всякая последовательность кодовых символов может быть единственным образом разбита на кодовые сло­ва. Коды, для которых последнее требование выполнено, называются однозначно декодируемыми (иногда их называ­ют кодами без запятой).

Наиболее простыми и употребимыми кодами без запятой являются так называемые префиксные коды, обладающие тем ствойством, что никакое кодовое слово не является началом (префиксом) другого кодового слова. Если код префиксный, то, читая кодовую запись подряд от начала, мы всегда смо­жем разобраться, где кончается одно кодовое слово и начи­нается следующее. Если, например, в кодовой записи встре­тилось кодовое обозначение 110, то раз­ночтений быть не может, так как в силу префиксности наш код не содержит кодо­вых обозначений 1, 11 или, скажем, 1101. Именно так обстояло дело для рассмотрен­ного выше кода, который очевидно явля­ется префиксным.           Рис. 6.

 

Нетрудно понять, как отражается свой­ство префиксности или его отсутствие на кодовом дереве. На рис. 6 представлено дерево для кода из таблицы 11 (круж­ками, как и раньше, помечены те вершины, которые соот­ветствуют кодовым словам). Таким образом, если свойство префикса не выполняется, то некоторые промежуточные вер­шины дерева могут соответствовать кодовым словам. Для кода Фано это невозможно, так как по самому алгоритму кодирования построение кодового слова заканчивается од­новременно с достижением концевой вершины. Следова­тельно, код Фано является префиксным кодом.

Задачи и дополнении

!. Префиксный код называют полным, если доставлен»! к нему любого нового кодового слова (в данном алфавите) нарушав: свойство префиксности. Убедиться, что двоичные коды, деревья кото рых изображены на рис. 3, 4, являются полными.

Па рис. 7 представлено кодовое дерево префиксного, но неполной двоичного кода. Действительно, добавив к кодовым словам 0, 10, II] слово 110, получим снова префиксный код.

Доказать, что двоичный код Фано является полным кодом, Верно ли аналогичное утверждение для кода Фано с произвольным ос; нованием?

Проанализировав задачи 1 и 2, сформулировать необходимо! и достаточное условие, которому должно удовлетворять кодовое дереве полного префиксного кода, и доказать его необходимость и достаточ ность.

Используя кодовое дерево, доказать, что всякий префиксный код может быть расширен до полного кода добавлением к нему некот )-| рого множества кодовых слов.

Пусть к — максимальное значение длин кодовых слов префикв сного кода. Показать, что число кодовых слов не превосходит величины 2к в случае двоичного кода и величины Лк в случае кода с произвольным | основанием А. Прн каких условиях достигается равенство?

Код, представленный на рис. 7, можно сделать более экономным,' отбрасывая в слове 111 последний символ. Прн этом свойство префикс! ности не нарушится. Подобная операция, состоящая в том, что каждой слово префиксного кода заменяется наименьшим его началом, не явля! ющимся началом других кодовых слов, называется усечением. Очевидно что в результате усечения получается префиксный код и при этом боле экономный, чем исходный. Возникают такне два вопроса:

Возможно ли усечение полного кода?

Можно ли утверждать, что в результате усечения получаете и полный код?

На рис. 8,о представлено кодовое дерево префиксного кода, для которого усечение невозможно. В то же время мы получим более эко ьамный префиксный код (рис. 8, б), если в словах 110 и 111 вычеркне» второй символ 1.

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

Любопытно рассмотреть примеры однозначно декодируемых кодов, не обладающих свойством префикса. Пожалуй, простейшим при­мером такого рода является двоичный код {1, 10}. Ясно, что в любо! кодовой последовательности, составленной из этих слов, всякое появле­ние символа 1 означает начало нового кодового слова. Последнее оста­ется справедливым для кода, каждое слобо которого есть единица с по­следующими нулями. Разумеется, подобные коды далеко не самые эко­номные.

Приведем менее тривиальиыи пример однозначно декодируемого кода: {01, 10, 011}. Рекомендуем читателю указать алгоритм одноз­начного выделения кодовых слов из кодовой последовательности для этого кода.

0. Как узнать, является ли произвольный код однозначно декоди­руемым? Для этого можно предложить следующий способ. Возьмем всевозможные пары кодовых слов, в которых одно слово является префиксом другого. Для каждой такой пары найдем «повисший» суффикс, который остается после удаления префиксного слова из начальной части более длинного слова. Например, повисший суффикс для пары 10 и 10010 есть 010. Выпишем все повисшие суффиксы. Далее проделаем то же самое для каждой пары слов, состоящей из повисшего суффикса и кодового слова, в которой одно слово является префиксом другого. Выпи­шем все новые повисшие суффиксы, которые при этом получатся. Будем продолжать этот процесс до тех пор, пока будут появляться новые суффиксы. Код является однозначно декодируемым тогда и только тогда, когда никакой суффикс не совпадет ии с одним кодовым словом.

10. Выяснить, обладают ли свойством однозначной декодируемое™ следующие коды:

 

 

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