Масштабирование счетчика последнего встреченного символа

Если в последний раз в текущем контексте был встречен некий символ s, то вероятность того, что и текущий символ также s, вырастает, причем час­то значительно. Этот факт позволяет улучшить предсказание за счет умно­жения счетчика последнего встреченного символа (ПВС) на некий.коэффи­циент. Судя по всему, впервые такая техника описана в [15], где она назы­вается recency scaling" - масштабированием новизны.

Техника была исследована М. А. Смирновым при разработке компрессо­ра PPMN. По состоянию на 2001 г. неизвестны другие программы сжатия, использующие recency scaling.

В большинстве случаев хорошо работает множитель 1.1-1.2, т. е. при та­ком значении наблюдается улучшение сжатия большинства файлов и мало­вероятно ухудшение сжатия какого-то "привередливого" файла. Но часто оптимальная величина,масштабирующего коэффициента колеблется в рай­оне 2-2.5, так что можно улучшить оценку за счет адаптивного изменения множителя. Подходящее значение выбирается на основе анализа сжимае­мых данных с помощью эмпирически полученных формул. Исследования показали, что величина наблюдаемой частоты совпадения последнего встреченного и текущего символов в недетерминированных контекстах по­зволяет подбирать коэффициент с хорошей точностью.

Для повышения точности оценки также следует учитывать расстояние между текущей позицией и моментом последней встречи текущего контек­ста. Если расстояние больше 5000 символов, то скорее всего масштабирова­ние счетчика ПВС только повредит. Но следует понимать, что учет этой ха­рактеристики требует существенных затрат памяти.

Рассмотрим реализацию простейшего алгоритма recency scaling на при­мере нашего компрессора Dummy.

В описание структуры КМ внесем поле last, описывающее ПВС для за­данного контекста.

struct ContextModel{ int esc,

TotFr,

last; int count[256];

};

Значение last будем вычислять как сумму номера символа и 1, для того чтобы нулевое значение last указывало на отсутствие необходимости выподнять масштабирование. В начале работы программы last будет равно ну­лю, так как cm является глобальной переменной.

В начало функций encodesym и decodesym добавим действия по ум­ножению счетчика ПВС на постоянный коэффициент 1.25.

int addition; if (CM->last) {

addition = CM->count [CM->last-l]»2;

CM->count[CM->last-l] += addition;

CM->TotFr += addition; }

Кроме того добавим сразу же после вызова методов AC.encode и AC.decodeupdate условные операторы, исправляющие значения счетчиков на первоначальные.

if (CM->last){

CM->count[CM->last-l] -= addition;

CM->TotFr -= addition; }

И, наконец, обеспечим правильное обновление last в функции updatemodel.

if (!stack[SP]->count[c])

stack [SP]->esc +«= 1; else stack[SP]->last = c+1;

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

Описанная модификация компрессора позволяет улучшить степень сжа­тия CalgCC примерно на 0.5%. Но оптимальная величина коэффициента масштабирования существенно меняется от файла к файлу. Так, например, для файла Obj2 максимальное улучшение сжатия - на 6% - было отмечено при коэффициенте 4.

Вывод. Масштабирование счетчика последнего встреченного символа (recency scaling) позволяет улучшить сжатие в среднем лишь на 0.5-1%, но может дать существенный выигрыш при обработке данных, статистические характеристики которых подвержены частым изменениям.

Масштабирование в детерминированных контекстах

Известно, что методы ОВУ А, В, С и, в меньшей степени, другие рас­смотренные априорные методы назначают завышенную вероятность ухода из детерминированных контекстов [15]. Это можно исправить, умножая счетчик единственного символа на определенный коэффициент. Такой при­ем был впервые описан в [15] под наименованием "deterministic scaling" -"детерминистического масштабирования". Нетрудно заметить, что этот м< ханизм есть частный случай recency scaling.

Эффект от deterministic scaling увеличивается, если при этом используем­ся частичное исключение при обновлении, а не обычное исключение пгя. обновлении [15].

Deterministic scaling имеет смысл применять только в сочетании с апри­орными методами ОВУ, ведь чем точнее вычисляется вероятность уход,. тем пользы от этого масштабирования меньше.

Увеличение точности предсказания наиболее вероятных символов

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

В этих случаях естественным является учет информации родительской КМ, что можно рассматривать как переход от неявного взвешивания к яв­ному.

Под НбВС будем здесь понимать символы с оценками вероятностей p(Sj\o) >p(s_mps\o)/2, где p(s_mps\o) соответствует самому вероятному символу (most probable symbol) $„,,, в текущей КМ. Частоты НбВС будем корректи­ровать, если До) < До-1). В этих случаях КМ(о) "молода" и частота Ду,|о) символа Si еще, как правило, меньше частоты Ду,|о-1). Уточненное значение .£коррСФ) счетчика представляет собой среднее взвешенное Дф) и "приведенной" частоты /'($, | о-1):

f (- I о) - №' К* 1^{0) +} Н° ~^Х) • М⁵>' ° ~^1}
/с"*^Л'^{1 }} До)+До-1)

где_Л*>-1) = /(,,|о-1)- /<°>-Л'»

До -1)- Д₅,\ о-1)

В случае использования наследуемых частот аналогичную коррекцию имеет смысл применять при наследовании.

Очевидно, что степень сжатия сильно зависит от точности предсказания НбВС, поэтому после выполнения коррекции частоты целесообразно делать адаптивную оценку вероятности символа по аналогии с SEE. Назовем такую технику Secondary Symbol Estimation (SSE) - вторичной оценкой символа. В компрессоре PPMonstr версии Н вторичная оценка выполняется для КМ с замаскированными символами (КМ типа т) и недетерминированных КМ с незамаскированными символами (КМ типа nm). Поля контекстов для SSE строятся следующим образом.

Для КМ типа nm:

1) частота J(s_mps\o) самого вероятного символа, квантуемая до 68 значе­ний;

2) 1-битовый флаг, указывающий, что было произведено масштабиро­вание счетчиков контекстной модели;

3) 1-битовый флаг, хранящий результат сравнения порядка о текущей КМ со средним порядком контекстных моделей, в которых были за­кодированы последние 128 символов;

4) 1-битовый флаг, принимающий значение 0, если 2 старших бита пре­дыдущего обработанного символа нулевые, и значение 1 в прочих случаях (аналог поля 4 контекста ухода для КМ типа d в SEE-dl);

5) 1-битовый флаг, равный нулю, если 2 старших бита символа s^,, ну­левые, и единице в остальных случаях (аналог поля 6 КУ для КМ ти­па d в SEE-dl).

Для КМ типа т:

1) оценка вероятности p(s_mps\o), квантуемая до 40 значений;

2) 1-битовый флаг результата сравнения средней частоты замаскиро­ванных и незамаскированных символов;

3) 1-битовый флаг, указывающий, что только один символ остался не­замаскированным;

4) аналог поля 2 контекста SSE для КМ типа nm (см. предыдущий спи­сок);

5) аналог поля 4 в предыдущем списке.

Техника SSE разработана Шкариным и используется для уточнения предсказания НбВС в компрессоре PPMonstr версии Н.

Заключение. Применение SSE к НбВС дает выигрыш в районе 0.5-1% и особенно полезно при сжатии неоднородных данных, т. е. либо порожденных источником, быстро меняющим свои характеристики, либо состоящих из фраг­ментов, сгенерированных существенно отличающимися источниками.

Общий случай применения вторичной оценки символа

Естественной является идея применения SSE ко всем символам контек­ста. Действительно, этот прием обеспечивает существенное улучшение сжа­тия неоднородных данных.

Рассмотрим обобщенный алгоритм применения SSE подробнее¹. Пусть символы КМ хранятся в виде упорядоченного списка, так что символ с наи­большей частотой записан первым, т.е. имеет ранг 1. Процедура оценки очередного символа s приобретает вид цепочки последовательных оценок альтернатив "да'7"нет": "да" - символ с текущим рангом равен s, "нет" -символы различаются, необходимо увеличить ранг на единицу и продол­жить поиск. Вероятность "да" для ранга / находится как

Q_l(o) = q^SSE(s_l\o),

где q^SSE(s_l \o) - оценка вероятности символа с рангом /, полученная с по­мощью SSE после оценивания символа с рангом М; вычисляется на осно­вании обычной оценки q{s_t \ о) и значений w,{o) полей контекста для SSE:

q** (s, | о) = SSE(q{_Si | о), w, (о), w₂ (о),... w_P (о)),

Например, пусть список символов текущей КМ(о) имеет вид "в", "б", "а", "г". Если обрабатывается символ "а", то он будет оценен посредством це­почки ответов "нет", "нет", "да" и получит вероятность (1 - Q\(o))(l --Q2(o))Q₃(o).

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

Положительный эффект обеспечивает внесение в контексты для SSE флагов, указывающих на совпадение ПВС текущего контекста и контек-' стов-предков. Аналогично присваивать ПВС ранг 1 лучше только в том слу­чае, если он равен ПВС "ближайших" предков.

В табл. 4.7 приведено сравнение характеристик сжатия компрессора PPMonstr версии Н и его модификации, использующей обобщенный алго-

Алгоритм разработан и реализован Д. Шкариным в ноябре 2001 г.

ритм SSE в сочетании с адаптацией новизны. В сравнении были использо­ваны файлы из наборов CalgCC и VYCCT. Все файлы, за исключением тек­стового Bookl, содержат неоднородные бинарные данные или смесь текста и бинарных данных. Использовались модели 64-го порядка.

Таблица 4.7

Вывод. Применение SSE ко всем символам контекста в сочетании с адаптацией новизны значительно улучшает сжатие неоднородных данных. Это позволяет получать стабильно наилучшую степень сжатия по сравне­нию с другими универсальными методами (BWT, LZ) при обработке файлов самых разнообразных типов, а не только текстов. Ценой увеличения степе­ни сжатия является падение скорости в 2 и более раза.