Моделирование

Психоакустические модели

Психоакустические модели дают возможность кодеру определить порог допустимого шума квантования на каждой подполосе. Эта информация будет использоваться алгоритмом назначения битов, что в сочетании с количеством имеющихся битов задаст число уровней квантования для каждой подполосы. Стандарт MPEG устанавливает две психоакустические модели. Обе модели могут использоваться любым слоем, но только модель II выдает особую информацию для слоя III. На практике модель I используется только слоями I и П. Слой III может работать с любой моделью, но лучшие результаты получаются с моделью П. ...

Вопросы для самоконтроля

1. Объясните связь между точностью предсказания значений данных и сте­пенью сжатия.

2. Что собой представляет модель источника данных в случае использова­ния для моделирования РРМ-алгоритма?

3. Почему технику уходов можно охарактеризовать как способ неявного взвешивания статистики контекстных моделей?

4. В каких случаях оценка вероятности ухода может равняться нулю?

5. Приведите пример блока данных, которые выгоднее сжимать, предска­зывая вероятность символов на базе их безусловных частот, а не с по­мощью РРМ-моделирования порядка 1.

6. Почему ...

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

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

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

Сравнение алгоритмов контекстного моделирования

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

Алгоритм сРРМИ реализует механизм наследования информации и ис­пользует SEE-d2. Описание прочих алгоритмов было дано выше.

Таблица ...

Обзор классических алгоритмов контекстного моделирования

LOEMA

Судя по всему, впервые алгоритм контекстного моделирования был реа­лизован в 1982 г. Робертсом (Roberts) [2]. Автор назвал свой алгоритм Local Order Estimation Markov Analysis (марковский анализ посредством оценива­ния локального порядка). В LOEMA используется полное смешивание оце­нок КМ различного порядка, при этом веса представляют собой значения уровня доверия к оценке в том смысле, как это понимается в математиче­ской статистике. Сравнение степени сжатия LOEMA с другими алгоритма­ми затруднено, так как, с одной стороны, программа, реализующая алго­ритм, не стала ...

Компрессоры и архиваторы, использующие контекстное моделирование

НА

Программа НА явилась, пожалуй, первым публично доступным архива­тором, использующим контекстное моделирование. Не исключено, что НА стал бы очень популярным архиватором, если бы его автор, Гарри Хирвола (Hirvola), не прекратил работать над проектом.

В НА реализованы алгоритм семейства LZ77 и алгоритм типа РРМ.

Алгоритм РРМ представляет собой хорошо продуманную модификацию классического РРМС. Метод ОВУ является априорным и основывает оцен­ку ухода из КМ на количестве имеющихся в ней символов с небольшой час­тотой. LOE не производится, последовательность ...

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

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

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

Алгоритмы РРМ

Техника контекстного моделирования Prediction by Partial Matching (предсказание по частичному совпадению), предложенная в 1984 г. Клири (Geary) и Уиттеном (Witten) [5], является одним из самых известных под­ходов к сжатию качественных данных и уж точно самым популярным среди контекстных методов. Значимость подхода обусловлена и тем фактом, что алгоритмы, причисляемые к РРМ, неизменно обеспечивают в среднем наи­лучшее сжатие при кодировании данных различных типов и служат стан­дартом, "точкой отсчета" при сравнении универсальных алгоритмов сжатия.

Перед собственно рассмотрением ...

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

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

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

Классификация стратегий моделирования

Перед рассмотрением контекстных методов моделирования следует сказать о классификации стратегий моделирования источника данных по способу по­строения и обновления модели. Выделяют 4 варианта моделирования:

■ статическое;

■ полуадаптивное;

■ адаптивное (динамическое);

■ блочно-адаптивное.

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