http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&user=Damm1t&feedformat=atomВикиконспекты - Вклад участника [ru]2024-03-28T21:48:07ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B5%D1%80%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%9A%D1%80%D0%B0%D1%84%D1%82%D0%B0&diff=63324Неравенство Крафта2018-01-04T23:12:57Z<p>Damm1t: </p>
<hr />
<div><br />
Рассматриваемое ниже неравенство Крафта показывает для каких длин кодовых слов существует префиксный код.<br />
<br />
{{Теорема<br />
|about=неравенство Крафта <br />
|statement=<br />
Пусть у нас есть <tex>n</tex> [[Основные определения, связанные со строками|символов]], кодовые слова которые имеют длины <tex>l_1 \leqslant l_2 \leqslant \ldots \leqslant l_n </tex>. <br />
<br />
Тогда необходимое и достаточное условие существования префиксного кода в <tex>r</tex>-ичном алфавите для данных символов, состоит в выполнении неравенства:<br />
<br />
<center><tex> \sum\limits_{i = 1}^{n} r ^{-l_i} \leqslant 1 </tex></center><br />
<br />
|proof= <br />
<br />
[[file:Treeforkraft.jpg|thumb|250px|Иллюстрация к доказательству индукционного перехода]]<br />
<br />
'''Необходимость:'''<br />
<br />
Напомним, что префиксный код можно представить в виде <tex>r</tex>-ичного корневого дерева, рёбра которого соответствуют символам алфавита, а листья соответствующим кодам. Неравенство Крафта будем доказывать по [[Математическая индукция|индукции]]. <br />
<br />
Для простоты рассмотрим сначала случай двоичного алфавита, то есть <tex>r = 2</tex>. <br />
<br />
'''База:''' Если максимальная длина пути на дереве равна <tex>1</tex>, то в дереве есть одно или два ребра длины <tex>1</tex>. Таким образом, либо <tex> \dfrac{1}{2} \leqslant 1 </tex> — для одного символа источника, либо <tex> \dfrac{1}{2} + \dfrac{1}{2} \leqslant 1 </tex> — для двух символов источника. <br />
<br />
'''Переход:''' Предположим далее, что неравенство Крафта справедливо для всех деревьев высоты меньше <tex>n - 1</tex>. <br />
Докажем, что оно справедливо и для всех деревьев высоты меньше <tex>n</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>.<br />
<br />
<br />
В случае произвольного недвоичного основания <tex>r</tex> имеется не более <tex>r</tex> ребер, исходящих из каждой вершины, то есть не более <tex>r</tex> поддеревьев; каждое из них присоединяется к основному дереву, давая дополнительный множитель <tex>\dfrac{1}{r}</tex>. Отсюда снова следует утверждение теоремы.<br />
<br />
'''Достаточность:'''<br />
<br />
[[file:Tree2forkraft.jpg|thumb|300px|Пример разбиения на группы, при <tex> r = 2</tex>, символах ''a, b, c'', где <tex> l_a = 2, l_b = 2, l_c = 1</tex>]]<br />
<br />
#Если некоторое <tex> l_i = 0 </tex> , то <tex> n = 1 </tex> . В таком случае пустая строка является искомым префиксным кодом. Далее все <tex> l_i \geqslant 1 </tex> . <br />
#Для доказательства корректности разделим длины <tex> l_i </tex> на <tex>r</tex> , возможно пустых, групп, внутри каждой из которых <tex> \sum\limits r ^{-l_i} \leqslant \dfrac{1}{r} </tex> .<br />
#:Пусть у нас есть <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> в порядке увеличения индекса.<br />
#:Докажем, что в таком случае группа будет либо полностью укомплектована <tex>(\sum\limits r ^{-l_i} = \dfrac{1}{r})</tex>, либо будут исчерпаны все возможные <tex> l_i </tex> . Это следует из того, что при <tex> l_i \geqslant 1 </tex> на <tex>i</tex>-ом шаге либо группа уже укомплектована, либо ее остаток равен: <br />
#: <center><tex> \dfrac{1}{r} - \left ( r^{-l_1} + r^{-l_2} + \ldots + r^{-l_{i-1}} \right ) = \dfrac{r^{l_i-1} - ( r^{l_i - l_1} + r^{l_i - l_2} + \ldots + r^{l_i - l_{i - 1}} )}{r^{l_i}}</tex></center><br />
#:Так как группа не укомплектована, то числитель положителен. Если добавим <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> групп, удовлетворяющих условию.<br />
#Выберем для каждой группы свой начальный символ. Запуститим данную процедуру для каждой группы слов, предварительно обрезав первую букву.<br />
#По индукции по величине <tex> l_n </tex> докажем, что наш алгоритм корректен. <br />
#:'''База:''' При <tex> l_n = 0 </tex> корректность процедуры очевидна. <br />
#:'''Переход: ''' Допустим, что процедура корректна для <tex> l_n = w </tex> . Докажем, что процедура корректна и для <tex> l_n = w + 1 </tex> . <br />
#:Заметим, что у слов каждой группы будет своя начальная буква, поэтому достаточно проверить префиксность кода для каждой группы. А это истинно по предположению индукции, где для каждой группы <tex> l_i \leqslant w </tex> . <br />
<br />
}}<br />
<br />
== Замечания ==<br />
<br />
Когда имеет место строгое неравенство? Легко заметить, что если любая концевая вершина дерева является кодовым словом, то <tex>K = 1</tex>. Строгое неравенство имеет место лишь в случае, когда некоторые из концевых вершин не используются. Однако, в случае двоичного кодового алфавита какая-нибудь концевая вершина не используется, то предыдущее решение оказывается лишним, и соответствующая цифра может быть удалена из каждого кодового слова, декодирование которого проходит через эту вершину. Таким образом, если имеет место строгое неравенство, то код неэффективен, но для двоичных деревьев очевидно, как можно его улучшить.<br />
<br />
Заметим еще раз, что теорема утверждает существование такого кода и ничего не говорит о конкретных кодах. Может существовать код, который удовлетворяет неравенству Крафта и тем не менее не является префиксным.<br />
<br />
<br />
== См.также ==<br />
*[[Неравенство Макмиллана]]<br />
<br />
== Источники информации ==<br />
*[http://ru.wikipedia.org/wiki/Неравенство_Крафта Википедия — Неравенство Крафта]<br />
*[http://books.sernam.ru/book_htc.php?id=35 Неравенство Крафта]<br />
*[https://xlinux.nist.gov/dads/HTML/kraftsinqlty.html Kraft's inequality]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Алгоритмы сжатия]]</div>Damm1thttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B5%D1%80%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%9A%D1%80%D0%B0%D1%84%D1%82%D0%B0&diff=63323Неравенство Крафта2018-01-04T22:47:24Z<p>Damm1t: </p>
<hr />
<div><br />
Рассматриваемое ниже неравенство Крафта показывает для каких длин кодовых слов существует префиксный код.<br />
<br />
{{Теорема<br />
|about=неравенство Крафта <br />
|statement=<br />
Пусть у нас есть <tex>n</tex> [[Основные определения, связанные со строками|символов]], кодовые слова которые имеют длины <tex>l_1 \leqslant l_2 \leqslant \ldots \leqslant l_n </tex>. <br />
<br />
Тогда необходимое и достаточное условие существования префиксного кода в <tex>r</tex>-ичном алфавите для данных символов, состоит в выполнении неравенства:<br />
<br />
<center><tex> \sum\limits_{i = 1}^{n} r ^{-l_i} \leqslant 1 </tex></center><br />
<br />
|proof= <br />
<br />
[[file:Treeforkraft.jpg|thumb|250px|Иллюстрация к доказательству индукционного перехода]]<br />
<br />
'''Необходимость:'''<br />
<br />
Напомним, что префиксный код можно представить в виде <tex>r</tex>-ичного корневого дерева, рёбра которого соответствуют символам алфавита, а листья соответствующим кодам. Неравенство Крафта будем доказывать по [[Математическая индукция|индукции]]. <br />
<br />
Для простоты рассмотрим сначала случай двоичного алфавита, то есть <tex>r = 2</tex>. <br />
<br />
'''База:''' Если максимальная длина пути на дереве равна <tex>1</tex>, то в дереве есть одно или два ребра длины <tex>1</tex>. Таким образом, либо <tex> \dfrac{1}{2} \leqslant 1 </tex> — для одного символа источника, либо <tex> \dfrac{1}{2} + \dfrac{1}{2} \leqslant 1 </tex> — для двух символов источника. <br />
<br />
'''Переход:''' Предположим далее, что неравенство Крафта справедливо для всех деревьев высоты меньше <tex>n - 1</tex>. <br />
Докажем, что оно справедливо и для всех деревьев высоты меньше <tex>n</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>.<br />
<br />
<br />
В случае произвольного недвоичного основания <tex>r</tex> имеется не более <tex>r</tex> ребер, исходящих из каждой вершины, то есть не более <tex>r</tex> поддеревьев; каждое из них присоединяется к основному дереву, давая дополнительный множитель <tex>\dfrac{1}{r}</tex>. Отсюда снова следует утверждение теоремы.<br />
<br />
'''Достаточность:'''<br />
<br />
[[file:Tree2forkraft.jpg|thumb|300px|Пример разбиения на группы, при <tex> r = 2</tex>, символах ''a, b, c'', где <tex> l_a = 2, l_b = 2, l_c = 1</tex>]]<br />
<br />
#Если некоторое <tex> l_i = 0 </tex> , то <tex> n = 1 </tex> . В таком случае пустая строка является искомым префиксным кодом. Далее все <tex> l_i \geqslant 1 </tex> . <br />
#Для доказательства корректности разделим длины <tex> l_i </tex> на <tex>r</tex> , возможно пустых, групп, внутри каждой из которых <tex> \sum\limits r ^{-l_i} \leqslant \dfrac{1}{r} </tex> .<br />
#:Пусть у нас есть <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> в порядке увеличения индекса.<br />
#:Докажем, что в таком случае группа будет либо полностью укомплектована, либо будут исчерпаны все возможные <tex> l_i </tex> . Это следует из того, что при <tex> l_i \geqslant 1 </tex> на <tex>i</tex>-ом шаге либо группа уже укомплектована, либо ее остаток равен: <br />
#: <center><tex> \dfrac{1}{r} - \left ( r^{-l_1} + r^{-l_2} + \ldots + r^{-l_{i-1}} \right ) = \dfrac{r^{l_i-1} - ( r^{l_i - l_1} + r^{l_i - l_2} + \ldots + r^{l_i - l_{i - 1}} )}{r^{l_i}}</tex></center><br />
#:Так как группа не укомплектована, то числитель положителен. Если добавим <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> групп, удовлетворяющих условию.<br />
#Выберем для каждой группы свой начальный символ. Запуститим данную процедуру для каждой группы слов, предварительно обрезав первую букву.<br />
#По индукции по величине <tex> l_n </tex> докажем, что наш алгоритм корректен. <br />
#:'''База:''' При <tex> l_n = 0 </tex> корректность процедуры очевидна. <br />
#:'''Переход: ''' Допустим, что процедура корректна для <tex> l_n = w </tex> . Докажем, что процедура корректна и для <tex> l_n = w + 1 </tex> . <br />
#:Заметим, что у слов каждой группы будет своя начальная буква, поэтому достаточно проверить префиксность кода для каждой группы. А это истинно по предположению индукции, где для каждой группы <tex> l_i \leqslant w </tex> . <br />
<br />
}}<br />
<br />
== Замечания ==<br />
<br />
Когда имеет место строгое неравенство? Легко заметить, что если любая концевая вершина дерева является кодовым словом, то <tex>K = 1</tex>. Строгое неравенство имеет место лишь в случае, когда некоторые из концевых вершин не используются. Однако, в случае двоичного кодового алфавита какая-нибудь концевая вершина не используется, то предыдущее решение оказывается лишним, и соответствующая цифра может быть удалена из каждого кодового слова, декодирование которого проходит через эту вершину. Таким образом, если имеет место строгое неравенство, то код неэффективен, но для двоичных деревьев очевидно, как можно его улучшить.<br />
<br />
Заметим еще раз, что теорема утверждает существование такого кода и ничего не говорит о конкретных кодах. Может существовать код, который удовлетворяет неравенству Крафта и тем не менее не является префиксным.<br />
<br />
<br />
== См.также ==<br />
*[[Неравенство Макмиллана]]<br />
<br />
== Источники информации ==<br />
*[http://ru.wikipedia.org/wiki/Неравенство_Крафта Википедия — Неравенство Крафта]<br />
*[http://books.sernam.ru/book_htc.php?id=35 Неравенство Крафта]<br />
*[https://xlinux.nist.gov/dads/HTML/kraftsinqlty.html Kraft's inequality]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Алгоритмы сжатия]]</div>Damm1thttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B5%D1%80%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%9A%D1%80%D0%B0%D1%84%D1%82%D0%B0&diff=63322Неравенство Крафта2018-01-04T22:24:30Z<p>Damm1t: </p>
<hr />
<div><br />
Рассматриваемое ниже неравенство Крафта показывает для каких длин кодовых слов существует префиксный код.<br />
<br />
{{Теорема<br />
|about=неравенство Крафта <br />
|statement=<br />
Пусть у нас есть <tex>n</tex> [[Основные определения, связанные со строками|символов]], кодовые слова которого имеют длины <tex>l_1 \leqslant l_2 \leqslant \ldots \leqslant l_n </tex>. <br />
<br />
Тогда необходимое и достаточное условие существования префиксного кода в <tex>r</tex>-ичном алфавите для данных символов, состоит в выполнении неравенства:<br />
<br />
<center><tex> \sum\limits_{i = 1}^{n} r ^{-l_i} \leqslant 1 </tex></center><br />
<br />
|proof= <br />
<br />
[[file:Treeforkraft.jpg|thumb|250px|Иллюстрация к доказательству индукционного перехода]]<br />
<br />
'''Необходимость:'''<br />
<br />
Напомним, что префиксный код можно представить в виде <tex>r</tex>-ичного корневого дерева, рёбра которого соответствуют символам алфавита, а листья соответствующим кодам. Неравенство Крафта будем доказывать по [[Математическая индукция|индукции]]. <br />
<br />
Для простоты рассмотрим сначала случай двоичного алфавита, то есть <tex>r = 2</tex>. <br />
<br />
'''База:''' Если максимальная длина пути на дереве равна <tex>1</tex>, то в дереве есть одно или два ребра длины <tex>1</tex>. Таким образом, либо <tex> \dfrac{1}{2} \leqslant 1 </tex> — для одного символа источника, либо <tex> \dfrac{1}{2} + \dfrac{1}{2} \leqslant 1 </tex> — для двух символов источника. <br />
<br />
'''Переход:''' Предположим далее, что неравенство Крафта справедливо для всех деревьев высоты меньше <tex>n - 1</tex>. <br />
Докажем, что оно справедливо и для всех деревьев высоты меньше <tex>n</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>.<br />
<br />
<br />
В случае произвольного недвоичного основания <tex>r</tex> имеется не более <tex>r</tex> ребер, исходящих из каждой вершины, то есть не более <tex>r</tex> поддеревьев; каждое из них присоединяется к основному дереву, давая дополнительный множитель <tex>\dfrac{1}{r}</tex>. Отсюда снова следует утверждение теоремы.<br />
<br />
'''Достаточность:'''<br />
<br />
[[file:Tree2forkraft.jpg|thumb|300px|Пример разбиения на группы, при <tex> r = 2</tex>, символах ''a, b, c'', где <tex> l_a = 2, l_b = 2, l_c = 1</tex>]]<br />
<br />
#Если некоторое <tex> l_i = 0 </tex> , то <tex> n = 1 </tex> . В таком случае пустая строка является искомым префиксным кодом. Далее все <tex> l_i \geqslant 1 </tex> . <br />
#Для доказательства корректности разделим длины <tex> l_i </tex> на <tex>r</tex> , возможно пустых, групп, внутри каждой из которых <tex> \sum\limits r ^{-l_i} \leqslant \dfrac{1}{r} </tex> .<br />
#:Пусть у нас есть <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> в порядке увеличения индекса.<br />
#:Докажем, что в таком случае группа будет либо полностью укомплектована, либо будут исчерпаны все возможные <tex> l_i </tex> . Это следует из того, что при <tex> l_i \geqslant 1 </tex> на <tex>i</tex>-ом шаге либо группа уже укомплектована, либо ее остаток равен: <br />
#: <center><tex> \dfrac{1}{r} - \left ( r^{-l_1} + r^{-l_2} + \ldots + r^{-l_{i-1}} \right ) = \dfrac{r^{l_i-1} - ( r^{l_i - l_1} + r^{l_i - l_2} + \ldots + r^{l_i - l_{i - 1}} )}{r^{l_i}}</tex></center><br />
#:Так как группа не укомплектована, то числитель положителен. Если добавим <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> групп, удовлетворяющих условию.<br />
#Выберем для каждой группы свой начальный символ. Запуститим данную процедуру для каждой группы слов, предварительно обрезав первую букву.<br />
#По индукции по величине <tex> l_n </tex> докажем, что наш алгоритм корректен. <br />
#:'''База:''' При <tex> l_n = 0 </tex> корректность процедуры очевидна. <br />
#:'''Переход: ''' Допустим, что процедура корректна для <tex> l_n = w </tex> . Докажем, что процедура корректна и для <tex> l_n = w + 1 </tex> . <br />
#:Заметим, что у слов каждой группы будет своя начальная буква, поэтому достаточно проверить префиксность кода для каждой группы. А это истинно по предположению индукции, где для каждой группы <tex> l_i \leqslant w </tex> . <br />
<br />
}}<br />
<br />
== Замечания ==<br />
<br />
Когда имеет место строгое неравенство? Легко заметить, что если любая концевая вершина дерева является кодовым словом, то <tex>K = 1</tex>. Строгое неравенство имеет место лишь в случае, когда некоторые из концевых вершин не используются. Однако, в случае двоичного кодового алфавита какая-нибудь концевая вершина не используется, то предыдущее решение оказывается лишним, и соответствующая цифра может быть удалена из каждого кодового слова, декодирование которого проходит через эту вершину. Таким образом, если имеет место строгое неравенство, то код неэффективен, но для двоичных деревьев очевидно, как можно его улучшить.<br />
<br />
Заметим еще раз, что теорема утверждает существование такого кода и ничего не говорит о конкретных кодах. Может существовать код, который удовлетворяет неравенству Крафта и тем не менее не является префиксным.<br />
<br />
<br />
== См.также ==<br />
*[[Неравенство Макмиллана]]<br />
<br />
== Источники информации ==<br />
*[http://ru.wikipedia.org/wiki/Неравенство_Крафта Википедия — Неравенство Крафта]<br />
*[http://books.sernam.ru/book_htc.php?id=35 Неравенство Крафта]<br />
*[https://xlinux.nist.gov/dads/HTML/kraftsinqlty.html Kraft's inequality]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Алгоритмы сжатия]]</div>Damm1thttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Tree2forkraft.jpg&diff=63321Файл:Tree2forkraft.jpg2018-01-04T22:21:42Z<p>Damm1t: </p>
<hr />
<div></div>Damm1thttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B5%D1%80%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%9A%D1%80%D0%B0%D1%84%D1%82%D0%B0&diff=63320Неравенство Крафта2018-01-04T21:43:06Z<p>Damm1t: </p>
<hr />
<div><br />
Рассматриваемое ниже неравенство Крафта показывает для каких длин кодовых слов существует префиксный код.<br />
<br />
{{Теорема<br />
|about=неравенство Крафта <br />
|statement=<br />
Пусть у нас есть <tex>n</tex> [[Основные определения, связанные со строками|символов]], кодовые слова которого имеют длины <tex>l_1 \leqslant l_2 \leqslant \ldots \leqslant l_n </tex>. <br />
<br />
Тогда необходимое и достаточное условие существования префиксного кода в <tex>r</tex>-ичном алфавите для данных символов, состоит в выполнении неравенства:<br />
<br />
<center><tex> \sum\limits_{i = 1}^{n} r ^{-l_i} \leqslant 1 </tex></center><br />
<br />
|proof= <br />
<br />
[[file:Treeforkraft.jpg|thumb|250px|Иллюстрация к доказательству индукционного перехода]]<br />
<br />
'''Необходимость:'''<br />
<br />
Напомним, что префиксный код можно представить в виде <tex>r</tex>-ичного корневого дерева, рёбра которого соответствуют символам алфавита, а листья соответствующим кодам. Неравенство Крафта будем доказывать по [[Математическая индукция|индукции]]. <br />
<br />
Для простоты рассмотрим сначала случай двоичного алфавита, то есть <tex>r = 2</tex>. <br />
<br />
'''База:''' Если максимальная длина пути на дереве равна <tex>1</tex>, то в дереве есть одно или два ребра длины <tex>1</tex>. Таким образом, либо <tex> \dfrac{1}{2} \leqslant 1 </tex> — для одного символа источника, либо <tex> \dfrac{1}{2} + \dfrac{1}{2} \leqslant 1 </tex> — для двух символов источника. <br />
<br />
'''Переход:''' Предположим далее, что неравенство Крафта справедливо для всех деревьев высоты меньше <tex>n - 1</tex>. <br />
Докажем, что оно справедливо и для всех деревьев высоты меньше <tex>n</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>.<br />
<br />
<br />
В случае произвольного недвоичного основания <tex>r</tex> имеется не более <tex>r</tex> ребер, исходящих из каждой вершины, то есть не более <tex>r</tex> поддеревьев; каждое из них присоединяется к основному дереву, давая дополнительный множитель <tex>\dfrac{1}{r}</tex>. Отсюда снова следует утверждение теоремы.<br />
<br />
'''Достаточность:'''<br />
<br />
#Если некоторое <tex> l_i = 0 </tex> , то <tex> n = 1 </tex> . В таком случае пустая строка является искомым префиксным кодом. Далее все <tex> l_i \geqslant 1 </tex> . <br />
#Для доказательства корректности разделим длины <tex> l_i </tex> на <tex>r</tex> , возможно пустых, групп, внутри каждой из которых <tex> \sum\limits r ^{-l_i} \leqslant \dfrac{1}{r} </tex> .<br />
#:Пусть у нас есть <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> в порядке увеличения индекса.<br />
#:Докажем, что в таком случае группа будет либо полностью укомплектована, либо будут исчерпаны все возможные <tex> l_i </tex> . Это следует из того, что при <tex> l_i \geqslant 1 </tex> на <tex>i</tex>-ом шаге либо группа уже укомплектована, либо ее остаток равен: <br />
#: <center><tex> \dfrac{1}{r} - \left ( r^{-l_1} + r^{-l_2} + \ldots + r^{-l_{i-1}} \right ) = \dfrac{r^{l_i-1} - ( r^{l_i - l_1} + r^{l_i - l_2} + \ldots + r^{l_i - l_{i - 1}} )}{r^{l_i}}</tex></center><br />
#:Так как группа не укомплектована, то числитель положителен. Если добавим <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> групп, удовлетворяющих условию.<br />
#Выберем для каждой группы свой начальный символ. Запуститим данную процедуру для каждой группы слов, предварительно обрезав первую букву.<br />
#По индукции по величине <tex> l_n </tex> докажем, что наш алгоритм корректен. <br />
#:'''База:''' При <tex> l_n = 0 </tex> корректность процедуры очевидна. <br />
#:'''Переход: ''' Допустим, что процедура корректна для <tex> l_n = w </tex> . Докажем, что процедура корректна и для <tex> l_n = w + 1 </tex> . <br />
#:Заметим, что у слов каждой группы будет своя начальная буква, поэтому достаточно проверить префиксность кода для каждой группы. А это истинно по предположению индукции, где для каждой группы <tex> l_i \leqslant w </tex> . <br />
<br />
}}<br />
<br />
== Замечания ==<br />
<br />
Когда имеет место строгое неравенство? Легко заметить, что если любая концевая вершина дерева является кодовым словом, то <tex>K = 1</tex>. Строгое неравенство имеет место лишь в случае, когда некоторые из концевых вершин не используются. Однако, в случае двоичного кодового алфавита какая-нибудь концевая вершина не используется, то предыдущее решение оказывается лишним, и соответствующая цифра может быть удалена из каждого кодового слова, декодирование которого проходит через эту вершину. Таким образом, если имеет место строгое неравенство, то код неэффективен, но для двоичных деревьев очевидно, как можно его улучшить.<br />
<br />
Заметим еще раз, что теорема утверждает существование такого кода и ничего не говорит о конкретных кодах. Может существовать код, который удовлетворяет неравенству Крафта и тем не менее не является префиксным.<br />
<br />
<br />
== См.также ==<br />
*[[Неравенство Макмиллана]]<br />
<br />
== Источники информации ==<br />
*[http://ru.wikipedia.org/wiki/Неравенство_Крафта Википедия — Неравенство Крафта]<br />
*[http://books.sernam.ru/book_htc.php?id=35 Неравенство Крафта]<br />
*[https://xlinux.nist.gov/dads/HTML/kraftsinqlty.html Kraft's inequality]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Алгоритмы сжатия]]</div>Damm1thttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B5%D1%80%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%9A%D1%80%D0%B0%D1%84%D1%82%D0%B0&diff=63319Неравенство Крафта2018-01-04T21:39:47Z<p>Damm1t: </p>
<hr />
<div><br />
Рассматриваемое ниже неравенство Крафта показывает для каких длин кодовых слов существует префиксный код.<br />
<br />
{{Теорема<br />
|about=неравенство Крафта <br />
|statement=<br />
Пусть у нас есть <tex>n</tex> [[Основные определения, связанные со строками|символов]], кодовые слова которого имеют длины <tex>l_1 \leqslant l_2 \leqslant \ldots \leqslant l_n </tex>. <br />
<br />
Тогда необходимое и достаточное условие существования префиксного кода в <tex>r</tex>-ичном алфавите для данных символов, состоит в выполнении неравенства:<br />
<br />
<center><tex> \sum\limits_{i = 1}^{n} r ^{-l_i} \leqslant 1 </tex></center><br />
<br />
|proof= <br />
<br />
[[file:Treeforkraft.jpg|thumb|250px|Иллюстрация к доказательству индукционного перехода]]<br />
<br />
'''Необходимость:'''<br />
<br />
Напомним, что префиксный код можно представить в виде <tex>r</tex>-ичного корневого дерева, рёбра которого соответствуют символам алфавита, а листья соответствующим кодам. Неравенство Крафта будем доказывать по [[Математическая индукция|индукции]]. <br />
<br />
Для простоты рассмотрим сначала случай двоичного алфавита, то есть <tex>r = 2</tex>. <br />
<br />
'''База:''' Если максимальная длина пути на дереве равна <tex>1</tex>, то в дереве есть одно или два ребра длины <tex>1</tex>. Таким образом, либо <tex> \dfrac{1}{2} \leqslant 1 </tex> — для одного символа источника, либо <tex> \dfrac{1}{2} + \dfrac{1}{2} \leqslant 1 </tex> — для двух символов источника. <br />
<br />
'''Переход:''' Предположим далее, что неравенство Крафта справедливо для всех деревьев высоты меньше <tex>n - 1</tex>. <br />
Докажем, что оно справедливо и для всех деревьев высоты меньше <tex>n</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>.<br />
<br />
<br />
В случае произвольного недвоичного основания <tex>r</tex> имеется не более <tex>r</tex> ребер, исходящих из каждой вершины, то есть не более <tex>r</tex> поддеревьев; каждое из них присоединяется к основному дереву, давая дополнительный множитель <tex>\dfrac{1}{r}</tex>. Отсюда снова следует утверждение теоремы.<br />
<br />
'''Достаточность:'''<br />
<br />
#Если некоторое <tex> l_i = 0 </tex> , то <tex> n = 1 </tex> . В таком случае пустая строка является искомым префиксным кодом. Далее все <tex> l_i \geqslant 1 </tex> . <br />
#Для доказательства корректности разделим длины <tex> l_i </tex> на <tex>r</tex> групп, внутри каждой из которых <tex> \sum\limits r ^{-l_i} \leqslant \dfrac{1}{r} </tex> .<br />
#:Пусть у нас есть <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> в порядке увеличения индекса.<br />
#:Докажем, что в таком случае группа будет либо полностью укомплектована, либо будут исчерпаны все возможные <tex> l_i </tex> . Это следует из того, что при <tex> l_i \geqslant 1 </tex> на <tex>i</tex>-ом шаге либо группа уже укомплектована, либо ее остаток равен: <br />
#: <center><tex> \dfrac{1}{r} - \left ( r^{-l_1} + r^{-l_2} + \ldots + r^{-l_{i-1}} \right ) = \dfrac{r^{l_i-1} - ( r^{l_i - l_1} + r^{l_i - l_2} + \ldots + r^{l_i - l_{i - 1}} )}{r^{l_i}}</tex></center><br />
#:Так как группа не укомплектована, то числитель положителен. Если добавим <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> групп, удовлетворяющих условию.<br />
#Выберем для каждой группы свой начальный символ. Запуститим данную процедуру для каждой группы слов, предварительно обрезав первую букву.<br />
#По индукции по величине <tex> l_n </tex> докажем, что наш алгоритм корректен. <br />
#:'''База:''' При <tex> l_n = 0 </tex> корректность процедуры очевидна. <br />
#:'''Переход: ''' Допустим, что процедура корректна для <tex> l_n = w </tex> . Докажем, что процедура корректна и для <tex> l_n = w + 1 </tex> . <br />
#:Заметим, что у слов каждой группы будет своя начальная буква, поэтому достаточно проверить префиксность кода для каждой группы. А это истинно по предположению индукции, где для каждой группы <tex> l_i \leqslant w </tex> . <br />
<br />
}}<br />
<br />
== Замечания ==<br />
<br />
Когда имеет место строгое неравенство? Легко заметить, что если любая концевая вершина дерева является кодовым словом, то <tex>K = 1</tex>. Строгое неравенство имеет место лишь в случае, когда некоторые из концевых вершин не используются. Однако, в случае двоичного кодового алфавита какая-нибудь концевая вершина не используется, то предыдущее решение оказывается лишним, и соответствующая цифра может быть удалена из каждого кодового слова, декодирование которого проходит через эту вершину. Таким образом, если имеет место строгое неравенство, то код неэффективен, но для двоичных деревьев очевидно, как можно его улучшить.<br />
<br />
Заметим еще раз, что теорема утверждает существование такого кода и ничего не говорит о конкретных кодах. Может существовать код, который удовлетворяет неравенству Крафта и тем не менее не является префиксным.<br />
<br />
<br />
== См.также ==<br />
*[[Неравенство Макмиллана]]<br />
<br />
== Источники информации ==<br />
*[http://ru.wikipedia.org/wiki/Неравенство_Крафта Википедия — Неравенство Крафта]<br />
*[http://books.sernam.ru/book_htc.php?id=35 Неравенство Крафта]<br />
*[https://xlinux.nist.gov/dads/HTML/kraftsinqlty.html Kraft's inequality]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Алгоритмы сжатия]]</div>Damm1thttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B5%D1%80%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%9A%D1%80%D0%B0%D1%84%D1%82%D0%B0&diff=63318Неравенство Крафта2018-01-04T21:23:00Z<p>Damm1t: </p>
<hr />
<div><br />
Рассматриваемое ниже неравенство Крафта показывает для каких длин кодовых слов существует префиксный код.<br />
<br />
{{Теорема<br />
|about=неравенство Крафта <br />
|statement=<br />
Пусть у нас есть <tex>n</tex> [[Основные определения, связанные со строками|символов]], кодовые слова которого имеют длины <tex>l_1 \leqslant l_2 \leqslant \ldots \leqslant l_n </tex>. <br />
<br />
Тогда необходимое и достаточное условие существования префиксного кода в <tex>r</tex>-ичном алфавите для данных символов, состоит в выполнении неравенства:<br />
<br />
<center><tex> \sum\limits_{i = 1}^{n} r ^{-l_i} \leqslant 1 </tex></center><br />
<br />
|proof= <br />
<br />
[[file:Treeforkraft.jpg|thumb|250px|Иллюстрация к доказательству индукционного перехода]]<br />
<br />
'''Необходимость:'''<br />
<br />
Напомним, что префиксный код можно представить в виде <tex>r</tex>-ичного корневого дерева, рёбра которого соответствуют символам алфавита, а листья соответствующим кодам. Неравенство Крафта будем доказывать по [[Математическая индукция|индукции]]. <br />
<br />
Для простоты рассмотрим сначала случай двоичного алфавита, то есть <tex>r = 2</tex>. <br />
<br />
'''База:''' Если максимальная длина пути на дереве равна <tex>1</tex>, то в дереве есть одно или два ребра длины <tex>1</tex>. Таким образом, либо <tex> \dfrac{1}{2} \leqslant 1 </tex> — для одного символа источника, либо <tex> \dfrac{1}{2} + \dfrac{1}{2} \leqslant 1 </tex> — для двух символов источника. <br />
<br />
'''Переход:''' Предположим далее, что неравенство Крафта справедливо для всех деревьев высоты меньше <tex>n - 1</tex>. <br />
Докажем, что оно справедливо и для всех деревьев высоты меньше <tex>n</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>.<br />
<br />
<br />
В случае произвольного недвоичного основания <tex>r</tex> имеется не более <tex>r</tex> ребер, исходящих из каждой вершины, то есть не более <tex>r</tex> поддеревьев; каждое из них присоединяется к основному дереву, давая дополнительный множитель <tex>\dfrac{1}{r}</tex>. Отсюда снова следует утверждение теоремы.<br />
<br />
'''Достаточность:'''<br />
<br />
#Если некоторое <tex> l_i = 0 </tex> , то <tex> n = 1 </tex> . В таком случае пустая строка является искомым префиксным кодом. Далее все <tex> l_i \geqslant 1 </tex> . <br />
#Для доказательства корректности разделим длины <tex> l_i </tex> на не более <tex>r</tex> групп, внутри каждой из которых <tex> \sum\limits r ^{-l_i} \leqslant \dfrac{1}{r} </tex> .<br />
#:Пусть у нас есть <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> в порядке увеличения индекса.<br />
#:Докажем, что в таком случае группа будет либо полностью укомплектована, либо будут исчерпаны все возможные <tex> l_i </tex> . Это следует из того, что при <tex> l_i \geqslant 1 </tex> на <tex>i</tex>-ом шаге либо группа уже укомплектована, либо ее остаток равен: <br />
#: <center><tex> \dfrac{1}{r} - \left ( r^{-l_1} + r^{-l_2} + \ldots + r^{-l_{i-1}} \right ) = \dfrac{r^{l_i-1} - ( r^{l_i - l_1} + r^{l_i - l_2} + \ldots + r^{l_i - l_{i - 1}} )}{r^{l_i}}</tex></center><br />
#:Так как группа не укомплектована, то числитель положителен. Если добавим <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> групп, удовлетворяющих условию.<br />
#Выберем для каждой группы свой начальный символ. Запуститим данную процедуру для каждой группы слов, предварительно обрезав первую букву.<br />
#По индукции по величине <tex> l_n </tex> докажем, что наш алгоритм корректен. <br />
#:'''База:''' При <tex> l_n = 0 </tex> корректность процедуры очевидна. <br />
#:'''Переход: ''' Допустим, что процедура корректна для <tex> l_n = w </tex> . Докажем, что процедура корректна и для <tex> l_n = w + 1 </tex> . <br />
#:Заметим, что у слов каждой группы будет своя начальная буква, поэтому достаточно проверить префиксность кода для каждой группы. А это истинно по предположению индукции, где для каждой группы <tex> l_i \leqslant w </tex> . <br />
<br />
}}<br />
<br />
== Замечания ==<br />
<br />
Когда имеет место строгое неравенство? Легко заметить, что если любая концевая вершина дерева является кодовым словом, то <tex>K = 1</tex>. Строгое неравенство имеет место лишь в случае, когда некоторые из концевых вершин не используются. Однако, в случае двоичного кодового алфавита какая-нибудь концевая вершина не используется, то предыдущее решение оказывается лишним, и соответствующая цифра может быть удалена из каждого кодового слова, декодирование которого проходит через эту вершину. Таким образом, если имеет место строгое неравенство, то код неэффективен, но для двоичных деревьев очевидно, как можно его улучшить.<br />
<br />
Заметим еще раз, что теорема утверждает существование такого кода и ничего не говорит о конкретных кодах. Может существовать код, который удовлетворяет неравенству Крафта и тем не менее не является префиксным.<br />
<br />
<br />
== См.также ==<br />
*[[Неравенство Макмиллана]]<br />
<br />
== Источники информации ==<br />
*[http://ru.wikipedia.org/wiki/Неравенство_Крафта Википедия — Неравенство Крафта]<br />
*[http://books.sernam.ru/book_htc.php?id=35 Неравенство Крафта]<br />
*[https://xlinux.nist.gov/dads/HTML/kraftsinqlty.html Kraft's inequality]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Алгоритмы сжатия]]</div>Damm1thttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B5%D1%80%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%9A%D1%80%D0%B0%D1%84%D1%82%D0%B0&diff=63317Неравенство Крафта2018-01-04T21:21:55Z<p>Damm1t: </p>
<hr />
<div><br />
Рассматриваемое ниже неравенство Крафта показывает для каких длин кодовых слов существует префиксный код.<br />
<br />
{{Теорема<br />
|about=неравенство Крафта <br />
|statement=<br />
Пусть у нас есть <tex>n</tex> [[Основные определения, связанные со строками|символов]], кодовые слова которого имеют длины <tex>l_1 \leqslant l_2 \leqslant \ldots \leqslant l_n </tex>. <br />
<br />
Тогда необходимое и достаточное условие существования префиксного кода в <tex>r</tex>-ичном алфавите для данных символов, состоит в выполнении неравенства:<br />
<br />
<center><tex> \sum\limits_{i = 1}^{n} r ^{-l_i} \leqslant 1 </tex></center><br />
<br />
|proof= <br />
<br />
[[file:Treeforkraft.jpg|thumb|250px|Иллюстрация к доказательству индукционного перехода]]<br />
<br />
'''Необходимость:'''<br />
<br />
Напомним, что префиксный код можно представить в виде <tex>r</tex>-ичного корневого дерева, рёбра которого соответствуют символам алфавита, а листья соответствующим кодам. Неравенство Крафта будем доказывать по [[Математическая индукция|индукции]]. <br />
<br />
Для простоты рассмотрим сначала случай двоичного алфавита, то есть <tex>r = 2</tex>. <br />
<br />
'''База:''' Если максимальная длина пути на дереве равна <tex>1</tex>, то в дереве есть одно или два ребра длины <tex>1</tex>. Таким образом, либо <tex> \dfrac{1}{2} \leqslant 1 </tex> — для одного символа источника, либо <tex> \dfrac{1}{2} + \dfrac{1}{2} \leqslant 1 </tex> — для двух символов источника. <br />
<br />
'''Переход:''' Предположим далее, что неравенство Крафта справедливо для всех деревьев высоты меньше <tex>n - 1</tex>. <br />
Докажем, что оно справедливо и для всех деревьев высоты меньше <tex>n</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>.<br />
<br />
<br />
В случае произвольного недвоичного основания <tex>r</tex> имеется не более <tex>r</tex> ребер, исходящих из каждой вершины, то есть не более <tex>r</tex> поддеревьев; каждое из них присоединяется к основному дереву, давая дополнительный множитель <tex>\dfrac{1}{r}</tex>. Отсюда снова следует утверждение теоремы.<br />
<br />
'''Достаточность:'''<br />
<br />
#Если некоторое <tex> l_i = 0 </tex> , то <tex> n = 1 </tex> . В таком случае пустая строка является искомым префиксным кодом. Далее все <tex> l_i \geqslant 1 </tex> . <br />
#Для доказательства корректности разделим длины <tex> l_i </tex> на не более <tex>r</tex> групп, внутри каждой из которых <tex> \sum\limits r ^{-l_i} \leqslant \dfrac{1}{r} </tex> .<br />
#:Пусть у нас есть <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> в порядке увеличения индекса.<br />
#:Докажем, что в таком случае группа будет либо полностью укомплектована, либо будут исчерпаны все возможные <tex> l_i </tex> . Это следует из того, что при <tex> l_i \geqslant 1 </tex> на <tex>i</tex>-ом шаге либо группа уже укомплектована, либо ее остаток равен: <br />
#: <center><tex> \dfrac{1}{r} - \left ( r^{-l_1} + r^{-l_2} + \ldots + r^{-l_{i-1}} \right ) = \dfrac{r^{l_i-1} - ( r^{l_i - l_1} + r^{l_i - l_2} + \ldots + r^{l_i - l_{i - 1}} )}{r^{l_i}}</tex></center><br />
#:Так как группа не укомплектована, то числитель положителен. Если добавим <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> групп, удовлетворяющих условию.<br />
#:Заметим, что при этом только последняя группа будет <tex> \leqslant \dfrac{1}{r} </tex>, остальные будут равны <tex> \dfrac{1}{r} </tex> .<br />
#Выберем для каждой группы свой начальный символ. Запуститим данную процедуру для каждой группы слов, предварительно обрезав первую букву.<br />
#По индукции по величине <tex> l_n </tex> докажем, что наш алгоритм корректен. <br />
#:'''База:''' При <tex> l_n = 0 </tex> корректность процедуры очевидна. <br />
#:'''Переход: ''' Допустим, что процедура корректна для <tex> l_n = w </tex> . Докажем, что процедура корректна и для <tex> l_n = w + 1 </tex> . <br />
#:Заметим, что у слов каждой группы будет своя начальная буква, поэтому достаточно проверить префиксность кода для каждой группы. А это истинно по предположению индукции, где для каждой группы <tex> l_i \leqslant w </tex> . <br />
<br />
}}<br />
<br />
== Замечания ==<br />
<br />
Когда имеет место строгое неравенство? Легко заметить, что если любая концевая вершина дерева является кодовым словом, то <tex>K = 1</tex>. Строгое неравенство имеет место лишь в случае, когда некоторые из концевых вершин не используются. Однако, в случае двоичного кодового алфавита какая-нибудь концевая вершина не используется, то предыдущее решение оказывается лишним, и соответствующая цифра может быть удалена из каждого кодового слова, декодирование которого проходит через эту вершину. Таким образом, если имеет место строгое неравенство, то код неэффективен, но для двоичных деревьев очевидно, как можно его улучшить.<br />
<br />
Заметим еще раз, что теорема утверждает существование такого кода и ничего не говорит о конкретных кодах. Может существовать код, который удовлетворяет неравенству Крафта и тем не менее не является префиксным.<br />
<br />
<br />
== См.также ==<br />
*[[Неравенство Макмиллана]]<br />
<br />
== Источники информации ==<br />
*[http://ru.wikipedia.org/wiki/Неравенство_Крафта Википедия — Неравенство Крафта]<br />
*[http://books.sernam.ru/book_htc.php?id=35 Неравенство Крафта]<br />
*[https://xlinux.nist.gov/dads/HTML/kraftsinqlty.html Kraft's inequality]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Алгоритмы сжатия]]</div>Damm1thttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B5%D1%80%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%9A%D1%80%D0%B0%D1%84%D1%82%D0%B0&diff=63315Неравенство Крафта2018-01-04T00:20:50Z<p>Damm1t: </p>
<hr />
<div><br />
Рассматриваемое ниже неравенство Крафта показывает для каких длин кодовых слов существует префиксный код.<br />
<br />
{{Теорема<br />
|about=неравенство Крафта <br />
|statement=<br />
Пусть у нас есть <tex>n</tex> [[Основные определения, связанные со строками|символов]], кодовые слова которого имеют длины <tex>l_1 \leqslant l_2 \leqslant \ldots \leqslant l_n </tex>. <br />
<br />
Тогда необходимое и достаточное условие существования префиксного кода в <tex>r</tex>-ичном алфавите для символов из <tex>\Sigma</tex>, состоит в выполнении неравенства:<br />
<br />
<center><tex> \sum\limits_{i = 1}^{n} r ^{-l_i} \leqslant 1 </tex></center><br />
<br />
|proof= <br />
<br />
[[file:Treeforkraft.jpg|thumb|250px|Иллюстрация к доказательству индукционного перехода]]<br />
<br />
'''Необходимость:'''<br />
<br />
Напомним, что префиксный код можно представить в виде <tex>r</tex>-ичного корневого дерева, рёбра которого соответствуют символам алфавита, а листья соответствующим кодам. Неравенство Крафта будем доказывать по [[Математическая индукция|индукции]]. <br />
<br />
Для простоты рассмотрим сначала случай двоичного алфавита, то есть <tex>r = 2</tex>. <br />
<br />
'''База:''' Если максимальная длина пути на дереве равна <tex>1</tex>, то в дереве есть одно или два ребра длины <tex>1</tex>. Таким образом, либо <tex> \dfrac{1}{2} \leqslant 1 </tex> — для одного символа источника, либо <tex> \dfrac{1}{2} + \dfrac{1}{2} \leqslant 1 </tex> — для двух символов источника. <br />
<br />
'''Переход:''' Предположим далее, что неравенство Крафта справедливо для всех деревьев высоты меньше <tex>n - 1</tex>. <br />
Докажем, что оно справедливо и для всех деревьев высоты меньше <tex>n</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>.<br />
<br />
<br />
В случае произвольного недвоичного основания <tex>r</tex> имеется не более <tex>r</tex> ребер, исходящих из каждой вершины, то есть не более <tex>r</tex> поддеревьев; каждое из них присоединяется к основному дереву, давая дополнительный множитель <tex>\dfrac{1}{r}</tex>. Отсюда снова следует утверждение теоремы.<br />
<br />
'''Достаточность:'''<br />
<br />
#Если некоторое <tex> l_i = 0 </tex> , то <tex> n = 1 </tex> . В таком случае пустая строка является искомым префиксным кодом. Далее все <tex> l_i \geqslant 1 </tex> . <br />
#Для доказательства корректности разделим длины <tex> l_i </tex> на не более <tex>r</tex> групп, внутри каждой из которых <tex> \sum\limits r ^{-l_i} \leqslant \dfrac{1}{r} </tex> .<br />
#:Пусть у нас есть <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> в порядке увеличения индекса.<br />
#:Докажем, что в таком случае группа будет либо полностью укомплектована, либо будут исчерпаны все возможные <tex> l_i </tex> . Это следует из того, что при <tex> l_i \geqslant 1 </tex> на <tex>i</tex>-ом шаге либо группа уже укомплектована, либо ее остаток равен: <br />
#: <center><tex> \dfrac{1}{r} - \left ( r^{-l_1} + r^{-l_2} + \ldots + r^{-l_{i-1}} \right ) = \dfrac{r^{l_i-1} - ( r^{l_i - l_1} + r^{l_i - l_2} + \ldots + r^{l_i - l_{i - 1}} )}{r^{l_i}}</tex></center><br />
#:Так как группа не укомплектована, то числитель положителен. Если добавим <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> групп, удовлетворяющих условию.<br />
#:Заметим, что при этом только последняя группа будет <tex> \leqslant \dfrac{1}{r} </tex>, остальные будут равны <tex> \dfrac{1}{r} </tex> .<br />
#Выберем для каждой группы свой начальный символ. Запуститим данную процедуру для каждой группы слов, предварительно обрезав первую букву.<br />
#По индукции по величине <tex> l_n </tex> докажем, что наш алгоритм корректен. <br />
#:'''База:''' При <tex> l_n = 0 </tex> корректность процедуры очевидна. <br />
#:'''Переход: ''' Допустим, что процедура корректна для <tex> l_n = w </tex> . Докажем, что процедура корректна и для <tex> l_n = w + 1 </tex> . <br />
#:Заметим, что у слов каждой группы будет своя начальная буква, поэтому достаточно проверить префиксность кода для каждой группы. А это истинно по предположению индукции, где для каждой группы <tex> l_i \leqslant w </tex> . <br />
<br />
}}<br />
<br />
== Замечания ==<br />
<br />
Когда имеет место строгое неравенство? Легко заметить, что если любая концевая вершина дерева является кодовым словом, то <tex>K = 1</tex>. Строгое неравенство имеет место лишь в случае, когда некоторые из концевых вершин не используются. Однако, в случае двоичного кодового алфавита какая-нибудь концевая вершина не используется, то предыдущее решение оказывается лишним, и соответствующая цифра может быть удалена из каждого кодового слова, декодирование которого проходит через эту вершину. Таким образом, если имеет место строгое неравенство, то код неэффективен, но для двоичных деревьев очевидно, как можно его улучшить.<br />
<br />
Заметим еще раз, что теорема утверждает существование такого кода и ничего не говорит о конкретных кодах. Может существовать код, который удовлетворяет неравенству Крафта и тем не менее не является префиксным.<br />
<br />
<br />
== См.также ==<br />
*[[Неравенство Макмиллана]]<br />
<br />
== Источники информации ==<br />
*[http://ru.wikipedia.org/wiki/Неравенство_Крафта Википедия — Неравенство Крафта]<br />
*[http://books.sernam.ru/book_htc.php?id=35 Неравенство Крафта]<br />
*[https://xlinux.nist.gov/dads/HTML/kraftsinqlty.html Kraft's inequality]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Алгоритмы сжатия]]</div>Damm1thttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B5%D1%80%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%9A%D1%80%D0%B0%D1%84%D1%82%D0%B0&diff=63314Неравенство Крафта2018-01-04T00:17:57Z<p>Damm1t: </p>
<hr />
<div><br />
Рассматриваемое ниже неравенство Крафта показывает для каких длин кодовых слов существует префиксный код.<br />
<br />
{{Теорема<br />
|about=неравенство Крафта <br />
|statement=<br />
Пусть у нас есть <tex>n</tex> [[Основные определения, связанные со строками|символов]], кодовые слова которого имеют длины <tex>l_1 \leqslant l_2 \leqslant \ldots \leqslant l_n </tex>. <br />
<br />
Тогда необходимое и достаточное условие существования префиксного кода в <tex>r</tex>-ичном алфавите для символов из <tex>\Sigma</tex>, состоит в выполнении неравенства:<br />
<br />
<center><tex> \sum\limits_{i = 1}^{n} r ^{-l_i} \leqslant 1 </tex></center><br />
<br />
|proof= <br />
<br />
[[file:Treeforkraft.jpg|thumb|250px|Иллюстрация к доказательству индукционного перехода]]<br />
<br />
'''Необходимость:'''<br />
<br />
Напомним, что префиксный код можно представить в виде <tex>r</tex>-ичного корневого дерева, рёбра которого соответствуют символам алфавита, а листья соответствующим кодам. Неравенство Крафта будем доказывать по [[Математическая индукция|индукции]]. <br />
<br />
Для простоты рассмотрим сначала случай двоичного алфавита, то есть <tex>r = 2</tex>. <br />
<br />
'''База:''' Если максимальная длина пути на дереве равна <tex>1</tex>, то в дереве есть одно или два ребра длины <tex>1</tex>. Таким образом, либо <tex> \dfrac{1}{2} \leqslant 1 </tex> — для одного символа источника, либо <tex> \dfrac{1}{2} + \dfrac{1}{2} \leqslant 1 </tex> — для двух символов источника. <br />
<br />
'''Переход:''' Предположим далее, что неравенство Крафта справедливо для всех деревьев высоты меньше <tex>n - 1</tex>. <br />
Докажем, что оно справедливо и для всех деревьев высоты меньше <tex>n</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>.<br />
<br />
<br />
В случае произвольного недвоичного основания <tex>r</tex> имеется не более <tex>r</tex> ребер, исходящих из каждой вершины, то есть не более <tex>r</tex> поддеревьев; каждое из них присоединяется к основному дереву, давая дополнительный множитель <tex>\dfrac{1}{r}</tex>. Отсюда снова следует утверждение теоремы.<br />
<br />
'''Достаточность:'''<br />
<br />
#Если некоторое <tex> l_i = 0 </tex> , то <tex> n = 1 </tex> . В таком случае пустая строка является искомым префиксным кодом. Далее все <tex> l_i \geqslant 1 </tex> . <br />
#Для доказательства корректности разделим длины <tex> l_i </tex> на не более <tex>r</tex> групп, внутри каждой из которых <tex> \sum\limits r ^{-l_i} \leqslant \dfrac{1}{r} </tex> .<br />
#:Пусть у нас есть <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> в порядке увеличения индекса.<br />
#:Докажем, что в таком случае группа будет либо полностью укомплектована, либо будут исчерпаны все возможные <tex> l_i </tex> . Это следует из того, что при <tex> l_i \geqslant 1 </tex> на <tex>i</tex>-ом шаге либо группа уже укомплектована, либо ее остаток равен: <br />
#: <center><tex> \dfrac{1}{r} - \left ( r^{-l_1} + r^{-l_2} + \ldots + r^{-l_{i-1}} \right ) = \dfrac{r^{l_i-1} - ( r^{l_i - l_1} + r^{l_i - l_2} + \ldots + r^{l_i - l_{i - 1}} )}{r^{l_i}}</tex></center><br />
#:Так как группа не укомплектована, то числитель положителен. Если добавим <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> \sum\limits_{j = 1}^{i} r ^{-l_j} \leqslant \dfrac{1}{r} </tex> . А значит, создавая группы по данному алгоритму мы сможем построить <tex>r</tex> групп, удовлетворяющих условию.<br />
#:Заметим, что при этом только последняя группа будет <tex> \leqslant \dfrac{1}{r} </tex>, остальные будут равны <tex> \dfrac{1}{r} </tex> .<br />
#Выберем для каждой группы свой начальный символ. Запуститим данную процедуру для каждой группы слов, предварительно обрезав первую букву.<br />
#По индукции по величине <tex> l_n </tex> докажем, что наш алгоритм корректен. <br />
#:'''База:''' При <tex> l_n = 0 </tex> корректность процедуры очевидна. <br />
#:'''Переход: ''' Допустим, что процедура корректна для <tex> l_n = w </tex> . Докажем, что процедура корректна и для <tex> l_n = w + 1 </tex> . <br />
#:Заметим, что у слов каждой группы будет своя начальная буква, поэтому достаточно проверить префиксность кода для каждой группы. А это истинно по предположению индукции, где для каждой группы <tex> l_i \leqslant w </tex> . <br />
<br />
}}<br />
<br />
== Замечания ==<br />
<br />
Когда имеет место строгое неравенство? Легко заметить, что если любая концевая вершина дерева является кодовым словом, то <tex>K = 1</tex>. Строгое неравенство имеет место лишь в случае, когда некоторые из концевых вершин не используются. Однако, в случае двоичного кодового алфавита какая-нибудь концевая вершина не используется, то предыдущее решение оказывается лишним, и соответствующая цифра может быть удалена из каждого кодового слова, декодирование которого проходит через эту вершину. Таким образом, если имеет место строгое неравенство, то код неэффективен, но для двоичных деревьев очевидно, как можно его улучшить.<br />
<br />
Заметим еще раз, что теорема утверждает существование такого кода и ничего не говорит о конкретных кодах. Может существовать код, который удовлетворяет неравенству Крафта и тем не менее не является префиксным.<br />
<br />
<br />
== См.также ==<br />
*[[Неравенство Макмиллана]]<br />
<br />
== Источники информации ==<br />
*[http://ru.wikipedia.org/wiki/Неравенство_Крафта Википедия — Неравенство Крафта]<br />
*[http://books.sernam.ru/book_htc.php?id=35 Неравенство Крафта]<br />
*[https://xlinux.nist.gov/dads/HTML/kraftsinqlty.html Kraft's inequality]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Алгоритмы сжатия]]</div>Damm1thttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B5%D1%80%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%9A%D1%80%D0%B0%D1%84%D1%82%D0%B0&diff=63307Неравенство Крафта2018-01-03T14:20:24Z<p>Damm1t: </p>
<hr />
<div><br />
Рассматриваемое ниже неравенство Крафта показывает для каких длин кодовых слов существует префиксный код.<br />
<br />
{{Теорема<br />
|about=неравенство Крафта <br />
|statement=<br />
Пусть <tex>\Sigma</tex> — [[Основные определения, связанные со строками|алфавит]] из <tex>n</tex> [[Основные определения, связанные со строками|символов]], кодовые слова которого имеют длины <tex>l_1 \leqslant l_2 \leqslant \ldots \leqslant l_n </tex>. <br />
<br />
Тогда необходимое и достаточное условие существования префиксного кода в <tex>r</tex>-ичном алфавите для символов из <tex>\Sigma</tex>, состоит в выполнении неравенства:<br />
<br />
<center><tex> \sum\limits_{i = 1}^{n} r ^{-l_i} \leqslant 1 </tex></center><br />
<br />
|proof= <br />
<br />
[[file:Treeforkraft.jpg|thumb|250px|Иллюстрация к доказательству индукционного перехода]]<br />
<br />
'''Необходимость:'''<br />
<br />
Напомним, что префиксный код можно представить в виде <tex>r</tex>-ичного корневого дерева, рёбра которого соответствуют символам алфавита, а листья соответствующим кодам. Неравенство Крафта будем доказывать по [[Математическая индукция|индукции]]. <br />
<br />
Для простоты рассмотрим сначала случай двоичного алфавита, то есть <tex>r = 2</tex>. <br />
<br />
'''База:''' Если максимальная длина пути на дереве равна <tex>1</tex>, то в дереве есть одно или два ребра длины <tex>1</tex>. Таким образом, либо <tex> \dfrac{1}{2} \leqslant 1 </tex> — для одного символа источника, либо <tex> \dfrac{1}{2} + \dfrac{1}{2} \leqslant 1 </tex> — для двух символов источника. <br />
<br />
'''Переход:''' Предположим далее, что неравенство Крафта справедливо для всех деревьев высоты меньше <tex>n - 1</tex>. <br />
Докажем, что оно справедливо и для всех деревьев высоты меньше <tex>n</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>.<br />
<br />
<br />
В случае произвольного недвоичного основания <tex>r</tex> имеется не более <tex>r</tex> ребер, исходящих из каждой вершины, то есть не более <tex>r</tex> поддеревьев; каждое из них присоединяется к основному дереву, давая дополнительный множитель <tex>\dfrac{1}{r}</tex>. Отсюда снова следует утверждение теоремы.<br />
<br />
'''Достаточность:'''<br />
<br />
#Если некоторое <tex> l_i = 0 </tex> , то <tex> n = 1 </tex> . В таком случае пустая строка является искомым префиксным кодом. Далее все <tex> l_i \geqslant 1 </tex> . <br />
#Для доказательства корректности разделим длины <tex> l_i </tex> на не более <tex>r</tex> групп, внутри каждой из которых <tex> \sum\limits r ^{-l_i} \leqslant \dfrac{1}{r} </tex> .<br />
#:Пусть у нас есть <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> в порядке увеличения индекса.<br />
#:Докажем, что в таком случае группа будет либо полностью укомплектована, либо будут исчерпаны все возможные <tex> l_i </tex> . Это следует из того, что при <tex> l_i \geqslant 1 </tex> на <tex>i</tex>-ом шаге либо группа уже укомплектована, либо ее остаток равен: <br />
#: <center><tex> \dfrac{1}{r} - \left ( r^{-l_1} + r^{-l_2} + \ldots + r^{-l_{i-1}} \right ) = \dfrac{r^{l_i-1} - ( r^{l_i - l_1} + r^{l_i - l_2} + \ldots + r^{l_i - l_{i - 1}} )}{r^{l_i}}</tex></center><br />
#:Так как группа не укомплектована, то числитель положителен. Если добавим <tex> l_i </tex> в группу, то числитель уменьшится на <tex>1</tex>, где <tex>l_i \in \mathbb{N}, r \in \mathbb{N} </tex>. Следовательно числитель натуральное число. Тогда, взяв <tex> l_i </tex> в группу, мы не перепрыгнем через максимальное значение, то есть сумма: <tex> \sum\limits_{j = 1}^{i} r ^{-l_j} \leqslant \dfrac{1}{r} </tex> . А значит, создавая группы по данному алгоритму мы сможем построить <tex>r</tex> групп, удовлетворяющих условию.<br />
#Поставим для всех слов из одной группы одинаковый символ <tex> \Rightarrow</tex> ''у каждой группы свой начальный символ''. Запуститим данную процедуру для каждой группы слов, предварительно обрезав первую букву.<br />
#По индукции по величине <tex> l_n </tex> докажем, что наш алгоритм корректен. <br />
#:'''База:''' Если <tex> l_n = 0 </tex>, то процедура корректна. <br />
#:'''Переход: ''' Допустим, что процедура корректна для <tex> l_n = w </tex> . Докажем, что процедура корректна и для <tex> l_n = w + 1 </tex> . <br />
#:Заметим, что у слов каждой группы будет своя начальная буква, поэтому достаточно проверить префиксность кода для каждой группы. А это истинно по предположению индукции, где для каждой группы <tex> l_i \leqslant w </tex> . <br />
<br />
}}<br />
<br />
== Замечания ==<br />
<br />
Когда имеет место строгое неравенство? Легко заметить, что если любая концевая вершина дерева является кодовым словом, то <tex>K = 1</tex>. Строгое неравенство имеет место лишь в случае, когда некоторые из концевых вершин не используются. Однако, в случае двоичного кодового алфавита какая-нибудь концевая вершина не используется, то предыдущее решение оказывается лишним, и соответствующая цифра может быть удалена из каждого кодового слова, декодирование которого проходит через эту вершину. Таким образом, если имеет место строгое неравенство, то код неэффективен, но для двоичных деревьев очевидно, как можно его улучшить.<br />
<br />
Заметим еще раз, что теорема утверждает существование такого кода и ничего не говорит о конкретных кодах. Может существовать код, который удовлетворяет неравенству Крафта и тем не менее не является префиксным.<br />
<br />
<br />
== См.также ==<br />
*[[Неравенство Макмиллана]]<br />
<br />
== Источники информации ==<br />
*[http://ru.wikipedia.org/wiki/Неравенство_Крафта Википедия — Неравенство Крафта]<br />
*[http://books.sernam.ru/book_htc.php?id=35 Неравенство Крафта]<br />
*[https://xlinux.nist.gov/dads/HTML/kraftsinqlty.html Kraft's inequality]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Алгоритмы сжатия]]</div>Damm1thttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B5%D1%80%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%9A%D1%80%D0%B0%D1%84%D1%82%D0%B0&diff=63306Неравенство Крафта2018-01-03T14:01:47Z<p>Damm1t: </p>
<hr />
<div><br />
Рассматриваемое ниже неравенство Крафта показывает для каких длин кодовых слов существует префиксный код.<br />
<br />
{{Теорема<br />
|about=неравенство Крафта <br />
|statement=<br />
Пусть <tex>\Sigma</tex> — [[Основные определения, связанные со строками|алфавит]] из <tex>n</tex> [[Основные определения, связанные со строками|символов]], кодовые слова которого имеют длины <tex>l_1 \leqslant l_2 \leqslant \ldots \leqslant l_n </tex>. <br />
<br />
Тогда необходимое и достаточное условие существования префиксного кода в <tex>r</tex>-ичном алфавите для символов из <tex>\Sigma</tex>, состоит в выполнении неравенства:<br />
<br />
<center><tex> \sum\limits_{i = 1}^{n} r ^{-l_i} \leqslant 1 </tex></center><br />
<br />
|proof= <br />
<br />
[[file:Treeforkraft.jpg|thumb|250px|Иллюстрация к доказательству индукционного перехода]]<br />
<br />
'''Необходимость:'''<br />
<br />
Напомним, что префиксный код можно представить в виде <tex>r</tex>-ичного корневого дерева, рёбра которого соответствуют символам алфавита, а листья соответствующим кодам. Неравенство Крафта будем доказывать по [[Математическая индукция|индукции]]. <br />
<br />
Для простоты рассмотрим сначала случай двоичного алфавита, то есть <tex>r = 2</tex>. <br />
<br />
'''База:''' Если максимальная длина пути на дереве равна <tex>1</tex>, то в дереве есть одно или два ребра длины <tex>1</tex>. Таким образом, либо <tex> \dfrac{1}{2} \leqslant 1 </tex> — для одного символа источника, либо <tex> \dfrac{1}{2} + \dfrac{1}{2} \leqslant 1 </tex> — для двух символов источника. <br />
<br />
'''Переход:''' Предположим далее, что неравенство Крафта справедливо для всех деревьев высоты меньше <tex>n - 1</tex>. <br />
Докажем, что оно справедливо и для всех деревьев высоты меньше <tex>n</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>.<br />
<br />
<br />
В случае произвольного недвоичного основания <tex>r</tex> имеется не более <tex>r</tex> ребер, исходящих из каждой вершины, то есть не более <tex>r</tex> поддеревьев; каждое из них присоединяется к основному дереву, давая дополнительный множитель <tex>\dfrac{1}{r}</tex>. Отсюда снова следует утверждение теоремы.<br />
<br />
'''Достаточность:'''<br />
<br />
#Если некоторое <tex> l_i = 0 </tex> , то <tex> n = 1 </tex> . В таком случае пустая строка является искомым префиксным кодом. Далее все <tex> l_i \geqslant 1 </tex> . <br />
#Для доказательства корректности разделим длины <tex> l_i </tex> на <tex>r</tex>, возможно пустых, групп, внутри каждой из которых <tex> \sum\limits r ^{-l_i} \leqslant \dfrac{1}{r} </tex> .<br />
#:Пусть у нас есть <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> в порядке увеличения индекса.<br />
#:Докажем, что в таком случае группа будет либо полностью укомплектована, либо будут исчерпаны все возможные <tex> l_i </tex> . Это следует из того, что при <tex> l_i \geqslant 1 </tex> на <tex>i</tex>-ом шаге либо группа уже укомплектована, либо ее остаток равен: <br />
#: <center><tex> \dfrac{1}{r} - \left ( r^{-l_1} + r^{-l_2} + \ldots + r^{-l_{i-1}} \right ) = \dfrac{r^{l_i-1} - ( r^{l_i - l_1} + r^{l_i - l_2} + \ldots + r^{l_i - l_{i - 1}} )}{r^{l_i}}</tex></center><br />
#:Так как группа не укомплектована, то числитель положителен. Если добавим <tex> l_i </tex> в группу, то числитель уменьшится на <tex>1</tex>, где <tex>l_i \in \mathbb{N}, r \in \mathbb{N} </tex>. Следовательно числитель натуральное число. Тогда, взяв <tex> l_i </tex> в группу, мы не перепрыгнем через максимальное значение, то есть сумма: <tex> \sum\limits_{j = 1}^{i} r ^{-l_j} \leqslant \dfrac{1}{r} </tex> . А значит, создавая группы по данному алгоритму мы сможем построить <tex>r</tex> групп, удовлетворяющих условию.<br />
#Поставим для всех слов из одной группы одинаковый символ <tex> \Rightarrow</tex> ''у каждой группы свой начальный символ''. Запуститим данную процедуру для каждой группы слов, предварительно обрезав первую букву.<br />
#По индукции по величине <tex> l_n </tex> докажем, что наш алгоритм корректен. <br />
#:'''База:''' Если <tex> l_n = 0 </tex>, то процедура корректна. <br />
#:'''Переход: ''' Допустим, что процедура корректна для <tex> l_n = w </tex> . Докажем, что процедура корректна и для <tex> l_n = w + 1 </tex> . <br />
#:Заметим, что у слов каждой группы будет своя начальная буква, поэтому достаточно проверить префиксность кода для каждой группы. А это истинно по предположению индукции, где для каждой группы <tex> l_i \leqslant w </tex> . <br />
<br />
}}<br />
<br />
== Замечания ==<br />
<br />
Когда имеет место строгое неравенство? Легко заметить, что если любая концевая вершина дерева является кодовым словом, то <tex>K = 1</tex>. Строгое неравенство имеет место лишь в случае, когда некоторые из концевых вершин не используются. Однако, в случае двоичного кодового алфавита какая-нибудь концевая вершина не используется, то предыдущее решение оказывается лишним, и соответствующая цифра может быть удалена из каждого кодового слова, декодирование которого проходит через эту вершину. Таким образом, если имеет место строгое неравенство, то код неэффективен, но для двоичных деревьев очевидно, как можно его улучшить.<br />
<br />
Заметим еще раз, что теорема утверждает существование такого кода и ничего не говорит о конкретных кодах. Может существовать код, который удовлетворяет неравенству Крафта и тем не менее не является префиксным.<br />
<br />
<br />
== См.также ==<br />
*[[Неравенство Макмиллана]]<br />
<br />
== Источники информации ==<br />
*[http://ru.wikipedia.org/wiki/Неравенство_Крафта Википедия — Неравенство Крафта]<br />
*[http://books.sernam.ru/book_htc.php?id=35 Неравенство Крафта]<br />
*[https://xlinux.nist.gov/dads/HTML/kraftsinqlty.html Kraft's inequality]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Алгоритмы сжатия]]</div>Damm1thttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B5%D1%80%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%9A%D1%80%D0%B0%D1%84%D1%82%D0%B0&diff=63305Неравенство Крафта2018-01-03T13:54:15Z<p>Damm1t: </p>
<hr />
<div><br />
Рассматриваемое ниже неравенство Крафта показывает для каких длин кодовых слов существует префиксный код.<br />
<br />
{{Теорема<br />
|about=неравенство Крафта <br />
|statement=<br />
Пусть <tex>\Sigma</tex> — [[Основные определения, связанные со строками|алфавит]] из <tex>n</tex> [[Основные определения, связанные со строками|символов]], кодовые слова которого имеют длины <tex>l_1 \leqslant l_2 \leqslant \ldots \leqslant l_n </tex>. <br />
<br />
Тогда необходимое и достаточное условие существования префиксного кода в <tex>r</tex>-ичном алфавите для символов из <tex>\Sigma</tex>, состоит в выполнении неравенства:<br />
<br />
<center><tex> \sum\limits_{i = 1}^{n} r ^{-l_i} \leqslant 1 </tex></center><br />
<br />
|proof= <br />
<br />
[[file:Treeforkraft.jpg|thumb|250px|Иллюстрация к доказательству индукционного перехода]]<br />
<br />
'''Необходимость:'''<br />
<br />
Напомним, что префиксный код можно представить в виде <tex>r</tex>-ичного корневого дерева, рёбра которого соответствуют символам алфавита, а листья соответствующим кодам. Неравенство Крафта будем доказывать по [[Математическая индукция|индукции]]. <br />
<br />
Для простоты рассмотрим сначала случай двоичного алфавита, то есть <tex>r = 2</tex>. <br />
<br />
'''База:''' Если максимальная длина пути на дереве равна <tex>1</tex>, то в дереве есть одно или два ребра длины <tex>1</tex>. Таким образом, либо <tex> \dfrac{1}{2} \leqslant 1 </tex> — для одного символа источника, либо <tex> \dfrac{1}{2} + \dfrac{1}{2} \leqslant 1 </tex> — для двух символов источника. <br />
<br />
'''Переход:''' Предположим далее, что неравенство Крафта справедливо для всех деревьев высоты меньше <tex>n - 1</tex>. <br />
Докажем, что оно справедливо и для всех деревьев высоты меньше <tex>n</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>.<br />
<br />
<br />
В случае произвольного недвоичного основания <tex>r</tex> имеется не более <tex>r</tex> ребер, исходящих из каждой вершины, то есть не более <tex>r</tex> поддеревьев; каждое из них присоединяется к основному дереву, давая дополнительный множитель <tex>\dfrac{1}{r}</tex>. Отсюда снова следует утверждение теоремы.<br />
<br />
'''Достаточность:'''<br />
<br />
#Если некоторое <tex> l_i = 0 </tex> , то <tex> n = 1 </tex> . В таком случае пустая строка является искомым префиксным кодом. Далее все <tex> l_i \geqslant 1 </tex> . <br />
#Для доказательства корректности разделим длины <tex> l_i </tex> на <tex>r</tex> групп, внутри каждой из которых <tex> \sum\limits r ^{-l_i} \leqslant \dfrac{1}{r} </tex> .<br />
#:Пусть у нас есть <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> в порядке увеличения индекса.<br />
#:Докажем, что в таком случае группа будет либо полностью укомплектована, либо будут исчерпаны все возможные <tex> l_i </tex> . Это следует из того, что при <tex> l_i \geqslant 1 </tex> на <tex>i</tex>-ом шаге либо группа уже укомплектована, либо ее остаток равен: <br />
#: <center><tex> \dfrac{1}{r} - \left ( r^{-l_1} + r^{-l_2} + \ldots + r^{-l_{i-1}} \right ) = \dfrac{r^{l_i-1} - ( r^{l_i - l_1} + r^{l_i - l_2} + \ldots + r^{l_i - l_{i - 1}} )}{r^{l_i}}</tex></center><br />
#:Так как группа не укомплектована, то числитель положителен. Если добавим <tex> l_i </tex> в группу, то числитель уменьшится на <tex>1</tex>, где <tex>l_i \in \mathbb{N}, r \in \mathbb{N} </tex>. Следовательно числитель натуральное число. Тогда, взяв <tex> l_i </tex> в группу, мы не перепрыгнем через максимальное значение, то есть сумма: <tex> \sum\limits_{j = 1}^{i} r ^{-l_j} \leqslant \dfrac{1}{r} </tex> . А значит, создавая группы по данному алгоритму мы сможем построить <tex>r</tex> групп, удовлетворяющих условию.<br />
#Пусть у всех слов из одной группы будет одна и та же начальная буква <tex> \Rightarrow</tex> ''у каждой группы своя начальная буква''. Запуститим данную процедуру для каждой группы слов, предварительно обрезав первую букву.<br />
#По индукции по величине <tex> l_n </tex> докажем, что наш алгоритм корректен. <br />
#:'''База:''' Если <tex> l_n = 0 </tex>, то процедура корректна. <br />
#:'''Переход: ''' Допустим, что процедура корректна для <tex> l_n = w </tex> . Докажем, что процедура корректна и для <tex> l_n = w + 1 </tex> . <br />
#:Заметим, что у слов каждой группы будет своя начальная буква, поэтому достаточно проверить префиксность кода для каждой группы. А это истинно по предположению индукции, где для каждой группы <tex> l_i \leqslant w </tex> . <br />
<br />
}}<br />
<br />
== Замечания ==<br />
<br />
Когда имеет место строгое неравенство? Легко заметить, что если любая концевая вершина дерева является кодовым словом, то <tex>K = 1</tex>. Строгое неравенство имеет место лишь в случае, когда некоторые из концевых вершин не используются. Однако, в случае двоичного кодового алфавита какая-нибудь концевая вершина не используется, то предыдущее решение оказывается лишним, и соответствующая цифра может быть удалена из каждого кодового слова, декодирование которого проходит через эту вершину. Таким образом, если имеет место строгое неравенство, то код неэффективен, но для двоичных деревьев очевидно, как можно его улучшить.<br />
<br />
Заметим еще раз, что теорема утверждает существование такого кода и ничего не говорит о конкретных кодах. Может существовать код, который удовлетворяет неравенству Крафта и тем не менее не является префиксным.<br />
<br />
<br />
== См.также ==<br />
*[[Неравенство Макмиллана]]<br />
<br />
== Источники информации ==<br />
*[http://ru.wikipedia.org/wiki/Неравенство_Крафта Википедия — Неравенство Крафта]<br />
*[http://books.sernam.ru/book_htc.php?id=35 Неравенство Крафта]<br />
*[https://xlinux.nist.gov/dads/HTML/kraftsinqlty.html Kraft's inequality]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Алгоритмы сжатия]]</div>Damm1thttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B5%D1%80%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%9A%D1%80%D0%B0%D1%84%D1%82%D0%B0&diff=63303Неравенство Крафта2018-01-02T23:22:16Z<p>Damm1t: </p>
<hr />
<div><br />
Рассматриваемое ниже неравенство Крафта показывает для каких длин кодовых слов существует префиксный код.<br />
<br />
{{Теорема<br />
|about=неравенство Крафта <br />
|statement=<br />
Пусть <tex>\Sigma</tex> — [[Основные определения, связанные со строками|алфавит]] из <tex>n</tex> [[Основные определения, связанные со строками|символов]], кодовые слова которого имеют длины <tex>l_1 \leqslant l_2 \leqslant \ldots \leqslant l_n </tex>. <br />
<br />
Тогда необходимое и достаточное условие существования префиксного кода в <tex>r</tex>-ичном алфавите для символов из <tex>\Sigma</tex>, состоит в выполнении неравенства:<br />
<br />
<center><tex> \sum\limits_{i = 1}^{n} r ^{-l_i} \leqslant 1 </tex></center><br />
<br />
|proof= <br />
<br />
[[file:Treeforkraft.jpg|thumb|250px|Иллюстрация к доказательству индукционного перехода]]<br />
<br />
'''Необходимость:'''<br />
<br />
Напомним, что префиксный код можно представить в виде <tex>r</tex>-ичного корневого дерева, рёбра которого соответствуют символам алфавита, а листья соответствующим кодам. Неравенство Крафта будем доказывать по [[Математическая индукция|индукции]]. <br />
<br />
Для простоты рассмотрим сначала случай двоичного алфавита, то есть <tex>r = 2</tex>. <br />
<br />
'''База:''' Если максимальная длина пути на дереве равна <tex>1</tex>, то в дереве есть одно или два ребра длины <tex>1</tex>. Таким образом, либо <tex> \dfrac{1}{2} \leqslant 1 </tex> — для одного символа источника, либо <tex> \dfrac{1}{2} + \dfrac{1}{2} \leqslant 1 </tex> — для двух символов источника. <br />
<br />
'''Переход:''' Предположим далее, что неравенство Крафта справедливо для всех деревьев высоты меньше <tex>n - 1</tex>. <br />
Докажем, что оно справедливо и для всех деревьев высоты меньше <tex>n</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>.<br />
<br />
<br />
В случае произвольного недвоичного основания <tex>r</tex> имеется не более <tex>r</tex> ребер, исходящих из каждой вершины, то есть не более <tex>r</tex> поддеревьев; каждое из них присоединяется к основному дереву, давая дополнительный множитель <tex>\dfrac{1}{r}</tex>. Отсюда снова следует утверждение теоремы.<br />
<br />
'''Достаточность:'''<br />
<br />
#Если некоторое <tex> l_i = 0 </tex> , то <tex> n = 1 </tex> . В таком случае пустая строка является искомым префиксным кодом. Далее все <tex> l_i \geqslant 1 </tex> . <br />
#Для доказательства корректности разделим длины <tex> l_i </tex> на <tex>r</tex> групп, внутри каждой из которых <tex> \sum\limits r ^{-l_i} \leqslant \dfrac{1}{r} </tex> .<br />
#:Пусть у нас есть <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> в порядке увеличения индекса.<br />
#:Докажем, что в таком случае группа будет либо полностью укомплектована, либо будут исчерпаны все возможные <tex> l_i </tex> . Это следует из того, что при <tex> l_i \geqslant 1 </tex> на <tex>i</tex>-ом шаге либо группа уже укомплектована, либо ее остаток равен: <br />
#: <center><tex> \dfrac{1}{r} - \left ( \dfrac{1}{r^{l_1}} + \dfrac{1}{r^{l_2}} + \ldots + \dfrac{1}{r^{l_{i-1}}} \right ) = \dfrac{r^{l_i-1} - ( r^{l_i - l_1} + r^{l_i - l_2} + \ldots + r^{l_i - l_{i - 1}} )}{r^{l_i}}</tex></center><br />
#:Так как группа не укомплектована, то числитель положителен. Если добавим <tex> l_i </tex> в группу, то числитель уменьшится на <tex>1</tex>. Тогда, взяв <tex> l_i </tex> в группу, мы не перепрыгнем через максимальное значение. А значит, создавая группы по данному алгоритму мы сможем построить <tex>r</tex> групп, удовлетворяющих условию.<br />
#У всех слов из одной группы будет одна и та же начальная буква. Запуститим данную процедуру для каждой группы слов, предварительно обрезав первую букву.<br />
#По индукции по величине <tex> l_n </tex> докажем, что наш алгоритм корректен. <br />
#:'''База:''' Если <tex> l_n = 0 </tex>, то процедура корректна. <br />
#:'''Переход: ''' Допустим, что процедура корректна для <tex> l_n = w </tex> . Докажем, что процедура корректна и для <tex> l_n = w + 1 </tex> . <br />
#:Заметим, что у слов каждой группы будет своя начальная буква, поэтому достаточно проверить префиксность кода для каждой группы. А это истинно по предположению индукции, где для каждой группы <tex> l_i \leqslant w </tex> . <br />
<br />
}}<br />
<br />
== Замечания ==<br />
<br />
Когда имеет место строгое неравенство? Легко заметить, что если любая концевая вершина дерева является кодовым словом, то <tex>K = 1</tex>. Строгое неравенство имеет место лишь в случае, когда некоторые из концевых вершин не используются. Однако, в случае двоичного кодового алфавита какая-нибудь концевая вершина не используется, то предыдущее решение оказывается лишним, и соответствующая цифра может быть удалена из каждого кодового слова, декодирование которого проходит через эту вершину. Таким образом, если имеет место строгое неравенство, то код неэффективен, но для двоичных деревьев очевидно, как можно его улучшить.<br />
<br />
Заметим еще раз, что теорема утверждает существование такого кода и ничего не говорит о конкретных кодах. Может существовать код, который удовлетворяет неравенству Крафта и тем не менее не является префиксным.<br />
<br />
<br />
== См.также ==<br />
*[[Неравенство Макмиллана]]<br />
<br />
== Источники информации ==<br />
*[http://ru.wikipedia.org/wiki/Неравенство_Крафта Википедия — Неравенство Крафта]<br />
*[http://books.sernam.ru/book_htc.php?id=35 Неравенство Крафта]<br />
*[https://xlinux.nist.gov/dads/HTML/kraftsinqlty.html Kraft's inequality]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Алгоритмы сжатия]]</div>Damm1thttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B5%D1%80%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%9A%D1%80%D0%B0%D1%84%D1%82%D0%B0&diff=63302Неравенство Крафта2018-01-02T23:15:05Z<p>Damm1t: </p>
<hr />
<div><br />
Рассматриваемое ниже неравенство Крафта показывает для каких длин кодовых слов существует префиксный код.<br />
<br />
{{Теорема<br />
|about=неравенство Крафта <br />
|statement=<br />
Пусть <tex>\Sigma</tex> — [[Основные определения, связанные со строками|алфавит]] из <tex>n</tex> [[Основные определения, связанные со строками|символов]], кодовые слова которого имеют длины <tex>l_1 \leqslant l_2 \leqslant \ldots \leqslant l_n </tex>. <br />
<br />
Тогда необходимое и достаточное условие существования префиксного кода в <tex>r</tex>-ичном алфавите для символов из <tex>\Sigma</tex>, состоит в выполнении неравенства:<br />
<br />
<center><tex> \sum\limits_{i = 1}^{n} r ^{-l_i} \leqslant 1 </tex></center><br />
<br />
|proof= <br />
<br />
[[file:Treeforkraft.jpg|thumb|250px|Иллюстрация к доказательству индукционного перехода]]<br />
<br />
'''Необходимость:'''<br />
<br />
Напомним, что префиксный код можно представить в виде <tex>r</tex>-ичного корневого дерева, рёбра которого соответствуют символам алфавита, а листья соответствующим кодам. Неравенство Крафта будем доказывать по [[Математическая индукция|индукции]]. <br />
<br />
Для простоты рассмотрим сначала случай двоичного алфавита, то есть <tex>r = 2</tex>. <br />
<br />
'''База:''' Если максимальная длина пути на дереве равна <tex>1</tex>, то в дереве есть одно или два ребра длины <tex>1</tex>. Таким образом, либо <tex> \dfrac{1}{2} \leqslant 1 </tex> — для одного символа источника, либо <tex> \dfrac{1}{2} + \dfrac{1}{2} \leqslant 1 </tex> — для двух символов источника. <br />
<br />
'''Переход:''' Предположим далее, что неравенство Крафта справедливо для всех деревьев высоты меньше <tex>n - 1</tex>. <br />
Докажем, что оно справедливо и для всех деревьев высоты меньше <tex>n</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>.<br />
<br />
<br />
В случае произвольного недвоичного основания <tex>r</tex> имеется не более <tex>r</tex> ребер, исходящих из каждой вершины, то есть не более <tex>r</tex> поддеревьев; каждое из них присоединяется к основному дереву, давая дополнительный множитель <tex>\dfrac{1}{r}</tex>. Отсюда снова следует утверждение теоремы.<br />
<br />
'''Достаточность:'''<br />
<br />
#Если некоторое <tex> l_i = 0 </tex> , то <tex> n = 1 </tex> . В таком случае пустая строка является искомым префиксным кодом. Далее все <tex> l_i \geqslant 1 </tex> . <br />
#Для доказательства корректности разделим длины <tex> l_i </tex> на <tex>r</tex> групп, внутри каждой из которых <tex> \sum\limits r ^{-l_i} \leqslant \dfrac{1}{r} </tex> .<br />
#:Пусть у нас есть <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> в порядке увеличения индекса.<br />
#:Докажем, что в таком случае группа будет либо полностью укомплектована, либо будут исчерпаны все возможные <tex> l_i </tex> . Это следует из того, что при <tex> l_i \geqslant 1 </tex> на <tex>i</tex>-ом шаге либо группа уже укомплектована, либо ее остаток равен: <br />
#: <center><tex> \dfrac{1}{r} - \left ( \dfrac{1}{r^{l_1}} + \ldots + \dfrac{1}{r^{l_{i-1}}} \right ) = \dfrac{r^{l_i-1} - ( r^{l_i - l_1} + r^{l_i - l_2} + \ldots + r^{l_i - l_{i - 1}} )}{r^{l_i}}</tex></center><br />
#:Так как группа не укомплектована, то числитель положителен. Если добавим <tex> l_i </tex> в группу, то числитель уменьшится на <tex>1</tex>. Тогда, взяв <tex> l_i </tex> в группу, мы не перепрыгнем через максимальное значение. А значит, создавая группы по данному алгоритму мы сможем построить <tex>r</tex> групп, удовлетворяющих условию.<br />
#У всех слов из одной группы будет одна и та же начальная буква. Запуститим данную процедуру для каждой группы слов, предварительно обрезав первую букву.<br />
#По индукции по величине <tex> l_n </tex> докажем, что наш алгоритм корректен. <br />
#:'''База:''' Если <tex> l_n = 0 </tex>, то процедура корректна. <br />
#:'''Переход: ''' Допустим, что процедура корректна для <tex> l_n = w </tex> . Докажем, что процедура корректна и для <tex> l_n = w + 1 </tex> . <br />
#:Заметим, что у слов каждой группы будет своя начальная буква, поэтому достаточно проверить префиксность кода для каждой группы. А это истинно по предположению индукции, где для каждой группы <tex> l_i \leqslant w </tex> . <br />
<br />
}}<br />
<br />
== Замечания ==<br />
<br />
Когда имеет место строгое неравенство? Легко заметить, что если любая концевая вершина дерева является кодовым словом, то <tex>K = 1</tex>. Строгое неравенство имеет место лишь в случае, когда некоторые из концевых вершин не используются. Однако, в случае двоичного кодового алфавита какая-нибудь концевая вершина не используется, то предыдущее решение оказывается лишним, и соответствующая цифра может быть удалена из каждого кодового слова, декодирование которого проходит через эту вершину. Таким образом, если имеет место строгое неравенство, то код неэффективен, но для двоичных деревьев очевидно, как можно его улучшить.<br />
<br />
Заметим еще раз, что теорема утверждает существование такого кода и ничего не говорит о конкретных кодах. Может существовать код, который удовлетворяет неравенству Крафта и тем не менее не является префиксным.<br />
<br />
<br />
== См.также ==<br />
*[[Неравенство Макмиллана]]<br />
<br />
== Источники информации ==<br />
*[http://ru.wikipedia.org/wiki/Неравенство_Крафта Википедия — Неравенство Крафта]<br />
*[http://books.sernam.ru/book_htc.php?id=35 Неравенство Крафта]<br />
*[https://xlinux.nist.gov/dads/HTML/kraftsinqlty.html Kraft's inequality]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Алгоритмы сжатия]]</div>Damm1thttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B5%D1%80%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%9A%D1%80%D0%B0%D1%84%D1%82%D0%B0&diff=63300Неравенство Крафта2018-01-02T21:50:41Z<p>Damm1t: </p>
<hr />
<div><br />
Рассматриваемое ниже неравенство Крафта показывает для каких длин кодовых слов существует префиксный код.<br />
<br />
{{Теорема<br />
|about=неравенство Крафта <br />
|statement=<br />
Пусть <tex>\Sigma</tex> — [[Основные определения, связанные со строками|алфавит]] из <tex>n</tex> [[Основные определения, связанные со строками|символов]], кодовые слова которого имеют длины <tex>l_1 \leqslant l_2 \leqslant \ldots \leqslant l_n </tex>. <br />
<br />
Тогда необходимое и достаточное условие существования префиксного кода в <tex>r</tex>-ичном алфавите для символов из <tex>\Sigma</tex>, состоит в выполнении неравенства:<br />
<br />
<center><tex> \sum\limits_{i = 1}^{n} r ^{-l_i} \leqslant 1 </tex></center><br />
<br />
|proof= <br />
<br />
[[file:Treeforkraft.jpg|thumb|250px|Иллюстрация к доказательству индукционного перехода]]<br />
<br />
'''Необходимость:'''<br />
<br />
Напомним, что префиксный код можно представить в виде <tex>r</tex>-ичного корневого дерева, рёбра которого соответствуют символам алфавита, а листья соответствующим кодам. Неравенство Крафта будем доказывать по [[Математическая индукция|индукции]]. <br />
<br />
Для простоты рассмотрим сначала случай двоичного алфавита, то есть <tex>r = 2</tex>. <br />
<br />
'''База:''' Если максимальная длина пути на дереве равна <tex>1</tex>, то в дереве есть одно или два ребра длины <tex>1</tex>. Таким образом, либо <tex> \dfrac{1}{2} \leqslant 1 </tex> — для одного символа источника, либо <tex> \dfrac{1}{2} + \dfrac{1}{2} \leqslant 1 </tex> — для двух символов источника. <br />
<br />
'''Переход:''' Предположим далее, что неравенство Крафта справедливо для всех деревьев высоты меньше <tex>n - 1</tex>. <br />
Докажем, что оно справедливо и для всех деревьев высоты меньше <tex>n</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>.<br />
<br />
<br />
В случае произвольного недвоичного основания <tex>r</tex> имеется не более <tex>r</tex> ребер, исходящих из каждой вершины, то есть не более <tex>r</tex> поддеревьев; каждое из них присоединяется к основному дереву, давая дополнительный множитель <tex>\dfrac{1}{r}</tex>. Отсюда снова следует утверждение теоремы.<br />
<br />
'''Достаточность:'''<br />
<br />
#Если некоторое <tex> l_i = 0 </tex> , то <tex> n = 1 </tex> . В таком случае пустая строка является искомым префиксным кодом. Далее все <tex> l_i \geqslant 1 </tex> . <br />
#Для доказательства корректности разделим длины <tex> l_i </tex> на <tex>r</tex> групп, внутри каждой из которых <tex> \sum\limits r ^{-l_i} \leqslant \dfrac{1}{r} </tex> .<br />
#:Пусть у нас есть <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> в порядке увеличения индекса.<br />
#:Докажем, что в таком случае группа будет либо полностью укомплектована, либо будут исчерпаны все возможные <tex> l_i </tex> . Это следует из того, что при <tex> l_i \geqslant 1 </tex> на <tex>i</tex>-ом шаге либо группа уже укомплектована, либо ее остаток равен: <br />
#: <center><tex> \dfrac{1}{r} - \left ( \dfrac{1}{r^{l_1}} + \ldots + \dfrac{1}{r^{l_i-1}} \right ) = \dfrac{r^{l_i-1} - ( r^{l_i - l_1} + r^{l_i - l_2} + \ldots + r^{l_i - l_{i - 1}} )}{r^{l_i}}</tex></center><br />
#:Так как группа не укомплектована, то числитель положителен. Если добавим <tex> l_i </tex> в группу, то числитель уменьшится на <tex>1</tex>. Тогда, взяв <tex> l_i </tex> в группу, мы не перепрыгнем через максимальное значение. А значит, создавая группы по данному алгоритму мы сможем построить <tex>r</tex> групп, удовлетворяющих условию.<br />
#У всех слов из одной группы будет одна и та же начальная буква. Запуститим данную процедуру для каждой группы слов, предварительно обрезав первую букву.<br />
#По индукции по величине <tex> l_n </tex> докажем, что наш алгоритм корректен. <br />
#:'''База:''' Если <tex> l_n = 0 </tex>, то процедура корректна. <br />
#:'''Переход: ''' Допустим, что процедура корректна для <tex> l_n = w </tex> . Докажем, что процедура корректна и для <tex> l_n = w + 1 </tex> . <br />
#:Заметим, что у слов каждой группы будет своя начальная буква, поэтому достаточно проверить префиксность кода для каждой группы. А это истинно по предположению индукции, где для каждой группы <tex> l_i \leqslant w </tex> . <br />
<br />
}}<br />
<br />
== Замечания ==<br />
<br />
Когда имеет место строгое неравенство? Легко заметить, что если любая концевая вершина дерева является кодовым словом, то <tex>K = 1</tex>. Строгое неравенство имеет место лишь в случае, когда некоторые из концевых вершин не используются. Однако, в случае двоичного кодового алфавита какая-нибудь концевая вершина не используется, то предыдущее решение оказывается лишним, и соответствующая цифра может быть удалена из каждого кодового слова, декодирование которого проходит через эту вершину. Таким образом, если имеет место строгое неравенство, то код неэффективен, но для двоичных деревьев очевидно, как можно его улучшить.<br />
<br />
Заметим еще раз, что теорема утверждает существование такого кода и ничего не говорит о конкретных кодах. Может существовать код, который удовлетворяет неравенству Крафта и тем не менее не является префиксным.<br />
<br />
<br />
== См.также ==<br />
*[[Неравенство Макмиллана]]<br />
<br />
== Источники информации ==<br />
*[http://ru.wikipedia.org/wiki/Неравенство_Крафта Википедия — Неравенство Крафта]<br />
*[http://books.sernam.ru/book_htc.php?id=35 Неравенство Крафта]<br />
*[https://xlinux.nist.gov/dads/HTML/kraftsinqlty.html Kraft's inequality]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Алгоритмы сжатия]]</div>Damm1thttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B5%D1%80%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%9A%D1%80%D0%B0%D1%84%D1%82%D0%B0&diff=63298Неравенство Крафта2018-01-02T21:21:57Z<p>Damm1t: </p>
<hr />
<div><br />
Рассматриваемое ниже неравенство Крафта показывает для каких длин кодовых слов существует префиксный код.<br />
<br />
{{Теорема<br />
|about=неравенство Крафта <br />
|statement=<br />
Пусть <tex>\Sigma</tex> — [[Основные определения, связанные со строками|алфавит]] из <tex>n</tex> [[Основные определения, связанные со строками|символов]], кодовые слова которого имеют длины <tex>l_1 \leqslant l_2 \leqslant \ldots \leqslant l_n </tex>. <br />
<br />
Тогда необходимое и достаточное условие существования префиксного кода в <tex>r</tex>-ичном алфавите для символов из <tex>\Sigma</tex>, состоит в выполнении неравенства:<br />
<br />
<center><tex> \sum\limits_{i = 1}^{n} r ^{-l_i} \leqslant 1 </tex></center><br />
<br />
|proof= <br />
<br />
[[file:Treeforkraft.jpg|thumb|250px|Иллюстрация к доказательству индукционного перехода]]<br />
<br />
'''Необходимость:'''<br />
<br />
Напомним, что префиксный код можно представить в виде <tex>r</tex>-ичного корневого дерева, рёбра которого соответствуют символам алфавита, а листья соответствующим кодам. Неравенство Крафта будем доказывать по [[Математическая индукция|индукции]]. <br />
<br />
Для простоты рассмотрим сначала случай двоичного алфавита, то есть <tex>r = 2</tex>. <br />
<br />
'''База:''' Если максимальная длина пути на дереве равна <tex>1</tex>, то в дереве есть одно или два ребра длины <tex>1</tex>. Таким образом, либо <tex> \dfrac{1}{2} \leqslant 1 </tex> — для одного символа источника, либо <tex> \dfrac{1}{2} + \dfrac{1}{2} \leqslant 1 </tex> — для двух символов источника. <br />
<br />
'''Переход:''' Предположим далее, что неравенство Крафта справедливо для всех деревьев высоты меньше <tex>n - 1</tex>. <br />
Докажем, что оно справедливо и для всех деревьев высоты меньше <tex>n</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>.<br />
<br />
<br />
В случае произвольного недвоичного основания <tex>r</tex> имеется не более <tex>r</tex> ребер, исходящих из каждой вершины, то есть не более <tex>r</tex> поддеревьев; каждое из них присоединяется к основному дереву, давая дополнительный множитель <tex>\dfrac{1}{r}</tex>. Отсюда снова следует утверждение теоремы.<br />
<br />
'''Достаточность:'''<br />
<br />
#: Если некоторое <tex> l_i = 0 </tex> , то <tex> n = 1 </tex> . В таком случае пустая строка является искомым префиксным кодом. Далее все <tex> l_i \geqslant 1 </tex> . <br />
<br />
#: Пусть у нас есть <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> в порядке увеличения индекса. <br />
<br />
*Докажем, что в таком случае группа будет либо полностью укомплектована, либо будут исчерпаны все возможные <tex> l_i </tex> . Это следует из того, что при <tex> l_i \geqslant 1 </tex> на <tex>i</tex>-ом шаге либо группа уже укомплектована, либо ее остаток равен: <br />
<br />
<center><tex> \dfrac{1}{r} - \left ( \dfrac{1}{r^{l_1}} + \ldots + \dfrac{1}{r^{l_i-1}} \right ) = \dfrac{r^{l_i-1} - ( r^{l_i - l_1} + r^{l_i - l_2} + \ldots + r^{l_i - l_{i - 1}} )}{r^{l_i}}</tex></center><br />
<br />
*Так как группа не укомплектована, то числитель положителен. Если добавим <tex> l_i </tex> в группу, то числитель уменьшится на <tex>1</tex>. Тогда, взяв <tex> l_i </tex> в группу, мы не перепрыгнем через максимальное значение. А значит, создавая группы по данному алгоритму мы сможем построить <tex>r</tex> групп, удовлетворяющих условию.<br />
<br />
#: Для доказательства достаточности опишем рекурсивную процедуру, которая строит код для данного набора длин <tex> l_i </tex> , удовлетворяющих неравенству <tex> \sum\limits_{i = 1}^{n} r ^{-l_i} \leqslant 1 </tex> .<br />
<br />
#: Разделим длины <tex> l_i </tex> на <tex>r</tex> групп, внутри каждой из которых <tex> \sum\limits r ^{-l_i} \leqslant \dfrac{1}{r} </tex> . Разделить длины на группы будем алгоритмом описанным выше. У всех слов из одной группы будет одна и та же начальная буква. <br />
<br />
#: Запуститим данную процедуру для каждой группы слов, предварительно обрезав первую букву.<br />
<br />
#: Доказательство корректности проведём по индукции по величине <tex> l_n </tex> . <br />
<br />
'''База:''' Если <tex> l_n = 0 </tex>, то процедура корректна. <br />
<br />
'''Переход: ''' Допустим, что процедура корректна для <tex> l_n = w </tex> . Докажем, что процедура корректна и для <tex> l_n = w + 1 </tex> . <br />
<br />
Заметим, что у слов каждой группы будет своя начальная буква, поэтому достаточно проверить префиксность кода для каждой группы. А это истинно по предположению индукции, где для каждой группы <tex> l_i \leqslant w </tex> . <br />
<br />
}}<br />
<br />
== Замечания ==<br />
<br />
Когда имеет место строгое неравенство? Легко заметить, что если любая концевая вершина дерева является кодовым словом, то <tex>K = 1</tex>. Строгое неравенство имеет место лишь в случае, когда некоторые из концевых вершин не используются. Однако, в случае двоичного кодового алфавита какая-нибудь концевая вершина не используется, то предыдущее решение оказывается лишним, и соответствующая цифра может быть удалена из каждого кодового слова, декодирование которого проходит через эту вершину. Таким образом, если имеет место строгое неравенство, то код неэффективен, но для двоичных деревьев очевидно, как можно его улучшить.<br />
<br />
Заметим еще раз, что теорема утверждает существование такого кода и ничего не говорит о конкретных кодах. Может существовать код, который удовлетворяет неравенству Крафта и тем не менее не является префиксным.<br />
<br />
<br />
== См.также ==<br />
*[[Неравенство Макмиллана]]<br />
<br />
== Источники информации ==<br />
*[http://ru.wikipedia.org/wiki/Неравенство_Крафта Википедия — Неравенство Крафта]<br />
*[http://books.sernam.ru/book_htc.php?id=35 Неравенство Крафта]<br />
*[https://xlinux.nist.gov/dads/HTML/kraftsinqlty.html Kraft's inequality]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Алгоритмы сжатия]]</div>Damm1thttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B5%D1%80%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%9A%D1%80%D0%B0%D1%84%D1%82%D0%B0&diff=63297Неравенство Крафта2018-01-02T17:11:35Z<p>Damm1t: </p>
<hr />
<div><br />
Рассматриваемое ниже неравенство Крафта показывает для каких длин кодовых слов существует префиксный код.<br />
<br />
{{Теорема<br />
|about=неравенство Крафта <br />
|statement=<br />
Пусть <tex>\Sigma</tex> — [[Основные определения, связанные со строками|алфавит]] из <tex>n</tex> [[Основные определения, связанные со строками|символов]], кодовые слова которого имеют длины <tex>l_1 \leqslant l_2 \leqslant \ldots \leqslant l_n </tex>. <br />
<br />
Тогда необходимое и достаточное условие существования префиксного кода в <tex>r</tex>-ичном алфавите для символов из <tex>\Sigma</tex>, состоит в выполнении неравенства:<br />
<br />
<center><tex> \sum\limits_{i = 1}^{n} r ^{-l_i} \leqslant 1 </tex></center><br />
<br />
|proof= <br />
<br />
[[file:Treeforkraft.jpg|thumb|250px|Иллюстрация к доказательству индукционного перехода]]<br />
<br />
'''Необходимость:'''<br />
<br />
Напомним, что префиксный код можно представить в виде <tex>r</tex>-ичного корневого дерева, рёбра которого соответствуют символам алфавита, а листья соответствующим кодам. Неравенство Крафта будем доказывать по [[Математическая индукция|индукции]]. <br />
<br />
Для простоты рассмотрим сначала случай двоичного алфавита, то есть <tex>r = 2</tex>. <br />
<br />
'''База:''' Если максимальная длина пути на дереве равна <tex>1</tex>, то в дереве есть одно или два ребра длины <tex>1</tex>. Таким образом, либо <tex> \dfrac{1}{2} \leqslant 1 </tex> — для одного символа источника, либо <tex> \dfrac{1}{2} + \dfrac{1}{2} \leqslant 1 </tex> — для двух символов источника. <br />
<br />
'''Переход:''' Предположим далее, что неравенство Крафта справедливо для всех деревьев высоты меньше <tex>n - 1</tex>. <br />
Докажем, что оно справедливо и для всех деревьев высоты меньше <tex>n</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>.<br />
<br />
<br />
В случае произвольного недвоичного основания <tex>r</tex> имеется не более <tex>r</tex> ребер, исходящих из каждой вершины, то есть не более <tex>r</tex> поддеревьев; каждое из них присоединяется к основному дереву, давая дополнительный множитель <tex>\dfrac{1}{r}</tex>. Отсюда снова следует утверждение теоремы.<br />
<br />
'''Достаточность:'''<br />
<br />
*Если некоторое <tex> l_i = 0 </tex> , то <tex> n = 1 </tex> . В таком случае пустая строка является искомым префиксным кодом. Далее все <tex> l_i \geqslant 1 </tex> . <br />
<br />
----<br />
<br />
Пусть у нас есть <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> в порядке увеличения индекса. <br />
<br />
Докажем, что в таком случае группа будет либо полностью укомплектована, либо будут исчерпаны все возможные <tex> l_i </tex> . Это следует из того, что при <tex> l_i \geqslant 1 </tex> на <tex>i</tex>-ом шаге либо группа уже укомплектована, либо ее остаток равен: <br />
<br />
<center><tex> \dfrac{1}{r} - \left ( \dfrac{1}{r^{l_1}} + \ldots + \dfrac{1}{r^{l_i-1}} \right ) = \dfrac{r^{l_{i-1}} - ( r^{l_i - l_1} + r^{l_i - l_2} + \ldots + r^{l_i - l_{i - 1}} )}{r^{l_i}}</tex></center><br />
<br />
Так как группа не укомплектована, то числитель положителен. Если добавим <tex> l_i </tex> в группу, то числитель уменьшится на <tex>1</tex>. Тогда, взяв <tex> l_i </tex> в группу, мы не перепрыгнем через максимальное значение. А значит, создавая группы по данному алгоритму мы сможем построить <tex>r</tex> групп, удовлетворяющих условию.<br />
<br />
----<br />
<br />
Для доказательства достаточности опишем рекурсивную процедуру, которая строит код для данного набора длин <tex> l_i </tex> , удовлетворяющих неравенству <tex> \sum\limits_{i = 1}^{n} r ^{-l_i} \leqslant 1 </tex> .<br />
<br />
*Разделим длины <tex> l_i </tex> на <tex>r</tex> групп, внутри каждой из которых <tex> \sum\limits r ^{-l_i} \leqslant \dfrac{1}{r} </tex> . Разделить длины на группы будем алгоритмом описанным выше. У всех слов из одной группы будет одна и та же начальная буква. <br />
<br />
*Запуститим данную процедуру для каждой группы слов, предварительно обрезав первую букву.<br />
<br />
Доказательство корректности проведём по индукции по величине <tex> l_n </tex> . <br />
<br />
'''База:''' Если <tex> l_n = 0 </tex>, то процедура корректна. <br />
<br />
'''Переход: ''' Допустим, что процедура корректна для <tex> l_n = w </tex> . Докажем, что процедура корректна и для <tex> l_n = w + 1 </tex> . <br />
<br />
Заметим, что у слов каждой группы будет своя начальная буква, поэтому достаточно проверить префиксность кода для каждой группы. А это истинно по предположению индукции, где для каждой группы <tex> l_i \leqslant w </tex> . <br />
<br />
}}<br />
<br />
== Замечания ==<br />
<br />
Когда имеет место строгое неравенство? Легко заметить, что если любая концевая вершина дерева является кодовым словом, то <tex>K = 1</tex>. Строгое неравенство имеет место лишь в случае, когда некоторые из концевых вершин не используются. Однако, в случае двоичного кодового алфавита какая-нибудь концевая вершина не используется, то предыдущее решение оказывается лишним, и соответствующая цифра может быть удалена из каждого кодового слова, декодирование которого проходит через эту вершину. Таким образом, если имеет место строгое неравенство, то код неэффективен, но для двоичных деревьев очевидно, как можно его улучшить.<br />
<br />
Заметим еще раз, что теорема утверждает существование такого кода и ничего не говорит о конкретных кодах. Может существовать код, который удовлетворяет неравенству Крафта и тем не менее не является префиксным.<br />
<br />
<br />
== См.также ==<br />
*[[Неравенство Макмиллана]]<br />
<br />
== Источники информации ==<br />
*[http://ru.wikipedia.org/wiki/Неравенство_Крафта Википедия — Неравенство Крафта]<br />
*[http://books.sernam.ru/book_htc.php?id=35 Неравенство Крафта]<br />
*[https://xlinux.nist.gov/dads/HTML/kraftsinqlty.html Kraft's inequality]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Алгоритмы сжатия]]</div>Damm1thttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B5%D1%80%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%9A%D1%80%D0%B0%D1%84%D1%82%D0%B0&diff=63293Неравенство Крафта2018-01-02T13:55:18Z<p>Damm1t: </p>
<hr />
<div><br />
Рассматриваемое ниже неравенство Крафта показывает для каких длин кодовых слов существует префиксный код.<br />
<br />
{{Теорема<br />
|about=неравенство Крафта <br />
|statement=<br />
Пусть <tex>\Sigma</tex> — [[Основные определения, связанные со строками|алфавит]] из <tex>n</tex> [[Основные определения, связанные со строками|символов]], кодовые слова которого имеют длины <tex>l_1 \leqslant l_2 \leqslant \ldots \leqslant l_n </tex>. <br />
<br />
Тогда необходимое и достаточное условие существования префиксного кода в <tex>r</tex>-ичном алфавите для символов из <tex>\Sigma</tex>, состоит в выполнении неравенства:<br />
<br />
<center><tex> \sum\limits_{i = 1}^{n} r ^{-l_i} \leqslant 1 </tex></center><br />
<br />
|proof= <br />
<br />
[[file:Treeforkraft.jpg|thumb|250px|Иллюстрация к доказательству индукционного перехода]]<br />
<br />
'''Необходимость:'''<br />
<br />
Напомним, что префиксный код можно представить в виде <tex>r</tex>-ичного корневого дерева, рёбра которого соответствуют символам алфавита, а листья соответствующим кодам. Неравенство Крафта будем доказывать по [[Математическая индукция|индукции]]. <br />
<br />
Для простоты рассмотрим сначала случай двоичного алфавита, то есть <tex>r = 2</tex>. <br />
<br />
'''База:''' Если максимальная длина пути на дереве равна <tex>1</tex>, то в дереве есть одно или два ребра длины <tex>1</tex>. Таким образом, либо <tex> \dfrac{1}{2} \leqslant 1 </tex> — для одного символа источника, либо <tex> \dfrac{1}{2} + \dfrac{1}{2} \leqslant 1 </tex> — для двух символов источника. <br />
<br />
'''Переход:''' Предположим далее, что неравенство Крафта справедливо для всех деревьев высоты меньше <tex>n - 1</tex>. <br />
Докажем, что оно справедливо и для всех деревьев высоты меньше <tex>n</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>.<br />
<br />
<br />
В случае произвольного недвоичного основания <tex>r</tex> имеется не более <tex>r</tex> ребер, исходящих из каждой вершины, то есть не более <tex>r</tex> поддеревьев; каждое из них присоединяется к основному дереву, давая дополнительный множитель <tex>\dfrac{1}{r}</tex>. Отсюда снова следует утверждение теоремы.<br />
<br />
'''Достаточность:'''<br />
<br />
Для доказательства достаточности опишем рекурсивную процедуру, которая строит код для данного набора длин <tex> l_i </tex> , удовлетворяющих неравенству <tex> \sum\limits_{i = 1}^{n} r ^{-l_i} \leqslant 1 </tex> .<br />
<br />
Если некоторое <tex> l_i = 0 </tex> , то <tex> n = 1 </tex> . В таком случае пустая строка является искомым префиксным кодом. Далее все <tex> l_i \geqslant 1 </tex> . <br />
<br />
Разделим длины <tex> l_i </tex> на <tex>r</tex> групп, внутри каждой из которых <tex> \sum\limits r ^{-l_i} \leqslant \dfrac{1}{r} </tex> . Разделить длины на группы можно следующим жадным образом: брать <tex> l_i </tex> в порядке увеличения индекса. Несложно понять, что в таком случае группа будет либо полностью укомплектована, либо будут исчерпаны все возможные <tex> l_i </tex> . Это следует из того, что при <tex> l_i \geqslant 1 </tex> , то на <tex>i</tex>-ом шаге либо группа уже укомплектована, либо <tex> \dfrac{1}{r} - \left ( \dfrac{1}{r^{l_1}} + \ldots + \dfrac{1}{r^{l_i-1}} \right ) </tex> делится на <tex>\dfrac{1}{r^{l_i}}</tex> , потому что каждый член слева делятся на <tex> \dfrac{1}{r^{l_i}} </tex> . Получаем, что остаток набираемой группы до <tex>\dfrac{1}{r}</tex> всегда делится на текущую величину <tex> r ^{-l_i} </tex> . А раз остаток делится, то взяв <tex> l_i </tex> в группу мы не перепрыгнем через максимальное значение.<br />
<br />
У всех слов из одной группы будет одна и та же начальная буква. Затем нужно запустить данную процедуру для каждой группы слов, предварительно обрезав первую букву.<br />
<br />
Доказательство корректности проведём по индукции по величине <tex> l_n </tex> . <br />
<br />
'''База:''' Если <tex> l_n = 0 </tex>, то процедура корректна. <br />
<br />
'''Переход: ''' Допустим, что процедура корректна для <tex> l_n = w </tex> . Докажем, что процедура корректна и для <tex> l_n = w + 1 </tex> . <br />
<br />
Заметим, что у слов каждой группы будет своя начальная буква, поэтому достаточно проверить префиксность кода для каждой группы. А это истинно по предположению индукции, где для каждой группы <tex> l_i \leqslant w </tex> . <br />
<br />
}}<br />
<br />
== Замечания ==<br />
<br />
Когда имеет место строгое неравенство? Легко заметить, что если любая концевая вершина дерева является кодовым словом, то <tex>K = 1</tex>. Строгое неравенство имеет место лишь в случае, когда некоторые из концевых вершин не используются. Однако, в случае двоичного кодового алфавита какая-нибудь концевая вершина не используется, то предыдущее решение оказывается лишним, и соответствующая цифра может быть удалена из каждого кодового слова, декодирование которого проходит через эту вершину. Таким образом, если имеет место строгое неравенство, то код неэффективен, но для двоичных деревьев очевидно, как можно его улучшить.<br />
<br />
Заметим еще раз, что теорема утверждает существование такого кода и ничего не говорит о конкретных кодах. Может существовать код, который удовлетворяет неравенству Крафта и тем не менее не является префиксным.<br />
<br />
<br />
== См.также ==<br />
*[[Неравенство Макмиллана]]<br />
<br />
== Источники информации ==<br />
*[http://ru.wikipedia.org/wiki/Неравенство_Крафта Википедия — Неравенство Крафта]<br />
*[http://books.sernam.ru/book_htc.php?id=35 Неравенство Крафта]<br />
*[https://xlinux.nist.gov/dads/HTML/kraftsinqlty.html Kraft's inequality]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Алгоритмы сжатия]]</div>Damm1thttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B5%D1%80%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%9A%D1%80%D0%B0%D1%84%D1%82%D0%B0&diff=63276Неравенство Крафта2018-01-01T12:11:51Z<p>Damm1t: доказательство достаточности</p>
<hr />
<div><br />
Рассматриваемое ниже неравенство Крафта показывает для каких длин кодовых слов существует префиксный код.<br />
<br />
{{Теорема<br />
|about=неравенство Крафта <br />
|statement=<br />
Пусть <tex>\Sigma</tex> — [[Основные определения, связанные со строками|алфавит]] из <tex>n</tex> [[Основные определения, связанные со строками|символов]], кодовые слова которого имеют длины <tex>l_1 \leqslant l_2 \leqslant \ldots \leqslant l_n </tex>, где <tex>i\in \left [ 1, n \right ]</tex>. <br />
<br />
Тогда необходимое и достаточное условие существования префиксного кода в <tex>r</tex>-ичном алфавите для символов из <tex>\Sigma</tex>, состоит в выполнении неравенства:<br />
<br />
<center><tex> \sum\limits_{i = 1}^{n} r ^{-l_i} \leqslant 1 </tex></center><br />
<br />
|proof= <br />
<br />
[[file:Treeforkraft.jpg|thumb|250px|Иллюстрация к доказательству индукционного перехода]]<br />
<br />
'''Необходимость:'''<br />
<br />
Напомним, что префиксный код можно представить в виде <tex>r</tex>-ичного корневого дерева, рёбра которого соответствуют символам алфавита, а листья соответствующим кодам. Неравенство Крафта будем доказывать по [[Математическая индукция|индукции]]. <br />
<br />
Для простоты рассмотрим сначала случай двоичного алфавита, то есть <tex>r = 2</tex>. <br />
<br />
'''База:''' Если максимальная длина пути на дереве равна <tex>1</tex>, то в дереве есть одно или два ребра длины <tex>1</tex>. Таким образом, либо <tex> \dfrac{1}{2} \leqslant 1 </tex> — для одного символа источника, либо <tex> \dfrac{1}{2} + \dfrac{1}{2} \leqslant 1 </tex> — для двух символов источника. <br />
<br />
'''Переход:''' Предположим далее, что неравенство Крафта справедливо для всех деревьев высоты меньше <tex>n - 1</tex>. <br />
Докажем, что оно справедливо и для всех деревьев высоты меньше <tex>n</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>.<br />
<br />
<br />
В случае произвольного недвоичного основания <tex>r</tex> имеется не более <tex>r</tex> ребер, исходящих из каждой вершины, то есть не более <tex>r</tex> поддеревьев; каждое из них присоединяется к основному дереву, давая дополнительный множитель <tex>\dfrac{1}{r}</tex>. Отсюда снова следует утверждение теоремы.<br />
<br />
'''Достаточность:'''<br />
<br />
Для доказательства достаточности опишем рекурсивную процедуру, которая строит код для данного набора длин <tex> l_i </tex>, удовлетворяющих неравенству <tex> \sum\limits_{i = 1}^{n} r ^{-l_i} \leqslant 1 </tex>.<br />
Если некоторое <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> l_i </tex> в порядке увеличения индекса. Несложно понять, что в таком случае группа будет либо полностью укомплектована, либо будут исчерпаны все возможные <tex> l_i </tex>. Затем нужно запустить данную процедуру для каждой группы слов, предварительно обрезав первую букву.<br />
<br />
Доказательство корректности проведём по индукции по величине <tex> l_n </tex>. <br />
<br />
'''База:''' Если <tex> l_n = 0 </tex>, то процедура корректна. <br />
<br />
'''Переход: ''' (очевиден) Допустим, что процедура корректна для <tex> l_n = w </tex>. Докажем, что процедура корректна и для <tex> l_n = w + 1 </tex>. <br />
<br />
Заметим, что у слов каждой группы будет своя начальная буква, поэтому достаточно проверить префиксность кода для каждой группы. А это истинно по предположению индукции, где для каждой группы <tex> l_i \leqslant w </tex>. <br />
<br />
}}<br />
<br />
== Замечания ==<br />
<br />
Когда имеет место строгое неравенство? Легко заметить, что если любая концевая вершина дерева является кодовым словом, то <tex>K = 1</tex>. Строгое неравенство имеет место лишь в случае, когда некоторые из концевых вершин не используются. Однако, в случае двоичного кодового алфавита какая-нибудь концевая вершина не используется, то предыдущее решение оказывается лишним, и соответствующая цифра может быть удалена из каждого кодового слова, декодирование которого проходит через эту вершину. Таким образом, если имеет место строгое неравенство, то код неэффективен, но для двоичных деревьев очевидно, как можно его улучшить.<br />
<br />
Заметим еще раз, что теорема утверждает существование такого кода и ничего не говорит о конкретных кодах. Может существовать код, который удовлетворяет неравенству Крафта и тем не менее не является префиксным.<br />
<br />
<br />
== См.также ==<br />
*[[Неравенство Макмиллана]]<br />
<br />
== Источники информации ==<br />
*[http://ru.wikipedia.org/wiki/Неравенство_Крафта Википедия — Неравенство Крафта]<br />
*[http://books.sernam.ru/book_htc.php?id=35 Неравенство Крафта]<br />
*[https://xlinux.nist.gov/dads/HTML/kraftsinqlty.html Kraft's inequality]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Алгоритмы сжатия]]</div>Damm1thttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B5%D1%80%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%9A%D1%80%D0%B0%D1%84%D1%82%D0%B0&diff=63265Неравенство Крафта2017-12-31T15:44:00Z<p>Damm1t: правки замечаний</p>
<hr />
<div><br />
Рассматриваемое ниже неравенство Крафта показывает для каких длин кодовых слов существует префиксный код.<br />
<br />
{{Теорема<br />
|about=неравенство Крафта <br />
|statement=<br />
Пусть <tex>\Sigma</tex> — [[Основные определения, связанные со строками|алфавит]] из <tex>n</tex> [[Основные определения, связанные со строками|символов]], кодовые слова которого имеют длины <tex>l_1 \leqslant l_2 \leqslant \ldots \leqslant l_n </tex>, где <tex>i\in \left [ 1, n \right ]</tex>. <br />
<br />
Тогда необходимое и достаточное условие существования префиксного кода в <tex>r</tex>-ичном алфавите для символов из <tex>\Sigma</tex>, состоит в выполнении неравенства:<br />
<br />
<center><tex> \sum\limits_{i = 1}^{n} r ^{-l_i} \leqslant 1 </tex></center><br />
<br />
|proof= <br />
<br />
[[file:Treeforkraft.jpg|thumb|250px|Иллюстрация к доказательству индукционного перехода]]<br />
Напомним, что префиксный код можно представить в виде <tex>r</tex>-ичного корневого дерева, рёбра которого соответствуют символам алфавита, а листья соответствующим кодам. Неравенство Крафта будем доказывать по [[Математическая индукция|индукции]]. <br />
<br />
'''Необходимость:'''<br />
<br />
Для простоты рассмотрим сначала случай двоичного алфавита, то есть <tex>r = 2</tex>. <br />
<br />
База: Если максимальная длина пути на дереве равна <tex>1</tex>, то в дереве есть одно или два ребра длины <tex>1</tex>. Таким образом, либо <tex> \dfrac{1}{2} \leqslant 1 </tex> — для одного символа источника, либо <tex> \dfrac{1}{2} + \dfrac{1}{2} \leqslant 1 </tex> — для двух символов источника. <br />
<br />
Предположим далее, что неравенство Крафта справедливо для всех деревьев высоты меньше <tex>n - 1</tex>. <br />
Докажем, что оно справедливо и для всех деревьев высоты меньше <tex>n</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>.<br />
<br />
<br />
В случае произвольного недвоичного основания <tex>r</tex> имеется не более <tex>r</tex> ребер, исходящих из каждой вершины, то есть не более <tex>r</tex> поддеревьев; каждое из них присоединяется к основному дереву, давая дополнительный множитель <tex>\dfrac{1}{r}</tex>. Отсюда снова следует утверждение теоремы.<br />
<br />
'''Достаточность:'''<br />
<br />
Для доказательства достаточности опишем рекурсивную процедуру, которая строит код для данного набора длин <tex> l_i </tex>, удовлетворяющих неравенству <tex> \sum\limits_{i = 1}^{n} r ^{-l_i} \leqslant 1 </tex>.<br />
Нужно разделить длины <tex> l_i </tex> на <tex>r</tex> групп, внутри каждой из которых <tex> \sum\limits r ^{-l_i} \leqslant \dfrac{1}{r} </tex>. У всех слов из слов из одной группы будет одна и та же начальная буква. Разделить длины на группы можно следующим жадным образом: брать <tex> l_i </tex> в порядке увеличения индекса. Несложно понять, что в таком случае группа будет либо полностью укомплектована, либо будут исчерпаны все возможные <tex> l_i </tex>. Затем нужно запустить данную процедуру для каждой группы слов, предварительно обрезав первую букву.<br />
<br />
}}<br />
<br />
== Замечания ==<br />
<br />
Когда имеет место строгое неравенство? Легко заметить, что если любая концевая вершина дерева является кодовым словом, то <tex>K = 1</tex>. Строгое неравенство имеет место лишь в случае, когда некоторые из концевых вершин не используются. Однако, в случае двоичного кодового алфавита какая-нибудь концевая вершина не используется, то предыдущее решение оказывается лишним, и соответствующая цифра может быть удалена из каждого кодового слова, декодирование которого проходит через эту вершину. Таким образом, если имеет место строгое неравенство, то код неэффективен, но для двоичных деревьев очевидно, как можно его улучшить.<br />
<br />
Заметим еще раз, что теорема утверждает существование такого кода и ничего не говорит о конкретных кодах. Может существовать код, который удовлетворяет неравенству Крафта и тем не менее не является префиксным.<br />
<br />
<br />
== См.также ==<br />
*[[Неравенство Макмиллана]]<br />
<br />
== Источники информации ==<br />
*[http://ru.wikipedia.org/wiki/Неравенство_Крафта Википедия — Неравенство Крафта]<br />
*[http://books.sernam.ru/book_htc.php?id=35 Неравенство Крафта]<br />
*[https://xlinux.nist.gov/dads/HTML/kraftsinqlty.html Kraft's inequality]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Алгоритмы сжатия]]</div>Damm1thttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B5%D1%80%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%9A%D1%80%D0%B0%D1%84%D1%82%D0%B0&diff=63229Неравенство Крафта2017-12-29T19:30:42Z<p>Damm1t: </p>
<hr />
<div><br />
Рассматриваемое ниже неравенство Крафта показывает, для каких длин кодовых слов существует префиксный код, но приведенное ниже доказательство не является конструктивным.<br />
{{Теорема<br />
|about=неравенство Крафта <br />
|statement=<br />
Необходимое и достаточное условие существования префиксного кода в <tex>r</tex>-ичном дереве для источника с [[Основные определения, связанные со строками|алфавитом]] <tex>S</tex> из <tex>n</tex> [[Основные определения, связанные со строками|символов]] <tex>s_i</tex>, где <tex>i\in \left [ 1, n \right ]</tex>, кодовые слова которого имеют длины <tex>l_1 \leqslant l_2 \leqslant \ldots \leqslant l_n </tex>, состоит в выполнении неравенства:<br />
<br />
<center><tex> \sum\limits_{i = 1}^{n} r ^{-l_i} \leqslant 1 </tex></center><br />
<br />
|proof= <br />
<br />
[[file:Treeforkraft.jpg|thumb|250px|Иллюстрация к доказательству индукционного перехода]]<br />
Неравенство Крафта легко доказать с помощью дерева декодирования, существование которого следует из существования префиксного кода. Будем рассуждать по [[Математическая индукция|индукции]]. <br />
<br />
Для простоты рассмотрим сначала случай двоичного алфавита, то есть <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> — для двух символов источника. <br />
<br />
Предположим далее, что неравенство Крафта справедливо для всех деревьев длины меньше <tex>n</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>.<br />
<br />
В случае произвольного недвоичного основания <tex>r</tex> имеется не более <tex>r</tex> ребер, исходящих из каждой вершины, то есть не более <tex>r</tex> поддеревьев; каждое из них присоединяется к основному дереву, давая дополнительный множитель <tex>\dfrac{1}{r}</tex>. Отсюда снова следует утверждение теоремы.<br />
<br />
}}<br />
<br />
== Замечания ==<br />
<br />
Когда имеет место строгое неравенство? Легко заметить, что если любая концевая вершина дерева является кодовым словом, то <tex>K = 1</tex>. Строгое неравенство имеет место лишь в случае, когда некоторые из концевых вершин не используются. Однако, в случае двоичного кодового алфавита какая-нибудь концевая вершина не используется, то предыдущее решение оказывается лишним, и соответствующая цифра может быть удалена из каждого кодового слова, декодирование которого проходит через эту вершину. Таким образом, если имеет место строгое неравенство, то код неэффективен, но для двоичных деревьев очевидно, как можно его улучшить.<br />
<br />
Заметим еще раз, что теорема утверждает существование такого кода и ничего не говорит о конкретных кодах. Может существовать код, который удовлетворяет неравенству Крафта и тем не менее не является префиксным.<br />
<br />
<br />
== См.также ==<br />
*[[Неравенство Макмиллана]]<br />
<br />
== Источники информации ==<br />
*[http://ru.wikipedia.org/wiki/Неравенство_Крафта Википедия — Неравенство Крафта]<br />
*[http://books.sernam.ru/book_htc.php?id=35 Неравенство Крафта]<br />
*[https://xlinux.nist.gov/dads/HTML/kraftsinqlty.html Kraft's inequality]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Алгоритмы сжатия]]</div>Damm1thttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B5%D1%80%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%9A%D1%80%D0%B0%D1%84%D1%82%D0%B0&diff=63228Неравенство Крафта2017-12-29T19:29:43Z<p>Damm1t: </p>
<hr />
<div><br />
Рассматриваемое ниже неравенство Крафта показывает, для каких длин кодовых слов существует префиксный код, но приведенное ниже доказательство не является конструктивным.<br />
{{Теорема<br />
|about=неравенство Крафта <br />
|statement=<br />
Необходимое и достаточное условие существования префиксного кода в <tex>r</tex>-ичном дереве для источника с [[Основные определения, связанные со строками|алфавитом]] <tex>S</tex> из <tex>n</tex> [[Основные определения, связанные со строками|символов]] <tex>s_i</tex>, где <tex>i\in \left [ 1, n \right ]</tex>, кодовые слова которого имеют длины <tex>l_1 \leqslant l_2 \leqslant \ldots \leqslant l_n </tex>, состоит в выполнении неравенства:<br />
<br />
<center><tex> \sum\limits_{i = 1}^{n} r ^{-l_i} \leqslant 1 </tex></center><br />
<br />
|proof= <br />
<br />
[[file:Treeforkraft.jpg|thumb|250px|Иллюстрация к доказательству индукционного перехода]]<br />
Неравенство Крафта легко доказать с помощью дерева декодирования, существование которого следует из существования префиксного кода. Будем рассуждать по [[Математическая индукция|индукции]]. <br />
<br />
Для простоты рассмотрим сначала случай двоичного алфавита, то есть <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> — для двух символов источника. <br />
<br />
Предположим далее, что неравенство Крафта справедливо для всех деревьев длины меньше <tex>n</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>.<br />
<br />
В случае произвольного недвоичного основания <tex>r</tex> имеется не более <tex>r</tex> ребер, исходящих из каждой вершины, то есть не более <tex>r</tex> поддеревьев; каждое из них присоединяется к основному дереву, давая дополнительный множитель <tex>\dfrac{1}{r}</tex>. Отсюда снова следует утверждение теоремы.<br />
<br />
}}<br />
<br />
== Замечания ==<br />
<br />
Когда имеет место строгое неравенство? Легко заметить, что если любая концевая вершина дерева является кодовым словом, то <tex>K = 1</tex>. Строгое неравенство имеет место лишь в случае, когда некоторые из концевых вершин не используются. Однако, в случае двоичного кодового алфавита какая-нибудь концевая вершина не используется, то предыдущее решение оказывается лишним, и соответствующая цифра может быть удалена из каждого кодового слова, декодирование которого проходит через эту вершину. Таким образом, если имеет место строгое неравенство, то код неэффективен, но для двоичных деревьев очевидно, как можно его улучшить.<br />
<br />
Заметим еще раз, что теорема утверждает существование такого кода и ничего не говорит о конкретных кодах. Может существовать код, который удовлетворяет неравенству Крафта и тем не менее не является мгновенным.<br />
<br />
<br />
== См.также ==<br />
*[[Неравенство Макмиллана]]<br />
<br />
== Источники информации ==<br />
*[http://ru.wikipedia.org/wiki/Неравенство_Крафта Википедия — Неравенство Крафта]<br />
*[http://books.sernam.ru/book_htc.php?id=35 Неравенство Крафта]<br />
*[https://xlinux.nist.gov/dads/HTML/kraftsinqlty.html Kraft's inequality]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Алгоритмы сжатия]]</div>Damm1thttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B5%D1%80%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%9A%D1%80%D0%B0%D1%84%D1%82%D0%B0&diff=63227Неравенство Крафта2017-12-29T19:28:15Z<p>Damm1t: </p>
<hr />
<div><br />
Рассматриваемое ниже неравенство Крафта показывает, для каких длин кодовых слов существует префиксный код, но приведенное ниже доказательство не является конструктивным.<br />
{{Теорема<br />
|about=неравенство Крафта <br />
|statement=<br />
Необходимое и достаточное условие существования префиксного кода в <tex>r</tex>-ичном дереве для источника с [[Основные определения, связанные со строками|алфавитом]]<br />
<tex>S</tex> из <tex>n</tex> [[Основные определения, связанные со строками|символов]] <tex>s_i</tex>, где <tex>i\in \left [ 1, n \right ]</tex>, кодовые слова которого имеют длины <tex>l_1 \leqslant l_2 \leqslant \ldots \leqslant l_n </tex>, состоит в выполнении неравенства:<br />
<br />
<center><tex> \sum\limits_{i = 1}^{n} r ^{-l_i} \leqslant 1 </tex></center><br />
<br />
|proof= <br />
<br />
[[file:Treeforkraft.jpg|thumb|250px|Иллюстрация к доказательству индукционного перехода]]<br />
Неравенство Крафта легко доказать с помощью дерева декодирования, существование которого следует из существования префиксного кода. Будем рассуждать по [[Математическая индукция|индукции]]. <br />
<br />
Для простоты рассмотрим сначала случай двоичного алфавита, то есть <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> — для двух символов источника. <br />
<br />
Предположим далее, что неравенство Крафта справедливо для всех деревьев длины меньше <tex>n</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>.<br />
<br />
В случае произвольного недвоичного основания <tex>r</tex> имеется не более <tex>r</tex> ребер, исходящих из каждой вершины, то есть не более <tex>r</tex> поддеревьев; каждое из них присоединяется к основному дереву, давая дополнительный множитель <tex>\dfrac{1}{r}</tex>. Отсюда снова следует утверждение теоремы.<br />
<br />
}}<br />
<br />
== Замечания ==<br />
<br />
Когда имеет место строгое неравенство? Легко заметить, что если любая концевая вершина дерева является кодовым словом, то <tex>K = 1</tex>. Строгое неравенство имеет место лишь в случае, когда некоторые из концевых вершин не используются. Однако, в случае двоичного кодового алфавита какая-нибудь концевая вершина не используется, то предыдущее решение оказывается лишним, и соответствующая цифра может быть удалена из каждого кодового слова, декодирование которого проходит через эту вершину. Таким образом, если имеет место строгое неравенство, то код неэффективен, но для двоичных деревьев очевидно, как можно его улучшить.<br />
<br />
Заметим еще раз, что теорема утверждает существование такого кода и ничего не говорит о конкретных кодах. Может существовать код, который удовлетворяет неравенству Крафта и тем не менее не является мгновенным.<br />
<br />
<br />
== См.также ==<br />
*[[Неравенство Макмиллана]]<br />
<br />
== Источники информации ==<br />
*[http://ru.wikipedia.org/wiki/Неравенство_Крафта Википедия — Неравенство Крафта]<br />
*[http://books.sernam.ru/book_htc.php?id=35 Неравенство Крафта]<br />
*[https://xlinux.nist.gov/dads/HTML/kraftsinqlty.html Kraft's inequality]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Алгоритмы сжатия]]</div>Damm1thttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B5%D1%80%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%9A%D1%80%D0%B0%D1%84%D1%82%D0%B0&diff=63226Неравенство Крафта2017-12-29T19:19:23Z<p>Damm1t: косметическая правка текста</p>
<hr />
<div><br />
Рассматриваемое ниже неравенство Крафта показывает, для каких длин кодовых слов существует префиксный код, но приведенное ниже доказательство не является конструктивным.<br />
{{Теорема<br />
|about=неравенство Крафта <br />
|statement=<br />
Необходимое и достаточное условие существования префиксного кода в <tex>r</tex> (ичном) дереве для источника с алфавитом <tex>S</tex> из <tex>n</tex> символов <tex>s_i</tex>, где <tex>i\in \left [ 1, n \right ]</tex>, кодовые слова которого имеют длины <tex>l_1 \leqslant l_2 \leqslant \ldots \leqslant l_n </tex>, состоит в выполнении неравенства:<br />
<br />
<center><tex> \sum\limits_{i = 1}^{n} r ^{-l_i} \leqslant 1 </tex></center><br />
<br />
|proof= <br />
<br />
[[file:Treeforkraft.jpg|thumb|250px|Иллюстрация к доказательству индукционного перехода]]<br />
Неравенство Крафта легко доказать с помощью дерева декодирования, существование которого следует из существования префиксного кода. Будем рассуждать по [[Математическая индукция|индукции]]. <br />
<br />
Для простоты рассмотрим сначала случай двоичного [[Основные определения, связанные со строками|алфавита]], то есть <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> — для двух символов источника. <br />
<br />
Предположим далее, что неравенство Крафта справедливо для всех деревьев длины меньше <tex>n</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>.<br />
<br />
В случае произвольного недвоичного основания <tex>r</tex> имеется не более <tex>r</tex> ребер, исходящих из каждой вершины, то есть не более <tex>r</tex> поддеревьев; каждое из них присоединяется к основному дереву, давая дополнительный множитель <tex>\dfrac{1}{r}</tex>. Отсюда снова следует утверждение теоремы.<br />
<br />
}}<br />
<br />
== Замечания ==<br />
<br />
Когда имеет место строгое неравенство? Легко заметить, что если любая концевая вершина дерева является кодовым словом, то <tex>K = 1</tex>. Строгое неравенство имеет место лишь в случае, когда некоторые из концевых вершин не используются. Однако, в случае двоичного кодового алфавита какая-нибудь концевая вершина не используется, то предыдущее решение оказывается лишним, и соответствующая цифра может быть удалена из каждого кодового слова, декодирование которого проходит через эту вершину. Таким образом, если имеет место строгое неравенство, то код неэффективен, но для двоичных деревьев очевидно, как можно его улучшить.<br />
<br />
Заметим еще раз, что теорема утверждает существование такого кода и ничего не говорит о конкретных кодах. Может существовать код, который удовлетворяет неравенству Крафта и тем не менее не является мгновенным.<br />
<br />
<br />
== См.также ==<br />
*[[Неравенство Макмиллана]]<br />
<br />
== Источники информации ==<br />
*[http://ru.wikipedia.org/wiki/Неравенство_Крафта Википедия — Неравенство Крафта]<br />
*[http://books.sernam.ru/book_htc.php?id=35 Неравенство Крафта]<br />
*[https://xlinux.nist.gov/dads/HTML/kraftsinqlty.html Kraft's inequality]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Алгоритмы сжатия]]</div>Damm1thttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B5%D1%80%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%9A%D1%80%D0%B0%D1%84%D1%82%D0%B0&diff=63221Неравенство Крафта2017-12-29T18:02:00Z<p>Damm1t: мелкие правки tex</p>
<hr />
<div><br />
Рассматриваемое ниже неравенство Крафта показывает, для каких длин кодовых слов существует префиксный код, но приведенное ниже доказательство не является конструктивным.<br />
{{Теорема<br />
|about=неравенство Крафта <br />
|statement=<br />
Необходимое и достаточное условие существования префиксного кода для источника с алфавитом <tex>S</tex> из <tex>q</tex> символов <tex>s_i</tex>, где <tex>i\in \left [ 1, q \right ]</tex>, кодовые слова которого имеют длины <tex>l_1 \leq l_2 \leq \ldots \leq l_q</tex>, состоит в выполнении неравенства:<br />
<br />
<center><tex> \sum\limits_{i = 1}^{q} r ^{-l_i} \leqslant 1 </tex></center><br />
где <tex>r</tex> — основание (число символов) в кодовом алфавите.<br />
<br />
|proof= <br />
<br />
[[file:Treeforkraft.jpg|thumb|250px|Иллюстрация к доказательству индукционного перехода]]<br />
Неравенство Крафта легко доказать с помощью дерева декодирования, существование которого следует из существования префиксного кода. Будем рассуждать по [[Математическая индукция|индукции]]. <br />
<br />
Для простоты рассмотрим сначала случай двоичного алфавита, т. е. <tex>r = 2</tex>. Если максимальная длина пути на дереве равна <tex>1</tex>, то в дереве есть одно или два ребра длины <tex>1</tex>. Таким образом, либо <tex> \dfrac{1}{2} \leq 1 </tex> — для одного символа источника, либо <tex> \dfrac{1}{2} + \dfrac{1}{2} \leq 1 </tex> — для двух символов источника. <br />
<br />
Предположим далее, что неравенство Крафта справедливо для всех деревьев длины меньше <tex>n</tex>. Для данного дерева максимальной длины <tex>n</tex> ребра из первой вершины ведут к двум поддеревьям, длины которых не превышают <tex>n - 1</tex>; для этих поддеревьев имеем неравенства <tex>K_1 \leq 1</tex> и <tex>K_2 \leq 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 \leq 1</tex>.<br />
<br />
В случае произвольного недвоичного основания <tex>r</tex> имеется не более <tex>r</tex> ребер, исходящих из каждой вершины, т. е. не более <tex>r</tex> поддеревьев; каждое из них присоединяется к основному дереву, давая дополнительный множитель <tex>\dfrac{1}{r}</tex>. Отсюда снова следует утверждение теоремы.<br />
<br />
<br />
== Замечания ==<br />
<br />
Когда имеет место строгое неравенство? Легко заметить, что если любая концевая вершина дерева является кодовым словом, то <tex>K = 1</tex>. Строгое неравенство имеет место лишь в случае, когда некоторые из концевых вершин не используются. Однако, в случае двоичного кодового алфавита какая-нибудь концевая вершина не используется, то предыдущее решение оказывается лишним, и соответствующая цифра может быть удалена из каждого кодового слова, декодирование которого проходит через эту вершину. Таким образом, если имеет место строгое неравенство, то код неэффективен, но для двоичных деревьев очевидно, как можно его улучшить.<br />
<br />
Заметим еще раз, что теорема утверждает существование такого кода и ничего не говорит о конкретных кодах. Может существовать код, который удовлетворяет неравенству Крафта и тем не менее не является мгновенным.<br />
<br />
}}<br />
<br />
== См.также ==<br />
*[[Неравенство Макмиллана]]<br />
<br />
== Источники информации ==<br />
*[http://ru.wikipedia.org/wiki/Неравенство_Крафта Википедия — Неравенство Крафта]<br />
*[http://books.sernam.ru/book_htc.php?id=35 Неравенство Крафта]<br />
*[https://xlinux.nist.gov/dads/HTML/kraftsinqlty.html Kraft's inequality]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Алгоритмы сжатия]]</div>Damm1thttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B5%D1%80%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%9A%D1%80%D0%B0%D1%84%D1%82%D0%B0&diff=63220Неравенство Крафта2017-12-29T17:37:43Z<p>Damm1t: мелкие изменения текста</p>
<hr />
<div><br />
Рассматриваемое ниже неравенство Крафта показывает, для каких длин кодовых слов существует префиксный код, но приведенное ниже доказательство не является конструктивным.<br />
{{Теорема<br />
|about=неравенство Крафта <br />
|statement=<br />
Необходимое и достаточное условие существования префиксного кода для источника с алфавитом <tex>S</tex> из <tex>q</tex> символов <tex>s_i</tex>, где <tex>i\in \left [ 1, q \right ]</tex>, кодовые слова которого имеют длины <tex>l_1 \leq l_2 \leq ... \leq l_q</tex>, состоит в выполнении неравенства:<br />
<br />
<center><tex> \sum\limits_{i = 1}^{q} r ^{-l_i} \leqslant 1 </tex></center><br />
где <tex>r</tex> — основание (число символов) в кодовом алфавите.<br />
<br />
|proof= <br />
<br />
[[file:Treeforkraft.jpg|thumb|250px|Иллюстрация к доказательству индукционного перехода]]<br />
Неравенство Крафта легко доказать с помощью дерева декодирования, существование которого следует из существования префиксного кода. Будем рассуждать по [[Математическая индукция|индукции]]. <br />
<br />
Для простоты рассмотрим сначала случай двоичного алфавита, т. е. <tex>r = 2</tex>. Если максимальная длина пути на дереве равна <tex>1</tex>, то в дереве есть одно или два ребра длины <tex>1</tex>. Таким образом, либо <tex> \frac{1}{2} \leq 1 </tex> — для одного символа источника, либо <tex> \frac{1}{2} + \frac{1}{2} \leq 1 </tex> — для двух символов источника. <br />
<br />
Предположим далее, что неравенство Крафта справедливо для всех деревьев длины меньше <tex>n</tex>. Для данного дерева максимальной длины <tex>n</tex> ребра из первой вершины ведут к двум поддеревьям, длины которых не превышают <tex>n - 1</tex>; для этих поддеревьев имеем неравенства <tex>K_1 \leq 1</tex> и <tex>K_2 \leq 1</tex>, где <tex>K_1, K_2</tex> — значения соответствующих им сумм. Каждая длина <tex>l_i</tex> в поддереве увеличивается на <tex>1</tex>, когда поддерево присоединяется к основному дереву, поэтому возникает дополнительный множитель <tex>\frac{1}{2}</tex>. Таким образом, имеем <tex>\frac{1}{2} K_1 + \frac{1}{2} K_2 \leq 1</tex>.<br />
<br />
В случае произвольного недвоичного основания <tex>r</tex> имеется не более <tex>r</tex> ребер, исходящих из каждой вершины, т. е. не более <tex>r</tex> поддеревьев; каждое из них присоединяется к основному дереву, давая дополнительный множитель <tex>\frac{1}{r}</tex>. Отсюда снова следует утверждение теоремы.<br />
<br />
<br />
== Замечания ==<br />
<br />
Когда имеет место строгое неравенство? Легко заметить, что если любая концевая вершина дерева является кодовым словом, то <tex>K = 1</tex>. Строгое неравенство имеет место лишь в случае, когда некоторые из концевых вершин не используются. Однако, в случае двоичного кодового алфавита какая-нибудь концевая вершина не используется, то предыдущее решение оказывается лишним, и соответствующая цифра может быть удалена из каждого кодового слова, декодирование которого проходит через эту вершину. Таким образом, если имеет место строгое неравенство, то код неэффективен, но для двоичных деревьев очевидно, как можно его улучшить.<br />
<br />
Заметим еще раз, что теорема утверждает существование такого кода и ничего не говорит о конкретных кодах. Может существовать код, который удовлетворяет неравенству Крафта и тем не менее не является мгновенным.<br />
<br />
}}<br />
<br />
== См.также ==<br />
*[[Неравенство Макмиллана]]<br />
<br />
== Источники информации ==<br />
*[http://ru.wikipedia.org/wiki/Неравенство_Крафта Википедия — Неравенство Крафта]<br />
*[http://books.sernam.ru/book_htc.php?id=35 Неравенство Крафта]<br />
*[https://xlinux.nist.gov/dads/HTML/kraftsinqlty.html Kraft's inequality]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Алгоритмы сжатия]]</div>Damm1thttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B5%D1%80%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%9A%D1%80%D0%B0%D1%84%D1%82%D0%B0&diff=63216Неравенство Крафта2017-12-29T01:47:49Z<p>Damm1t: полное переписывание статьи</p>
<hr />
<div><br />
Рассматриваемое ниже неравенство Крафта показывает, для каких длин кодовых слов существует префиксный код, но не показывает, как его строить.<br />
{{Теорема<br />
|about=неравенство Крафта <br />
|statement=<br />
Необходимое и достаточное условие существования префиксного кода для источника с алфавитом <tex>S</tex> из <tex>q</tex> символов <tex>s_i</tex>, где <tex>i\in \left [ 1, q \right ]</tex>, кодовые слова которого имеют длины <tex>l_1 \leq l_2 \leq ... \leq l_q</tex>, состоит в выполнении неравенства:<br />
<br />
<center><tex> \sum\limits_{i = 1}^{q} r ^{-l_i} \leqslant 1 </tex></center><br />
где <tex>r</tex> - основание (число символов) в кодовом алфавите.<br />
<br />
|proof= <br />
<br />
[[file:Treeforkraft.jpg|thumb|250px|Иллюстрация к доказательству индукционного перехода]]<br />
Неравенство Крафта легко доказать с помощью дерева декодирования, существование которого следует из существования префиксного кода. Будем рассуждать по [[Математическая индукция|индукции]]. <br />
<br />
Для простоты рассмотрим сначала случай двоичного алфавита, т. е. <tex>r = 2</tex>. Если максимальная длина пути на дереве равна 1, то на нем есть одно или два ребра длины 1. Таким образом, либо <tex> \frac{1}{2} \leq 1 </tex> — для одного символа источника, либо <tex> \frac{1}{2} + \frac{1}{2} \leq 1 </tex> - для двух символов источника. <br />
<br />
Предположим далее, что неравенство Крафта справедливо для всех деревьев длины меньше <tex>n</tex>. Для данного дерева максимальной длины <tex>n</tex> ребра из первой вершины ведут к двум поддеревьям, длины которых не превышают <tex>n - 1</tex>; для этих поддеревьев имеем неравенства <tex>K_1 \leq 1</tex> и <tex>K_2 \leq 1</tex>, где <tex>K_1, K_2</tex> - значения соответствующих им сумм. Каждая длина <tex>l_i</tex> в поддереве увеличивается на 1, когда поддерево присоединяется к основному дереву, поэтому возникает дополнительный множитель <tex>\frac{1}{2}</tex>. Таким образом, имеем <tex>\frac{1}{2} K_1 + \frac{1}{2} K_2 \leq 1</tex>.<br />
<br />
В случае произвольного недвоичного основания <tex>r</tex> имеется не более <tex>r</tex> ребер, исходящих из каждой вершины, т. е. не более <tex>r</tex> поддеревьев; каждое из них присоединяется к основному дереву, давая дополнительный множитель <tex>\frac{1}{r}</tex>. Отсюда снова следует утверждение теоремы.<br />
<br />
<br />
== Замечания ==<br />
<br />
Когда имеет место строгое неравенство? Легко заметить, что если любая концевая вершина дерева является кодовым словом, то <tex>K = 1</tex>. Строгое неравенство имеет место лишь в случае, когда некоторые из концевых вершин не используются. Однако, в случае двоичного кодового алфавита какая-нибудь концевая вершина не используется, то предыдущее решение оказывается лишним, и соответствующая цифра может быть удалена из каждого кодового слова, декодирование которого проходит через эту вершину. Таким образом, если имеет место строгое неравенство, то код неэффективен, но для двоичных деревьев очевидно, как можно его улучшить.<br />
<br />
Заметим еще раз, что теорема утверждает существование такого кода и ничего не говорит о конкретных кодах. Может существовать код, который удовлетворяет неравенству Крафта и тем не менее не является мгновенным.<br />
<br />
}}<br />
<br />
== См.также ==<br />
*[[Неравенство Макмиллана]]<br />
<br />
== Источники информации ==<br />
*[http://ru.wikipedia.org/wiki/Неравенство_Крафта Википедия — Неравенство Крафта]<br />
*[http://books.sernam.ru/book_htc.php?id=35 Неравенство Крафта]<br />
*[https://xlinux.nist.gov/dads/HTML/kraftsinqlty.html Kraft's inequality]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Алгоритмы сжатия]]</div>Damm1thttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Treeforkraft.jpg&diff=63213Файл:Treeforkraft.jpg2017-12-29T01:30:34Z<p>Damm1t: загружена новая версия «Файл:Treeforkraft.jpg»</p>
<hr />
<div></div>Damm1thttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Treeforkraft.jpg&diff=63210Файл:Treeforkraft.jpg2017-12-29T01:19:18Z<p>Damm1t: </p>
<hr />
<div></div>Damm1t