Изменения

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

|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> {{---}} длины кодовых слов.

Рассмотрим отрезок <tex>[0;1[file:Treeforkraft.jpg|thumb|250px|Иллюстрация к доказательству индукционного перехода]]</tex> на числовой прямой. '''Необходимость:'''

Разделим его пополамНапомним, причем левую половину обозначим что префиксный код можно представить в виде <tex>M_0r</tex>-ичного корневого дерева, рёбра которого соответствуют символам алфавита, а правую <tex>M_1</tex>листья соответствующим кодам. Неравенство Крафта будем доказывать по [[Математическая индукция|индукции]].

Затем поделим <tex>M_0</tex> пополам и обозначим его левую половину <tex>M_{00}</tex>, а правую <tex>M_{01}</tex>Для простоты рассмотрим сначала случай двоичного алфавита, и, проделав то же самое с <tex>M_1</tex>, получим <tex>M_{10}</tex>, а левую есть <tex>M_{11}r = 2</tex>.

Будем выполнять эти действия'''База:''' Если максимальная длина пути на дереве равна <tex>1</tex>, пока длина индекса полученного отрезка то в дереве есть одно или два ребра длины <tex>M_j1</tex> не превосходит . Таким образом, либо <tex> \max(l_1, l_2dfrac{1}{2} \leqslant 1 </tex> — для одного символа источника,либо <tex> \dfrac{1}{2} + \dfrac{1}{2} \ldots,l_I)leqslant 1 </tex>— для двух символов источника.

Заметим'''Переход:''' Предположим далее, что:*любому кодовому слову неравенство Крафта справедливо для всех деревьев высоты меньше <tex>C_jn - 1</tex> сопоставлен свой отрезок <tex>M_{C_j}</tex> (Например. Докажем, кодовому слову что оно справедливо и для всех деревьев высоты меньше <tex>1011n</tex> соответствует отрезок . Для данного дерева максимальной высоты <tex>M_{1011}n</tex>);*длина отрезка <tex>M_{C_i}</tex> равна ребра из первой вершины ведут к двум поддеревьям, высоты которых не превышают <tex>2^{n -l_i}1</tex> (Например, ; для этих поддеревьев имеем неравенства <tex>M_0K_1 \leqslant 1</tex> имеет длину и <tex dpi = 140> K_2 \frac12leqslant 1</tex>, а где <tex>M_{00}</tex> соответственно <tex dpi = 140> \frac14</tex>);*Если кодовое слово <tex>x</tex> является '''[[Основные определенияK_1, связанные со строками | префиксом]]''' кодового слова <tex>yK_2</tex>, то отрезок — значения соответствующих им сумм. Каждая длина <tex>M_xl_i</tex> содержит в поддереве увеличивается на <tex>M_y1</tex> (Например, кодовое слово <tex>01</tex> является '''[[Основные определениякогда поддерево присоединяется к основному дереву, связанные со строками | префиксом]]''' поэтому возникает дополнительный множитель <tex>0111\dfrac{1}{2}</tex>. Таким образом, а отрезокимеем <tex>M_\dfrac{1}{2} K_1 + \dfrac{011}</tex> содержит <tex>M_{01112}K_2 \leqslant 1</tex>, это его самая правая четверть);.

Если В случае произвольного недвоичного основания <tex>r</tex> имеется не более <tex>r</tex> ребер, исходящих из каждой вершины, то есть не более <tex>r</tex> поддеревьев; каждое из них присоединяется к основному дереву, давая дополнительный множитель <tex>\dfrac{1}{r}</tex>. Отсюда снова следует утверждение теоремы. '''Достаточность:''' [[file:Tree2forkraft.jpg|thumb|300px|Пример разбиения на отрезке группы, при <tex> r = 2</tex>, символах ''a, b, c'', где <tex>[0;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>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^{Il_i - l_1} M_+ r^{C_il_i - l_2} + \ldots + r^{l_i - l_{i - 1}} )}{r^{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>См.также ==*[[Неравенство Макмиллана]]

*[ftphttp://remotesensingbooks.sernam.ru/InfoTheory_lec05book_htc.pdf Теория информацииphp?id=35 Неравенство Крафта]* Александр Х. Шень Программирование[https: теоремы и задачи//xlinux. {{---}} Мnist.: МЦНМО, 2007gov/dads/HTML/kraftsinqlty. {{---}} С. 208. {{---}} ISBN 978-5-94057-310-4html Kraft's inequality]