Алгоритмы, структуры данных




Исключения. - часть 2


Т.о. вероятность символа берется только из контекста максимально возможного для него порядка.

Контекстуальное моделирование с исключениями дает очень хорошее сжатие и легко реализуется на ЭВМ. Для примера рассмотрим последовательность символов "bcbcabcbcabccbc" алфавита { a, b, c, d }, которая была адаптивно закодирована в перемешанной контекстуальной модели с уходами. Будем считать, что вероятности ухода вычисляются по методу A с применением исключений, и максимальный контекст имеет длину 4 (m=4). Рассмотрим кодирование следующего символа "d". Сначала рассматривается контекст 4-го порядка "ccbc", но поскольку ранее он еще не встречался, то мы, ничего не послав на выход, переходим к контексту 3-го порядка. Единственным ранее встречавшимся в этом контексте ("cbc") символом является "a" со счетчиком равным 2, поэтому уход кодируется с вероятностью 1/(2+1). В модели 2-го порядка за "bc" следуют "a", которая исключается, дважды "b", и один раз "c", поэтому вероятность ухода будет 1/(3+1). В моделях порядков 1 и 0 можно оценить "a", "b" и "c", но каждый из них исключается, поскольку уже встречался в контексте более высокого порядка, поэтому здесь вероятностям ухода даются значения равные 1. Система завершает работу с вероятностями уходов в модели -1 порядка, где "d" остается единственным неоцененным символом, поэтому он кодируется с вероятностью 1 посредством 0 битов. В pезультате получим, что для кодирования используется 3.6 битов. Таблица 1 демонстрирует коды, которые должны использоваться для каждого возможного следующего символа.

Таблица 1. Механизм кодирования с уходами (и с исключениями) 4-х символов алфавита { a, b, c, d }, которые могут следовать за строкой "bcbcabcbcabccbc".

СимволКодирование
a a
2/3
( Всего = 2/3 ; 0.58 битов )
b<ESC>    b
 1/3        2/4
( Всего = 1/6 ; 2.6 битов )
c<ESC>    c
 1/3        1/4
( Всего = 1/12; 3.6 битов )
d<ESC>   <ESC>   <ESC>   <ESC>   d 
  1/3          1/4            1             1        1
( Всего = 1/12; 3.6 битов )
<


Содержание  Назад  Вперед