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

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

Алгоритм

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

Арифметическое кодирование

Побитовый арифметический кодер, такой как DMC, состоит из двух компонентов: предиктора и арифметического кодера. Предиктор принимает n- битную входную строку x = x ₁ x ₂ ... x _n и присваивает ей вероятность p ( x ), выраженную как произведение серии предсказаний, p ( x ₁ ) p ( x ₂ | Икс ₁ ) п ​​( Икс ₃ | Икс ₁ Икс ₂ ) ... п ( Икс _п | Икс ₁ Икс ₂ ... Икс _{п –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 представляет собой таблицу, которая отображает (побитово) контексты в пару счетчиков 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 ₁ вычисляются , бит xi _Для кодируется или декодируется, модель обновляется путем добавления 1 к счетчику, соответствующему xi _, и следующий контекст находится путем прохождения ссылки, xi _{соответствующей} .

Добавление новых контекстов

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 битов слева. В контексте А было 4 нулевых бита и некоторое количество единиц. В контексте B было 3 нуля и 7 единиц ( n = 10), что предсказывает p ₁ = 0,7.

Состояние	п 0	№ 1	следующий 0	следующий 1
А = 11111	4		Б
Б = 110	3	7	И	Ф

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

Состояние	п 0	№ 1	следующий 0	следующий 1
А = 11111	4		С
Б = 110	1.8	4.2	И	Ф
С = 111110	1.2	2.8	И	Ф

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

Внешние ссылки

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