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) показывает, что в пределе стремится к . Вот почему арифметическое кодирование может, в принципе, сжимать строку до ее теоретического предела.
|