Реферат: Коды Шеннона – Фано и Хафмана
ВВЕДЕНИЕ
Новые направления, возникшие в математике в ХХвеке, обычно оперируют со сложными понятиями и представлениями, которые струдом поддаются популяризации. На этом фоне весьма значительна заслугавыдающегося американского математика и инженера Клода Шеннона, который в1947—1948 годах, исходя из элементарных соображений, открыл новую область математики- теорию информации. Толчком к созданию новой науки были чисто техническиепроблемы передачи информации по телеграфным и телефонным проводам, однако кнастоящему времени благодаря общему характеру теория информации находитприменение в исследованиях, относящихся к передаче и сохранению любойинформации в природе и технике.
В конце сороковых годов, на заре развития теории информации, идеиразработки новых эффективных способов кодирования информации носились в воздухе.Исследователи занимались вопросами энтропии, содержимого информации иизбыточности. Интересно, что эти первоначальные работы в области сжатияинформации велись до появления современного цифрового компьютера. Сегоднятеория информации развивается параллельно с программированием, но в то времяидея разработки алгоритмов, использующих двоичную арифметику для кодированиясимволов, была значительным шагом вперед.
Одними из первых алгоритмов эффективного кодирования информации былиалгоритмы Шеннона – Фано и Хафмана.
В данной работе рассмотрены базовые понятия энтропиии информации, а также описаны принципы кодирования сообщений по Шеннону – Фанои Хафману, показана их важная роль при передаче информации по линиям связи.
Но линии связи, для которых были разработаныэти методы кодирования информации, уже в прошлом. К счастью, для принциповШеннона — Фано и Хафмана нашли применение и в современном мире: для сжатияинформации. Архиваторы PKZIP, ARJ, а также часть всем нам хорошоизвестного стандарта JPEG(сжатие графической информации спотерями) работают именно на этих принципах.
Коды Шеннона – Фано и Хафмана преподаются вовсех технических ВУЗах мира и, кроме того, входят в программу для углубленногоизучения информатики в школе.
Поэтому изучение методов кодирования Шеннона –Фано и Хафмана является актуальным.
Цельданной работы — изучить принципы кодирования информацииШеннона — Фано и Хафмана и применение их при решении задач.
Задачасостоит в том, чтобы изучить энтропии и избыточностьконкретных типов сообщений для последующего применения к ним принципов Шеннона- Фано и Хафмана.
1. Информация и кодирование. КодыШеннона — Фано и Хафмана.
1.1 Информацияи кодирование.
Слово «информация» известно в наше время каждому.Происходит оно от латинского «informatio»,что означает – разъяснение, сообщение, осведомленность. Однако в постоянноеупотребление оно вошло не так давно, в середине двадцатого века, с подачи КлодаШеннона. Он ввел этот термин в узком техническом смысле применительно к теориисвязи или передачи кодов, которая получила название «Теория информации». Здесь важны не любые сведения, а лишь те, которыеснимают полностью или уменьшают существующую неопределенность. Философское,и поэтому более широкое определение этого термина дает один из основателейинформатики, известный американский ученый Норберт Винер: «Информация – это обозначение содержания, черпаемого нами из внешнегомира в процессе нашего приспособления к нему и приведение в соответствие с нимнашего мышления». Разумеется, это далеко не единственные в своем родеопределения информации.
В настоящее время этот термин имеет более глубокий имногогранный смысл. Во многом оставаясьинтуитивным, он получает разные смысловые наполнения в разных отрасляхчеловеческой деятельности:
v<span Times New Roman"">
v<span Times New Roman"">
v<span Times New Roman"">
v<span Times New Roman"">
Такое разнообразие подходов не случайно, а следствиетого, что выявилась необходимость осознанной организации процессов движения иобработки того, что имеет общее название – информация.
Для дальнейшего рассмотрения нам необходимо то понятиеинформации, которое подразумевает передачу информационных сообщений по линиямсвязи. Рассмотрим общую схему передачи сообщений; для определенности будемговорить, например, о телеграфии. На одном конце линии отправитель подаетнекоторое сообщение, записанное припомощи любого из известных нам алфавитов или цифр, или и букв и цифр вместе взятых. Для передачитакого рода сообщений используются последовательности сигналов постоянного тока,некоторые характеристики которого телеграфист может менять по своему усмотрению,воспринимаемых вторым телеграфистом на приемном конце линии. Простейшимиразличимыми сигналами, широко используемыми на практике, является посылкатока (т.е. включение его на некоторое вполне определенное время) иотсутствие посылки – пауза (выключение тока на то же время); при помощиодних только этих двух сигналов уже можно передать любое сообщение, еслиусловиться заменять каждую букву или цифру определенной комбинацией посылоктока и пауз.
В технике связи правило, сопоставляющее каждомупередаваемому сообщению некоторую комбинацию сигналов, обычно называется кодом(в случае телеграфии – телеграфным кодом), а сама операция перевода сообщения впоследовательность различных сигналов – кодированиемсообщения. Под «кодом» будетпониматься такая совокупность пкодовых обозначений, сопоставляемых пбуквам алфавита, для которой выполняется условие: никакое кодовое обозначениеодной буквы не совпадает с началом какого-либо другого более длинного кодовогообозначения, т.е. коды должны быть однозначнодекодируемыми.При этом коды, использующие только два различных элементарныхсигнала (например, посылку тока и паузу), называются двоичными кодами. Внекоторых телеграфных аппаратах кроме простого включения и выключения токаможно также изменять его направление на обратное. При этом появляетсявозможность вместо посылок тока и пауз использовать в качестве основныхсигналов посылку тока в двух различных направлениях или же использовать сразутри различных элементарных сигнала одной и той же длительности – посылку тока водном направлении, посылку тока в другом направлении и паузу (такой способкодирования называется троичным кодом). Возможны также еще более сложныетелеграфные аппараты, в которых посылки тока различаются не только опнаправлению, но и по силе тока; тем самым мы получаем возможность сделать числоразличных элементарных сигналов еще большим. Увеличение числа разныхэлементарных сигналов позволяет сделать код более сжатым. Однако вместе с темоно усложняет и удорожает систему передачи, так что в технике все жепредпочтительно используются коды с малым числом элементарных сигналов.
Пусть имеется сообщение, записанное при помощинекоторого «алфавита», содержащего п«букв». Требуется «закодировать» это сообщение, т.е. указать правило,сопоставляющее каждому такому сообщению определенную последовательность из т различных «элементарных сигналов»,составляющих «алфавит» передачи. Мы будем считать кодирование тем более выгодным,чем меньше элементарных сигналов приходится затратить на передачу сообщения.Если считать, что каждый из элементарных сигналов продолжается одно и то жевремя, то наиболее выгодный код позволит затратить на передачу сообщения меньшевсего времени.
Главным свойством случайных событий является отсутствие полнойуверенности в их наступлении, создающее известную неопределенность привыполнении связанных с этими событиями опытов. Однако совершенно ясно, чтостепень этой неопределенности в различных случаях будет совершенно разной. Дляпрактики важно уметь численно оценивать степень неопределенности самыхразнообразных опытов, чтобы иметь возможность сравнить их с этой стороны.Рассмотрим два независимых опыта <img src="/cache/referats/25989/image002.gif" v:shapes="_x0000_i1025"> и<img src="/cache/referats/25989/image004.gif" v:shapes="_x0000_i1026"> а также сложный опыт <img src="/cache/referats/25989/image006.gif" v:shapes="_x0000_i1027"><img src="/cache/referats/25989/image002.gif" v:shapes="_x0000_i1028"> и<img src="/cache/referats/25989/image004.gif" v:shapes="_x0000_i1029"><img src="/cache/referats/25989/image002.gif" v:shapes="_x0000_i1030"> имеет k равновероятных исходов, а опыт <img src="/cache/referats/25989/image004.gif" v:shapes="_x0000_i1031"> имеет l равновероятных исходов. Очевидно, что неопределенностьопыта <img src="/cache/referats/25989/image006.gif" v:shapes="_x0000_i1032"> большенеопределенности опыта<img src="/cache/referats/25989/image002.gif" v:shapes="_x0000_i1033"><img src="/cache/referats/25989/image002.gif" v:shapes="_x0000_i1034"> здесь добавляется ещенеопределенность исхода опыта <img src="/cache/referats/25989/image004.gif" v:shapes="_x0000_i1035"><img src="/cache/referats/25989/image006.gif" v:shapes="_x0000_i1036"><img src="/cache/referats/25989/image002.gif" v:shapes="_x0000_i1037"> и<img src="/cache/referats/25989/image004.gif" v:shapes="_x0000_i1038">
<img src="/cache/referats/25989/image010.gif" v:shapes="_x0000_i1039">
Условиям <img src="/cache/referats/25989/image012.gif" v:shapes="_x0000_i1040"> <img src="/cache/referats/25989/image014.gif" v:shapes="_x0000_i1041"><img src="/cache/referats/25989/image016.gif" v:shapes="_x0000_i1042"> при <img src="/cache/referats/25989/image018.gif" v:shapes="_x0000_i1043"> удовлетворяет толькоодна функция — <img src="/cache/referats/25989/image020.gif" v:shapes="_x0000_i1044">
<img src="/cache/referats/25989/image022.gif" v:shapes="_x0000_i1045">
Рассмотрим опыт А, состоящий изопытов <img src="/cache/referats/25989/image024.gif" v:shapes="_x0000_i1046"> и имеющих вероятности <img src="/cache/referats/25989/image026.gif" v:shapes="_x0000_i1047">А будет равна
<img src="/cache/referats/25989/image028.gif" v:shapes="_x0000_i1048">
Это последнее число будем называть энтропией опыта <img src="/cache/referats/25989/image002.gif" v:shapes="_x0000_i1049"> и обозначать через <img src="/cache/referats/25989/image031.gif" v:shapes="_x0000_i1050">
Если число букв в «алфавите» равно п, а число используемых элементарных сигналов равно т, то при любом методе кодирования среднее число элементарных сигналов,приходящихся на одну букву алфавита, неможет быть меньше чем <img src="/cache/referats/25989/image033.gif" v:shapes="_x0000_i1051">; однако он всегда может быть сделано сколь угодно близким к этому отношению, еслитолько отдельные кодовые обозначения сопоставлять сразу достаточно длинными«блоками», состоящими из большого числа букв.
Мы рассмотрим здесь лишь простейший случай сообщений,записанных при помощи некоторых п«букв», частоты проявления которых на любом месте сообщения полностьюхарактеризуется вероятностями р1,р2, … …, рп, где, разумеется, р1 + р2 + … + рп= 1, при котором вероятность pi проявления i-й буквы на любомместе сообщения предполагается одной и той же, вне зависимости от того, какиебуквы стояли на всех предыдущих местах, т.е. последовательные буквы сообщения независимыдруг от друга. На самом деле в реальных сообщениях это чаще бывает не так; вчастности, в русском языке вероятность появления той или иной буквы существеннозависит от предыдущей буквы. Однако строгий учет взаимной зависимости буквсделал бы все дельнейшие рассмотрения очень сложными, но никак не изменитбудущие результаты.
Мы будем пока рассматривать двоичные коды;обобщение полученных при этом результатов на коды, использующие произвольноечисло т элементарных сигналов, является,как всегда, крайне простым. Начнем с простейшего случая кодов, сопоставляющихотдельное кодовое обозначение – последовательность цифр 0 и 1 – каждой «букве»сообщения. Каждому двоичному коду для п-буквенногоалфавита может быть сопоставлен некоторый метод отгадывания некоторогозагаданного числа х, непревосходящего п, при помощивопросов, на которые отвечается лишь«да» (1) или «нет» (0), что и приводит нас к двоичному коду. При заданныхвероятностях р1, р2, … …, рп отдельных букв передача многобуквенного сообщениянаиболее экономный код будет тот, для которого при этих именно вероятностях п значений х среднее значение числа задаваемых вопросов (двоичных знаков: 0 и1 или элементарных сигналов) оказывается наименьшим.
Прежде всего среднее число двоичных элементарныхсигналов, приходящихся в закодированном сообщении на одну букву исходногосообщения, не может быть меньше Н,где Н = — p1 logp1 –p2 logp2 — … — pnlogpn – энтропияопыта, состоящего в распознавании одной буквы текста (или, короче, простоэнтропия одной буквы). Отсюда сразу следует, что при любом методе кодирования для записи длинного сообщения из М буквтребуется не меньше чем МН двоичных знаков, и никак не может превосходитьодного бита.
Если вероятности р1,р2, … …, рп не все равны между собой, то Н < logn; поэтому естественно думать, чтоучет статистических закономерностей сообщения может позволить построить кодболее экономичный, чем наилучший равномерный код, требующий не менее М logn двоичных знаков для записи текста из М букв.
1.2 КодыШеннона – Фано.
Для удобства расположим все имеющиеся п букв в один столбик в порядке убываниявероятностей. Затем все эти буквы следует разбить на две группы – верхнюю инижнюю – так, чтобы суммарная вероятность первой группы была наиболее близка ксуммарной вероятности второй группы. Для букв первой группы в качестве первойцифры кодового обозначения используется цифра 1, а для букв второй группы –цифра 0. Далее, каждую из двух групп подобным образом снова надо разделить надве части и в качестве второй цифры кодового обозначения мы будем использоватьцифру 1 или 0 в зависимости от того, принадлежит ли наша группа к первой или ковторой из этих подгрупп. Затем, каждая из содержащих более одной буквы группснова делится на две части возможно более близкой суммарной вероятности и т.д.;процесс повторяется до тех пор, пока мы не придем к группам, каждая из которыхсодержит по одной единственной букве.
Такой метод кодирования сообщений был впервыепредложен в 1948 – 1949 гг. независимо друг от друга Р. Фано и К. Шенноном;поэтому соответствующий код обычно называется кодом Шеннона – Фано. Так,например, если наш алфавит содержит всего шесть букв, вероятность которых (впорядке убывания) равны 0,4, 0,2, 0,2, 0,1, 0,05 и 0,05, то на первом этапеделения букв на группы мы отщепим лишь одну первую букву (1-я группа), оставивво второй группе все остальные. Далее, вторая буква составит 1-ю подгруппу 2-йгруппы; 2-я же подгруппа той же группы, состоящая из оставшихся четырех букв,будет и далее последовательно делиться на части так, что каждый раз 1-я частьбудет состоять лишь из одной буквы.
№ буквы
вероят-ность
разбиение на подгруппы (римские цифры обозначают номера групп и подгрупп)
кодовое обозначение
1
0,4
} I
1
2
0,2
} II
} I
01
3
0,2
} II
} I
001
4
0,1
} II
} I
0001
5
0,05
} II
} I
00001
6
0,05
} II
00000
Табл.1
Аналогично предыдущему примеру разобран случай«алфавита», включающего 18 букв, имеющих следующие вероятности: 0,3; 0,2; 0,1(2 буквы); 0,05; 0,03 (5 букв); 0,02(2 буквы); 0,01 (6 букв). (Табл. 2)
№ буквы
вероят-ность
разбиение на подгруппы
кодовое обозначение
1
0,3
} I
} I
11
2
0,2
} II
10
3
0,1
} II
} I
} I
011
4
0,1
} II
} I
0101
5
0,05
} II
0100
6
0,03
} II
} I
} I
} I
00111
7
0,03
} II
00110
8
0,03
} II
} I
00101
9
0,03
} II
00100
10
0,03
} II
} I
} I
00011
11
0,02
} II
} I
000101
12
0,02
} II
000100
13
0,01
} II
} I
} I
000011
14
0,01
} II
} I
0000101
15
0,01
} II
0000100
16
0,01
} II
} I
000001
17
0,01
} II
} I
0000001
18
0,01
} II
0000000
Табл.2
Основной принцип, положенный в основу кодирования пометоду Шеннона – Фано, заключается в том, что при выборе каждой цифры кодовогообозначения мы стараемся, чтобы содержащееся в ней количество информации былонаибольшим, т. е. чтобы независимо от значений всех предыдущих цифр эта цифрапринимала оба возможных для нее значения 0 и 1 по возможности с одинаковойвероятностью. Разумеется, количество цифр в различных обозначениях при этомоказывается различным (в частности, во втором из разобранных примеров онменяется от двух до семи), т. е. код Шеннона – Фано является неравномерным.Нетрудно понять, однако, что никакое кодовое обозначение здесь не можетоказаться началом другого, более длинного обозначения; поэтому закодированноесообщение всегда может быть однозначно декодировано. В результате, среднее значение длины такого обозначения все же оказываетсялишь немногим большим минимального значения Н,допускаемого соображениями сохранения количества информации при кодировании.Так, для рассмотренного выше примера 6-буквенного алфавита наилучшийравномерный код состоит из трехзначных кодовых обозначений (ибо 22 <6 < 23), и поэтому в нем на каждую букву исходного сообщенияприходится ровно 3 элементарных сигнала; при использовании же кода Шеннона –Фано среднее число элементарных сигналов, приходящихся на одну букву сообщения,равно
<img src="/cache/referats/25989/image035.gif" v:shapes="_x0000_i1052">
Это значениезаметно меньше, чем 3, и не очень далеко от энтропии
<img src="/cache/referats/25989/image037.gif" v:shapes="_x0000_i1053">
Аналогично этому для рассмотрения примера18-буквенного алфавита наилучший равномерный код состоит из пятизначных кодовыхобозначений (так как 24 < 18 < 25); в случае жекода Шеннона – Фано имеются буквы, кодируемые даже семью двоичными сигналами,но зато среднее число элементарных сигналов, приходящихся на одну букву, здесьравно <img src="/cache/referats/25989/image039.gif" v:shapes="_x0000_i1054">
Последнее значение заметно меньше, чем 5, — и уже ненамного отличается от величины
<img src="/cache/referats/25989/image041.gif" v:shapes="_x0000_i1055">
Особенновыгодно бывает кодировать по методу Шеннона – Фано не отдельные буквы, а сразуцелые блоки из нескольких букв. Правда, при этом все равно невозможно превзойтипредельное значение Н двоичных знаковна одну букву сообщения. Рассмотрим, например, случай, когда имеются лишь дверазличные буквы А и Б, имеющие вероятности р(А)= 0,7 и р(Б) = 0,3; тогда
H = — 0,7 log0,7 – 0,3 log0,3 = 0,881…
Применение метода Шеннона – Фано к исходномудвухбуквенному алфавиту здесь оказывается бесцельным: оно приводит нас лишь кпростейшему равномерному коду
буква
вероятность
кодовое обозначение
А
0,7
1
Б
0,3
требующему для передачи каждой буквы одного двоичногознака – на 12% больше минимального достижимого значения 0,881 дв.зн./букву.Применяя же метод Шеннона – Фано к кодированию всевозможных двухбуквенныхкомбинаций (вероятность которых определяется правилом умножения вероятностейдля независимых событий), мы придем к следующему коду:
комбина- ция букв
вероятность
кодовое обозначение
АА
0,49
1
АБ
0,21
01
БА
0,21
001
ББ
0,09
000
Среднее значение длины кодового обозначения здесьравно
<img src="/cache/referats/25989/image043.gif" v:shapes="_x0000_i1056">
так что на одну букву алфавита здесь приходится в среднем <img src="/cache/referats/25989/image045.gif" v:shapes="_x0000_i1057"> двоичных знаков – лишьна 3% больше значения 0,881 дв.зн./букву. Еще лучше результаты мы получим,применив метод Шеннона – Фано к кодированию трехбуквенной комбинации; при этом мыпридем к следующему коду:
комбина- ция букв
вероятность
кодовое обозначение
ААА
0,343
11
ААБ
0,147
10
АБА
0,147
011
БАА
0,147
010
АББ
0,063
0010
БАБ
0,063
0011
ББА
0,063
0001
БББ
0,027
0000
Среднее значение длины кодового обозначения здесь равно2,686, т.е. на одну букву текста приходится в среднем 0,895 двоичных знаков,что всего на 1,5% больше значения <img src="/cache/referats/25989/image047.gif" v:shapes="_x0000_i1058"> дв.зн./букву.
В случае ещебольшей разницы в вероятностях букв А иБ приближение к минимально возможномузначению Н дв.зн./букву можетнесколько менее быстрым, но оно проявляется не менее наглядно. Так, при р(А)= 0,89 и р(Б) = 0,11 это значение равно – 0,89 log0,89 –0,11 log0,11 ≈ 0,5дв.зн./букву, а равномерный код <img src="/cache/referats/25989/image049.gif" v:shapes="_x0000_i1059"> (равносильныйприменению кода Шеннона – Фано к совокупности двух имеющихся букв) требуетзатраты одного двоичного знака на каждую букву – в два раза больше. Нетруднопроверить, что применение кода Шеннона – Фано к всевозможным двухбуквеннымкомбинациям здесь приводит к коду, в котором на каждую букву приходится всреднем 0,66 двоичных знаков, применение к трехбуквенным комбинациям — 0,55, ак четырехбуквенным блокам — в среднем 0,52 двоичных знаков – всего на 4% большеминимального значения 0,50 дв.зн./букву.
1.3 Коды Хафмана.
Близок к кодуШеннона – Фано, но еще выгоднее, чем последний, так называемый код Хафмана.Построение этого кода опирается на простое преобразование используемогоалфавита, называемое сжатиемалфавита. Пусть мы имеем алфавит А,содержащий буквы <img src="/cache/referats/25989/image051.gif" v:shapes="_x0000_i1060"><img src="/cache/referats/25989/image053.gif" v:shapes="_x0000_i1061">
<img src="/cache/referats/25989/image055.gif" v:shapes="_x0000_i1062">
Условимся теперь неразличать между собой две наименее вероятные буквы нашего алфавита, т.е.будем считать, что ап-1и ап – это одна и та жебуква b нового алфавита А1,содержащего теперь уже буквы <img src="/cache/referats/25989/image057.gif" v:shapes="_x0000_i1063"> и b (т.е. ап-1 или ап), вероятности появлениякоторых в сообщении соответственно равны <img src="/cache/referats/25989/image059.gif" v:shapes="_x0000_i1064"> и рп-1 + рп.Алфавит А1 и называется полученным из алфавита А с помощью сжатия (или однократного сжатия).
Расположимбуквы нового алфавита А1 впорядке убывания их вероятностей и подвергнем сжатию алфавит А1; при этом мы придем калфавиту А2, которыйполучается из первоначального алфавита Ас помощью двукратного сжатия (а изалфавита А1 – с помощьюпростого или однократного сжатия). Ясно, что алфавит А2 будет содержать уже всего п – 2 буквы. Продолжая эту процедуру, мы будем приходить ко всеболее коротким
алфавитам; после (п– 2)-кратного сжатия мы придем к алфавиту Ап-2,содержащему уже всего две буквы.
Вот,например, как преобразуется с помощью последовательных сжатий рассмотренныйвыше алфавит, содержащий 6 букв, вероятности которых равны 0,4, 0,2, 0,2, 0,1,0,05 и 0,05:
№ буквы
Вероятности
исходный алфавит А
сжатые алфавиты
А1
А2
А3
А4
1
<img src="/cache/referats/25989/image060.gif" v:shapes="_x0000_s1109 _x0000_s1035 _x0000_s1031 _x0000_s1034 _x0000_s1036 _x0000_s1037 _x0000_s1038 _x0000_s1039 _x0000_s1040 _x0000_s1041 _x0000_s1042 _x0000_s1043 _x0000_s1044 _x0000_s1045 _x0000_s1046 _x0000_s1047 _x0000_s1048">
0,4
0,4
0,4
0,6
2
0,2
0,2
0,2
0,4
0,4
3
0,2
0,2
0,2
0,2
4
0,1
0,1
0,2
5
0,05
0,1
6
0,05
Табл.3
Условимся теперь приписывать двум буквам последнегоалфавита Ап-2кодовые обозначения 1 и 0. Далее, если кодовые обозначения уже приписаны всембуквам алфавита Aj, то буквам«предыдущего» алфавита Aj-1 (где,разумеется, А1-1 = А0– это исходный алфавит А), сохранившимся и в алфавите Aj, мы пишем те же кодовые обозначения,которые они имели в алфавите Aj-1;двум же буквам a’ и a’’ алфавита Aj,«слившимся» в одну букву b алфавита Aj-1, мы припишем обозначения,получившиеся из кодового обозначения буквы b добавлением цифр 1 и 0в конце. (Табл.4)
№ буквы
Вероятности
исходный алфавит А
сжатые алфавиты
А1
А2
А3
А4
1
<img src="/cache/referats/25989/image061.gif" v:shapes="_x0000_s1110 _x0000_s1051 _x0000_s1052 _x0000_s1053 _x0000_s1054 _x0000_s1055 _x0000_s1056 _x0000_s1057 _x0000_s1058 _x0000_s1059 _x0000_s1060 _x0000_s1061 _x0000_s1062 _x0000_s1063 _x0000_s1064 _x0000_s1065 _x0000_s1066"> 0
0,4 0
0,4 0
0,4 0
0,6 1
2
0,2 10
0,2 10
0,2 10
0,4 11
0,4 0
3
0,2 111
0,2 111
0,2 111
0,2 10
4
0,1 1101
0,1 1101
0,2 110
5
0,05 11001
0,1 1100
6
0,05 11000
Табл.4
Легко видеть, что из самого построения получаемоготаким образом кода Хафмана вытекает,что он удовлетворяет общему условию: никакое кодовое обозначение не являетсяздесь началом другого, более длинного кодового обозначения. Заметим еще, чтокодирование некоторого алфавита по методу Хафмана (так же, впрочем, как и пометоду Шеннона – Фано) не является однозначной процедурой.
Так, например, на любом этапе построения кода можно,разумеется, заменить цифру 1 на цифру 0 и наоборот; при этом мы получим два разныхкода (отличающихся весьма несущественно друг от друга). Но помимо того в некоторыхслучаях можно построить и несколько существенно различающихся кодов Хафмана;так, например, в разобранном выше примере можно строить код и в соответствии соследующей таблицей:
№ буквы
Вероятности
исходный алфавит А
сжатые алфавиты
А1
А2
А3
А4
1
<img src="/cache/referats/25989/image062.gif" v:shapes="_x0000_s1111 _x0000_s1069 _x0000_s1070 _x0000_s1071 _x0000_s1072 _x0000_s1073 _x0000_s1074 _x0000_s1075 _x0000_s1076 _x0000_s1077 _x0000_s1078 _x0000_s1079 _x0000_s1080 _x0000_s1081 _x0000_s1082 _x0000_s1083 _x0000_s1084"> 11
0,4 11
0,4 11
0,4 0
0,6 1
2
0,2 01
0,2 01
0,2 10
0,4 11
0,4 0
3
0,2 00
0,2 00
0,2 01
0,2 10
4
0,1 100
0,1 101
0,2 00
5
0,05 1011
0,1 100
6
0,05 1010
Табл.5
Получаемый при этом новый код также является кодомХафмана, но длины имеющихся кодовых обозначений теперь уже оказываются совсемдругими. Отметим, что среднее число элементарных сигналов, приходящихсяна одну букву, для обоих построенных кодов Хафмана оказывается точноодинаковым: в первом случае оно равно
<img src="/cache/referats/25989/image064.gif" v:shapes="_x0000_i1065">
а во втором – равно
<img src="/cache/referats/25989/image066.gif" v:shapes="_x0000_i1066">
Можнопоказать, что код Хафмана всегда является самым экономичным из всехвозможных в том смысле, что ни для какогодругого метода кодирования букв некоторого алфавита среднее число элементарныхсигналов, приходящихся на одну букву, не может быть меньше того, какоеполучается при кодировании по методу Хафмана (отсюда, разумеется, сразувытекает и то, что для любых двух кодов Хафмана средняя длина кодовогообозначения должна быть точно одинаковой – ведь оба они являются наиболееэкономными).
Рассуждения, приведенные в пунктах 1.2 и 1.3 полностьюреализуются при решении задач (примертакой задачи приведен в приложении А).
2. Энтропия конкретных типовсообщений.
2.1 Основнаятеорема о кодировании.
Достигнутая в рассмотренных выше примерах степень близости среднего числадвоичных знаков, приходящихся на одну букву сообщения, к значению Н может быть еще сколь угодно увеличенапри помощи перехода к кодированию все более и более длинных блоков. Этовытекает из следующего общего утверждения, которое мы будем в дальнейшемназывать основной теоремой о кодировании, точнее, основной теоремой окодировании при отсутствии помех: прикодировании сообщения, разбитого на N-буквенные блоки, можно,выбрав N достаточно большим, добиться того,чтобы среднее число двоичных элементарных сигналов, приходящихся на одну буквуисходного сообщения, было сколь угодно близко к Н. Кодирование сразудлинных блоков имеет значительные преимущества при наличии помех,препятствующих работе линии связи.
Ввиду большойважности сформулированной здесь основной теоремы о кодировании мы приведем нижеее доказательство, основанное на использовании метода кодирования Шеннона — Фано. Предположим сначала, что при составляющем основу метода Шеннона – Фанопоследовательном делении совокупности кодируемых букв (под которыми могутпониматься также целые «блоки») на все меньшие и меньшие группы нам каждый разудается добиться того, чтобы вероятности двух получаемых групп были точно равнымежду собой. В таком случае после первого деления мы придем к группам, имеющимсуммарную вероятность ½, после второго – к группам суммарной вероятности¼, …, после l-го деления – к группам суммарнойвероятности 1/2l. При этом l-значное кодовое обозначении будут иметь те буквы, которыеоказываются выделенными в группу из одного элемента ровно после l делений; иначе говоря, при выполнении этого условия длина liкодового обозначения будет связана с вероятностью рiсоответствующей буквы формулой
<img src="/cache/referats/25989/image068.gif" v:shape