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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (косметическая правка текста)
м
Строка 4: Строка 4:
 
|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>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>, состоит в выполнении неравенства:
  
 
<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>
Строка 13: Строка 14:
 
Неравенство Крафта легко доказать с помощью дерева декодирования, существование которого следует из существования префиксного кода. Будем рассуждать по [[Математическая индукция|индукции]].  
 
Неравенство Крафта легко доказать с помощью дерева декодирования, существование которого следует из существования префиксного кода. Будем рассуждать по [[Математическая индукция|индукции]].  
  
Для простоты рассмотрим сначала случай двоичного [[Основные определения, связанные со строками|алфавита]], то есть <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</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>.

Версия 22:28, 29 декабря 2017

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

Теорема (неравенство Крафта):
Необходимое и достаточное условие существования префиксного кода в [math]r[/math]-ичном дереве для источника с алфавитом
[math]S[/math] из [math]n[/math] символов [math]s_i[/math], где  [math]i\in \left [ 1, n \right ][/math], кодовые слова которого имеют длины [math]l_1 \leqslant l_2 \leqslant \ldots \leqslant l_n [/math], состоит в выполнении неравенства:
[math] \sum\limits_{i = 1}^{n} r ^{-l_i} \leqslant 1 [/math]
Доказательство:
[math]\triangleright[/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[/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]\triangleleft[/math]

Замечания

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

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


См.также

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