• \(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,\] \[|C(x)| = \ceil{-\log_2 P(x)} + 1\]

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

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

• Используется вероятностная модель источника.

• Отделена от алгоритма кодирования.

• Произвольный выбор вероятностной модели.

Источник \(X=\{x_1, \ldots, x_n, x_I\}\)

• \(x_I\) – “конец сообщения”.
• вероятностная модель, \(P(x_i|\vect s)\)

Алгоритм:

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

Формально \[Q(x_k | \vect s) \equiv \sum_{i=1}^{k-1} P(x_i | \vect s),\] \[R(x_k | \vect s) \equiv Q(x_k | \vect s) + P(x_k | \vect s).\]

l := 0.0
h := 1.0
w := h-l
for n = 1 to N {
  h := l + w * R(x_n | s_n)
  l := l + w * Q(x_n | s_n)
  w := h - l
}

l := 0.0
h := 1.0
w := h-l
for n = 1 to N {
  h := l + w * R(x_n | s_n)
  l := l + w * Q(x_n | s_n)
  w := h - l
}

• N – длина сообщения
• s_n – строка ранее прочитанных символов
• x_n – очередной символ источника

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

1. Выберем отрезок, содержащий число, соответствующее коду. Символ, соответствующий отрезку, дописываем в ответ.
2. Нормируем отрезок и вещественное число.
3. Повторим пункты 1—2 до тех пор, пока не получим ответ.

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

Лучше Хаффмана с большой длиной блока?

• Да!
• Арифметическое кодирование – вычисляем \(N |X|\) вероятностей
• Алгоритм Хаффмана – вычисляем все \(|X|^N\) вероятностей.

Ожидаемая длина кода

Энтропия строки \(\vect s\) длины \(N\)

\[H = - \sum_{\vect s \in X^N} P(\vect s) \log_2 P(\vect s)\]

Та же энтропия, что у выбора отрезка длиной \(P(\vect s)\) на интервале \([0,1)\).

Избыточность арифметического кода – только из-за конечной точности.

Пусть кодируется интервал \([R_l, R_h)\), который “почти полностью” заполняет некий двоичный интервал \([B_l, B_h)\), \(0 < R_l - B_l < \varepsilon,\) \(0 < B_h - R_h < \varepsilon\).

Интервалы \([B_l, B_l + (B_h-B_l)/2)\), \([B_l+ (B_h-B_l)/2, B_h)\) не подходят, т.к. \(R_l > B_l,\) \(R_h < B_h\).

Интервал \([B_l + (B_h-B_l)/4, B_l + 3(B_h-B_l)/4)\) – подходит. Требует 2 дополнительных бит.

\[L(C,X^N) < H(X^N)+2\]

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

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

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

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

Алгоритм движется по входной строке, держа в памяти “словарь”. Встречая новую подстроку, алгоритм выводит индекс в словаре максимального префикса и суффикс (при двоичном входном алфавите, суффикс всегда имеет длину 1 бит). Для записи префикса используется \(\ceil{log_2 N}\) бит, где \(N\) – текущий размер словаря.

На практике, размер “словаря” ограничивается.

При декодировании, “словарь” восстанавливается “на лету”.

Пример

Рассмотрим алгоритм LZ для двоичных входного и целевого алфавита.

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

Для эргодического источника LZ с ростом размера сообщения асимптотически приближается к энтропии источника.

Ключевые слова:

• “асимптотически”
• “с ростом размера сообщения”

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