29
правок
Изменения
правки замечаний
Рассматриваемое ниже неравенство Крафта показывает, для каких длин кодовых слов существует префиксный код, но приведенное ниже доказательство не является конструктивным.
{{Теорема
|about=неравенство Крафта
|statement=
<center><tex> \sum\limits_{i = 1}^{n} r ^{-l_i} \leqslant 1 </tex></center>
[[file:Treeforkraft.jpg|thumb|250px|Иллюстрация к доказательству индукционного перехода]]
Для простоты рассмотрим сначала случай двоичного алфавита, то есть <tex>r = 2</tex>. База: Если максимальная длина пути на дереве равна <tex>1</tex>, то в дереве есть одно или два ребра длины <tex>1</tex>. Таким образом, либо <tex> \dfrac{1}{2} \leqslant 1 </tex> — для одного символа источника, либо <tex> \dfrac{1}{2} + \dfrac{1}{2} \leqslant 1 </tex> — для двух символов источника. Предположим далее, что неравенство Крафта справедливо для всех деревьев высоты меньше <tex>n - 1</tex>. Докажем, что оно справедливо и для всех деревьев высоты меньше <tex>n</tex>. Для данного дерева максимальной высоты <tex>n</tex> ребра из первой вершины ведут к двум поддеревьям, высоты которых не превышают <tex>n - 1</tex>; для этих поддеревьев имеем неравенства <tex>K_1 \leqslant 1</tex> и <tex>K_2 \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 \leqslant 1</tex>.
В случае произвольного недвоичного основания <tex>r</tex> имеется не более <tex>r</tex> ребер, исходящих из каждой вершины, то есть не более <tex>r</tex> поддеревьев; каждое из них присоединяется к основному дереву, давая дополнительный множитель <tex>\dfrac{1}{r}</tex>. Отсюда снова следует утверждение теоремы.
'''Достаточность:'''
Для доказательства достаточности опишем рекурсивную процедуру, которая строит код для данного набора длин <tex> l_i </tex>, удовлетворяющих неравенству <tex> \sum\limits_{i = 1}^{n} r ^{-l_i} \leqslant 1 </tex>.
Нужно разделить длины <tex> l_i </tex> на <tex>r</tex> групп, внутри каждой из которых <tex> \sum\limits r ^{-l_i} \leqslant \dfrac{1}{r} </tex>. У всех слов из слов из одной группы будет одна и та же начальная буква. Разделить длины на группы можно следующим жадным образом: брать <tex> l_i </tex> в порядке увеличения индекса. Несложно понять, что в таком случае группа будет либо полностью укомплектована, либо будут исчерпаны все возможные <tex> l_i </tex>. Затем нужно запустить данную процедуру для каждой группы слов, предварительно обрезав первую букву.
}}