Динамическое марковское сжатие

Динамическое марковское сжатие ( DMC ) - это алгоритм сжатия данных без потерь , разработанный Гордоном Кормаком и Найджелом Хорспулом . ^[1] Он использует арифметическое кодирование с предсказанием, аналогичное предсказанию путем частичного совпадения (PPM), за исключением того, что входные данные предсказываются по одному биту за раз (а не по одному байту за раз). DMC имеет хорошую степень сжатия и умеренную скорость, как и PPM, но требует немного больше памяти и не широко применяется. Некоторые недавние реализации включают в себя ловушку экспериментальных программ сжатия от Nania Francesco Antonio, ocamydФрэнка Швеллинджера и как подмодель в пакете Мэтта Махони. Они основаны на реализации Гордона Кормака на языке C 1993 года .

Алгоритм [ править ]

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

Арифметическое кодирование [ править ]

Поразрядный арифметический кодер, такой как DMC, имеет два компонента: предсказатель и арифметический кодер. Предиктор принимает n- битную входную строку x = x ₁ x ₂ ... x _n и присваивает ей вероятность p ( x ), выраженную как произведение ряда предсказаний, p ( x ₁ ) p ( x ₂ | x ₁ ) p ( x ₃ | x ₁ x ₂ ) ... p ( x _n | x ₁ x ₂ ... x _{n –1} ). Арифметический кодер поддерживает два двоичных числа высокой точности, p _low и p _high , представляющих возможный диапазон для полной вероятности того, что модель присвоит всем строкам лексикографически меньше x , учитывая биты x, видимые до сих пор. Сжатый код для x - это p _x , самая короткая битовая строка, представляющая число между p _low и p _high . Всегда можно найти число в этом диапазоне не более чем на один бит длиннее, чемПредел Шеннона , log ₂  1 / p ( x '). Одно такое число может быть получено из p _high , отбрасывая все завершающие биты после первого бита, который отличается от p _low .

Сжатие происходит следующим образом. Начальный диапазон установлен на p _low = 0, p _high = 1. Для каждого бита предсказатель оценивает p ₀ = p ( x _i = 0 | x ₁ x ₂ ... x _{i –1} ) и p ₁ = 1. -  p ₀ , вероятность 0 или 1 соответственно. Затем арифметический кодер делит текущий диапазон ( p _low ,  p _high ) на две части пропорционально p ₀ и p.₁ . Тогда поддиапазон, соответствующий следующему биту x _i, становится новым диапазоном.

Для декомпрессии предсказатель делает идентичную серию предсказаний, учитывая уже распакованные биты. Арифметический кодер выполняет идентичную серию разбиений диапазона, затем выбирает диапазон, содержащий p _x, и выводит бит x _i, соответствующий этому поддиапазону.

На практике нет необходимости сохранять p _low и p _high в памяти для высокой точности. По мере сужения диапазона начальные биты обоих чисел будут одинаковыми и могут быть немедленно выведены.

Модель DMC [ править ]

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

В исходной реализации DMC исходная таблица - это набор всех контекстов длиной от 8 до 15 бит, которые начинаются на границе байта. Начальное состояние - это любой из 8-битных контекстов. Счетчики представляют собой числа с плавающей запятой, инициализированные небольшой ненулевой константой, например 0,2. Счетчики не инициализируются нулевым значением, чтобы можно было кодировать значения, даже если они не были просмотрены ранее в текущем контексте.

Моделирование одинаково для сжатия и распаковки. Для каждого бита вычисляются p ₀ и p ₁ , бит x _i кодируется или декодируется, модель обновляется путем добавления 1 к счетчику, соответствующему x _i , и следующий контекст находится путем перехода по ссылке, соответствующей x _i .

Добавление новых контекстов [ править ]

DMC, описанный выше, эквивалентен контекстной модели первого порядка. Однако добавление более длинных контекстов для улучшения сжатия - это нормально. Если текущий контекст - A, а следующий контекст B будет отбрасывать биты слева, то DMC может добавить (клонировать) новый контекст C из B. C представляет тот же контекст, что и A, после добавления одного бита справа, как с B , но без потери битов слева. Таким образом, ссылка от A будет перемещена от B к точке с C. Оба B и C сделают один и тот же прогноз, и оба будут указывать на одну и ту же пару следующих состояний. Общее количество n = n ₀  +  n ₁ для C будет равно количеству n _x для A (для входного бита  x), и это количество будет вычтено из B.

Например, предположим, что состояние A представляет контекст 11111. На входном бите 0 он переходит в состояние B, представляющее контекст 110, полученный путем отбрасывания 3 битов слева. В контексте A было 4 нулевых бита и некоторое количество единичных битов. В контексте B было 3 нуля и 7 единиц ( n  = 10), что предсказывает p ₁ = 0,7.

C клонирован из B. Он представляет контекст 111110. Оба B и C предсказывают p ₁ = 0,7, и оба переходят в одно и то же следующее состояние, E и F. Счетчик для C равен n = 4, что равно n ₀ для A. Это оставляет n = 6 для B.

Состояния клонируются непосредственно перед переходом к ним. В исходном DMC условием для клонирования состояния является переход от A к B как минимум 2, а счетчик B как минимум на 2 больше этого. (Когда второй порог больше 0, это гарантирует, что другие состояния все равно перейдут в B после клонирования). Некоторые реализации, такие как hook, позволяют устанавливать эти пороги в качестве параметров. В paq8l эти пороги увеличиваются по мере использования памяти для замедления скорости роста новых состояний. В большинстве реализаций, когда память исчерпана, модель отбрасывается и повторно инициализируется обратно к исходной побайтной модели порядка 1.

Ссылки [ править ]

Внешние ссылки [ править ]

• Сжатие данных с использованием динамического марковского моделирования
• Канал Google Developers на YouTube: Compressor Head Episode 3 (Markov Chain Compression) ( страница будет воспроизводить звук при загрузке)