748
правок
Изменения
Нет описания правки
{{Теорема
|about=неравенство Крафта
|statement=
Тогда необходимое и достаточное условие существования префиксного кода в <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> {{---}} длины кодовых слов.
|proof=
В случае произвольного недвоичного основания <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> 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_limits r ^{-l_i} = \dfrac{1}{r})</tex>, либо будут исчерпаны все возможные <tex> l_i </tex> . Это следует из того, что при <tex> l_i \geqslant 1 </tex> на <tex>i = </tex>-ом шаге либо группа уже укомплектована, либо ее остаток равен: #: <center><tex> \dfrac{1}{r} - \left ( r^{I-l_1} M_+ r^{C_i-l_2} = + \sum\limits_ldots + r^{-l_{i -1}} \right ) = \dfrac{r^{l_i-1}- ( r^{Il_i - l_1} 2+ r^{l_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>Заметим еще раз, что теорема утверждает существование такого кода и ничего не говорит о конкретных кодах. Может существовать код, который удовлетворяет неравенству Крафта и тем не менее не является префиксным.
== Ссылки См.также ==*[http://ru.wikipedia.org/wiki/Неравенство_Крафта [Неравенство Крафта — ВикипедияМакмиллана]*[ftp://remotesensing.ru/InfoTheory_lec05.pdf Теория информации]
== Литература Источники информации ==* Александр Х[http://ru.wikipedia. Шень Программированиеorg/wiki/Неравенство_Крафта Википедия — Неравенство Крафта]*[http: теоремы и задачи//books.sernam. {{---}} Мru/book_htc.php?id=35 Неравенство Крафта]*[https: МЦНМО, 2007//xlinux. {{---}} Сnist. 208gov/dads/HTML/kraftsinqlty. {{---}} ISBN 978-5-94057-310-4html Kraft's inequality]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Алгоритмы сжатия]]