Оценки эффективности
Эффективность посимвольного кодирования
Под неэффективностью того или иного способа кодирования мы будем понимать среднестатистическую длину закодированного сообщения в пересчёте на один символ (чем короче результирующие кодировки — тем более эффективным мы будем считать такой способ кодирования).
Для посимвольного кодирования это — то же самое, что и среднестатистическая длина кода символа.
Например, если в алфавите всего три символа, а никаких статистических закономерностей между теми или иными символами сообщения не наблюдается, то приходится считать, что вероятность встретить любой из символов равна \(1/3\). Таким образом, если длины кодов символов равны \(L_1\), \(L_2\) и \(L_3\), неэффективность кодирования равна
\[ \frac{L_1 + L_2 + L_3}{3} \]
Например, для равномерного кодирования (длины всех кодов символов одинаковы и минимальны) эта неэффективность равна
\[ \frac{2+2+2}{3} = 2 \text{(бит на символ)} \]
В общем же случае, если вероятности возможных символов равны \(p_1, p_2, \ldots p_n\), а длины их кодов равны \(L_1, L_2, \ldots L_n\) соответственно, неэффективность посимвольного кодирования равна
\[ \sum_i p_i L_i = p_1 L_1 + p_2 L_2 + \ldots + p_n L_n \]
Очевидно, эта неэффективность не может быть слишком маленькой: среди длин не может быть более одного нуля, более двух единиц, более четырёх двоек и так далее. К сожалению, такой «наивный» подход
- во-первых, даёт очень грубую оценку
- во-вторых, плохо исследуется математическими методами
Поэтому мы сейчас займёмся его модификацией.
Кроссэнтропия
Обозначим \(q_i = 2^{-L_i}\). Тогда неэффективность кодирования примет вид
\[ -\sum_i p_i \log q_i \]
Формула такого вида называется кроссэнтропией наборов \(p_1, p_2, \ldots p_n\) и \(q_1, q_2, \ldots q_n\).
У кроссэнтропии есть замечательное свойство: её очень легко оценить снизу, если фиксировать сумму \(q_i\). Поэтому без лишних слов обозначим \(S = \sum_i q_i\) и докажем, что
\[ -\sum_i p_i \log q_i \geqslant -\sum_i p_i \log (Sp_i) \]
Правую часть нетрудно получить как единственную критическую точку кроссэнтропии, рассмотренной как зависимость от \(q_2, \ldots q_n\).
Это неравенство можно преобразовать к виду
\[ \sum_i p_i \log \left(\frac{q_i}{Sp_i}\right) \leqslant 0 \]
Но это — частный случай неравенства Йенсена. Говоря по-другому, это — тривиальное следствие обратной выпуклости логарифма (точка на хорде находится под точкой на графике):
\[ 0 = \log 1 = \log \left( \sum_i \frac{p_i q_i}{S p_i} \right) \]
Таким образом, мы доказали, что среднестатистическая длина символа не меньше, чем
\[ -\sum_i p_i \log (Sp_i) = -\sum_i p_i \log S -\sum_i p_i \log p_i = -\log S - \sum_i p_i \log p_i \]
Второе слагаемое в (самой) правой части называется энтропией набора \(p_1, p_2, \ldots p_n\).
Оценка эффективности префиксных кодировок
В общем случае \(S\) не превосходит \(\log n + 1\). Но для префиксных кодировок \(S\) не превосходит \(1\): если расположить коды слов в листьях бинарного дерева, пути в котором — эти самые коды (например, код 011 соответствует шагу влево от корня, затем двум шагам вправо), то сумма \(q_i\) для всех кодов в таком дереве равна полусумме таких сумм в поддеревьях корня. В дереве же высоты 0 такая сумма равна либо 0, либо 1. Поэтмоу в деревьях высоты 1 эта сумма не превосходит 1. И в деревьях высоты 2 — тоже. И так далее (формально это можно доказать, предположив, что неравенство нарушается, и рассмотрев минимальную высоту деревьев, для которой это неравенство нарушается).
Поэтому эффективность префиксной кодировки не может быть лучше энтропии набора вероятностей символов. Тем не менее, даже такая эффективность не достигается. Самой же эффективной среди префиксных кодировок является кодировка Хаффмана.
Кодировка Хаффмана
Сначала договоримся, что мы будем рассматривать только такие префиксные кодировки, в которых ни один из кодов символов нельзя укоротить (путём удаления какого-либо из бит) с сохранением префиксности. Далее будем называть такие кодировки несократимыми.
Нетрудно заметить, что если самая эффективная префиксная кодировка и существует, то она обязана быть несократимой. Также заметим, что несократимых кодировок конечное количество: длина кода символа в несократимой кодировке не может превосходить общее количество символов.
Значит, самая эффективная префиксная кодировка существует: чтобы её найти, достаточно перебрать все несократимые префиксные кодировки. Далее все самые эффективные кодировки (вообще говоря, обычно есть много кодировок с одной и той же эффективностью) мы будем для краткости называть оптимальными.
Теперь сформулируем и докажем (доказательства написаны курсивом) несколько полезных фактов про оптимальные кодировки.
- В оптимальной кодировке код самого редкого символа самый длинный. Если это не так (т.е. есть менее редкий символ с более длинным кодом), то можно поменять местами коды самого редкого символа и символа с самым длинным кодом. Эффективность кодировки повысится.
- В оптимальной кодировке второй по редкости символ должен иметь код той же длины, что и самый редкий. Если символов хотя бы два, то в любой несократимой кодировке у самого длинного кода есть «сосед», отличающийся лишь последним битом. Если же в оптимальной кодировке второй по редкости символ имеет не ту же длину кода, что и самый редкий, можно код этого символа обменять с соседом кода самого редкого. Такой обмен увеличивает эффективность и, тем самым, противоречит оптимальности.
- Среди оптимальных кодировок существует такая (назовём её особо оптимальной), в которой два самых редких символа имеют соседние (в том же смысле, что и в доказательстве предыдущего пунтка) коды. Выберем любую оптимальную кодировку и поменяем местами соседа кода самого редкого символа с кодом второго по редкости символа, получив таким образом искомую кодировку.
- Если заменить в алфавите два самых редких символа (назовём их \(\alpha\) и \(\beta\)) с вероятностями \(p\) и \(q\) на один (назовём его \(\mathfrak{M}\)) с вероятностью \((p+q)\), то оптимальная для полученного алфавита кодировка может быть превращена в оптимальную для исходного путём раздвоения кодового слова \(w\) символа \(\mathfrak{M}\) на кодовые слова \(w0\) и \(w1\) для символов \(\alpha\) и \(\beta\). Пусть полученная кодировка не оптимальна и имеет неэффективность, равную \(N\). Тогда рассмотрим особо оптимальную кодировку, в которой коды символов \(\alpha\) и \(\beta\) соседние. Заменим эти два кода на их общий префикс, а символы \(\alpha\) и \(\beta\) — на \(\mathfrak{M}\). Получим кодировку, неэффективность которой меньше \(N-(p+q)\). Осталось заметить, что неэффективность исходной кодировки была равна \(N-(p+q)\).
Многократно редуцируя алфавит подобным образом, получим алфавит из одного символа, для которого оптимальная кодировка — пустой код. Оптимальная кодировка для исходного алфавита может быть получена обратной цепочкой «раздвоений». Такая оптимальная кодировка называется кодировкой Хаффмана.
Про кодировку Хаффмана нужно понимать, что:
- она определена неоднозначно (так как «раздвоение» можно сделать двумя разными способами, да и вариантов того, какие два символа соединять, иногда доступно сразу несколько)
- могут быть кодировки с такой же эффективностью, отличающиеся от любой из кодировок Хаффмана
Эффективность произвольного кодирования
Если рассматривается произвольное кодирование, то аналогом средней длины кода символа является следующая величина, определённая для каждого целого неотрицательного \(N\):
\[ \frac{1}{N}\sum_i P_i L_i \]
где сумма берётся по всевозможным текстам длины \(N\), символом \(P_i\) обозначена вероятность возникновения \(i\)-го текста, а \(L_i\) — длина \(i\)-го текста.
Как и ранее, вводя обозначение \(Q_i=2^{-L_i}\), мы можем получить нижнюю теоретическую оценку на неэффективность кодирования сообщений длины \(N\):
\[ -\frac{\log\sum_i Q_i}{N} - \frac{\sum_i P_i \log P_i}{N} \]
В числителе первой дроби среди слагаемых под логарифмом не более одной единицы, не более двух половин, не более четырёх четвертей и так далее… Это означает, что если количество слагаемых не превосходит \(2^{k}-1\), то вся сумма не превосходит \(k\).
Слагаемых \(Q_i\) у нас \(n^N\). Поэтому
\[ \sum_i Q_i \leqslant \log (n^N + 1) \leqslant \log (2 n^N) \leqslant 1 + N \log n \leqslant 2 N \log n \]
А «средняя длина кода символа» не меньше чем
\[ -\frac{\log(2N\log n)}{N} - \frac{\sum_i P_i \log P_i}{N} \]
Учитывая, что
\[ \frac{\log (2N\log n)}{N} \rightarrow_N 0 \]
можно говорить о том, что нижняя теоретическая оценка на неэффективность кодирования (для достаточно длинных сообщений):
\[ -\frac{\sum_i P_i \log P_i}{N} \]
Если же хочется в целом оценить неэффективность кодировки, не выбирая конкретную длину сообщений, то можно вычислить так называемое среднее Чезаро последовательности нижних оценок
\[ B_N = -\frac{\log(2N\log n)}{N} - \frac{\sum_i P_i \log P_i}{N} \]
Под средним Чезаро бесконечной последовательности \(B\) понимается
\[ \lim_k \frac{B_1+B_2+\ldots+B_k}{k} \]
Опять же, если заменить последовательность \(B\) на последовательность
\[ C_N = - \frac{\sum_i P_i \log P_i}{N} \]
то среднее Чезаро не поменяется (это следует из того факта, что среднее Чезаро сходящейся последовательности равно пределу этой последовательности; доказательство этого факта оставляем читателю в качестве нетрудного упражнения).
Вообще говоря, во всех вышеприведённых рассуждениях мы предполагали, что длина сообщения заранее известна и не требует кодировки. Если это не так, то можно либо явно кодировать длину её двоичной записью, либо добавить к алфавиту один дополнительный символ, сигнализирующей о конце. Оба этих способа не меняют нижнюю теоретическую оценку. Для первого способа длина кода длины в пересчёте на один символ сообщения в пределе равна нулю. Для второго способа длины всех сообщений просто увеличиваются на 1 с сохранением того же набора вероятностей. Среднее Чезаро от такого преобразования не меняется (аккуратное доказательство оставим в качестве упражнения для читателя).
Аддитивность энтропии
В случае, когда вероятности появления очередной буквы не зависят от того, какие буквы были до неё, вероятность получить текст, состоящий из букв с вероятностями \(p_{i_1}, p_{i_2}, \ldots p_{i_n}\), равна
\[ p_{i_1} p_{i_2} \ldots p_{i_n} \]
Энтропия такого набора, оказывается, просто в \(n\) раз больше энтропии набора \(p_i\). Для того, чтобы это понять, первым делом раскроем логарифм произведения и во всех суммах, кроме первой, переименуем «связанные переменные»
\[ -\sum_{i_1i_2\ldots i_n} p_{i_1} p_{i_2} \ldots p_{i_n} \log p_{i_1} p_{i_2} \ldots p_{i_n} = -n \sum_{i_1i_2\ldots i_n} p_{i_1} p_{i_2} \ldots p_{i_n} \log p_{i_1} \]
Осталось заметить, что
\[ \sum_{i_2\ldots i_n} p_{i_2} \ldots p_{i_n} = (\sum_i p_i)^{n-1} = 1 \]
откуда сразу следует, что искомая энтропия равна
\[ -n \sum_i p_i \log p_i \]
В пересчёте на один символ это даёт в точности энтропию набора \(p_i\).
Зависимые вероятности
Важно понимать, что энтропия является теоретическим минимумом, если события «на \(i\)-м месте текста встретился такой-то символ алфавита» являются независимыми. В противном случае может быть всякое.
Например, можно гипотетически предствить, что в алфавите всего две буквы: после \(a\) всегда идёт \(b\), а после \(b\) — всегда \(a\). Тогда вероятности встречи символов равны \(1/2\), а энтропия равна \(1\) биту на символ. Но при этом в реальности любое сообщение фиксированной длины можно закодировать \(0\) битами (а если длина заранее неизвестна, то на кодировку длины, равной \(n\), достаточно \(\log n\) бит, что в пределе также даёт \(0\) бит на символ).
Диапазонная кодировка
Диапазонная (она же — арифметическая) кодировка — способ достичь теоретического минимума неэффективности.
Пусть требуется кодировать сообщения, вероятность \(i\)-го из которых равна \(P_i\). Для этого разобьём отрезок от \(0\) до \(1\) на участки с длинами \(P_i\).
Каждое сообщение будем кодировать двоичной записью дробной части любой из точек этого отрезка.
Нетрудно заметить, что для того, чтобы хотя бы одно число с \(k\) двоичными цифрами в дробной части гарантированно попало в любой отрезок длины \(P_i\), достаточно, чтобы
\[ 2^{-k} \leqslant P_i \]
В частности, можно выбрать все \(k\) так, чтобы длины кодов равнялись результатам округления вверх соответствующих логарифмов. Различные варианты арифметических кодировщиков как раз и отличаются друг от друга алгоритмами выбора конкретных точек внутри отрезков.
Если все сообщения имеют одну и ту же длину \(N\), то неэффективность такого кодирования не превышает
\[ \frac{\sum_i P_i (1 + \log P_i)}{N} = \frac{1}{N} + \frac{\sum_i P_i \log P_i}{N} \]
Учитывая, что первое слагаемое имеет нулевой предел (и, более того, даёт вклад не более 1 бита в общую длину сообщения), можно говорить о том, что арифметическая кодировка достигает нижней теоретической оценки на неэффективность кодирования — удельной (в пересчёте на один символ) энтропии вероятностного распределения текстов. Иногда по этой причине арифметическая кодировка называется энтропийной.