Изменения

Необходимое и достаточное условие существования префиксного кода в <tex>r</tex> (ичном) дереве для источника с алфавитом <tex>S</tex> из <tex>qn</tex> символов <tex>s_i</tex>, где <tex>i\in \left [ 1, q n \right ]</tex>, кодовые слова которого имеют длины <tex>l_1 \leq leqslant l_2 \leq leqslant \ldots \leq l_qleqslant l_n </tex>, состоит в выполнении неравенства:

<center><tex> \sum\limits_{i = 1}^{qn} r ^{-l_i} \leqslant 1 </tex></center>где <tex>r</tex> — основание (число символов) в кодовом алфавите.

Для простоты рассмотрим сначала случай двоичного [[Основные определения, связанные со строками|алфавита]], т. е. то есть <tex>r = 2</tex>. Если максимальная длина пути на дереве равна <tex>1</tex>, то в дереве есть одно или два ребра длины <tex>1</tex>. Таким образом, либо <tex> \dfrac{1}{2} \leq leqslant 1 </tex> — для одного [[Основные определения, связанные со строками|символа ]] источника, либо <tex> \dfrac{1}{2} + \dfrac{1}{2} \leq leqslant 1 </tex> — для двух символов источника.

Предположим далее, что неравенство Крафта справедливо для всех деревьев длины меньше <tex>n</tex>. Для данного дерева максимальной длины <tex>n</tex> ребра из первой вершины ведут к двум поддеревьям, длины которых не превышают <tex>n - 1</tex>; для этих поддеревьев имеем неравенства <tex>K_1 \leq leqslant 1</tex> и <tex>K_2 \leq leqslant 1</tex>, где <tex>K_1, K_2</tex> — значения соответствующих им сумм. Каждая длина <tex>l_i</tex> в поддереве увеличивается на <tex>1</tex>, когда поддерево присоединяется к основному дереву, поэтому возникает дополнительный множитель <tex>\dfrac{1}{2}</tex>. Таким образом, имеем <tex>\dfrac{1}{2} K_1 + \dfrac{1}{2} K_2 \leq leqslant 1</tex>.

В случае произвольного недвоичного основания <tex>r</tex> имеется не более <tex>r</tex> ребер, исходящих из каждой вершины, т. е. то есть не более <tex>r</tex> поддеревьев; каждое из них присоединяется к основному дереву, давая дополнительный множитель <tex>\dfrac{1}{r}</tex>. Отсюда снова следует утверждение теоремы.