Часть 4. Вероятность ухода
Sep. 15th, 2011 11:25 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
thedeemon(начало цикла здесь)
В предыдущей части мы довольно простыми наблюдениями и соображениями пришли к алгоритму PPM. Большая часть данных в нем сжимается в длинных контекстах, в большинстве из которых встречается не так много различных символов. При этом очень важную роль играет псевдо-символ ухода, обозначающий все еще невстреченные в данном контексте символы. Если переоценить его вероятность, то часто встречающиеся в данном контексте символы будут иметь меньшую вероятность и будут сжаты хуже. Если же недооценить вероятность ухода, то при появлении новых символов в контексте на кодирование символа ухода уйдет слишком много бит. Нужно найти наиболее адекватную оценку вероятности ухода, но фактически это значит, что нам нужно оценить вероятность события, которое еще ни разу не наступало (вероятность встречи символа, который еще ни разу не встречался). Классический тервер тут бессилен. Можно поиграть в баесианца и применить правило Лапласа или другую оценку, основанную на произвольно выбранном априорном распределении вероятностей. Что мы имеем в каждый момент времени, это набор счетчиков для встреченных в данном контексте символов и счетчик для символа ухода. Пусть в данном контексте к некоторому моменту встретилось d различных символов и N символов всего. Если изначально положить счетчик уходов равным 1, а счетчики символов 0, и при встрече очередного символа увеличивать на 1 счетчик этого символа, то вероятность ухода получится 1/(N+1). В литературе этот метод назван методом А, а использующий его PPM соответственно PPMA. Если каждый раз, когда встречается новый символ, увеличивать также счетчик уходов, то оценка вероятности ухода получится d/(N+d). Такой метод обозначен в литературе буквой С, и общий алгоритм - PPMC. Но можно не гадать, а подойти более рационально: взять реальные данные и посмотреть статистику. Я написал маленькую программу, которая составляет статистику по всем контекстам заданной длины, и при встрече очередного символа смотрит количество различных символов в данном контексте d и общее число встреченных в нем символов N, и обновляет общую табличку, где для каждого сочетания (d,N) подсчитывается количство новых символов и старых символов. Т.е. подсчитывает вероятность встречи нового символа для каждого значения пары (d, N). Получилось что-то такое:
Матрица треугольная, т.к. d <= N, число различных символов не больше числа всех символов.
Какое выражение с d и N дает значения, больше всего похожие на полученные тут? Очень простое:
d / 2N
Такой метод оценки тоже описан в литературе и носит имя D, а общий алгоритм с ним - PPMD. Важно заметить, что этот PPMD - совсем не тот PPMd, который используется сейчас в rar'e и 7zip'e в режимах максимального сжатия. Авторы статьи про PPM в педивикии этого не знают. Для реализации PPMD нужно при появлении в контексте нового символа увеличивать его счетчик и счетчик уходов на 1, а при появлении уже известного символа увеличивать его счетчик на 2, а счетчик уходов не трогать. В прошлой части я писал, что в демонстрационном компрессоре поигрался с этими константами, и результат, который сжимал лучше PPMD, получился при увеличении счетчика символа на 11, а счетчика уходов на 5, при начальном значении счетчика уходов равным 6. Т.е. оценка вероятности ухода получилась приблизительно такая:
5d / (11N + 5d)
Подобные априорные оценки вероятности ухода как-то работают, но явно неоптимально. Стоит попытаться их улучшить. Если при кодировании файла для каждого символа записать в лог 1, если он был угадан с первого раза (т.е. уже был в самом длинном найденном контексте), и 0, если для его кодирования пришлось использовать символ ухода и переходить к более короткому контексту, то получим для hhguide.txt такую последовательность в начале:
11111111111010111110111101001011101000100010100001011101010001000011100000101000001000101001001111110001000000001000101000010000110100100100100111111100000000001000100...
и такую ближе к концу:
...100100000011111111001101111111111111111101001111111111111111111111111001111111001001111111111100111111111111110011111111111111111111101111101011111111111111111111111111111111111001111111111111111110101110
Если посчитать, как часто встречается 0 сразу после 0 и 0 сразу после 1, то вероятности получатся очень разные: если предыдущий символ был угадан сразу (т.е. без эскейпов), то вероятность эскейпа для текущего символа всего 13%, если же предыдущий символ был закодирован с эскейпами, то вероятность эскейпа для текущего уже 42%. Т.е. как минимум вероятность ухода зависит не только от d и N, но и от истории. Казалось бы, мы уже учли историю, т.к. d и N берутся из статистики для данного контекста (Nesc и total). Но сводить все только к d и N получается неоптимально: если у нас в контексте встречено 3 различных символа и 5 символов всего, то в начале файла это может означать, что другие символы еще просто не успели встретиться, а ближе к концу файла это может означать, что в данном контексте другие символы скорее всего и не встречаются вовсе, поэтому в начале и в конце файла вероятность ухода может быть очень разной при тех же самых d и N. Чтобы задействовать это наблюдение, можно попытаться как-то классифицировать контексты и при оценке вероятности ухода для текущего контекста смотреть на накопленную статистику других похожих контекстов. Т.е. для символа ухода создается своя особенная модель, где на входе могут быть характеристики текущего контекста (d и N), характеристики его родителей, история кодирования недавних символов и пр., а на выходе - уточненная вероятность ухода. Такой подход носит название SEE - Secondary Escape Estimation. В алгоритме PPMd он развит очень сильно. Там отдельно обрабатываются детерминированные контексты, отдельно контексты, где часть символов исключена маской и отдельно недетерминированные незамаскированные. В модели помимо d и N учитываются число символов в родительском контексте, оценка вероятности предыдущего символа, пара верхних бит предыдущего символа, число закодированных подряд без эскейпов недавних символов, число незамаскированных символов в контексте, число потенциально замаскированных в родительском контексте и пр. Довольно сложная модель, но дающая довольно хороший результат.
Для демонстрационных целей я применил намного более простую схему. У нас есть априорная оценка вероятности ухода ~ 5d / (11N + 5d), получаемая увеличением счетчиков. Она по контексту дает нам некую величину Pesc. Предположим, что эта оценка имеет системную ошибку и выдает для каких-то контекстов, например, 0.23 там, где "правильное" значение 0.26. Тогда можно ее квантовать до некоторого количества дискретных значений и сделать специальную таблицу, в которой нашу оценку вероятности использовать в качестве индекса, а в ячейках таблицы иметь счетчики того, сколько раз при такой оценке на самом деле произошел уход из контекста, а сколько - был встречен знакомый символ. Эта таблица будет mapping'ом предполагаемой вероятности на реальную. Изначально запишем в нее пары (k, N-k), где N - размер таблицы. Тогда, например, если мы квантуем до 100 значений, нам 1000 раз модель выдала оценку вероятности ухода 0.34, при этом из этой тысячи 310 раз произошел уход, а 690 раз был встречен знакомый символ, то изначально в 34-й ячейке было (34,66), а после 1000 инкрементов там будет (34+310, 66+690) = (344, 756), и скорректированная вероятность ухода получится 344 / (344 + 756) = 0.3127. Нетрудно видеть, что если оценка вероятности правильная, то скорректированное значение будет совпадать с входным. Если же оценка ошибочная, то ошибка будет исправляться по мере накопления статистики. Такая коррекция вероятностей носит название SSE - Secondary Symbol Estimation и может применяться не только к символам ухода, но и ко всем остальным. Сделав такую таблицу на 129 значений и прогнав один из тестовых текстов, мы получим такой ее вид:
Где-то оценка вероятности вполне адекватна, но местами хорошо заметны пики, где есть явные отличия априорной оценки от реальной вероятности. Если посмотреть, где они, можно узнать вполне характерные вероятности, которые получаются в самых молодых контекстах (которые встречались 1 или несколько раз). Самый большой пик соотвествует как раз оценке, выдаваемой контекстом, в котором всего один символ, встреченный один раз. И в этом есть логика: в молодых контекстах еще слишком мало информации, чтобы нормально предсказать вероятность ухода. Давайте разделим таблицу на две: одну для молодых контекстов (где общее число символов меньше некоторого порога), и вторую для более зрелых. Кроме того, мы видели раньше, что вероятность ухода сильно зависит от того, был ли уход при кодировании предыдущего символа. Еще можно предположить, что априорная оценка для детерминированных контекстов (где встречался всего один символ один или более раз) может быть неточной/ошибочной, но эту коррекцию ее ошибки не стоит распространять на более зрелые и разнообразные контексты. Так все контексты мы разделим на 8 классов: по признаку молодости, детерминированности и наличия уходов при кодировании предыдущего символа. Посмотрим на их статистику:
Видим, что разные классы контекстов действительно имеют разную статистику, разные ошибки. Большой пик наверху характерен для молодых детерминированных контекстов. Для старых недетерминированных характерно проседание в начале и середине, т.е. реальная вероятность ухода там меньше априорной ее оценки. Причем если предыдущий символ был угадан без уходов, то вероятность ухода текущего символа заметно меньше, чем если у предыдущего символа был уход. Некоторые же классы контекстов предсказываются довольно хорошо, и для них скорректированная вероятность совпадает с априорной (их график лежит на прямой y=x).
Как применить такую коррекцию оценки вероятности ухода для сжатия? При кодировании очередного символа мы получаем серию интервалов (1 или более), кодирующих 0 или более уходов и сам символ. Каждый такой интервал получается из статистики некоторого контекста, в которой есть счетчик Nesc (или просто ne) символов ухода и счетчики реальных символов, сумму которых обозначим nc. Вероятность ухода получается равной ne/(ne+nc). С ней мы можем заглянуть в таблицу корректировки и получить новую вероятность P. Теперь нужно получить новое значение ne2, такое что ne2/(ne2 + nc) = P. Но есть два нюанса: поскольку все счетчики - целые числа, то если ne и nc малы, минимальное изменение ne (на 1) дает очень резкое изменение ne/(ne+nc). Поэтому в этом случае следует увеличить все счетчики в несколько раз, а потом уже корректировать ne. Другой нюанс в том, что если в ходе корректировки ne увеличится, то ne+nc может превысить максимально разрешенное значение (оно должно быть меньше минимального значения рабочего интервала range coder'a). В этом случае нужно все счетчики масштабировать вниз. В итоге мы сделаем функцию, которая, используя информацию о контексте (ne, nc) и историю кодирования предыдущего символа, корректирует переданный ей интервал (cumFreq, freq, totFreq). Скорректированный интервал уже будем передавать range coder'у. Применение такой переоценки вероятности ухода позволило еще немного улучшить сжатие и сжать те два файла до 218736 и 76603 байт.
Вот как выглядит получившееся решение на языке Clean. Функция ppm_compress получает строку с исходными данными и выдает строку со сжатыми данными.
Главный цикл - пробег по исходной строке в foldArray, для каждого символа определяется строка-контекст cx длины не больше Order (4), маска (для symbol exclusion) заполняется единицами, дальше текущий символ с учетом его контекста и дерева контекстов tr оценивается, превращаясь в серию интервалов, которые по одному передаются в encodeInterv, где они переоцениваются описанным выше способом, скармливаются range coder'у, после чего статистика в таблице веронятностей уходов etab обновляется. Признак success того, что символ угадан с первого раза без уходов становится контекстом ухода prev_succ для следующего символа. Статистика в дереве контекстов обновляется прямо во время оценки символа, поэтому вместе с интервалами возвращается и обновленное дерево контекстов. Исходное содержимое дерева - baseTree, в нем один корневой контекст с единицами для всех возможных символов и нулевой вероятностью ухода.
Функция декодирования ppm_decompress получает строку со сжатыми данными и длину исходного несжатого сообщения (она сохраняется в файле), возвращая строку разжатых данных этой длины.
Главный цикл заполняет выходной буфер символ за символом. Для каждого символа заполняется единицами маска, символ декодируется, используя текущее состояние range coder'a, контекст и дерево контекстов, обновляется строка-контекст, обновляется статистика в дереве контекстов.
Поскольку дерево контекстов описано вариантным типом (листья, узлы с одной ветвью, узлы с множеством ветвей), но смысл действий для всех вариантов один, я приведу лишь наиболее общий код - для варианта со множеством ветвей. Оценка символа серией интервалов при сжатии выглядит так:
Нам нужно найти в дереве контекстов самый длинный подходящий контекст. Строка-контекст передается в cx, позиция в ней в аргументе ci. Если мы дошли до левого конца строки (ci < 0), то это самый длинный контекст, мы получаем интервал из статистики данного контекста st и обновляем ее, передав текущий символ и флаг того, найден он в данном контексте или нет. Если же в строке контекста еще можно сдвинуться влево, т.е. может быть более длинный контекст, то смотрим, есть ли у нас в массиве дочерних контекстов (которые на символ длиннее текущего) ветвь в ячейке с индексом, соответсвующему очередному символу контекста. Массив этот содержит уникальные значения, поэтому мы не можем просто так прочитать нужное значение в какую-то переменную - это нарушит уникальность. Мы можем лишь извлечь уникальный элемент массива, положив вместо него что-то взамен. Мы это делаем, положив в замен Nothing, и смотрим, что получили: если это Nothing, то такой ветви у данного узла нет, поэтому текущий контекст - самый длинный подходящий из имеющихся в дереве, хоть он и короче переданной строки-контекста. Мы достраиваем ветвь дерева так, чтобы весь контекст теперь в нем содержался, оцениваем символ статистикой текущего контекста и возвращаем полученные сведения вместе с обновленным поддеревом. Если же ветка была найдена, т.е. в дереве есть более длинный подходящий контекст, то рекурсивно вызываем оценку символа в той ветви, сдвинув позицию в строке-контексте на один влево. Оценка символа в поддереве вернет признак успеха (найден символ там или нет), список интервалов, обновленную маску и обновленное поддерево. Это поддерево мы записываем на его позицию в массиве поддеревьев, а дальше в зависимости от того, был ли найден кодируемый символ в более длинных контекстах (т.е. в поддереве), два варианта. Если найден, то возвращаем найденное. Если не найден, то пытаемся оценить его в текущем контексте, обновляем статистику и результат оценки в текущем контексте присоединяем к списку интервалов, полученных при его оценке более длинными контекстами.
Декодирование символа аналогично обходит дерево контекстов рекурсивно. Мы не можем сразу при этом обходе обновлять статистику в нем, т.к. оценка идет от длинных контекстов к коротким, и первые несколько результатов могут быть символами ухода, и там мы еще не знаем какой символ будет декодирован. Поэтому мы запоминаем, на какой глубине дерева был в конечном итоге декодирован символ (не escape) и потом обновляем дерево отдельным проходом в updateTree. Кроме того, мы не можем так разделить оценку символа интервалами и их переоценку, т.к. чтобы получить очередной интервал мы должны передать range coder'у текущий, поэтому надо сразу знать их скорректированные значения.
Обновление дерева, когда известен декодированный символ и глубина, на которой он был декодирован:
На меньшей глубине мы статистику не обновляем - это update exclusion.
Код получения интервалов из статистики и их обновления я не привожу, он вполне тривиален. Полный проект со всеми исходниками и ехе-шником можно взять здесь: entropical.zip Там около 700 строк на Clean, а размер бинарника всего сотня кб.
Помимо описанного выше, в компрессоре применен еще один способ повысить сжатие. Когда человек читает текст, он понимает, что "Hello" и "hello" - одно и то же слово. Но для компрессора это совсем разные слова, в них получаются разные контексты. Что, конечно, ведет к неоптимальности сжатия. Можно научить компрессор распознавать тексты и проводить над данными трансформацию. В данном случае, заменять одиночные заглавные буквы на пару из спец-символа и маленькой буквы. Так многие слова окажутся лишь в одном виде, их статистики сольются и общее сжатие слегка подрастет, несмотря на то, что объем сжимаемых данных увеличится. В серьезных компрессорах подобных трансформаций бывает довольно много. Например, в исполняемых файлах заменяют относительные адреса переходов абсолютными (так больше повторов), записанными в big-endian (так часть адреса и команда перехода сливаются в одно "слово"). Будем считать английским текстом данные, где не встречается 0 (мы будем его использовать для спец-символа), и количество букв составляет более половины всего содержания:
Трансформация заглавных букв:
Флаг использовалась трансформация или нет будем хранить в верхней половине первого байта сжатых данных (в силу особенностей нашего алгоритма первый байт всегда 0 или 1). С такой трансформацией тестовые файлы сжались до 218590 и 76292 байт. Сравним это с "конкурентами":
Тут rar и 7zip использовались в их режимах по умолчанию. В режимах максимального сжатия они используют PPMd, который позволяет сжать до 203653 и 70591, так что рекорда мы тут не поставили, но для простого демонстрационного компрессора по-моему неплохо. Чтобы убедиться, что мы не слишком узко заточились на два тестовых файла, возьмем классический тестовый набор Calgary Corpus, на нем суммарный размер сжатых файлов выглядит так:
Продолжение...
В предыдущей части мы довольно простыми наблюдениями и соображениями пришли к алгоритму PPM. Большая часть данных в нем сжимается в длинных контекстах, в большинстве из которых встречается не так много различных символов. При этом очень важную роль играет псевдо-символ ухода, обозначающий все еще невстреченные в данном контексте символы. Если переоценить его вероятность, то часто встречающиеся в данном контексте символы будут иметь меньшую вероятность и будут сжаты хуже. Если же недооценить вероятность ухода, то при появлении новых символов в контексте на кодирование символа ухода уйдет слишком много бит. Нужно найти наиболее адекватную оценку вероятности ухода, но фактически это значит, что нам нужно оценить вероятность события, которое еще ни разу не наступало (вероятность встречи символа, который еще ни разу не встречался). Классический тервер тут бессилен. Можно поиграть в баесианца и применить правило Лапласа или другую оценку, основанную на произвольно выбранном априорном распределении вероятностей. Что мы имеем в каждый момент времени, это набор счетчиков для встреченных в данном контексте символов и счетчик для символа ухода. Пусть в данном контексте к некоторому моменту встретилось d различных символов и N символов всего. Если изначально положить счетчик уходов равным 1, а счетчики символов 0, и при встрече очередного символа увеличивать на 1 счетчик этого символа, то вероятность ухода получится 1/(N+1). В литературе этот метод назван методом А, а использующий его PPM соответственно PPMA. Если каждый раз, когда встречается новый символ, увеличивать также счетчик уходов, то оценка вероятности ухода получится d/(N+d). Такой метод обозначен в литературе буквой С, и общий алгоритм - PPMC. Но можно не гадать, а подойти более рационально: взять реальные данные и посмотреть статистику. Я написал маленькую программу, которая составляет статистику по всем контекстам заданной длины, и при встрече очередного символа смотрит количество различных символов в данном контексте d и общее число встреченных в нем символов N, и обновляет общую табличку, где для каждого сочетания (d,N) подсчитывается количство новых символов и старых символов. Т.е. подсчитывает вероятность встречи нового символа для каждого значения пары (d, N). Получилось что-то такое:
Матрица треугольная, т.к. d <= N, число различных символов не больше числа всех символов.
Какое выражение с d и N дает значения, больше всего похожие на полученные тут? Очень простое:
d / 2N
Такой метод оценки тоже описан в литературе и носит имя D, а общий алгоритм с ним - PPMD. Важно заметить, что этот PPMD - совсем не тот PPMd, который используется сейчас в rar'e и 7zip'e в режимах максимального сжатия. Авторы статьи про PPM в педивикии этого не знают. Для реализации PPMD нужно при появлении в контексте нового символа увеличивать его счетчик и счетчик уходов на 1, а при появлении уже известного символа увеличивать его счетчик на 2, а счетчик уходов не трогать. В прошлой части я писал, что в демонстрационном компрессоре поигрался с этими константами, и результат, который сжимал лучше PPMD, получился при увеличении счетчика символа на 11, а счетчика уходов на 5, при начальном значении счетчика уходов равным 6. Т.е. оценка вероятности ухода получилась приблизительно такая:
5d / (11N + 5d)
Подобные априорные оценки вероятности ухода как-то работают, но явно неоптимально. Стоит попытаться их улучшить. Если при кодировании файла для каждого символа записать в лог 1, если он был угадан с первого раза (т.е. уже был в самом длинном найденном контексте), и 0, если для его кодирования пришлось использовать символ ухода и переходить к более короткому контексту, то получим для hhguide.txt такую последовательность в начале:
11111111111010111110111101001011101000100010100001011101010001000011100000101000001000101001001111110001000000001000101000010000110100100100100111111100000000001000100...
и такую ближе к концу:
...100100000011111111001101111111111111111101001111111111111111111111111001111111001001111111111100111111111111110011111111111111111111101111101011111111111111111111111111111111111001111111111111111110101110
Если посчитать, как часто встречается 0 сразу после 0 и 0 сразу после 1, то вероятности получатся очень разные: если предыдущий символ был угадан сразу (т.е. без эскейпов), то вероятность эскейпа для текущего символа всего 13%, если же предыдущий символ был закодирован с эскейпами, то вероятность эскейпа для текущего уже 42%. Т.е. как минимум вероятность ухода зависит не только от d и N, но и от истории. Казалось бы, мы уже учли историю, т.к. d и N берутся из статистики для данного контекста (Nesc и total). Но сводить все только к d и N получается неоптимально: если у нас в контексте встречено 3 различных символа и 5 символов всего, то в начале файла это может означать, что другие символы еще просто не успели встретиться, а ближе к концу файла это может означать, что в данном контексте другие символы скорее всего и не встречаются вовсе, поэтому в начале и в конце файла вероятность ухода может быть очень разной при тех же самых d и N. Чтобы задействовать это наблюдение, можно попытаться как-то классифицировать контексты и при оценке вероятности ухода для текущего контекста смотреть на накопленную статистику других похожих контекстов. Т.е. для символа ухода создается своя особенная модель, где на входе могут быть характеристики текущего контекста (d и N), характеристики его родителей, история кодирования недавних символов и пр., а на выходе - уточненная вероятность ухода. Такой подход носит название SEE - Secondary Escape Estimation. В алгоритме PPMd он развит очень сильно. Там отдельно обрабатываются детерминированные контексты, отдельно контексты, где часть символов исключена маской и отдельно недетерминированные незамаскированные. В модели помимо d и N учитываются число символов в родительском контексте, оценка вероятности предыдущего символа, пара верхних бит предыдущего символа, число закодированных подряд без эскейпов недавних символов, число незамаскированных символов в контексте, число потенциально замаскированных в родительском контексте и пр. Довольно сложная модель, но дающая довольно хороший результат.
Для демонстрационных целей я применил намного более простую схему. У нас есть априорная оценка вероятности ухода ~ 5d / (11N + 5d), получаемая увеличением счетчиков. Она по контексту дает нам некую величину Pesc. Предположим, что эта оценка имеет системную ошибку и выдает для каких-то контекстов, например, 0.23 там, где "правильное" значение 0.26. Тогда можно ее квантовать до некоторого количества дискретных значений и сделать специальную таблицу, в которой нашу оценку вероятности использовать в качестве индекса, а в ячейках таблицы иметь счетчики того, сколько раз при такой оценке на самом деле произошел уход из контекста, а сколько - был встречен знакомый символ. Эта таблица будет mapping'ом предполагаемой вероятности на реальную. Изначально запишем в нее пары (k, N-k), где N - размер таблицы. Тогда, например, если мы квантуем до 100 значений, нам 1000 раз модель выдала оценку вероятности ухода 0.34, при этом из этой тысячи 310 раз произошел уход, а 690 раз был встречен знакомый символ, то изначально в 34-й ячейке было (34,66), а после 1000 инкрементов там будет (34+310, 66+690) = (344, 756), и скорректированная вероятность ухода получится 344 / (344 + 756) = 0.3127. Нетрудно видеть, что если оценка вероятности правильная, то скорректированное значение будет совпадать с входным. Если же оценка ошибочная, то ошибка будет исправляться по мере накопления статистики. Такая коррекция вероятностей носит название SSE - Secondary Symbol Estimation и может применяться не только к символам ухода, но и ко всем остальным. Сделав такую таблицу на 129 значений и прогнав один из тестовых текстов, мы получим такой ее вид:
Где-то оценка вероятности вполне адекватна, но местами хорошо заметны пики, где есть явные отличия априорной оценки от реальной вероятности. Если посмотреть, где они, можно узнать вполне характерные вероятности, которые получаются в самых молодых контекстах (которые встречались 1 или несколько раз). Самый большой пик соотвествует как раз оценке, выдаваемой контекстом, в котором всего один символ, встреченный один раз. И в этом есть логика: в молодых контекстах еще слишком мало информации, чтобы нормально предсказать вероятность ухода. Давайте разделим таблицу на две: одну для молодых контекстов (где общее число символов меньше некоторого порога), и вторую для более зрелых. Кроме того, мы видели раньше, что вероятность ухода сильно зависит от того, был ли уход при кодировании предыдущего символа. Еще можно предположить, что априорная оценка для детерминированных контекстов (где встречался всего один символ один или более раз) может быть неточной/ошибочной, но эту коррекцию ее ошибки не стоит распространять на более зрелые и разнообразные контексты. Так все контексты мы разделим на 8 классов: по признаку молодости, детерминированности и наличия уходов при кодировании предыдущего символа. Посмотрим на их статистику:
Видим, что разные классы контекстов действительно имеют разную статистику, разные ошибки. Большой пик наверху характерен для молодых детерминированных контекстов. Для старых недетерминированных характерно проседание в начале и середине, т.е. реальная вероятность ухода там меньше априорной ее оценки. Причем если предыдущий символ был угадан без уходов, то вероятность ухода текущего символа заметно меньше, чем если у предыдущего символа был уход. Некоторые же классы контекстов предсказываются довольно хорошо, и для них скорректированная вероятность совпадает с априорной (их график лежит на прямой y=x).
Как применить такую коррекцию оценки вероятности ухода для сжатия? При кодировании очередного символа мы получаем серию интервалов (1 или более), кодирующих 0 или более уходов и сам символ. Каждый такой интервал получается из статистики некоторого контекста, в которой есть счетчик Nesc (или просто ne) символов ухода и счетчики реальных символов, сумму которых обозначим nc. Вероятность ухода получается равной ne/(ne+nc). С ней мы можем заглянуть в таблицу корректировки и получить новую вероятность P. Теперь нужно получить новое значение ne2, такое что ne2/(ne2 + nc) = P. Но есть два нюанса: поскольку все счетчики - целые числа, то если ne и nc малы, минимальное изменение ne (на 1) дает очень резкое изменение ne/(ne+nc). Поэтому в этом случае следует увеличить все счетчики в несколько раз, а потом уже корректировать ne. Другой нюанс в том, что если в ходе корректировки ne увеличится, то ne+nc может превысить максимально разрешенное значение (оно должно быть меньше минимального значения рабочего интервала range coder'a). В этом случае нужно все счетчики масштабировать вниз. В итоге мы сделаем функцию, которая, используя информацию о контексте (ne, nc) и историю кодирования предыдущего символа, корректирует переданный ей интервал (cumFreq, freq, totFreq). Скорректированный интервал уже будем передавать range coder'у. Применение такой переоценки вероятности ухода позволило еще немного улучшить сжатие и сжать те два файла до 218736 и 76603 байт.
Вот как выглядит получившееся решение на языке Clean. Функция ppm_compress получает строку с исходными данными и выдает строку со сжатыми данными.
Order :== 4
baseTree = Leaf (StLarge ones 0 256) where
ones = createArray 256 1
ppm_compress :: {#Char} -> .{#Char}
ppm_compress text = finishEncode rc where
rc0 = newEncoder (20 + size text)
tr0 :: *ContextTree
tr0 = baseTree
(rc,tr,_,_,_,etab) = foldArray encodeSymb (rc0,tr0,"",mask0, 1, etab0) text
mask0 = createArray 256 1
etab0 = mk_etab
encodeSymb (rc,tr,cx,mask, prev_succ, etab) c
# cxlen = size cx
# cx = (if (cxlen < Order+1) cx (cx % (1, cxlen)) ) +++ {c}
#! mask = { mask & [i] = 1 \\ i <- [0..255]}
# (found, est_list, mask, tr) = estimateSymbol c cx (size cx - 2) mask tr
# success = if (length est_list == 1) 1 0
# (rc,etab,_) = foldr encodeInterv (rc,etab,prev_succ) est_list
= (rc, tr, cx, mask, success, etab)
encodeInterv ival=:(cf,fr,tf, ne,found) (rc,etab,ecx)
#! ((cumFreq, freq, totFreq),etab) = reestimateEsc ecx etab ival
#! rc = encode rc cumFreq freq totFreq
#! etab = updEscN ne (tf-ne) ecx etab (not found)
= (rc,etab,ecx)
Главный цикл - пробег по исходной строке в foldArray, для каждого символа определяется строка-контекст cx длины не больше Order (4), маска (для symbol exclusion) заполняется единицами, дальше текущий символ с учетом его контекста и дерева контекстов tr оценивается, превращаясь в серию интервалов, которые по одному передаются в encodeInterv, где они переоцениваются описанным выше способом, скармливаются range coder'у, после чего статистика в таблице веронятностей уходов etab обновляется. Признак success того, что символ угадан с первого раза без уходов становится контекстом ухода prev_succ для следующего символа. Статистика в дереве контекстов обновляется прямо во время оценки символа, поэтому вместе с интервалами возвращается и обновленное дерево контекстов. Исходное содержимое дерева - baseTree, в нем один корневой контекст с единицами для всех возможных символов и нулевой вероятностью ухода.
Функция декодирования ppm_decompress получает строку со сжатыми данными и длину исходного несжатого сообщения (она сохраняется в файле), возвращая строку разжатых данных этой длины.
ppm_decompress :: {#Char} !Int -> .{#Char}
ppm_decompress compressed len = decloop 0 rc0 tr0 buf0 mask0 "" 1 etab0 where
rc0 = newDecoder compressed
buf0 :: *{#Char}
buf0 = createArray len '-'
tr0 = baseTree
etab0 = mk_etab
mask0 = createArray 256 1
decloop pos rc tr buf mask cx ecx etab
| pos >= len = buf
#! mask = { mask & [i] = 1 \\ i <- [0..255]}
# (rc, symb, depth, escn, mask, etab, tr) = decodeSymbol rc cx (size cx - 1) 0 mask ecx etab tr
# success = if (escn == 0) 1 0
# c = toChar symb
# buf & [pos] = c
# cx = cx +++ {c}
# cxlen = size cx
# tr = updateTree c cx (cxlen - 2) depth tr
# cx = (if (cxlen <= Order) cx (cx % (1, cxlen)) )
= decloop (pos+1) rc tr buf mask cx success etab
Главный цикл заполняет выходной буфер символ за символом. Для каждого символа заполняется единицами маска, символ декодируется, используя текущее состояние range coder'a, контекст и дерево контекстов, обновляется строка-контекст, обновляется статистика в дереве контекстов.
Поскольку дерево контекстов описано вариантным типом (листья, узлы с одной ветвью, узлы с множеством ветвей), но смысл действий для всех вариантов один, я приведу лишь наиболее общий код - для варианта со множеством ветвей. Оценка символа серией интервалов при сжатии выглядит так:
estimateSymbol :: !Char !{#Char} !Int !*{#Int} !*ContextTree -> *(Bool,[(!Int,!Int,!Int,!Int,!Bool)],.{#Int},*ContextTree)
estimateSymbol c cx ci mask (LargeNode st chld_arr)
| ci < 0
# (found, cumFreq, freq, totFreq, ne, mask, st) = getSymbInfo c mask st
# st = incrCount c found st
= (found, [(cumFreq, freq, totFreq, ne,found)], mask, LargeNode st chld_arr)
#! chi = toInt cx.[ci]
#! (chld, chld_arr) = replace chld_arr chi Nothing
= case chld of
Nothing
# br = createBranch cx ci
# chld_arr & [chi] = br
# (found, cumFreq, freq, totFreq, ne, mask, st) = getSymbInfo c mask st
# st = incrCount c found st
# tr = LargeNode st chld_arr
= (found, [(cumFreq, freq, totFreq, ne,found)], mask, tr)
chld_tree
# (found, est_list, mask, chld_tree) = estimateSymbol c cx (ci-1) mask chld_tree
# chld_arr & [chi] = chld_tree
| found
//# st = incrCount c found st //update exclusion
# tr = LargeNode st chld_arr
= (found, est_list, mask, tr)
//symbol not found in higher order context (child), est_list contains Esc estimations
# (found, cumFreq, freq, totFreq, ne, mask, st) = getSymbInfo c mask st
# st = incrCount c found st
# tr = LargeNode st chld_arr
= (found, [(cumFreq, freq, totFreq, ne,found) : est_list], mask, tr)
Нам нужно найти в дереве контекстов самый длинный подходящий контекст. Строка-контекст передается в cx, позиция в ней в аргументе ci. Если мы дошли до левого конца строки (ci < 0), то это самый длинный контекст, мы получаем интервал из статистики данного контекста st и обновляем ее, передав текущий символ и флаг того, найден он в данном контексте или нет. Если же в строке контекста еще можно сдвинуться влево, т.е. может быть более длинный контекст, то смотрим, есть ли у нас в массиве дочерних контекстов (которые на символ длиннее текущего) ветвь в ячейке с индексом, соответсвующему очередному символу контекста. Массив этот содержит уникальные значения, поэтому мы не можем просто так прочитать нужное значение в какую-то переменную - это нарушит уникальность. Мы можем лишь извлечь уникальный элемент массива, положив вместо него что-то взамен. Мы это делаем, положив в замен Nothing, и смотрим, что получили: если это Nothing, то такой ветви у данного узла нет, поэтому текущий контекст - самый длинный подходящий из имеющихся в дереве, хоть он и короче переданной строки-контекста. Мы достраиваем ветвь дерева так, чтобы весь контекст теперь в нем содержался, оцениваем символ статистикой текущего контекста и возвращаем полученные сведения вместе с обновленным поддеревом. Если же ветка была найдена, т.е. в дереве есть более длинный подходящий контекст, то рекурсивно вызываем оценку символа в той ветви, сдвинув позицию в строке-контексте на один влево. Оценка символа в поддереве вернет признак успеха (найден символ там или нет), список интервалов, обновленную маску и обновленное поддерево. Это поддерево мы записываем на его позицию в массиве поддеревьев, а дальше в зависимости от того, был ли найден кодируемый символ в более длинных контекстах (т.е. в поддереве), два варианта. Если найден, то возвращаем найденное. Если не найден, то пытаемся оценить его в текущем контексте, обновляем статистику и результат оценки в текущем контексте присоединяем к списку интервалов, полученных при его оценке более длинными контекстами.
Декодирование символа аналогично обходит дерево контекстов рекурсивно. Мы не можем сразу при этом обходе обновлять статистику в нем, т.к. оценка идет от длинных контекстов к коротким, и первые несколько результатов могут быть символами ухода, и там мы еще не знаем какой символ будет декодирован. Поэтому мы запоминаем, на какой глубине дерева был в конечном итоге декодирован символ (не escape) и потом обновляем дерево отдельным проходом в updateTree. Кроме того, мы не можем так разделить оценку символа интервалами и их переоценку, т.к. чтобы получить очередной интервал мы должны передать range coder'у текущий, поэтому надо сразу знать их скорректированные значения.
decodeSymbol :: *RCState {#Char} !Int !Int *{#.Int} EscCtx *EscTab *ContextTree -> *(*RCState,!Int,!Int,!Int,*{#Int},.EscTab,*ContextTree)
decodeSymbol rc cx ci depth mask ecx etab tr=:(LargeNode st chld_arr)
| ci < 0
# (rc, symb, mask, st, etab) = decodeSymbolWithStats rc mask st ecx etab
= (rc, symb, depth, (if (symb >= 0) 0 1), mask, etab, LargeNode st chld_arr)
#! chi = toInt cx.[ci]
#! (chld, chld_arr) = replace chld_arr chi Nothing
= case chld of
Nothing
# (rc, symb, mask, st, etab) = decodeSymbolWithStats rc mask st ecx etab
= (rc, symb, depth, (if (symb >= 0) 0 1), mask, etab, LargeNode st chld_arr)
chld_tree
# (rc, symb, dpt,escn, mask, etab, ch_tr) = decodeSymbol rc cx (ci-1) (depth+1) mask ecx etab chld_tree
# chld_arr & [chi] = ch_tr //put back wat was replace'd just before the case
| symb >=0 = (rc, symb, dpt,escn, mask, etab, LargeNode st chld_arr)
# (rc, symb, mask, st, etab) = decodeSymbolWithStats rc mask st ecx etab
= (rc, symb, depth, escn + (if (symb >= 0) 0 1), mask, etab, LargeNode st chld_arr)
decodeSymbolWithStats :: *RCState *{#.Int} *Stats EscCtx *EscTab -> *(*RCState,!Int,.{#Int},*Stats,.EscTab)
decodeSymbolWithStats rc mask st ecx etab
#! (mask, st, nc, ne) = getTotFreq mask st
#! (neSd, ncSd, shift, etab) = getEscN ne nc ecx etab
#! totFr = neSd + ncSd
#! (valSd, rc) = getFreq rc totFr
#! val = if (valSd < neSd) 0 (rot (valSd - neSd) (~shift) + ne)
#! (symb, cumFr, fr, mask, st) = findSymbByVal val mask st
#! esc = symb < 0
#! freq = if esc neSd (rot fr shift)
#! cumFreq = if esc 0 (rot (cumFr - ne) shift + neSd)
#! etab = updEscN ne nc ecx etab esc
#! rc = decode rc cumFreq freq
= (rc, symb, mask, st, etab)
Обновление дерева, когда известен декодированный символ и глубина, на которой он был декодирован:
updateTree :: !Char {#Char} !Int !Int !*ContextTree -> *ContextTree
updateTree c cx ci depth (LargeNode st chld_arr)
# found = depth >= 0
# st = if (depth <= 0) (incrCount c found st) st
| ci < 0 = LargeNode st chld_arr
#! chi = toInt cx.[ci]
#! (chld, chld_arr) = replace chld_arr chi Nothing
# ch_tr = case chld of
Nothing = createBranch cx ci
ch_tree = updateTree c cx (ci-1) (depth-1) ch_tree
# chld_arr & [chi] = ch_tr
= LargeNode st chld_arr
На меньшей глубине мы статистику не обновляем - это update exclusion.
Код получения интервалов из статистики и их обновления я не привожу, он вполне тривиален. Полный проект со всеми исходниками и ехе-шником можно взять здесь: entropical.zip Там около 700 строк на Clean, а размер бинарника всего сотня кб.
Помимо описанного выше, в компрессоре применен еще один способ повысить сжатие. Когда человек читает текст, он понимает, что "Hello" и "hello" - одно и то же слово. Но для компрессора это совсем разные слова, в них получаются разные контексты. Что, конечно, ведет к неоптимальности сжатия. Можно научить компрессор распознавать тексты и проводить над данными трансформацию. В данном случае, заменять одиночные заглавные буквы на пару из спец-символа и маленькой буквы. Так многие слова окажутся лишь в одном виде, их статистики сольются и общее сжатие слегка подрастет, несмотря на то, что объем сжимаемых данных увеличится. В серьезных компрессорах подобных трансформаций бывает довольно много. Например, в исполняемых файлах заменяют относительные адреса переходов абсолютными (так больше повторов), записанными в big-endian (так часть адреса и команда перехода сливаются в одно "слово"). Будем считать английским текстом данные, где не встречается 0 (мы будем его использовать для спец-символа), и количество букв составляет более половины всего содержания:
is_text :: .{#Char} -> Bool
is_text str = no_zero && nletters > (size str)/2 where
cnts0 :: *{#Int}
cnts0 = createArray 256 0
cnts = foldArray count cnts0 str
no_zero = cnts.[0]==0
nletters = sum [cnts.[i] \\ i<-[65..122]]
count cnts c
#! i = toInt c
#! old = cnts.[i]
= {cnts & [i] = old+1 }
Трансформация заглавных букв:
text_transform trans text :== {c \\ c <- trans src_list} where
src_list = [c \\ c <-: text]
is_cap c = c>='A' && c<='Z'
decap c = toChar (toInt c + 32)
cap c = toChar (toInt c - 32)
transform_caps :: {#Char} -> {#Char}
transform_caps text = text_transform f text where
f :: [Char] -> [Char]
f [] = []
f [c : d : rest] | is_cap c && not (is_cap d) = [z : decap c : d : f rest]
f [c : rest] = [c : f rest]
z = toChar 0
inverse_transform_caps :: {#Char} -> {#Char}
inverse_transform_caps text = text_transform f text where
f :: [Char] -> [Char]
f [] = []
f [z : c : rest] | z == zr = [cap c : f rest]
f [c : rest] = [c : f rest]
zr = toChar 0
Флаг использовалась трансформация или нет будем хранить в верхней половине первого байта сжатых данных (в силу особенностей нашего алгоритма первый байт всегда 0 или 1). С такой трансформацией тестовые файлы сжались до 218590 и 76292 байт. Сравним это с "конкурентами":
meden.txt hhguide.txt
source 810114 274191
zip 310056 101171
rar 270238 92690
7z lzma 253886 87602
bz2 226367 78570
entropical 218590 76292
Тут rar и 7zip использовались в их режимах по умолчанию. В режимах максимального сжатия они используют PPMd, который позволяет сжать до 203653 и 70591, так что рекорда мы тут не поставили, но для простого демонстрационного компрессора по-моему неплохо. Чтобы убедиться, что мы не слишком узко заточились на два тестовых файла, возьмем классический тестовый набор Calgary Corpus, на нем суммарный размер сжатых файлов выглядит так:
original 3141622 zip 987364 rar 915537 7z 848687 bz2 828415 entropical 827957
Продолжение...
