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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
(правки замечаний)
Строка 1: Строка 1:
  
Рассматриваемое ниже неравенство Крафта показывает, для каких длин кодовых слов существует префиксный код, но приведенное ниже доказательство не является конструктивным.
+
Рассматриваемое ниже неравенство Крафта показывает для каких длин кодовых слов существует префиксный код.
 +
 
 
{{Теорема
 
{{Теорема
 
|about=неравенство Крафта  
 
|about=неравенство Крафта  
 
|statement=
 
|statement=
  Необходимое и достаточное условие существования префиксного кода в <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>, состоит в выполнении неравенства:
+
  Пусть <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>.
 +
 
 +
Тогда необходимое и достаточное условие существования префиксного кода в <tex>r</tex>-ичном алфавите для символов из <tex>\Sigma</tex>, состоит в выполнении неравенства:
  
 
<center><tex> \sum\limits_{i = 1}^{n} r ^{-l_i} \leqslant 1 </tex></center>
 
<center><tex> \sum\limits_{i = 1}^{n} r ^{-l_i} \leqslant 1 </tex></center>
Строка 11: Строка 14:
  
 
[[file:Treeforkraft.jpg|thumb|250px|Иллюстрация к доказательству индукционного перехода]]
 
[[file:Treeforkraft.jpg|thumb|250px|Иллюстрация к доказательству индукционного перехода]]
Неравенство Крафта легко доказать с помощью дерева декодирования, существование которого следует из существования префиксного кода. Будем рассуждать по [[Математическая индукция|индукции]].  
+
Напомним, что префиксный код можно представить в виде <tex>r</tex>-ичного корневого дерева, рёбра которого соответствуют символам алфавита, а листья соответствующим кодам. Неравенство Крафта будем доказывать по [[Математическая индукция|индукции]].  
 +
 
 +
'''Необходимость:'''
  
Для простоты рассмотрим сначала случай двоичного алфавита, то есть <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> — для двух символов источника.  
+
Для простоты рассмотрим сначала случай двоичного алфавита, то есть <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> — для двух символов источника.
 +
 
 +
Предположим далее, что неравенство Крафта справедливо для всех деревьев высоты меньше <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>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>r</tex> имеется не более <tex>r</tex> ребер, исходящих из каждой вершины, то есть не более <tex>r</tex> поддеревьев; каждое из них присоединяется к основному дереву, давая дополнительный множитель <tex>\dfrac{1}{r}</tex>. Отсюда снова следует утверждение теоремы.
 
В случае произвольного недвоичного основания <tex>r</tex> имеется не более <tex>r</tex> ребер, исходящих из каждой вершины, то есть не более <tex>r</tex> поддеревьев; каждое из них присоединяется к основному дереву, давая дополнительный множитель <tex>\dfrac{1}{r}</tex>. Отсюда снова следует утверждение теоремы.
 +
 +
'''Достаточность:'''
 +
 +
Для доказательства достаточности опишем рекурсивную процедуру, которая строит код для данного набора длин <tex> l_i </tex>, удовлетворяющих неравенству <tex> \sum\limits_{i = 1}^{n} r ^{-l_i} \leqslant 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>. Затем нужно запустить данную процедуру для каждой группы слов, предварительно обрезав первую букву.
  
 
}}
 
}}

Версия 18:44, 31 декабря 2017

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

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

Тогда необходимое и достаточное условие существования префиксного кода в [math]r[/math]-ичном алфавите для символов из [math]\Sigma[/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] l_i [/math], удовлетворяющих неравенству [math] \sum\limits_{i = 1}^{n} r ^{-l_i} \leqslant 1 [/math].

Нужно разделить длины [math] l_i [/math] на [math]r[/math] групп, внутри каждой из которых [math] \sum\limits r ^{-l_i} \leqslant \dfrac{1}{r} [/math]. У всех слов из слов из одной группы будет одна и та же начальная буква. Разделить длины на группы можно следующим жадным образом: брать [math] l_i [/math] в порядке увеличения индекса. Несложно понять, что в таком случае группа будет либо полностью укомплектована, либо будут исчерпаны все возможные [math] l_i [/math]. Затем нужно запустить данную процедуру для каждой группы слов, предварительно обрезав первую букву.
[math]\triangleleft[/math]

Замечания

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

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


См.также

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