Вероятность

Арифметическое кодирование

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

Фрагментирование

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

Основная идея состоит в том, чтобы для каждой ...

Другие методы контекстного моделирования

Среди нерассмотренных остался интересный метод универсального сжа­тия Context Tree Weighting (взвешивание контекстного дерева), или CTW, который потенциально обеспечивает лучшую степень сжатия среди всех из­вестных алгоритмов [16]. В CTW при оценке вероятности символа исполь­зуется явное взвешивание.

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

Различные способы повышения точности предсказания

Масштабирование счетчика последнего встреченного символа

Если в последний раз в текущем контексте был встречен некий символ s, то вероятность того, что и текущий символ также s, вырастает, причем час­то значительно. Этот факт позволяет улучшить предсказание за счет умно­жения счетчика последнего встреченного символа (ПВС) на некий.коэффи­циент. Судя по всему, впервые такая техника описана в [15], где она назы­вается recency scaling" - масштабированием новизны.

Техника была исследована М. А. Смирновым при разработке компрессо­ра PPMN. По состоянию на 2001 г. ...

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

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

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

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

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

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

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

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

Арифметическое кодирование

Метод Хаффмана является простым и эффективным, однако, как было замечено в § 1.4, он порождает наилучшие коды переменной длины (коды, у которых средняя длина равна энтропии алфавита) только когда вероятности символов алфавита являются степенями числа 2, то есть равны 1/2, 1/4, 1/8 и т.п. Это связано с тем, что метод Хаффмана присваивает каждому символу алфавита код с целым числом битов. Теория информации предсказывает, что при вероятности символа, скажем, 0.4, ему в идеале следует присвоить код длины 1.32 бита, поскольку — log20.4 « 1.32. А метод Хаффмана присвоит этому ...

Энтропия

Основы теории информации были заложены Клодом Шеноном в 1948 году в лаборатории Белла. Эта теория оказалась настоящим сюрпризом, поскольку все привыкли воспринимать информацию лишь качественно. Для наших целей сжатия данных нам необходимо освоить только одно теоретико-информационное понятие, а именно, энтропию. Под энтропией символа а, имеющего вероятность Р, подразумевается количество информации, содержащейся в а, которая равна — Р log2P. Например, если вероятность Расимвола а равна 0.5, то его энтропия — ...