Введение. Количество информации.

Maxime, 15.10.95

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

Однако, Шеннон не был первым, кто задумывался о сущности информации и определении ее количества. Первый шаг на этом пути сделал в 1928 г. Хартли. Основной полученный им результат можно сформулировать примерно так: если в заданном множестве, содержащем N элементов, выделен некоторый элемент x, о котором известно лишь, что он принадлежит этому множеству, то, чтобы найти x, необходимо получить количество информации, равное log2 N. Эту формулу обычно называют формулой Хартли.

Формула Хартли является частным случаем более общей формулы Шеннона, позволяющей найти количество информации в случайном сообщении фиксированного алфавита. Пусть X1, ..., Xn - символы этого алфавита, P1, ..., Pn - вероятности их появления в тексте сообщения, тогда формула Шеннона принимает вид:

H = P1*log2(1 / P1) + ... + Pn*log2(1 / Pn),
где H - количество бит информации в одном символе сообщения, или энтропия символа сообщения. Это число показывает минимальное среднее число бит, необходимых для представления одного символа алфавита данного сообщения. В некоторых случаях алфавит сообщения может быть неизвестен, тогда выдвигаются гипотезы об алфавите сообщения. Для разных алфавитов может быть достигнут разный коэффициент сжатия. Например, текстовый файл, если его рассматривать как последовательность битов, имеет энтропию порядка 0.7 - 0.9, если как последовательность байтов, - 0.5 - 0.7, хотя популярные программы сжатия уменьшают размеры текстовых файлов до 0.3 - 0.4 от исходного размера.

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


Изменена 19.03.2011 06:45 MSK Яндекс цитирования Рейтинг@Mail.ru   quill