Неравенство Крафта

Материал из Викиконспекты
Перейти к: навигация, поиск

Предварительные определения

Определение:
Пусть заданы два произвольных конечных множества, которые называются, соответственно, кодируемым алфавитом и кодирующим алфавитом. Их элементы называются символами, а строки (последовательности конечной длины) символов — словами. Длина слова — это число символов, из которого оно состоит.

В качестве кодирующего алфавита часто рассматривается множество [math]\{0, 1\}[/math] — так называемый двоичный или бинарный алфавит.


Определение:
Кодом для алфавита [math]A[/math] называется функция [math]C[/math], которая для каждого символа [math]x[/math] из [math]A[/math] указывает слово [math]C(x)[/math], кодирующее этот символ.


Определение:
Префиксным кодом называется код, в котором ни одно из кодовых слов не является префиксом никакого другого кодового слова.


Неравенство Крафта

Теорема:
Для любого префиксного кода [math]C[/math], отображающего произвольный алфавит [math]A[/math] на двоичный алфавит [math] \{0,1\} [/math] , длины кодовых слов должны удовлетворять неравенству:
[math] \sum\limits_{i = 1}^{I} 2^{-l_i} \leqslant 1 , [/math]
где [math]|A| = I[/math] , а [math]l_i[/math] — длины кодовых слов.
Доказательство:
[math]\triangleright[/math]

Рассмотрим отрезок [math][0;1][/math] на числовой прямой.

Разделим его пополам, причем левую половину обозначим [math]M_0[/math], а правую [math]M_1[/math].

Затем поделим [math]M_0[/math] пополам и обозначим его левую половину [math]M_{00}[/math], а правую [math]M_{01}[/math], и, проделав то же самое с [math]M_1[/math], получим [math]M_{10}[/math], а левую [math]M_{11}[/math].

Будем выполнять эти действия, пока длина индекса полученного отрезка [math]M_j[/math] не превосходит [math]max(l_1, l_2,\ldots,l_I)[/math].

Заметим, что:

  • любому кодовому слову [math]C_j[/math] сопоставлен свой отрезок [math]M_{C_j}[/math] (Например, кодовому слову [math]1011[/math] соответствует отрезок [math]M_{1011}[/math]);
  • длина отрезка [math]M_{C_i}[/math] равна [math]2^{-l_i}[/math] (Например, [math]M_0[/math] имеет длину [math]\frac12[/math], а [math]M_{00}[/math] соответственно [math]\frac14[/math]);
  • Если кодовое слово [math]x[/math] является префиксом кодового слова [math]y[/math], то отрезок [math]M_x[/math] содержит [math]M_y[/math] (Например, кодовое слово [math]01[/math] является префиксом [math]0111[/math], а отрезок[math]M_{01}[/math] содержит [math]M_{0111}[/math], это его самая правая четверть);

Рассмотрим префиксный код [math]C[/math]: так как ни одно из кодовых слов не является префиксом никакого другого кодового слова, то никакие два отрезка не пересекаются.

Если на отрезке [math][0;1][/math] выбрать некоторое количество непересекающихся отрезков, то очевидно, что сумма их длин не превзойдет [math]1[/math], то есть [math] \sum\limits_{i = 1}^{I} M_{C_i} \leqslant 1[/math].

Отсюда следует, что [math]\sum\limits_{i = 1}^{I} M_{C_i} = \sum\limits_{i = 1}^{I} 2^{-l_i} \leqslant 1[/math].
[math]\triangleleft[/math]

Следствие

Можно обобщить неравенство Крафта для случаев, когда кодирующим алфавитом является k-ичный. В доказательстве изменятся некоторые пункты:

  • отрезок [math][0;1][/math] придется делить не на [math]2[/math], а на [math]k[/math] равных частей;
  • соответственно неравенство примет вид: [math]\sum\limits_{i = 1}^{I} k^{-l_i} \leqslant 1 [/math].

Ссылки

Литература

  • А. Шень Программирование: теоремы и задачи. — М.: МЦНМО, 2007. С. 208. ISBN 978-5-94057-310-4