Изменения

{{Определение |definition='''Кодом''' Рассматриваемое ниже неравенство Крафта показывает для алфавита <tex>A</tex> называется функция <tex>C</tex>, которая для каждого символа <tex>x</tex> из <tex>A</tex> указывает слово <tex>C(x)</tex>, кодирующее этот символкаких длин кодовых слов существует префиксный код.}}

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

Тогда необходимое и достаточное условие существования префиксного кода в <tex>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>[0;1]r</tex> на числовой прямой-ичного корневого дерева, рёбра которого соответствуют символам алфавита, а листья соответствующим кодам. Неравенство Крафта будем доказывать по [[Математическая индукция|индукции]].

Разделим его пополамДля простоты рассмотрим сначала случай двоичного алфавита, причем левую половину обозначим то есть <tex>M_0</tex>, а правую <tex>M_1r = 2</tex>.

Затем поделим '''База:''' Если максимальная длина пути на дереве равна <tex>M_01</tex> пополам и обозначим его левую половину , то в дереве есть одно или два ребра длины <tex>M_{00}1</tex>. Таким образом, а правую либо <tex>M_\dfrac{011}{2} \leqslant 1 </tex>— для одного символа источника, и, проделав то же самое с либо <tex>M_1</tex>, получим <tex>M_\dfrac{1}{2} + \dfrac{101}</tex>, а левую <tex>M_{112}\leqslant 1 </tex>— для двух символов источника.

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

Рассмотрим префиксный код В случае произвольного недвоичного основания <tex>Cr</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^{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;1]</tex> придется делить не на <tex>2</tex>, а на <tex>k</tex> равных частей;*соответственно неравенство примет вид: <tex>\sum\limits_{i = 1}^{I} k^{-l_i} \leqslant 1 </tex>.

Когда имеет место строгое неравенство? Легко заметить, что если любая концевая вершина дерева является кодовым словом, то <tex>K =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]