Дискретная математика (998286), страница 29
Текст из файла (страница 29)
Д„. Это слово состоит из п элементарных кодов и имеет длину 1. Таким образом, и(п,т) — это число некоторых слов вида Д,... 111„; таких что ~А, А„~ = 1. В силу разделимости схемы и(п,~) < 2', в противном случае заведомо существовали бы два одинаковых слова А, ... рг„= Д,... 1ух„, допускающих различное разложение. Имеем и(п, 1) 2' 2т 2с 2=1 1=1 л о Следовательно, Уп (1 2 ")" < п1, и значит, 2 2 ' < тгп1, откуда 2 ' < 1пп ~lп( =1. Неравенство Макмиллана является не только необходимым, но и в некотором смысле достаточным условием разделимости схемы алфавитного кодирования.
Глава 6. Кодирование ТЕОРЕМА Если наела 11,..., 1» удовлетворяют неравенству ~ Х—, <1, 1 1=1 то существует разделимая схема алфавитного кодирования а = (аг — л 331)1 где т'1 11 = Щ. Доказательство Без ограничений общности можно считать, что 11 < 11 « ° 1„. Разобьем множество (1„..., 1„) на классы эквивалентности по равенству (Х,1,..., Х, ), тп < и. Пусть лг Е Х,г, рг: = д~, х~; рг = и, Л, < л, « " < Л„. г=1 Тогда неравенство Макмиллана можно записать так: — < 1. г=1 Из этого неравенства следуют т неравенств для частичных сумм: 111 — (1=ьгг1 < 2 ' Аг 21 — + — <1»гФггэ<2 г — гг 2 г г 111 РО л л-л 2л, 2л, '- 1 (2) — + — + ° ° + — < 1 ~ гг,» «< 2 — 1112 111 ро 11 л л -л, 21, 2лг 21 -л, 21 -л (ш) Рассмотрим слова длины Л1 в алфавите В.
Поскольку,ил < 2А', из этих слов можно выбрать 111 различных слов )3„..., Д„длины Л1. Исключим из дальнейшего рассмотрения все слова из В*, начинающиеся со слов г31,...,В„,. Далее рассмотрим множество слов в алфавите В длиной Лг и не начинающихся со слов 331,...,Д,, Таких слов будет 2А' — р12А' "'. Но ггз ( 2А' — р121' "', значит, можно выбРать Ра Различных слов. Обозначим их Х3„,+1,,33„,+н,. Исключим слова, начинающиеся с Вн,+1,...,Д„+„„из дальнейшего рассмотрения. И так далее, используя неравенства для частичных сумм, мы будем на г-м шаге выби- раТЬ 111 СЛОВ ДЛИНЫ Лг, 13нг+Иг 1--ЕИ вЂ” ...,33т+Лг+-+т-г+Ло ПРИЧЕМ ЭТИ СЛОВа не булут начинаться с тех слов, которые были выбраны раньше.
В то же время длины этих слов все время растут (так как Л1 < Лг « Л ), поэтому они не могут быть префиксами тех слов, которые выбраны раньше. Итак, в конце имеем набор из и слов (31,..., г3н,+...+„= В„, ф1) = 11,..., Щ = 1„, коды 331,..., Р„ не являются префиксами друг друга, а значит, схема а = (аг -+ Вг)». 1 будет префиксной и, по теореме предыдущего подраздела„разделимой. П 6.2.
Кодирование с минимальной избыточностью Пример Азбука Морзе — зто схема алфавитного кодирования (А + 01,  — ь 1000, С вЂ” т 1010,  — > 100, Е -+ О, Г -+ 0010, С -+ 110, Н -+ 0000, 1 -+ 00„7 -т 0111, К -+ 101, Ь вЂ” т 0100, М -т 11, Н -+ 10, О -+ 111, Р -+ 0110,Я -+ 1101, В -> 010, Я -ь ООО,Т -+ 1, У -+ 001, 1т -+ 0001, ИС вЂ > 011,Х -+ 1001, У вЂ” т 1011, Я -+ 1100), где по историческим и техническим причинам 0 называется точкой и обознача- ется знаком «ь, а 1 называется тире и обозначается знаком « — ь.
Имеем: 1/4+ 1/16+ 1/16+ 1/8+ 1/2+ 1/16+ 1/8+ 1/16+ 1/4+ 1/16+ + 1/8 + 1/16+ 1/4+ 1/4 + 1/8+ 1/16 + 1/16+ 1/8 + 1/8+ + 1/2+ 1/8+ 1/16+ 1/8+ 1/16+ 1/16+ 1/16 = = 2/2+ 4/4+ 7/8+ 12/16 = 3 + б/8 > 1. Таким образом, неравенство Макмиллана для азбуки Морзе не выполнено, и эта схема не является разделимой. На самом деле в азбуке Морзе имеются дополни- тельные элементы — паузы между буквами (и словами), которые позволяют де- кодировать сообшения.
Эти дополнительные элементы определены неформаль- но, поэтому прием и передача сообшений с помощью азбуки Морзе, особенно с высокой скоростью, является некоторым искусством, а не простой технической процедурой. 6.2. Кодирование с минимальной избыточностью Для практики важно, чтобы коды сообшений имели по возможности наименьшую длину. Алфавитное кодирование пригодно для любых сообщений, то есть Я = А*.
Если больше про множество Я ничего не известно, то точно сформулировать задачу оптимизации затруднительно. Однако на практике часто доступна дополнительная информация. Например, для текстов на естественных языках известно распределение вероятности появления букв в сообщении. Использова'ние такой информации позволяет строго поставить и решить задачу построения оптимального алфавитного. кодирования. 6.2.1. Минимизация длины кода сообщения Если задана разделимая схема алфавитного кодирования а = (а, -т Д)",. и то любая схема о' = (а, -'+ От'),", где (,Ут,..., /т'„) является перестановкой (Д,..., он), также будет разделимой.
Если длины элементарных кодов равны, то перестановка элементарных кодов в схеме не влияет на длину кода сообщения. Но если длины элементаРных кодов различны, то длина кода сообщения зависит от состава букв в сообшении и от того, какие элементарные коды каким буквам назначены. 1ЕВ Глава В. Кодирование Если заданы конкретное сообщение и конкретная схема кодирования, то нетрудно подобрать такую перестановку элементарных кодов, при которой длина кода сообщения будет минимальна. Пусть Ьы...,1с„— количества вхождений букв аы, ..,а„в сообщение Я, а 1ы...,1„— длины элементарных кодов 11,,...,13„, соответственно.
Тогда, если Ы ( Ь и 1« > 1, то )с«1«+ 6111 < Ь«1. + Ь 1ь Действительно, пусть 61 = 6+ а, Ьс = Ь и 1 = 1, 1« = 1+ Ь, где а, 6 > О. Тогда (Ы1, + 611«) — (Ь«1« + Ьз11) = (Ы + (Ь+ а)(1 + Ь)) — (й(1 + Ь) + 1(Ь + а)) = = (Ы+ а1+ ЬЬ+аЬ+ Ы) — (Ы+а1+ Ы+ Ыс) = аЬ > О. Отсюда вытекает злгоритм назначения элементарных кодов, при котором длина кода конкретного сообщения Я будет минимальна: нужно отсортировать буквы в порядке убывания количества вхождений, элементарные коды отсортировать в порядке возрастания длины и назначить коды буквам в этом порядке.
ЗАМЕЧАНИЕ Этот простой метод решает задачу минимизации длины кода только для фиксированного сообщения Я и фиксированной схемы о. 6.2.2. Цена кодирования Пусть заданы алфавит А = (аы...,а„) и вероятности появления букв в сообщении Р = (ры...,р„) (р; — вероятность появления буквы ас). Не ограничивая общности, можно считать, что рс+. +р„= 1 и р, » р„> 0 (то есть можно сразу исключить буквы, которые не могут появиться в сообщении, и упорядочить буквы по убыванию вероятности их появлении). Для каждой (разделимой) схемы о. = (а; -«11«),, алфавитного кодирования математическое ожидание коэффициента увеличения длины сообщения при кодировании (обозначается 1 ) определяется следующим образом: и 1 (Р):=~~ р«1о где 1«:=Щ «=1 и называется средней ценой (или длиной) кодирования с«при распределении вероятностей Р, Пример Для разделимой схемы А = (а, Ь), В = (О, Ц, Ю = (а -«0,6 — «ОЦ при распределении вероятностей (0.5, 0.5) цена кодирования составляет 0.5 в 1+ 0.5 * 2 = 1.5, а при распределении вероятностей (09,0,1) она равна 0 9*1+01*2 = 11.
Обозначим и Р): = гп1 1„(Р), Р,: = впцР«ьс =(1~Щз(а — 1Я + 1 6.2. Кодирование с минимальной избыточностью Очевидно, что всегда существует разделимая схема а = (а; -+ )тс),. с, такая что 'у'! [рс] = Е,. Такая схема называется схемой равномерного кодирования. Следовательно, 1 < 1„(Р) < Е, и достаточно учитывать только такие схемы, для которых 'г'! рс!с < Е где !с — целое н 1; < Е/р„. Таким образом, имеется лишь конечное число схем сг, для которых 1,(Р) < ! (Р) < Е. Следовательно, существует схема о„, на которой инфимум достигается: ! „(Р) = !.(Р).
Алфавитное (разделимое) кодирование а„для которого 1„,(Р) = 1,(Р), называется кодированием с минимальной избыточностью, или олптимальным кодированием, для распределения вероятностей Р. 6.2.3. Алгоритм Фано Следуюший рекурсивный алгоритм строит разделимую префиксную схему ал- фавитного кодирования, близкого к оптимальному Алгоритм 6.1. Построение кодирования, близкого к оптимальному Вход: Р; апау [1..п] оЕ геа! — массив вероятностей появления букв в сообщении, упорядоченный по невозрастанню; 1 > Р[1] » Р[п] > О, Р[1] + ° ° + Р[п] = 1. Выход: С: астау [1..п, 1..Е] оЕ 0..1 — массив элементарных кодов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
