Неравенство Крафта

Рассматриваемое ниже неравенство Крафта показывает, для каких длин кодовых слов существует префиксный код, но приведенное ниже доказательство не является конструктивным.

Теорема (неравенство Крафта):

Необходимое и достаточное условие существования префиксного кода в [math]r[/math]-ичном дереве для источника с алфавитом [math]S[/math] из [math]n[/math] символов [math]s_i[/math], где [math]i\in \left [ 1, n \right ][/math], кодовые слова которого имеют длины [math]l_1 \leqslant l_2 \leqslant \ldots \leqslant l_n [/math], состоит в выполнении неравенства: [math] \sum\limits_{i = 1}^{n} r ^{-l_i} \leqslant 1 [/math]

Доказательство:

[math]\triangleright[/math]

Иллюстрация к доказательству индукционного перехода Неравенство Крафта легко доказать с помощью дерева декодирования, существование которого следует из существования префиксного кода. Будем рассуждать по индукции. Для простоты рассмотрим сначала случай двоичного алфавита, то есть [math]r = 2[/math]. Если максимальная длина пути на дереве равна [math]1[/math], то в дереве есть одно или два ребра длины [math]1[/math]. Таким образом, либо [math] \dfrac{1}{2} \leqslant 1 [/math] — для одного символа источника, либо [math] \dfrac{1}{2} + \dfrac{1}{2} \leqslant 1 [/math] — для двух символов источника. Предположим далее, что неравенство Крафта справедливо для всех деревьев длины меньше [math]n[/math]. Для данного дерева максимальной длины [math]n[/math] ребра из первой вершины ведут к двум поддеревьям, длины которых не превышают [math]n - 1[/math]; для этих поддеревьев имеем неравенства [math]K_1 \leqslant 1[/math] и [math]K_2 \leqslant 1[/math], где [math]K_1, K_2[/math] — значения соответствующих им сумм. Каждая длина [math]l_i[/math] в поддереве увеличивается на [math]1[/math], когда поддерево присоединяется к основному дереву, поэтому возникает дополнительный множитель [math]\dfrac{1}{2}[/math]. Таким образом, имеем [math]\dfrac{1}{2} K_1 + \dfrac{1}{2} K_2 \leqslant 1[/math]. В случае произвольного недвоичного основания [math]r[/math] имеется не более [math]r[/math] ребер, исходящих из каждой вершины, то есть не более [math]r[/math] поддеревьев; каждое из них присоединяется к основному дереву, давая дополнительный множитель [math]\dfrac{1}{r}[/math]. Отсюда снова следует утверждение теоремы.

[math]\triangleleft[/math]

Замечания

Когда имеет место строгое неравенство? Легко заметить, что если любая концевая вершина дерева является кодовым словом, то [math]K = 1[/math]. Строгое неравенство имеет место лишь в случае, когда некоторые из концевых вершин не используются. Однако, в случае двоичного кодового алфавита какая-нибудь концевая вершина не используется, то предыдущее решение оказывается лишним, и соответствующая цифра может быть удалена из каждого кодового слова, декодирование которого проходит через эту вершину. Таким образом, если имеет место строгое неравенство, то код неэффективен, но для двоичных деревьев очевидно, как можно его улучшить.

Заметим еще раз, что теорема утверждает существование такого кода и ничего не говорит о конкретных кодах. Может существовать код, который удовлетворяет неравенству Крафта и тем не менее не является префиксным.

См.также

• Неравенство Макмиллана

Источники информации

• Википедия — Неравенство Крафта
• Неравенство Крафта
• Kraft's inequality