Что обозначает n в формуле хартли

Что обозначает n в формуле хартли

1.2. Формула Хартли измерения количества информации. Закон аддитивности информации

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

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

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

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

Решим эту задачу с точки зрения содержательного и алфавитного подходов. Поскольку изначально в шкафу было `8` полок, а в итоге мы выберем одну, следовательно, неопределённость знания о местоположении книги уменьшится в `8` раз. Мы говорили, что один бит – это количество информации, уменьшающее неопределённость знания в `2` раза. Следовательно, мы должны получить `3` бита информации.

Теперь попробуем использовать алфавитный подход. Закодируем номера всех полок при помощи `0` и `1`. Получим следующие номера: `000, 001, 010, 011, 100, 101, 110, 111`. Для того чтобы узнать, на какой полке находится книга, мы должны узнать номер этой полки. Каждый номер состоит из `3` двоичных знаков. А по определению, `1` бит (в алфавитном подходе) – это количество информации в сообщении, состоящем из `1` двоичного знака. То есть мы тоже получим `3` бита информации.

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

Назовём логарифмом числа `N` по основанию `a` такое число `X`, что Обозначение:

На параметры логарифма налагаются некоторые ограничения. Число `N` обязательно должно быть строго больше `0`. Число `a` (основание логарифма) должно быть также строго больше нуля и при этом не равняться единице (ибо при возведении единицы в любую степень получается единица).

Теперь вернёмся к нашей задаче. Итак, какое же количество информации нам нужно получить, чтобы выбрать один исход из `N` равновероятных? Ответ на этот вопрос даёт формула Хартли: `H=log_aN`, где `N` – это количество исходов, а `H` – количество информации, которое нужно получить для однозначного выбора `1` исхода. Основание логарифма обозначает единицу измерения количества информации. То есть если мы будем измерять количество информации в битах, то логарифм нужно брать по основанию `2`, а если основной единицей измерения станет трит, то, соответственно, логарифм берётся по основанию `3`.

Рассмотрим несколько примеров применения формулы Хартли.

В библиотеке `16` стеллажей, в каждом стеллаже `8` полок. Какое количество информации несёт сообщение о том, что нужная книга находится на четвёртой полке?

Решим эту задачу с точки зрения содержательного подхода. В переданном нам сообщении указан только номер полки, но не указан номер стеллажа. Таким образом, устранилась неопределённость, связанная с полкой, а стеллаж, на котором находится книга, мы всё ещё не знаем. Так как известно, что в каждом стеллаже по `8` полок, следовательно, неопределённость уменьшилась в `8` раз. Следовательно, количество информации можно вычислить по формуле Хартли `H=log_2 8=3` бита информации.

Имеется `27` монет, одна из которых фальшивая и легче всех остальных. Сколько потребуется взвешиваний на двухчашечных весах, чтобы однозначно найти фальшивую монету?

В этой задаче неудобно использовать бит в качестве основной единицы измерения информации. Двухчашечные весы могут принимать три положения: левая чаша перевесила, значит, фальшивая монета находится в правой; правая чаша перевесила, значит, монета находится в левой; или же весы оказались в равновесии, что означает отсутствие фальшивой монеты на весах. Таким образом, одно взвешивание может уменьшить неопределённость в три раза, следовательно, будем использовать в качестве основной единицы измерения количес-тва информации трит.

По формуле Хартли `H = log _3 27 = 3` трита. Таким образом, мы видим, что для того чтобы найти фальшивую монету среди остальных, нам потребуется три взвешивания.

Логарифмы обладают очень важным свойством: `log_a(X*Y)=log_aX+log_aY`.

Если переформулировать это свойство в терминах количества информации, то мы получим закон аддитивности информации: Коли-чество информации`H(x_1, x_2)`, необходимое для установления пары `(x_1, x_2)`, равно сумме количеств информации `H(x_1)` и `H(x_2)`, необходимых для независимого установления элементов `x_1` и `x_2`:

Проиллюстрируем этот закон на примере. Пусть у нас есть игральная кость в форме октаэдра (с `8` гранями) и монета. И мы одновременно подбрасываем их вверх. Нужно узнать, какое количество информации несёт сообщение о верхней стороне монеты после падения (орёл или решка) и числе, выпавшему на игральной кости.

Игральная кость может упасть `8` различными способами, следовательно, по формуле Хартли можно вычислить, что, определив число, выпавшее на игральной кости, мы получаем `3` бита информации. Соответственно, монета может упасть только `2` способами и несёт в себе `1` бит информации. По закону аддитивности информации мы можем сложить полученные результаты и узнать, что интересующее нас сообщение несёт `4` бита информации.

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

Источник

Основы теории информации. Формула Хартли. Формула Шеннона.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

\[ H = P_a \log_2\frac<1> + P_b \log_2\frac<1> \]

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

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

\[ H(P_a) = P_a \log_2\frac<1> + (1-P_a) \log_2\frac<1> <1-P_a>\]

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

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

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

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

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

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

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

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

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

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

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

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

Легко можно показать случаи не оптимального кодирования информации. Допустим, кодируется результат падения монеты: орел или решка. Мы уже знаем, что количество информации в данном случае равно одному биту. При этом, если закодировать эти значения, например, русскими словами в коде 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 \]

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

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

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

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

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

\[\log_2 N! = \sum_^N \log_2 i \[\log_2 N! = \sum_^N \log_2 i > \sum_^N \log_2 i > \frac <2>\log_2 \frac<2>\]

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

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

Источник