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

---

В отличие от алгоритма Хаффмана, не имеет жёсткого постоянного соответствия входных символов группам битов выходного потока. Это даёт алгоритму большую гибкость в представлении дробных частот встречаемости символов.

Как правило, превосходит алгоритм Хаффмана по эффективности сжатия, позволяет сжимать данные с энтропией, меньшей 1 бита на кодируемый символ, но некоторые версии имеют патентные ограничения от компании IBM^[1].

Обеспечивает почти оптимальную степень сжатия с точки зрения энтропийной оценки кодирования Шеннона. На каждый символ требуется почти ${\displaystyle H}$ бит, где ${\displaystyle H}$ — информационная энтропия источника.

В отличие от алгоритма Хаффмана, метод арифметического кодирования показывает высокую эффективность для дробных неравномерных интервалов распределения вероятностей кодируемых символов. Однако в случае равновероятного распределения символов, например, для строки бит 010101…0101 длины ${\displaystyle s}$ метод арифметического кодирования приближается к префиксному коду Хаффмана и даже может занимать на один бит больше^[2].

Для описания алгоритма на некотором алфавите с данными о частотности использования символов используется отрезок ${\displaystyle [0;1]}$, называемый «рабочим», на котором располагаются точки таким образом, что длины образованных отрезков будут равны частоте использования символа, и каждый такой отрезок соответствует одному символу.

Для символа из потока выбирается соответствующий ему отрезок, после чего он становится рабочим отрезком. Далее отрезок разбивается его таким же образом, как был разбит ${\displaystyle [0;1]}$; операция выполняется для некоторого числа последовательных символов. Затем выбирается произвольное число из рабочего отрезка. Биты этого числа вместе с длиной его битовой записи и считаются результатом арифметического кодирования использованных символов потока.

---