1.7.3. Заключительные замечанияВо всех приведенных примерах мы использовали десятичную систему исчисления для лучшего понимания арифметического метода сжатия. Оказывается, что все эти алгоритмы и правила применимы и к двоичному представлению чисел с одним изменением: каждое появление цифры 9 надо заменить цифрой 1 (наибольшей двоичной цифрой). Может показаться, что приведенные выше примеры не производят никакого сжатия, и во всех трех рассмотренных примерах строки «SWISS_MISS», « Для того, чтобы выяснить степень компрессии, достигаемую с помощью арифметического сжатия, необходимо рассмотреть два факта: (1) на практике все операции совершаются над двоичными числами, поэтому следует переводить все результаты в двоичную форму перед тем, как оценивать эффективность компрессии; (2) поскольку последним кодируемым символом является eof, окончательный код может быть любым числом между Low и High. Это позволяет выбрать более короткое число для окончательного сжатого кода. Табл. 1.25 кодирует строку «SWISS_MISS» некоторым числом в интервале от Ответ будет «да». Используя вероятности из табл. 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). Начинаем с интервала Вероятность этой строки равна Следующее рассуждение показывает, почему арифметическое кодирование может быть весьма эффективным методом сжатия. Обозначим через
что влечет неравенство
Когда
|