Неравенство МакМилана

Необходимые определения

Пусть нам дан алфавит, то есть конечное множество, элементы которого называются символами или буквами этого алфавита. Кодом для алфавита [math]A[/math] называется функция (таблица) [math]\alpha[/math], которая для каждого символа [math]a[/math] из [math]A[/math] указывает двоичное слово [math]\alpha(a)[/math], называемое кодовым словом, или просто кодом этого символа. (Двоичное слово - конечная последовательность нулей и единиц.) Не требуется, чтобы коды всех символов имели равные длины.

Хороший код должен позволять декодирование(восстановление последовательности символов по ее коду). Пусть фиксирован алфавит [math]A[/math] и код [math]\alpha[/math] для этого алфавита. Для каждого слова [math]P[/math] в алфавите [math]A[/math] (то есть для любой конечной последовательности букв алфавита [math]A[/math]) рассмотрим двоичное слово[math]\alpha(P)[/math], которое получается, если записать подряд коды всех букв из [math]P[/math] (без каких либо разделителей). Код [math]\alpha[/math] называется однозначным, если коды различных слов различны: [math]\alpha(P)\ne\alpha(P')[/math] при [math]P\ne{P'}[/math].

Неравенство Макмиллана

Теорема:

Неравенство Крафта—Макмиллана выполняется не только для любого префиксного кода, но и вообще для любого однозначного кода.

Примечание: Именно это доказал Макмиллан, Крафт доказал неравенство для префиксных кодов.

Доказательство

Есть разные способы решить эту задачу, но будет приведено простое и красивое, хотя и несколько загадочное, решение.
Пусть имеется однозначный код с [math]k[/math] кодовыми словами [math]P_1,P_2, ..., P_k[/math]. Необходимо доказать, что их длины [math]n_i=|P_i|[/math] удовлетворяют Неравенству Крафта—Макмиллана.

Вместо нулей и единиц будем использовать [math]a[/math] и [math]b[/math] (из чего составлять коды разницы нет). Запишем формально сумму всех кодовых слов как алгебраическое выражение

[math]P_1+P_2+...P_k[/math]

(многочлен от [math]a[/math] и [math]b[/math], в котором одночлены записаны как произведения переменных [math]a[/math] и [math]b[/math], без возведения в степень). Теперь (ещё боле странное на первый взгляд действие) возведём это в степень [math]N[/math](произвольное натуральное число) и раскроем скобки, сохраняя порядок переменных(не собирая вместе одинаковые переменные) в одночленах:

[math](P_1+P_2+...P_k)^N=[/math] сумма одночленов.

Например, для кода со словами [math]0,10,11[/math] (которые теперь записываются как [math]a,ba,bb[/math]) и для [math]N=2[/math] получаем

[math](a+ba+bb)^2=(a+ba+bb)(a+ba+bb)=aa+aba+abb+baa+baba+babb+bba+bbba+bbbb.[/math]

В этом примере все одночлены в правой части различны (если не переставлять переменные), и это не случайно: так будет для любого однозначного кода. В самом деле, по определению однозначности никакое слово не может быть получено двумя способами при соединении кодовых слов.

Теперь подставим [math]a=b=\frac{1}{2}[/math] в наше неравенство(если оно верно для букв, то оно верно и для любых их числовых значений). Слева получится

[math](2^{-n_1}+2^{-n_2}+...+2^{-n_i})^N[/math]

(в скобке как раза выражение из неравенства Крафта—Макмиллана). Правую часть мы оценим сверху, сгруппировав слова пол длинам: имеется не более [math]2^l[/math] слагаемых длины [math]l[/math], каждое из которых равно [math]2^{-l}[/math], и потому слагаемые данной длины в сумме не превосходят единицы, а правая часть не превосходит максимальной длины слагаемых, то есть [math]Nmax(n_i)[/math]. Итак, получаем, что

[math](2^{-n_1}+2^{-n_2}+...+2^{-n_i})^N\lt Nmax(n_i)[/math]

и это верно при любом [math]N[/math]. Если основание степени в левой степени больше единицы, то при больших [math]N[/math] это неравенство нарушится (показательная функция растет быстрее линейной). Поэтому, для однозначного кода выполняется неравенство Крафта-Макмиллана. Что и требовалось доказать.

Ссылки

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

Литература

А. Шень "Программирование: теоремы и задачи" (Издание четвёртое, Москва, Издательство МЦНМО, 2011)