Арифметический сжатие - метод, в основе которого лежит очень простая идея: представляем текст кодируется в виде дроби, при этом строим дробь таким образом, чтобы текст был представлен как можно компактнее.
Обеспечивает почти оптимальную степень сжатия с точки зрения энтропийной оценки кодирования Шеннона. На каждый символ нужно почти H бит, где H - информационная энтропия источника.
Пусть есть какой-то алфавит, а также данные о частотности использования символов (опционально). Тогда рассмотрим на координатной прямой отрезок от 0 до 1.
Расположим на нем точки таким образом, что длины отрезков будут равны частоте использования символа, и каждый такой отрезок будет соответствовать одному символу.
Теперь возьмем символ из потока и найдем для него отрезок среди свежесформированных, теперь отрезок для этого символа стал рабочим. Разобьем его таким же образом, как разбили отрезок от 0 до 1. Выполним эту операцию для некоторого числа последовательных символов. Затем выберем любое число с рабочего отрезка. Биты этого числа вместе с длиной его битовой записи и результат арифметического кодирования использованных символов потока.