Повышение точности оценок в контекстных моделях высоких порядков

Наряду с задачей оценки вероятности ухода серьезной проблемой РРМ является недостаточный объем статистики в КМ высоких порядков, что приводит к большим погрешностям оценок. Как побочный результат имеет­ся неприятная зависимость порядка обычной РРМ-модели, обеспечивающе­го наилучшее сжатие, от вида данных. Как правило, оптимальный порядок обычной модели колеблется от 0 до 16 (для текстов в районе 4-6), кроме то­го, часто существуют значительные локальные изменения внутри файла. Например, на рис. 4.3 приведен типичный для классического РРМ-алгрритма график зависимости степени сжатия текста от порядка модели. Видно, что максимум достигается при N = 4...5, после чего наблюдается плавное падение степени сжатия.

155

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

4

ос 3.5

х

я 3

л 2.5

z

§ ^{2 5} 1.5

1

012345678 Порядок

Рис. 4.3. Зависимость степени сжатия от порядка модели для классического РРМ-алгоритма

Можно выделить два подхода к решению проблемы:

■ выбор порядка модели, обеспечивающего наилучшее сжатие, при оцени­вании каждого символа;

■ использование статистики контекстов-предков.

Выбор локального порядка модели

Механизм выбора порядка модели для кодирования каждого символа получил название Local Order Estimation (LOE) - оценки локального поряд­ка. Схемы LOE носят чисто эвристический характер и заключаются в том, что мы задаем некую функцию "доверия" и пробуем предсказать с ее помо­щью эффективность кодирования текущего символа в той или иной доступ­ной - соответствующей активному контексту и физически существующей -КМ порядка от 0 до заданного N. Можно выделить 3 типа схем LOE:

1) ищем оптимальный порядок сверху вниз от КМ максимального по­рядка N к КМ минимального порядка; прекращаем поиск, как только КМ меньшего порядка кажется нам более "подозрительной", чем те­кущая, которую и используем для оценки вероятности символа;

2) поиск снизу вверх;

3) оценка всех доступных КМ.

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

Выбор той или иной функции доверия зависит от особенностей конкрет­ной реализации РРМ, характеристик данных, для сжатия которых разраба­тывается компрессор, и, как нередко бывает, личных пристрастий разработ­чика. Как показал опыт, различные "наивные" энтропийные оценки надеж­ности КМ работают плохо. Эти оценки основываются на сравнении средней длины кодов для текущей КМ(о) и родительской KM(o-l). Неудача объяс­няется, видимо, тем, что в силу чистой случайности функция распределения в КМ(о) может быть более плоской, чем в следующей рассматриваемой KM(o-l). Поэтому для получения правдоподобной оценки надо сравнивать среднюю длину кодов для всех дочерних контекстных моделей текущей КМ(о) со средней длиной кодов для всех дочерних контекстных моделей родительской КМ(о-1).

В [3] был предложен эффективный и простой метод, дающий оценку на­дежности КМ исходя из оценки вероятности Q наиболее вероятного в КМ символа (Most Probable Symbol's Probability, MPS-P) и количества уходов Е из КМ. Обобщенно формулу можно записать так:

aQlo_e2Q + bE(log₂E-c) + d(l-Q)Qog₂E-c), (4.1)

где константы а, Ь, с, d подбираются эмпирическим путем.

Критерием выбора КМ является минимальное значение выражения (4.1) среди всех доступных КМ.

К счастью, оценка только по Q дает хорошие результаты уже в том слу­чае, когда просто выбираем КМ с максимальным Q (соответствует варианту обобщенной формулы при b = d = 0).

Можно дать следующий пример, демонстрирующий недостатки "наив­ного" энтропийного подхода и подхода MPS-P. Пусть мы кодируем с помо­щью РРМ-моделирования порядка 2 последовательность алфавита {"О", "1"}, порожденную источником с такими вероятностями генерации симво­лов:

/>(0|00) = 0,/>(1|00)=1, />(0|10)=р(1|10) = 0.5.

Пусть появление строк "00" и "10" равновероятно. Если уже обработан большой блок входной последовательности и контекст текущего символа равен "10", то в соответствии с заданным описанием источника в КМ(2) оценки вероятностей

<КО|10) = <7(1|10) = 0.5, а в КМ(1) оценки составляют

q(0\0) = 0.25, ?(1|0) = 0.75.

Средняя длина кодов для КМ(2) равна

-*(0|10)tog₂₉(0|10)-tfl|IO)log₂rfl|10),

что составляет 1 бит. В то же время средняя длина для КМ(1) равна -?(0|0)1о₈₁?(0|0)-*(1|0)1о«₃*(1|0),

что соответствует примерно 0.8 бита. Поэтому, если пользуемся "наивным" энтропийным критерием, то мы должны выбрать для кодирования КМ(1). Критерий MPS-P также указывает на КМ(1). Этот выбор ошибочен. Дейст­вительно, если мы кодируем в КМ(2), то символы "О" и "1" требуют по -log₂ 0.5 = 1 биту. Если в КМ(1), то для кодирования "0" нужно —log2 0.25 = = 2 бита, а для "1" требуется -log₂ 0.75 ~ 0.4 бита. В соответствии с приня­тым описанием источника вероятности появления "0" и "1" после строки "10" одинаковы, поэтому при каждом оценивании на основании статистики для контекста "0" вместо статистики для контекста "10" мы будем терять в среднем 0.5(2-1) + 0.5(0.4-1) = 0.2 бита.

Добавим, что известные варианты реализации подхода LOE плохо соче­таются в смысле улучшения сжатия с механизмом наследованием информа­ции, так как эти техники эксплуатируют примерно одинаковые недостатки классического алгоритма РРМ.

Наследование информации

Метод наследования информации позволяет существенно улучшить точ­ность оценок. На конец 2001 г. имеется по крайней мере одна очень эффек­тивная реализация РРМ, обеспечивающая высокую степень сжатия типовых данных, в особенности текстов, в первую очередь из-за применения насле­дования информации [1].

Метод наследования информации, предложенный Шкариным в [1], бо­рется с неточностью оценок символов в КМ больших порядков и основан на очень простой идее. Логично предположить, что распределения частот сим­волов в родительских и дочерних КМ похожи. Тогда при появлении в до­черней КМ(о) нового символа s,- целесообразно инициализировать его счет­чик ,Д.ф) некоторой величиной /°(j, | о), зависящей от информации о дан­ном символе в родительской КМ (или нескольких контекстных моделях-предках). Пусть в результате серии уходов мы спустились с КМ(о) на КМ(о-&), где символ и был успешно оценен. Тогда начальное значение счетчика символа в КМ(о) разумно вычислять, исходя из равенства

/°(^\о)_ f(s_t\o-k) _(42y

f(o) f(₀-k) + F.__u' ^l j

где f\s_t \o)~ наследуемая частота;/(о) - сумма частот всех символов

КМ(о), включая символ ухода; /v*,₀- сумма частот всех символов, реально встреченных в контекстах порядков о-к+ \...о.

К-^= Z \Дт)-Ае*с\т)-%Г(_5/\т)

где J[esc\m) - частота для символа ухода в KM(m); S(m) - количество симво­лов в КМ(т), не включая символ ухода.

сЭч Упражнение. Объясните смысл слагаемого F^₀ в выражении (4.2).

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

Г0|_О)=_____ /(»>•/<'>-*>____ .

f(p)-sio) + f(o-k)-f(s,\o-k)

При самой простой реализации величина f°(s, \ о) вычисляется и при­сваивается сразу при создании нового счетчика в КМ(о). Но можно отло­жить наследование частоты до следующего появления символа 5, в этом контексте порядка о. Вероятнее всего, к тому времени родительская КМ бу­дет обладать большим объемом статистики, что должно дать более точную оценку f°(s, | о) и в конечном итоге улучшить сжатие. Такое "отложенное" наследование требует повторного поиска родительской КМ и символа Si в ней, что может существенно замедлить обработку.

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

Заключение. Существующие реализации компрессоров, использующих механизм наследования информации, обеспечивают лучшее сжатие, чем компрессоры с LOE.