Опрос

Какой архиватор наиболее эффективный?:

Новички

Виктор Васильев
Юрий Антонов
Сергей Андреевич
Генадий
Avanasy

Заключительные замечания

Во всех приведенных примерах мы использовали десятичную систему исчисления для лучшего понимания арифметического метода сжатия. Оказывается, что все эти алгоритмы и правила применимы и к двоичному представлению чисел с одним изменением: каждое появление цифры 9 надо заменить цифрой 1 (наибольшей двоичной цифрой).

Может показаться, что приведенные выше примеры не производят никакого сжатия, и во всех трех рассмотренных примерах строки «SWISS-MISS», «02^2^1 «3^3» и «азазазазеоЬ кодируются слишком длинными последовательностями. Похоже, что длина окончательного кода сжатия зависит от вероятностей символов. Длинные числа вероятностей табл. 1.27а породят длинные цифры при кодировании, а короткие цифры табл. 1.24 породят более разумные значения переменных Low и High табл. 1.25. Это поведение требует дополнительных разъяснений.

Для того, чтобы выяснить степень компрессии, достигаемую с помощью арифметического сжатия, необходимо рассмотреть два факта: (1) на практике все операции совершаются над двоичными числами, поэтому следует переводить все результаты в двоичную форму перед тем, как оценивать эффективность компрессии; (2) поскольку последним кодируемым символом является eof, окончательный код может быть любым числом между Low и High. Это позволяет выбрать более короткое число для окончательного сжатого кода.

Табл. 1.25 кодирует строку «SWISS-MISS» некоторым числом в интервале от Low=0.71753375 до High=0.717535, чьи двоичные значения будут приблизительно равны 0.10110111101100000100101010111 и 0.1011011110110000010111111011. Тогда декодер может выбрать строку «10110111101100000100» в качестве окончательного сжатого кода. Строка из 10 символов сжата в строку из 20 битов. Хорошее ли это сжатие?

Ответ будет «да». Используя вероятности из табл. 1.24, легко вычислить вероятность строки «SWISS-MISS». Она равна Р = 0.55 х х0.1 х 0.22 х 0.1 х 0.1 = 1.25 х Ю-6. Энтропия этой строки — log2P = = 19.6096. Значит, двадцать бит - это минимальное число, необходимое для практического кодирования этой строки.

Вероятности символов из табл. 1.27а равны 0.975, 0.001838 и 0.023162. Эти величины требуют довольно много десятичных цифр для записи, а конечные значения Low и High в табл. 1.28 равны 0.994 62270125 и 0.994623638610941. Опять кажется, что тут нет никакого сжатия, однако анализ энтропии показывает отличное сжатие и в этом случае.

Вычисляем вероятность строки «аг^^азаз» и получаем число 0.9752 х 0.001838 х 0.0231622 « 9.37361 х 10~7, а ее энтропия будет равна -log2 (9.37361 х Ю-7) « 20.0249.

В двоичном представлении значения переменных Low и High равны 0.111111101001111110010111111001 и 0.1111111010011111100111101. Можно выбрать любое число из этого промежутка, и мы выбираем «1111111010011111100». Этот код имеет длину 19 (он и теоретически должен быть 21-битным, но числа в табл. 1.28 имеют ограниченную точность).

Пример: Даны три символа aj, a2 и eof с вероятностями Pi = = 0.4, Р20.5 и Peof = 0.1. Кодируем строку «a2a2a2eof». Размер конечного кода будет равен теоретическому минимуму.

Шаги кодирования просты (см. первый пример на стр. 63). Начинаем с интервала [0,1). Первый символ сокращает интервал до [0.4,0.9), второй - до [0.6,0.85), третий - до [0.7,0.825), а четвертый eof - до [0.8125,0.8250). Приблизительные двоичные значения концов равны 0.1101000000 и 0.1101001100, поэтому в качестве кода выбирается 7-битовое число «1101000».

Вероятность этой строки равна 0.53 х 0.1 = 0.0125, тогда число — log2 0.0125 « 6.322, то есть, теоретический минимум длины кода равен 7 бит. (Конец примера.)

Следующее рассуждение показывает, почему арифметическое кодирование может быть весьма эффективным методом сжатия. Обозначим через s последовательность кодируемых символов, а через Ь - число бит, требуемых для кодирования s. Если длина s растет, то ее вероятность P(s) уменьшается, а число b растет. Поскольку логарифм является функцией информации, легко видеть, что число Ь растет с той же скоростью, что log2P(s) убывает. Значит, их произведение остается постоянным. В теории информации показано, что

2 < 2bP(s) < 4,

что влечет неравенство

1 - log2Р(з) <Ь<2- log2Р(з). (1.1)

Когда s растет, ее вероятность уменьшается, а число — log2P(s) становится большим положительным числом. Двойное неравенство (1.1) показывает, что в пределе b стремится к — log2P(s). Вот почему арифметическое кодирование может, в принципе, сжимать строку до ее теоретического предела.