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