Дискретная математика (998286), страница 30
Текст из файла (страница 30)
Рано(1,п, 0) ( вызов рекурсивной процедуры Рано ) Основная работа по построению элементарных кодов выполняется следующей рекурсивной процедурой Рапо. Вход: Ь вЂ” индекс начала обрабатываемой части массива Р, е — индекс конца обрабатываемой части массива Р, й — длина уже построенных кодов в обрабатываемой части массива С. Выход: заполненный массив С.
!Е е > Ь сйеп й: = й+ 1 ( место для очередного разряда в коде ) пс: =Мес!(Ь,е) ( деление массива на две части ) !ог с 6 от Ь Со е Йо С[А й]: =1 > т ( в первой части добавляем О, во второй — ! ) епс! Еог Рапо(Ь,т, й) ( обработка первой части ) Рапо(т + 1,е, й) ( обработка второй части ) епс! !Е Функция Мес( находит медиану указанной части массива Р[Ь..е], то есть определяет такой индекс пс (Ь < пс < е), что сумма элементов Р[Ь.гп] наиболее близка к сумме элементов Р[т+ 1..е].
Вход: Ь вЂ” индекс начала обрабатываемой части массива Р, е — индекс конца обрабатываемой части массива Р. в — „,„. [ьгс — с. ч~][ еь,е — с ;=ь с= -~-1 Я~: = 0 ( сумма элементов первой части ) Еог ! йод Ь со е — 1 с!о Глава Б. Кодирование Яь: = Яь + Р[ь] 1 вначале все, кроме последнего ) епй 1ог Я,: = Р[е[ 1 сумма элементов второй части ) т: = е 1 начинаем искать медиану с конца ) гереат Ы: = Яь — Я„ 1 разность сумм первой и второй части ) т: = тп — 1 1 сдвигаем границу медианы вниз ) Яь. = Яь — Р[т[; Я,: = Я, + Р[т) ~тй [Яь — Я,[ > д гетпгп пь ОБОСНОВАНИЕ При каждом удлинении кодов в одной части коды удлиняются нулями, а в другой — единицами.
Таким образом, коды одной части не могут быть префиксами другой. Удлинение кода заканчивается тогда и только тогда, когда длина части равна 1, то есть остается единственный код. Таким образом, схема по построению префиксная, а потому разделимая. П Пример Коды„построенные алгоритмом Фано для заданного распределения вероятностей (и= 7). рь С[1! 1ь 0.20 00 2 0.20 010 3 0.19 011 3 0.12 100 3 0.11 101 3 0.09 110 3 0.09 111 3 1, [Р) 2.80 6.2.4.
Оптимальное кодирование Оптимальное кодирование обладает определенными свойствами, которые можно использовать для его построения. ЛЕММА Пусть сг = (а; -+ Яь),", — схема оптимального кодирования для распределения вероятностей Р = р, » ° ° р„> О. Тогда если рь > р, то 1ь < 1 . Доюьзательство От пРотивного. ПУсть ь < 1, Рь > Рз и 1ь > 1, Тогда РассмотРим а' = (аь -+ Ям..., аь -+ Яу,..., пу -+ Яь,...,а„-+ Д,). 169 6.2. Кодирование с минимальной иабыточностыо Имеем: (. '1., = (Р,й+ РЛВ) — (р,.~, + Р,.ц = (р, — рз)(1г — 13) > О, что противоречит тому, что о — оптимально.
Таким образом, ие ограничивая общности, можно считать, что 1, « 1„. ЛЕММА Если а = (аг -+ )3з)г з — схема оптимального префиксного кодирования для распределения вероятностей Р = Р, » р„> О, то среди элементарных кодов, имеющих максимальную длину, имеются два, которые различаются только в последнем разряде. Доказательство От противного. 1.
Пусть кодовое слово максимальной длины одно и имеет вид г3„= )3Ь, где Ь = О Ч Ь = 1. Имеем: Чт' Е 1сп — 1 (г < у3). Так как схема префиксиая, то слова 13т,..., 13„з ие являются префиксами з3. С другой стороны, з3 ие является префиксом слов )3з,...,13„ы ииаче было бы 13 = з3зь а значит, 13з было бы префиксом 13„. Тогда схема о': =(от -+ 33т,..., а„-+ ф) тоже префиксиая, причем 1 (Р) = 1„(Р) — р„, что противоречит оптимальности о.
2. Пусть теперь два кодовых слова з3„, и г3„максимальной длины отличаются ие в последнем разряде, то есть 13„з = ЯЬ', Д„= ~3"Ьн, г3' ф,3", причем 1У, з3н ие являются префиксами для 3„..., 13н з и наоборот. Тогда схема а'.=(оз -+ ~м...,он з -+ ~3„юа„з -+ 13'Ь',о„-+ )3н) также является префиксиой, причем з (Р) = з,(Р) — р„, что противоречит оптимальности о. П ТЕОРЕМА Если о„т = (аг -+ 13г),", — схема оптимального пРефиксного кодирования для распределения вероятноппей Р = рз » ° р„з > О и рз = Ч'+ ч", причем н Рз ~ Э~Эрз-\ ~Эрз+з л ° - >Р -з ~ЭЧ >-Я > О, то кодирование со схемой о„= (аз -+ т3з,..., а. з -ь Ц з,а +т -+ Д+т,..., а„, -+ 33„з,о, -+ /3;О,о„-+ /3,1) является оптимальным префиксныи кодированием для распределения вероязпнон =Рз~.
- Рз-т|рз+з~ ° . Рн-з Я Я Доказательство 1. Если о з было префиксиым, то в„тоже будет префиксиым по построению. 3то Глава В. Кодирование Ь.(Р) =*Рг[г+Рх[з+" +Рт-г]1-г+Ругг[э+г+" + + Р -г( -~+3Ъ+ + Ол(1 - = =Р 1, +" +Р„,[„, +13(п'+е")+(и'+о") = =Рг(г+" +Р— 1 — +(тру+Ру =1.,(Р - )+Ру 3. Пусть схема гг„': =(аг -+ г3;),"., оптимальна для Р„. Тогда по предшествующей лемме гг„' = (аг -+ 13~,,а„а -+ 13'„юа„г -+ 130,а„-+ ]31). Положим Р = [г3[ и рассмотрим схему пг г: =(аг -+ Дг„...,а -+,9,...,ав а -+ гуго а), где 1' определено так, чтобы Р, , > д' + 3" > Р,„,. (ль(Рн) =(гРг+" +1 аР -а+(1'+1)3'+(1'+1)Ч" = =[гРг+ ' +1 -ар -2+1(ч +Я )+(гг +Ч ) = — (Р 1)+Р . 3.
ог — префиксное, значит, гг„' г тоже префиксное. з. а„, — оптимально, значит, 1 ° (Р„г) > 1,(Р„г). г'. 1,„(Р„) = 1,„, (Р„г) + р < (,(Р„д) +Ру = 1 (Р„), но ггг — оптимально, значит, а„оптимально. П б.2.5. Алгоритм Хаффмена Следующий рекурсивный алгоритм строит схему оптимального префиксного алфавитного кодирования для заданного распределения вероятностей появления зукв.
чпгоритм В.2. Построение оптимальной схемы — рекурсивная процедура Нпй1пап Вход: п — количество букв, Р: апау [1г.а] о( геа1 — массив вероятностей букв, упорядоченный по убыванию. Выход: С: аггау [1 зп 1..Ь] о1 О..1 — массив элементарных кодов, б: апау [1..о] ог 1..Ь— массив длин элементарных кодов схемы оптимального префнксного кодирования. Ю и = 2 1Ьеп С[1,1]: =О;1[1]: = 1( первый элемент ) С[2,1]:=1;с[2]:=1( второй элемент ) еЬе чг = Р[п — Ц+ Р[п] ( сумма двух последних вероятностей ) 3: =ор(п,ч) ( поиск места и вставка суммы ) Ни%пап(Р,о — 1) ( рекурсивный вызов ) Почгп(н,у) ( достраивание кодов ) епг[ 1Е Функция Ур находит в массиве Р место, в котором должно находиться число д ,см. предыдушнй алгоритм) и вставляет это число, сдвигая вниз остальные элеяенты.
6.2. Кодирование о минимальной избыточностью Вход: и — длина обрабатываемой части массива Р, Ч вЂ” вставляемая сумма. Выход: измененный массив Р. Уог» бото н — 1 4отчпго 2 йо 11 Р[» — Ц ( Ч 1)тея Р[»]: = Р[» — Ц( сдвиг элемента массива ) е1зе у: = т — 1( определение места вставляемого элемента ) еюд уог» ( все сделано — цикл не нужно продолжать ) еаза 1У евй уог Р[Я: = ч ( запись вставляемого элемента ) гегцгя у Процедура Почи строит оптимальный код для и букв на основе построенного оптимального кода для а — 1 буквы, Для этого код буквы с номером,у временно исключается из массива С путем сдвига вверх кодов букв с номерами, большими у, а затем н конец обрабатываемой части массива С добавляется пара кодов, полученных из кода буквы с номером .у удлинением на О и 1, соответственно.
Здесь С[т, *] означает вырезку из массива, то есть т-ю строку массива С. Вход: н — длина обрабатываемой части массива Р, у — номер «разделяемой» буквы. Выходу оптимальные коды в первых н элементах массивов С н б с; = С[у, «]( запоминание кода буквы у ) 1: = «[у]( и длины этого кода ) Гог т бом у Го н — 2 Йо С(», «]: = С(»+ 1, «]( сдвиг кода ) «[1]: = «[1 + Ц ( и его длины ) еод уог С[и — 1, «]: = с; С(н, «]: = с( копирование кода буквы у' ) С[п — 1,1+ Ц: = О; С[н,1+ Ц: = 1( наращивание кодов ) «[н — Ц: =1+ 1; «(н]: =1+ 1( н увеличение ллнн ) ОБОСНОВАНИЕ Для пары букв при любом распределении вероятностей оптимальное кодирование очевидно: первой букве нужно назначить код О, а второй — 1. Именно это и делается в первой части оператора 11 основной процедуры Нцйпап.
Рекурсивная часть алгоритма в точности следует доказательству теоремы предыдущего подраздела. С помощью функции 1)р в исходном упорядоченном массиве Р отбрасываются две последние (наименьшие) вероятности, и нх сумма вставляется в массив Р, так чтобы массив (на единицу меньшей длины) остался упорядоченным.
Заметим, что при этом место вставки сохраняется в локальной переменной у'. Так пРоисходит до тех пор, пока не останется массив из двух элементов, для которого оптимальный код известен. После этого в обратном порядке строятся оптимальные коды для трех, четырех и т. д. элементов. Заметим, что при этом массив вероятностей Р уже не нужен — нужна толыто последовательность номеров кодов, которые должны быть изъяты из массива кодов и продублированы в конце с добавлением разряда.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
