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

Пусть у нас есть некий алфавит, а так-же данные о частотности использования символов (опционально). Тогда рассмотрим на координатной прямой отрезок о 0 до 1.

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

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

Как только символы закончатся, выберем число из рабочего отрезка - это единственное число, которое требуется, чтобы закодировать последовательность чисел.