Сжатие данных и энтропия
Зафиксируем алфавит \(A\) из \(k\) символов \(a_1, a_2, \ldots a_k\). Нас интересуют строки длины \(n\) над этим алфавитом. Очевидно, что всего строк будет
\[N_1 = k^n.\]Для запоминания строки достаточно запомнить ее номер от \(0\) до \(N_1 - 1\), потратив при этом не более
\[\left\lceil \log_2{N_1} \right\rceil \text{ бит.}\]Такой способ запоминания называется энумеративным кодированием: каждому элементу множества приписывается фиксированный номер.
Пусть каждый символ \(a_i\) встречается в строке \(n_i\) раз. Таких строк будет меньше, чем \(N_1\), а именно:
\[N_2 = \frac{n!}{n_1!n_2! \ldots n_k!}.\]Аналогично, для запоминания строки достаточно запомнить ее номер и потратить при этом не более
\[\left\lceil\log_2{N_2}\right\rceil \text{ бит.}\]Описанную схему запоминания строк, когда известна статистика встречаемости всех символов алфавита в строке, можно считать сжатием. Если принять первый способ запоминания строк как эталонный, то коэффициент сжатия по сравнению со вторым способом:
\[k = \frac{N_1}{N_2}.\]Одна и та же строка в зависимости от способа кодирования может быть представлена разным количеством бит. Числа \(N_1\) и \(N_2\) – это энтропия Хартли для множества всех строк фиксированной длины и множества всех строк с фиксированной статистикой соответственно.
В среднем, для хранения каждого символа строки во втором случае требуется
\[\frac{1}{n}\log_2{N_2} \text{ бит.}\]Используя формулу Стирлинга, можно формально показать, что при \(n \to \infty\) имеет место сходимость:
\[\frac{1}{n}\log_2{\frac{n!}{n_1!n_2! \ldots n_k!}} \to -\sum_{i = 1}^{k} \frac{n_i}{n}\log_2\frac{n_i}{n}.\]Выражение справа является энтропией Шеннона:
\[H = -\sum_{i = 1}^{k}p_i\log_{2}p_i \text{, где } p_i = \frac{n_i}{n}.\]При достаточно больших значениях \(n\) энтропия Шеннона позволяет очень точно аппроксимировать значение
\[\frac{1}{n}\log_2{N_2},\]но всегда
\[\frac{1}{n}\log_2{N_2} < H.\]Вычисление энтропии с использованием логарифма по произвольному основанию:
\[H = \frac{1}{\log{2}}\left(\log{n} - \frac{1}{n}\sum_{i}n_i\log{n_i}\right)\]