Обновление счетчиков символов

Модификация счетчиков после обработки очередного символа может быть реализована по-разному. После кодирования каждого символа естест­венно изменять соответствующие счетчики во всех КМ порядков 0,l,...,N, что и предлагается, в частности, делать в алгоритмах РРМА и РРМВ. Такой подход называется полным обновлением (full updates). Но в случае класси­ческого, не использующего наследование информации РРМ лучшие резуль­таты достигаются, когда счетчики оцененного символа увеличиваются только в КМ порядков о, о+1, ..., N, где о - порядок КМ, в которой символ был закодирован. Иначе говоря, счетчик обработанного символа не увели­чивается в какой-то активной КМ, если он был оценен в КМ более высокого порядка. Эта техника имеет самостоятельное название- исключение при обновлении (update exclusion).

Термин "исключение при обновлении" не следует путать с исключением (exclusion), под которым понимают сам механизм уходов с маскированием счетчиков тех символов, которые встречались в контекстах большего по­рядка.

Применение исключения при обновлении позволяет улучшить сжатие обычного РРМ-компрессора примерно на 1-2% по сравнению с тем случа­ем, когда производится обновление счетчиков символа во всех КМ. Одно­временно ускоряется работа компрессора. В случае применения наследова­ния информации, а также для алгоритма РРМ* (описание РРМ* приведено ниже) польза от исключения при обновлении не столь очевидна.

Роль контекстов-предков сравнительно небольших порядков значитель­но возрастает при использовании техники наследования информации, по­этому необходимо более быстрое обновление их статистики. Как показыва­ют эксперименты, полное обновление работает все же плохо и в этом слу­чае. Поэтому обычно следует использовать решение, промежуточное между исключением при обновлении и полным обновлением. Например, помимо увеличения с весом 1 в рамках реализации исключения при обновлении, имеет смысл инкрементировать с весом 1/(о-/'+1) счетчики символа в кон­текстных моделях меньших порядков /. Под КМ(<) понимаются предки той КМ(о), в которой символ был оценен. Например, в компрессоре PPMd дела­ется модификация счетчика с весом 1/2 только в родительской КМ и только в определенных случаях. При этом основное условие выполнения такой мо­дификации требует, чтобы счетчик оцененного символа в КМ(о) был мень­ше некоторого порога.

В алгоритме РРМ* применяется частичное исключение при обновлении (partial update exclusion). В этом случае производится увеличение счетчиков во всех так называемых детерминированных КМ, а если же их нет, то толь­ко в недетерминированной КМ с самым большим порядком. Под детерми­нированной понимается такая КМ, что в соответствующем ей контексте до данного момента встречался только один символ (любое число раз). Анало­гично такой контекст называется детерминированным.

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

Использование в качестве шага прироста счетчиков величин, больших единицы, необходимо для успешной работы сложных методов обновления, а также способствует лучшей адаптации модели при масштабировании. В качестве добавки веса 1 хорошо работают 4 или 8, при этом все еще от­сутствует проблема переполнения даже при использовании для счетчиков 16-битовых машинных слов. Например, если шаг прироста равен четырем, то счетчик символа может принимать значения: 4 (инициализация при пер­вом появлении символа в контексте), 8, 12, 16... В компрессоре Dummy ис­пользуется единичный шаг прироста.