Понятие информации

Информация – это одно из фундаментальных понятий современной науки, наряду с понятиями материи и энергии. По-видимому, не только понятие. В начале прошлого века Эйнштейн показал, что материя и энергия – по сути одно и то же (знаменитая формула \(E=m c^2\)). Современные исследования в физике указывают на то, что подобная связь может быть и между информацией и энергией.

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

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

Информация по Шеннону

Информация – это снятая неопределенность.

Это удобное интуитивное определение. Неопределенность в данном случае – характеристика нашего незнания о предмете. Например, в момент броска игрального кубика, мы не знаем, какая из 6 граней выпадет. Когда же кубик останавливается на какой-то грани – мы получаем информацию.

Это определение, однако, не слишком удобно без некоторой количественной меры неопределенности.

Величина неопределенности

количество возможных равновероятных исходов события

Так, например, игральный кубик имеет неопределенность 6.

Такой подход к определению информации называется содержательным. Он интуитивно понятен, однако, не отвечает на вопрос “сколько информации получено”.

Количество информации по Колмогорову

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

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

В качестве основной единицы количества информации принято брать бит – от binary digit.

При алфавитном подходе один бит – это количество информации, которое можно закодировать одним двоичным знаком (0 или 1). С точки зрения содержательного подхода, один бит – это количество информации, уменьшающее неопределенность в два раза.

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

В вопросе хранения информации, основным показателем является не количество информации, а информационный объем

Информационный объем сообщения

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

В отличие от количества информации, информационный объем может быть не минимальным. В частности, кодирование текстов в различных кодировках далеко не оптимально.

Формула Хартли

Сколько же информации получается в результате броска кубика?

Рассмотрим сначала более простую задачу: сколько информации получается в результате броска монеты? Считаем, что возможны два варианта: “орел” и “решка”.

Исходя из содержательного подхода, неопределенность броска монеты составляет 2. После броска, мы имеем один вариант. Следовательно, неопределенность уменьшилась вдвое. В результате броска монеты мы получаем один бит информации.

Рассмотрим теперь бросок двух монет (или два броска одной монеты). Каждый из бросков имеет два варианта исхода. Всего мы имеем четыре варианта исхода: орел-орел, орел-решка, решка-орел, решка-решка. После бросков, мы получаем один конкретный вариант, то есть, неопределенность уменьшается в 4 раза – или дважды уменьшается в 2 раза. Мы, таким образом, получаем 2 бита информации.

Для броска трех монет, имеем 8 вариантов исхода, и в результате получаем 3 бита информации.

Интуитивно ясно, что если имеется \(N\) равновероятных исходов, то количество информации, которое мы получаем при реализации одного из них, составляет \(\log_2 N\). Докажем это более строго.

\(\Delta\)

для набора из \(N\) различных символов можно составить \(N^m\) различных комбинаций (“слов”) длины \(m\) (это утверждение легко доказывается по индукции, и известно из комбинаторики).

Существует такое \(k \in \mathbb{N}\) – количество необходимых для кодирования этого слова двоичных знаков – что \[2^k < N^m \leq 2^{k+1}\].

Логарифмируя неравенства, получаем: \[ k < m\log_2 N \leq k+1\] или \[ \frac{k}{m} < log_2 N \leq \frac{k}{m}+\frac{1}{m}\]. Таким образом, среднее количество информации, приходящееся на один символ \(\frac{k}{m}\) отличается от \(\log_2 N\) не более, чем на \(\frac{1}{m}\).

Тогда при оптимальном кодировании информации (которое при неограниченном \(m\) достижимо с произвольной точностью), на один символ приходится \(\log_2 N\) бит информации (или, что то же, один символ кодируется в среднем \(\log_2 N\) двоичными символами) \(\blacksquare\)

Выражение \[H = \log_2 N,\] где \(H\) – количество информации в символе \(N\)-значного алфавита, называется Формулой Хартли.

Возвращаясь к кубику, количество информации, полученное в результате броска кубика составляет \(\log_2 6 \approx 2.585\).

Применения формулы Хартли

Формула Хартли находит много различных применений. Одно из наиболее интересных заключается в оценке классов сложности вычислительных задач. Рассмотрим на примере алгоритмов сортировки.

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

Массив длинны \(N\) имеет \(N!\) различных перестановок (это утверждение легко доказывается по индукции, и известно из комбинаторики).

Операция сравнения двух элементов по сути несет один бит информации (либо первый больше второго, либо меньше или равен), а по формуле Хартли количество информации, соответствующее выбору одного из \(N!\) вариантов \(H=\log_2(N!)\), то есть, потребуется по крайней мере \(\log_2(N!)\) операций сравнения.

Для больших \(N\) можно использовать формулу Стирлинга для оценки факториала: \[N! = \sqrt{2\pi N} N^N e^{-N}.\]

Тогда \[\begin{align} H &\approx \log_2(\sqrt{2\pi N} N^N e^{-N}) \\ & = \log_2(\sqrt{2\pi N}) + \log_2(N^N) + \log_2(e^{-N}) \\ & = \frac{1}{2} \log_2(2 \pi N) + N \log_2(N) -N \log_2(e) \\ & = \frac{1}{2} \log_2(2 \pi) + (N+\frac{1}{2}) \log_2(N) - N \log_2(e) \end{align}\]

Поскольку \(N \log_2 N\) растет быстрее, чем \(N\), то по порядку роста можно ввести оценку \[H = \mathcal{O}(N \log N),\] что будет соответствовать классу сложности DTIME(\(N\log N\)).

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

Закон аддитивности информации

Еще одно занимательное следствие формулы Хартли – это аддитивность информации.

Рассмотрим некую пару \((x_1, x_2) \in X\), где \(x_1\in X_1\) и \(x_2 \in X_2\). Очевидно, что \(X = X_1 \times X_2\) – декатрово произведение, и, если \(X_1\) состоит из \(N_1\) элементов, а \(X_2\) – из \(N_2\) элементов, то \(X\) состоит из \(N_1 N_2\) элементов.

По формуле Хартли, количество информации, соответствующее выбору \((x_1, x_2)\) из \(X\) равно \[H(x_1, x_2) = \log_2(N_1 N_2)\]

По правилом арифметики с логарифмами,

\[\begin{align} H(x_1, x_2) & = \log_2(N_1 N_2) \\ & = \log_2 N_1 + \log_2 N_2 \end{align}\]

Но \(\log_2 N_1\) в свою очередь равно количеству информации, соответствующему выбору \(x_1\) из \(X_1\), а \(\log_2 N_2\) – \(x_2\) из \(X_2\). И действительно, чтобы выбрать пару \((x_1, x_2)\), мы можем выбрать сначала \(x_1\), затем \(x_2\).

Таким образом, по формуле Хартли, \[H(x_1, x_2) = H(x_1) + H(x_2),\] то есть, информация аддитивна – если мы получаем \(H_1\) информации об одном предмете и \(H_2\) – о другом, то всего мы получаем \(H_1 + H_2\) информации о двух предметах.

Закон аддитивности информации

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

Этот закон легко обобщается для набора \(N\) элементов.

Формула Шеннона

До сих пор мы рассматривали случай, когда все варианты равновероятны. Предположим, что это не так.

Пусть у нас имеется сообщение (“слово”), состоящее из символов \({a, b}\), причем известно, что в сообщении есть \(n\) символов \(a\) и \(m\) символов \(b\). Сколько информации приходится в среднем на символ этого сообщения?

Рассмотрим новый алфавит \({a_1, \ldots, a_n, b_1, \ldots, b_m}\) из \(n+m\) символов и запишем с его помощью наше сообщение таким образом, чтобы символы не повторялись. В таком случае, вероятность обнаружить какой-либо символ одинакова, и мы можем применить формулу Хартли.

Среднее количество информации на символ в таком случае, \[H_{n+m} = \log_2(n+m)\]. Однако, в исходном алфавите, мы не различаем символы \(a_i\). Если бы мы делали различие между ними, то выбор одного из \(n\) вариантов соответствовал бы количеству информации \(H_{a_i} = \log_2 n\). Аналогично, \(H_{b_i} = \log_2 m\). Однако, поскольку мы не делаем различий, мы по сути теряем эту информацию для каждого символа.

Всего на сообщение теряется \(n \log_2 n + m \log_2 m\) бит информации, а всего информации в сообщении \((n+m) \log_2(n+m)\).

Таким образом, всего в сообщении в исходном алфавите содержится \[\begin{align} H_\Sigma & = (n+m) \log_2(n+m) - n \log_2 n - m \log_2 m \\ & = n \log_2(n+m) + m \log_2(n+m) - n \log_2 n - m \log_2 m \\ & = n \log_2\frac{n+m}{n} + m \log_2\frac{n+m}{m} \end{align}\] бит информации.

Тогда среднее количество информации на один символ сообщения

\[ H = \frac{H_\Sigma}{n+m} \] \[ H = \frac{n}{n+m} \log_2\frac{n+m}{n} + \frac{m}{n+m}\log_2\frac{n+m}{m} \]

Но \(P_a = \frac{n}{n+m}\) – это вероятность обнаружить в сообщении символ \(a\), а \(P_b = \frac{m}{n+m}\) – символ \(b\). Тогда

\[ H = P_a \log_2\frac{1}{P_a} + P_b \log_2\frac{1}{P_b} \]

Это частный случай формулы Шеннона – для двух-символьного алфавита.

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

Поскольку вероятность аддитивна, \(P_a + P_b = 1\), \(P_b = 1 - P_a\), можем записать \(H\) как функцию \(P_a\):

\[ H(P_a) = P_a \log_2\frac{1}{P_a} + (1-P_a) \log_2\frac{1}{1-P_a} \]

График этой функции показан на рисунке:

Можно так же рассчитать производную:

\[\frac{d H(P_a)}{dP_a} = \log_2\frac{1-P_a}{P_a}\]

и найти нули:

\[\log_2\frac{1-P_a}{P_a} = 0\] \[\frac{1-P_a}{P_a} = 1\] \[1-P_a = P_a\] \[P_a = \frac{1}{2}\]

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

В других случаях, выбор из двух вариантов соответствует менее чем одному биту информации.

Формула Шеннона для двух-символьного алфавита легко обобщается на случай \(N\)-символьного алфавита по индукции: \[ H = \sum_{i=1}^N P_i \log_2{\frac{1}{P_i}}\]

\(\Delta\)

Действительно, база индукции для случая \(N=2\) уже доказана. Предположив, что формула верна для алфавита \(N-1\) элементов, вычислим \(H\) для \(N\) элементов.

Для этого, отождествим последние два символа алфавита. Для отождествленного алфавита количество информации на символ \[ H_{N-1} = \sum_{i=1}^{N-2} P_i \log_2{\frac{1}{P_i}} + (P_{N-1}+P_N) \log_2{\frac{1}{P_{N-1}+P_N}} \]

Среди двух отождествленных символов, каждый из них появляется с относительной вероятностью, соответственно, \[q_{N-1} = \frac{P_{N-1}}{P_{N-1}+P_N},\] \[q_{N} = \frac{P_{N}}{P_{N-1}+P_N}.\]

В силу отождествления, на каждый отождествленный символ теряется \[ q_{N-1} \log_2\frac{1}{q_{N-1}} + q_{N} \log_2\frac{1}{q_{N}}\] бит информации, а их доля среди всех символов составляет \(P_{N-1}+P_N\).

Тогда в результате отождествления, мы потеряли в среднем \[ P_{N-1} \log_2\frac{1}{q_{N-1}} + P_{N} \log_2\frac{1}{q_{N}}\] бит на символ. Прибавив это выражение к \(H_{N-1}\), получим: \[ \sum_{i=1}^{N-2} P_i \log_2{\frac{1}{P_i}} + (P_{N-1}+P_N) \log_2{\frac{1}{P_{N-1}+P_N}} + P_{N-1} \log_2\frac{1}{q_{N-1}} + P_{N} \log_2\frac{1}{q_{N}}\] \[ \sum_{i=1}^{N-2} P_i \log_2{\frac{1}{P_i}} + P_{N-1} \log_2\frac{1}{q_{N-1}(P_{N-1}+P_N)} + P_{N} \log_2\frac{1}{q_{N}(P_{N-1}+P_N)}\] \[ \sum_{i=1}^{N-2} P_i \log_2{\frac{1}{P_i}} + P_{N-1} \log_2\frac{1}{P_{N-1}} + P_{N} \log_2\frac{1}{P_{N}}\] \[ \sum_{i=1}^{N} P_i \log_2{\frac{1}{P_i}}.\] \(\blacksquare\)

Связь формул Хартли и Шеннона

Формула Хартли представляет собой частный случай формулы Шеннона.

Действительно, в предположении, что имеется набор из \(N\) элементов, и вероятность выбора каждого элемента одинакова, то \(P_i = P_j = P\) и \(\sum_{i=1}^N P_i = 1\), следовательно, \(P = \frac{1}{N}\). Тогда по формуле Шеннона, \[\begin{align} H & = \sum_{i=1}^{N} P \log_2{\frac{1}{P}} \\ & = \sum_{i=1}^{N} \frac{1}{N} \log_2{N} \\ & = \log_2{N}. \end{align}\]

Мы получили формулу Хартли.

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

Для достижения соответствия информационного объема и количества информации, необходимо оптимальное кодирование информации.

Легко можно показать случаи не оптимального кодирования информации. Допустим, кодируется результат падения монеты: орел или решка. Мы уже знаем, что количество информации в данном случае равно одному биту. При этом, если закодировать эти значения, например, русскими словами в коде UTF-8, то в среднем на одно значение уйдет 9 бит.

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

Алгоритм Хаффмана

Алгоритм Хаффмана является алгоритмом префиксного кодирования: символы произвольного алфавита кодируются двоичными последовательностями различной длины таким образом, что ни один более короткий код не является префиксом более длинного. При этом, для достижения оптимального кодирования, наиболее часто встречающиеся символы кодируются наиболее короткой последовательностью, а наиболее редко встречающиеся – наиболее длинной.

Для построения кода, всем символам алфавита присваиваются значения приоритетов, соответствующие частоте появления символа.

Затем два символа с наименьшим значением приоритета “склеиваются”, образуя при этом бинарное дерево (выбор символов с одинаковым приоритетом произволен). Результат получает приоритет, равный сумме приоритетов входящих в него символов. Процесс продолжается, пока в итоге не останется одно бинарное дерево.

После этого, “левым” ветвям дерева (с более низким приоритетом) присваивается код “0”, а “правым” (с более высоким) – “1”. Кодом символа является последовательность кодов ветвей, приводящих к нему.

Например, нам нужно оптимально закодировать сообщение “шла Маша по шоссе”. Всего сообщение состоит из 17 символов. Символы алфавита и их приоритеты:

“Склеим” символы “п”, “е”:

Теперь “л” и “м”

Теперь “пе” и “лМ”:

Действуя далее аналогично:

Приоритет последнего оставшегося узла равен длине сообщения.

Изображение соответствующего дерева:

Таким образом, коды символов:

Средний информационный вес символа по формуле Шеннона: \[ H = 4\frac{1}{17}\log_2 17 + 3 \frac{2}{17}\log_2 \frac{17}{2} + \frac{3}{17}\log_2 \frac{17}{3} + \frac{4}{17}\log_2 \frac{17}{4}\] \[ H \approx 2.98 \]

Средний информационный вес по расчету:

\[ H = \frac{2\cdot 4 + 3 \cdot 3 + 3\cdot 2\cdot 3 + 4\cdot 4}{17} = 3 \]

Разница оценки по формуле Шеннона и фактической величины не превосходит \[\frac{1}{17} \approx 0.06\]

С ростом общего числа символов в сообщении это различие будет становиться все меньше.

Минимальная сложность сортировки сравнением

Анализ сложности сортировки сравнением можно провести с точки зрения теории информации. Действительно, сравнение типа a < b даёт результат “да” или “нет”, то есть не больше 1 бита информации. В то же время, сортировка массива \(N\) различных элементов соответствует выбору одной из всех возможных перестановок. Число перестановок массива длины \(N\) – \(N!\). Тогда, считая все перестановки равновероятными, по формуле Хартли получаем, что выбору одной перестановки соответствует \(\log_2 N!\) бит информации.

Рассмотрим \(\log_2 N!\):

\[\log_2 N! = \sum_{i=1}^N \log_2 i < N \log_2 N\] \[\log_2 N! = \sum_{i=1}^N \log_2 i > \sum_{i=N/2}^N \log_2 i > \frac{N}{2} \log_2 \frac{N}{2}\]

Пусть \(N\ge 4\), тогда:
\(\log_2 N \ge \log_2 4 = 2\)
\(\log_2 \frac{N}{2}\ge 1\)
\(\frac{N}{4}\log_2 \frac{N}{2}\ge \frac{N}{4}\)
\(\frac{N}{2}\log_2 \frac{N}{2} \ge \frac{N}{4}\log_2 N,\)
тогда \[N \log_2 N > \log_2 N! > \frac{N}{4}\log_2 N,\]

т.е. для выбора одной перестановки, в отсутствие дополнительной информации о структуре массива, требуется \(\mathcal O(N\log N)\) бит, т.е. \(\mathcal O(N\log N)\) операций сравнения.

Таким образом, для алгоритмов, выполняющих одно сравнение за итерацию, число итераций не может быть лучше \(\mathcal O(N\log N).\)