При необходимости построить префиксный код с большим числом кодовых слов заданной длины проверка существования такого кода может быть достаточно сложной.Но Рассматриваемое ниже неравенство Крафта даёт достаточное условие существования префиксных и любых [[Кодирование информации | однозначно декодируемых кодов]]показывает, обладающих заданным набором для каких длин кодовых словсуществует префиксный код, но не показывает, как его строить.
{{Теорема
|about=неравенство Крафта (англ. Kraft's inequality)
|statement=
Для любого [[Кодирование информации | Необходимое и достаточное условие существования префиксного кода]] для источника с алфавитом <tex>S</tex> из <tex>Cq</tex>, отображающего произвольный алфавит символов <tex>As_i</tex> на двоичный алфавит , где <tex> i\{0in \left [ 1,1q \} right ]</tex> , кодовые слова которого имеют длины кодовых слов должны удовлетворять неравенству<tex>l_1 \leq l_2 \leq ... \leq l_q</tex>, состоит в выполнении неравенства:
<center><tex> \sum\limits_{i = 1}^{Iq} 2r ^{-l_i} \leqslant 1 , </tex></center>где <tex>|A| = Ir</tex> , а <tex>l_i</tex> {{---}} длины кодовых словоснование (число символов) в кодовом алфавите.
|proof=
Рассмотрим отрезок <tex>[0;1[file:Treeforkraft.jpg|thumb|250px|Иллюстрация к доказательству индукционного перехода]]Неравенство Крафта легко доказать с помощью дерева декодирования, существование которого следует из существования префиксного кода. Будем рассуждать по [[Математическая индукция|индукции]]</tex> на числовой прямой.
Разделим его пополамДля простоты рассмотрим сначала случай двоичного алфавита, причем левую половину обозначим т. е. <tex>M_0r = 2</tex>. Если максимальная длина пути на дереве равна 1, а правую то на нем есть одно или два ребра длины 1. Таким образом, либо <tex> \frac{1}{2} \leq 1 </tex> — для одного символа источника, либо <tex>M_1\frac{1}{2} + \frac{1}{2} \leq 1 </tex>- для двух символов источника.
Затем поделим Предположим далее, что неравенство Крафта справедливо для всех деревьев длины меньше <tex>M_0n</tex> пополам и обозначим его левую половину . Для данного дерева максимальной длины <tex>M_{00}n</tex>ребра из первой вершины ведут к двум поддеревьям, а правую длины которых не превышают <tex>n - 1</tex>; для этих поддеревьев имеем неравенства <tex>K_1 \leq 1</tex> и <tex>M_{01}K_2 \leq 1</tex>, игде <tex>K_1, проделав то же самое с K_2</tex>M_1- значения соответствующих им сумм. Каждая длина <tex>l_i</tex>в поддереве увеличивается на 1, получим когда поддерево присоединяется к основному дереву, поэтому возникает дополнительный множитель <tex>M_\frac{101}{2}</tex>. Таким образом, а левую имеем <tex>M_\frac{1}{2} K_1 + \frac{1}{112}K_2 \leq 1</tex>.
Будем выполнять эти действия, пока длина индекса полученного отрезка В случае произвольного недвоичного основания <tex>M_jr</tex> имеется не превосходит более <tex> \max(l_1r</tex> ребер, l_2исходящих из каждой вершины,т. е. не более <tex>r</tex> поддеревьев; каждое из них присоединяется к основному дереву, давая дополнительный множитель <tex>\ldots,l_I)frac{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>, это его самая правая четверть);
Рассмотрим префиксный код <tex>C</tex>: так как ни одно из кодовых слов не является [[Основные определения, связанные со строками | префиксом]] никакого другого кодового слова, то никакие два отрезка не пересекаются.== Замечания ==
Если на отрезке Когда имеет место строгое неравенство? Легко заметить, что если любая концевая вершина дерева является кодовым словом, то <tex>[0;K = 1]</tex> выбрать некоторое количество непересекающихся отрезков. Строгое неравенство имеет место лишь в случае, когда некоторые из концевых вершин не используются. Однако, в случае двоичного кодового алфавита какая-нибудь концевая вершина не используется, то предыдущее решение оказывается лишним, и соответствующая цифра может быть удалена из каждого кодового слова, декодирование которого проходит через эту вершину. Таким образом, если имеет место строгое неравенство, то код неэффективен, но для двоичных деревьев очевидно, как можно его улучшить. Заметим еще раз, что сумма их длин теорема утверждает существование такого кода и ничего не превзойдет <tex>1</tex>говорит о конкретных кодах. Может существовать код, то есть <tex> \sum\limits_{i = 1}^{I} M_{C_i} \leqslant 1</tex>который удовлетворяет неравенству Крафта и тем не менее не является мгновенным.
Отсюда следует, что <tex>\sum\limits_{i = 1}^{I} M_{C_i} = \sum\limits_{i = 1}^{I} 2^{-l_i} \leqslant 1</tex>.
}}
== Следствие ==
Можно обобщить неравенство Крафта для случаев, когда кодирующим алфавитом является k-ичный. В доказательстве изменятся некоторые пункты:
*отрезок <tex>[0;1]</tex> придется делить не на <tex>2</tex>, а на <tex>k</tex> равных частей,
*соответственно неравенство примет вид: <tex>\sum\limits_{i = 1}^{I} k^{-l_i} \leqslant 1 </tex>.
== См.также ==
== Источники информации ==
*[http://ru.wikipedia.org/wiki/Неравенство_Крафта Википедия — Неравенство Крафта]
*[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]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Алгоритмы сжатия]]
