Беседы об информатике

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

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

Стремимся вдаль

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

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

Предел, к которому стремится относительная частота при неограниченном увеличении длины строки, есть не что иное, как вероятность встретить символ в тексте написанном на каком-либо языке.

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

Пока речь идет об одной-единственной задаче: как передать по каналу связи некоторое сообщение за минимальное время? С учетом огромного числа различных каналов связи в мире и их загруженности даже ничтожное сокращение затрат на передачу одного сообщения сулило грандиозный, как теперь говорят, экономический эффект. Так вот, учет частоты, с которой встречаются различные буквы английского алфавита, а теперь мы скажем — учет вероятностей, с которыми встречаются эти буквы, — позволяет уменьшить среднее количество посылок на символ приблизительно на 12 процентов. Это огромная величина. К. Шеннон стал бы мультимиллионером, если бы до него соответствующие методы уже не были предложены Морзе.

Все ли возможности исчерпаны учетом вероятностей появления отдельных букв?

Конечно, не все. Двухбуквенные сочетания также встречаются с различными вероятностями. Каждый знающий английский язык хорошо представляет себе, что сочетания «th» или «ou» встречаются чаще, чем другие. Дальнейший выигрыш был получен с учетом вероятности двухбуквенных, трехбуквенных и так далее сочетаний. Снова возникает интересная подробность. Вероятность, с которой встречается некая пара произвольно выбранных из алфавита букв (без учета особенностей языка), равна произведению вероятностей появления каждой буквы. Произведению, а не сумме.

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

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

Вероятности появления каждого символа не меняются во времени. Требование к стационарности совершенно необходимо. Сама по себе вероятность — это предел отношения количества случаев, когда встречается данный символ, к длине строки символов при условии, что длина строки стремится к бесконечности. А стремление длины строки к бесконечности означает, что время передачи t стремится к бесконечности.

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