С.В. Яблонский - Введение в дискретную математику (1060464), страница 40
Текст из файла (страница 40)
Найдем их средние длины ),р — — 2, ),р 0,40+ 2 0,25+ 3 0,35 ~ 1,95, ч. гч. теОРия нодпровлння гтт Таким образом, средняя длина может изменяться при переходе от одной схемы алфавитного кодирования к другой. Ввиду этого для данного источника сообщений можно ввести величину 1р, где 1а =1п)1;р. в х (Здесь нижняя грань берется по всем схемам Х, обеспечивающим свойство взаимной однозначности.) Легко видеть, что 1(1р() 1опчг( (верхнюю оценку дает равномерное кодирование).
Отсюда видно, что для построения кодов, у которых величина 1„близка к 1ю можно не учитывать коды с большим, чем ]1оя, г[. Значит, для таких схем р)~Ъоа г( Поскольку при вычислении 1„члены с р = О не играют роли, то, положив рр = ш)пр;, имеем $ р$ФО ) 1оо г( 1~( — ч р для всех 1, для которых речь О, и, значит, имеется конечное число вариантов значений 1гм для которых 1р ( )ьр (()1оачг[ Следовательно, величина 1р достигается на некотором Х и может быть определена как ш)п 1,р. х 3 Определение. Коды, определяемые схемой Е с 1,р — — )ю называются кодами с минимальной избыточностью, или кодами Хафмана (41).
Очевидно, что коды с минимальной избыточностью дают в среднем минимальное увеличение длин слов при соответствующем кодировании. Ввиду этого представляет интерес аадача о построении кодов с минимальной иэбыточпостью. Замечание. В силу следствия 2 из 3 3 существует алфавитное кодирование со свойством префикса, дающее коды с минимальной избыточностью. Ввиду этого при построении кодов с минимальной избыточпостью ч. 1у.
теогия кодпРОВАш$я 278 можно ограничиться рассмотрением кодов, обладающих свойством префикса. Теперь перейдем к вопросу о построении кодов с минимальной избыточностью. Каждому алфавитному кодированию со свойством префикса можно сопоставить кодовое дерево. На примере покажем, каким образом зто делается. Пример 10.
Пусть задана схема Е следующего вида (г 8, 9=4): р,=0,22 р,=О,2О р, =0,14 р, = О',11 р,=О1О р, =0,09 р,-0,08 р, 0,06. Ь!Ь1 Ьз Ь,Ь, Ь,Ь, Ь,Ь,Ь, Ь,Ь, Ь,Ь, Ь,Ь,Ь, а,— а,— п,— а,— И~— п,— а,— а,— р ~р >р Очевидно, данная схема определяет код со свойством префикса и 0,20+ 2(0,22+ 0,14+ 0,11+ 0,09+ 0,08)+ +3(0,10+0,06) 0,20+2 0,64+3 0,16 0,20+ 1,28 + 0,48 = 1,96. Элементарные коды определяют дерево (см. рис.
11). Концевым вершинам этого дерева соответствуют элементарные коды, определяемые путем (ветвью), идущим из Ю~ Ю~ др корня, н им приписаны вероятности появления элементарных кодов. Легко видеть, что кодовое дерево, у которого конд1 4 дз аь 07 ат цевым вершинам приписаны вер р у р д з е ~ а г роятности, аадает схему алфавитного кодирования со свойством префикса. рг рз Сначала рассмотрим част- ный случай задачи, именно, Рве. И когда среди чисел р„..., р, имеется не более одного, рав- ного пулю. Без ограничения общпостп можно считать, что ч. ьч, творьья кодирования гту Лемма ь. льля кода с лшнимальной избыточностью из условия р»(р< следует, что 1,~(». Доказательство. Предположим противное, т.
е. р»(р<, а Ь»()ь Тогда, если в схеме для кода с минимальной избыточностью: а< — Вь а> — В„ поменять местами элементарные коды В, и Вь мы полу- чим схему Е'ь а< — Вь '(Г]' аь — Вь » имеющую меньшую среднюю длину»ср чем для схемы Х. В самом деле, 1ср — ьер = (РА + РИ (Р»ь»' + РА) - (р, — р») ()ь — )») > О. Последнее противоречит минимальной избыточности Е.
Лемма доказана. Следствие. В кодовом дереве для кода с минимальной избыточностью вероятности, приписанные концевым вершинам из Г-го яруса, не меньше, чем вероятности, приписаннь»е концевым вершинам из ь'"-го яруса, если ь'" ) ь". Далее будем рассматривать конечные деревья с максимальным порядком ветвления (числом исходящих из вершин ребер) д. Определение. Неконцевая вершина дерева называется насыщенной, если ее порядок ветвления равен д. Конечное дерево называется насыщенньиа, если в нем насыщены все неконцевые вершины, за исключением, быть может, одной, лежащей в предпоследнем ярусе, и порядок ветвления этой исключительной вершины равен д», где 2 ~ д» ( у.
В случае, когда в насыщенном дереве нет исключи-' тельной вершины, будем считать, что д»=у (роль ис- ч. 1ч. теоРпя нодпРовхппя 280 ключительной вершины в этом случае может играть любая неконцеван вершина из предпоследнего яруса). Покажем, что по числам г и д число о, определяется однозначно. С этой целью заданное насыщенное дерево будет преобразовано в другое насыщенное дерево, имеющее определенную структуру и связанное с исходным деревом только тем, что у пего то же число концевых и то же число внутренних вершин.
Один шаг преобразования уе Рве. 13 Рве. 12 (см. рис. 12) состоит в перемещении некоторого пучка из д концевых ребер в корень дерева, причем к корню присоединяется одна из концевых вершин (пучок ребер при исключительной вершине не трогается, если даже о,= о). Такое преобразование выполняется до тех пор, пока это возможно, и в результате получается дерево, изображенное на рис. 13. Из него видно, что число о, удовлетворяет уравнению г = 1(о — 1) + д,.
Вычислим остаток от деления г на д — 1 и положим д — 1, если остаток равен Ое де о„если остаток равен 1, остатку, если он ) 2. (5) Л е м м а 2. Среди кодов с минимальной избыточностью существует код, кодовое дерево которого является насыщенным. Д о к а з а т е л ь с т в о. Рассмотрим два преобразования кодовых деревьев указанного ниже типа, которые не увеличивают среднюю длину.
1. Удаление ребра в последнем ярусе. Если в некотором пучке последнего яруса кодового дерева содержится ровно одно ребро, то с ним связан эле- Ч. 1Ч. ТЕОРИЯ КОДПРОВХНПЯ ментарный код В В'Ь с вероятностью р, причем слово В' не является префиксом никакого другого элементарного кода. Удаляя данное ребро и перенося вероятность р в вершину, из которой исходило это ребро, получим новое кодовое дерево. Этому преобразованию соответствует переход от схемы л к схеме Г, если заменить в Х элементарный код В на В'. Очевидно, с (ср = )ср — Р ~~ (ср 2. Перемещение ребер из последнего яруса в вершину кодового дерева, которая не является насыщенной. Пусть кодовое дерево в последнем 1-м ярусе содерл!нт пе менее двух ребер.
Значит, существует ребро, концевой вершине которого приписана вероятность р(р ) 0), и некоторый элементарный код В. Пусть, далее, имеется вершина, расположенная в Г-м ярусе (Г ~1 — 1) и не являющаяся насыщенной. Обозначим через В' слово, соответствующее этой вершине. Из ненасыщенности вершины следует, что суп1ествует символ Ь„для которого В'Ь, не является префиксом никакого элементарного кода. В этом случае можно упомянутое ребро последнего яруса перенести в данную ненасыщенную вершину по направлению !.
Таким образом, заменяя элементарный код В на В'Ьь мы получаем из схемы 2 схему Х'; р( + р (((В ) + 1) ~ 1,„. Преобразования 1 и 2 позволяют любой префиксный код из рассматриваемого класса, в том числе в код с минимальной избыточностью, привести к коду, дерево которого является насыщенным, не увеличивая при этом среди!ою длину.
Лемма доказана. Пример 11. Используя преобразования 1 и 2, кодовое дерево, изображенное на рис. 11, можно прсобрааовать в дерево, которое является насыщенным (рис. 14). Найдем величину 1,р для этого кода: (ср = 0!22 + Ос20 + 2 (О 14 + 0 11 + Ое10 + Ое09 + + 0,08+ 0,06) = 0,42 + 2 0,58 1,58.
Средняя длина данного кода меньше исходного. 3 а и с ч а и и е. Рассмотрим код с минимальной избыточностью, кодовое дерево которого насыщено. Возьмем пучок ребер последнего яруса, идущих из исключи- 282 Ч. 1Ч. ТЕОРИЯ КОДИРОВАНИЯ тельной вершины (см. определение на с. 279). Если та. кой вершины нет, то возьмем произвольный пучок в последнем ярусе. Пусть д,— число ребер во взятом пучке, 2 < д, < д. В силу следствия вершинам из последнего яруса приписаны Ь Ьв вероятности р, +„..., р„где е е 2 3 гп ~ д„либо равные им вероятностн Рг (это возмонсно при р, р,— +~). Поэтому путем перестановки эле- гегюз а» ег ег ментарных кодов максимальной длнРз Рв Ре Ре Р Рв НЫ И ЭЛЕМЕНтаРНЫХ КО)СОВ, СООтВЕт- ствующих одинаковым вероятностям Рвс.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
