§ 1.11. Кодовые деревья. Неравенство Крафта

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

На рис. 1.11.1 и 1.11.2 показаны двоичные кодовые деревья, соответствующие кодам примеров 1.10.1 и 1.10.2.

Рис. 1.11.1. Двоичное кодовое дерево для кода примера 1.10.1.

Рис. 1.11.2. Двоичное кодовое дерево для кода примера 1.10.2.

Под рисунком дерева показано правило сопоставления ребер и двоичных символов: каждому правому ребру сопоставляется 1, каждому левому — 0. На рис. 1.11.3 приведен пример троичного дерева, соответствующего троичному коду 00, 01, 02, 10, 11, 12, 20, 210, 220, 221, 222.

Узлы дерева, отстоящие от корня на ребер, образуют ярус порядка Порядком узла называют номер его яруса. Порядком дерева называют максимальный из порядков его узлов. Узел, из которого не выходит ни одного ребра, называется концевым.

Код является префиксным, если кодовые слова соответствуют только концевым узлам дерева. В противном случае код не является префиксным.

Теорема 1.11. I (неравенство Крафта). Для того чтобы существовал префиксный код в алфавите объема D с длинами кодовых слов необходимо и достаточно, чтобы

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

Рис. 1.11.3. Троичное кодовое дерево.

Рассмотрим вначале необходимость. Заметим, что необходимость условия 1.11.1 для всех кодов, а не только для префиксных, была установлена в теореме 1.10.1.

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

Так как количество узлов, исключаемых яруса всеми концевыми узлами порядков не может превосходить максимального количества узлов на этом ярусе, то

Отсюда после деления обеих частей неравенства на следует (1.11.1).

Докажем теперь достаточность. Для этого следует доказать, что при выполнении (1.11.1) дерево с концевыми узлами порядков может быть построено. Предположим, что среди

этого набора порядков число встречается точно раз, Тогда

Перепишем это неравенство следующим образом:

Тогда

Применим метод полной индукции. Дерево, содержащее концевых узлов порядка 1, может быть построено. Действительно, из (1.11.3) следует, что т. е. Так как максимальное возможное количество концевых узлов порядка 1 есть то дерево с концевыми узлами порядка 1 может быть построено.

Предположим, что дерево с концевыми узлами порядка может быть построено. Докажем, что к этому дереву можно добавить еще концевых узлов порядка Если верно предположение индукции, то из яруса порядка исключаются возможных концевых узлов. Так как максимальное количество возможных концевых узлов в этом ярусе равно . То есть количество свободных узлов на ярусе Из (1.11.5) следует, что количество узлов на ярусе которые должны быть добавлены, не превосходит количества свободных узлов. Следовательно, к дереву с концевыми узлами порядка могут быть добавлены концевых узлов порядка Теорема доказана.