Префиксный код Шеннона-Фано
Код Шеннона-Фано
Код строится следующим образом:
1) буквы алфавита сообщений выписываются в таблицу в порядке убывания вероятностей;
2) затем они разделяются на две группы так, чтобы суммы вероятностей в каждой из групп были по возможности одинаковы;
3) всем буквам верхней половины в качестве первого символа приписывается 1, а всем нижним - 0;
4) каждая из полученных групп, в свою очередь, разбивается на две подгруппы с одинаковыми суммарными вероятностями и т. д.
Процесс повторяется до тех пор, пока в каждой подгруппе останется по одной букве.
Пример. Рассмотрим алфавит из восьми букв (табл. 12). При обычном (не учитывающем статистических характеристик) кодировании для представления каждой буквы требуется три символа.
Таблица 8.12 Таблица 13
| Буквы | Вероятности | Кодовые комбинации | Буквы | Вероятности | Кодовые комбинации | |
| 0,22 | 11 | 0,22 | 11 | |||
| 0,20 | 101 | 0,20 | 10 | |||
| 0,16 | 100 | 0,16 | 011 | |||
| 0,16 | 01 | 0,16 | 010 | |||
| 0,10 | 001 | 0,10 | 001 | |||
| 0,10 | 0001 | 0,10 | 0001 | |||
| 0,04 | 00001 | 0,04 | 00001 | |||
| 0,02 | 00000 | 0,02 | 00000 |
Вычислим энтропию набора букв: Н
и среднее число символов на букву
где n() - число символов в кодовой комбинации, соответствующей букве.
Значения Н(z) и l ср не очень различаются по величине. Условие теоремы Шеннона выполнено Н(z) <= l ср
Рассмотренная методика Шеннона-Фано не всегда приводит к однозначному построению кода. Ведь при разбиении на подгруппы можно сделать большей по вероятности как верхнюю, так и нижнюю подгруппу.
Множество вероятностей в предыдущей таблице можно было разбить иначе (табл. 13). При этом среднее число символов на букву оказывается равным 2,80. Таким образом, построенный код может оказаться не самым лучшим. При построении эффективных кодов с основанием s > 2 неопределенность становится еще больше.
Метод Хаффмена
Метод Хаффмена свободен от недостатка связанного с неоднозначностью построения кода. Данная методика также использует статистические свойства источника сообщений. Метод гарантирует однозначное построение кода с наименьшим для данного распределения вероятностей средним числом символов на букву.
В таблице 14 показаны основные шаги построения кода.
Таблица 14
| Буквы | Вероятности | Вспомогательные столбцы | ||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | ||
| 0,22 | 0,22 | 0,22 | 0,26 | 0,32 | 0,42 | 0,58 | 1 | |
| 0,20 | 0,20 | 0,20 | 0,22 | 0,26 | 0,32 | 0,42 | ||
| 0,16 | 0,16 | 0,16 | 0,20 | 0,22 | 0,26 | |||
| 0,16 | 0,16 | 0,16 | 0,16 | 0,20 | ||||
| 0,10 | 0,10 | 0,16 | 0,16 | |||||
| 0,10 | 0,10 | 0,10 | ||||||
| 0,04 | 0,06 | |||||||
| 0,02 | ||||||||
Для двоичного кода методика сводится к следующему:
1) Буквы алфавита сообщений выписываются в основной столбец в порядке убывания вероятностей;
2) две последние буквы объединяются в одну вспомогательную букву, которой приписывается суммарная вероятность;
3) вероятности букв, не участвовавших в объединении, и полученная суммарная вероятность снова располагаются в порядке убывания вероятностей в дополнительном столбце, а две последние буквы снова объединяются.
Процесс продолжается до тех пор, пока не получим единственную вспомогательную букву с вероятностью, равной единице.
Для составления кодовой комбинации, соответствующей данному сообщению, необходимо проследить путь перехода сообщений по строкам и столбцам таблицы. Для наглядности строится кодовое дерево(рис.1).
Рис.1 Кодовое дерево
Из точки, соответствующей вероятности 1, направляются две ветви, причем ветви с большей вероятностью присваивается символ 1, а с меньшей - 0. Такое последовательное ветвление продолжается до тех пор, пока не дойдем до каждой буквы (рис. 1).
Теперь, двигаясь по кодовому дереву сверху вниз, можно записать для каждой буквы соответствующую ей кодовую комбинацию;
01 00 111 110 100 1011 10101 10100
Алгоритм метода Шеннона-Фано - один из первых алгоритмов сжатия, который впервые сформулировали американские учёные Шеннон и Фано, и он имеет большое сходство с алгоритмом Хаффмана. Алгоритм основан на частоте повторения. Так, часто встречающийся символ кодируется кодом меньшей длины, а редко встречающийся - кодом большей длины.
В свою очередь, коды, полученные при кодировании, префиксные. Это и позволяет однозначно декодировать любую последовательность кодовых слов. Но все это вступление.
Для работы оба алгоритма должны иметь таблицу частот элементов алфавита.
Итак, алгоритм Хаффмана работает следующим образом:
- На вход приходят упорядоченные по невозрастанию частот данные .
- Выбираются две наименьших по частоте буквы алфавита, и создается родитель (сумма двух частот этих «листков»).
- Потомки удаляются и вместо них записывается родитель, «ветви» родителя нумеруются: левой ветви ставится в соответствие «1», правой «0».
- Шаг два повторяется до тех пор, пока не будет найден главный родитель - «корень».
Алгоритм Шеннона-Фано работает следующим образом:
- На вход приходят упорядоченные по невозрастанию частот данные.
- Находится середина, которая делит алфавит примерно на две части. Эти части (суммы частот алфавита) примерно равны. Для левой части присваивается «1», для правой «0», таким образом мы получим листья дерева
- Шаг 2 повторяется до тех пор, пока мы не получим единственный элемент последовательности, т.е. листок
Таким образом, видно, что алгоритм Хаффмана как бы движется от листьев к корню, а алгоритм Шеннона-Фано, используя деление, движется от корня к листям.
Ну вот, быстро осмыслив информацию, можно написать код алгоритма Шеннона-Фано на паскале. Попросили именно на нем написать. Поэтому приведу листинг вместе с комментариями.
Program ShennonFano;
uses crt;
const
a:array of char = ("a","b","c","d","e","f"); { символы }
af:array of integer = (10, 8, 6, 5, 4, 3); { частота символов }
{ Процедура для поиска кода каждой буквы }
procedure SearchTree(branch:char; full_branch:string; start_pos:integer; end_pos:integer);
var
dS:real; { Среднее значение массива }
i, m, S:integer; { m - номер средней буквы в последовательности, S - сумма чисел, левой ветки }
c_branch:string; { текущая история поворотов по веткам }
begin
{ проверка если это вход нулевой то очистить историю }
if (a<>" ") then c_branch:= full_branch + branch
else c_branch:= "";
{ Критерий выхода: если позиции символов совпали, то это конец }
if (start_pos = end_pos) then
begin
WriteLn(a, " = ", c_branch);
exit;
end;
{ Подсчет среднего значения частоты в последовательности }
dS:= 0;
for i:=start_pos to end_pos do dS:= dS + af[i];
dS:= dS/2;
{ Тут какой угодно можно цикл for, while, repeat поиск середины }
S:= 0;
i:= start_pos;
m:= i;
while ((S+af[i]
Ну вот собственно и все, о чем я хотел рассказать. Всю информацию можно взять из википедии. На рисунках приведены частоты сверху.
Спасибо за внимание!
Оптимальным кодом можно определить тот, в котором каждый двоичный символ будет передавать максимальную информацию. В силу формул Хартли и Шеннона максимум энтропии достигается при равновероятных событиях, следовательно, двоичный код будет оптимальным, если в закодированном сообщении символы 0 и 1 будут встречаться одинаково часто.
Рассмотрим в качестве примера оптимальное двоичное кодирование букв русского алфавита вместе с символом пробела «-». Полагаем, что известны вероятности появления в сообщении символов русского алфавита, например, приведенные в таблице 3.
Таблица 3.Частота букв русского языка (предположение)
К. Шеннон и Р. Фано независимо предложили в 1948-1949 гг. способ построения кода, основанный на выполнении условия равной вероятности символов 0 и 1 в закодированном сообщении.
Все кодируемые символы (буквы) разделяются на две группы так, что сумма вероятностей символов в первой группе равна сумме вероятностей символов второй группы (то есть вероятность того, что в сообщении встретится символ из первой группы, равна вероятности того, что в сообщении встретится символ из второй группы).
Для символов первой группы значение первого разряда кода присваивается равным «0», для символов второй группы – равными «1».
Далее каждая группа разделяется на две подгруппы, так чтобы суммы вероятностей знаков в каждой подгруппе были равны. Для символов первой подгруппы каждой группы значение второго разряда кода присваивается равным «0», для символов второй подгруппы каждой группы – «1». Такой процесс разбиения символов на группы и кодирования продолжается до тех пор, пока в подгруппах не остается по одному символу.
Пример кодирования символов русского алфавита приведен в табл. 4
Таблица 4. Пример кодирования букв русского алфавита с помощью кода Шеннна-Фано.
Анализ приведенных в таблице кодов приводит к выводу, что часто встречающиеся символы кодируются более короткими двоичными последовательностями, а редко встречающиеся - более длинными. Значит, в среднем для кодирования сообщения определенной длины потребуется меньшее число двоичных символов 0 и 1, чем при любом другом способе кодирования.
Вместе с тем процедура построения кода Шеннона-Фано удовлетворяет критерию различимости Фано. Код является префиксным и не требует специального символа, отделяющего буквы друг от друга для однозначного него декодирование двоичного сообщения.
Таким образом, проблема помехоустойчивого кодирования представляет собой обширную область теоретических и прикладных исследований. Основными задачами при этом являются следующие: отыскание кодов, эффективно исправляющих ошибки требуемого вида; нахождение методов кодирования и декодирования и простых способов их реализации.
Наиболее разработаны эти задачи применительно к систематическим кодам. Такие коды успешно применяются в вычислительной технике, различных автоматизированных цифровых устройствах и цифровых системах передачи информации.
Заключение
Мы рассмотрели задачу кодирования, которая включает в себя:
1.Обеспечение экономичности передачи информации посредством устранения избыточности.
2. Обеспечение надежности (помехоустойчивости) передачи информации
3.Согласование скорости передачи информации с пропускной способностью канала
Задача кодирования является одним из главных понятий информатики, так как кодирование предшествует передаче и хранению информации, и, соответственно, является основой их успешного осуществления.
При передаче сообщений по каналам связи могут возникать помехи, способные привести к искажению принимаемых знаков. Эта проблема решается с помощью помехоустойчивого кодирования. Помехоустойчивое кодирование передаваемой информации позволяет в приемной части системы обнаруживать и исправлять ошибки. Коды, применяемые при помехоустойчивом кодировании, называются корректирующими кодами. Впервые, исследование эффективного кодирования произвел Клод Шеннон. Для теории связи важнейшее значение имеют две теоремы, доказанные Шенноном.
В работе были рассмотрены эти теоремы, и можно прийти к выводу, что первая – затрагивает ситуацию с кодированием при передаче сообщения по линии связи, в которой отсутствуют помехи, искажающие информацию, т.е. эта теорема является эталоном, какими должны быть помехоустойчивые коды, Вторая теорема относится к реальным линиям связи с помехами.
Если рассмотреть примеры кодирования, на основе первой теоремы Шеннона, то можно прийти к выводам, что это кодирования является достаточно эффективным, так как получаемый код практически не имеет избыточности, но, к сожалению, в реальных линиях связи множество помех, и такой результат недостижим. Поэтому код Шеннона не является таким же эффективным как, например код Хафмена. Но, несмотря на это нужно отметить, что Клод Шеннон был одним из основателей теории кодирования и его работы внесли огромный вклад в развитие информатики.
Список литературы:
1. Журнал "Радио", номер 9, 1999г.
наук, г. Москва
2. Кловский Д.Д. Теория передачи сигналов. -М.: Связь, 1984.
3. Кудряшов Б.Д. Теория информации. Учебник для вузов Изд-во ПИТЕР,
4. Рябко Б.Я Фионов А.Н. Эффективный метод адаптивного
арифметического кодирования для источников с большими алфавитами
// Проблемы передачи информации 1999 Т.35, Вып С.95 - 108.
5. Семенюк В.В. Экономное кодирование дискретной информации СПб.:
СПбГИТМО (ТУ), 2001
6. Дмитриев В.И. Прикладная теория информации. М.: Высшая школа,
7. Нефедов В.Н Осипова В.А. Курс дискретной математики. М.: МАИ,
8. Колесник В.Д Полтырев Г.Ш. Курс теории информации. М.: Наука,
ЛАБОРАТОРНАЯ РАБОТА 9
Эффективное кодирование
Цель: Изучение методик эффективного кодирования.
1. Построить код Шеннона-Фано по выбранным вариантам и результаты свести в таблицы.
2. Построить код Хаффмана по выбранным вариантам и результаты свести в таблицы. Для каждого построенного кода построить кодовое дерево.
Отчет по лабораторной работе должен содержать:
– краткие теоретические сведения о коде Шеннона-Фано и коде Хаффмана;
– построить коды Шеннона-Фано и Хаффмана при различных вариантах входных данных (для каждого кода выбрать произвольно три группы по 12 символов в каждой, присвоить каждому символу вероятность (сумма равна единице) и построить указанные коды).
– выводы.
Основные понятия и определения
Код Шеннона-Фано
Код строят следующим образом: знаки алфавита сообщений вписываются в таблицу в порядке убывания вероятностей. Затем их разделяют на две группы так, чтобы суммы вероятностей в каждой из групп были по возможности одинаковы. Всем знакам верхней половины в качестве первого символа приписывают «0», а всем нижним – «1». Каждую из полученных групп, в свою очередь разбивают на две подгруппы с одинаковыми суммарными вероятностями и т. д. Процесс повторяется до тех пор, пока в каждой подгруппе останется по одному знаку.
Пример 1. Проведем эффективное кодирование ансамбля из восьми знаков, характеристики которого представлены в табл. 3.1.
Таблица 3.1
| Знаки | Вероятность | Кодовые комбинации | Ступень разбиения |
| Z 1 | 0.22 | ||
| Z 2 | 0.2 | ||
| Z 3 | 0.16 | ||
| Z 4 | 0.16 | ||
| Z 5 | 0.1 | ||
| Z 6 | 0.1 | ||
| Z 7 | 0.04 | ||
| Z 8 | 0.02 |
Рис. 3.1. Дерево группового разделения вероятностей Шеннона-Фано
Ясно, что при обычном (не учитывающем статистических характеристик) кодировании для представления каждого знака требуется три двоичных символа. Используя методику Шеннона-Фано, получаем совокупность кодовых комбинаций, приведенных в табл. 3.1.
Так как вероятности знаков представляют собой целочисленные отрицательные степени двойки, то избыточность при кодировании устраняется полностью. Среднее число символов на знак в этом случае точно равно энтропии. Убедимся в этом, вычислив энтропию
,
и среднее число символов на знак
,
где – число символов в кодовой комбинации, соответствующей знаку .
В общем случае для алфавита из восьми знаков среднее число символов на знак будет меньше трех, но больше энтропии алфавита .
Пример 2. Определим среднюю длину кодовой комбинации при эффективном кодировании знаков ансамбля. Приведенного в табл. 3.2.
Энтропия ансамбля равна 2,76. В результате сопоставления отдельным знакам ансамбля кодовых комбинаций по методике Шеннона-Фано (табл. 3.2) получаем среднее число символов на знак, равное 2,84.
Таблица 3.2
Характеристики ансамбля из восьми знаков
| Знаки | Вероятность | Кодовые комбинации | Ступень разбиения |
| Z 1 | 0,22 | ||
| Z 2 | 0,20 | ||
| Z 3 | 0,16 | ||
| Z 4 | 0,16 | ||
| Z 5 | 0,10 | ||
| Z 6 | 0,10 | ||
| Z 7 | 0,04 | ||
| Z 8 | 0,02 |
Следовательно, некоторая избыточность в последовательностях символов осталась. Из теоремы Шеннона следует, что эту избыточность также можно устранить, если перейти к кодированию достаточно большими блоками.
ВВЕДЕНИЕ Новые направления, возникшие в математике в ХХ веке, обычно оперируют со сложными понятиями и представлениями, которые с трудом поддаются популяризации. На этом фоне весьма значительна заслуга выдающегося американского математика и инженера Клода Шеннона, который в 1947-1948 годах, исходя из элементарных соображений, открыл новую область математики - теорию информации. Толчком к созданию новой науки были чисто технические проблемы передачи информации по телеграфным и телефонным проводам, однако к настоящему времени благодаря общему характеру теория информации находит применение в исследованиях, относящихся к передаче и сохранению любой информации в природе и технике. В конце сороковых годов, на заре развития теории информации, идеи разработки новых эффективных способов кодирования информации носились в воздухе. Исследователи занимались вопросами энтропии, содержимого информации и избыточности. Интересно, что эти первоначальные работы в области сжатия информации велись до появления современного цифрового компьютера. Сегодня теория информации развивается параллельно с программированием, но в то время идея разработки алгоритмов, использующих двоичную арифметику для кодирования символов, была значительным шагом вперед. Одними из первых алгоритмов эффективного кодирования информации были алгоритмы Шеннона - Фано и Хафмана. В данной работе рассмотрены базовые понятия энтропии и информации, а также описаны принципы кодирования сообщений по Шеннону - Фано и Хафману, показана их важная роль при передаче информации по линиям связи. Но линии связи, для которых были разработаны эти методы кодирования информации, уже в прошлом. К счастью, для принципов Шеннона - Фано и Хафмана нашли применение и в современном мире: для сжатия информации. Архиваторы PKZIP, ARJ, а также часть всем нам хорошо известного стандарта JPEG (сжатие графической информации с потерями) работают именно на этих принципах. Коды Шеннона - Фано и Хафмана преподаются во всех технических ВУЗах мира и, кроме того, входят в программу для углубленного изучения информатики в школе. Поэтому изучение методов кодирования Шеннона - Фано и Хафмана является актуальным. Цель данной работы - изучить принципы кодирования информации Шеннона - Фано и Хафмана и применение их при решении задач. Задача состоит в том, чтобы изучить энтропии и избыточность конкретных типов сообщений для последующего применения к ним принципов Шеннона - Фано и Хафмана. 1. Информация и кодирование. Коды Шеннона - Фано и Хафмана. 1.1 Информация и кодирование. Слово "информация" известно в наше время каждому. Происходит оно от латинского "informatio", что означает - разъяснение, сообщение, осведомленность. Однако в постоянное употребление оно вошло не так давно, в середине двадцатого века, с подачи Клода Шеннона. Он ввел этот термин в узком техническом смысле применительно к теории связи или передачи кодов, которая получила название "Теория информации". Здесь важны не любые сведения, а лишь те, которые снимают полностью или уменьшают существующую неопределенность. Философское, и поэтому более широкое определение этого термина дает один из основателей информатики, известный американский ученый Норберт Винер: "Информация - это обозначение содержания, черпаемого нами из внешнего мира в процессе нашего приспособления к нему и приведение в соответствие с ним нашего мышления". Разумеется, это далеко не единственные в своем роде определения информации. В настоящее время этот термин имеет более глубокий и многогранный смысл. Во многом оставаясь интуитивным, он получает разные смысловые наполнения в разных отраслях человеческой деятельности: * в житейском аспекте под информацией понимают сведения об окружающем мире и протекающих в нем процессах, воспринимаемые человеком или специальными устройствами; * в технике под информацией понимают сообщения, передаваемые в форме знаков или сигналов; * в теории информации (по К. Шеннону) важны не любые сведения, а лишь те, которые снимают полностью или уменьшают существующую неопределенность; * в семантической теории (смысл сообщения) - это сведения, обладающие новизной, и так далее... Такое разнообразие подходов не случайно, а следствие того, что выявилась необходимость осознанной организации процессов движения и обработки того, что имеет общее название - информация. Для дальнейшего рассмотрения нам необходимо то понятие информации, которое подразумевает передачу информационных сообщений по линиям связи. Рассмотрим общую схему передачи сообщений; для определенности будем говорить, например, о телеграфии. На одном конце линии отправитель подает некоторое сообщение, записанное при помощи любого из известных нам алфавитов или цифр, или и букв и цифр вместе взятых. Для передачи такого рода сообщений используются последовательности сигналов постоянного тока, некоторые характеристики которого телеграфист может менять по своему усмотрению, воспринимаемых вторым телеграфистом на приемном конце линии. Простейшими различимыми сигналами, широко используемыми на практике, является посылка тока (т.е. включение его на некоторое вполне определенное время) и отсутствие посылки - пауза (выключение тока на то же время); при помощи одних только этих двух сигналов уже можно передать любое сообщение, если условиться заменять каждую букву или цифру определенной комбинацией посылок тока и пауз. В технике связи правило, сопоставляющее каждому передаваемому сообщению некоторую комбинацию сигналов, обычно называется кодом (в случае телеграфии - телеграфным кодом), а сама операция перевода сообщения в последовательность различных сигналов - кодированием сообщения. Под "кодом" будет пониматься такая совокупность п кодовых обозначений, сопоставляемых п буквам алфавита, для которой выполняется условие: никакое кодовое обозначение одной буквы не совпадает с началом какого-либо другого более длинного кодового обозначения, т.е. коды должны быть однозначно декодируемыми. При этом коды, использующие только два различных элементарных сигнала (например, посылку тока и паузу), называются двоичными кодами. В некоторых телеграфных аппаратах кроме простого включения и выключения тока можно также изменять его направление на обратное. При этом появляется возможность вместо посылок тока и пауз использовать в качестве основных сигналов посылку тока в двух различных направлениях или же использовать сразу три различных элементарных сигнала одной и той же длительности - посылку тока в одном направлении, посылку тока в другом направлении и паузу (такой способ кодирования называется троичным кодом). Возможны также еще более сложные телеграфные аппараты, в которых посылки тока различаются не только оп направлению, но и по силе тока; тем самым мы получаем возможность сделать число различных элементарных сигналов еще большим. Увеличение числа разных элементарных сигналов позволяет сделать код более сжатым. Однако вместе с тем оно усложняет и удорожает систему передачи, так что в технике все же предпочтительно используются коды с малым числом элементарных сигналов. Пусть имеется сообщение, записанное при помощи некоторого "алфавита", содержащего п "букв". Требуется "закодировать" это сообщение, т.е. указать правило, сопоставляющее каждому такому сообщению определенную последовательность из т различных "элементарных сигналов", составляющих "алфавит" передачи. Мы будем считать кодирование тем более выгодным, чем меньше элементарных сигналов приходится затратить на передачу сообщения. Если считать, что каждый из элементарных сигналов продолжается одно и то же время, то наиболее выгодный код позволит затратить на передачу сообщения меньше всего времени. Главным свойством случайных событий является отсутствие полной уверенности в их наступлении, создающее известную неопределенность при выполнении связанных с этими событиями опытов. Однако совершенно ясно, что степень этой неопределенности в различных случаях будет совершенно разной. Для практики важно уметь численно оценивать степень неопределенности самых разнообразных опытов, чтобы иметь возможность сравнить их с этой стороны. Рассмотрим два независимых опыта и а также сложный опыт, состоящий в одновременном выполнении опытов и. Пусть опыт имеет k равновероятных исходов, а опыт имеет l равновероятных исходов. Очевидно, что неопределенность опыта больше неопределенности опыта, так как к неопределенности здесь добавляется еще неопределенность исхода опыта. Естественно считать, что степень неопределенности опыта равна сумме неопределенностей, характеризующих опыты и, т.е.: . Условиям, при удовлетворяет только одна функция - : . Рассмотрим опыт А, состоящий из опытов и имеющих вероятности. Тогда общая неопределенность для опыта А будет равна Это последнее число будем называть энтропией опыта и обозначать через. Если число букв в "алфавите" равно п, а число используемых элементарных сигналов равно т, то при любом методе кодирования среднее число элементарных сигналов, приходящихся на одну букву алфавита, не может быть меньше чем; однако он всегда может быть сделано сколь угодно близким к этому отношению, если только отдельные кодовые обозначения сопоставлять сразу достаточно длинными "блоками", состоящими из большого числа букв. Мы рассмотрим здесь лишь простейший случай сообщений, записанных при помощи некоторых п "букв", частоты проявления которых на любом месте сообщения полностью характеризуется вероятностями р1, р2, ... ..., рп, где, разумеется, р1 + р2 + ... + рп = 1, при котором вероятность pi проявления i-й буквы на любом месте сообщения предполагается одной и той же, вне зависимости от того, какие буквы стояли на всех предыдущих местах, т.е. последовательные буквы сообщения независимы друг от друга. На самом деле в реальных сообщениях это чаще бывает не так; в частности, в русском языке вероятность появления той или иной буквы существенно зависит от предыдущей буквы. Однако строгий учет взаимной зависимости букв сделал бы все дельнейшие рассмотрения очень сложными, но никак не изменит будущие результаты. Мы будем пока рассматривать двоичные коды; обобщение полученных при этом результатов на коды, использующие произвольное число т элементарных сигналов, является, как всегда, крайне простым. Начнем с простейшего случая кодов, сопоставляющих отдельное кодовое обозначение - последовательность цифр 0 и 1 - каждой "букве" сообщения. Каждому двоичному коду для п-буквенного алфавита может быть сопоставлен некоторый метод отгадывания некоторого загаданного числа х, не превосходящего п, при помощи вопросов, на которые отвечается лишь "да" (1) или "нет" (0) , что и приводит нас к двоичному коду. При заданных вероятностях р1, р2, ... ..., рп отдельных букв передача многобуквенного сообщения наиболее экономный код будет тот, для которого при этих именно вероятностях п значений х среднее значение числа задаваемых вопросов (двоичных знаков: 0 и 1 или элементарных сигналов) оказывается наименьшим. Прежде всего среднее число двоичных элементарных сигналов, приходящихся в закодированном сообщении на одну букву исходного сообщения, не может быть меньше Н, где Н = - p1 log p1 - p2 log p2 - ... - pn log pn - энтропия опыта, состоящего в распознавании одной буквы текста (или, короче, просто энтропия одной буквы). Отсюда сразу следует, что при любом методе кодирования для записи длинного сообщения из М букв требуется не меньше чем МН двоичных знаков, и никак не может превосходить одного бита. Если вероятности р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-я часть будет состоять лишь из одной буквы. № буквывероят-ностьразбиение на подгруппы (римские цифры обозначают номера групп и подгрупп)кодовое обозначение10,4} I 120,2} II} I 0130,2} II} I 00140,1} II} I 000150,05} II} I0000160,05} II00000 Табл.1 Аналогично предыдущему примеру разобран случай "алфавита", включающего 18 букв, имеющих следующие вероятности: 0,3; 0,2; 0,1 (2 буквы); 0,05; 0,03 (5 букв); 0,02(2 буквы); 0,01 (6 букв). (Табл. 2) № буквывероят-ностьразбиение на подгруппы кодовое обозначение10,3} I} I 1120,2} II 1030,1} II} I} I 01140,1} II} I 010150,05} II 010060,03} II} I} I} I 0011170,03} II 0011080,03} II} I 0010190,03} II 00100100,03} II} I} I 00011110,02} II} I 000101120,02} II 000100130,01} II} I} I 000011140,01} II} I0000101150,01} II0000100160,01} II} I 000001170,01} II} I0000001180,01} II0000000 Табл.2 Основной принцип, положенный в основу кодирования по методу Шеннона - Фано, заключается в том, что при выборе каждой цифры кодового обозначения мы стараемся, чтобы содержащееся в ней количество информации было наибольшим, т. е. чтобы независимо от значений всех предыдущих цифр эта цифра принимала оба возможных для нее значения 0 и 1 по возможности с одинаковой вероятностью. Разумеется, количество цифр в различных обозначениях при этом оказывается различным (в частности, во втором из разобранных примеров он меняется от двух до семи), т. е. код Шеннона - Фано является неравномерным. Нетрудно понять, однако, что никакое кодовое обозначение здесь не может оказаться началом другого, более длинного обозначения; поэтому закодированное сообщение всегда может быть однозначно декодировано. В результате, среднее значение длины такого обозначения все же оказывается лишь немногим большим минимального значения Н, допускаемого соображениями сохранения количества информации при кодировании. Так, для рассмотренного выше примера 6-буквенного алфавита наилучший равномерный код состоит из трехзначных кодовых обозначений (ибо 22 < 6 < 23), и поэтому в нем на каждую букву исходного сообщения приходится ровно 3 элементарных сигнала; при использовании же кода Шеннона - Фано среднее число элементарных сигналов, приходящихся на одну букву сообщения, равно Это значение заметно меньше, чем 3, и не очень далеко от энтропии Аналогично этому для рассмотрения примера 18-буквенного алфавита наилучший равномерный код состоит из пятизначных кодовых обозначений (так как 24 < 18 < 25); в случае же кода Шеннона - Фано имеются буквы, кодируемые даже семью двоичными сигналами, но зато среднее число элементарных сигналов, приходящихся на одну букву, здесь равно Последнее значение заметно меньше, чем 5, - и уже не намного отличается от величины Особенно выгодно бывает кодировать по методу Шеннона - Фано не отдельные буквы, а сразу целые блоки из нескольких букв. Правда, при этом все равно невозможно превзойти предельное значение Н двоичных знаков на одну букву сообщения. Рассмотрим, например, случай, когда имеются лишь две различные буквы А и Б, имеющие вероятности р(А) = 0,7 и р(Б) = 0,3; тогда H = - 0,7 log0,7 - 0,3 log0,3 = 0,881... Применение метода Шеннона - Фано к исходному двухбуквенному алфавиту здесь оказывается бесцельным: оно приводит нас лишь к простейшему равномерному коду буква вероятность кодовое обозначение А 0,7 1 Б 0,3 0 требующему для передачи каждой буквы одного двоичного знака - на 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А410,40,40,40,40,620,20,20,20,40,430,20,20,20,240,10,10,250,050,160,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А410,4 00,4 00,4 0 0,4 00,6 120,2 100,2 100,2 100,4 11 0,4 030,2 1110,2 1110,2 1110,2 10 40,1 11010,1 11010,2 110 50,05 110010,1 1100 60,05 11000 Табл. 4 Легко видеть, что из самого построения получаемого таким образом кода Хафмана вытекает, что он удовлетворяет общему условию: никакое кодовое обозначение не является здесь началом другого, более длинного кодового обозначения. Заметим еще, что кодирование некоторого алфавита по методу Хафмана (так же, впрочем, как и по методу Шеннона - Фано) не является однозначной процедурой. Так, например, на любом этапе построения кода можно, разумеется, заменить цифру 1 на цифру 0 и наоборот; при этом мы получим два разных кода (отличающихся весьма несущественно друг от друга). Но помимо того в некоторых случаях можно построить и несколько существенно различающихся кодов Хафмана; так, например, в разобранном выше примере можно строить код и в соответствии со следующей таблицей: № буквыВероятностиисходный алфавит Асжатые алфавитыА1А2А3А410,4 110,4 110,4 11 0,4 00,6 120,2 010,2 010,2 100,4 11 0,4 030,2 000,2 000,2 010,2 10 40,1 1000,1 1010,2 00 50,05 10110,1 100 60,05 1010 Табл.5 Получаемый при этом новый код также является кодом Хафмана, но длины имеющихся кодовых обозначений теперь уже оказываются совсем другими. Отметим, что среднее число элементарных сигналов, приходящихся на одну букву, для обоих построенных кодов Хафмана оказывается точно одинаковым: в первом случае оно равно, а во втором - равно. Можно показать, что код Хафмана всегда является самым экономичным из всех возможных в том смысле, что ни для какого другого метода кодирования букв некоторого алфавита среднее число элементарных сигналов, приходящихся на одну букву, не может быть меньше того, какое получается при кодировании по методу Хафмана (отсюда, разумеется, сразу вытекает и то, что для любых двух кодов Хафмана средняя длина кодового обозначения должна быть точно одинаковой - ведь оба они являются наиболее экономными). Рассуждения, приведенные в пунктах 1.2 и 1.3 полностью реализуются при решении задач (пример такой задачи приведен в приложении А). 2. Энтропия конкретных типов сообщений. 2.1 Основная теорема о кодировании. Достигнутая в рассмотренных выше примерах степень близости среднего числа двоичных знаков, приходящихся на одну букву сообщения, к значению Н может быть еще сколь угодно увеличена при помощи перехода к кодированию все более и более длинных блоков. Это вытекает из следующего общего утверждения, которое мы будем в дальнейшем называть основной теоремой о кодировании, точнее, основной теоремой о кодировании при отсутствии помех: при кодировании сообщения, разбитого на N-буквенные блоки, можно, выбрав N достаточно большим, добиться того, чтобы среднее число двоичных элементарных сигналов, приходящихся на одну букву исходного сообщения, было сколь угодно близко к Н. Кодирование сразу длинных блоков имеет значительные преимущества при наличии помех, препятствующих работе линии связи. Ввиду большой важности сформулированной здесь основной теоремы о кодировании мы приведем ниже ее доказательство, основанное на использовании метода кодирования Шеннона - Фано. Предположим сначала, что при составляющем основу метода Шеннона - Фано последовательном делении совокупности кодируемых букв (под которыми могут пониматься также целые "блоки") на все меньшие и меньшие группы нам каждый раз удается добиться того, чтобы вероятности двух получаемых групп были точно равны между собой. В таком случае после первого деления мы придем к группам, имеющим суммарную вероятность 1/2, после второго - к группам суммарной вероятности 1/4, ..., после l-го деления - к группам суммарной вероятности 1/2l. При этом l-значное кодовое обозначении будут иметь те буквы, которые оказываются выделенными в группу из одного элемента ровно после l делений; иначе говоря, при выполнении этого условия длина li кодового обозначения будет связана с вероятностью рi соответствующей буквы формулой В общем случае величина - log pi, где pi - вероятность i-й буквы алфавита, целым числом не будет, поэтому длина li кодового обозначения i-й буквы не сможет быть равна log pi. Поскольку при кодировании по методу Шеннона - Фано мы последовательно делим наш алфавит на группы, по возможности близкой суммарной вероятности, то длина кодового обозначения i-й буквы при таком кодировании будет близка к - log pi. Обозначим, в этой связи, через li первое целое число, не меньше чем - log pi: (А) Последнее неравенство можно переписать еще так: или (Б) Здесь отметим, что в случае любых п чисел, удовлетворяющих неравенству, (1) существует двоичный код, для которого эти числа являются длинами кодовых обозначений, сопоставляемых п буквам некоторого алфавита. Среднее число l двоичных сигналов, приходящихся на одну букву исходного сообщения (или, средняя длина кодового обозначения) дается суммой. Умножим теперь задающее величину li неравенство (А) на pi, сложим все полученные таким образом неравенства, отвечающие значениям i = 1, 2, ..., п, и учтем, что, где - энтропия опыта, состоящего в определении одной буквы сообщения, и что p1 + p2 + ... +pn = 1. В результате получаем, что. Применим это неравенство к случаю, когда описанный выше метод используется для кодирования всевозможных N-буквенных блоков (которые можно считать буквами нового алфавита). В силу предположения о независимости последовательных букв сообщения энтропия опыта, состоящего в определении всех букв блока, равна Следовательно, средняя длина lN кодового обозначения N-буквенного блока удовлетворяет неравенствам Но при кодировании сразу N-буквенных блоков среднее число l двоичных элементарных сигналов, приходящихся на одну букву сообщения, будет равно средней длине lN кодового обозначения одного блока, деленной на число N букв в блоке: . Поэтому при таком кодировании, то есть здесь среднее число элементарных сигналов, приходящихся на одну букву, отличается от минимального значения Н не больше, чем на. Полагая, мы сразу приходим к основной теореме о кодировании. Приведенное доказательство может быть применено также и к более общему случаю, когда последовательные буквы текста являются взаимно зависимыми. При этом придется только неравенство для величины lN писать в виде, где - энтропия N-буквенного блока, которая в случае зависимости букв сообщения друг от друга всегда будет меньше чем NH (ибо и). Отсюда следует, что, значит, в этом более общем случае при (при безграничном увеличении длины блоков) среднее число элементарных сигналов, затрачиваемых на передачу одной буквы, неограниченно приближается к величине, где есть "удельная энтропия", приходящаяся на одну букву многобуквенного текста. Существование предела следует из неравенств, показывающих, что последовательность является монотонно не возрастающей последовательностью положительных (больших 0) чисел. Все предыдущее утверждения легко переносятся также и на случай т-ичных кодов, использующих т элементарных сигналов. Так, для построения т-ичных кодов Шеннона - Фано надо лишь разбивать группы символов не на две, а на т частей по возможности близкой вероятности, а для построения т-ичного кода Хаффмана надо использовать операцию сжатия алфавита, при которой каждый раз сливаются не две, а т букв исходного алфавита, имеющих наименьшие вероятности. Ввиду важности кодов Хаффмана, остановимся на последнем вопросе чуть подробнее. Сжатие алфавита, при котором т букв заменяются на одну, приводит к уменьшению числа букв на т - 1; так как для построения т-ичного кода, очевидно, требуется, чтобы последовательность "сжатий" в конце концов привела нас к алфавиту из т букв (сопоставляемых т сигналам кода), то необходимо, чтобы число п букв первоначального алфавита было представимо в виде n = m + k(m - 1), где k - целое число. Этого, однако, всегда можно добиться, добавив, если нужно, к первоначальному алфавиту еще несколько "фиктивных букв", вероятности которых считаются равными нулю. После этого построение т-ичного кода Хаффмана и доказательство его оптимальности (среди всех т-ичных кодов) проводятся уже точно так же, как и случае двоичного кода. Так, например, в случае уже рассматривавшегося выше алфавита из 6 букв, имеющих вероятности 0,4, 0,2, 0,2, 0,1, 0,05, и 0,05 для построения троичного кода Хаффмана, надо присоединить к нашему алфавиту еще одну букву нулевой вероятности и далее поступать так, как указано ниже: № буквывероятности и кодовые обозначенияисходный алфавитсжатые алфавиты10,4 00,4 00,4 020,2 20,2 20,4 130,2 100,2 100,2 240,1 110,1 11 50,05 1200,1 12 60,05 121 70 - Табл.6 Столь же просто переносятся на случай т-ичных кодов и на приведенное выше доказательство основной теоремы о кодировании. В частности, соответствующее видоизменение основывается на том факте, что любые п чисел l1, l2, ..., ln , удовлетворяющих неравенству, являются длинами кодовых обозначений некоторого т-ичного кода для п-буквенного алфавита. Повторяя рассуждения для случая т = 2, легко получить следующий результат (называемый основной теоремой о кодировании для т-ичных кодов): при любом методе кодирования, использующем т-ичный код, среднее число элементарных сигналов, приходящихся на одну букву сообщения, никогда не может быть меньше отношения (где Н - энтропия одной буквы сообщения); однако оно всегда может быть сделано сколь угодно близким к этой величине, если кодировать сразу достаточно длинные "блоки" из N букв. Отсюда ясно, что если по линии связи за единицу времени можно передать L элементарных сигналов (принимающих т различных значений), то скорость передачи сообщений по такой линии не может быть большей, чем букв/ед. времени; однако передача со скоростью, сколь угодно близкой к v (но меньшей v!), уже является возможной. Величина, стоящая в числителе выражения для v, зависит лишь от самой линии связи (в то время как знаменатель Н характеризует передаваемое сообщение). Эта величина указывает на наибольшее количество единиц информации, которое можно передать по нашей линии за единицу времени (ибо один элементарный сигнал, как мы знаем, может содержать самое большее log m единиц информации); она называется пропускной способностью линии связи. Понятие пропускной способности играет важную роль в теории связи. 2.2 Энтропия и информация конкретных типов сообщений. 2.2.1 Письменная речь Для передачи М-буквенного сообщения допускающей m различных элементарных сигналов, требуется затратить не меньше чем сигналов, где n - число букв "алфавита. Так как русский "телеграфный" алфавит содержит 32 буквы (не различаются букв е и ё, ь и ъ, но причисляются к числу букв и "нулевая буква" - пустой промежуток между словами), то на передачу М-буквенного сообщения надо затратить элементарных сигналов. Здесь Н0 = log 32 = 5 бит - энтропия опыта, заключающегося в приеме одной буквы русского текста, при условии, что все буквы считаются одинаково вероятными. Для получения текста, в котором каждая буква содержит 5 бит информации требуется выписать 32 буквы на отдельных билетиках, сложить все эти билетики в урну и затем вытаскивать их по одному, каждый раз записывая вытянутую букву, а билетик возвращая обратно в урну и снова перемешивая ее содержимое. Произведя такой опыт, мы придем к "фразе" вроде следующей: СУХЕРРОБЬДЩ ЯЫХВЩИЮАЙЖТЛФВНЗАГФОЕН-ВШТЦР ПХГБКУЧТЖЮРЯПЧЬКЙХРЫС Разумеется, этот текст имеет очень мало общего с русским языком! Для более точного вычисления информации, содержащейся в одной букве русского текста, надо знать вероятности появления различных букв. Ориентировочные значения частот отдельных букв русского языка собраны в следующей таблице: буква относ. частота- 0,175о 0,090е, ё 0,072а 0,062и 0,062т 0,053н 0,053с 0,045буква относ. частотар 0,040в 0,038л 0,035к 0,028м 0,026д 0,025п 0,023у 0,021буква относ. частотая 0,018ы 0,016з 0,016ь, ъ 0,014б 0,014г 0,013ч 0,012й 0,010буква относ. частотах 0,009ж 0,007ю 0,006ш 0,006ц 0,004щ 0,003э 0,003ф 0,002 Табл.7 Приравняв эти частоты вероятностям появления соответствующих букв, получим для энтропии одной буквы русского текста приближенное значение): бит. Из сравнения этого значения с величиной Н0 = log 32 = 5 бит видно, что неравномерность появления различных букв алфавита приводит к уменьшению информации, содержащейся в одной букве русского текста, примерно на 0,65 бит. Сокращение числа требующихся элементарных сигналов можно показать кодированием отдельных букв русского алфавита по методу Шеннона - Фано: буквакод. обозн.буквакод. обозн.буквакод. обозн.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 Табл.8 Среднее количество элементарных сигналов при таком методе кодирования, будет равно, то есть будет весьма близко к значению При определении энтропии опыта состоящего в определении одной буквы русского текста, мы считали все буквы независимыми. Это значит, что для составления "текста", в котором каждая буква содержит бит информации, мы должны прибегнуть к помощи урны, в которой лежат тщательно перемешанные 1000 бумажек, на 175 из которых не написано ничего, на 90 - написана буква о, на 72 - буква е, ..., наконец, на 2 бумажках - буква ф (см. табл.7). Извлекая из такой урны бумажки по одной, мы придем к "фразе" вроде следующей: ЕЫНТ ЦИЯЬА ОЕРВ ОДНГ ЬУЕМЛОЛЙК ЗБЯ ЕНВТША. Эта "фраза" несколько более похожа на осмысленную русскую речь, чем предыдущая, но и она, разумеется, еще очень далека от разумного текста. Несходство нашей фразы с осмысленным текстом естественно объясняется тем, что на самом деле последовательные буквы русского текста вовсе не независимы друг от друга. Так, например, если мы знаем, что очередной буквой явилась гласная, то значительно возрастает вероятность появления на следующем месте согласной буквы; буква "ь" никак не может следовать ни за пробелом, ни за гласной буквой; за буквой "ч" никак не могут появиться буквы "ы", "я" или "ю", а скорее всего будет стоять одна из гласных "и" и "е" или согласная "т" и т. д. Наличие в русском языке дополнительных закономерностей, не учтенных в нашей "фразе", приводит к дальнейшему уменьшению степени неопределенности одной буквы русского текста. Для этого надо лишь подсчитать условную энтропию опыта, состоящего в определении одной буквы русского текста, при условии, что нам известен исход опыта, состоящего в определении предшествующей буквы того же текста. Условная энтропия определяется следующей формулой: где через р(-), р(а), р(б), ..., р(я) обозначены вероятности (частоты) отдельных букв русского языка. Разумеется заранее можно сказать, что вероятности р(- -), р(яь) и многие другие (например, р(ьь), р(- ь), р(чя) и т.д.) будут равны нулю. Мы можем быть уверены, что условная энтропия окажется меньше безусловной энтропии. Величину можно конкретизировать как "среднюю информацию", содержащуюся в определении исхода следующего опыта. Имеется 32 урны, обозначенные 32 буквами русского алфавита; в каждой из урн лежат бумажки, на которых выписаны двухбуквенные сочетания, начинающиеся с обозначенной на урне буквы, причем количества бумажек с разными парами букв пропорциональны частотам (вероятностям) соответствующих двухбуквенных сочетаний. Опыт состоит в многократном извлечении бумажек из урн и выписывании с них последней буквы. При этом каждый раз (начиная со второго) бумажка извлекается из той урны, которая содержит сочетания, начинающиеся с последней выписанной буквы; после того как буква выписана, бумажка возвращается в урну, содержимое которой снова тщательно перемешивается. Опыт такого рода приводит к "фразе" вроде следующей: УМАРОНО КАЧ ВСВАННЫЙ РОСЯ НЫХ КОВКРОВ НЕДАРЕ. По звучанию эта "фраза" заметно ближе к русскому языку. Знание двух предшествующих букв еще более уменьшает неопределенность опыта, состоящего в определении следующей буквы, что находит отражение в положительности разности, где - "условная энтропия второго порядка": Наглядным подтверждением сказанного является опыт, состоящий в вытаскивании бумажек с трехбуквенными сочетаниями из 322 урн, в каждой из которых лежат бумажки, начинающиеся на одни и те же две буквы (или опыт с русской книгой, в которой много раз наудачу отыскивается первое повторение последнего уже выписанного двухбуквенного сочетания и выписывается следующая за ним буква), приводит к "фразе" вроде следующей: ПОКАК ПОТ ДУРНОСКАКА НАКОНЕПНО ЗНЕ СТВОЛОВИЛ СЕ ТВОЙ ОБНИЛЬ, еще более близкой к русской речи, чем предыдущая. Аналогично этому можно определить и энтропию отвечающую опыту по определению буквы русского текста при условии знания трех предшествующих букв. Он состоит в извлечении бумажек из 323 урн с четырехбуквенными сочетаниями (или - аналогичный описанному выше эксперимент с русской книгой), приводит к "фразе" вроде следующей: ВЕСЕЛ ВРАТЬСЯ НЕ СУХОМ И НЕПО И КОРКО, Еще лучшее приближение к энтропии буквы осмысленного русского текста дают величины при N = 5,6, .... Нетрудно видеть, что с ростом N энтропия НN может только убывать. Если еще учесть, что все величины НN положительны, то отсюда можно будет вывести, что величина при стремится к определенному пределу. Нам уже известно, что среднее число элементарных сигналов, необходимое для передачи одной буквы русского текста, не может быть меньшим. Разность, показывающую, насколько меньше единицы отношение "предельной энтропии" к величине, характеризующей наибольшую информацию, которая может содержаться в одной букве алфавита с данным числом букв, Шеннон назвал избыточностью языка. Избыточность русского языка (как и избыточность других европейских языков) заметно превышает 50%. То есть, мы можем сказать, что выбор следующей буквы осмысленного текста более, чем на 50% определяется самой структурой языка и, следовательно, случаен лишь в сравнительно небольшой степени. Избыточность R является весьма важной статистической характеристикой языка, но ее численное значение пока ни для одного языка не определено с удовлетворительной точностью. В отношении русского языка, в частности, имеются лишь данные о значениях величин Н2 и Н3. Н0Н1Н2Н3log 32 = 54,353,523,01(для полноты мы здесь привели также и значения энтропии Н0 и Н1). Отсюда можно только вывести, что для русского языка, на самом деле величина R значительно больше этого числа. Ясно, что для всех языков, использующих латинский алфавит, максимальная информация Н0, которая могла бы приходиться па одну букву текста, имеет одно и то же значение: бит (26 различных букв алфавита и 27-я "буква" - пустой промежуток между словами). Использовав таблицы относительных частот различных букв в английском, немецком, французском и испанском языках, можно показать, что энтропия Н1 для этих языков равна (в битах): языкангл.немецк.франц.испанск.Н14,034,103,963,98 Мы видим, что во всех случаях величина Н1 заметно меньше, чем Н0 = log 27 4,76 бит, причем ее значения для различных языков не очень сильно разнятся между собой. Величины Н2 и Н3 для английского языка были подсчитаны Шенноном, при этом он использовал имеющиеся таблицы частот в английском языке различных двухбуквенных и трехбуквенных сочетаний. Учтя также и статистические данные о частотах появления различных слов в английском языке, Шеннон сумел приближенно оценить и значения величин Н5 и H8. В результате он получил: Н0Н1 Н2Н3Н5Н84,764,03 3,323,10≈2,1≈1,9 Отсюда можно заключить, что для английского языка избыточность R во всяком случае не меньше, чем, т. е., превосходит 60%. Подсчет величин Н9, Н10 и т. д. по известной нам формуле невозможенен, так как уже для вычисления Н9 требуется знание вероятностей всех 9-буквенных комбинаций, число которых выражается 13-значным числом (триллионы!). Поэтому для оценки величин HN при больших значениях N приходится ограничиваться косвенными методами. Остановимся на одном из такого рода методе, предложенном Шенноном. "Условная энтропия" НN представляет собой меру степени неопределенности опыта, состоящего в определении N-й буквы текста, при условии, что предшествующие N - 1 букв нам известны. Эксперимент по отгадыванию N-й буквы легко может быть поставлен: для этого достаточно выбрать (N - 1)-буквенный отрывок осмысленного текста и предложить кому-либо отгадать следующую букву. Подобный опыт может быть повторен многократно, при этом трудность отгадывания N-й буквы может быть оценена с помощью среднего значения QN числа попыток, требующихся для нахождения правильного ответа. Ясно, что величины QN, определенные для разных значений 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 000. Из полученных данных можно заключить, что величина Н32 (так же как и H64 и Н128) практически не отличается от Н10000, в то время как "условная энтропия" Н16 еще заметно больше этой величины. Таким образом, можно предположить, что при возрастании N величина HN убывает вплоть до значений N = 30, но при дальнейшем росте N она уже практически не меняется; поэтому вместо "предельной энтропии" можно говорить, например, об условной энтропии H30 или H40. Эксперименты по отгадыванию букв не только позволяют судить о сравнительной величине условных энтропии HN при разных N, но дают также возможность оцепить и сами значения НN. По данным таких экспериментов можно определить не только среднее число QN попыток, требующихся для отгадывания N-й буквы текста по N - 1 предшествующим, но и вероятности (частоты) того, что буква будет правильно угадана с 1-й, 2-й, 3-й, ..., n-й попытки (где п = 27 - число букв алфавита; QN =). Нетрудно понять, что вероятности равны вероятностям букв алфавита, расположенных в порядке убывания частот. В самом деле, если ни одна из букв, предшествующих отгадываемой букве х, нам не известна, то естественно прежде всего предположить, что х совпадает с самой распространенной буквой a1 (причем вероятность правильно угадать здесь будет равна р(а1)); затем следует предположить, что х совпадает с а2 (вероятность правильного ответа здесь будет равна р(а2)) и т. д. Отсюда следует, что энтропия Н1 равна сумме. Если же N > 1, то можно показать, что сумма (*) не будет превосходить условную энтропию HN (это связано с тем, что величины представляют собой определенным образом усредненные вероятности исходов опыта). С другой стороны, несколько более сложные соображения, на которых мы здесь не будем останавливаться, позволяют доказать, что сумма (**) при всяком N будет не больше условной энтропии НN. Таким образом, выражения (*) и (**) (составленные из вероятностей, которые можно оценить по данным эксперимента) определяют границы, между которыми должна заключаться величина HN. Надо только еще иметь в виду, что обе оценки (*) и (**) получаются в предположении, что - это те вероятности угадывания буквы по N - 1 предыдущим буквам с первой, второй, третьей и т. д. попыток, которые получаются в предположении, что отгадывающий всегда называет очередную букву наиболее целесообразно - с полным учетом всех статистических закономерностей данного языка. В случае же реальных опытов любые ошибки в стратегии отгадывающего (т. е. отличия называемых им букв от тех, которые следовало бы назвать, исходя из точной статистики языка) будут неизбежно приводить к завышению обеих сумм (*) и (**); именно поэтому целесообразно учитывать лишь данные "наиболее успешного отгадывающего", так как для него это завышение будет наименьшим. Поскольку каждый отгадывающий иногда ошибается, то оценку (**) на практике нельзя считать вполне надежной оценкой снизу истинной энтропии (в отличие от оценки сверху (*), которая из-за ошибок отгадывающего может только стать еще больше). Кроме того, значения сумм (*) и (**), к сожалению, не сближаются неограниченно при увеличении N (начиная с N ≈ 30 эти суммы вообще перестают зависеть от N); поэтому полученные на этом пути оценки избыточности языка не будут особенно точными. В частности, опыты Шеннона показали лишь, что величина H100 по-видимому, заключается между 0,6 и 1,3 бит. Отсюда можно заключить, что избыточность для английского языка по порядку величины должна быть близка к 80%. 2.2.2 Устная речь. Перейдем теперь к вопросу об энтропии и информации устной речи. Естественно думать, что все статистические характеристики такой речи будут еще более зависеть от выбора разговаривающих лиц и от характера их разговора. Пониженное значение энтропии устной речи может быть связано с тем, что в разговоре мы зачастую употребляем больше повторений одних и тех же слов и нередко добавляем довольно много "лишних" слов - это делается как для облегчения восприятия речи, так и просто затем, чтобы говорящий имел время обдумать, что он хочет сказать дальше. Определив среднее число букв, произносимых за единицу времени, можно приближенно оценить количество информации, сообщаемое при разговоре за 1 сек; обычно оно имеет порядок 5 - 6 бит. Из разговора мы можем судить о настроении говорящего и об его отношении к сказанному; мы можем узнать говорящего, если даже никакие другие источники информации не указывают нам его; мы можем во многих случаях определить место рождения незнакомого нам человека по его произношению; мы можем оценить громкость устной речи, которая в случае передачи голоса по линии связи во многом определяется чисто техническими характеристиками линии передачи, и т. д. Количественная оценка всей этой информации представляет собой очень сложную задачу, требующую значительно больших знаний об языке. Исключением в этом отношении является сравнительно узкий вопрос о логических ударениях, подчеркивающих в фразе отдельные слова. Ударение чаще всего падает на наиболее редко употребляемые слова (что, впрочем, довольно естественно - ясно, что вряд ли кто будет выделять логическим ударением наиболее распространенные слона - например, предлоги или союзы). Если вероятность того, что данное слово Wr находится под ударением, мы обозначим через qr, то средняя информация, заключающаяся в сведениях о наличии или отсутствии ударения на этом слове, будет равна Пусть теперь - вероятности (частоты) всех слов W1, W2, . . ., WK (здесь К - общее число всех употребляемых слов. В таком случае для средней информации Н, заключенной в логическом ударении, можно написать следующую формулу: Cредняя информация, которую мы получаем, выяснив, на какие слова падает логическое ударение, по порядку величины близка к 0,65 бит/слово. Во время разговора отдельные буквы никогда не произносятся, а произносятся звуки, существенно отличающиеся от букв. Поэтому основным элементом устной речи надо считать отдельный звук - фонему. Осмысленная устная речь составляется из фонем точно так же, как осмысленная письменная речь составляется из букв. Поэтому во всех случаях, когда нас интересует лишь передача "смысловой информации" устной речи наибольший интерес представляет не энтропия и информация одной "произнесенной буквы", а энтропия и информация одной реально произнесенной фонемы. Список фонем данного языка, разумеется, не совпадает со списком букв алфавита, так как одна и та же буква в разных случаях может звучать по-разному. В русском языке 42 различные фонемы и подсчитали частоты отдельных фонем (а также различных комбинаций двух и трех следующих друг за другом фонем). Н0 = log 42 одной фонемы, энтропии первого порядка (где - относительные частоты различных фонем) и "условных энтропии" Н2 и Н3: Н0Н1Н2Н3log 42 ≈ 5,38 4,77 3,62 0,70 Если сравнить эти значения со значениями величин Н0, Н1, Н2, H3 для письменной русской речи, то убывание ряда условных энтропии для фонем происходит заметно быстрее, чем в случае букв письменного текста. Для определения избыточности R(слова), можно установить связь между избыточностями устной и письменной речи. Из того, что устная речь может быть записана, а письменная - прочитана, следует, что "полная информация", содержащаяся в определенном тексте, не зависит от того, в какой форме - устной или письменной - этот текст представлен, т. е. что. Отсюда вытекает, что где есть среднее число букв, приходящихся на одну фонему ("средняя длина фонемы"). Эта величина является важной статистической характеристикой языка, связывающей устную и письменную речь. Из последней формулы следует также, что или где k - общее число фонем, а п - число букв; за здесь естественнее принимать. Однако использование этой формулы затрудняется отсутствием статистических данных, позволяющих определить величину. 2.2.3 Музыка. Исследования того же рода могут быть проведены и в отношении музыкальных сообщений. Естественно думать, что связи между последовательными звуками некоторой мелодии, выражающимися отдельными нотными знаками, достаточно сильны: так как одни сочетания звуков будут более благозвучны, чем другие, то первые будут встречаться в музыкальных произведениях чаще вторых. Если мы выпишем ряд нот наудачу, то информация, содержащаяся в каждой ноте этой записи, будет наибольшей; однако с музыкальной точки зрения такая хаотическая последовательность нот не будет представлять никакой ценности. Для того чтобы получить приятное на слух звучание, необходимо внести в наш ряд определенную избыточность; при этом можно опасаться, что в случае слишком большой избыточности, при которой последующие ноты уже почти однозначно определяются предшествующими, мы получим лишь крайне монотонную и малоинтересную музыку. Какова же та избыточность, при которой может получиться "хорошая" музыка? Избыточность простых мелодий никак не меньше, чем избыточность осмысленной речи. Необходимо было бы специально изучить вопрос об избыточности различных форм музыкальных произведений или произведений различных композиторов. К примеру, проанализировать с точки зрения теории информации популярный альбом детских песенок. Для простоты в этой работе предполагалось, что все звуки находятся в пределах одной октавы; так как в рассматриваемых мелодиях не встречались так называемые хроматизмы, то все эти мелодии могли быть приведены к семи основным звукам; До, ре, ми, фа, соль, ля и си, каждый длительностью в одну восьмую. Учет звуков, длительностью более одной восьмой, осуществлялся с помощью добавления к семи нотам восьмого "основного элемента" О, обозначающего продление предшествующего звука еще на промежуток времени в одну восьмую (или же паузу в одну восьмую). Таким образом, "максимальная возможная энтропия" Н0 одной ноты здесь равна Н0 = log 8 = 3 бита. Подсчитав частоты (вероятности) отдельных нот во всех 39 анализируемых песенках, находим, что С помощью найденных вероятностей сочетаний из двух нот, можно подсчитать также условную энтропию Н2, она оказывается близкой к 2,42 . По одним только значениям Н1 и Н2 еще очень мало что можно сказать о степени избыточности рассматриваемых, по-видимому, она заметно выше, чем. Этот вывод подтверждается исследованиями многих известных авторов. 2.2.4 Передача телевизионных изображений. Наш глаз способен различить лишь конечное число степеней яркости изображения и лишь не слишком близкие его участки, поэтому любое изображение можно передавать "по точкам", каждая из которых является сигналом, принимающим лишь конечное число значений. Необходимо учитывать значительное число (несколько десятков) градаций степени почернения ("яркости") каждого элемента, кроме того, на телеэкране ежесекундно сменяется 25 кадров, создавая впечатление "движения". Однако, по линии связи фактически передается не исход опыта, состоящего в определении значения непрерывно меняющейся от точки к точке, во времени и окраски или яркости изображения, а исход совсем другого "квантованного" опыта, состоящего в определении цвета (белого или черного) или градаций яркости в конечном числе "точек". Этот новый опыт может иметь уже лишь конечное число исходов, и мы можем измерить его энтропию Н. Общее число элементов ("точек") для черно-белого телевидения, на которые следует разлагать изображение, определяется в первую очередь так называемой "разрешающей способностью" глаза, т. е. его способностью различать близкие участки изображения. В современном телевидении это число обычно имеет порядок нескольких сотен тысяч (в советских телепередачах изображение разлагалось на 400 000 - 500 000 элементов, в американских - примерно на 200 000 - 300 000, в передачах некоторых французских и бельгийских телецентров - почти на 1 000 000). Нетрудно понять, что по этой причине энтропия телевизионного изображения имеет огромную величину. Если даже считать, что человеческий глаз различает лишь 16 разных градаций яркости (значение явно заниженное) и что изображение разлагается всего на 200000 элементов, то мы найдем, что "энтропия нулевого порядка" здесь равна Н0 = log 16200000 = 800 000 бит. Значение истинной энтропии Н, разумеется, будет меньше, так как телевизионное изображение имеет значительную избыточность. При вычислении величины Н0 мы предполагали, что значения яркости в любых двух "точках" изображения являются независимыми между собой, в то время как на самом деле яркость обычно очень мало меняется при переходе к соседним элементам того же (или даже другого, но близкого по времени) изображения. Наглядный смысл этой избыточности R заключается в том, что среди наших 16200000 возможных комбинаций значений яркости во всех точках экрана осмысленные комбинации, которые можно назвать "изображениями", будут составлять лишь ничтожно малую часть, а остальное будет представлять собой совершенно беспорядочную совокупность точек разной яркости, весьма далекую от какого бы то ни было "сюжета". Между тем реальная "степень неопределенности" Н телевизионного изображения должна учитывать только те комбинации значений яркости, которые имеют хоть какие-то шансы быть переданными. Для определения точного значения энтропии Н (или избыточности R) телевизионного изображения нужно детально изучить статистические зависимости между яркостями различных точек экрана. Так, найдены значения энтропий Н0, Н1, Н2 и Н3 для двух конкретных телевизионных изображений, первое из которых (изображение А - парк с деревьями и строениями) было более сложным, а второе (изображение В - довольно темная галерея с прохожими) было более однотонным по цвету и содержало меньше деталей, при этом различали 64 разных градаций яркости элемента телевизионного изображения, поэтому энтропия Н0 (отнесенная к одному элементу, а не ко всему изображению в целом) здесь оказалась равной Н0 = log 64 = 6 бит. Далее с помощью специального радиотехнического устройства были подсчитаны для обоих рассматриваемых изображений относительные частоты (вероятности) всех различимых градаций яркости и определил "энтропию первого порядка" То же самое радиотехническое устройство было применено затем для вычисления относительных частот pij пар соседних (по горизонтали) элементов, в которых первый элемент имеет i-e значение яркости, а второй j-e, а также относительных частот pijk троек соседних (также лишь по горизонтали) элементов, в которых первый элемент имел i-e значение яркости, второй j-e, а третий k-е (числа i, j, и k пробегали все значения от 1 до 64). Эти частоты позволили определить "энтропии сложных опытов" и а затем и "условные энтропии" и последняя ив которых, впрочем, была подсчитана лишь для изображения Б. Полученные результаты сведены в следующую таблицу: Н0Н1Н2Н3Изображение А65,7 3,4 -Изображение Б64,31,91,5 Избыточность R, оцененная по величине Н2 для изображения А равна 44%, а для изображения Б - 68%; действительное значение избыточности может быть только больше этого. Что же касается условной энтропии Н3 при известных яркостях двух предыдущих элементов той же строки, то она сравнительно мало отличается от Н2 (изображение Б, 75%); отсюда можно заключить, что знание яркости самого близкого элемента определяет весьма большую часть общей избыточности. Близкий характер имеет также другой опыт, опирающийся на разбиение возможных значений яркости элемента телевизионного изображения на 8, а не на 64 градаций, для которого вычислены энтропии Н0 и Н1 и ряда условных энтропии Н2, Н3 и Н4 одного элемента изображения для следующих четырех спортивных телевизионных сюжетов: А - быстро бегущие баскетболисты, Б - лицо одного зрителя на трибуне стадиона крупным планом, В - панорамирование вида зрителей на трибуне и Г - быстро бегущие футболисты. Будем обозначать цифрами 1 и 2 соседние с данным по горизонтали и по вертикали элементы изображения, цифрой 3 - соседний по диагонали элемент, цифрой 4 - тот же, что и рассматриваемый, элемент на предшествующем кадре телевизионной передачи, цифрой 5 - элемент на той же горизонтали, соседний с элементом 1, и, наконец, цифрой 6 - тот же элемент на кадре, предшествующем тому, который содержит элемент 4 (рис 1), а) б) рис 1. и будем указывать в обозначениях условных энтропий сверху в скобках номера элементов изображения, степень яркости которых считается известной. В таком случае значения энтропии (в битах) могут быть сведены в следующую таблицу: А31,960,690,98-1,77Б31,950,360,36--В32,781,341,952,78-Г32,45--2,002,08 А0,68-0,56--Б0,35-0,270,26-В--1,221,181,19Г-1,83--- Результаты последнего опыта приводят к выводу, что для бедного деталями изображения ("лицо") избыточность не меньше, чем 90%, а для изображения, богатого деталями ("зрители"), она не меньше, чем 60%. Причины этого расхождения пока неясны. Для цветных телевизионных изображений информация по порядку величины сравнима с удвоенной информацией, содержащейся в соответствующем черно-белом изображении. ЗАКЛЮЧЕНИЕ В данной работе были поставлены следующие цели и задачи. Цель: изучить принципы кодирования информации Шеннона - Фано и Хафмана и применение их при решении задач. Задача: изучить энтропии и избыточность конкретных типов сообщений для последующего применения к ним принципов Шеннона - Фано и Хафмана. После выполнения целей и задач дипломной работы были сделаны следующие выводы. До появления работ Шеннона и Фано, кодирование символов алфавита при передаче сообщения по каналам связи осуществлялось одинаковым количеством бит, получаемым по формуле Хартли. С появлением этих работ начали появляться способы, кодирующие символы разным числом бит в зависимости от вероятности появления их в тексте, то есть более вероятные символы кодируются короткими кодами, а редко встречающиеся символы - длинными (длиннее среднего). С тех пор, как Д.А.Хаффман опубликовал в 1952 году свою работу "Метод построения кодов с минимальной избыточностью", его алгоритм кодирования стал базой для огромного количества дальнейших исследований в этой области. Стоит отметить, что за 50 лет со дня опубликования, код Хаффмана ничуть не потерял своей актуальности и значимости. Так с уверенностью можно сказать, что мы сталкиваемся с ним, в той или иной форме (дело в том, что код Хаффмана редко используется отдельно, чаще работая в связке с другими алгоритмами), практически каждый раз, когда архивируем файлы, смотрим фотографии, фильмы, посылаем факс или слушаем музыку. Преимуществами данных методов являются их очевидная простота реализации и, как следствие этого, высокая скорость кодирования и декодирования. Основным недостатком является их неоптимальность в общем случае. 3