Динамическое марковское сжатие - Dynamic Markov compression

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

Алгоритм

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

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

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

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

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

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

Модель DMC

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

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

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

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

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

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

государство	п₀	п₁	Следующий₀	Следующий₁
А = 11111	4		B
В = 110	3	7	E	F

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

государство	п₀	п₁	Следующий₀	Следующий₁
А = 11111	4		C
В = 110	1.8	4.2	E	F
С = 111110	1.2	2.8	E	F

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

использованная литература

^ Гордон Кормак и Найджел Хорспул, "Сжатие данных с использованием динамического марковского моделирования", Computer Journal 30: 6 (декабрь 1987 г.)

внешняя ссылка

Сжатие данных с использованием динамического марковского моделирования
Канал Google Developers на YouTube: Головка компрессора, эпизод 3 (сжатие цепи Маркова) ( Страница будет воспроизводить звук при загрузке)

[1] Гордон Кормак и Найджел Хорспул, "Сжатие данных с использованием динамического марковского моделирования", Computer Journal 30: 6 (декабрь 1987 г.)

[1]