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

Исследователи занимались вопросами энтропии, содержимого информации и избыточности.

Интересно, что эти первоначальные работы в области сжатия информации велись до появления современного цифрового компьютера.

Сегодня теория информации развивается параллельно с программированием, но в то время идея разработки алгоритмов, использующих двоичную арифметику для кодирования символов, была значительным шагом вперед.

Одними из первых алгоритмов эффективного кодирования информации были алгоритмы Шеннона – Фано и Хафмана. В данной работе рассмотрены базовые понятия энтропии и информации, а также описаны принципы кодирования сообщений по Шеннону – Фано и Хафману, показана их важная роль при передаче информации по линиям связи. Но линии связи, для которых были разработаны эти методы кодирования информации, уже в прошлом. К счастью, для принципов Шеннона - Фано и Хафмана нашли применение и в современном мире: для сжатия информации.

Архиваторы PKZIP , ARJ , а также часть всем нам хорошо известного стандарта JPEG (сжатие графической информации с потерями) работают именно на этих принципах. Коды Шеннона – Фано и Хафмана преподаются во всех технических ВУЗах мира и, кроме того, входят в программу для углубленного изучения информатики в школе.

Поэтому изучение методов кодирования Шеннона – Фано и Хафмана является актуальным. Цель данной работы - изучить принципы кодирования информации Шеннона - Фано и Хафмана и применение их при решении задач.

Задача состоит в том, чтобы изучить энтропии и избыточность конкретных типов сообщений для последующего применения к ним принципов Шеннона - Фано и Хафмана. 1. Информация и кодирование. Коды Шеннона - Фано и Хафмана. 1.1 Информация и кодирование. Слово «информация» известно в наше время каждому.

Происходит оно от латинского « informatio », что означает – разъяснение, сообщение, осведомленность.

Однако в постоянное употребление оно вошло не так давно, в середине двадцатого века, с подачи Клода Шеннона. Он ввел этот термин в узком техническом смысле применительно к теории связи или передачи кодов, которая получила название «Теория информации». Здесь важны не любые сведения, а лишь те, которые снимают полностью или уменьшают существующую неопределенность.

Философское, и поэтому более широкое определение этого термина дает один из основателей информатики, известный американский ученый Норберт Винер: «Информация – это обозначение содержания, черпаемого нами из внешнего мира в процессе нашего приспособления к нему и приведение в соответствие с ним нашего мышления». Разумеется, это далеко не единственные в своем роде определения информации. В настоящее время этот термин имеет более глубокий и многогранный смысл. Во многом оставаясь интуитивным, он получает разные смысловые наполнения в разных отраслях человеческой деятельности: v v v v Такое разнообразие подходов не случайно, а следствие того, что выявилась необходимость осознанной организации процессов движения и обработки того, что имеет общее название – информация. Для дальнейшего рассмотрения нам необходимо то понятие информации, которое подразумевает передачу информационных сообщений по линиям связи.

Рассмотрим общую схему передачи сообщений; для определенности будем говорить, например, о телеграфии. На одном конце линии отправитель подает некоторое сообщение, записанное при помощи любого из известных нам алфавитов или цифр, или и букв и цифр вместе взятых. Для передачи такого рода сообщений используются последовательности сигналов постоянного тока, некоторые характеристики которого телеграфист может менять по своему усмотрению, воспринимаемых вторым телеграфистом на приемном конце линии.

Простейшими различимыми сигналами, широко используемыми на практике, является посылка тока (т.е. включение его на некоторое вполне определенное время) и отсутствие посылки – пауза (выключение тока на то же время); при помощи одних только этих двух сигналов уже можно передать любое сообщение, если условиться заменять каждую букву или цифру определенной комбинацией посылок тока и пауз. В технике связи правило, сопоставляющее каждому передаваемому сообщению некоторую комбинацию сигналов, обычно называется кодом (в случае телеграфии – телеграфным кодом), а сама операция перевода сообщения в последовательность различных сигналов – кодированием сообщения. Под «кодом» будет пониматься такая совокупность п кодовых обозначений, сопоставляемых п буквам алфавита, для которой выполняется условие: никакое кодовое обозначение одной буквы не совпадает с началом какого-либо другого более длинного кодового обозначения, т.е. коды должны быть однозначно декодируемыми. При этом коды, использующие только два различных элементарных сигнала (например, посылку тока и паузу), называются двоичными кодами. В некоторых телеграфных аппаратах кроме простого включения и выключения тока можно также изменять его направление на обратное. При этом появляется возможность вместо посылок тока и пауз использовать в качестве основных сигналов посылку тока в двух различных направлениях или же использовать сразу три различных элементарных сигнала одной и той же длительности – посылку тока в одном направлении, посылку тока в другом направлении и паузу (такой способ кодирования называется троичным кодом). Возможны также еще более сложные телеграфные аппараты, в которых посылки тока различаются не только оп направлению, но и по силе тока; тем самым мы получаем возможность сделать число различных элементарных сигналов еще большим.

Увеличение числа разных элементарных сигналов позволяет сделать код более сжатым.

Однако вместе с тем оно усложняет и удорожает систему передачи, так что в технике все же предпочтительно используются коды с малым числом элементарных сигналов. Пусть имеется сообщение, записанное при помощи некоторого «алфавита», содержащего п «букв». Требуется «закодировать» это сообщение, т.е. указать правило, сопоставляющее каждому такому сообщению определенную последовательность из т различных «элементарных сигналов», составляющих «алфавит» передачи. Мы будем считать кодирование тем более выгодным, чем меньше элементарных сигналов приходится затратить на передачу сообщения. Если считать, что каждый из элементарных сигналов продолжается одно и то же время, то наиболее выгодный код позволит затратить на передачу сообщения меньше всего времени.

Главным свойством случайных событий является отсутствие полной уверенности в их наступлении, создающее известную неопределенность при выполнении связанных с этими событиями опытов.

Однако совершенно ясно, что степень этой неопределенности в различных случаях будет совершенно разной. Для практики важно уметь численно оценивать степень неопределенности самых разнообразных опытов, чтобы иметь возможность сравнить их с этой стороны.

Рассмотрим два независимых опыта и а также сложный опыт и имеет k равновероятных исходов, а опыт имеет l равновероятных исходов.

Очевидно, что неопределенность опыта больше неопределенности опыта здесь добавляется еще неопределенность исхода опыта и Условиям при удовлетворяет только одна функция - Рассмотрим опыт А, состоящий из опытов и имеющих вероятности А будет равна Это последнее число будем называть энтропией опыта и обозначать через Если число букв в «алфавите» равно п, а число используемых элементарных сигналов равно т, то при любом методе кодирования среднее число элементарных сигналов, приходящихся на одну букву алфавита, не может быть меньше чем ; однако он всегда может быть сделано сколь угодно близким к этому отношению, если только отдельные кодовые обозначения сопоставлять сразу достаточно длинными «блоками», состоящими из большого числа букв. Мы рассмотрим здесь лишь простейший случай сообщений, записанных при помощи некоторых п «букв», частоты проявления которых на любом месте сообщения полностью характеризуется вероятностями р 1 , р 2 , … …, р п , где, разумеется, р 1 + р 2 + … + р п = 1, при котором вероятность p i проявления i -й буквы на любом месте сообщения предполагается одной и той же, вне зависимости от того, какие буквы стояли на всех предыдущих местах, т.е. последовательные буквы сообщения независимы друг от друга. На самом деле в реальных сообщениях это чаще бывает не так; в частности, в русском языке вероятность появления той или иной буквы существенно зависит от предыдущей буквы.

Однако строгий учет взаимной зависимости букв сделал бы все дельнейшие рассмотрения очень сложными, но никак не изменит будущие результаты. Мы будем пока рассматривать двоичные коды; обобщение полученных при этом результатов на коды, использующие произвольное число т элементарных сигналов, является, как всегда, крайне простым.

Начнем с простейшего случая кодов, сопоставляющих отдельное кодовое обозначение – последовательность цифр 0 и 1 – каждой «букве» сообщения.

Каждому двоичному коду для п-буквенного алфавита может быть сопоставлен некоторый метод отгадывания некоторого загаданного числа х, не превосходящего п, при помощи вопросов, на которые отвечается лишь «да» (1) или «нет» (0) , что и приводит нас к двоичному коду. При заданных вероятностях р 1 , р 2 , … …, р п отдельных букв передача многобуквенного сообщения наиболее экономный код будет тот, для которого при этих именно вероятностях п значений х среднее значение числа задаваемых вопросов (двоичных знаков: 0 и 1 или элементарных сигналов) оказывается наименьшим.

Прежде всего среднее число двоичных элементарных сигналов, приходящихся в закодированном сообщении на одну букву исходного сообщения, не может быть меньше Н, где Н = - p 1 log p 1 – p 2 log p 2 - … - p n log p n – энтропия опыта, состоящего в распознавании одной буквы текста (или, короче, просто энтропия одной буквы). Отсюда сразу следует, что при любом методе кодирования для записи длинного сообщения из М букв требуется не меньше чем МН двоичных знаков, и никак не может превосходить одного бита. Если вероятности р 1 , р 2 , … …, р п не все равны между собой, то Н log n ; поэтому естественно думать, что учет статистических закономерностей сообщения может позволить построить код более экономичный, чем наилучший равномерный код, требующий не менее М log n двоичных знаков для записи текста из М букв. 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-я часть будет состоять лишь из одной буквы.

Разумеется, количество цифр в различных обозначениях при этом оказывается различным (в частности, во втором из разобранных примеров он меняется от двух до семи), т. е. код Шеннона – Фано является неравномерным.

Нетрудно понять, однако, что никакое кодовое обозначение здесь не может оказаться началом другого, более длинного обозначения; поэтому закодированное сообщение всегда может быть однозначно декодировано. В результате, среднее значение длины такого обозначения все же оказывается лишь немногим большим минимального значения Н, допускаемого соображениями сохранения количества информации при кодировании. Так, для рассмотренного выше примера 6-буквенного алфавита наилучший равномерный код состоит из трехзначных кодовых обозначений (ибо 2 2 3 ), и поэтому в нем на каждую букву исходного сообщения приходится ровно 3 элементарных сигнала; при использовании же кода Шеннона – Фано среднее число элементарных сигналов, приходящихся на одну букву сообщения, равно Это значение заметно меньше, чем 3, и не очень далеко от энтропии Аналогично этому для рассмотрения примера 18-буквенного алфавита наилучший равномерный код состоит из пятизначных кодовых обозначений (так как 2 4 5 ); в случае же кода Шеннона – Фано имеются буквы, кодируемые даже семью двоичными сигналами, но зато среднее число элементарных сигналов, приходящихся на одну букву, здесь равно Последнее значение заметно меньше, чем 5, - и уже не намного отличается от величины Особенно выгодно бывает кодировать по методу Шеннона – Фано не отдельные буквы, а сразу целые блоки из нескольких букв.

Правда, при этом все равно невозможно превзойти предельное значение Н двоичных знаков на одну букву сообщения.

Рассмотрим, например, случай, когда имеются лишь две различные буквы А и Б, имеющие вероятности р(А) = 0,7 и р(Б) = 0,3; тогда H = - 0,7 log 0,7 – 0,3 log 0,3 = 0,881… Применение метода Шеннона – Фано к исходному двухбуквенному алфавиту здесь оказывается бесцельным: оно приводит нас лишь к простейшему равномерному коду

Применяя же метод Шеннона – Фано к кодированию всевозможных двухбуквенных комбинаций (вероятность которых определяется правилом умножения вероятностей для независимых событий), мы придем к следующему коду:

Нетрудно проверить, что применение кода Шеннона – Фано к всевозможным двухбуквенным комбинациям здесь приводит к коду, в котором на каждую букву приходится в среднем 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

№ буквы	Вероятности
исходный алфавит А	сжатые алфавиты
А 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

Заметим еще, что кодирование некоторого алфавита по методу Хафмана (так же, впрочем, как и по методу Шеннона – Фано) не является однозначной процедурой. Так, например, на любом этапе построения кода можно, разумеется, заменить цифру 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

Отметим, что среднее число элементарных сигналов, приходящихся на одну букву, для обоих построенных кодов Хафмана оказывается точно одинаковым: в первом случае оно равно а во втором – равно Можно показать, что код Хафмана всегда является самым экономичным из всех возможных в том смысле, что ни для какого другого метода кодирования букв некоторого алфавита среднее число элементарных сигналов, приходящихся на одну букву, не может быть меньше того, какое получается при кодировании по методу Хафмана (отсюда, разумеется, сразу вытекает и то, что для любых двух кодов Хафмана средняя длина кодового обозначения должна быть точно одинаковой – ведь оба они являются наиболее экономными). Рассуждения, приведенные в пунктах 1.2 и 1.3 полностью реализуются при решении задач (пример такой задачи приведен в приложении А). 2. Энтропия конкретных типов сообщений. 2.1 Основная теорема о кодировании.

Достигнутая в рассмотренных выше примерах степень близости среднего числа двоичных знаков, приходящихся на одну букву сообщения, к значению Н может быть еще сколь угодно увеличена при помощи перехода к кодированию все более и более длинных блоков. Это вытекает из следующего общего утверждения, которое мы будем в дальнейшем называть основной теоремой о кодировании, точнее, основной теоремой о кодировании при отсутствии помех: при кодировании сообщения, разбитого на N -буквенные блоки, можно, выбрав N достаточно большим, добиться того, чтобы среднее число двоичных элементарных сигналов, приходящихся на одну букву исходного сообщения, было сколь угодно близко к Н. Кодирование сразу длинных блоков имеет значительные преимущества при наличии помех, препятствующих работе линии связи. Ввиду большой важности сформулированной здесь основной теоремы о кодировании мы приведем ниже ее доказательство, основанное на использовании метода кодирования Шеннона - Фано.

Предположим сначала, что при составляющем основу метода Шеннона – Фано последовательном делении совокупности кодируемых букв (под которыми могут пониматься также целые «блоки») на все меньшие и меньшие группы нам каждый раз удается добиться того, чтобы вероятности двух получаемых групп были точно равны между собой. В таком случае после первого деления мы придем к группам, имеющим суммарную вероятность ½, после второго – к группам суммарной вероятности ¼, …, после l -го деления – к группам суммарной вероятности 1/2 l . При этом l -значное кодовое обозначении будут иметь те буквы, которые оказываются выделенными в группу из одного элемента ровно после l делений; иначе говоря, при выполнении этого условия длина l i кодового обозначения будет связана с вероятностью р i соответствующей буквы формулой В общем случае величина – log p i , где p i – вероятность i -й буквы алфавита, целым числом не будет, поэтому длина l i кодового обозначения i -й буквы не сможет быть равна log p i . Поскольку при кодировании по методу Шеннона – Фано мы последовательно делим наш алфавит на группы, по возможности близкой суммарной вероятности, то длина кодового обозначения i -й буквы при таком кодировании будет близка к – log p i . Обозначим, в этой связи, через l i первое целое число, не меньше чем – log p i : (А) Последнее неравенство можно переписать еще так: или (Б) Здесь отметим, что в случае любых п чисел (1) существует двоичный код, для которого эти числа являются длинами кодовых обозначений, сопоставляемых п буквам некоторого алфавита.

Среднее число l двоичных сигналов, приходящихся на одну букву исходного сообщения (или, средняя длина кодового обозначения) дается суммой Умножим теперь задающее величину l i неравенство (А) на p i , сложим все полученные таким образом неравенства, отвечающие значениям i = 1, 2, …, п, и учтем, что где - энтропия опыта p 1 + p 2 + … + p n = 1. В результате получаем, что Применим это неравенство к случаю, когда описанный выше метод используется для кодирования всевозможных N -буквенных блоков (которые можно считать буквами нового алфавита). В силу предположения о независимости последовательных букв сообщения энтропия опыта Следовательно, средняя длина l N кодового обозначения N -буквенного блока удовлетворяет неравенствам Но при кодировании сразу N -буквенных блоков среднее число l двоичных элементарных сигналов, приходящихся на одну букву сообщения, будет равно средней длине l N кодового обозначения одного блока, деленной на число N букв в блоке: Поэтому при таком кодировании то есть здесь среднее число элементарных сигналов, приходящихся на одну букву, отличается от минимального значения Н не больше, чем на Приведенное доказательство может быть применено также и к более общему случаю, когда последовательные буквы текста являются взаимно зависимыми. При этом придется только неравенство для величины l N писать в виде где - энтропия N -буквенного блока, которая в случае зависимости букв сообщения друг от друга всегда будет меньше чем NH (ибо и значит, в этом более общем случае при (при безграничном увеличении длины блоков) среднее число элементарных сигналов, затрачиваемых на передачу одной буквы, неограниченно приближается к величине есть «удельная энтропия», приходящаяся на одну букву многобуквенного текста.

Существование предела следует из неравенств является монотонно не возрастающей последовательностью положительных (больших 0) чисел. Все предыдущее утверждения легко переносятся также и на случай т-ичных кодов, использующих т элементарных сигналов. Так, для построения т-ичных кодов Шеннона – Фано надо лишь разбивать группы символов не на две, а на т частей по возможности близкой вероятности, а для построения т-ичного кода Хаффмана надо использовать операцию сжатия алфавита, при которой каждый раз сливаются не две, а т букв исходного алфавита, имеющих наименьшие вероятности. Ввиду важности кодов Хаффмана, остановимся на последнем вопросе чуть подробнее.

Сжатие алфавита, при котором т букв заменяются на одну, приводит к уменьшению числа букв на т – 1; так как для построения т-ичного кода, очевидно, требуется, чтобы последовательность «сжатий» в конце концов привела нас к алфавиту из т букв (сопоставляемых т сигналам кода), то необходимо, чтобы число п букв первоначального алфавита было представимо в виде n = m + k ( m - 1), где k – целое число. Этого, однако, всегда можно добиться, добавив, если нужно, к первоначальному алфавиту еще несколько «фиктивных букв», вероятности которых считаются равными нулю. После этого построение т-ичного кода Хаффмана и доказательство его оптимальности (среди всех т-ичных кодов) проводятся уже точно так же, как и случае двоичного кода. Так, например, в случае уже рассматривавшегося выше алфавита из 6 букв, имеющих вероятности 0,4, 0,2, 0,2, 0,1, 0,05, и 0,05 для построения троичного кода Хаффмана, надо присоединить к нашему алфавиту еще одну букву нулевой вероятности и далее поступать так, как указано ниже:

№ буквы	вероятности и кодовые обозначения
исходный алфавит	сжатые алфавиты
1	0,4 0	0,4 0	0,4 0
2	0,2 2	0,2 2	0,4 1
3	0,2 10	0,2 10	0,2 2
4	0,1 11	0,1 11
5	0,05 120	0,1 12
6	0,05 121
7	0 -

Повторяя рассуждения для случая т = 2, легко получить следующий результат (называемый основной теоремой о кодировании для т-ичных кодов): при любом методе кодирования, использующем т-ичный код, среднее число элементарных сигналов, приходящихся на одну букву сообщения, никогда не может быть меньше отношения (где Н – энтропия одной буквы сообщения); однако оно всегда может быть сделано сколь угодно близким к этой величине, если кодировать сразу достаточно длинные «блоки» из N букв.

Отсюда ясно, что если по линии связи за единицу времени можно передать L элементарных сигналов (принимающих т различных значений), то скорость передачи сообщений по такой линии не может быть большей, чем букв/ед. времени; однако передача со скоростью, сколь угодно близкой к v (но меньшей v !), уже является возможной.

Величина v , зависит лишь от самой линии связи (в то время как знаменатель Н характеризует передаваемое сообщение). Эта величина указывает на наибольшее количество единиц информации, которое можно передать по нашей линии за единицу времени (ибо один элементарный сигнал, как мы знаем, может содержать самое большее log m единиц информации); она называется пропускной способностью линии связи.

Понятие пропускной способности играет важную роль в теории связи. 2.2 Энтропия и информация конкретных типов сообщений. 2.2.1 Письменная речь Для передачи М-буквенного сообщения допускающей m различных элементарных сигналов, требуется затратить не меньше чем сигналов, где n — число букв «алфавита. Так как русский «телеграфный» алфавит содержит 32 буквы (не различаются букв е и ё, ь и ъ, но причисляются к числу букв и «нулевая буква» — пустой промежуток между словами), то на передачу М-буквенного сообщения надо затратить элементарных сигналов. Здесь Н 0 = log 32 = 5 бит - энтропия опыта, заключающегося в приеме одной буквы русского текста, при условии, что все буквы считаются одинаково вероятными. Для получения текста, в котором каждая буква содержит 5 бит информации требуется выписать 32 буквы на отдельных билетиках, сложить все эти билетики в урну и затем вытаскивать их по одному, каждый раз записывая вытянутую букву, а билетик возвращая обратно в урну и снова перемешивая ее содержимое.

Произведя такой опыт, мы придем к «фразе» вроде следующей: СУХЕРРОБЬДЩ ЯЫХВЩИЮАЙЖТЛФВНЗАГФОЕН-ВШТЦР ПХГБКУЧТЖЮРЯПЧЬКЙХРЫС Разумеется, этот текст имеет очень мало общего с русским языком! Для более точного вычисления информации, содержащейся в одной букве русского текста, надо знать вероятности появления различных букв.

Ориентировочные значения частот отдельных букв русского языка собраны в следующей таблице:

Сокращение числа требующихся элементарных сигналов можно показать кодированием отдельных букв русского алфавита по методу Шеннона — Фано:

буква	код. обозн.	буква	код. обозн.	буква	код. обозн.
	111	к	01000	х	0000100
а	1010	л	01001	ц	00000010
б	000101	м	00111	ч	000011
в	01010	н	0111	ш	00000011
г	000100	о	110	щ	00000001
д	001101	п	001100	ы	001000
е, ё	1011	р	01011	ь,ъ	000110
ж	0000011	с	0110	э	000000001
в	000111	т	1000	ю	00000010
и	1001	у	00101	я	001001
й	0000101	ф	000000000

Несходство нашей фразы с осмысленным текстом естественно объясняется тем, что на самом деле последовательные буквы русского текста вовсе не независимы друг от друга. Так, например, если мы знаем, что очередной буквой явилась гласная, то значительно возрастает вероятность появления на следующем месте согласной буквы; буква «ь» никак не может следовать ни за пробелом, ни за гласной буквой; за буквой «ч» никак не могут появиться буквы «ы», «я» или «ю», а скорее всего будет стоять одна из гласных «и» и «е» или согласная «т» и т. д.

Наличие в русском языке дополнительных закономерностей, не учтенных в нашей «фразе», приводит к дальнейшему уменьшению степени неопределенности одной буквы русского текста. Для этого надо лишь подсчитать условную энтропию опыта предшествующей буквы того же текста.

Условная энтропия определяется следующей формулой: р(-), р(а), р(б), ..., р(я) обозначены вероятности (частоты) отдельных букв русского языка.

Разумеется заранее можно сказать, что вероятности р(- -), р(яь) и многие другие (например, р(ьь), р(- ь), р(чя) и т.д.) будут равны нулю. Мы можем быть уверены, что условная энтропия окажется меньше безусловной энтропии Величину можно конкретизировать как «среднюю информацию», содержащуюся в определении исхода следующего опыта.

Имеется 32 урны, обозначенные 32 буквами русского алфавита; в каждой из урн лежат бумажки, на которых выписаны двухбуквенные сочетания, начинающиеся с обозначенной на урне буквы, причем количества бумажек с разными парами букв пропорциональны частотам (вероятностям) соответствующих двухбуквенных сочетаний. Опыт состоит в многократном извлечении бумажек из урн и выписывании с них последней буквы. При этом каждый раз (начиная со второго) бумажка извлекается из той урны, которая содержит сочетания, начинающиеся с последней выписанной буквы; после того как буква выписана, бумажка возвращается в урну, содержимое которой снова тщательно перемешивается. Опыт такого рода приводит к «фразе» вроде следующей: УМАРОНО КАЧ ВСВАННЫЙ РОСЯ НЫХ КОВКРОВ НЕДАРЕ. По звучанию эта «фраза» заметно ближе к русскому языку.

Знание двух предшествующих букв еще более уменьшает неопределенность опыта, состоящего в определении следующей буквы, что находит отражение в положительности разности - «условная энтропия второго порядка»: Наглядным подтверждением сказанного является опыт, состоящий в вытаскивании бумажек с трехбуквенными сочетаниями из 32 2 урн, в каждой из которых лежат бумажки, начинающиеся на одни и те же две буквы (или опыт с русской книгой, в которой много раз наудачу отыскивается первое повторение последнего уже выписанного двухбуквенного сочетания и выписывается следующая за ним буква), приводит к «фразе» вроде следующей: ПОКАК ПОТ ДУРНОСКАКА НАКОНЕПНО ЗНЕ СТВОЛОВИЛ СЕ ТВОЙ ОБНИЛЬ, еще более близкой к русской речи, чем предыдущая.

Аналогично этому можно определить и энтропию отвечающую опыту по определению буквы русского текста при условии знания трех предшествующих букв. Он состоит в извлечении бумажек из 32 3 урн с четырехбуквенными сочетаниями (или — аналогичный описанному выше эксперимент с русской книгой), приводит к «фразе» вроде следующей: ВЕСЕЛ ВРАТЬСЯ НЕ СУХОМ И НЕПО И КОРКО, Еще лучшее приближение к энтропии буквы осмысленного русского текста дают величины при N = 5,6, .... Нетрудно видеть, что с ростом N энтропия Н N может только убывать. Если еще учесть, что все величины Н N положительны, то отсюда можно будет вывести, что величина при стремится к определенному пределу Нам уже известно, что среднее число элементарных сигналов, необходимое для передачи одной буквы русского текста, не может быть меньшим Разность к величине Избыточность R является весьма важной статистической характеристикой языка, но ее численное значение пока ни для одного языка не определено с удовлетворительной точностью. В отношении русского языка, в частности, имеются лишь данные о значениях величин Н 2 и Н 3 .

Величины Н 2 и Н 3 для английского языка были подсчитаны Шенноном, при этом он использовал имеющиеся таблицы частот в английском языке различных двухбуквенных и трехбуквенных сочетаний. Учтя также и статистические данные о частотах появления различных слов в английском языке, Шеннон сумел приближенно оценить и значения величин Н 5 и H 8 . В результате он получил:

Остановимся на одном из такого рода методе, предложенном Шенноном. «Условная энтропия» Н N представляет собой меру степени неопределенности опыта N-й буквы текста, при условии, что предшествующие N — 1 букв нам известны.

Эксперимент по отгадыванию N-й буквы легко может быть поставлен: для этого достаточно выбрать (N — 1)-буквенный отрывок осмысленного текста и предложить кому-либо отгадать следующую букву.

Подобный опыт может быть повторен многократно, при этом трудность отгадывания N-й буквы может быть оценена с помощью среднего значения Q N числа попыток, требующихся для нахождения правильного ответа. Ясно, что величины Q N , определенные для разных значений N, являются определенными характеристиками статистической структуры языка, в частности, его избыточности.

Шеннон произвел ряд подобных экспериментов, в которых N принимало значения 1, 2, 3, ..., 14, 15 и 100. При этом он обнаружил, что отгадывание 100-й буквы по 99 предшествующим является заметно более простой задачей, чем отгадывание 15-й буквы по 14 предыдущим.

Отсюда можно сделать вывод, что Н 15 ощутимо больше, чем Н 100 , т. е. что Н 15 никак еще нельзя отождествить с предельным значением N = 1, 2, 4, 8, 16, 32, 64, 128 и N 10 00. Из полученных данных можно заключить, что величина Н 32 (так же как и H 64 и Н 128 ) практически не отличается от Н 10000 , в то время как «условная энтропия» Н 16 еще заметно больше этой величины. Таким образом, можно предположить, что при возрастании N величина H N убывает вплоть до значений N = 30, но при дальнейшем росте N она уже практически не меняется; поэтому вместо «предельной энтропии» можно говорить, например, об условной энтропии H 30 или H 40 . Эксперименты по отгадыванию букв не только позволяют судить о сравнительной величине условных энтропии H N при разных N, но дают также возможность оцепить и сами значения Н N . По данным таких экспериментов можно определить не только среднее число Q N попыток, требующихся для отгадывания N-й буквы текста по N — 1 предшествующим, но и вероятности (частоты) того, что буква будет правильно угадана с 1-й, 2-й, 3-й, ..., n-й попытки (где п = 27 - число букв алфавита; Q N = равны вероятностям букв алфавита, расположенных в порядке убывания частот. В самом деле, если ни одна из букв, предшествующих отгадываемой букве х, нам не известна, то естественно прежде всего предположить, что х совпадает с самой распространенной буквой a 1 (причем вероятность правильно угадать здесь будет равна р(а 1 )); затем следует предположить, что х совпадает с а 2 (вероятность правильного ответа здесь будет равна р(а 2 )) и т. д.

Отсюда следует, что энтропия Н 1 равна сумме . Если же N > 1, то можно показать, что сумма (*) не будет превосходить условную энтропию H N (это связано с тем, что величины представляют собой определенным образом усредненные вероятности исходов опыта (**) при всяком N будет не больше условной энтропии Н N . Таким образом, выражения (*) и (**) (составленные из вероятностей H N . Надо только еще иметь в виду, что обе оценки (*) и (**) получаются в предположении, что - это те вероятности угадывания буквы по N — 1 предыдущим буквам с первой, второй, третьей и т. д. попыток, которые получаются в предположении, что отгадывающий всегда называет очередную букву наиболее целесообразно — с полным учетом всех статистических закономерностей данного языка. В случае же реальных опытов любые ошибки в стратегии отгадывающего (т. е. отличия называемых им букв от тех, которые следовало бы назвать, исходя из точной статистики языка) будут неизбежно приводить к завышению обеих сумм (*) и (**); именно поэтому целесообразно учитывать лишь данные «наиболее успешного отгадывающего», так как для него это завышение будет наименьшим.

Поскольку каждый отгадывающий иногда ошибается, то оценку (**) на практике нельзя считать вполне надежной оценкой снизу истинной энтропии (в отличие от оценки сверху (*), которая из-за ошибок отгадывающего может только стать еще больше). Кроме того, значения сумм (*) и (**), к сожалению, не сближаются неограниченно при увеличении N (начиная с N 30 эти суммы вообще перестают зависеть от N); поэтому полученные на этом пути оценки избыточности языка не будут особенно точными. В частности, опыты Шеннона показали лишь, что величина H 100 по-видимому, заключается между 0,6 и 1,3 бит.

Отсюда можно заключить, что избыточность для английского языка по порядку величины должна быть близка к 80%. 2.2.2 Устная речь.

Перейдем теперь к вопросу об энтропии и информации устной речи. Естественно думать, что все статистические характеристики такой речи будут еще более зависеть от выбора разговаривающих лиц и от характера их разговора.

Пониженное значение энтропии устной речи может быть связано с тем, что в разговоре мы зачастую употребляем больше повторений одних и тех же слов и нередко добавляем довольно много «лишних» слов — это делается как для облегчения восприятия речи, так и просто затем, чтобы говорящий имел время обдумать, что он хочет сказать дальше.

Определив среднее число букв, произносимых за единицу времени, можно приближенно оценить количество информации, сообщаемое при разговоре за 1 сек; обычно оно имеет порядок 5 - 6 бит. Из разговора мы можем судить о настроении говорящего и об его отношении к сказанному; мы можем узнать говорящего, если даже никакие другие источники информации не указывают нам его; мы можем во многих случаях определить место рождения незнакомого нам человека по его произношению; мы можем оценить громкость устной речи, которая в случае передачи голоса по линии связи во многом определяется чисто техническими характеристиками линии передачи, и т. д.

Количественная оценка всей этой информации представляет собой очень сложную задачу, требующую значительно больших знаний об языке.

Исключением в этом отношении является сравнительно узкий вопрос о логических ударениях, подчеркивающих в фразе отдельные слова.

Ударение чаще всего падает на наиболее редко употребляемые слова (что, впрочем, довольно естественно - ясно, что вряд ли кто будет выделять логическим ударением наиболее распространенные слона - например, предлоги или союзы). Если вероятность того, что данное слово W r находится под ударением, мы обозначим через q r , то средняя информация, заключающаяся в сведениях о наличии или отсутствии ударения на этом слове, будет равна Пусть теперь - вероятности (частоты) всех слов W 1 , W 2 , . . ., W K (здесь К - общее число всех употребляемых слов. В таком случае для средней информации Н, заключенной в логическом ударении, можно написать следующую формулу: C редняя информация, которую мы получаем, выяснив, на какие слова падает логическое ударение, по порядку величины близка к 0,65 бит/слово. Во время разговора отдельные буквы никогда не произносятся, а произносятся звуки, существенно отличающиеся от букв.

Поэтому основным элементом устной речи надо считать отдельный звук - фонему.

Осмысленная устная речь составляется из фонем точно так же, как осмысленная письменная речь составляется из букв.

Поэтому во всех случаях, когда нас интересует лишь передача «смысловой информации» устной речи наибольший интерес представляет не энтропия и информация одной «произнесенной буквы», а энтропия и информация одной реально произнесенной фонемы.

Список фонем данного языка, разумеется, не совпадает со списком букв алфавита, так как одна и та же буква в разных случаях может звучать по-разному. В русском языке 42 различные фонемы и подсчитали частоты отдельных фонем (а также различных комбинаций двух и трех следующих друг за другом фонем). Н 0 = log 42 одной фонемы, энтропии первого порядка (где - относительные частоты различных фонем) и «условных энтропии» Н 2 и Н 3 :

Исследования того же рода могут быть проведены и в отношении музыкальных сообщений.

Естественно думать, что связи между последовательными звуками некоторой мелодии, выражающимися отдельными нотными знаками, достаточно сильны: так как одни сочетания звуков будут более благозвучны, чем другие, то первые будут встречаться в музыкальных произведениях чаще вторых. Если мы выпишем ряд нот наудачу, то информация, содержащаяся в каждой ноте этой записи, будет наибольшей; однако с музыкальной точки зрения такая хаотическая последовательность нот не будет представлять никакой ценности. Для того чтобы получить приятное на слух звучание, необходимо внести в наш ряд определенную избыточность; при этом можно опасаться, что в случае слишком большой избыточности, при которой последующие ноты уже почти однозначно определяются предшествующими, мы получим лишь крайне монотонную и малоинтересную музыку.

Какова же та избыточность, при которой может получиться «хорошая» музыка? Избыточность простых мелодий никак не меньше, чем избыточность осмысленной речи.

Необходимо было бы специально изучить вопрос об избыточности различных форм музыкальных произведений или произведений различных композиторов. К примеру, проанализировать с точки зрения теории информации популярный альбом детских песенок. Для простоты в этой работе предполагалось, что все звуки находятся в пределах одной октавы; так как в рассматриваемых мелодиях не встречались так называемые хроматизмы, то все эти мелодии могли быть приведены к семи основным звукам; До, ре, ми, фа, соль, ля и си, каждый длительностью в одну восьмую. Учет звуков, длительностью более одной восьмой, осуществлялся с помощью добавления к семи нотам восьмого «основного элемента» О, обозначающего продление предшествующего звука еще на промежуток времени в одну восьмую (или же паузу в одну восьмую). Таким образом, «максимальная возможная энтропия» Н 0 одной ноты здесь равна Н 0 = log 8 = 3 бита.

Подсчитав частоты (вероятности) отдельных нот во всех 39 анализируемых песенках, находим, что С помощью найденных вероятностей сочетаний из двух нот, можно подсчитать также условную энтропию Н 2 , она оказывается близкой к 2,42 . По одним только значениям Н 1 и Н 2 еще очень мало что можно сказать о степени избыточности рассматриваемых, по-видимому, она заметно выше, чем 2.2.4 Передача телевизионных изображений. Наш глаз способен различить лишь конечное число степеней яркости изображения и лишь не слишком близкие его участки, поэтому любое изображение можно передавать «по точкам», каждая из которых является сигналом, принимающим лишь конечное число значений. Необходимо учитывать значительное число (несколько десятков) градаций степени почернения («яркости») каждого элемента, кроме того, на телеэкране ежесекундно сменяется 25 кадров, создавая впечатление «движения». Однако, по линии связи фактически передается не исход опыта может иметь уже лишь конечное число исходов, и мы можем измерить его энтропию Н. Общее число элементов («точек») для черно-белого телевидения, на которые следует разлагать изображение, определяется в первую очередь так называемой «разрешающей способностью» глаза, т. е. его способностью различать близкие участки изображения. В современном телевидении это число обычно имеет порядок нескольких сотен тысяч (в советских телепередачах изображение разлагалось на 400 00 - 500 000 элементов, в американских - примерно на 200 00 - 300 000, в передачах некоторых французских и бельгийских телецентров - почти на 1 000 000). Нетрудно понять, что по этой причине энтропия телевизионного изображения имеет огромную величину. Если даже считать, что человеческий глаз различает лишь 16 разных градаций яркости (значение явно заниженное) и что изображение разлагается всего на 200000 элементов, то мы найдем, что «энтропия нулевого порядка» здесь равна Н 0 = log 16 200000 = 800 000 бит.

Значение истинной энтропии Н, разумеется, будет меньше, так как телевизионное изображение имеет значительную избыточность Н 0 мы предполагали, что значения яркости в любых двух «точках» изображения являются независимыми между собой, в то время как на самом деле яркость обычно очень мало меняется при переходе к соседним элементам того же (или даже другого, но близкого по времени) изображения.

Наглядный смысл этой избыточности R заключается в том, что среди наших 16 200000 возможных комбинаций значений яркости во всех точках экрана осмысленные комбинации, которые можно назвать «изображениями», будут составлять лишь ничтожно малую часть, а остальное будет представлять собой совершенно беспорядочную совокупность точек разной яркости, весьма далекую от какого бы то ни было «сюжета». Между тем реальная «степень неопределенности» Н телевизионного изображения должна учитывать только те комбинации значений яркости, которые имеют хоть какие-то шансы быть переданными. Для определения точного значения энтропии Н (или избыточности R ) телевизионного изображения нужно детально изучить статистические зависимости между яркостями различных точек экрана. Так, найдены значения энтропий Н 0 , Н 1 , Н 2 и Н 3 для двух конкретных телевизионных изображений, первое из которых (изображение А — парк с деревьями и строениями) было более сложным, а второе (изображение В — довольно темная галерея с прохожими) было более однотонным по цвету и содержало меньше деталей, при этом различали 64 разных градаций яркости элемента телевизионного изображения, поэтому энтропия Н 0 (отнесенная к одному элементу, а не ко всему изображению в целом) здесь оказалась равной Н 0 = log 64 = 6 бит. Далее с помощью специального радиотехнического устройства были подсчитаны для обоих рассматриваемых изображений относительные частоты (вероятности) всех различимых градаций яркости и определил «энтропию первого порядка» То же самое радиотехническое устройство было применено затем для вычисления относительных частот p i j пар соседних (по горизонтали) элементов, в которых первый элемент имеет i-e значение яркости, а второй j-e, а также относительных частот p i jk троек соседних (также лишь по горизонтали) элементов, в которых первый элемент имел i-e значение яркости, второй j-e, а третий k -е (числа i, j , и k пробегали все значения от 1 до 64). Эти частоты позволили определить «энтропии сложных опытов» и а затем и «условные энтропии» и последняя ив которых, впрочем, была подсчитана лишь для изображения Б. Полученные результаты сведены в следующую таблицу:

Близкий характер имеет также другой опыт, опирающийся на разбиение возможных значений яркости элемента телевизионного изображения на 8, а не на 64 градаций, для которого вычислены энтропии Н 0 и Н 1 и ряда условных энтропии Н 2 , Н 3 и Н 4 одного элемента изображения для следующих четырех спортивных телевизионных сюжетов: А - быстро бегущие баскетболисты, Б - лицо одного зрителя на трибуне стадиона крупным планом, В - панорамирование вида зрителей на трибуне и Г - быстро бегущие футболисты. Будем обозначать цифрами 1 и 2 соседние с данным по горизонтали и по вертикали элементы изображения, цифрой 3 — соседний по диагонали элемент, цифрой 4 — тот же, что и рассматриваемый, элемент на предшествующем кадре телевизионной передачи, цифрой 5 — элемент на той же горизонтали, соседний с элементом 1, и, наконец, цифрой 6 - тот же элемент на кадре, предшествующем тому, который содержит элемент 4 (рис 1), а) б) рис 1. и будем указывать в обозначениях условных энтропий сверху в скобках номера элементов изображения, степень яркости которых считается известной. В таком случае значения энтропии (в битах) могут быть сведены в следующую таблицу:

А	3	1,96	0,69	0,98	-	1,77
Б	3	1,95	0,36	0,36	-	-
В	3	2,78	1,34	1,95	2,78	-
Г	3	2,45	-	-	2,00	2,08

А	0,68	-	0,56	-	-
Б	0,35	-	0,27	0,26	-
В	-	-	1,22	1,18	1,19
Г	-	1,83	-	-	-

Задача: изучить энтропии и избыточность конкретных типов сообщений для последующего применения к ним принципов Шеннона - Фано и Хафмана. После выполнения целей и задач дипломной работы были сделаны следующие выводы. До появления работ Шеннона и Фано, кодирование символов алфавита при передаче сообщения по каналам связи осуществлялось одинаковым количеством бит, получаемым по формуле Хартли. С появлением этих работ начали появляться способы, кодирующие символы разным числом бит в зависимости от вероятности появления их в тексте, то есть более вероятные символы кодируются короткими кодами, а редко встречающиеся символы - длинными (длиннее среднего). С тех пор, как Д.А.Хаффман опубликовал в 1952 году свою работу 'Метод построения кодов с минимальной избыточностью', его алгоритм кодирования стал базой для огромного количества дальнейших исследований в этой области. Стоит отметить, что за 50 лет со дня опубликования, код Хаффмана ничуть не потерял своей актуальности и значимости. Так с уверенностью можно сказать, что мы сталкиваемся с ним, в той или иной форме (дело в том, что код Хаффмана редко используется отдельно, чаще работая в связке с другими алгоритмами), практически каждый раз, когда архивируем файлы, смотрим фотографии, фильмы, посылаем факс или слушаем музыку.