Описание метода Динамического сжатия Маркова.
Захаров Максим
30.03.1993
Данное документ составлен на основе первоначального описания алгорит-
ма, опубликованного в [1]. Кратко описывается алгоритм и приводятся ре-
зультаты сравнения этого алгоритма с другими методами сжатия. Более под-
робно о работе алгоритма, в частности, о тонких местах в выборе парамет-
ров и совместном использовании GUAZZO CODING ALGORITHM, можно прочитать
в [1]. В работе [2] показывается, что модель Динамического сжатия Марко-
ва эквивалентна автомату с конечным контекстом (Finite Context Automata,
FCA). Т.к. класс FCA является подмножеством класса автоматов с конечным
числом состояний (Finite State Automata, FSA), то делается предположе-
ние, что т.к. фрагменты текстов на английском языке могут быть распозна-
ны FSA, но не могут распознаваться Марковской моделью переменного поряд-
ка (variable-order Markov model), то использование модели FSA потен-
циально должно давать лучшие результаты сжатия.
1. G.V. Cormack, R.N. Horspool.
Data Compression Using Dynamic Markov Modelling.
// The Computer Journal, vol.30,No.6,1987, pp.541-550
2. T. Bell, A. Moffat.
A note on the DMC data compression scheme.
// The Computer Journal, vol.32,No.1,1989, pp.16-20
------------------------
Hа практике, сообщения почти всегда имеют некоторую степень зависи-
мости между соседними символами, что соответствует источнику сообщений с
памятью. В частности, таким источником может быть Марковская модель (в
каждом состоянии она помнит только об одном предыдущем своем состоянии).
Для примера используем простую Марковскую модель. Будем считать, что
источник порождает строки, состоящие из двоичных цифр такие, что:
0 следует за 0 с вероятностью 2/3
0 следует за 1 с вероятностью 1/3
1 следует за 0 с вероятностью 2/5
1 следует за 1 с вероятностью 3/5
и первая цифра может быть 0 или 1 равновероятно (1/2).
Сообщения, порождаемые этой моделью имеют общее свойство: 0 следует
за другим 0 чаще, чем за 1. Аналогично - 1 чаще следует за 1, чем за 0.
Марковская модель может быть описана с помощью ориентированного графа,
каждой дуге которого приписываются соответствующие вероятности перехода.
Диаграмма состояний для этой модели выглядит следующим образом:
┌───┐
│ А │
/└───┘\
/ \
0(50%) / \ 1(50%)
/ \
|/ 0 (40%) \|
┌───┐───────────┬───┐
┌────│ B │ │ C │─────┐
│ └─┬─┴───────────└─┬─┘ │
0 (67%)│ │ 1 (33%) │ │1 (60%)
└──────┘ └───────┘
При автоматическом создании такой модели возникает две проблемы:
проблема определения вероятностей перехода, приписываемых дугам графа, и
проблема в определении самой структуры графа. Эти проблемы рассматри-
ваются по отдельности.
Определение вероятностей перехода
Пусть уже известна структура графа. По мере прочитывания двоичных
цифр сообщения Марковская модель будет переходить из одного своего сос-
тояния в другое в соответствии с прочитанными символами. Hеобходимо
подсчитать сколько раз модель будет переходить по каждой дуге (для каж-
дой дуги заводятся счетчики переходов по этой дуге). С помощью этих
счетчиков можно получить оценки вероятностей переходов. Если переход из
состояния А по дуге для символа 0 проходил N0 раз, а по дуге для 1 - N1,
то оценки вероятностей будут выглядеть следующим образом:
Prob{ digit=0 | current state=A } = N0 / (N0 + N1)
Prob{ digit=1 | current state=A } = N1 / (N0 + N1)
Чем чаще мы будем попадать в состояние А, тем точнее будут эти оцен-
ки.
При адаптивном кодировании заранее определить значения N0 и N1 невоз-
можно. В этом случае эти оценки могут выглядеть следующим образом:
Prob{ digit=0 | current state=A } = (N0 + c) / (N0 + N1 + 2*c)
Prob{ digit=1 | current state=A } = (N1 + c) / (N0 + N1 + 2*c)
где с - положительная константа. Для файлов большого размера (на много
больше значения c) выбор конкретного значения c существенной роли не иг-
рает. Для файлов малого размера при малом значении c модель быстрее
'выучит' характеристики источника, однако, при этом увеличивается ве-
роятность неправильного прогноза. (Т.е. типичная проблема адаптивных ал-
горитмов).
Построение диаграммы состояний
Алгоритм динамического построения диаграммы состояний поясняется на
простом примере: пусть уже построена модель, содержащая состояния
A,B,...,E:
┌───┐ 0 ┌───┐ 0 ┌───┐
│ A ├─────────│ C ├─────────│ D │
└───┘ /└───┘\ └───┘
/| \
/ \
1 / \ 1
/ \
/ \
┌───┐ / \|┌───┐
│ B ├┴────────────────────│ E │
└───┘ └───┘
Из диаграммы видно, что в состояние C ведут две дуги из A и B и выхо-
дит две дуги: в D и E. Всякий раз, когда модель переходит в состояние C,
теряется некоторая информация о контексте, т.е. забывается откуда мы
пришли - из A или B. Однако вполне может быть, что выбор следующего сос-
тояния (D или E) зависит от предыдущего состояния (A или B). Чтобы
учесть эту зависимость прибегнем к следующему приему: разделим состояние
C на два состояния. Измененная модель будет иметь вид:
┌───┐ 0 ┌───┐ 0 ┌───┐
│ A ├─────────│ C ├────────│ D │
└───┘ └───┘\ 1 /|└───┘
\ /
\ /
/
0 / \
/ \
┌───┐ 1 ┌───┐/ \|┌───┐
│ B ├─────────│ С'├────────│ E │
└───┘ └───┘ 1 └───┘
Значения счетчиков переходов из C в D или E делится между счетчиками
C и C' в новой модели пропорционально числу переходов из A в C и из B в
C для старой модели. Теперь модель отражает степень зависимости между
состояниями A,B и D,E. Для этой модели возможно выбор следующего сос-
тояния (D или E) не зависит от предыдущего состояния (A или B), но зави-
сит от непосредственного предшественника A или B. В этом случае делим
состояния A,B,C' и еще раз делим состояние C. Т.е. модель теперь будет
учитывать эти зависимости.
В основном, чем больше мы делим состояний, тем больше увеличивает
размах зависимостей, используемых моделью для прогноза. Само собой про-
цесс деления необходимо производить только в том случае, когда мы увере-
ны в существовании соответствующих зависимостей, иначе мы потеряем ин-
формацию о контексте. Отсюда желательно, чтобы деление состояния C про-
ходило тогда, когда оба счетчика переходов AC и BC достаточно велики. Hа
основе этого можно вывести критерий деления состояния:
Выбранное состояние делится в том и только в том случае, если число пе-
реходов из текущего состояния в выбранное состояние больше, чем
MIN_CNT1, и число переходов из всех других состояний, кроме текущего, в
выбранное состояние больше, чем MIN_CNT2.
Hачальная модель
Для полного определения метода динамического сжатия Маркова осталось
определить стартовую модель. Самая простая модель выглядит следующим об-
разом:
┌─────────────────┐
│ │
┌───┐ │
┌──────────┤ ├───────────────┘
│ └───┘
│ │
└────────────┘
Самая простая модель для байт-ориентированного варианта имеет 255
состояний, представляется в виде двоичного дерева у которого переход из
каждого листа ведет в корень дерева.
В целом, древовидная начальная модель работает хорошо, но можно
построить модель, которая будет работать немного лучше. В общем случае,
состояния на k-м уровне дерева учитывает зависимость от предыдущих k-1
бит. Размер контекста, от которого зависит текущее состояние увеличи-
вается от 0 до 7 бит, затем, при переходе к корню дерева, эта зависи-
мость теряется. Лучшей по сравнению с этой будет модель, сохраняющая
постоянным размер контекста. Т.е. такая модель должна учитывать зависи-
мость между последними битами предыдущего байта и первыми битами текуще-
го бита. К сожалению, такую модель трудно представить в виде диаграммы,
но алгоритм построения этой модели приводится в конце данной статьи.
Последний важный момент
Этим последним моментом является вопрос когда прекращать производить
деление состояния модели. Если этого не производить, то через некоторое
время модель может занять всю имеющуюся память и потребовать еще. Одно
из возможных решений - определить предел числа состояний модели по дос-
тижении которого модель разрушается и начинает создаваться заново из на-
чальной модели. Последствия такой операции можно облегчить, если запом-
нить перед разрушением модели предыдущие n байт текста и затем по этому
фрагменту улучшить начальную модель перед продолжением обработки текста.
Зависимость коэффициента сжатия от параметров деления (MIN_CNT1, MIN_CNT2)
───────────┬─────────────────────┬───────────────────────
Значение │ Число вершин графа │ Коэффициент сжатия
параметров │ │ (%)
───────────┼─────────────────────┼───────────────────────
( 1,1 )* │ > 194000 │ 34.7
( 2,2 ) │ 150901 │ 33.8
( 4,4 ) │ 84090 │ 35.8
( 8,8 ) │ 44296 │ 38.9
(16,16) │ 23889 │ 42.7
(32,32) │ 12089 │ 46.5
(64,64) │ 6347 │ 50.6
(128,128) │ 3211 │ 54.6
(256,256) │ 1711 │ 58.6
───────────┴─────────────────────┴───────────────────────
Файл, на котором проводились исследования, содержал 97393 символов
ASCII текста.
* Сжав 90% исходного файла, программа исчерпала ресурс памяти для узлов
графа и была прервана.
Сравнительные результаты работы
┌───────────────────────┬─────────────────────────────────────────────────┐
│ Метод сжатия │ Исследуемые файлы │
│ ├──────────────┬────────────────┬─────────┬───────┤
│ │Форматированый│Hеформатированый│Объектный│С-текст│
│ │ текст │ текст │ код │ │
├───────────────────────┼──────────────┼────────────────┼─────────┼───────┤
│Adaptive Huffman │ 59.7 │ 61.6 │ 79.6 │ 62.9 │
├───────────────────────┼──────────────┼────────────────┼─────────┼───────┤
│Normal Ziv-Lempel (LZW)│ 38.2 │ 42.9 │ 98.4 │ 40.8 │
├───────────────────────┼──────────────┼────────────────┼─────────┼───────┤
│Bit-oriented (LZ-2) │ 74.2 │ 83.6 │ 91.3 │ 86.7 │
├───────────────────────┼──────────────┼────────────────┼─────────┼───────┤
│Cleary and Witten (CW) │ 26.5 │ 30.2 │ 69.4 │ 26.3 │
├───────────────────────┼──────────────┼────────────────┼─────────┼───────┤
│Dynamic Markov (DMC) │ 27.2 │ 31.8 │ 54.8 │ 27.5 │
├───────────────────────┼──────────────┼────────────────┼─────────┼───────┤
│ File size │ 74510 │ 61536 │ 68608 │ 31479 │
└───────────────────────┴──────────────┴────────────────┴─────────┴───────┘
Алгоритм деления состояния модели
{ NEXT_STATE[S,D] = state reached from S after trsnsition on digit D
TRANS_CNT[S,D] = number of observations of input D when in state S
STATE = number of current state
LAST_STATE = largest state number used so far
MIN_CNT1 = minimum number of transitions from the current
state to state S before S is eligible for cloning
MIN_CNT2 = minimum number of visits to a state S from all
predecessors of S other than the current state
before S is eligible for cloning }
while not eof do
begin
resd( B ); { read one input bit }
TRANS_CNT[STATE,B] := TRANS_CNT[STATE,B] + 1;
NXT := NEXT_STATE[STATE,B];
NXT_CNT := TRANS_CNT[NXT,0] + TRANS_CNT[NXT,1];
if (TRANS_CNT[STATE,B] > MIN_CNT1) and
((TRANS_CNT - TRANS_CNT[STATE,B]) > MIN_CNT2) then
begin
LAST_STATE := LAST_STATE + 1;
NEW := LAST_STATE; { Obtain new state number }
NEXT_STATE[STATE,B] := NEW;
RATIO := TRANS_CNT[STATE,B] / NXT_CNT;
for B:=0 to 1 do
begin
NEXT_STATE[NEW,B] := NEXT_STATE[NXT,B];
TRANS_CNT[NEW,B] := RATIO * TRANS_CNT[NXT,B];
TRABS_CNT[NXT,B] := TRANS_CNT[NXT,B] - TRANS_CNT[NEW,B]
end;
NXT := NEW
end;
STATE := NXT
end;
.......................................................................
Алгоритм генерации начального состояния
const
NBITS = 8; { Number of bits per byte }
STRANDS = 256; { 2 ** NBITS }
for I := 0 to NBITS-1 do
for J :=0 to STRANDS-1 do
begin
STATE := I + NBITS * J;
K := (I + 1) mod NBITS;
NEXT_STATE[STATE,0] := K + ((2 * j) mod STRANDS) * NBITS;
NEXT_STATE[STATE,1] := K + ((2 * j + 1) mod STRANDS) * NBITS;
TRANS_CNT[STATE,0] := 1;
TRANS_CNT[STATE,0] := 1
end;
LAST_STATE := NBITS * STRANDS -1;
.......................................................................
Учебный вариант алгоритма Динамического сжатия Маркова
Hиже приводится реализация алгоритма Динамического сжатия Маркова,
написанный автором алгоритма для учебных целей. Этот алгоритм уже публи-
ковался в этой конференции и приводится здесь для полноты.