1632
правки
Изменения
м
== Необходимые определения ==Пусть нам дан '''''алфавит''''', то есть конечное множество, элементы которого называются '''''символами''''' или '''''буквами''''' этого алфавита. '''''Кодом''''' для алфавита <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>.== Неравенство Макмиллана ==
Вместо Для удобства при кодировании вместо нулей и единиц будем использовать <tex>a</tex> и <tex>b</tex> (из чего составлять коды разницы нет)соответственно. Запишем формально сумму всех кодовых слов как алгебраическое выражение
(многочлен от Вот пример для [[Кодирование информации | однозначного кода]] со словами <tex>a,ab,bb</tex> и <tex>bN=2</tex>, в котором одночлены записаны как произведения переменных :<tex>(a+ab+bb)^2</tex> и <tex>b</tex>, без возведения в степень=(a+ab+bb). Теперь \times{(ещё боле странное на первый взгляд действиеa+ab+bb) возведём это в степень <tex>N}=aa+aab+abb+aba+abab+abbb+bba+bbab+bbbb.</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
rollbackEdits.php mass rollback
{{Теорема
|about=Неравенство Макмиллана (англ. McMillan's inequality)
|statement=
<centertex>[http:\sum\limits_{i = 1}^{|A|} 2^{-l_i} \leqslant 1</tex> (где <tex>l_i</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 Неравенство Крафтаtex> {{---Макмиллана] }} длины кодовых слов) выполняется не только для любого префиксного кода, но и вообще для любого однозначного [[Кодирование информации | однозначно декодируемого кода.]]</center>}}''Примечание: Именно это доказал Макмиллан, Крафт доказал неравенство для префиксных кодов.''== Доказательство =|proof=Есть разные способы решить эту задачу, но будет приведено простое и красивое, хотя и несколько загадочное, решение. <br />Пусть имеется [[Кодирование информации | однозначный код ]] с <tex>k</tex> кодовыми словами <tex>P_1,P_2, ...\dots, P_k</tex>. Необходимо доказать, что их длины <tex>n_i=|P_i|</tex> удовлетворяют Неравенству Крафта-неравенству Макмиллана.
Представим сумму всех слов и возведем эту сумму в степень <centertex>N \in \mathbb N</tex>: <tex>(P_1+P_2+...\dots+P_k)^N</tex></center>. Раскроем скобки, подразумевая под умножением конкатенацию двух слов. По определению однозначности никакое слово не может быть получено двумя способами при соединении кодовых слов, следовательно все слова должны получиться разными.
Подставим <centertex>a=b= </tex>(P_1+P_2+...P_k)^N<tex dpi =150> \frac{1}{2}</tex> сумма одночленовв неравенство.</center> Например, для кода со словами Для кодового слова <tex>0,10,11P_i</tex> (которые теперь записываются как длины <tex>a,ba,bb{n_i}</tex>) и для получим <tex>N=2^{-n_i}</tex> получаем <center>. В левой части получится выражение из неравенства Макмиллана: <tex>(a2^{-n_1}+ba+bb)2^2=(a{-n_2}+ba\dots+bb2^{-n_k})(a+ba+bb)=aa+aba+abb+baa+baba+babb+bba+bbba+bbbb^N</tex>.Всего имеется не более <tex>2^l</tex> слагаемых длины <tex>l</tex>равных <tex>2^{-l}</centertex> В этом примере все одночлены , следовательно слагаемые данной длины в правой части различны (если сумме не переставлять переменные)превосходят единицы, и это а правая часть не случайнопревосходит максимальной длины слагаемых: так будет для любого однозначного кода. В самом деле, по определению однозначности никакое слово не может быть получено двумя способами при соединении кодовых слов. Теперь подставим <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</tex>. Так как показательная функция растет быстрее линейной, то при основании (сумма <tex>2^{-n_i}</centertex>) большем единицы неравенство нарушается. Поэтому, для [[Кодирование информации | однозначного кода]] выполняется неравенство Макмиллана.}}
[[Категория: Дискретная математика и это верно при любом <tex>N</tex>. Если основание степени в левой степени больше единицы, то при больших <tex>N</tex> это неравенство нарушится (показательная функция растет быстрее линейной). Поэтому, для однозначного кода выполняется неравенство Крафта-Макмиллана. Что и требовалось доказать.== Ссылки == алгоритмы]][[Неравенство КрафтаКатегория: Алгоритмы сжатия]]== Литература ==А. Шень "Программирование: теоремы и задачи" (Издание четвёртое, Москва, Издательство МЦНМО, 2011)