Коды Шеннона – Фано и Хафмана

ВВЕДЕНИЕ
Новые направления, возникшие в математике в ХХве­ке, обычно оперируют со сложными понятиями и представлениями, которые струдом поддаются попу­ляризации. На этом фоне весьма значительна заслугавыдающегося американского математика и инженера Клода Шеннона, который в1947—1948 годах, исходя из элементарных соображений, открыл новую область ма­тематики- теорию информации. Толчком к созда­нию новой науки были чисто техническиепроблемы передачи информации по телеграфным и телефонным проводам, однако кнастоящему времени благодаря об­щему характеру теория информации находитприменение в исследованиях, относящихся к передаче и сохране­нию любойинформации в природе и технике.
В конце сороковых годов, на заре развития теории информации, идеиразработки новых эффективных способов кодирования информации носились в возду­хе.Исследователи занимались вопросами энтропии, содержимого информации иизбыточности. Интерес­но, что эти первоначальные работы в области сжатияинформации велись до появления современного циф­рового компьютера. Сегоднятеория информации раз­вивается параллельно с программированием, но в то времяидея разработки алгоритмов, использующих двоичную арифметику для кодированиясимволов, была значительным шагом вперед.
Одними из первых алгоритмов эффективного кодиро­вания информации былиалгоритмы Шеннона – Фано и Хафмана.
В данной работе рассмотрены базовые понятия эн­тропиии информации, а также описаны принципы кодирования сообщений по Шеннону – Фанои Хафману, показана их важ­ная роль при передаче информации по линиям связи.
Но линии связи, для которых были разработаныэти методы кодирования информации, уже в прошлом. К счастью, для принциповШеннона — Фано и Хафмана нашли применение и в современном мире: для сжатияинформации.  Архиваторы PKZIP, ARJ, а также часть всем нам хорошоизвестного стандарта JPEG(сжатие графической информации спотерями) работают именно на этих принципах.
Коды Шеннона – Фано и Хафмана преподаются вовсех технических ВУЗах мира и, кроме того, входят в программу для углубленногоизучения информатики в школе.
Поэтому изучение методов кодирования Шеннона –Фано и Хафмана является актуальным.
Цельданной работы — изучить принципы кодирования информацииШеннона — Фано и Хафмана и применение их при решении задач.
Задачасостоит в том, чтобы изучить энтропии и избыточностьконкретных типов сообщений для последующего применения к ним принципов Шеннона- Фано и Хафмана.
1. Информация и кодирование. КодыШеннона — Фано и Хафмана.
1.1 Информацияи кодирование.
Слово «информация» известно в наше время каждому.Происходит оно от латинского «informatio»,что означает – разъяснение, сообщение, осведомленность. Однако в постоянноеупотребление оно вошло не так давно, в середине двадцатого века, с подачи КлодаШеннона. Он ввел этот термин в узком техническом смысле применительно к теориисвязи или передачи кодов, которая получила название «Теория информации». Здесь важны не любые сведения, а лишь те, которыеснимают полностью или уменьшают существующую неопределенность. Философское,и поэтому более широкое определение этого термина дает один из основателейинформатики, известный американский ученый Норберт Винер: «Информация – это обозначение содержания, черпаемого нами из внешнегомира в процессе нашего приспособления к нему и приведение в соответствие с нимнашего мышления». Разумеется, это далеко не единственные в своем родеопределения информации.
В настоящее время этот термин имеет более глубокий имногогранный смысл. Во многом  оставаясьинтуитивным, он получает разные смысловые наполнения в разных отрасляхчеловеческой деятельности:
v    
v    
v    
v    
Такое разнообразие подходов не случайно, а следствиетого, что выявилась необходимость осознанной организации процессов движения иобработки того, что имеет общее название – информация.
Для дальнейшего рассмотрения нам необходимо то понятиеинформации, которое подразумевает передачу информационных сообщений по линиямсвязи. Рассмотрим общую схему передачи сообщений; для определенности будемговорить, например, о телеграфии. На одном конце линии отправитель подаетнекоторое сообщение, записанное припомощи любого из известных нам алфавитов или цифр, или  и букв и цифр вместе взятых. Для передачитакого рода сообщений используются последовательности сигналов постоянного тока,некоторые характеристики которого телеграфист может менять по своему усмотрению,воспринимаемых вторым телеграфистом на приемном конце линии. Простейшимиразличимыми сигналами, широко используемыми на практике, является посылкатока (т.е. включение его на некоторое вполне определенное время) иотсутствие посылки – пауза (выключение тока на то же время); при помощиодних только этих двух сигналов уже можно передать любое сообщение, еслиусловиться заменять каждую букву или цифру определенной комбинацией посылоктока и пауз.
В технике связи правило, сопоставляющее каждомупередаваемому сообщению некоторую комбинацию сигналов, обычно называется кодом(в случае телеграфии – телеграфным кодом), а сама операция перевода сообщения впоследовательность различных сигналов – кодированиемсообщения. Под «кодом» будетпониматься такая совокупность пкодовых обозна­чений, сопоставляемых пбуквам алфавита, для которой выполняется условие: никакое кодовое обозначениеодной буквы не совпадает с началом какого-либо другого более длинного кодовогообозначения, т.е. коды должны быть однозначнодекодируемыми.При этом коды, использующие только два различных элементарныхсигнала (например, посылку тока и паузу), называются двоичными кодами. Внекоторых телеграфных аппаратах кроме простого включения и выключения токаможно также изменять его направление на обратное. При этом появляетсявозможность вместо посылок тока и пауз использовать в качестве основныхсигналов посылку тока в двух различных направлениях или же использовать сразутри различных элементарных сигнала одной и той же длительности – посылку тока водном направлении, посылку тока в другом направлении и паузу (такой способкодирования называется троичным кодом). Возможны также еще более сложныетелеграфные аппараты, в которых посылки тока различаются не только опнаправлению, но и по силе тока; тем самым мы получаем возможность сделать числоразличных элементарных сигналов еще большим. Увеличение числа разныхэлементарных сигналов позволяет сделать код более сжатым. Однако вместе с темоно усложняет и удорожает систему передачи, так что в технике все жепредпочтительно используются коды с малым числом элементарных сигналов.
Пусть имеется сообщение, записанное при помощинекоторого «алфавита», содержащего п«букв». Требуется «закодировать» это сообщение, т.е. указать правило,сопоставляющее каждому такому сообщению определенную последовательность из т различных «элементарных сигналов»,составляющих «алфавит» передачи. Мы будем считать кодирование тем более выгодным,чем меньше элементарных сигналов приходится затратить на передачу сообщения.Если считать, что каждый из элементарных сигналов продолжается одно и то жевремя, то наиболее выгодный код позволит затратить на передачу сообщения меньшевсего времени.
Главным свойством случайных событий является отсутствие полнойуверенности в их наступлении, создаю­щее известную неопределенность привыполнении связан­ных с этими событиями опытов. Однако совершенно ясно, чтостепень этой неопределенности в различных случаях будет совершенно разной. Дляпрактики важно уметь численно оценивать сте­пень неопределенности самыхразнообраз­ных опытов, чтобы иметь возможность сравнить их с этой стороны.Рассмотрим два независимых опыта  и а также сложный опыт  и имеет k равновероятных исходов, а опыт  имеет l равновероят­ных исходов. Очевидно, что неопределенностьопыта  большенеопределенности опыта здесь добавляется ещенеопределенность исхода опыта  и

Условиям   при  удовлетворяет толькоодна функция —

Рассмотрим опыт А, состоящий изопытов  и имеющих вероятности А будет равна

Это последнее число будем называть энтропией опыта  и обозначать через
Если число букв в «алфавите» равно п, а число используемых элементарных сигналов равно т, то при любом методе кодирования среднее число элементарных сигналов,приходящихся на одну букву алфавита, неможет быть меньше чем ; однако он всегда может быть сделано сколь угодно близким к этому отношению, еслитолько отдельные кодовые обозначения сопоставлять сразу достаточно длинными«блоками», состоящими из большого числа букв.
Мы рассмотрим здесь лишь простейший случай сообщений,записанных при помощи некоторых п«букв», частоты проявления которых на любом месте сообщения полностьюхарактеризуется вероятностями р1,р2, … …, рп, где, разумеется, р1 + р2 + … + рп= 1, при котором вероятность pi проявления i-й буквы  на любомместе сообщения предполагается одной и той же, вне зависимости от того, какиебуквы стояли на всех предыдущих местах, т.е. последовательные буквы сообщения независимыдруг от друга. На самом деле в реальных сообщениях это чаще бывает не так; вчастности, в русском языке вероятность появления той или иной буквы существеннозависит от предыдущей буквы. Однако строгий учет взаимной зависимости буквсделал бы все дельнейшие рассмотрения очень сложными, но никак не изменитбудущие результаты.
Мы будем пока рассматривать двоичные коды;обобщение полученных при этом результатов на коды, использующие произвольноечисло т элементарных сигналов, является,как всегда, крайне простым. Начнем с простейшего случая кодов, сопоставляющихотдельное кодовое обозначение – последовательность цифр 0 и 1 – каждой «букве»сообщения. Каждому двоичному коду для п-буквенногоалфавита может быть сопоставлен некоторый метод отгадывания некоторогозагаданного числа х, непревосходящего п, при помощивопросов, на которые отвечается  лишь«да» (1) или «нет» (0), что и приводит нас к двоичному коду. При заданныхвероятностях р1, р2, … …, рп отдельных букв передача многобуквенного сообщениянаиболее экономный код будет тот, для которого при этих именно вероятностях п значений х среднее значение числа задаваемых вопросов (двоичных знаков: 0 и1 или элементарных сигналов) оказывается наименьшим.
Прежде всего среднее число двоичных элементарныхсигналов, приходящихся в закодированном сообщении на одну букву исходногосообщения, не может быть меньше Н,где Н = — p1 logp1 –p2 logp2 — … — pnlogpn – энтропияопыта, состоящего в распознавании одной буквы текста (или, короче, простоэнтропия одной буквы). Отсюда сразу следует, что при любом методе кодирования для записи длинного сообщения из М буквтребуется не меньше чем МН двоичных знаков, и никак не может превосходитьодного бита.
Если вероятности р1,р2, … …, рп  не все равны между собой, то Н
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

 Это значениезаметно меньше, чем 3, и не очень далеко от энтропии

Аналогично этому для рассмотрения примера18-буквенного алфавита наилучший равномерный код состоит из пятизначных кодовыхобозначений (так как 24  
Последнее значение заметно меньше, чем 5, — и уже ненамного отличается от величины

    Особенновыгодно бывает кодировать по методу Шеннона – Фано не отдельные буквы, а сразуцелые блоки из нескольких букв. Правда, при этом все равно невозможно превзойтипредельное значение Н двоичных знаковна одну букву сообщения. Рассмотрим, например, случай, когда имеются лишь дверазличные буквы А и Б, имеющие вероятности р(А)= 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
Среднее значение длины кодового обозначения здесьравно

так что на одну букву алфавита здесь приходится в среднем  двоичных знаков – лишьна 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% больше значения  дв.зн./букву.
    В случае ещебольшей разницы в вероятностях букв А иБ приближение к минимально возможномузначению Н дв.зн./букву можетнесколько менее быстрым, но оно проявляется не менее наглядно. Так, при р(А)= 0,89 и р(Б) = 0,11 это значение равно – 0,89 log0,89 –0,11 log0,11 ≈ 0,5дв.зн./букву, а равномерный код  (равносильныйприменению кода Шеннона – Фано к совокупности двух имеющихся букв) требуетзатраты одного двоичного знака на каждую букву – в два раза больше. Нетруднопроверить, что применение кода Шеннона – Фано к всевозможным двухбуквеннымкомбинациям здесь приводит к коду, в котором на каждую букву приходится всреднем 0,66 двоичных знаков, применение к трехбуквенным комбинациям — 0,55, ак четырехбуквенным блокам — в среднем 0,52 двоичных знаков – всего на 4% большеминимального значения 0,50 дв.зн./букву.
    1.3 Коды Хафмана.
    Близок к кодуШеннона – Фано, но еще выгоднее, чем последний, так называемый код Хафмана.Построение этого кода опирается на простое преобразование используемогоалфавита, называемое сжатиемалфавита. Пусть мы имеем алфавит А,содержащий буквы

Условимся теперь неразличать между собой две наименее вероятные буквы нашего алфавита, т.е.будем считать, что ап-1и ап – это одна и та жебуква b нового алфавита А1,содержащего теперь уже буквы  и b (т.е. ап-1 или ап), вероятности появлениякоторых в сообщении соответственно равны  и рп-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

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
      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
       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
Получаемый при этом новый код также является кодомХафмана, но длины имеющихся кодовых обозначений теперь уже оказываются совсемдругими. Отметим, что среднее число элементарных сигналов, приходящихсяна одну букву, для обоих построенных кодов Хафмана оказывается точноодинаковым: в первом случае оно равно

а во втором – равно

    Можнопоказать, что код Хафмана всегда является самым экономичным из всехвозможных в том смысле, что ни для какогодругого метода кодирования букв некоторого алфавита среднее число элементарныхсигналов, приходящихся на одну букву, не может быть меньше того, какоеполучается при кодировании по методу Хафмана (отсюда, разумеется, сразувытекает и то, что для любых двух кодов Хафмана средняя длина кодовогообозначения должна быть точно одинаковой – ведь оба они являются наиболееэкономными).
Рассуждения, приведенные в пунктах 1.2 и 1.3 полностьюреализуются при решении  задач (примертакой задачи приведен в приложении А).
2. Энтропия конкретных типовсообщений.    
2.1 Основнаятеорема о кодировании.      
Достигнутая в рассмотренных  выше примерах степень близости среднего числадвоичных знаков, приходящихся на одну букву сообщения, к значению Н может быть еще сколь угодно увеличенапри помощи перехода к кодированию все более и более длинных блоков. Этовытекает из следующего общего утверждения, которое мы будем в дальнейшемназывать основной теоремой о кодировании, точнее, основной теоремой окодировании при отсутствии помех: прикодировании сообщения, разбитого на N-буквенные блоки, можно,выбрав N достаточно большим, добиться того,чтобы среднее число двоичных элементарных сигналов, приходящихся на одну буквуисходного сообщения, было сколь угодно близко к Н. Кодирование сразудлинных блоков имеет значительные преимущества при наличии помех,препятствующих работе линии связи.
    Ввиду большойважности сформулированной здесь основной теоремы о кодировании мы приведем нижеее доказательство, основанное на использовании метода кодирования Шеннона — Фано. Предположим сначала, что при составляющем основу метода Шеннона – Фанопоследовательном делении совокупности кодируемых букв (под которыми могутпониматься также целые «блоки») на все меньшие и меньшие группы нам каждый разудается добиться того, чтобы вероятности двух получаемых групп были точно равнымежду собой. В таком случае после первого деления мы придем к группам, имеющимсуммарную вероятность ½, после второго – к группам суммарной вероятности¼, …, после l-го деления – к группам суммарнойвероятности 1/2l. При этом l-значное кодовое обозначении будут иметь те буквы, которыеоказываются выделенными в группу из одного элемента ровно после l делений; иначе говоря, при выполнении этого условия длина liкодового обозначения будет связана с вероятностью рiсоответствующей буквы формулой