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