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

Определение:

Арифметическое кодирование (англ. Arithmetic coding) — алгоритм сжатия информации без потерь, который при кодировании ставит в соответствие тексту вещественное число из отрезка [math][0; 1)[/math]. Данный метод, как и алгоритм Хаффмана, является энтропийным, т.е. длина кода конкретного символа зависит от частоты встречаемости этого символа в тексте. Арифметическое кодирование показывает более высокие результаты сжатия, чем алгоритм Хаффмана, для данных с неравномерными распределениями вероятностей кодируемых символов.

Принцип действия

При арифметическом кодировании каждый символ кодируется нецелым числом бит, что эффективнее кода Хаффмана (теоретически, символу [math]a[/math] с вероятностью появления [math]p(a)[/math] допустимо ставить в соответствие код длины [math]-\log_2 p(a)[/math], следовательно, при кодировании алгоритмом Хаффмана это достигается только с вероятностями, равными обратным степеням двойки).

Кодирование

На вход алгоритму передаются текст для кодирования и список частот встречаемости символов.

1. Рассмотрим отрезок [math][0; 1)[/math] на координатной прямой.
2. Поставим каждому символу текста в соответствие отрезок, длина которого равна частоте его появления.
3. Считаем символ из входного потока и рассмотрим отрезок, соответствующий этому символу. Разделим этот отрезок на части, пропорциональные частотам встречаемости символов.
4. Повторим пункт [math](3)[/math] до конца входного потока.
5. Выберем любое число из получившегося отрезка, которое и будет результатом арифметического кодирования.

Псевдокод

• [math]\mathtt{s}\,[/math] — текст, подаваемый на вход;
• [math]\mathtt{n}\,[/math] — длина исходного текста;
• [math]\mathtt{m}\,[/math] — мощность алфавита исходного текста;
• [math]\mathtt{letters[m]}\,[/math] — массив символов, составляющих алфавит исходного текста;
• [math]\mathtt{probability[m]}\,[/math] — массив вероятностей обнаружения символа в тексте;
• [math]\mathtt{Segment}\,[/math] — структура, задающая подотрезок отрезка [math][0; 1)[/math], соответствующего конкретному символу на основе частотного анализа. Имеет поля:
  • [math]\mathtt{left}\,[/math] — левая граница подотрезка;
  • [math]\mathtt{right}\,[/math] — правая граница подотрезка;
• [math]\mathtt{left}\,[/math], [math]\mathtt{right}\,[/math] — границы отрезка, содержащего возможный результат арифметического кодирования.

struct Segment:
    double left
    double right

Segment[m] defineSegments(letters: char[m], probability: double[m]):
   Segment[m] segment
   double l = 0
   for i = 0 to m - 1
       segment[letters[i]].left = l
       segment[letters[i]].right = l + probability[i]
       l = segment[letters[i]].right
   return segment

double arithmeticCoding(letters: char[m], probability: double[m], s: char[n]):
    Segment[m] segment = defineSegments(letters, probability)
    double left = 0
    double right = 1
    for i = 0 to n - 1
        char symb = s[i]
        double newRight = left + (right - left) * segment[symb].right
        double newLeft = left + (right - left) * segment[symb].left
        left = newLeft
        right = newRight
    return (left + right) / 2

Замечание: для оптимизации размера кода можно выбрать из полученного на последнем шаге диапазона [math][left; right][/math] число, содержащее наименьшее количество знаков в двоичной записи.

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

Алгоритм по вещественному числу восстанавливает исходный текст.

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

Псевдокод

• [math]\mathtt{code}\,[/math] — вещественное число, подаваемое на вход;
• [math]\mathtt{n}\,[/math] — длина восстанавливаемого текста;
• [math]\mathtt{m}\,[/math] — мощность алфавита исходного текста;
• [math]\mathtt{letters[m]}\,[/math] — массив символов, составляющих алфавит исходного текста;
• [math]\mathtt{probability[m]}\,[/math] — массив вероятностей обнаружения символа в тексте;
• [math]\mathtt{segment}\,[/math] — структура, задающая подотрезок отрезка [math][0; 1)[/math], соответствующего конкретному символу на основе частотного анализа. Имеет поля:
  • [math]\mathtt{left}\,[/math] — левая граница подотрезка;
  • [math]\mathtt{right}\,[/math] — правая граница подотрезка;
  • [math]\mathtt{character}\,[/math] — значение символа.

struct Segment:
    double left
    double right
    char character

Segment[m] defineSegments(letters: char[n], probability: double[n]):
   Segment[m] segment
   double l = 0
   for i = 0 to m - 1
       segment[i].left = l
       segment[i].right = l + probability[i]
       segment[i].character = letters[i]
       l = segment[i].right
   return segment

string arithmeticDecoding(letters: char[m], probability: double[m], code: double, n: int):
    Segment[m] segment = defineSegments(letters, probability) 
    string s = ""
    for i = 0 to n - 1
        for j = 0 to m - 1
            if code >= segment[j].left and code < segment[j].right
                s += segment[j].character
                code = (code – segment[j].left) / (segment[j].right – segment[j].left)
                break
    return s

Замечание: кодировщику и декодировщику должно быть известно, когда завершать работу. Для этого можно передавать в качестве аргумента длину текста или символ конца файла, после которого процесс должен быть остановлен.

Замечание: Несмотря на преимущества арифметического кодирования, существует проблема при его практическом применении из-за несовершенства представления чисел с плавающей точкой в памяти компьютера — поскольку некоторые дробные числа не могут быть точно представлены в двоичном коде, используемом современными процессорами (например, [math]\dfrac{1}{3}[/math]), границы символов будут округлены, что может повлечь за собой неверную работу алгоритма при больших объёмах данных. В общем случае, алгоритм можно модифицировать так, чтобы результатом было дробное число. В такой реализации вероятность встречи символа представляется в виде рационального числа. Поскольку в каждой итерации будет переход из текущего отрезка в один из его [math]m[/math] подотрезков, кратных по длине [math]n[/math], а всего итераций [math]n[/math], в конечном результате знаменатель дроби не превысит [math]n^{n}[/math], а поскольку сумма всех вероятностей встречи символов равна [math]1[/math], полученная дробь будет находиться в промежутке [math][0; 1)[/math].

Пример работы

Рассмотрим в качестве примера строку [math]abacaba[/math]:

Кодирование

Символ	Частота появления
[math]a[/math]	[math]0.571429[/math]
[math]b[/math]	[math]0.285714[/math]
[math]c[/math]	[math]0.142857[/math]

Пример работы кодировщика

Считанный символ	Левая граница отрезка	Правая граница отрезка
	[math]0[/math]	[math]1[/math]
[math]a[/math]	[math]0[/math]	[math]0.571429[/math]
[math]b[/math]	[math]0.326531[/math]	[math]0.489796[/math]
[math]a[/math]	[math]0.326531[/math]	[math]0.419825[/math]
[math]c[/math]	[math]0.406497[/math]	[math]0.419825[/math]
[math]a[/math]	[math]0.406497[/math]	[math]0.414113[/math]
[math]b[/math]	[math]0.410849[/math]	[math]0.413025[/math]
[math]a[/math]	[math]0.410849[/math]	[math]0.412093[/math]

Код: [math]0.411471[/math]

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

Код: [math]0.411471[/math]

Пример работы декодировщика

Декодируемый символ	Код
[math]a[/math]	[math]0.411471[/math]
[math]b[/math]	[math]0.720074[/math]
[math]a[/math]	[math]0.520259[/math]
[math]c[/math]	[math]0.910454[/math]
[math]a[/math]	[math]0.373178[/math]
[math]b[/math]	[math]0.653061[/math]
[math]a[/math]	[math]0.285714[/math]

Замечание: при декодировании текста можно не только нормализовывать рабочий отрезок и текущий код, но и уменьшать рабочий отрезок (аналогично кодированию), не изменяя значение кода.

Декодирование (второй способ)

Код: [math]0.411471[/math]

Пример работы декодировщика (второй способ)

Декодируемый символ	Границы отрезка
[math]a[/math]	[math]0[/math]	[math]0.571429[/math]	[math]0.857143[/math]	[math]1[/math]
[math]b[/math]	[math]0[/math]	[math]0.326531[/math]	[math]0.489796 [/math]	[math]0.571429[/math]
[math]a[/math]	[math]0.326531 [/math]	[math]0.419825 [/math]	[math]0.466472 [/math]	[math]0.489796 [/math]
[math]c[/math]	[math]0.326531[/math]	[math]0.379842[/math]	[math]0.406497[/math]	[math]0.419825[/math]
[math]a[/math]	[math]0.406497[/math]	[math]0.414113[/math]	[math]0.417921 [/math]	[math]0.419825[/math]
[math]b[/math]	[math]0.406497[/math]	[math]0.410849[/math]	[math]0.413025[/math]	[math]0.414113[/math]
[math]a[/math]	[math]0.410849[/math]	[math]0.412093[/math]	[math]0.412714[/math]	[math]0.413025[/math]

Оценка длины кодового слова

Теорема:

При арифметическом кодировании длина кодового слова не превышает энтропии исходного текста.

Доказательство:

[math]\triangleright[/math]

Введём следующие обозначения: [math]l[/math] — длина текста, [math]n[/math] — размер алфавита, [math]f_i[/math] — частота встречаемости символа, [math]p_i[/math] — вероятность вхождения символа. Размер сообщения [math]L[/math] можно найти по формуле: [math] L = \prod\limits_{i=1}^l p_{fi} = \prod\limits_{i=1}^n p_{i}^{f_{i}}[/math] Число бит в закодированном тексте: [math]\log_2 L = \sum\limits_{i=1}^n f_i\cdot \log_2 p_i = l \cdot \sum\limits_{i=1}^n p_i\cdot \log_2 p_i = -l \cdot H(p_1...p_n)[/math]

[math]\triangleleft[/math]

См. также

• Алгоритм Хаффмана
• Алгоритмы LZ77 и LZ78
• Энтропия случайного источника

Источники информации

• Википедия — Арифметическое кодирование
• Wikipedia — Arithmetic coding
• Арифметическое кодирование
• Визуализатор арифметического кодирования