Неравенство Крафта
Версия от 17:36, 13 января 2015; 194.85.161.2 (обсуждение)
Предварительные определения
Определение: |
Пусть заданы два произвольных конечных множества, которые называются, соответственно, кодируемым алфавитом и кодирующим алфавитом. Их элементы называются символами, а строки (последовательности конечной длины) символов — словами. Длина слова — это число символов, из которого оно состоит. |
В качестве кодирующего алфавита часто рассматривается множество
— так называемый двоичный или бинарный алфавит.
Определение: |
Кодом для алфавита | называется функция , которая для каждого символа из указывает слово , кодирующее этот символ.
Определение: |
Префиксным кодом называется код, в котором ни одно из кодовых слов не является префиксом никакого другого кодового слова. |
Неравенство Крафта
Теорема: |
Для любого префиксного кода , отображающего произвольный алфавит на двоичный алфавит , длины кодовых слов должны удовлетворять неравенству:
|
Доказательство: |
Рассмотрим отрезок на числовой прямой.Разделим его пополам, причем левую половину обозначим , а правую .Затем поделим пополам и обозначим его левую половину , а правую , и, проделав то же самое с , получим , а левую .Будем выполнять эти действия, пока длина индекса полученного отрезка не превосходит .Заметим, что:
Рассмотрим префиксный код : так как ни одно из кодовых слов не является префиксом никакого другого кодового слова, то никакие два отрезка не пересекаются.Если на отрезке Отсюда следует, что выбрать некоторое количество непересекающихся отрезков, то очевидно, что сумма их длин не превзойдет , то есть . . |
Следствие
Можно обобщить неравенство Крафта для случаев, когда кодирующим алфавитом является k-ичный. В доказательстве изменятся некоторые пункты:
- отрезок придется делить не на , а на равных частей;
- соответственно неравенство примет вид: .
Ссылки
Литература
- А. Шень Программирование: теоремы и задачи. — М.: МЦНМО, 2007. С. 208. ISBN 978-5-94057-310-4