Неравенство Крафта — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Следствие)
м (rollbackEdits.php mass rollback)
 
(не показаны 84 промежуточные версии 6 участников)
Строка 1: Строка 1:
== Предварительные определения ==
 
Пусть заданы два произвольных конечных множества, которые называются, соответственно, '''кодируемым алфавитом''' и '''кодирующим алфавитом'''. Их элементы называются '''символами''', а строки (последовательности конечной длины) символов — '''словами'''. Длина слова — это число символов, из которого оно состоит.
 
  
В качестве кодирующего алфавита часто рассматривается множество <tex>\{0, 1\}</tex> — так называемый двоичный или бинарный алфавит.
+
Рассматриваемое ниже неравенство Крафта показывает для каких длин кодовых слов существует префиксный код.
  
Код называется '''разделимым''' (или ''однозначно декодируемым''), если никаким двум словам кодируемого алфавита не может быть сопоставлен один и тот же код.
+
{{Теорема
 +
|about=неравенство Крафта
 +
|statement=
 +
Пусть у нас есть <tex>n</tex> [[Основные определения, связанные со строками|символов]], кодовые слова которых имеют длины <tex>l_1 \leqslant l_2 \leqslant \ldots \leqslant l_n </tex>.
 +
 
 +
Тогда необходимое и достаточное условие существования префиксного кода в <tex>r</tex>-ичном алфавите для данных символов, состоит в выполнении неравенства:
 +
 
 +
<center><tex> \sum\limits_{i = 1}^{n} r ^{-l_i} \leqslant 1 </tex></center>
  
'''Префиксным кодом''' называется алфавитный код, в котором ни одно из кодовых слов не является префиксом никакого другого кодового слова.
+
|proof=
  
Любой префиксный код является разделимым.
+
[[file:Treeforkraft.jpg|thumb|250px|Иллюстрация к доказательству индукционного перехода]]
  
== Введение ==
+
'''Необходимость:'''
Зачем нужны коды с разной длиной кодовых символов? Дело в том, что чаще всего разные символы встречаются с разной частотой и иногда выгодно закодировать часто встречающиеся символы как можно меньшим количеством кодовых символов. Но что мешает нам выбирать кодовые слова короткими? Оказывается, для того чтобы код был разделимым, требуется чтобы длины кодовых символов удовлетворяли неравенству Крафта.
 
== '''Неравенство Крафта''' ==
 
{{Теорема
 
|statement=
 
Для любого префиксного кода <tex>C(X)</tex> отображающего произвольный алфавит <tex>A_x</tex> на двоичный алфавит <tex> \{0,1\} </tex> , длины кодовых слов должны удовлетворять неравенству:
 
  
<center><tex> \sum\limits_{i = 1}^{I} 2^{-l_i} \le 1 , </tex></center>
+
Напомним, что префиксный код можно представить в виде <tex>r</tex>-ичного корневого дерева, рёбра которого соответствуют символам алфавита, а листья соответствующим кодам. Неравенство Крафта будем доказывать по [[Математическая индукция|индукции]].  
где <tex>|A_x| = I</tex> , а <tex>l_i</tex> {{---}} длины кодовых слов.
 
  
|proof=  
+
Для простоты рассмотрим сначала случай двоичного алфавита, то есть <tex>r = 2</tex>.
  
Рассмотрим отрезок <tex>[0;1]</tex> на числовой прямой.
+
'''База:''' Если максимальная длина пути на дереве равна <tex>1</tex>, то в дереве есть одно или два ребра длины <tex>1</tex>. Таким образом, либо <tex> \dfrac{1}{2} \leqslant 1 </tex> — для одного символа источника, либо <tex> \dfrac{1}{2} + \dfrac{1}{2} \leqslant 1 </tex> — для двух символов источника.  
  
Разделим его пополам, причем левую половину обозначим <tex>M_0</tex>, а правую <tex>M_1</tex>.
+
'''Переход:''' Предположим далее, что неравенство Крафта справедливо для всех деревьев высоты меньше <tex>n - 1</tex>.
 +
Докажем, что оно справедливо и для всех деревьев высоты меньше <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>.
  
Затем поделим <tex>M_0</tex> пополам и обозначим его левую половину <tex>M_{00}</tex>, а правую <tex>M_{01}</tex>, и, проделав то же самое с <tex>M_1</tex>, получим <tex>M_{10}</tex>, а левую <tex>M_{11}</tex>.
 
  
Будем выполнять эти действия, пока длина индекса полученного отрезка <tex>M_j</tex> не превосходит <tex>max(l_1, l_2,\ldots,l_I)</tex>.
+
В случае произвольного недвоичного основания <tex>r</tex> имеется не более <tex>r</tex> ребер, исходящих из каждой вершины, то есть не более <tex>r</tex> поддеревьев; каждое из них присоединяется к основному дереву, давая дополнительный множитель <tex>\dfrac{1}{r}</tex>. Отсюда снова следует утверждение теоремы.
  
Теперь можно наблюдать, что:
+
'''Достаточность:'''
*любому кодовому слову <tex>C_j</tex> сопоставлен свой отрезок <tex>M_{C_j}</tex> (Например, кодовому слову <tex>1011</tex> соответствует отрезок <tex>M_{1011}</tex>);
 
*длина отрезка <tex>M_{C_i}</tex> равна <tex>2^{-l_i}</tex> (Например, <tex>M_0</tex> имеет длину <tex>\frac12</tex>, а <tex>M_{00}</tex> соответственно <tex>\frac14</tex>);
 
*Если кодовое слово <tex>x</tex> является префиксом кодового слова <tex>y</tex>, то отрезок <tex>M_x</tex> содержит <tex>M_y</tex> (Например, кодовое слово <tex>01</tex> является префиксом <tex>0111</tex>, а отрезок<tex>M_{01}</tex> содержит <tex>M_{0111}</tex>, это его самая правая четверть);
 
  
Рассмотрим префиксный код <tex>C(X)</tex>: так как ни одно из кодовых слов не является префиксом никакого другого кодового слова, то никакие два отрезка не пересекаются.
+
[[file:Tree2forkraft.jpg|thumb|300px|Пример разбиения на группы, при <tex> r = 2</tex>, символах ''a, b, c'', где <tex> l_a = 2, l_b = 2, l_c = 1</tex>]]
  
Если на отрезке <tex>[0;1]</tex> выбрать некоторое количество непересекающихся отрезков, то очевидно, что сумма их длин не превзойдет <tex>1</tex>, то есть <tex> \sum\limits_{i = 1}^{I} M_{C_i} \le 1</tex>.
+
#Если некоторое <tex> l_i = 0 </tex> , то <tex> n = 1 </tex> . В таком случае пустая строка является искомым префиксным кодом. Далее все <tex> l_i \geqslant 1 </tex> .
 +
#Для доказательства корректности разделим длины <tex> l_i </tex> на <tex>r</tex> , возможно пустых, групп, внутри каждой из которых <tex> \sum\limits r ^{-l_i} \leqslant \dfrac{1}{r} </tex> .
 +
#:Пусть у нас есть <tex>n</tex> символов, кодовые слова имеют длины <tex>l_1 \leqslant l_2 \leqslant \ldots \leqslant l_n </tex>. Давайте разделим данные символы на <tex>r</tex> групп, внутри каждой из которых <tex> \sum\limits r ^{-l_i} \leqslant \dfrac{1}{r} </tex> . Разделить символы на группы можно следующим жадным образом: брать <tex> l_i </tex> в порядке увеличения индекса.
 +
#:Докажем, что в таком случае группа будет либо полностью укомплектована <tex>(\sum\limits r ^{-l_i} = \dfrac{1}{r})</tex>, либо будут исчерпаны все возможные <tex> l_i </tex> . Это следует из того, что при <tex> l_i \geqslant 1 </tex> на <tex>i</tex>-ом шаге либо группа уже укомплектована, либо ее остаток равен:
 +
#: <center><tex> \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>
 +
#:Так как группа не укомплектована, то числитель положителен. Если добавим <tex> l_i </tex> в группу, то числитель уменьшится на <tex>1</tex>, где <tex>l_i - l_j</tex> неотрицательно при <tex> i \geqslant j </tex> , и <tex> r \in \mathbb{N} </tex>. Следовательно числитель — натуральное число. Тогда, взяв <tex> l_i </tex> в группу, мы не перепрыгнем через максимальное значение, то есть сумма группы <tex> \leqslant \dfrac{1}{r} </tex> . А значит, создавая группы по данному алгоритму мы сможем построить <tex>r</tex> групп, удовлетворяющих условию.
 +
#Выберем для каждой группы свой начальный символ. Запуститим данную процедуру для каждой группы слов, предварительно обрезав первую букву.
 +
#По индукции по величине <tex> l_n </tex> докажем, что наш алгоритм корректен.
 +
#:'''База:''' При <tex> l_n = 0 </tex> корректность процедуры очевидна.
 +
#:'''Переход: ''' Допустим, что процедура корректна для <tex> l_n = w </tex> . Докажем, что процедура корректна и для <tex> l_n = w + 1 </tex> .
 +
#:Заметим, что у слов каждой группы будет своя начальная буква, поэтому достаточно проверить префиксность кода для каждой группы. А это истинно по предположению индукции, где для каждой группы <tex> l_i \leqslant w </tex> .  
  
Отсюда следует, что <tex>\sum\limits_{i = 1}^{I} M_{C_i} = \sum\limits_{i = 1}^{I} 2^{-l_i} \le 1</tex>.
 
 
}}
 
}}
  
== Следствие ==
+
== Замечания ==
Можно обобщить неравенство Крафта для случаев, когда кодирующим алфавитом является k-ичный. В доказательстве изменятся некоторые пункты:
+
 
*отрезок <tex>[0;1]</tex> придется делить не на <tex>2</tex>, а на <tex>k</tex> равных частей;
+
Когда имеет место строгое неравенство? Легко заметить, что если любая концевая вершина дерева является кодовым словом, то <tex>K = 1</tex>. Строгое неравенство имеет место лишь в случае, когда некоторые из концевых вершин не используются. Однако, в случае двоичного кодового алфавита какая-нибудь концевая вершина не используется, то предыдущее решение оказывается лишним, и соответствующая цифра может быть удалена из каждого кодового слова, декодирование которого проходит через эту вершину. Таким образом, если имеет место строгое неравенство, то код неэффективен, но для двоичных деревьев очевидно, как можно его улучшить.
*соответственно неравенство примет вид: <tex>\sum\limits_{i = 1}^{I} k^{-l_i} \le 1 </tex>.
+
 
 +
Заметим еще раз, что теорема утверждает существование такого кода и ничего не говорит о конкретных кодах. Может существовать код, который удовлетворяет неравенству Крафта и тем не менее не является префиксным.
 +
 
  
== Ссылки ==
+
== См.также ==
*[http://ru.wikipedia.org/wiki/Неравенство_Крафта Неравенство Крафта — Википедия]
+
*[[Неравенство Макмиллана]]
*ftp://remotesensing.ru/InfoTheory_lec05.pdf
 
  
== Литература ==
+
== Источники информации ==
*А.Шень "ПРОГРАММИРОВАНИЕ теоремы и задачи".
+
*[http://ru.wikipedia.org/wiki/Неравенство_Крафта Википедия — Неравенство Крафта]
 +
*[http://books.sernam.ru/book_htc.php?id=35 Неравенство Крафта]
 +
*[https://xlinux.nist.gov/dads/HTML/kraftsinqlty.html Kraft's inequality]
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Алгоритмы сжатия]]
 
[[Категория: Алгоритмы сжатия]]

Текущая версия на 19:43, 4 сентября 2022

Рассматриваемое ниже неравенство Крафта показывает для каких длин кодовых слов существует префиксный код.

Теорема (неравенство Крафта):
Пусть у нас есть [math]n[/math] символов, кодовые слова которых имеют длины [math]l_1 \leqslant l_2 \leqslant \ldots \leqslant l_n [/math].

Тогда необходимое и достаточное условие существования префиксного кода в [math]r[/math]-ичном алфавите для данных символов, состоит в выполнении неравенства:

[math] \sum\limits_{i = 1}^{n} r ^{-l_i} \leqslant 1 [/math]
Доказательство:
[math]\triangleright[/math]
Иллюстрация к доказательству индукционного перехода

Необходимость:

Напомним, что префиксный код можно представить в виде [math]r[/math]-ичного корневого дерева, рёбра которого соответствуют символам алфавита, а листья соответствующим кодам. Неравенство Крафта будем доказывать по индукции.

Для простоты рассмотрим сначала случай двоичного алфавита, то есть [math]r = 2[/math].

База: Если максимальная длина пути на дереве равна [math]1[/math], то в дереве есть одно или два ребра длины [math]1[/math]. Таким образом, либо [math] \dfrac{1}{2} \leqslant 1 [/math] — для одного символа источника, либо [math] \dfrac{1}{2} + \dfrac{1}{2} \leqslant 1 [/math] — для двух символов источника.

Переход: Предположим далее, что неравенство Крафта справедливо для всех деревьев высоты меньше [math]n - 1[/math]. Докажем, что оно справедливо и для всех деревьев высоты меньше [math]n[/math]. Для данного дерева максимальной высоты [math]n[/math] ребра из первой вершины ведут к двум поддеревьям, высоты которых не превышают [math]n - 1[/math]; для этих поддеревьев имеем неравенства [math]K_1 \leqslant 1[/math] и [math]K_2 \leqslant 1[/math], где [math]K_1, K_2[/math] — значения соответствующих им сумм. Каждая длина [math]l_i[/math] в поддереве увеличивается на [math]1[/math], когда поддерево присоединяется к основному дереву, поэтому возникает дополнительный множитель [math]\dfrac{1}{2}[/math]. Таким образом, имеем [math]\dfrac{1}{2} K_1 + \dfrac{1}{2} K_2 \leqslant 1[/math].


В случае произвольного недвоичного основания [math]r[/math] имеется не более [math]r[/math] ребер, исходящих из каждой вершины, то есть не более [math]r[/math] поддеревьев; каждое из них присоединяется к основному дереву, давая дополнительный множитель [math]\dfrac{1}{r}[/math]. Отсюда снова следует утверждение теоремы.

Достаточность:

Пример разбиения на группы, при [math] r = 2[/math], символах a, b, c, где [math] l_a = 2, l_b = 2, l_c = 1[/math]
  1. Если некоторое [math] l_i = 0 [/math] , то [math] n = 1 [/math] . В таком случае пустая строка является искомым префиксным кодом. Далее все [math] l_i \geqslant 1 [/math] .
  2. Для доказательства корректности разделим длины [math] l_i [/math] на [math]r[/math] , возможно пустых, групп, внутри каждой из которых [math] \sum\limits r ^{-l_i} \leqslant \dfrac{1}{r} [/math] .
    Пусть у нас есть [math]n[/math] символов, кодовые слова имеют длины [math]l_1 \leqslant l_2 \leqslant \ldots \leqslant l_n [/math]. Давайте разделим данные символы на [math]r[/math] групп, внутри каждой из которых [math] \sum\limits r ^{-l_i} \leqslant \dfrac{1}{r} [/math] . Разделить символы на группы можно следующим жадным образом: брать [math] l_i [/math] в порядке увеличения индекса.
    Докажем, что в таком случае группа будет либо полностью укомплектована [math](\sum\limits r ^{-l_i} = \dfrac{1}{r})[/math], либо будут исчерпаны все возможные [math] l_i [/math] . Это следует из того, что при [math] l_i \geqslant 1 [/math] на [math]i[/math]-ом шаге либо группа уже укомплектована, либо ее остаток равен:
    [math] \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}}[/math]
    Так как группа не укомплектована, то числитель положителен. Если добавим [math] l_i [/math] в группу, то числитель уменьшится на [math]1[/math], где [math]l_i - l_j[/math] неотрицательно при [math] i \geqslant j [/math] , и [math] r \in \mathbb{N} [/math]. Следовательно числитель — натуральное число. Тогда, взяв [math] l_i [/math] в группу, мы не перепрыгнем через максимальное значение, то есть сумма группы [math] \leqslant \dfrac{1}{r} [/math] . А значит, создавая группы по данному алгоритму мы сможем построить [math]r[/math] групп, удовлетворяющих условию.
  3. Выберем для каждой группы свой начальный символ. Запуститим данную процедуру для каждой группы слов, предварительно обрезав первую букву.
  4. По индукции по величине [math] l_n [/math] докажем, что наш алгоритм корректен.
    База: При [math] l_n = 0 [/math] корректность процедуры очевидна.
    Переход: Допустим, что процедура корректна для [math] l_n = w [/math] . Докажем, что процедура корректна и для [math] l_n = w + 1 [/math] .
    Заметим, что у слов каждой группы будет своя начальная буква, поэтому достаточно проверить префиксность кода для каждой группы. А это истинно по предположению индукции, где для каждой группы [math] l_i \leqslant w [/math] .
[math]\triangleleft[/math]

Замечания

Когда имеет место строгое неравенство? Легко заметить, что если любая концевая вершина дерева является кодовым словом, то [math]K = 1[/math]. Строгое неравенство имеет место лишь в случае, когда некоторые из концевых вершин не используются. Однако, в случае двоичного кодового алфавита какая-нибудь концевая вершина не используется, то предыдущее решение оказывается лишним, и соответствующая цифра может быть удалена из каждого кодового слова, декодирование которого проходит через эту вершину. Таким образом, если имеет место строгое неравенство, то код неэффективен, но для двоичных деревьев очевидно, как можно его улучшить.

Заметим еще раз, что теорема утверждает существование такого кода и ничего не говорит о конкретных кодах. Может существовать код, который удовлетворяет неравенству Крафта и тем не менее не является префиксным.


См.также

Источники информации