Недостатки посимвольного кодирования

Алгоритм Хаффмана часто называется “оптимальным”, однако следует понимать, что это оптимальный алгоритм посимвольного кодирования. Как правило, посимвольное кодирование неэффективно само по себе.

Во-первых, посимвольное кодирование само по себе не допускает адаптации к контексту. Например, при кодировании русского текста, после буквы “ш” не может находиться буква “ы” (ну или по крайней мере вероятность её там обнаружить крайне мала). Однако, при посимвольном кодировании, это нельзя прямо учесть. Один способ учёта таких связей в заключается в кодировании диграмм, триграмм и пр, однако это ведёт к “раздуванию” кодовых таблиц. Другой вариант – модификация таблиц кодов “на лету”, однако этот подход сильно усложняет кодирование и декодирование. Плюс, этот вариант подразумевает передачу кодовых таблиц вместе с кодированным сообщением, что, вообще говоря, может сильно увеличивать избыточность.

Во-вторых, невинно выглядящая оценка для ожидаемой длины кодового слова в оптимальном случае, \(H(X) \le L(C,X) < H(X)+1\) говорит нам, что кодирование будет иметь от 0 до 1 бит избыточности. Если \(H(X)\) велико, это не слишком важно, однако в реальных приложениях ситуация \(H(X) \le 1\) не редка, и в таком случае избыточность кода в итоге будет доминировать.

Арифметическое кодирование

Основная идея арифметического кодирования заключается в следующем. Рассмотрим посимвольный код Элиаса: для его построения, нам достаточно по известным вероятностям каждого символа вычислить число \(F_i = \frac{p_i}{2} + \sum_{j=1}^{i-1} p_j,\) и каждый символ закодировать \(\left\lceil -\log_2 p_i \right\rceil + 1\) битами двоичного представления \(F_i\). Этот код, очевидно, неэффективен: даже если собственное информационное содержание символа меньше 1 бита, код Элиаса использует не менее 2 бит на символ. Однако, код Элиаса требует для построения только знания вероятностей появления каждого символа \(p_i\). Что, если вместо кодирования посимвольно, кодировать аналогичным образом всю строку целиком, для каждого символа рассматривая условные вероятности его появления при известной остальной строке \(P(x_i | \mathbf{s})\)? Это приводит нас к арифметическому кодированию.

Арифметическое кодирование

алгоритм сжатия информации без потерь, который при кодировании ставит в соответствие тексту вещественное число из отрезка [0;1).

Арифметические коды разработаны Элиасом, Риссаненом и Паско, практический алгоритм разработан Виттеном и др¹²

В алгоритме арифметического кодирования используется вероятностная модель источника. При этом вероятностная модель чётко отделена от, собственно, алгоритма кодирования. Ключевым отличием от алгоритмов посимвольного кодирования является произвольность выбора вероятностной модели – символы не обязательно считаются независимыми.

Пусть имеется источник \(X=\{x_1, \ldots, x_n, x_I\}\), где \(x_I\) – специальный символ, означающий “конец сообщения”. Источник посимвольно производит символы \(x_i\), не обязательно независимые. Пусть имеется вероятностная модель, способная для произвольного символа \(x_i\) и известной строки ранее полученных символов \(\mathbf{s} = x_1 x_2 \ldots x_{i-1}\) вычислить вероятность \(P(x_i|\mathbf{s})\). Двоичная последовательность на выходе из кодера соответствует числу в интервале \([0, 1)\), дробная часть которого в двоичном представлении является последовательностью на выходе из кодера. На интервале \([0, 1)\) Каждому символу источника \(x_i\) ставится в соответствие интервал длины, пропорциональной \(P(x_i)\). На каждом из этих интервалов, каждой последовательности двух символов \(x_i x_j\) ставится в соответствие интервал длины, пропорциональной \(P(x_j | x_i)\), и т.д.

Тогда, алгоритм кодирования:

1. Поставим каждому символу \(x_i\) в соответствие отрезок, длина которого пропорциональна \(P(x_i)\) его появления.
2. Считаем символ \(x_i\) из источника и рассмотрим интервал, соответствующий этому символу. Разделим этот отрезок на части, пропорциональные \(P(x_j | x_i)\).
3. Повторим пункт (3) до конца входного потока.
4. Выберем любое число из получившегося отрезка, которое и будет результатом арифметического кодирования.

Кодирование

Более формально, алгоритм можно описать следующим образом. Каждый интервал определяется “кумулятивными вероятностями”: \[Q(x_k | \mathbf{s}) \equiv \sum_{i=1}^{k-1} P(x_i | \mathbf{s}),\] \[R(x_k | \mathbf{s}) \equiv Q(x_k | \mathbf{s}) + P(x_k | \mathbf{s}).\]

Тогда,

u := 0.0
v := 1.0
p := v-u
for n = 1 to N {
  v := u + p R(x_n | s_n)
  u := u + p Q(x_n | s_n)
  p := v - u
}

Здесь N – длина сообщения, s_n – строка \(\mathbf{s}\) всех ранее прочитанных символов, x_n – очередной символ источника. Здесь неявно предполагается арифметика бесконечной точности.

Этот алгоритм может быть реализован потоково, т.е. отправлять первые биты кода до того, как получены последние символы источника. Действительно, если на очередном шаге алгоритма оказывается, например, что \(u = 0.10101101\ldots_2\), \(v = 0.10101110\ldots_2\), то, независимо от остальных символов источника, код будет начинаться на 10101101.

Для оптимизации размера кода, на последнем шаге в интервале \([u, v)\) выбирается число, имеющее наименьшее число знаков в двоичном представлении.

На практике используется целочисленная арифметика вместо арифметики с плавающей запятой.

Декодирование

1. Выберем на интервале \([0;1)\), разделённом на части, длины которых пропорциональны вероятностям \(P(x_i)\), подинтервал, содержащий число, соответствующее коду. Символ, соответствующий этому подотрезку, дописываем в ответ.
2. Нормируем подотрезок и вещественное число.
3. Повторим пункты 1—2 до тех пор, пока не получим ответ.

Этот алгоритм также допускает потоковую реализацию. Действительно, аналогично посимвольному алгоритму Элиаса, прочитав первых \(\left\lceil \log_2 |X| + 1 \right\rceil\) бит источника, можно однозначно определить интервал, соответствующий первому символу \(x_1\) и т.д.

Эффективность

На первый взгляд может показаться, что арифметическое кодирование не сильно лучше алгоритма Хаффмана с большой длиной блока. Однако, это не так. Статистическая модель источника в случае арифметического кодирования требует вычисления \(N |X|\) вероятностей, в то время как аналогичная таблица для алгоритма Хаффмана требует вычисления всех совместных вероятностей всех возможных комбинаций символов, т.е. \(|X|^N\) вероятностей.

Длина кода

Ожидаемая длина кода самой последовательности источника, в предположении, что вероятностная модель точно описывает распределение вероятностей, близка к Шенноновской энтропии. Действительно, Шенноновская энтропия \[H = - \sum_{\mathbf{s} \in X^N} P(\mathbf{s}) \log_2 P(\mathbf{s})\] соответствует выбору отрезка длины \(P(\mathbf{s})\) на интервале \([0, 1)\), что, собственно, и происходит. Ситуация, однако, осложняется тем, что мы кодируем действительные интервалы двоичным числом конечной точности. В худшем случае, действительный интервал почти полностью заполняет некий двоичный интервал длины \(L\). В таком случае, чтобы однозначно представить этот действительный интервал, требуется выбрать бинарный интервал меньшей длины. Выбрать двоичный интервал длины \(L/2\) нельзя, поскольку либо начало, либо конец будет выходить за рамки действительного интервала, следующая возможная длина двоичного интервала \(L/4\) подходит, её использование несёт \(\log_2 4 = 2\) дополнительных бит.

Таким образом, в худшем случае арифметическое кодирование даёт код, длина которого не более, чем на два бита отличается от Шенноновской энтропии сообщения.

Другие применения арифметического кодирования

Эффективная генерация случайных значений

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

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

Эффективный ввод

Арифметическое кодирование может также использоваться в системах ввода, когда важным оказывается уменьшение числа необходимых действий со стороны пользователя (например, для пользователей с ограниченными возможностями, или систем с ограниченными возможностями ввода). При наличии достаточно хорошей статистической модели языка, в системе ввода, предполагающей при вводе последовательный выбор одного из двух вариантов (для простоты), число действий будет не больше, чем на 2 больше Шенноновской энтропии вводимого текста, в то время как традиционные системы (напр. экранные клавиатуры) значительно менее эффективных³⁴.

Кодирование Лемпеля-Зива

Алгоритм Лемпеля-Зива использует подход, сильно отличающийся от подхода арифметического кодирования, но при этом является значительно более универсальным, хотя не самым эффективным алгоритмом сжатия. Алгоритм разработан Авраамом Лемпелем и Яаковым Зивом в 1977 и 1978 годах, и, считая различные модификации (LZW, LZMA) является одним из наиболее широко применимых – в основном, конечно, в силу универсальности.

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

Алгоритм движется по входной строке, держа в памяти “словарь” – упорядоченный массив виденных подстрок. Каждый раз, когда в тексте встречается новая подстрока, алгоритм выводит индекс максимального префикса этой подстроки в словаре и суффикс (несложные рассуждения показывают, что при двоичном входном алфавите, суффикс всегда имеет длину 1 бит). Для записи префикса используется \(\left\lceil log_2 N \right\rceil\) бит, где \(N\) – размер словаря.

На практике, размер “словаря” ограничивается по техническим соображениям, и после достижения максимального размера, новые записи не добавляются.

При декодировании, “словарь” восстанавливается последовательно при чтении закодированного сообщения.

Пример

Входная строка 11010111011101

Кодирование:

1. Словарь содержит пустую строку с индексом 0.
2. Читается символ 1 входной строки
3. Строка 1 добавляется в словарь с префиксом 0 и индексом 1
4. Читается символ 1 входной строки
5. Строка 11 добавляется в словарь с префиксом 1 и индексом 2
6. и т.д.

Словарь таким образом имеет вид:

1 10 101 11 0 111 01

1. (0, 1) – 1
2. (1, 0) – 10
3. (2, 1) – 101
4. (1, 1) – 011
5. (0, 0) – 0000
6. (4, 1) – 1001
7. (5, 1) – 1011

В результате код

110101011000010011011

Можно заметить, что код длиннее исходной строки. Причина в том, что исходная строка слишком короткая, а в коде Лемпеля-Зива присутствует избыточность, которая убывает с ростом размера входной строки.

Теоретические свойства

В отличие от прочих рассмотренных кодов, код Лемпеля-Зива определяется без упоминания вероятностной модели источника сообщений. Однако, для эргодического источника (т.е. источника, имеющего ограниченную память), можно показать, что алгоритм Лемпеля-Зива с ростом размера сообщения асимптотически даёт размер кодированного сообщения равный энтропии источника.

Ключевые слова здесь “асимптотически” и “с ростом размера сообщения”. Для очень многих источников, размер сообщения, при котором длина кода близка к энтропии, непрактично высок, соответственно в реальных применениях LZ далёк от эффективности арифметического кодирования. Тем не менее, для источников с большим числом повторов, LZ даёт практически хорошие результаты.

---

1. Witten I. H., Neal R. M., Cleary J. G. Arithmetic coding for data compression //Communications of the ACM. – 1987. – Т. 30. – №. 6. – С. 520-540.↩︎

2. Moffat A., Neal R. M., Witten I. H. Arithmetic coding revisited //ACM Transactions on Information Systems (TOIS). – 1998. – Т. 16. – №. 3. – С. 256-294.↩︎

3. Ward D. J., Blackwell A. F., MacKay D. J. C. Dasher-a data entry interface using continuous gestures and language models //UIST. – 2000. – С. 129-137.↩︎

4. Ward D. J., Blackwell A. F., MacKay D. J. C. Dasher: A gesture-driven data entry interface for mobile computing //Human–Computer Interaction. – 2002. – Т. 17. – №. 2-3. – С. 199-228.↩︎