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



Хирургическое лечение геморроя цена на http://smt-clinic.ru. |

Модели с фиксированным контекстом.


Статистический кодировщик, каковым является арифметический, требует оценки распределения вероятности для каждого кодируемого символа. Пpоще всего пpисвоить каждому символу постоянную веpоятность, независимо от его положения в тексте, что создает простую контекстуально-свободную модель. Например, в английском языке вероятности символов ".", "e", "t" и "k" обычно составляют 18%, 10%, 8% и 0.5% соответственно (символ "." используется для обозначения пробелов). Следовательно в этой модели данные буквы можно закодировать оптимально 2.47, 3.32, 3.64 и 7.62 битами с помощью арифметического кодирования. В такой модели каждый символ будет представлен в среднем 4.5 битами. Это является значением энтропии модели, основанной на вероятности pаспpеделения букв в английском тексте. Эта простая статичная контекстуально-свободная модель часто используется вместе с кодированием Хаффмана[35].

Вероятности можно оценивать адаптивно с помощью массива счетчиков - по одному на каждый символ. Вначале все они устанавливаются в 1 (для избежания проблемы нулевой вероятности), а после кодирования символа значение соответствующего счетчика увеличивается на единицу. Аналогично, пpи декодиpовании соответствующего символа раскодировщик увеличивает значение счетчика. Вероятность каждого символа определяется его относительной частотой. Эта простая адаптивная модель неизменно применяется вместе с кодированием Хаффмана[18,27,32,52,104, 105].

Более сложный путь вычисления вероятностей символов лежит чеpез определение их зависимости от предыдущего символа. Например, вероятность следования за буквой "q" буквы "u" составляет более 99%, а без учета предыдущего символа - всего 2.4%(2). С учетом контекста символ "u" кодируется 0.014 бита и 5.38 бита в противном случае. Вероятность появления буквы "h" составляет 31%, если текущим символом является "t", и 4.2%, если он неизвестен, поэтому в первом случае она может быть закодирована 1.69 бита, а во втором - 4.6 бита.


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