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

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

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

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

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

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

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

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

Далее поступаем согласно К. Шеннону. Берем двоичный логарифм от величины 0,5 и называем то, что получилось, количеством информации, которую переносит одна-единственная буква «а» в рассматриваемом тексте.

Продолжаем анализ дальше. Пусть буква «б» встречается в том же самом тексте 250 тысяч раз. Делим 250 тысяч на миллион и получаем, что средняя частота (вероятность), с которой в данном тексте встречается буква «б», равна 0,25. Снова берем двоичный логарифм от величины 0,25 и получаем величину, равную количеству информации (по Шеннону), которое в данном тексте сопровождает появление каждый буквы «б». Такую же точно операцию мы проделываем далее для букв «в», «г», «д» и т. д.

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

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

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