Изменения

При необходимости построить префиксный код с большим числом кодовых слов заданной длины проверка существования такого кода может быть достаточно сложной.Но Рассматриваемое ниже неравенство Крафта даёт достаточное условие существования префиксных и любых [[Кодирование информации | однозначно декодируемых кодов]], обладающих заданным набором показывает для каких длин кодовых словсуществует префиксный код. 

|about=неравенство Крафта (англ. Kraft's inequality)

Для любого [[Кодирование информации | префиксного кода]] Пусть у нас есть <tex>Cn</tex>[[Основные определения, связанные со строками|символов]], отображающего произвольный алфавит кодовые слова которых имеют длины <tex>Al_1 \leqslant l_2 \leqslant \ldots \leqslant l_n </tex> на двоичный алфавит .  Тогда необходимое и достаточное условие существования префиксного кода в <tex> \{0,1\} r</tex> -ичном алфавите для данных символов, длины кодовых слов должны удовлетворять неравенствусостоит в выполнении неравенства:

<center><tex> \sum\limits_{i = 1}^{In} 2r ^{-l_i} \leqslant 1 , </tex></center>где <tex>|A| = I</tex> , а <tex>l_i</tex> {{---}} длины кодовых слов.

Рассмотрим отрезок [[file:Treeforkraft.jpg|thumb|250px|Иллюстрация к доказательству индукционного перехода]] '''Необходимость:''' Напомним, что префиксный код можно представить в виде <tex>r</tex>-ичного корневого дерева, рёбра которого соответствуют символам алфавита, а листья соответствующим кодам. Неравенство Крафта будем доказывать по [0;1[Математическая индукция|индукции]].  Для простоты рассмотрим сначала случай двоичного алфавита, то есть <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>M_0n - 1</tex>. Докажем, а правую что оно справедливо и для всех деревьев высоты меньше <tex>M_1n</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>M_jr</tex> имеется не превосходит более <tex> \max(l_1r</tex> ребер, l_2исходящих из каждой вершины,то есть не более <tex>r</tex> поддеревьев; каждое из них присоединяется к основному дереву, давая дополнительный множитель <tex>\ldots,l_I)dfrac{1}{r}</tex>. Отсюда снова следует утверждение теоремы.

Заметим, что'''Достаточность:*любому кодовому слову <tex>C_j</tex> сопоставлен свой отрезок <tex>M_{C_j}</tex> (Например, кодовому слову <tex>1011</tex> соответствует отрезок <tex>M_{1011}</tex>);*длина отрезка <tex>M_{C_i}</tex> равна <tex>2^{-l_i}</tex> (Например, <tex>M_0</tex> имеет длину <tex dpi="150"> \frac{1}{2}</tex>, а <tex>M_{00}</tex> соответственно <tex dpi="150"> \frac{1}{4}</tex>);*Если кодовое слово <tex>x</tex> является [[Основные определения, связанные со строками | префиксом]] кодового слова <tex>y</tex>, то отрезок <tex>M_x</tex> содержит <tex>M_y</tex> (Например, кодовое слово <tex>01</tex> является [[Основные определения, связанные со строками | префиксом]] <tex>0111</tex>, а отрезок<tex>M_{01}</tex> содержит <tex>M_{0111}</tex>, это его самая правая четверть);'''

Рассмотрим префиксный код [[file:Tree2forkraft.jpg|thumb|300px|Пример разбиения на группы, при <tex>Cr = 2</tex>: так как ни одно из кодовых слов не является [[Основные определения, связанные со строками | префиксомсимволах ''a, b, c'', где <tex> l_a = 2, l_b = 2, l_c = 1</tex>]] никакого другого кодового слова, то никакие два отрезка не пересекаются.

#Если некоторое <tex> l_i = 0 </tex> , то <tex> n = 1 </tex> . В таком случае пустая строка является искомым префиксным кодом. Далее все <tex> l_i \geqslant 1 </tex> . #Для доказательства корректности разделим длины <tex> l_i </tex> на отрезке <tex>[0;r</tex> , возможно пустых, групп, внутри каждой из которых <tex> \sum\limits r ^{-l_i} \leqslant \dfrac{1}{r} </tex> .#:Пусть у нас есть <tex>n</tex> символов, кодовые слова имеют длины <tex>l_1 \leqslant l_2 \leqslant \ldots \leqslant l_n </tex>. Давайте разделим данные символы на <tex>r</tex> групп, внутри каждой из которых <tex> \sum\limits r ^{-l_i} \leqslant \dfrac{1}{r} </tex> . Разделить символы на группы можно следующим жадным образом: брать <tex> l_i </tex> в порядке увеличения индекса.#:Докажем, что в таком случае группа будет либо полностью укомплектована <tex>(\sum\limits r ^{-l_i} = \dfrac{1]}{r})</tex> выбрать некоторое количество непересекающихся отрезков, то очевиднолибо будут исчерпаны все возможные <tex> l_i </tex> . Это следует из того, что сумма их длин не превзойдет при <tex>l_i \geqslant 1</tex>на <tex>i</tex>-ом шаге либо группа уже укомплектована, то есть либо ее остаток равен: #: <center><tex> \sumdfrac{1}{r} - \left ( r^{-l_1} + r^{-l_2} + \limits_ldots + r^{-l_{i -1}} \right ) = \dfrac{r^{l_i-1}- ( r^{l_i - l_1} + r^{l_i - l_2} + \ldots + r^{Il_i - l_{i - 1}} )} M_{C_ir^{l_i} }</tex></center>#:Так как группа не укомплектована, то числитель положителен. Если добавим <tex> l_i </tex> в группу, то числитель уменьшится на <tex>1</tex>, где <tex>l_i - l_j</tex> неотрицательно при <tex> i \geqslant j </tex> , и <tex> r \in \mathbb{N} </tex>. Следовательно числитель — натуральное число. Тогда, взяв <tex> l_i </tex> в группу, мы не перепрыгнем через максимальное значение, то есть сумма группы <tex> \leqslant \dfrac{1}{r} </tex> . А значит, создавая группы по данному алгоритму мы сможем построить <tex>r</tex> групп, удовлетворяющих условию.#Выберем для каждой группы свой начальный символ. Запуститим данную процедуру для каждой группы слов, предварительно обрезав первую букву.#По индукции по величине <tex> l_n </tex> докажем, что наш алгоритм корректен. #:'''База:''' При <tex> l_n = 0 </tex> корректность процедуры очевидна. #:'''Переход: ''' Допустим, что процедура корректна для <tex> l_n = w </tex> . Докажем, что процедура корректна и для <tex> l_n = w + 1 </tex> . #:Заметим, что у слов каждой группы будет своя начальная буква, поэтому достаточно проверить префиксность кода для каждой группы. А это истинно по предположению индукции, где для каждой группы <tex> l_i \leqslant w </tex>.

== Следствие Замечания ==Можно обобщить Когда имеет место строгое неравенство Крафта для случаев? Легко заметить, когда кодирующим алфавитом что если любая концевая вершина дерева является k-ичный. В доказательстве изменятся некоторые пункты:*отрезок кодовым словом, то <tex>[0;K = 1]</tex> придется делить . Строгое неравенство имеет место лишь в случае, когда некоторые из концевых вершин не используются. Однако, в случае двоичного кодового алфавита какая-нибудь концевая вершина не на <tex>2</tex>используется, то предыдущее решение оказывается лишним, и соответствующая цифра может быть удалена из каждого кодового слова, декодирование которого проходит через эту вершину. Таким образом, если имеет место строгое неравенство, то код неэффективен, а на <tex>k</tex> равных частейно для двоичных деревьев очевидно,как можно его улучшить. *соответственно неравенство примет вид: <tex>\sum\limits_{i = 1}^{I} k^{-l_i} \leqslant 1 </tex>Заметим еще раз, что теорема утверждает существование такого кода и ничего не говорит о конкретных кодах. Может существовать код, который удовлетворяет неравенству Крафта и тем не менее не является префиксным.