thedeemon: (Default)
Dmitry Popov ([personal profile] thedeemon) wrote2011-09-15 10:59 pm
Entry tags:

Часть 3. Контекстное моделирование

(начало серии постов здесь)

В предыдущей части мы увидели, что вычисленная в лоб по вероятностям символов информационная энтропия файла дает оценку снизу по сжатию для оперирующего этими вероятностями арифметического кодера, однако простой zip умудряется сжать текст в полтора раза лучше. Все дело в том, что до этого момента мы рассматривали лишь индивидуальные символы, не обращая внимания на то, что их порядок не совсем случаен: текст состоит не из произвольной последовательности символов, а из слов языка и знаков пунктуации. Если мы прочитали последовательность букв "функц", то можем быть почти уверены, что следующая буква будет "и". Когда в английском тексте встречается буква "q", то если этот текст не про Аль-Каиду, следующая буква почти наверняка будет "u". Как это можно формализовать? Рассматривая текущий символ как случайную величину Х, можно предыдущий символ считать другой наблюдаемой одновременно с Х случайной величиной Y. Понятно, что мат.ожидание и дисперсия у них будут одинаковые, но раз они как-то связаны, можно предположить, что между ними будет корреляция. Попробуем посчитать коэффициенты корреляции для символов i и i-k:

corr xs ys = sumxy / ((sqrt sumx) * (sqrt sumy))
where
  sumxy = sum [(x-mx)*(y-my) \\ x <- xs & y <- ys]
  sumx = sum [(x-mx)*(x-mx) \\ x <- xs]
  sumy = sum [(y-my)*(y-my) \\ y <- ys]
  mx = avg xs
  my = avg ys

kcorr str k = corr xs ys
where
  xs = map fst lst
  ys = map snd lst
  lst = [(toReal str.[i-k], toReal str.[i]) \\ i <- [k..n-1]]
  n = size str

corrs text = [kcorr text k \\ k <- [1..7]]

А вот фиг. Результаты:
  k   meden.txt   hhguide.txt
  1    0.071       0.104
  2   -0.088       0.030
  3   -0.044       0.034
  4    0.030       0.029
  5    0.013       0.009
  6   -0.048      -0.037
  7   -0.026      -0.002

Корреляция незначительная. Нужен другой подход. Давайте рассмотрим пару (str[i-k], str[i]) как одну случайную величину с 256*256 = 65536 теоретически возможными значениями. Подсчитав число различных таких пар в файле, мы можем получить распределение вероятностей и вычислить совместную энтропию H(X,Y). Для файла meden.txt и k=1
H(X,Y) = 7.97
при этом H(X) = H(Y) = 4.49
Т.е. степень неопределенности для пары подряд идущих символов получилась меньше, чем сумма неопределенностей каждого из них. Обозначим эту разницу I(X,Y):
I(X,Y) = H(X) + H(Y) - H(X,Y)
Что можно о ней сказать?

Поскольку H(X,Y) = Сумма -P(X,Y) * log2(P(X,Y))
то в случае независимых случайных величин X и Y
P(X,Y) = P(X) * P(Y) и

Поэтому если X и Y независимы, то
I(X,Y) = H(X) + H(Y) - (H(X) + H(Y)) = 0

Если вспомнить, что условная вероятность X при имеющемся Y
P(X|Y) = P(X,Y) / P(Y)
то можно определить условную энтропию
H(X|Y) = Сумма по y от P(y) * H(X|Y=y)
Тогда

значит
H(Y) - H(X,Y) = -H(X|Y)
и
I(X,Y) = H(X) + H(Y) - H(X,Y) = H(X) - H(X|Y)
А поскольку H(X|Y) <= H(X) (знание Y не увеличивает неопределенности Х), то
I(X,Y) >= 0

У нас получилась некоторая характеристика случайных величин X и Y, которая равна нулю, когда они независимы, больше нуля, когда они зависимы, и равна разности между неопределенностью одной величины и ее же неопределенностью при известном значении второй величины. Получается это как бы количество информации в одной величине о другой величине. Причем, в силу симметричности, взаимное:
I(X,Y) = H(X) - H(X|Y) = H(Y) - H(Y|X)
Кстати,
I(X,X) = H(X) + H(X) - H(X,X) = H(X)
Количество информации об Х в самом Х равно энтропии Х.

Давайте посчитаем I(str[i-k], str[i]) для тех же текстов:
  k  meden   hhguide
  1   1.02    1.12    
  2   0.42    0.57 
  3   0.22    0.30 
  4   0.10    0.18
  5   0.06    0.12
  6   0.04    0.07
  7   0.02    0.04 

Вот это уже интереснее. Интуитивно понятно, что ближайшие символы в тексте более зависимы (их сочетания менее случайны), и следовательно содержат больше информации друг о друге. И рассчитанные значения I(X,Y) это подтверждают: больше всего информации о текущем символе в его ближайшем соседе, а по мере удаления символов друг от друга их взаимная информация уменьшается.

Наша формула предсказывает, что в предыдущем символе содержится примерно 1 бит информации о текущем. Если взять компрессор из предыдущей части и вместо одной таблицы частот символов сделать 256 таких таблиц, используя при кодировании каждого символа предыдущий символ в качестве индекса, то meden.txt сожмется до 359970 байт, а hhguide.txt до 119047 (без учета размера таблиц). Это 3.55 и 3.47 бита на символ соответственно, т.е. как раз примерно на 1 бит меньше, чем при независимом кодировании символов. Работает теория. :)

Но мы видим, что информация о текущем символе есть не только в предыдущем символе, но и в более ранних. Если мы только знаем, что последний прочитанный символ был "у", угадать следующий довольно сложно, но если мы знаем, что только что прочитали цепочку "Петербу", то можем быть почти уверены, что следующая буква "р". А чем больше оценка вероятности кодируемого символа, тем больше его подинтервал в арифметическом кодере, тем меньше бит на него уйдет. В экстремальном случае мы точно знаем какой символ будет следующий, тогда его вероятность равна единице, интервал тоже равен 1, а значит его кодирование не меняет рабочего интервала арифметика, т.е. все равно, что мы вообще этот символ не кодировали, на него тратится 0 бит.

Отсюда возникает идея сделать оценку вероятностей для очередного сжимаемого символа зависимой от недавней истории - k последних встреченных символов. Эти k символов называются контекстом. Для каждого контекста у нас будет своя статистика, предсказывающая вероятности появления разных символов с этим контекстом. Записывать все эти таблицы в получаемый файл слишком накладно, т.к. контекстов может быть очень много разных, поэтому будем статистику накапливать по мере сжатия: встретили символ в данном контексте, увеличили его счетчик. Если кодер и декодер будут делать это синхронно, то в каждый момент времени у них будут одинаковые модели, и записывать статистику в файл вообще не нужно. Весь этот подход с построением вероятностной модели данных с разными контекстами носит название "контекстное моделирование".

Как хранить все эти контексты? Практичные современные компрессоры используют простые хэш-таблицы на базе массивов, частенько забивая на коллизии. Мне такой подход не нравится, и для демонстрации я буду использовать дерево. Так нагляднее, и нет коллизий и потерь информации из-за них. Каждая вершина дерева будет некоторым контекстом со своей статистикой, в корне нулевой контекст - пустая строка, из него идут помеченные символами дуги к контекстам первого порядка - из одного символа, из них - к контекстам из двух символов и т.д. Это trie. Вот так с нуля строится дерево по мере прочтения строки "ананас":


Длину контекста ограничим 4 символами. Сколько всего может быть разных контекстов? Если бы данные были совсем случайными и их было много, то количество контекстов длины n приближалось бы к 256^n. Но в тексте у нас встречаются далеко не все возможные комбинации символов, поэтому если посчитать на примере наших двух файлов количество разных подстрок длины n, получим такие числа:
 length   meden.txt  hhguide.txt
   1           86         84
   2         1689       1203
   3        10630       7532
   4        39421      25395
   5       101079      56700

Очень немного по сравнению с потенциально возможным количеством. Более того, из-за такого сравнительно низкого разнообразия строк, очень много узлов в дереве будут иметь всего одну ветвь (для контекстов длины 3 таких почти половина). Аналогично со статистикой символов: из 256 возможных всего в этих текстах встречаются 84-86 разных, но среди контекстов длины 3-4 (коих большинство) у большого числа контекстов разнообразие встреченных символов очень мало (в почти половине трехсимвольных контекстов по одному символу, в 90% - не больше 10 различных символов). Контексты, в которых встречается только один символ, называются детерминированными. Знание этой статистики позволяет выбрать более экономное представление данных, а память в современных алгоритмах сжатия - самый главный ресурс.

Итак, дерево контекстов должно содержать статистику в узлах и именованные символами поддеревья с более длинными контекстами. Я разделил узлы на три вида: листья (узлы без поддеревьев), узлы с единственным поддеревом, и узлы с большим числом поддеревьев.
:: CxTree a = Leaf a
            | CxDet a !Char .(CxTree a)
            | LargeNode a .{.CxTree a} 
            | Nothing

Здесь а - параметр типа, туда будет подставлен контейнер для статистики. Лист содержит только статистику. Узел с единственным поддеревом - статистику, символ поддерева и само поддерево. Узел с большим числом поддеревьев - свою статистику и массив из 256 поддеревьев, где индексом служит символ поддерева. Поскольку поддеревьев обычно меньше 256, а нулевых укателей у нас в языке нет, то вместо null использован четвертый вариант узла - Nothing. Точки перед типами означают, что они могут быть уникальными (а могут и не быть).

Учитывая большое количество детерминированных и малонаселенных контекстов, статистику я тоже описал вариантным типом:
:: Stats = StDet !Char !Int // c, Nc
         | StSmall !String .{#Int} !Int !Int //symbols, counters, Nesc, total
         | StLarge .{#Int} !Int !Int // counters, Nesc, total

Три варианта: детерминированный контекст с единственным символом и его счетчиком, большой контекст с массивом на 256 счетчиков всех возможных символов, и маленький контекст с несколькими различными символами (от 2 до 10), где символы перечислены в строке, а их счетчики в массиве той же длины. Кроме того, для недетерминированных контекстов хранится значение total - сумма всех счетчиков. Она увеличивается каждый раз, когда увеличивается какой-то счетчик, и нужна, чтобы при достижении определенного порога перенормировать счетчики, чтобы сумма частот всегда была не больше минимального значения рабочего интервала range coder'a. Смысл еще одного числа (Nesc) будет раскрыт чуть ниже.

Как такое дерево контекстов использовать для сжатия? На примере с "у" и "Петербу" видно, что более длинные контексты по идее должны лучше предсказывать следующий символ, поэтому при сжатии очередного символа имеет смысл найти самый длинный подходящий контекст из имеющихся в дереве и использовать его статистику. Однако в большинстве длинных контекстов встречается очень немного различных символов, а в силу устройства range coder'a мы не можем сжать символ, у которого нулевая вероятность. Если же назначить всем возможным символам какую-то ненулевую вероятность, то с учетом того, что большинство из них никогда не встретится в данном контексте, вероятность реально встречающихся символов будет недооценена, что пагубно отразится на степени сжатия. Поэтому можно сделать следующую схему: ввести один псевдо-символ с ненулевой вероятностью, который будет обозначать все еще невстреченные в данном контексте символы. Если текущий символ еще не встречался в рассматриваемом контексте, то вместо него кодируем тот псевдо-символ и переходим к родительскому (более короткому) контексту. Этот псевдо-символ называют символом ухода (escape symbol). Если и в более коротком контексте наш символ не встречался, то опять кодируем символ ухода и переходим еще на уровень ближе к корню. В самом корне дерева у нас пустой контекст, в котором уже для всех символов вероятность ненулевая, там уж точно текущий символ будет закодирован. Декодер так же начинает с самого длинного найденного контекста, если декодирован символ ухода, то переходит к более короткому контексту и так далее, пока не будет декодирован символ, отличный от символа ухода. На каждом шаге счетчик закодированного символа увеличивается, таким образом накапливается статистика о распределении символов. Такая схема с последовательным обходом контекстов от длинного к коротким носит название PPM - Prediction by Partial Match. Те самые поля Nesc из описанной выше структуры для статистики как раз содержат счетчики символа ухода.

Если описанную только что схему реализовать в таком виде, наши тестовые файлы meden.txt и hhguide.txt сожмутся до 252248 и 92760 байт соответственно, что уже лучше, чем zip с его 310056 и 101171, но пока хуже, чем bzip2 с его 226367 и 78570. Определенно, есть еще куда расти. Код я пока не буду приводить, лучше покажу чуть позже сразу с улучшениями.

Первая довольно очевидная идея улучшения: если текущий символ не найден в каком-то контексте, и кодируется символ ухода, то значит текущий символ точно не совпадает ни с одним из известных в том контексте символов. А значит, когда мы оцениваем его в более коротком контексте, то вероятность встретить один из символов, известных предыдущему контексту, нулевая. Можно исключить их при расчете вероятностей/интервалов в очередном контексте, что пропорционально увеличит вероятности и интервалы остальных символов, тем самым на них потратится меньше бит. Эта техника называется "исключение" (exclusion) или "маскирование". Простой способ реализации - иметь маску из 256 флагов (единиц), при уходе из контекста обнулять все флаги, соответствующие известным символам, а при расчете интервалов в очередном контексте умножать счетчики символов на соответствующие им значения маски, тем самым локально обнуляя вероятности символов, заведомо отличающихся от текущего. Применение этого приема позволило сжать наши тестовые файлы до 235012 и 84630 байт.

Следующий простой прием: увеличивать счетчики символов не на единицу, а на разные константы. Это во-первых влияет на скорость обновления статистики, т.к. с учетом периодической перенормировки счетчиков более свежие значения получают больший вес, и чем быстрее их увеличиваешь, тем чаще делается перенормировка, тем быстрее эволюционирует и адаптируется статистика. Во-вторых, можно счетчики настоящих символов и символа ухода увеличивать по-разному, что дает другую вероятность ухода. В третьих, можно при создании контекста инициализировать его первые счетчики по-разному, тем самым влияя на оценки вероятностей в молодых контекстах (в которых еще мало символов встретилось). Опасность этого подхода (подгонки констант) заключается в том, что легко настроить алгоритм так, что конкретные тестовые данные будут сжиматься лучше, а другие файлы хуже. Тем не менее, поиграв с константами начальных значений счетчиков и дельт, я нашел набор, который неплохо подошел к тем двум тестовым текстам, но также оказался неплохим и с другими данными. Те два текста сжались до 222014 и 78314 байт.

До этого при сжатии очередного символа мы увеличивали его счетчик в контекстах всех длин. Однако оказывается, что если увеличивать его только в тех контекстах, которые участвовали в кодировании текущего символа, т.е. все, выдавшие символ ухода, плюс тот, где символ таки был закодирован, но не включая более короткие контексты, то это может улучшить сжатие. Этот прием называется update exclusion. С ним те файлы сжались до 220096 и 77129 байт.

Можно ли еще лучше? Можно, об этом в следующей части. Пока же стоит сделать паузу и посмотреть внимательнее на процесс сжатия в текущей схеме. Каждый символ кодируется последовательностью из 1-5 интервалов: 0 или более интервалов для символа ухода и один для самого символа. Если для каждого сжимаемого символа вывести в лог использованные интервалы (в виде cumFreq, freq, totFreq) и количество потраченных на них бит, то начало файла выглядит так:
D (68,1,256; L=8) LE=0 LD=8 L=8
o (118,1,263; L=8.038) LE=0 LD=8.038 L=8.038
u (131,1,270; L=8.076) LE=0 LD=8.076 L=8.076
g (110,1,277; L=8.113) LE=0 LD=8.113 L=8.113
l (122,1,284; L=8.149) LE=0 LD=8.149 L=8.149
a (104,1,291; L=8.184) LE=0 LD=8.184 L=8.184
s (150,1,298; L=8.219) LE=0 LD=8.219 L=8.219
#32 (32,1,305; L=8.252) LE=0 LD=8.252 L=8.252
A (72,1,312; L=8.285) LE=0 LD=8.285 L=8.285
d (128,1,319; L=8.317) LE=0 LD=8.317 L=8.317
a (118,8,326; L=5.348) LE=0 LD=5.348 L=5.348
m (0,1,2; L=1)(165,1,325; L=8.344) LE=1 LD=8.344 L=9.344
s (185,8,340; L=5.409) LE=0 LD=5.409 L=5.409
#13 (0,1,2; L=1)(13,1,339; L=8.405) LE=1 LD=8.405 L=9.405
#10 (10,1,354; L=8.467) LE=0 LD=8.467 L=8.467
T (119,1,361; L=8.495) LE=0 LD=8.495 L=8.495
h (174,1,368; L=8.523) LE=0 LD=8.523 L=8.523
e (164,1,375; L=8.550) LE=0 LD=8.550 L=8.550
#32 (46,8,382; L=5.577) LE=0 LD=5.577 L=5.577
H (0,1,2; L=1)(106,1,381; L=8.573) LE=1 LD=8.573 L=9.573
i (203,1,396; L=8.629) LE=0 LD=8.629 L=8.629
t (256,1,403; L=8.654) LE=0 LD=8.654 L=8.654
c (169,1,410; L=8.679) LE=0 LD=8.679 L=8.679
h (202,8,417; L=5.703) LE=0 LD=5.703 L=5.703
#32 (0,1,2; L=1)(46,15,416; L=4.793) LE=1 LD=4.793 L=5.793
H (7,8,15; L=0.906) LE=0 LD=0.906 L=0.906
i (0,1,2; L=1)(1,1,2; L=1) LE=1 LD=1 L=2
k (0,1,2; L=1)(0,1,2; L=1)(0,1,2; L=1)(217,1,407; L=8.668) LE=3 LD=8.668 L=11.66
e (192,8,438; L=5.774) LE=0 LD=5.774 L=5.774
r (0,1,2; L=1)(253,1,423; L=8.724) LE=1 LD=8.724 L=9.724
...
Тут LE - число бит, потраченное на escape symbol, LD - потраченное на сам символ, а L - их сумма, сколько на символ ушло всего. Самые первые символы кодируются корневым пустым контекстом, где изначально у каждого символа вероятность 1/256. Поэтому на первый символ ушло ровно 8 бит. Его счетчик, а значит и оценка вероятности, был увеличен, поэтому вероятности остальных символов чуть уменьшились, и следующие символы занимают чуть больше 8 бит. Когда же буква "а" встречается второй раз, ее вероятность уже больше, и она кодируется в 5.348 бит. Когда в строке "Douglas Adams" мы доходим до буквы m, мы впервые встречаем контекст, который встречался раньше - "a". В прошлый раз после "а" шла "s", но в этот раз встретилась не она, поэтому в том контексте нужного символа нет, кодируется escape, мы переходим в более короткий контекст - корневой - и кодируем символ "m" в нем.

Ближе к концу файла, когда статистика по контекстам накоплена хорошая, цифры уже другие:
D (0,36,202; L=2.488)(152,50,512; L=3.356) LE=2.488 LD=3.356 L=5.844
o (72,44,116; L=1.398) LE=0 LD=1.398 L=1.398
n (61,11,72; L=2.710) LE=0 LD=2.710 L=2.710
' (6,110,117; L=0.089) LE=0 LD=0.089 L=0.089
t (7,154,161; L=0.064) LE=0 LD=0.064 L=0.064
#32 (21,1001,1100; L=0.136) LE=0 LD=0.136 L=0.136
p (2139,88,3470; L=5.301) LE=0 LD=5.301 L=5.301
r (86,11,109; L=3.308) LE=0 LD=3.308 L=3.308
e (33,55,220; L=2) LE=0 LD=2 L=2
t (630,242,927; L=1.937) LE=0 LD=1.937 L=1.937
e (27,99,303; L=1.613) LE=0 LD=1.613 L=1.613
n (77,55,143; L=1.378) LE=0 LD=1.378 L=1.378
d (22,66,89; L=0.431) LE=0 LD=0.431 L=0.431
#32 (16,33,127; L=1.944) LE=0 LD=1.944 L=1.944
y (0,41,416; L=3.342)(882,40,952; L=4.572) LE=3.342 LD=4.572 L=7.915
o (138,165,303; L=0.876) LE=0 LD=0.876 L=0.876
u (12,550,573; L=0.059) LE=0 LD=0.059 L=0.059
#32 (41,4422,6906; L=0.643) LE=0 LD=0.643 L=0.643
w (4206,484,4734; L=3.289) LE=0 LD=3.289 L=3.289
a (26,253,632; L=1.320) LE=0 LD=1.320 L=1.320
n (60,198,269; L=0.442) LE=0 LD=0.442 L=0.442
t (142,726,869; L=0.259) LE=0 LD=0.259 L=0.259
#32 (26,539,753; L=0.482) LE=0 LD=0.482 L=0.482
t (702,473,1252; L=1.404) LE=0 LD=1.404 L=1.404
o (461,451,924; L=1.034) LE=0 LD=1.034 L=1.034
#32 (41,1860,2099; L=0.174) LE=0 LD=0.174 L=0.174
t (9835,2135,12542; L=2.554) LE=0 LD=2.554 L=2.554
a (31,187,2991; L=3.999) LE=0 LD=3.999 L=3.999
l (127,55,193; L=1.811) LE=0 LD=1.811 L=1.811
k (11,341,397; L=0.219) LE=0 LD=0.219 L=0.219
#32 (31,154,395; L=1.358) LE=0 LD=1.358 L=1.358
t (224,77,312; L=2.018) LE=0 LD=2.018 L=2.018
o (23,55,78; L=0.504) LE=0 LD=0.504 L=0.504
#32 (6,210,260; L=0.308) LE=0 LD=0.308 L=0.308
m (6898,484,12553; L=4.696) LE=0 LD=4.696 L=4.696
e (214,187,490; L=1.389) LE=0 LD=1.389 L=1.389
, (0,26,269; L=3.371)(101,80,652; L=3.026) LE=3.371 LD=3.026 L=6.397
...
В слове "Don't" на букву "t" ушло всего 0.064 бита! Рассматривать в таком виде логи не очень удобно, давайте лучше превратим их в трехмерный текст: по одной оси будет сам текст, по второй - число бит, потраченное на сам символ, по третьей - число бит, потраченное на escape. Эти две оси выразим цветом: синий цвет будет означать число бит, потраченное на сам символ, а красный - на escape. Чтобы покрасить пробелы, заменим их на "_". Буквы, которые были угаданы с первой попытки (без эскейпов), и на которые потрачено много бит, станут синими. Если много ушло на escape, но мало на сам символ - будет красным. Если много и туда, и туда, будет фиолетовым. Если же везде ушло мало, будет почти черным. Вот начало текста, а вот кусок ближе к концу:

Хорошо видно, какие части текста легко предсказуемы (черные), а какие сложнее. Трудно предсказать начало слова, особенно если начинается с большой буквы. Также неожиданности бывают, когда слово содержит префикс, известный как другое слово (the/there, black/blackness, etc.). В целом количество потраченных бит неплохо выражает степень "сюрприза" или неопределенности при кодировании символа. И эта неопреденность зависит от истории, от накопленной статистики, от состояния модели, другими словами.

Продолжение...

Post a comment in response:

This account has disabled anonymous posting.
If you don't have an account you can create one now.
HTML doesn't work in the subject.
More info about formatting