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

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

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

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

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

Ответ будет «да». Используя вероятности из табл. 1.24, легко вычислить вероятность строки «SWISS_MISS». Она равна . Энтропия этой строки . Значит, двадцать бит - это минимальное число, необходимое для практического кодирования этой строки.

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

Вычисляем вероятность строки «» и получаем число , а ее энтропия будет равна .

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

Пример: Даны три символа ,  и  с вероятностями ,  и . Кодируем строку «». Размер конечного кода будет равен теоретическому минимуму.

Шаги кодирования просты (см. первый пример на стр. 63). Начинаем с интервала . Первый символ сокращает интервал до , второй - до , третий до , а четвертый eof - до . Приблизительные двоичные значения концов равны 0.1101000000 и 0.1101001100, поэтому в качестве кода выбирается 7-битовое число «1101000».

Вероятность этой строки равна , тогда число , то есть, теоретический минимум длины кода равен 7 бит. (Конец примера.)

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

,

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

.       (1.1)

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