\[H = \log_2 N,\]

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

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

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

• легко обобщается для набора \(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\), тогда:

• требуется \(\mathcal O(N\log N)\) бит
• операция сравнения даёт 1 бит
• \(\mathcal O(N\log N)\) операций сравнения.
• сложность \(\mathcal O(N\log N)\) – оптимальна для алгоритмов сортировки сравнением

• Рассмотрим алфавит \({a_1, \ldots, a_n, b_1, \ldots, b_m}\) из \(n+m\) символов и запишем с его помощью наше сообщение таким образом, чтобы символы не повторялись. Вероятность обнаружить любой символ нового алфавита одинакова, и мы можем применить формулу Хартли.
• \(H_{n+m} = \log_2(n+m)\)
• В исходном алфавите, символы \(a_i\) неразличимы. За счёт отождествления теряется \(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)\)

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

• количество информации на символ алфавита зависит от вероятности получения этого символа
• вероятность аддитивна, \(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}\)

• количество информации максимально при равновероятных исходах

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

• Пусть для \(N=M-1:\) \(H = \sum_{i=1}^{M-1} P_i \log_2{\frac{1}{P_i}}\)
• Рассмотрим алфавит длины \(N=M\).
• Отождествим \(M\)-тый и \(M-1\)-й символы. Тогда применима формула Шеннона для алфавита размера \(M-1\):
• \(H_{M-1} = \sum_{i=1}^{M-2} P_i \log_2{\frac{1}{P_i}} + (P_{M-1}+P_M) \log_2{\frac{1}{P_{M-1}+P_M}}\)
• относительные вероятности появления отождествлённых символов
• \(q_{M-1} = \frac{P_{M-1}}{P_{M-1}+P_M},\)
• \(q_{M} = \frac{P_{M}}{P_{M-1}+P_M}.\)

• В результате отождествления, теряется \(q_{M-1} \log_2\frac{1}{q_{M-1}} + q_{M} \log_2\frac{1}{q_{M}}\) бит на отождествлённый символ,

• доля отождествлённых символов \(P_{M-1}+P_M\)

• В среднем теряется

  \(H_ε = P_{M-1} \log_2\frac{1}{q_{M-1}} + P_{M} \log_2\frac{1}{q_{M}}\)

  \(H_ε = P_{M-1} \log_2\frac{P_{M-1}+P_M}{P_{M-1}} + P_{M} \log_2\frac{P_{M-1}+P_M}{P_{M}}\)

• Тогда в силу аддтитвности информации,

• \(H_M = H_{M-1}+H_ε\)

  \(H_M = \sum_{i=1}^{M-2} P_i \log_2{\frac{1}{P_i}} + (P_{M-1}+P_M) \log_2{\frac{1}{P_{M-1}+P_M}}\\+P_{M-1} \log_2\frac{P_{M-1}+P_M}{P_{M-1}} + P_{M} \log_2\frac{P_{M-1}+P_M}{P_{M}}\)

  \(H_M = \sum_{i=1}^{M-2} P_i \log_2{\frac{1}{P_i}} +P_{M-1} \log_2\frac{1}{P_{M-1}} + P_{M} \log_2\frac{1}{P_{M}}\)

  \(H_M = \sum_{i=1}^{M} P_i \log_2{\frac{1}{P_i}}\)

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

• Формула Хартли – частный случай формулы Шеннона.
• Если \(P_i = \frac{1}{N},\) то

• \(H = \sum_{i=1}^{N} P_i \log_2{\frac{1}{P_i}}\)

  \(H = \sum_{i=1}^{N} \frac{1}{N} \log_2{N}\)

  \(H = \frac{N}{N} \log_2{N}\)

  \(H = \log_2{N}\)

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

• алгоритм префиксного кодирования
• для оптимального кодирования, более вероятные символы кодируются более короткой последовательностью

Алгоритм:

• символам алфавита присваиваются значения приоритетов, соответствующие частоте
• два символа с наименьшими приоритетами отождествляются, отождествлённый символ получает приоритет, равный сумме
• Последовательность отождествлений образует двоичное дерево
• “левым” ветвям дерева присваивается код “0”, а “правым” – “1”. Кодом символа является последовательность кодов ветвей, приводящих к нему.

• закодируем сообщение “шла_Маша_по_шоссе”.