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

Характеристики

Степень сжатия

лучшая > 8, худшая - 1

Обеспечивает лучшую степень сжатия чем алгоритм Хаффмана. Т.е. в соответсвии с теоремой Шеннона - -log₂(f) бит на цепочку.

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

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

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

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

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

Интервальное кодирование

То же самое, но с оговоркой, что мы работаем и используем дискретные величины.