Решение задач по статистическому расчету количества информации

Статистический подход к количественному измерению информации

Американский инженер Р. Хартли (1928 г.) рассматривал процесс получения информации из одиночного символа а, который может принимать m равновероятных значений (состояний) {а₁, а₂, …, а_m}, как выбор одного его возможного значения (состояния) а_i из множества {а₁, а₂, …, а_m}.

Допустим, необходимо закодировать состояния {а₁, а₂, …, а_m} при помощи двоичного кода постоянной длины d. Поскольку у такого кода значения разрядов независимо могут принимать 2 значения (0 или 1), то общее число всех возможных различных двоичных наборов длины d по формуле для размещений равно 2^d. Из соотношения 2^d³m следует, что минимальное значение d равно ближайшему целому сверху к log₂m.

В качестве меры информации I принята величина, пропорциональная d:

I=k×log₂m.

где k – постоянный коэффициент.

В теории информации принято определять I как безразмерную величину. Следовательно, коэффициент k также должен быть отвлеченным числом. Для его определения используется понятие двоичной единицы информации – это количество информации, получаемое в результате одиночного (одноразового) выбора из двух равновероятностных возможностей (m=2). Такую единицу измерения называют “бит” (bit от слов “binary digit” – двоичная единица).

Из условия I=k log₂2=k=1 следует: k=1. Формула для количества информации:

I=log₂m.

В общем случае у одиночного символа а, который может принимать m значений {а₁, а₂,…, а_m}, вероятности данных значений не одинаковы. Обозначим их как р₁, р₂,…, р_m. В 1948 г. К. Шеннон предложил обобщенную формулу определения количества информации для одного символа, учитывающую неодинаковую вероятность его значений:

I=–(p₁log₂p₁+p₁log₂p₁+ ...+p_mlog₂p_m),

где p_i – вероятность того, что именно i – ое значение принимает сим­вол а.

Если все сообщения равновероятны (т. е. р_i=1/m), то I=log₂m и формула Шеннона совпадает с формулой Хартли.

Набор значений {а₁, а₂,…, а_m}, которые может принимать символ а, в некотором языке (естественном или формальном) называют его алфавитом. Общее число m возможных значений символа в алфавите называют мощностью алфавита.

С точки зрения статистической оценки емкости текстовых массивов, записанных на естественных языках, к их буквенным алфавитам необходимо добавлять все дополнительные символы, используемые в тексте - разделители, знаки препинания и т.д.

При равных вероятностях р₁, р₂,…, р_m символов алфавита полный битовый объем информации в тексте – линейном массиве, содержащем N символов (информационный вес), равен: I = N × i = N ×log₂m.

Решение задач данного типа основано на использовании формул Хартли (равновероятные сообщения) и Шеннона (для различаю­щихся вероятностей).

Пример 1. Для задания текста на английском языке необходимо применить 27 символов (26 букв и пропуск между словами); в русском языке – 32 символа. Перед получением информации о букве имеет место неопределенность из 27 или 32 исходов, после получе­ния информации неопределенность равна нулю. Следовательно, при равновероятном появлении всех символов суммарное битовое количество информации (вес), содержащийся в предложении из n символов, равен:

в английском языке I_англ=n log₂27; в русском языке I_русск=n log₂32.

Информационный вес для каждого символа равен:

i_англ=1×log₂27»4,76 бит; i_русск=1×log₂32=5 бит.

Замечание. На самом деле вероятности р₁, р₂,…, р_m появления символов алфавита в реальных текстах, как правило, не равны друг другу. Гипотеза об их равенстве обычно применяется для приближенных оценок битового количества информации в текстах.

Пример 2. Найти, сколько бит информации несет каждое двузначное десятичное число вида ХХ₁₀ со всеми значащими цифрами (отвлекаясь при этом от его конкретного числового значения).

Решение. Так как таких чисел может быть всего 90 (от 10 до 99), то количество информации будет равно I=log₂90 или приблизи­тельно I=6.5. Так как в таких числах значащая первая цифра имеет 9 значений (1–9), а вторая – 10 значений (0–9), то I=log₂90=log₂9+log₂10. Приблизительное значение log₂10 равно 3.32.

Ответ. log₂90.

Отсюда можно сделать вывод о том, что сообщение в одну десятичную единицу несет в себе в 3.32 больше информации, чем в одну двоичную единицу (чем log₂2=1). Вторая цифра в любом двузначном числе несёт в себе больше информации, чем первая. Например, в числе 22 вторая цифра 2 несёт в себе больше информации, чем первая, если заранее эти цифры не были известны. Если же обе цифры известны (т.е. конкретное число 22 было задано), то количество информации равно 0.

Пример 3. Чему равно количество информации в системе при­нимающей 16 равновероятных состояний (1, 2, …, 16), если:

1) состояние системы не известно и

2) состояние системы известно.

Решение. m=16. Так как состояния равновероятны (р_i=1/m), то при неопределенном состоянии системы количество информации в ней по формуле Хартли равно: I=log₂m=log₂16=4.

Пусть состояние системы известно и равно k (1£k£16). В этом случае выбора, собственно говоря, нет. При этом для всех состояний i вероятности р_i=0, кроме некоторого одного состояния k, у которого р_k=1. По формуле Шеннона получим: I=log₂1=0, т.е. система не содержит информации.

Ответ. 1) 4; 2) 0.

Пример 4. ДНК человека можно представить себе как некоторое слово в четырехбуквенном алфавите, где каждой буквой помечается звено цепи ДНК (нуклеотид). Сколько информации (в битах) содержит цепь ДНК, если в нее входит примерно 1,5×10²³ нуклеоти­дов?

Решение. На один нуклеотид приходится log₂(4)=2 (бит) информации. Следовательно, ДНК в организме человека позволяет хранить 3×10²³ бит информации.

Непосредственное применение формулы Хартли дает такой же результат:

1) общее число вариантов рассмотренной ДНК равно

2) количество информации в одной ДНК

Ответ. 3·10²³.

Пример 5. Световое табло состоит из лампочек, каждая из которых может находиться в двух состояниях (“включено” или “выклю­чено”). Какое наименьшее количество лампочек должно находиться на табло, чтобы с его помощью можно было бы передать 200 разных сигналов?

Решение. Обозначим искомое минимальное число лампочек через n. Так как каждая лампочка может находиться независимо от других в m=2 состояниях, то по формуле для числа размещений получим, что общее число различных комбинаций включения n лампочек равно: U_n²=2ⁿ.

Так как таких комбинаций должно быть не меньше 200, то отсю­да получим условие на число n: 2ⁿ³200. Поскольку искомое число n – целое, то n=]log₂200[=8.

Ответ. 8.

Пример 6. Какое наименьшее число символов должно быть в алфавите, для того, чтобы при помощи всевозможных трехбуквенных слов, состоящих из символов данного алфавита, можно было передать не менее 9 различных сообщений?

Решение. Обозначим искомое минимальное число симво­лов в алфавите через n. Максимальное число сообщений, передаваемых трехбуквенными словами, равно U₃ⁿ=n³. Так как сообщений должно быть не менее 9, то отсюда получим условие на число: n³³9. Так как искомое число n – целое, то .

Ответ. 3.