DMC (алгоритм сжатия)

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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)