Арифметическое сжатие

Сжатие по методу Хаффмана постепенно вытесняется арифметическим сжатием. Свою роль в этом сыграло то, что закончились сроки действия патентов, ограничивающих использование арифметического сжатия. Кроме того, алгоритм Хаффмана приближает относительные частоты появления отсчетов в потоке частотами, кратными

Рисунок 3.2. Коды Хаффмана

степени двойки (например, для символов а, b, с, d с вероятностями 1/2, 1/4, 1/8, 1/8 будут использованы коды О, 10, 110, 111), а арифметическое сжатие дает лучшую степень приближения частоты. По теореме Шеннона наилучшее сжатие в двоичной арифметике мы получим, если будем кодировать отсчет с относительной частотой f с помощью бит.

На рис. приводится сравнение оптимального кодирования и кодирования по методу Хаффмана. Хорошо видно, что в ситуации, когда относительные частоты не являются степенями двойки, сжатие становится менее эффективным (мы тратим больше битов, чем это необходимо). Например, если у нас два отсчета а и b с вероятностями 253/256 и 3/256, то в идеале мы должны потратить на цепочку из 256 байт

,

т. е. 24 бита. При кодировании по Хаффману мы закодируем а и b как 0 и 1 и нам придется потратить 1 -253+1 -3=256 бит, т. е. в 10 раз больше.

Рисунок 3.3. Сравнение эффективности арифметического сжатия и метода Хаффмана

Арифметическое сжатие - достаточно изящный метод, в основе которого лежит очень простая идея. Кодируемая последовательность представляется в виде дроби, при этом дробь строится таким образом, чтобы последовательность данных была представлена как можно компактнее. Для этого последовательность разбивается на подынтервалы с длинами, равными вероятностям появления величин в потоке [5].

Арифметическое сжатие выделяется тем, что обеспечивает возможность кодирование менее одного бита на символ.