Dynamic Markov Encoding
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 + 2c)
Prob{digit=1 | current state=A} = (N1 + c)/(N0 + N1 + 2c)
где с - положительная константа. Для файлов большого размера (намного
больше значения 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
состояний, представляется в виде двоичного дерева у которого переход из
каждого листа ведет в корень дерева.
Во второй части даются сравнительные результаты работы алгоритма и
приводятся алгоритмы деления и построения начальной модели.
Зависимость коэффициента сжатия от параметров деления
(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% исходного файла, программа исчерпала ресурс памяти для узлов
графа и была прервана.
Сравнительные результаты работы
╔════════════════════════╦══════════════════════════════════════════════════╗
║ Метод сжатия ║ Исследуемые файлы ║
║ ╠══════════════╦════════════════╦═══════════╦══════╣
║ ║Formatted text║Unformatted text║Object code║C-text║
╠════════════════════════╬══════════════╬════════════════╬═══════════╬══════╣
║ 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 ║ 74,510 ║ 61,536 ║ 68,608 ║31,479║
╚════════════════════════╩══════════════╩════════════════╩═══════════╩══════╝
Алгоритм деления состояния модели
{ 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;