Первая мысль, которая приходит в голову, заключается в том, что компания должна зашифровать столько информации, сколько букв в сообщении. Например, «Сегодня я опоздаю на ужин» содержит 21 единицу информации или 25, если считать пробелы. Но мы ошибаемся, потому что в одной букве содержится больше, чем одна единица информации. Итак, прежде всего мы должны подумать о том, что такое информация и как ее можно измерить.
Понятие информации связано с понятием сообщения: предположим, что каждый раз, когда мы посылаем сообщение, мы передаем информацию. Если мы определим самое простое сообщение, которое можем послать, оно и будет минимальной единицей информации.
В нашу информационную эпоху все знают о том, что минимальной единицей информации является бит. Бит — это единица или ноль, аналог ответа на вопрос: «да» или «нет». Не существует меньшей единицы, ведь наименьшее, что мы можем передать, это присутствие или отсутствие чего-либо. Чтобы узнать содержание сообщения, мы должны перевести его в биты.
Посмотрим, как можно зашифровать фразу «Сегодня я опоздаю на ужин» в битах. При этом мы можем шифровать только два типа данных: ноль или один. Однако в двух битах мы можем зашифровать четыре: 00, 01,10, 11. В трех битах у нас уже восемь возможностей: 000, 001, 010, 011, 100, 101, 110, 111. А для n бит у нас есть 2n возможностей, то есть два, умноженное на себя n раз. Каково минимальное число битов, нужное нам, чтобы зашифровать буквы алфавита? Поскольку в латинском алфавите 26 букв, нам потребуется по крайней мере 26 возможностей. Наиболее близкая степень двух — 32, или 23, так что минимальное необходимое число битов для того, чтобы зашифровать букву, равно пяти.
На практике для шифрования буквы используется более пяти битов, поскольку у нас есть заглавные буквы и различные символы, которые также нужно связать с последовательностью битов. Обычно используют восемь битов, из которых составлен так называемый код ASCII, который позволяет представить каждую букву в виде последовательности единиц и нулей. Например, буква а соответствует последовательности 01100001.
Коды ASCII для заглавных и строчных букв. Существует 8-битная кодировка кириллического алфавита, совместимая с ASCII, — КОИ-8.
Поскольку каждой букве соответствуют восемь битов, а наше сообщение содержит двадцать пять букв, мы можем сосчитать, сколько информации в нем содержится:
25·8 = 200 битов.
В целом мы можем представить любую цепочку символов в качестве цепочки битов, информация которой обычно равна ее длине. Но это не всегда так. Например, возьмем цепочку:
1111111111111111111111111111111111111111111111.
Это сообщение содержит 46 битов, но они несут меньше информации, чем могли бы, поскольку здесь повторяется одна и та же цифра. Действительно, если бы мы хотели продлить цепочку, то легко могли бы догадаться, что следующий символ — тоже единица. Итак, предсказуемость цепочки делает информацию, которую она содержит, меньшей, чем ее длина в битах. Именно здесь вступает понятие энтропии: предсказуемая цепочка битов характеризуется меньшим количеством энтропии и, следовательно, меньшим количеством непредсказуемой информации. Поэтому энтропия — хорошая мера информации, содержащейся в цепочке битов.
Энтропия
ШеннонаСвязь между информацией и случайностью очень тонка и предполагает, что создание цепочки в битах — процесс с непрогнозируемым результатом. Представим, что цепочка битов выбирается на основе броска монеты. В этом случае мы знаем, что следующий бит будет либо нулем (орел), либо единицей (решка), но не более того: монета абсолютно непредсказуема. В этом случае случайно возникшая цепочка битов содержит количество информации, равное ее длине.
Но предположим, что монета, которую мы используем, фальшивая, и на вероятность выпадения орла приходится 70 %. В этом случае каждый бит будет содержать немного меньше информации, поскольку мы знаем, что более вероятно выпадение орла.
Крайний случай — это цепочка, состоящая из единиц. Если мы знаем, что при броске всегда выпадает решка, то, подбрасывая монету, не получаем вообще никакой информации. Итак, когда цепочка битов полностью предсказуема, содержание информации в ней нулевое. Шеннон основывался на этой идее в сочетании с формулой энтропии Больцмана для создания собственного определения энтропии, применимого к информации.
Поскольку вероятность получения результата играет роль, подобную числу микросостояний в теории Больцмана, Шеннон определил энтропию как сумму логарифмов вероятности получения этого результата для каждого бита. В математической нотации его формула выглядит следующим образом:
Н = — P1log2P1 — P2log2P2 — P3log2P3 — … — Pnlog2Pn,
где H — энтропия, Р — вероятность получения некоторого значения для каждого символа.
Символы log2 означают, что логарифм — это действие, обратное возведению в степень двух. Например, логарифм восьми по основанию два равен трем, поскольку три — это степень, в которую надо возвести два, чтобы получить восемь.
Формулу можно трактовать следующим образом: если некоторое значение бита очень вероятно, его информационное содержание низко; если значение маловероятно, бит несет гораздо больше информации. Нам нужно найти сумму всех возможных значений и умножить на их вероятность, поскольку наиболее вероятные значения встречаются чаще.
Формулу Шеннона можно использовать для определения информационной насыщенности сообщения, статистически исследовав появление в нем различных символов.
Возьмем предыдущий пример: «Сегодня я опоздаю на ужин». Порядок букв может показаться стихийным, и только зная, что фраза написана на русском языке, мы можем сделать какие-либо выводы о вероятности каждой буквы. Например, мы знаем, что в русском языке вероятность встретить букву ы после ж, ш или я после ч, щ крайне низка. Мы также знаем, что в начале слова никогда не встречаются буквы ъ и ь. Вся эта информация может использоваться для сжатия сообщения. Но даже если бы мы ничего не знали о языке как таковом, статистический анализ любого текста позволяет, основываясь на частоте каждой буквы, довольно сильно сжать его. Этот метод используется в программах для сжатия архивов: вначале они ищут в сообщении закономерности, а затем используют их для уплотнения информации.
Энтропия Шеннона измеряется в битах. Если вычислить ее содержание в букве такого текста, как эта книга, окажется, что она равна примерно одному биту, что намного меньше восьми битов, необходимых для передачи этой буквы.
* * *
ШЕННОН И ФОН НЕЙМАН
Определение энтропии Шеннона, кажется, гораздо больше связано с информацией, чем с энтропией, так что выбор названия может показаться удивительным. Согласно некоторым его биографам, идея принадлежала великому математику Джону фон Нейману (1903–1957), который во время одного из своих визитов сказал Шеннону следующее: «Тебе следует назвать ее энтропией по двум причинам. Во-первых, твоя функция неопределенности уже используется в статистической механике под таким названием, так что у нее уже есть имя. А во-торых, и это более важно, никто на самом деле не понимает, что такое энтропия, поэтому в спорах у тебя всегда будет преимущество».
* * *
Энтропия чисел
Поскольку число также может быть выражено как цепочка символов, в нем тоже имеется некоторое количество информации и, следовательно, некоторая энтропия Шеннона. Самый простой способ вычислить энтропию числа — это рассмотреть его выражение в двоичной системе. При этом вместо привычных арабских цифр используются единицы и нули. Когда мы записываем число арабскими цифрами, то на самом деле используем степени числа 10:
2345 = 2·1000 + 3·100 + 4·10 + 5·1 = 2·103 + 3·102 + 4·101 + 5·100.
Но мы можем использовать и степени числа два. Возьмем, например, число 10:
10 = 1·8 + 0·4 + 1·2 + 0·1 = 1·23 + 0·22 + 1·21 + 0·20.
Его запись в двоичной системе выглядит так:
1010.
Значит, для передачи числа 10 требуется четыре бита информации. В десятичной форме мы могли бы выразить 10 как:
10,000000000…
И для его передачи нам потребовалось бы бесконечное число символов. Двоичное выражение десяти также можно было бы представить в виде:
1010,000000000000000…
И снова нам потребовалось бы бесконечное количество битов для передачи его в таком виде. Однако, поскольку ноль после запятой повторяется бесконечно, он не несет никакой информации, и его энтропия Шеннона равна нулю. Итак, энтропия Шеннона числа 10 — четыре бита.
