Во всех приведенных примерах мы использовали десятичную систему исчисления для лучшего понимания арифметического метода сжатия. Оказывается, что все эти алгоритмы и правила применимы и к двоичному представлению чисел с одним изменением: каждое появление цифры 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.5⁵ х х0.1 х 0.2² х 0.1 х 0.1 = 1.25 х Ю^-6. Энтропия этой строки — log₂P = = 19.6096. Значит, двадцать бит - это минимальное число, необходимое для практического кодирования этой строки.

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

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

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

Пример: Даны три символа aj, a₂ и eof с вероятностями Pi = = 0.4, Р₂— 0.5 и P_eof = 0.1. Кодируем строку «a₂a2a2eof». Размер конечного кода будет равен теоретическому минимуму.

Шаги кодирования просты (см. первый пример на стр. 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.5³ х 0.1 = 0.0125, тогда число — log₂ 0.0125 « 6.322, то есть, теоретический минимум длины кода равен 7 бит. (Конец примера.)

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

2 < 2^bP(s) < 4,

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

1 - log₂Р(з) <Ь<2- log₂Р(з). (1.1)

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