Неравенство Макмиллана — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «== Необходимые определения == Пусть нам дан '''''алфавит''''', то есть конечное множество, элеме...»)
 
 
(не показаны 43 промежуточные версии 3 участников)
Строка 1: Строка 1:
== Необходимые определения ==
+
При необходимости построить префиксный код с большим числом кодовых слов заданной длины проверка существования такого кода может быть достаточно сложной. Но неравенство Макмиллана даёт необходимое условие существования префиксных и любых [[Кодирование информации | однозначно декодируемых кодов]], обладающих заданным набором длин кодовых слов.
Пусть нам дан '''''алфавит''''', то есть конечное множество, элементы которого называются '''''символами''''' или '''''буквами''''' этого алфавита. '''''Кодом''''' для алфавита <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>.
 
== Неравенство Макмиллана ==
 
 
{{Теорема
 
{{Теорема
 +
|about=Неравенство Макмиллана (англ. McMillan's inequality)
 
|statement=
 
|statement=
<center>
+
<tex> \sum\limits_{i = 1}^{|A|} 2^{-l_i} \leqslant 1</tex> (где <tex>l_i</tex> {{---}} длины кодовых слов) выполняется для любого [[Кодирование информации | однозначно декодируемого кода.]]
[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 Неравенство Крафта-Макмиллана] выполняется не только для любого префиксного кода, но и вообще для любого однозначного кода.
+
|proof=
</center>
+
Пусть имеется [[Кодирование информации | однозначный код]] с <tex>k</tex> кодовыми словами <tex>P_1,\dots, P_k</tex>. Необходимо доказать, что их длины <tex>n_i=|P_i|</tex> удовлетворяют неравенству Макмиллана.
}}
 
''Примечание: Именно это доказал Макмиллан, Крафт доказал неравенство для префиксных кодов.''
 
== Доказательство ==
 
Есть разные способы решить эту задачу, но будет приведено простое и красивое, хотя и несколько загадочное, решение. <br />
 
Пусть имеется однозначный код с <tex>k</tex> кодовыми словами <tex>P_1,P_2, ..., P_k</tex>. Необходимо доказать, что их длины <tex>n_i=|P_i|</tex> удовлетворяют Неравенству Крафта-Макмиллана.
 
  
Вместо нулей и единиц будем использовать <tex>a</tex> и <tex>b</tex> (из чего составлять коды разницы нет). Запишем формально сумму всех кодовых слов как алгебраическое выражение
+
Для удобства при кодировании вместо нулей и единиц будем использовать <tex>a</tex> и <tex>b</tex> соответственно.
  
<center><tex>P_1+P_2+...P_k</tex></center>
+
Представим сумму всех слов и возведем эту сумму в степень <tex>N \in \mathbb N</tex>: <tex>(P_1+P_2+\dots+P_k)^N</tex>. Раскроем скобки, подразумевая под умножением конкатенацию двух слов. По определению однозначности никакое слово не может быть получено двумя способами при соединении кодовых слов, следовательно все слова должны получиться разными.
  
(многочлен от <tex>a</tex> и <tex>b</tex>, в котором одночлены записаны как произведения переменных <tex>a</tex> и <tex>b</tex>, без возведения в степень). Теперь (ещё боле странное на первый взгляд действие) возведём это в степень <tex>N</tex>(произвольное натуральное число) и раскроем скобки, сохраняя порядок переменных(не собирая вместе одинаковые переменные) в одночленах:
+
Вот пример для [[Кодирование информации | однозначного кода]] со словами <tex>a,ab,bb</tex> и <tex>N=2</tex>:
 +
<tex>(a+ab+bb)^2</tex><tex>=(a+ab+bb)\times{(a+ab+bb)}=aa+aab+abb+aba+abab+abbb+bba+bbab+bbbb.</tex> Все получившиеся слагаемые различны (соответствует определению однозначности).
  
<center><tex>(P_1+P_2+...P_k)^N=</tex> сумма одночленов.</center>
+
Подставим <tex>a=b= </tex> <tex dpi = 150> \frac{1}{2}</tex> в неравенство. Для кодового слова <tex>P_i</tex> длины <tex>{n_i}</tex> получим <tex>2^{-n_i}</tex>. В левой части получится выражение из неравенства Макмиллана: <tex>(2^{-n_1}+2^{-n_2}+\dots+2^{-n_k})^N</tex>. Всего имеется не более <tex>2^l</tex> слагаемых длины <tex>l</tex> равных <tex>2^{-l}</tex>, следовательно слагаемые данной длины в сумме не превосходят единицы, а правая часть не превосходит максимальной длины слагаемых: <tex>N\times{\max(n_i)}</tex>. Получаем, что <tex>(2^{-n_1}+2^{-n_2}+\dots+2^{-n_k})^N \leqslant N\times{\max(n_i)}</tex> верно для любого <tex>N</tex>. Так как показательная функция растет быстрее линейной, то при основании (сумма <tex>2^{-n_i}</tex>) большем единицы неравенство нарушается. Поэтому, для [[Кодирование информации | однозначного кода]] выполняется неравенство Макмиллана.
 
+
}}
Например, для кода со словами <tex>0,10,11</tex> (которые теперь записываются как <tex>a,ba,bb</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.</tex></center>
 
 
 
В этом примере все одночлены в правой части различны (если не переставлять переменные), и это не случайно: так будет для любого однозначного кода. В самом деле, по определению однозначности никакое слово не может быть получено двумя способами при соединении кодовых слов.
 
 
 
Теперь подставим <tex>a=b=\frac{1}{2}</tex> в наше неравенство(если оно верно для букв, то оно верно и для любых их числовых значений). Слева получится
 
 
 
<center><tex>(2^{-n_1}+2^{-n_2}+...+2^{-n_i})^N</tex></center>
 
  
(в скобке как раза выражение из неравенства Крафта-Макмиллана). Правую часть мы оценим сверху, сгруппировав слова пол длинам: имеется не более <tex>2^l</tex> слагаемых длины <tex>l</tex>, каждое из которых равно <tex>2^{-l}</tex>, и потому слагаемые данной длины в сумме не превосходят единицы, а правая часть не превосходит максимальной длины слагаемых, то есть <tex>Nmax(n_i)</tex>. Итак, получаем, что
+
== См.также ==
 +
*[[Неравенство Крафта]]
  
<center><tex>(2^{-n_1}+2^{-n_2}+...+2^{-n_i})^N<Nmax(n_i)</tex></center>
+
== Источники информации ==
 +
*[http://ru.wikipedia.org/wiki/Неравенство_Крафта_—_Макмиллана Википедия — Неравенство Макмиллана]
 +
*''Шень А. Х.'' Программирование: теоремы и задачи. {{---}} М.: МЦНМО, 2011. С. 206 - 210. ISBN 978-5-94057-696-9
  
и это верно при любом <tex>N</tex>. Если основание степени в левой степени больше единицы, то при больших <tex>N</tex> это неравенство нарушится (показательная функция растет быстрее линейной). Поэтому, для однозначного кода выполняется неравенство Крафта-Макмиллана. Что и требовалось доказать.
+
[[Категория: Дискретная математика и алгоритмы]]
== Ссылки ==
+
[[Категория: Алгоритмы сжатия]]
[[Неравенство Крафта]]
 
== Литература ==
 
А. Шень "Программирование: теоремы и задачи" (Издание четвёртое, Москва, Издательство МЦНМО, 2011)
 

Текущая версия на 15:46, 23 декабря 2017

При необходимости построить префиксный код с большим числом кодовых слов заданной длины проверка существования такого кода может быть достаточно сложной. Но неравенство Макмиллана даёт необходимое условие существования префиксных и любых однозначно декодируемых кодов, обладающих заданным набором длин кодовых слов.

Теорема (Неравенство Макмиллана (англ. McMillan's inequality)):
[math] \sum\limits_{i = 1}^{|A|} 2^{-l_i} \leqslant 1[/math] (где [math]l_i[/math] — длины кодовых слов) выполняется для любого однозначно декодируемого кода.
Доказательство:
[math]\triangleright[/math]

Пусть имеется однозначный код с [math]k[/math] кодовыми словами [math]P_1,\dots, P_k[/math]. Необходимо доказать, что их длины [math]n_i=|P_i|[/math] удовлетворяют неравенству Макмиллана.

Для удобства при кодировании вместо нулей и единиц будем использовать [math]a[/math] и [math]b[/math] соответственно.

Представим сумму всех слов и возведем эту сумму в степень [math]N \in \mathbb N[/math]: [math](P_1+P_2+\dots+P_k)^N[/math]. Раскроем скобки, подразумевая под умножением конкатенацию двух слов. По определению однозначности никакое слово не может быть получено двумя способами при соединении кодовых слов, следовательно все слова должны получиться разными.

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

Подставим [math]a=b= [/math] [math] \frac{1}{2}[/math] в неравенство. Для кодового слова [math]P_i[/math] длины [math]{n_i}[/math] получим [math]2^{-n_i}[/math]. В левой части получится выражение из неравенства Макмиллана: [math](2^{-n_1}+2^{-n_2}+\dots+2^{-n_k})^N[/math]. Всего имеется не более [math]2^l[/math] слагаемых длины [math]l[/math] равных [math]2^{-l}[/math], следовательно слагаемые данной длины в сумме не превосходят единицы, а правая часть не превосходит максимальной длины слагаемых: [math]N\times{\max(n_i)}[/math]. Получаем, что [math](2^{-n_1}+2^{-n_2}+\dots+2^{-n_k})^N \leqslant N\times{\max(n_i)}[/math] верно для любого [math]N[/math]. Так как показательная функция растет быстрее линейной, то при основании (сумма [math]2^{-n_i}[/math]) большем единицы неравенство нарушается. Поэтому, для однозначного кода выполняется неравенство Макмиллана.
[math]\triangleleft[/math]

См.также[править]

Источники информации[править]