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

Алгоритм

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

Модель

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

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

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

Примечания