Масштабирование счетчика последнего встреченного символа
Если в последний раз в текущем контексте был встречен некий символ 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(smps\o)/2, где p(smps\o) соответствует самому вероятному символу (most probable symbol) $„,,, в текущей КМ. Частоты НбВС будем корректировать, если До) < До-1). В этих случаях КМ(о) "молода" и частота Ду,|о) символа Si еще, как правило, меньше частоты Ду,|о-1). Уточненное значение .£коррСФ) счетчика представляет собой среднее взвешенное Дф) и "приведенной" частоты /'($, | о-1):
f (- I о) - №' К* 10)
+
Н° ~Х) • М5>' ° ~1}
/с"*Л'1
} До)+До-1)
гдеЛ*>-1) = /(,,|о-1)- /<°>-Л'»
До -1)- Д5,\ о-1)
В случае использования наследуемых частот аналогичную коррекцию имеет смысл применять при наследовании.
Очевидно, что степень сжатия сильно зависит от точности предсказания НбВС, поэтому после выполнения коррекции частоты целесообразно делать адаптивную оценку вероятности символа по аналогии с SEE. Назовем такую технику Secondary Symbol Estimation (SSE) - вторичной оценкой символа. В компрессоре PPMonstr версии Н вторичная оценка выполняется для КМ с замаскированными символами (КМ типа т) и недетерминированных КМ с незамаскированными символами (КМ типа nm). Поля контекстов для SSE строятся следующим образом.
Для КМ типа nm:
1) частота J(smps\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(smps\o), квантуемая до 40 значений;
2) 1-битовый флаг результата сравнения средней частоты замаскированных и незамаскированных символов;
3) 1-битовый флаг, указывающий, что только один символ остался незамаскированным;
4) аналог поля 2 контекста SSE для КМ типа nm (см. предыдущий список);
5) аналог поля 4 в предыдущем списке.
Техника SSE разработана Шкариным и используется для уточнения предсказания НбВС в компрессоре PPMonstr версии Н.
Заключение. Применение SSE к НбВС дает выигрыш в районе 0.5-1% и особенно полезно при сжатии неоднородных данных, т. е. либо порожденных источником, быстро меняющим свои характеристики, либо состоящих из фрагментов, сгенерированных существенно отличающимися источниками.
Общий случай применения вторичной оценки символа
Естественной является идея применения SSE ко всем символам контекста. Действительно, этот прием обеспечивает существенное улучшение сжатия неоднородных данных.
Рассмотрим обобщенный алгоритм применения SSE подробнее1. Пусть символы КМ хранятся в виде упорядоченного списка, так что символ с наибольшей частотой записан первым, т.е. имеет ранг 1. Процедура оценки очередного символа s приобретает вид цепочки последовательных оценок альтернатив "да'7"нет": "да" - символ с текущим рангом равен s, "нет" -символы различаются, необходимо увеличить ранг на единицу и продолжить поиск. Вероятность "да" для ранга / находится как
Ql(o) = qSSE(sl\o),
где qSSE(sl \o) - оценка вероятности символа с рангом /, полученная с помощью SSE после оценивания символа с рангом М; вычисляется на основании обычной оценки q{st \ о) и значений w,{o) полей контекста для SSE:
q** (s, | о) = SSE(q{Si | о), w, (о), w2 (о),... wP (о)),
Например, пусть список символов текущей КМ(о) имеет вид "в", "б", "а", "г". Если обрабатывается символ "а", то он будет оценен посредством цепочки ответов "нет", "нет", "да" и получит вероятность (1 - Q\(o))(l --Q2(o))Q3(o).
Дальнейшее улучшение сжатия обеспечивается соединением SSE с техникой recency scaling. В этом случае символом с рангом 1 считается последний встреченный в контексте символ (ПВС), если, конечно, он не замаскирован. Такая "адаптация новизны" позволяет значительно улучшить приспособляемость модели к потоку данных с меняющимися вероятностными характеристиками.
Положительный эффект обеспечивает внесение в контексты для SSE флагов, указывающих на совпадение ПВС текущего контекста и контек-' стов-предков. Аналогично присваивать ПВС ранг 1 лучше только в том случае, если он равен ПВС "ближайших" предков.
В табл. 4.7 приведено сравнение характеристик сжатия компрессора PPMonstr версии Н и его модификации, использующей обобщенный алго-
Алгоритм разработан и реализован Д. Шкариным в ноябре 2001 г.
ритм SSE в сочетании с адаптацией новизны. В сравнении были использованы файлы из наборов CalgCC и VYCCT. Все файлы, за исключением текстового Bookl, содержат неоднородные бинарные данные или смесь текста и бинарных данных. Использовались модели 64-го порядка.
Таблица 4.7
Название файла |
Размер сжатого файла, байт |
Улучшение сжатия, % |
Падение скорости сжатия, раз |
|
для версии Н |
для модификации версии Н |
|||
Bookl |
205144 |
203669 |
0.7 |
2.0 |
Fileware.doc |
112111 |
100454 |
10.4 |
2.5 |
Obj2 |
65093 |
58466 |
10.2 |
2.1 |
0S2.ini |
94218 |
83405 |
11.5 |
2.2 |
Samples.xls |
70912 |
64666 |
8.8 |
2.0 |
Wcc386.exe |
278045 |
255719 |
8.0 |
3.3 |
Вывод. Применение SSE ко всем символам контекста в сочетании с адаптацией новизны значительно улучшает сжатие неоднородных данных. Это позволяет получать стабильно наилучшую степень сжатия по сравнению с другими универсальными методами (BWT, LZ) при обработке файлов самых разнообразных типов, а не только текстов. Ценой увеличения степени сжатия является падение скорости в 2 и более раза.