WikiSort.ru - Не сортированное

ПОИСК ПО САЙТУ | о проекте

DMC (англ. dynamic Markov compression, динамическое марковское сжатие[1]) — алгоритм сжатия данных без потерь, разработанный Горданом Кормаком (Gordon Cormack) и Нигелем Хокспулом (Nigel Horspool). [2] Метод построен аналогично методу PPM: сам алгоритм является предиктором (рассчитывает вероятности символов), а непосредственное сжатие производится энтропийным кодировщиком. В отличие от PPM, метод DMC как правило работает на уровне бит, тогда как PPM — на уровне байт. DMC обеспечивает сопоставимые с PPM уровни сжатия и скорость обработки, но требует больше памяти и не так распространён, как PPM. Некоторыми из современных реализаций являются: компрессор hook от Нании Франческо Антонио (Nania Francesco Antonio) , компрессор ocamyd от Франка Швеллингера (Frank Schwellinger), также DMC используется в качестве одной из моделей в компрессоре Мета Матони (Matt Mahoney) paq8l. Все перечисленные компрессоры основаны на оригинальной реализации 1993 года на языке C от Гордона Кормака.

Алгоритм

DMC предсказывает и кодирует один бит за один логический шаг работы. Он отличается от PPM тем, что работает на уровне бит, а не байтов. Отличие от методов смешивания контекстов (например, PAQ) состоит в том, что DMC строит и использует одну единую модель источника. Непосредственное сжатие осуществляется с помощью арифметического кодирования.

Модель

Модель источника предсказывает следующий бит на основании текущего контекста. Модель может быть представлена в виде графа, каждый узел которого содержит в себе два счётчика: n0 и n1, где n0 — счётчик битов со значением 0, и n1 — счётчик битов со значением 1. Один из узлов всегда является текущим. Один из счётчиков в текущем узле увеличивается, когда в исходных данных встречается бит с соответствующим значением. Также узел имеет два ребра, связывающие его с другими узлами или с самим собой. Одно из рёбер используется, когда в исходных данных встречается 0, другое — когда 1. В простейшем случае модель состоит из одного узла, ссылающегося на самого себя. В данной конфигурации модель может только считать соотношение количества битов со значением 0 к количеству битам со значением 1 в исходных данных. Когда же в модели становится больше одного узла, то при обработке очередного бита может произойти переход к другому узлу, а также образование нового узла.

Предсказание следующего бита осуществляется расчётом вероятностей для 0 по формуле p0 = n0/n = n0/(n0 + n1) и, соответственно, для 1 по формуле p1 = 1 − p0 = n1/n. Таким образом, каждый узел воплощает отдельное состояние модели, в котором она делает разные предсказания. Контекст в модели DMC не запоминается явно, но он учитывается моделью в результате переходов между узлами графа состояний.

Моделирование осуществляется одинаково и при сжатии и при декомпрессии.

Примечания

  1. Ватолин Д. Методы сжатия данных. Устройство архиваторов, сжатие изображения и видео.. М.: Диалог-МИФИ, 1993. — С. 9. ISBN 5-86404-170-x.
  2. Gordon Cormack and Nigel Horspool, "Data Compression using Dynamic Markov Modelling", Computer Journal 30:6 (December 1987)

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .




Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2024
WikiSort.ru - проект по пересортировке и дополнению контента Википедии