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

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

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