Методы контекстного моделирования

Применение методов контекстного моделирования для сжатия данных опирается на парадигму сжатия с помощью универсального моделирования и кодирования (universal modelling and coding), предложенную Риссаненом (Rissanen) и Лэнгдоном (Langdon) в 1981 г. [12]. В соответствии с данной идеей процесс сжатия состоит из двух самостоятельных частей:

■ моделирования;

■ кодирования.

Под моделированием понимается построение модели информационного источника, породившего сжимаемые данные, а под кодированием - отобра­жение обрабатываемых данных в сжатую форму представления на основа­нии результатов моделирования (рис. 4.1). "Кодировщик" создает выход­ной поток, являющийся компактной формой представления обрабатываемой последовательности, на основании информации, поставляемой ему "моде-лировщиком".

Рис. 4.1. Схема процесса сжатия данных в соответствии с концепцией универсального моделирования и кодирования

Следует заметить, что понятие "кодирование" часто используют в широ­ком смысле для обозначения всего процесса сжатия, т. е. включая модели­рование в данном нами определении. Таким образом, необходимо различать понятие кодирования в широком смысле (весь процесс) и в узком (генера­ция потока кодов на основании информации модели). Понятие "статистиче­ское кодирование" также используется, зачастую с сомнительной коррект­ностью, для обозначения того или иного уровня кодирования. Во избежание путаницы ряд авторов применяет термин "энтропийное кодирование" для кодирования в узком смысле. Это наименование далеко от совершенства и встречает вполне обоснованную критику. Далее в этой главе процесс коди­рования в широком смысле будем именовать "кодированием", а в узком смысле - "статистическим кодированием" или "собственно кодированием".

Из теоремы Шеннона о кодировании источника [13] известно, что сим­вол s_h вероятность появления которого равняется p(s,), выгоднее всего пред­ставлять -log₂ p(si) битами, при этом средняя длина кодов может быть вы­числена по приводившейся ранее формуле (1.1 и 1.2). Практически всегда истинная структура источника скрыта, поэтому необходимо строить модель источника, которая позволила бы нам в каждой позиции входной последовательности найти оценку q(si) вероятности появления каждого символа s, алфавита входной последовательности.

Оценка вероятностей символов при моделировании производится на ос­новании известной статистики и, возможно, априорных предположений, по­этому часто говорят о задаче статистического моделирования. Можно ска­зать, что моделировщик предсказывает вероятность появления каждого символа в каждой позиции входной строки, отсюда еще одно наименование этого компонента - "предсказатель" или "предиктор" (от predictor). На этапе статистического кодирования выполняется замещение символа s_t с оценкой вероятности появления qfsj) кодом длиной -log2 q(s,) бит.

Рассмотрим пример. Предположим, что мы сжимаем последовательность символов алфавита {"0","1"}, порожденную источником без памяти, и веро­ятности генерации символов следующие: р("0") = 0.4, р("1") = 0.6. Пусть наша модель дает такие оценки вероятностей: #("0") = 0.35, <7("1") = 0.65. Энтропия Я источника равна

-p('0')loe₂p(^,0')-p(4Vog₁pCl^r) =

= -0.4 log₂ 0.4 - 0.6 log₂ 0.6 я 0.971 бита.

Если подходить формально, то "энтропия" модели получается равной -qC0^r)lo_elq('0^,)-q(T)hg₂q(4')-= -0.35 log₂ 0.35 - 0.65 log₂ 0.65 « 0.934 бита.

Казалось бы, что модель обеспечивает лучшее сжатие, чем это позволяет формула Шеннона. Но истинные вероятности появления символов не изме­нились! Если исходить из вероятностей р, то "0" следует кодировать -log₂0.4 ~ 1.322 бита, а для "1" нужно отводить -log₂0.6 ~ 0.737 бита. Для оценок вероятностей q мы имеем -log₂0.35 ~ 1.515 бита и -log₂0.65 ~ 0.621 бита соответственно. При каждом кодировании на основании информации модели в случае "0" мы будем терять 1.515 - 1.322 = 0.193 бита, а в случае "1" выигрывать 0.737 - 0.621 =0.116 бита. С учетом вероятностей появле­ния символов средний проигрыш при каждом кодировании составит 0.40.193 -0.60.116 = 0.008 бита.

Вывод. Чем точнее оценка вероятностей появления символов, тем больше коды соответствуют оптимальным, тем лучше сжатие.

Правильность декодирования обеспечивается использованием точно та­кой же модели, которая была применена при кодировании. Следовательно, при моделировании для сжатия данных нельзя пользоваться информацией, которая неизвестна декодеру.

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

Задача статистического кодирования была в целом успешно решена к началу 80-х г. Арифметический кодер позволяет сгенерировать сжатую по­следовательность, длина которой обычно всего лишь на десятые доли про­цента превышает теоретическую длину, рассчитанную с помощью формулы (1.1). Более того, применение современной модификации арифметического кодера - интервального кодера - позволяет осуществлять собственно коди­рование очень быстро. Скорость статистического кодирования составляет миллионы символов в секунду на современных ПК.

В свете вышесказанного повышение точности моделей является факти­чески единственным способом существенного улучшения сжатия.