Новиков Ф.А. Дискретная математика для программистов (860615), страница 40
Текст из файла (страница 40)
@jt = • k = I k\/tе l..k(it=jt),то есть любое слово, составленное из элементарных кодов, единственным образом разлагается на элементарные коды. Алфавитное кодирование с разделимойсхемой допускает декодирование.2116.1. Алфавитное кодированиеЕсли таблица кодов содержит одинаковые элементарные коды, то есть если3 i,j( i ^ j к Pi = /3j),где (3i,[3j е V, то схема заведоморассматриваются, то естьне является разделимой.
Такие схемы далее неV i ^ j ( f t , 0jEV6.1.3. Префиксные схемыСхема сг называется префиксной, если элементарный код одной буквы не является префиксом элементарного кода другой буквы:^3Pi,PjeV,peB*ТЕОРЕМА( i ^ j k Pi =PjP).Префиксная схема является разделимой.ДОКАЗАТЕЛЬСТВОО Т противного. Пусть кодирование с префиксной схемой а пеявляется разделимым. Тогда существует такое слово Р е F(T(A*), чтоp = ph...pik=ph .. .Pj, k 3t (Ve < t {0i. = Pja k pit фПоскольку pit... pik = P j t .
. . Pji, значит, 3/3' (pit =противоречит тому, что схема префиксная.PjtP'V pjt =pjt)).PitP'),но это•ЗАМЕЧАНИЕСвойство быть префиксной достаточно, но не необходимо для разделимости схемы.ПримерРазделимая, но не префиксная схема:А = {а,Ь},В={0,1},<т = (а-> 0, ft-+01).6.1.4. Неравенство МакмилланаЧтобы схема алфавитного кодирования была разделимой, необходимо, чтобыдлины элементарных кодов удовлетворяли определённому соотношению, известному как неравенство Макмиллана.ТЕОРЕМА 1Если схема а = (ац —>празделима, то1где h'. =\Pi\.212Глава 6. Кодирование 212ДОКАЗАТЕЛЬСТВООбозначим I: = max k. Рассмотрим некоторую к-ю степень лег£1..пвой части неравенства/т»\)—иЕ2<г=1fc\Раскрывая скобки, имеем суммугде i i , . . . , -ifc — различные наборы номеров элементарных кодов.
Обозначим черезv(k, t) количество входящих в эту сумму слагаемых вида 1/2*, где t = +.. .+l-ik.Для некоторых t может быть, что и(к, t) = 0. Приводя подобные, имеем суммуklEt=iu{k,t)2* 'Каждому слагаемому вида) - 1 можно сопоставить код (слово в алфавите В) вида fax • • • (3ik- Это слово состоит из к элементарных кодов и имеетдлину t.Таким образом, v(k,t) — это число некоторых слов вида /3ix ...Pik, таких, что| Ai ... Pik \ = t.
В силу разделимости схемы i/(/с, t) ^ 2Ь, в противном случае заведомо существовали бы два одинаковых слова. . . (3ik =. . . (3jk, допускающихразличное разложение. Имеем:t=1Следовательно, Vfct=l^и значит, Vк ^ ^ 2~li ^ tyki^J, откудаn'i=l^ lim \fkl = 1.к—>oo•Неравенство Макмиллаиа является не только необходимым, но и в некоторомсмысле достаточным условием разделимости схемы алфавитного кодирования.ТЕОРЕМА 2Если числа 1\,..., 1п удовлетворяют неравенствуп12^г—1то существует такая разделимая (даже префиксная) схема алфавитного кодирования а =—• (3i)™=1,4moVi= U).2136.1. Алфавитное кодированиеДОКАЗАТЕЛЬСТВОБез ограничения общности можно считать, что Zi ^ 12 ^ . . . ^^ 1п.
Разобьем множество { / i , . . . , / n } "а классы эквивалентности по равенствутп{ L i , . . . , Lrn}, га ^ га. Пусть А* е Li, Hi • = \Li\. Тогда J2 tM = п , Ai < Л2 < . . . <г= 1< А т . В этих обозначениях неравенство Макмиллана можно записать так:тпг=1Из этого неравенства следуют га неравенств для частичных сумм:,^М2+^++HM<1.9ЛТNA M -AI-III*- ц22х™~х2 - . . . -2А--Л—1.Рассмотрим слова длины Ai в алфавите В.
Поскольку fj,i ^ 2 Al , из этих словможно выбрать //i различных слов Р\,...длины Ai. Исключим из дальнейшего рассмотрения все слова из В*, начинающиеся со слов P i , . . .Далеерассмотрим множество слов в алфавите В длиной Х2 и не начинающихся сослов /5Ь . .
.Таких слов будет 2х2 - fii2X2~Xl. Но р2 ^ 2Л2 - /zi2 A2_Al , значит,можно выбрать fi2 различных слов. Обозначим их Рщ+i,...Исключимслова, начинающиеся с /3М1+ь . . . , /?М1+М2, из дальнейшего рассмотрения. И далее,используя неравенства для частичных сумм, мы будем па г-м шаге выбирать /i;слов длины Ai, /? Ml+M2+ ... +Mi _ 1 ,...,/3 Ail+M2 +... +Mi _ 1+/ii , причём эти слова пе будутначинаться с тех слов, которые были выбраны раньше. В то же время длины этихслов всё время растут (так как Ai < \ 2 < ...
< А т ), поэтому они пе могут бытьпрефиксами тех слов, которые выбраны раньше. Итак, в конце имеем набор из гаслов 01,...= Рп, \Pi\ = h, - • •, I Ai| = In, КОДЫ pi,...,pnпе являютсяпрефиксами друг друга, а значит, схема а = (а* —>будет префиксной и, потеореме предыдущего подраздела, разделимой.•ПримерАзбука Морзе1 — это схема алфавитного кодирования(Л->01,Я —• 0000,О —• 111,У —> 0001,В —• 1000,I —> 00,Р0110,Ж —^ 011,С —> 1010, L>-*100, Е -> 0,F —> 0010, G —> 110,^ —> 0111, АГ —> 101, L —> 0100, М 1 1 ,N ^ 10,Q1101, Я —• 010, 5 —> 000,Г —> 1,С/ —> 001,Х->1001, Y ^ 1011, Z->1100),где по историческим и техническим причинам 0 называется точкой и обозначается знаком «•», а 1 называется тире и обозначается знаком «—».
Имеем:1Самуэль Морзе (1791-1872).214Глава 6. Кодирование 2141/4 ++ 1/16 +1/16+1/4 +1/16+1/16 +1/8+1/8 +1/2+1/16 +1/16+1/4 +1/8 +1/4 ++ 1/8++ 1/16+1/16+1/8+1/16+1/16+1/8+1/16+1/8+1/16 =1/2+1/8 += 2 / 2 + 4 / 4 + 7 / 8 + 1 2 / 1 6 = 3 + 5 / 8 > 1.Таким образом, неравенство Макмиллаиа для азбуки Морзе пе выполнено, и этасхема не является разделимой. На самом деле в азбуке Морзе имеются дополнительные элементы — паузы между буквами (и словами), которые позволяют декодировать сообщения.
Эти дополнительные элементы определены неформально,поэтому приём и передача сообщений с помощью азбуки Морзе, особенно с высокой скоростью, являлись некоторым искусством, а не простой техническойпроцедурой.Если схема алфавитного кодирования а = (а, —> Pi)™= i разделима,то существует префиксная схема а' = (аг —> Д-)-1=1, причём Vг (\Pi\ = \Р'{\).СЛЕДСТВИЕПример Схема (а —• 0, b —• 01) — разделимая, но не префиксная, а схема(а —> 0,6 —> 10) — префиксная (и разделимая).6.2. Кодирование с минимальнойизбыточностьюДля практики важно, чтобы коды сообщений имели по возможности наименьшую длину. Алфавитное кодирование пригодно для любых сообщений, то естьдля S = А*.
Если больше про множество S ничего не известно, то точно сформулировать задачу оптимизации затруднительно. Однако на практике часто доступна дополнительная информация. Например, для текстов на естественных языкахизвестно распределение вероятности появления букв в сообщении. Использование такой информации позволяет строго поставить и решить задачу построенияоптимального алфавитного кодирования.6.2.1.
Минимизация длины кода сообщенияЕсли задана разделимая схема алфавитного кодирования а — (а* —>i> т олюбая схема а' = (а* -н• Р/)™=1, где последовательность (Р\,...,Р'п)являетсяперестановкой последовательности ( P i , . . . , /5П), также будет разделимой. Еслидлины элементарных кодов равны, то перестановка элементарных кодов в схеме не влияет на длину кода сообщения. Но если длины элементарных кодовразличны, то длииа кода сообщения зависит от состава букв в сообщении и оттого, какие элементарные коды каким буквам назначены. Если заданы конкретное сообщение и конкретная схема кодирования, то нетрудно подобрать такуюперестановку элементарных кодов, при которой длина кода сообщения будет минимальна. Пусть ki,..., kn — количества вхождений букв ai,..., ап в сообщение2156.2.
Кодирование с минимальной избыточностьюs £ S, a li,... ,1п — длины элементарных кодов (3\,... ,0п соответственно. Тогда,если к{ ^ kj и li^ lj, то kiU + kjlj ^ kilj + kjU. Действительно, пусть kj = к + a,ki = к и lj = I, k = / + b, где a, b ^ 0. Тогда(kilj + kjli) - (kih + kjlj) = (kl + (k + a)(l + b)) - (k(l + b) + l(k + a)) == (kl + al + bk + ab + kl) - (kl + al + kl + bk) = ab ^ 0.Отсюда вытекает алгоритм назначения элементарных кодов, при котором длина кода конкретного сообщения s е S будет минимальна: нужно отсортироватьбуквы сообщения s в порядке убывания количества вхождений, элементарныекоды отсортировать в порядке возрастания длины и назначить коды буквам вэтом порядке.ЗАМЕЧАНИЕЭтот простой метод решает задачу минимизации длины кода только для фиксированногосообщения s е S и фиксированной схемы а.6.2.2.
Цена кодированияПусть заданы алфавит А = { a i , . . . , a n } и вероятности появления букв в сообщении Р = (pi,... ,р п ) (pi — вероятность появления буквы а;). Не ограничиваяобщности, можно считать, что PI + . . . +рп = 1 и р\ ^ . . . ^ рп > 0 (то есть можносразу исключить буквы, которые не могут появиться в сообщении, и упорядочить буквы по убыванию вероятности их появления). Для каждой (разделимой)схемы сг =—>i алфавитного кодирования математическое ожидание коэффициента увеличения длины сообщения при кодировании а (обозначается 1 а )определяется следующим образом:п1 рл)= Y 1гдеli= i&i'г=1и называется средней ценой (или длиной) кодирования ивероятностей Р.Пример Для разделимой схемы А = {a, Ь}, В = {0,1}, опри распределении вероятностей (0,5; 0,5) цепа кодирования+ 0,5 * 2 = 1,5, а при распределении вероятностей (0,9; 0,1)+ 0,1 *2 = 1,1.при распределении= {а —> 0,6 —• 01}составляет 0,5 * 1 +она равна 0 , 9 * 1 +Введём обозначения:U(P)= f inf ltr(P),аР* ==f minpi,г—1L = f [log 2 (n - 1)J + 1.Очевидно, что всегда существует разделимая схема а = (ai —>i> такая, чтоVi (\Pi\) = L.
Такая схема называется схемой равномерного кодирования. Следовательно, 1 ^ l*(P) ^ L, и достаточно учитывать только такие схемы, длякоторых Vг (PIU) ^ L, где U — целое и ^ ^ L/p*. Таким образом, имеется лишьконечное число схем а, для которых U(P) ^ 1<т(Р) ^ L. Значит, существует схема=сг*, на которой ипфимум достигается:1*(Р)-216Глава 6. Кодирование 216Алфавитное (разделимое) кодирование <т*, для которого /о-, ( Р ) = 1*{Р), называется кодированием с минимальной избыточностью, или оптимальным кодированием, для распределения вероятностей Р.6.2.3. Алгоритм ФаноРекурсивный алгоритм Фано 1 строит разделимую префиксную схему алфавитного кодирования, близкого к оптимальному.Алгоритм 6.1 Построение кодирования, близкого к оптимальномуВход: Р : array [l..n] of real — массив вероятностей появления букв в сообщении, упорядоченный по невозрастанию; 1 ^ Р[1] ^ ...
^ Р[п] > О,Р[1] + . . . + Р[п] = 1.Выход: С : array [l..n, 1..L] of 0..1 — массив элементарных кодов.Fano(l,n, 0) { вызов рекурсивной процедуры Fano }Основная работа по построению элементарных кодов выполняется следующейрекурсивной процедурой Fano.Вход: Ь — индекс начала обрабатываемой части массива Р, е — индекс конца обрабатываемой части массива Р, к — длина уже построенных кодов в обрабатываемой частимассива С.Выход: заполненный массив С.if е> b thenк: = к + 1 { место для очередного разряда в коде }тп: = Med(b, е) { деление массива на две части }for г from Ь to е doС[г, к]: = г > тп { в первой части добавляем 0, во второй — 1 }end forFano(6, тп, к) { обработка первой части }Fano(m + 1, е, к) { обработка второй части }end ifФункция Med находит медиану указанной части массива Р[Ь..е], то есть определяет такой индекс тп (b ^ тп < е), что сумма элементов Р[Ь..тп] наиболее близкак сумме элементов Р[(тп + 1)..е].Вход: b — индекс начала обрабатываемой части массива Р, е — индекс конца обрабатываемой части массива Р.Выход: тп — индекс медианы, то естьminm £ b .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
