Путешествие от частицы до Вселенной. Математика газовой динамики
Шрифт:
Первая мысль, которая приходит в голову, заключается в том, что компания должна зашифровать столько информации, сколько букв в сообщении. Например, «Сегодня я опоздаю на ужин» содержит 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 означают, что логарифм — это действие, обратное возведению в степень двух. Например, логарифм восьми по основанию два равен трем, поскольку три — это степень, в которую надо возвести два, чтобы получить восемь.
Формулу можно трактовать следующим образом: если некоторое значение бита очень вероятно, его информационное содержание низко; если значение маловероятно, бит несет гораздо больше информации. Нам нужно найти сумму всех возможных значений и умножить на их вероятность, поскольку наиболее вероятные значения встречаются чаще.
Формулу Шеннона можно использовать для определения информационной насыщенности сообщения, статистически исследовав появление в нем различных символов.
Возьмем предыдущий пример: «Сегодня я опоздаю на ужин». Порядок букв может показаться стихийным, и только зная, что фраза написана на русском языке, мы можем сделать какие-либо выводы о вероятности каждой буквы. Например, мы знаем, что в русском языке вероятность встретить букву ы после ж, ш или я после ч, щ крайне низка. Мы также знаем, что в начале слова никогда не встречаются буквы ъ и ь. Вся эта информация может использоваться для сжатия сообщения. Но даже если бы мы ничего не знали о языке как таковом, статистический анализ любого текста позволяет, основываясь на частоте каждой буквы, довольно сильно сжать его. Этот метод используется в программах для сжатия архивов: вначале они ищут в сообщении закономерности, а затем используют их для уплотнения информации.