Арифметическое кодирование
Характеристики
- Степень сжатия
- лучшая > 8, худшая - 1
Обеспечивает лучшую степень сжатия чем алгоритм Хаффмана. То есть в соответсвии с теоремой Шеннона — -log2(f) бит на цепочку.
Принцип действия
Пусть у нас есть некий алфавит, а так-же данные о частотности использования символов (опционально). Тогда рассмотрим на координатной прямой отрезок о 0 до 1.
Назовём этот отрезок рабочим. Расположем на нём точки таким образом, что длины образованных отрезков будут равны частоте использования символа и каждый такой отрезок будет соответсвовать одному символу.
Теперь возьмём символ из потока и найдём для него отрезок, среди только что сформированных, теперь отрезок для этого сомвола стал рабочим. Разобьём его таким же образом, как разбили отрезок от 0 до 1. Выполним эту операцию для следующего символа.
Как только символы закончатся, выберем число из рабочего отрезка — это единственное число, которое требуется, чтобы закодировать последовательность чисел.
Интервальное кодирование
То же самое, но с оговоркой, что мы работаем и используем дискретные величины.