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

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

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

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

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

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

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

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

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

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

А теперь самое интересное. На памятнике немецкому ученому Л. Больцману (1844–1906) высечена формула, выведенная им в 1877 году и связывающая вероятность состояния физической системы и величину энтропии этой системы. Мы не станем сейчас разбираться в смысле терминов: вероятность, состояние и энтропия. Скажем только, что энтропия — это термодинамическая величина, описывающая состояние нагретого тела, и что относительно этой самой энтропии выведен один из законов — так называемое второе начало термодинамики, — претендующий на роль одного из фундаментальных законов природы.

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