Опрос

Какой архиватор наиболее эффективный?:

Новички

Виктор Васильев
Юрий Антонов
Сергей Андреевич
Генадий
Avanasy

Контекстное моделирование

Итак, нам необходимо решить задачу оценки вероятностей появления символов в каждой позиции обрабатываемой последовательности. Для того чтобы разжатие произошло без потерь, мы можем пользоваться только той информацией, которая в полной мере известна как кодеру, так и декодеру. Обычно это означает, что оценка вероятности очередного символа должна зависеть только от свойств уже обработанного блока данных.

Пожалуй, наиболее простой способ оценки реализуется с помощью по­луадаптивного моделирования и заключается в предварительном подсчете безусловной частоты появления символов в сжимаемом блоке. Полученное распределение вероятностей используется для статистического кодирования всех символов блока. Если, например, такую модель применить для сжатия текста на русском языке, то в среднем на кодирование каждого символа бу­дет потрачено примерно 4.5 бита. Это значение является средней длиной кодов для модели, базирующейся на использовании безусловного распределения вероятностей букв в тексте. Заметим, что уже в этом простом случае достигается степень сжатия 1.5 по отношению к тривиальному кодированию, когда всем символам назначаются коды одинаковой длины. Действительно, размер алфавита русского текста превышает 64 знака, но меньше 128 знаков (строчные и заглавные буквы, знаки препинания, пробел), что требует 7-битовых кодов.

Анализ распространенных типов данных, - например, тех же текстов на естественных языках, - выявляет сильную зависимость вероятности появ­ления символов от непосредственно им предшествующих. Иначе говоря, большая часть данных, с которыми мы сталкиваемся, порождается источни­ками с памятью. Допустим, нам известно, что сжимаемый блок является текстом на русском языке. Если, например, строка из трех только что обра­ботанных символов равна "_цы" (подчеркиванием здесь и далее обозначает­ся пробел), то текущий символ скорее всего входит в следующую группу: "г" ("цыган"), "к" ("цыкать"), "п" ("цыпочки"), "ц" ("цыц"). Или, в случае анализа фазу нескольких слов, если предыдущая строка равна "Вста-вай,_проклятьем_заклейменный,", то продолжением явно будет "весь_мир_". Следовательно, учет зависимости частоты появления символа (в общем случае - блока символов) от предыдущих должен давать более точные оценки и в конечном счете лучшее сжатие. Действительно, в случае посим­вольного кодирования при использовании информации об одном непосред­ственно предшествующем символе достигается средняя длина кодов в 3.6 бита для русских текстов, при учете двух последних - уже порядка 3.2 бита. В первом случае моделируются условные распределения вероятностей сим­волов, зависящие от значения строки из одного непосредственно предшест­вующего символа, во втором - зависящие от строки из двух предшествую­щих символов.

Любопытно, что модели, оперирующие безусловными частотами и часто­тами в зависимости от одного предшествующего символа, дают примерно оди­наковые результаты для всех европейских языков (за исключением, быть мо­жет, самых экзотических) -4.5 и 3.6 бита соответственно.

Улучшение сжатия при учете предыдущих элементов (пикселов, сэмп­лов, отсчетов, чисел) отмечается и при обработке данных других распро­страненных типов: объектных файлов, изображений, аудиозаписей, таблиц чисел.

Терминология

Под контекстным моделированием будем понимать оценку вероятности появления символа (элемента, пиксела, сэмпла, отсчета и даже набора каче­ственно разных объектов) в зависимости от непосредственно ему предшест­вующих, или контекста.

Заметим, что в быту понятие "контекст" обычно используется в глобаль­ном значении - как совокупность символов (элементов), окружающих те­кущий обрабатываемый. Это контекст в широком смысле. Выделяют также "левосторонние" и "правосторонние" контексты, т. е. последовательности символов, непосредственно примыкающих к текущему символу слева и справа соответственно. Здесь и далее под контекстом будем понимать именно классический левосторонний: так, например, для последнего симво­ла "о" последовательности "...молоко..." контекстом является "...молок".

Если длина контекста ограничена, то такой подход будем называть кон­текстным моделированием ограниченного порядка (finite-context modeling), при этом под порядком понимается максимальная длина используемых кон­текстов N. Например, при моделировании порядка 3 для последнего симво­ла "о" в последовательности "...молоко..." контекстом максимальной длины 3 является строка "лок". При сжатии этого символа под "текущими контек­стами" могут пониматься "лок", "ок", "к", а также пустая строка "". Все эти контексты длины от N до 0 назовем активными контекстами в том смысле, что при оценке символа может быть использована накопленная для них сть тистика.

Далее вместо "контекст длины о, о < N" мы будем обычно говоритг "контекст порядка о".

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

Оценки вероятностей при контекстном моделировании строятся на о» новании обычных счетчиков частот, связанных с текущим контекстом. Earn мы обработали строку "абсабвбабс",то для контекста "аб" счетчик символ*. "с" равен двум (говорят, что символ "с" появился в контексте "аб" 2 раза), символа "в" - единице. На основании этой статистики можно утверждать, что вероятность появления "с" после "аб" равна 2/3, а вероятность появле­ния "в" - 1/3, т. е. оценки формируются на основе уже просмотренной части потока.

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

Под порядком КМ будем понимать длину соответствующего ей контек­ста. Если порядок КМ равен о, то будем обозначать такую КМ как "КМ(о)".

Кроме обычных КМ, часто используют контекстную модель минус 1-го порядка КМ(-1), присваивающую одинаковую вероятность всем символам алфавита сжимаемого потока.

Понятно, что для 0-го и минус 1-го порядка контекстная модель одна, а КМ большего порядка может быть несколько, вплоть до qN, где q - размер алфавита обрабатываемой последовательности. КМ(0) и КМ(-1) всегда ак­тивны.

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

Часто говорят о "родительских" и "дочерних" контекстах. Для контекста "к" дочерними являются "ок" и "лк", поскольку они образованы сцеплением (конкатенацией) одного символа и контекста "к". Аналогично для контекста "лок" родительским является контекст "ок", а контекстами-предками - "ок", "к", "". Очевидно, что "пустой" контекст "" является предком для всех. Ана­логичные термины применяются для КМ, соответствующих контекстам.

Совокупность КМ образует модель источника данных. Под порядком модели понимается максимальный порядок используемых КМ.

ВИДЫ КОНТЕКСТНОГО МОДЕЛИРОВАНИЯ

Пример обработки строки "абсабвбабс" иллюстрирует сразу две пробле­мы контекстного моделирования:

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

■ как оценивать вероятность символов, имеющих нулевую частоту (на­пример, "г").

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

Если в модели используются для оценки только КМ(ЛО, то иногда такой подход называют "чистым" (pure) контекстным моделированием порядка N. Из-за вышеуказанного недостатка "чистые" модели представляют обычно только научный интерес.

Действительно, реально используемые файлы обычно имеют сравни­тельно небольшой размер, поэтому для улучшения их сжатия необходимо учитывать оценки вероятностей, получаемые на основании статистики кон­текстов разных длин. Техника объединения оценок вероятностей, соответ­ствующих отдельным активным контекстам, в одну оценку называется смешиванием (blending). Известно несколько способов выполнения смеши­вания.

Рассмотрим модель произвольного порядка N. Если q(si\o) есть вероят­ность, присваиваемая в активной КМ(о) символу j, алфавита сжимаемого потока, то смешанная вероятность q(si) вычисляется в общем случае как

N 0—1

где w(o) - вес оценки КМ(о).

Оценка q(Sj\o) обычно определяется через частоту символа s,- по триви­альной формуле

,, |/Л f(s,\o)

До)

rnfiJ[si\o) - частота появления символа st в соответствующем контексте по­рядка о; До) - общая частота появления соответствующего контекста поряд­ка о в обработанной последовательности.

Заметим, что правильнее было бы писать не, скажем, Ду/|о), иДз^С^), т. е. "частота появления символа S/ в КМ порядка о с номером До)", по­скольку контекстных моделей порядка о может быть огромное количество. Но при сжатии каждого текущего символа мы рассматриваем только одну КМ для каждого порядка, так как контекст определяется непосредственно примыкающей слева к символу строкой определенной длины. Иначе говоря, для каждого символа мы имеем набор из N+1 активных контекстов длины от N до 0, каждому из которых однозначно соответствует только одна КМ, если она вообще есть. Поэтому здесь и далее используется сокращенная за­пись.

Если вес w(-l) > 0, то это гарантирует успешность кодирования любого символа входного потока, так как наличие КМ(-1) позволяет всегда получать ненулевую оценку вероятности и, соответственно, код конечной длины.

Различают модели с полным смешиванием (fully blended), когда предска­зание определяется статистикой КМ всех используемых порядков, и с час­тичным смешиванием (partially blended) - в противном случае.

Пример 1

Рассмотрим процесс оценки отмеченного на рисунке стрелкой символа

"л", встретившегося в блоке "молочноемолоко". Считаем, что модель рабо­тает на уровне символов.

м

о

л

0

ч

н

о

е

м

о | л | о

к

о

Пусть мы используем контекстное моделирование порядка 2 и делаем полное смешивание оценок распределений вероятностей в КМ 2-го, 1-го и 0-го порядка с весами 0.6, 0.3 и 0.1. Считаем, что в начале кодирования в КМ(0) создаются счетчики для всех символов алфавита {"м", "о", "л", "ч", "н", "е","_", "к"} и инициализируются единицей; счетчик символа после его обработки увеличивается на единицу.

Для текущего символа "л" имеются контексты "мо", "о" и пустой (0-го порядка). К данному моменту для них накоплена статистика, показанная в табл. 4.1.

Таблица 4.1

Символы

"м"

"о"

"л"

-ч«

"н"

"е"

"к"

КМ

порядка 0 (контекст

Частоты

3

5

2

2

2

2

2

1

Накоплен­ные частоты

3

8

10

12

14

16

18

19

КМ

порядка 1 (контекст

"0")

Частоты

-

-

1

-

1

-

-

Накоплен­ные частоты

-

-

2

-

3

-

-

КМ

порядка 2 ("мо")

Частоты

-

-

-

-

-

-

-

Накоплен­ные частоты

-

-

-

-

-

-

-

Тогда оценка вероятности для символа "л" будет равна

^(*л*) = 0.1— + 0.3-- + 0.6- = 0,71.
4 19 3 1

В общем случае для однозначного кодирования символа "л" такую оцен­ку необходимо проделать для всех символов алфавита. Действительно, с одной стороны, декодер не знает, чему равен текущий символ, с другой сто­роны, оценка вероятности не гарантирует уникальности кода, а лишь задает его длину. Поэтому статистическое кодирование выполняется на основании накопленной частоты (см. подробности в примере 2 и в подразд. "Арифме­тическое сжатие" гл. 1). Например, если кодировать на основании статисти­ки только 0-го порядка, то существует взаимно-однозначное соответствие между накопленными частотами из диапазона (8,10] и символом "л", что не имеет места в случае просто частоты (частоту 2 имеют еще 4 символа). Понятно, что.аналогичные свойства остаются в силе и в случае оценок, полу­чаемых частичным смешиванием.

Упражнение. Предложите способы увеличения средней скорости вычисления

оценок для методов контекстного моделирования со смешиванием, как пол­ным, так и частичным.

Очевидно, что успех применения смешивания зависит от способа выбора весов w(o). Простой путь состоит в использовании заданного набора фиксиро­ванных весов КМ разных порядков при каждой оценке; этот способ был при­менен в примере 2. Естественно, альтернативой является адаптация весов по мере кодирования. Приспособление может заключаться в придании все боль­шей значимости КМ все больших порядков или, скажем, попытке выбрать наи­лучшие веса на основании определенных статистических характеристик по­следнего обработанного блока данных. Но так исторически сложилось, что ре­альное развитие получили методы неявного взвешивания. Это объясняется в первую очередь их меньшей вычислительной сложностью.

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

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