Изменения

== Необходимые определения ==Пусть нам дан '''''алфавит''''', то есть конечное множество, элементы которого называются '''''символами''''' или '''''буквами''''' этого алфавита. '''''Кодом''''' для алфавита <tex>A</tex> называется функция (таблица) <tex>\alpha</tex>, которая для каждого символа <tex>a</tex> из <tex>A</tex> указывает двоичное слово <tex>\alpha(a)</tex>, называемое '''''кодовым словом''''', или просто '''''кодом''''' этого символа. (Двоичное слово - конечная последовательность нулей и единиц.) Не требуется, чтобы коды всех символов имели равные При необходимости построить префиксный код с большим числом кодовых слов заданной длиныпроверка существования такого кода может быть достаточно сложной. Хороший код должен позволять декодирование(восстановление последовательности символов по ее коду). Пусть фиксирован алфавит <tex>A</tex> Но неравенство Макмиллана даёт необходимое условие существования префиксных и код <tex>\alpha</tex> для этого алфавита. Для каждого слова <tex>P</tex> в алфавите <tex>A</tex> (то есть для любой конечной последовательности букв алфавита <tex>A</tex>) рассмотрим двоичное слово<tex>\alpha(P)</tex>любых [[Кодирование информации | однозначно декодируемых кодов]], которое получается, если записать подряд коды всех букв из <tex>P</tex> (без каких либо разделителей). Код <tex>\alpha</tex> называется '''''однозначным''''', если коды различных обладающих заданным набором длин кодовых слов различны: <tex>\alpha(P)\ne\alpha(P')</tex> при <tex>P\ne{P'}</tex>.== Неравенство Макмиллана ==

<center>[http://neerc.ifmo.ru/mediawiki/index.php/%D0%9D%D0%B5%D1%80%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE_%D0%9A%D1%80%D0%B0%D1%84%D1%82%D0%B0 Неравенство Крафта-Макмиллана] выполняется не только для любого префиксного кода, но и вообще для любого однозначного кода.</center><center> <tex> \sum\limits_{i = 1}^{I|A|} 2^{-l_i} \le leqslant 1 , </tex></center><center>(где <tex>|A| = I</tex> , а <tex>l_i</tex> {{---}} длины кодовых слов) выполняется для любого [[Кодирование информации | однозначно декодируемого кода.]]|proof=Пусть имеется [[Кодирование информации | однозначный код]] с <tex>k</centertex>}}''Примечание: Именно это доказал Макмилланкодовыми словами <tex>P_1,\dots, P_k</tex>. Необходимо доказать, Крафт доказал неравенство для префиксных кодовчто их длины <tex>n_i=|P_i|</tex> удовлетворяют неравенству Макмиллана.''

== Доказательство ==Есть разные способы решить эту задачу, но будет приведено простое Для удобства при кодировании вместо нулей и красивое, хотя и несколько загадочное, решение. <br />Пусть имеется однозначный код с единиц будем использовать <tex>ka</tex> кодовыми словами <tex>P_1,P_2, ..., P_k</tex>. Необходимо доказать, что их длины и <tex>n_i=|P_i|b</tex> удовлетворяют Неравенству Крафта-Макмилланасоответственно.

Вместо нулей Представим сумму всех слов и единиц будем использовать возведем эту сумму в степень <tex>aN \in \mathbb N</tex> и : <tex>b(P_1+P_2+\dots+P_k)^N</tex> (из чего составлять коды разницы нет). Запишем формально сумму всех Раскроем скобки, подразумевая под умножением конкатенацию двух слов. По определению однозначности никакое слово не может быть получено двумя способами при соединении кодовых слов как алгебраическое выражение, следовательно все слова должны получиться разными.

Вот пример для [[Кодирование информации | однозначного кода]] со словами <centertex>a,ab,bb</tex>P_1и <tex>N=2</tex>:<tex>(a+P_2ab+...P_kbb)^2</tex><tex>=(a+ab+bb)\times{(a+ab+bb)}=aa+aab+abb+aba+abab+abbb+bba+bbab+bbbb.</centertex>Все получившиеся слагаемые различны (соответствует определению однозначности).

(многочлен от Подставим <tex>a=b= </tex> и <texdpi = 150>b\frac{1}{2}</tex>, в котором одночлены записаны как произведения переменных неравенство. Для кодового слова <tex>aP_i</tex> и длины <tex>b{n_i}</tex>, без возведения в степень). Теперь (ещё боле странное на первый взгляд действие) возведём это в степень получим <tex>N2^{-n_i}</tex>(произвольное натуральное число) и раскроем скобки, сохраняя порядок переменных(не собирая вместе одинаковые переменные) в одночленах. В левой части получится выражение из неравенства Макмиллана: <center><tex>(P_12^{-n_1}+P_22^{-n_2}+\dots+...P_k2^{-n_k})^N=</tex> сумма одночленов.</center> Например, для кода со словами Всего имеется не более <tex>0,10,112^l</tex> (которые теперь записываются как слагаемых длины <tex>a,ba,bbl</tex>) и для равных <tex>N=2</tex> получаем <center><tex>(a+ba+bb)^2=(a+ba+bb)(a+ba+bb)=aa+aba+abb+baa+baba+babb+bba+bbba+bbbb.{-l}</tex></center> В этом примере все одночлены , следовательно слагаемые данной длины в правой части различны (если сумме не переставлять переменные)превосходят единицы, и это а правая часть не случайнопревосходит максимальной длины слагаемых: так будет для любого однозначного кода. В самом деле, по определению однозначности никакое слово не может быть получено двумя способами при соединении кодовых слов. Теперь подставим <tex>a=b=N\fractimes{1}{2\max(n_i)}</tex> в наше неравенство(если оно верно для букв. Получаем, то оно верно и для любых их числовых значений). Слева получится  <center>что <tex>(2^{-n_1}+2^{-n_2}+...\dots+2^{-n_in_k})^N\leqslant N\times{\max(n_i)}</tex>верно для любого <tex>N</centertex>. Так как показательная функция растет быстрее линейной, то при основании (сумма <tex>2^{-n_i}</tex>) большем единицы неравенство нарушается. Поэтому, для [[Кодирование информации | однозначного кода]] выполняется неравенство Макмиллана.}}

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

<center><tex>(2^== Источники информации ==*[http://ru.wikipedia.org/wiki/Неравенство_Крафта_—_Макмиллана Википедия — Неравенство Макмиллана]*''Шень А. Х.'' Программирование: теоремы и задачи. {{-n_1--}+2^{-n_2}+М.: МЦНМО, 2011.С.206 - 210.+2^{ISBN 978-5-94057-696-n_i})^N<Nmax(n_i)</tex></center>9

[[Категория: Дискретная математика и это верно при любом <tex>N</tex>. Если основание степени в левой степени больше единицы, то при больших <tex>N</tex> это неравенство нарушится (показательная функция растет быстрее линейной). Поэтому, для однозначного кода выполняется неравенство Крафта-Макмиллана. Что и требовалось доказать.== Ссылки == алгоритмы]][[Неравенство КрафтаКатегория: Алгоритмы сжатия]]== Литература ==А. Шень "Программирование: теоремы и задачи" (Издание четвёртое, Москва, Издательство МЦНМО, 2011)