Оценка вероятности ухода

На долю символов ухода обычно приходится порядка 30% и более от всех оценок, вычисляемых моделировщиком РРМ. Это определило при­стальное внимание к проблеме оценки вероятности символов с нулевой час­тотой. Львиная доля публикаций, посвященных РРМ, прямо касаются оцен­ки вероятности ухода (ОВУ).

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

Априорные методы

Введем обозначения:

С - общее число просмотров контекста, т. е. сколько раз он встретился в обработанном блоке данных;

S - количество разных символов в контексте;

Sr^ - количество таких разных символов, что они встречались в контек­сте ровно / раз;

£**' - значение ОВУ по методу х.

Изобретатели алгоритма РРМ предложили два метода ОВУ: так назы­ваемые метод А и метод В. Использующие их алгоритмы РРМ были назва­ны РРМА и РРМВ соответственно.

В дальнейшем было описано еще 5 априорных подходов к ОВУ: методы С, D, Р, X и ХС [8, 10, 17]. По аналогии с РРМА и РРМВ алгоритмы РРМ, применяющие методы С и D, получили названия РРМС и PPMD соответст­венно.

Идея методов и их сравнение представлены в табл. 4.4 и табл. 4.5.

Таблица 4.4

Метод

Еи) =

А

1

С + 1

В

s-s(1> с

С

s

C + S

D .

S 1С

Р

~с~~~сг+~сг

X

5(,)

с

ХС

•

с(1)

—, при 0 < 5(1) < С С >

£(С), в противном случае

Кстати, в примере 2 был использован метод А, а в компрессоре Dummy -метод С.

При реализации метода В воздерживаются от оценки символов до тех пор, пока они не появятся в текущем контексте более одного раза. Это дос­тигается за счет вычитания единицы из счетчиков. Методы Р, X, ХС бази­руются на предположении о том, что вероятность появления в обрабаты­ваемых данных символа s, подчиняется закону Пуассона с параметром А,. , ,

Таблица 4.5

Тип файлов

Точность предсказания

Лучше

-»

Хуже

Тексты

ХС

D

Р

X

с

В

А

Двоичные файлы

С

X

Р

ХС

D

В

А

Места в табл. 4.5 очень условны. Так, например, при сжатии текстов ме­тоды ХС, D, Р, X показывают весьма близкие результаты и многое зависит от порядка модели и используемых для сравнения файлов. В большинстве случаев существенным является только отставание точности ОВУ по спосо­бам А и В от других методов.

cSiv Упражнение. Выполните действия, описанные в примере 2, используя ОВУ по методу С. Если текущий символ "6", то точность его предсказания улучшится, останется неизменной или ухудшится?

Адаптивные методы

Чтобы улучшить оценку вероятности ухода, необходимо иметь такую модель оценки, которая бы адаптировалась к обрабатываемым данным. По­добный адаптивный механизм получил название Secondary Escape Estimation (SEE), т. е. дополнительной оценки ухода или вторичной оценки ухода. Метод заключается в тривиальном вычислении вероятности ухода из текущей КМ через частоту появления новых символов (или, что то же, сим­волов ухода) в контекстных моделях со схожими характеристиками:

где flesc) - число наблюдавшихся уходов из контекстных моделей типа /'; л, - число просмотров контекстных моделей типа i.

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

Метод Z

Одна из самых ранних попыток реализации SEE известна как метод Z, а использующая его разновидность алгоритма РРМ - PPMZ [3]. Для точно­сти описания этой техники SEE объект "контекст" ниже будет также имено­ваться "РРМ-контекстом".

Для нахождения ОВУ строятся так называемые контексты ухода (escape contexts) (КУ), формируемые из четырех полей. В полях КУ содержится ин­формация о значениях следующих величин: последние 4 символа РРМ-контекста, порядок РРМ-контекста, количество уходов и количество успеш­ных оценок в соответствующей КМ. Нескольким КМ может соответство­вать один КУ.

Информация о фактическом количестве уходов и успешных кодирова­ний во всех контекстных моделях, имеющих общий КУ, запоминается в счетчиках контекстной модели уходов КМУ, построенной для данного КУ. Эта информация определяет ОВУ для текущей КМ. ОВУ находится путем взвешивания оценок, которые дают три КМУ (КМУ порядка 2, I и 0), отве­чающие характеристикам текущей КМ.

КУ порядка 2 наиболее точно соответствует текущей КМ, контексты ухода порядком ниже формируются главным образом путем выбрасывания части информации из полей КУ порядка 2. Компоненты КУ порядка 2 опре­деляются в соответствии с табл. 4.6 [3].

Таблица 4.6

Номер

поля

Размер,

бит

Способ формирования значения поля

Параметр и его значения

Значение поля

I

2

Порядок КМ

Порядок КМ/2 (с округлени­ем до младшего)

2

2

Количество уходов из КМ

I

0

2

1

3

2

>3

3

3

3

Количество успешных оценок в КМ

0

0

I

1

2

2

3,4

3

5,6

4

7,8,9

5

10,11,12

6

>12

7

4

9

Х| = 7 младших бит по­следнего (только что обра­ботанного) символа РРМ-контекста;

Xj = шестой и пятый биты предпоследнего символа; т. е., если расписать байт как совокупность 8 бит хХХххххх, то это биты XX

((Х2&0х60)« 2) | X,

В состав КУ всех порядков входят поля 1, 2, 3. Для КУ порядка 1 поле 4 состоит из 8 бит и строится из шестых и пятых битов последних четырех обработанных символов. У КУ порядка 0 четвертое поле отсутствует. Оче­видно, что алгоритм построения поля 4 для КУ порядков 1 и 2 призван улучшить предсказание ухода для текстов на английском языке в кодировке ASCII. Аналогичный прием, хотя и в не столь явном виде, используется в адаптивных методах ОВУ SEE-dl и SEE-d2, рассмотренных ниже.

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

После ОВУ выполняется поиск текущего символа среди имеющихся в КМ. По результатам поиска (символ найден или нет) обновляются счетчики соответствующих трех КМУ порядка 0,1 и 2.

Методы SEE-dI и SEE-D2

Современным адаптивным методом является подход, предложенный Шкариным и успешно применяемый в компрессорах PPMd и PPMonstr [1]. При каждой оценке используется КУ только какого-то одного типа (в мето­де Z их 3), но в зависимости от требований, предъявляемых к компрессору, автор предлагает применять один из двух методов. Назовем первый метод SEE-dl, а второй - SEE-d2.

Метод SEE-dl используется в компрессоре PPMd и ориентирован на хо­рошую точность оценки при небольших вычислительных затратах. Рас­смотрим его подробно.

Все КМ разобьем на 3 типа:

■ детерминированные (или бинарные), содержащие только один символ; назовем их контекстными моделями типа d;

■ с незамаскированными символами, т. е. ни один из символов, имеющих­ся в данной КМ, не встречался в КМ больших порядков; обычно это КМ

максимального порядка или КМ, с которой началась оценка; назовем их контекстными моделями типа nm; ■ с замаскированными символами; назовем их контекстными моделями типа т.

Как показали эксперименты, вероятность ухода из КМ разных типов коррелирует с разными характеристиками.

Случай КМ типа d является наиболее простым, так как у такой модели малое число степеней свободы. Естественно, наибольшее влияние на веро­ятность ухода оказывает счетчик частоты единственного символа.

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

1. Счетчик частоты символа квантуется до 128 значений.

2. Существует сильная взаимосвязь между родительскими и дочерними КМ, поэтому число символов в родительской КМ квантуется до четырех значений.

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

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

5. Кроме чередования блоков хорошо и плохо предсказуемых символов, часто встречаются длинные блоки очень хорошо предсказуемых данных. Это обычно бывает в случае множественных повторов длинных строк в сжимаемом потоке. Часто РРМ-модели небольших порядков плохо рабо­тают в таких ситуациях. Введем 1-битовый флаг, свидетельствующий о нахождении в таком блоке. Флаг принимает значение 1, если при обра­ботке предыдущих символов ни разу не происходил уход и оценки веро­ятности превышали 0.5 для L или большего количества этих символов. L обычно равно порядку РРМ-модели.

6. Возможность ухода зависит от единственного символа КМ типа d. Пусть соответствующий флаг равен нулю, если 2 старших бита символа нуле­вые, и единице в остальных случаях.

Таким образом, всего возможно 128-4-2-2-2-2 = 8192 контекста ухода для КМ типа d.

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

р^\о) = р'(1-р),

где p(s* | о) - вероятность появления символа 5, в заданной КМ(о) после серии из к иных символов.

3)1 Иначе говоря, p(sf \ о) - вероятность успеха в первый раз после ровно к ис­пытаний по схеме Бернулли при вероятности успеха (1 - р).

Параметр р геометрического распределения может быть найден через оценку для соответствующей КМ типа d. Получив р, можно оценить частоту счетчика числа уходов. Это делается только для КМ, содержащих 1 символ, при добавлении нового символа, т. е. когда КМ перестает быть детермини­рованной. Далее значение счетчика символа ухода изменяется только при добавлении в КМ новых символов. Величина инкремента 8 счетчика равна

1/2, при 4S(o)<S(o-k)

. 1/4, при 2S(o)<S(o-k) ,

О, для всех прочих случаев

где S(o) - число символов в модифицируемой КМ(о); S(o-k) - число симво­лов в КМ(о-£), в которой реально был оценен текущий символ.

Если новому символу соответствует небольшая вероятность, то 5 увели­чивается на l-f°(si\o), где /°(5(|о) есть наследуемая частота нового символа Si (см. подразд. "Наследование информации" в подразд. "Повыше­ние точности оценок в контекстных моделях высоких порядков").

Вероятность ухода из КМ типа m больше всего зависит от суммы значе­ний всех счетчиков. Но эта сумма должна представляться достаточно точно, что приведет к большому количеству используемых КМУ и, как следствие, к недостатку статистики в каждой КМУ. Поэтому будем моделировать не вероятность ухода, а величину счетчика символа ухода, которая слабо зави­сит от суммы частот. Поля КУ формируются следующим образом: 1. Имеется сильная взаимосвязь между частотой уходов и числом незамас­кированных символов; произведем квантование этого числа до 25 значе­ний.

2. Результат сравнения числа незамаскированных символов S(o)-S(p+l) в КМ(о) с числом символов S(o+1) в дочерней КМ(о+1) запишем в виде 1-битового флага.

3. Аналогично полю 2 введем флаг результата сравнения числа незамаски­рованных символов S(o)-S(o+l) с числом символов 5(о-1) - S(o), кото­рые останутся незамаскированными в родительской КМ(о-1), если те­кущая КМ(о) не сможет оценить обрабатываемый символ.

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

5. Существует статистическая взаимосвязь между частотой уходов и сред­ней частотой символов в КМ, включая символ ухода, где Яр)

есть сумма значений всех счетчиков текущей КМ(о).

Всего может использоваться до 25-2-2-2-2 = 400 контекстов ухода для КМ типа т.

Метод SEE-d2, используемый в компрессоре PPMonstr, отличается от SEE-dl следующим образом:

1) добавлено 4 поля в КУ для КМ типа d;

2) добавлено 2 поля в КУ для КМ типа т;

3) для КМ типа nm используется адаптивная оценка.

Данная модификация позволяет улучшить сжатие на 0.5-1%, но вычис­ление значений дополнительных полей существенно замедляет работу ком­прессора.

Как SEE-d2, так и SEE-dl обычно эффективнее SEE по методу Z с точки зрения точности оценок и вычислительной сложности.

Пример реализации адаптивной ОВУ

Заменим в нашем компрессоре Dummy априорный метод ОВУ на адап­тивный. С целью максимального упрощения контекст ухода будем форми­ровать на основании только частоты появления контекста TotFr.

Рассмотрим, как изменится программа. Для подсчета числа успешных кодирований и числа уходов создадим структуры данных:

struct SEE_item { //счетчики для контекста ухода

int e, s; }; int TF2Index [MAX_TotFr+l]; //таблица квантования TotFr

SEE item *SEE;

Алгоритм квантования TotFr описывается следующим образом:

Значение TotFr

Номер КУ

1

1

2...3

2

4...7

3

8...15

4


Иначе говоря, по мере роста TotFr диапазон возможных значений TotFr группы КМ, относимых к одному и тому же КУ, в 2 раза больше предыду­щего. Если MAX_TotFr = 0x3fff, то всего может использоваться до 14 КУ. Изменим соответствующим образом функцию initmodel.

void init_model (void){

... // ранее описанные действия по инициализации

int ind

i - 1, size = 1; do{

int j = 0;

do{

TF2Index [i+j] =

)while (++j < size)

i +« j;

size «= 1;

ind++; )while ((i + size) <= for (; i <= MAXJTotFr;

TF2Index [i] = ind; /*на всякий случай отнесем

с номером 0 */

TF2Index [0] = 0;

SEE = (SEE_item*) new SEE_item[ind+l]; //проинициализируем счетчики КМУ for (i = 0; i <= ind; i++) {

SEEti].e = 0;

//это предотвратит деление на 0, хотя и сместит оценку

SEEti].s = 1; } }

Функция encodesym примет такой вид (изменения выделены жирным

шрифтом):

//номер КУ //значение TotFr //размер диапазона

ind;

MAX_TotFr)

КМ с TotFr = 0 к КУ

О,


int encode_sym (ContextModel *CM, int с){ int esc; stack [SP++] = CM;

SEE_item *E ;

E = calc_SEE (CM, Јesc); //находим адаптивную ОВУ

if (CM->count[c]){

int CumFreqUnder = 0;

for (int i = 0; i < c; i++)

CumFreqUnder += CM->count[i]; AC.encode (CumFreqUnder, CM->count[c],

CM->TotFr + esc); /* увеличиваем счетчик успешных кодирований для

текущего КУ */

Е->8++; return 1; }else{

if (CM->esc){

AC.encode (CM->TotFr, esc, CM->TotFr + esc);

//увеличиваем счетчик уходов для текущего КУ

Е->е++;

>

return 0;

} }

В функции декодирования символа decodesym произведем аналогич­ные изменения.

int decode_sym (ContextModel *CM, int *c) { stack [SP++] = CM; if (!CM->esc) return 0; int esc; SEE_item *E = calc_SEE (CM, fiesc) ;

int cum_freq = AC.get_freq (CM->TotFr + esc); if (cum_freq < CM->TotFr){ int CumFreqUnder = 0; int i = 0; for (;;){

if ( (CumFreqUnder + CM->count[i]) <= cum_freq)

CumFreqUnder += CM->count[i]; else break; i++;

)

AC.decode update (CumFreqUnder, CM->count[i],


Методы сжатия данных

CM->TotFr + esc); *с = i; E->s++; return 1; )else{

AC.decode_update (CM->TotFr, esc,

CM->TotFr + esc); E->e++; return 0; > }

Зависимость между требуемым значением счетчика уходов, с одной сто­роны, и количеством уходов и успешных кодирований, с другой стороны, имеет вид

esc _ e

TotFr + esc e+s'

откуда

esc = - • TotFr. s

Поэтому функцию calcSEE, в которой собственно и осуществляется

адаптивная ОВУ, реализуем так:

const int SEEJTHRESHl = 10; const int SEE_THRESH2 = 0x7ff;

SEE_item* calc_SEE (ContextModel* CM, int *esc){ SEE_item* E = SSEE[TF2Index[CM->TotFr]]; if ((E->e + E->s) > SEEJTHRESHl){

*esc = E->e * CM->TotFr / E->s; //адаптивная оценка if (! (*esc)) *esc = 1; if ( (E->e + E->s) > SEE_THRESH2){ E->e -= E->e » 1; E->s -= E->s >> 1; } }

else *esc = CM->esc; //априорная оценка return E; }

Константа SEETHRESH1 определяет порог частоты использования КУ, ниже которого предпочтительнее все же применение априорного метода оценки, так как не набралось еще значительного объема статистики для те­кущего КУ. Константа SEETHRESH2 налагает ограничение на значения счетчиков успешных кодирований s и ухода е чтобы, с одной стороны, пре­дотвратить переполнение при умножении Е->е * CM->TotFr, а с другой -улучшить адаптацию к локальным изменениям характеристик сжимаемого потока.

Предложенная реализация вычисления средней частоты уходов крайне неэкономна. Так, например, можно избежать умножения на CM->TotFr, так как обычно в пределах группы КМ, относимых к одному КУ, эта величина изменяется не сильно, поэтому имеет смысл заложить неявное умножение на соответствующую константу в сам алгоритм изменения счетчиков ens. Практичная реализация адаптивной оценки среднего изложена в [1].

Также необходимо следить за величиной esc, поскольку достаточно большая сумма CM->TotFr + esc может привести к переполнению в арифме­тическом кодере. Мы не делали соответствующих проверок лишь с целью упрощения описания.

Упражнение. Добавление адаптивного метода ОВУ требует изменения действий по кодированию знака конца файла. Предложите вариант такой модификации.

Если сравнивать с помощью CalgCC, то применение описанного метода адаптивной ОВУ улучшает сжатие всего лишь приблизительно на 0.3%. Не­большой эффект объясняется не только простым механизмом вычисления ОВУ, но и малым порядком используемой модели.

Заключение. Даже сложные адаптивные методы ОВУ улучшают сжатие обычно лишь на 1-2% по сравнению с априорными методами, но требуют существенных вычислительных затрат.

  • 295 просмотров