Измерение информации с помощью формулы Хартли

Информация стала неотъемлемой частью нашей жизни. Но как ее измерить? В 1928 году Ральф Хартли предложил формулу для подсчета количества информации. Давайте разберемся, как она работает и где применяется.

Что такое информация и как ее определить

Существует интуитивное определение информации как уменьшения неопределенности. Чем больше мы узнаем, тем меньше остается неизвестного. Однако такое определение не дает количественной оценки.

Поэтому в информатике чаще используется алфавитный подход . Информация - это последовательность символов некоторого алфавита. Чем больше символов в алфавите и чем длиннее последовательность, тем больше информации.

В качестве единицы измерения принят бит - символ двоичного алфавита 0 или 1. 1 бит - это количество информации, необходимое для выбора из 2 равновероятных событий.

Существуют и более крупные единицы:

• 1 байт = 8 бит
• 1 Кб = 1024 байта
• 1 Мб = 1024 Кб

По некоторым гипотезам, информация физически связана с энергией. Это выражается формулой Эйнштейна E = mc^2, где m - "информационная масса".

Формула Хартли для равновероятных событий

Рассмотрим пример. Допустим, нужно угадать число от 1 до 100. Есть метод "деления пополам": спрашиваем, больше ли число 50. Если нет, то спрашиваем про 25 и т.д. Сколько вопросов потребуется?

Каждый вопрос дает 1 бит информации, так как есть 2 равновероятных варианта. Оказывается, для числа от 1 до 100 потребуется всего 7 вопросов (2^7 = 128 вариантов).

Это количество информации подсчитывает формула Хартли:

I = log₂N

где N - число вариантов (в нашем случае 100), а I - количество информации в битах для выбора одного варианта (7 бит).

Ту же формулу можно применить для подсчета информации при бросании монет, кубиков и других равновероятных событий. Например, для классического кубика с 6 гранями получаем:

I = log₂6 ≈ 2.6 бита

То есть в среднем каждый бросок кубика дает около 2.6 бита информации.

Формула Шеннона для неравновероятных событий

Формула Хартли справедлива только для равновероятных событий. А как быть, если вероятности разные?

Допустим, есть сообщение из 2 символов A и B, причем A встречается с вероятностью 0.7, а B — с вероятностью 0.3. Тогда в среднем 1 символ несет -0.7*log₂0.7 - 0.3*log₂0.3 ≈ 0.88 бита информации.

Для общего случая формула имеет вид:

I = -∑_iP(x_i) log₂ P(x_i)

Это формула Шеннона. При равных вероятностях P(x_i) = 1/N она переходит в формулу Хартли.

Оптимальное кодирование по Хаффману

Чтобы подсчитанная по формулам информация соответствовала реальному объему данных, необходимо оптимальное кодирование. Рассмотрим алгоритм Хаффмана на примере.

Пусть есть фраза:
шла Маша по шоссе

При кодировании в UTF-8 каждый символ занимает в среднем по 9 бит. С помощью алгоритма Хаффмана удается сжать до 5.2 бит/символ.

Таким образом, алгоритм Хаффмана позволяет приблизиться к теоретическому пределу по формуле Хартли.

Сравнение кодирования текста в UTF-8 и по Хаффману

Для примера фразы в 17 символов UTF-8 требует 17*9 = 153 бита. Алгоритм Хаффмана - только 17*5.2 = 88 бит, то есть почти вдвое меньше!

Это иллюстрирует, насколько важно оптимальное кодирование для реализации теоретических оценок по формуле Хартли.

Применение алгоритма Хаффмана на практике

Наиболее известное применение алгоритма Хаффмана - сжатие данных без потерь. Он используется в форматах GIF, PNG, MPEG и других.

Также его можно применить для экономии памяти при хранении данных, оптимизации баз данных, сетевого трафика и многого другого.

Ограничения алгоритма Хаффмана

Основное ограничение в том, что алгоритм оптимален только для фиксированной вероятностной модели источника сообщений. Если частоты символов меняются - нужно заново строить дерево кодирования.

Кроме того, для алгоритма требуется дополнительная память для хранения таблицы кодов. А декодирование требует обращения к этой таблице для каждого символа.

Адаптивные алгоритмы кодирования

Чтобы преодолеть недостаток Хаффман-кодирования с фиксированной моделью, разработаны адаптивные алгоритмы.

Они анализируют уже закодированную часть сообщения и динамически обновляют вероятности символов и дерево кодирования.

Алгоритм Фано

Одним из первых адаптивных алгоритмов стал алгоритм Фано. Он также использует дерево кодирования, но строит его иначе.

Главное отличие в том, что на каждом шаге разбивается не пара символов с наименьшей частотой, а все множество символов пополам.

Арифметическое кодирование

Еще один популярный подход - арифметическое кодирование. Вместо набора кодов оно представляет все сообщение одним действительным числом от 0 до 1.

По мере чтения сообщения, интервал для числа сужается. Это позволяет адаптировать код под изменение вероятностей.

LZW и другие алгоритмы

Помимо этого существует множество адаптивных алгоритмов сжатия данных без потерь: LZW, LZ77, LZ78 и др.

Они комбинируют идеи кодирования Хаффмана, выделения повторяющихся последовательностей, арифметического кодирования.

Применение теории информации в криптографии

Помимо сжатия данных, идеи теории информации активно применяются в криптографии - науке о безопасной передаче и хранении данных:

• Шифрование с открытым ключом. Например, в асимметричных алгоритмах шифрования, таких как RSA, используются принципы теории чисел, тесно связанные с теорией информации.
• Генерация псевдослучайных чисел. Другой пример - генераторы псевдослучайных чисел на основе хаотических отображений. Их непредсказуемость напрямую связана с количеством генерируемой энтропии.
• Теорема о стойкости одноразового блокнота. Важный результат теории информации в криптографии - теорема о стойкости одноразового блокнота. Она устанавливает нижнюю границу криптостойкости.
• Квантовое шифрование. Перспективное направление - построение криптосистем на основе квантовой физики, неразрывно связанной с понятием информации.

Такие системы обещают абсолютную стойкость, основанную на законах квантовой механики.