24 октября 2003 - Shelwien

На сей раз к словарям меня вывело обсуждение исключений при обновлении в ru.compress.

Я как-то давно на эту тему не задумывался (разбираться со смешиванием было интересней ;), но ведь в самом деле легко привести пример, когда обновлять все контексты неправильно. Взять, скажем, данные, обработанные RLE-фильтром, заменяющим последовательности одинаковых символов на спец-символ и длину последовательности. Понятно, что длину тоже надо кодировать в контексте предыдущих символов. Но, при этом, нельзя использовать статистику младших порядков (и, особенно, ее обновлять). С другой стороны, вот ppmy, ash, и paq вроде бы обходятся без исключений, но, при этом, как-то работают.

Потом, правда, я вспомнил, что в ash статистика обновляется по-разному в зависимости от порядка контекста - а это явный аналог partial updates, т.к. чем старше порядок, тем "агрессивнее" обновление. В ppmy и paq такого нет, но статистика там частотная и апдейт "ослабляется" со временем - в итоге, опять же, высокие порядки, где меньше статистики, обновляются "сильнее". Хотя, все же в paq, возможно, ситуация несколько иная. Частоты там хранятся в очень специфическом виде, так что контексты разных порядков должны, по идее, быстро "уравниваться в правах". Возможно, именно по этой причине контекстная модель paq, сама по себе, и выдает не слишком привлекательные результаты. Однако, тут есть определенные возможности для экспериментов. ;)

Кстати, по поводу экспериментов. В версии paq4 Махони реализовал, наконец, адаптивное смешивание. Я бы не сказал, что в нем (на данный момент) есть какой-то практический смысл (своей эффективностью paq4 обязан в большей степени новым субмоделям), но определенный интерес представляет сама формула апдейта веса. Я бы записал ее так:

w_i += t_i/c * (c_i/t_i-c/t)

Второй множитель здесь вполне логичен и, я бы даже сказал, традиционен (Сергей Оснач называет эстиматоры такого рода "балансировщиками" и весьма активно использует) - это разность вероятности текущего символа в данном контексте и в смешанном распределении. А вот с первым дело темное. Допустим еще, что обратная зависимость от смешанной частоты текущего символа просто приводит к постепенному "ослаблению" апдейта на стационарных данных (я бы использовал что-нибудь другое, но у меня и веса не были бы глобальными), но вот почему инкремент веса контекста прямо пропорционален сумме его счетчиков - это вопрос. Выходит, что резче всего веса будут меняться в самых старых контекстах. Объясните мне кто-нибудь, я что-то не понимаю, или это очередной глюк Махони из-за чрезмерной теоретизации - типа лишних SSE-индексов в paq3?

...Ладно, это я что-то совсем уже уклонился от темы :)

Так вот, поскольку с обоснованной методикой выбора контекстов для обновления в универсальной модели есть большие проблемы, то я решил, в очередной раз, посмотреть на словари - т.к. текст можно сжимать словной моделью и нулевого порядка, где с апдейтами все ясно. Несколько забегая вперед, скажу, что для моделирования словарей, похоже, полное исключение при обновлении применять нерентабельно - крайне слабая (и, обычно, отрицательная) реакция на замену часто встречающихся суффиксов отдельными символами это подтверждает. Да и способность моделей типа ash приемлемо сжимать тексты, очевидно, объясняется именно этим ;)

Последние мои идеи насчет словарей касались моделирования алфавитов. Словарь можно представить в виде дерева, так устраняется существенная часть явной избыточности, но возникает необходимость рассчитывать вероятности встречания различных множеств символов. Проблема в том, что, кроме контекстных, в множествах есть еще и внутренние корреляции и возникают трудности уже даже не теоретического, а вполне практического характера - нереально перебирать все возможные подмножества и собирать статистику по встречанию в их контексте еще каких-то символов. Мало того, есть большие подозрения, что работать с множествами символов недостаточно, т.к. из морфологических соображений должны быть корреляции между целыми суффиксами.

Не знаю уж, к счастью ли, но эта проблема оказалась несколько надуманной ;) Я посмотрел на отфильтрованный dictpack1 бергмансовский словарь, и обнаружил, что в нетронутом виде там остались практически только суффиксы - причем, поскольку там кодируются длины различающихся суффиксов слов (а не совпадающих префиксов, как мне казалось раньше ;), то у образующихся списков суффиксов слов есть большие шансы совпасть с аналогичными списками других слов, так что частично искомые корреляции все-таки учитываются и в обычном dictpack1, без особых сложностей. Конечно, по-хорошему надо бы все же моделировать множества суффиксов, и про зависимость от префиксов тоже не забывать, но это в будущем. А для начала я решил "перевернуть" отфильтрованный dictpack1 бергмансовский словарь - ведь правильней моделировать длину суффикса в контексте символов суффикса, а не наоборот. На удивление, из этого кое-что вышло:

Компрессор           порядок символов:
                     обычный   обратный

ppmonstr Ir1 -o32    426005    425978
ash02                426945    425273

Так я впервые победил ppmonstr ;) (Что интересно, другие лидирующие компрессоры показывают на этом файле заметно худшие результаты - к чему бы это?)

paq4                 439841    437689
epm r9 0             428853    428302
epm r9 c             432507    432875
slim 17 -tt- -tl     432257    432488
slim 17 <default>    436887    432843

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

able ful al
ally ing ic
ible ion
like ism
ment ist
ness ous
ship

Получилось

ash02                425594    424098
epm r9 0             428234    427740
ppmonstr Ir1         429519    430304
slim 17 -tt- -tl     430103    430856
paq4                 434743    432314

Разница еще более впечатляющая, не правда ли? ;)

Но достичь чего-то большего за счет новых замен стало совсем уж сложно, так что я решил попробовать другие методы - тем более, что рекордные показатели ash этому способствовали. Для начала, проще всего показалось использовать знание грамматики обрабатываемого файла (перевернутого отфильтрованного english.dic):

[...]
tel Г
hsi З
detraeh Г
ts 
s А
re Е
y Г
seirreb А
gn 
[...]

Итак, известно, что за LF следует слово, терминируемое пробелом; затем идет код длины различия - заглавная русская буква; затем опять LF. "Универсальная" модель компрессора (увы, и ash в том числе :), естественно, ничего об этом не знает, и оставляет интервалы вероятности для всех символов в любых случаях. Логично было попробовать "маскировать" ненужные символы, пользуясь знанием структуры файла. Ну, я и попробовал (все последующие результаты получены исключительно при помощи ash02, т.к. для них требуется модифицированная модель):

+Alphabet switching            423390

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

+Char order limit              420595

Ну, уже что-то. Раз так, можно полностью реализовать реконструкцию части слова (файл обрабатывается, фактически, с конца, так что только части), и учесть все доступные ограничения:

+Word order limit              410119

...Что и позволило получить желаемое существенное улучшение. ;)
(Хотя необходимость специальной обработки односимвольных кодов суффиксов вызвала некоторые сложности)

Архив с новой версией кодера/декодера словаря можно найти здесь: http://compression.ru/sh/dictpack3.rar

Кроме того, как некоторым известно, на днях я разбирался со сжатием юкинского ca.fdb и получил 48701, что несколько лучше 60k, выдаваемых compressia, и уж тем более 78k paq4, которым кое-кто позавидовал ;)

К теме это имеет такое отношение, что ca.fdb - в душе словарь, и логично было (и будет ;) использовать специализированные словарные методы - в частности dictpack1. Так я и поступил вот здесь: http://compression.ru/sh/fltca1.rar

Теперь же, раз появилась улучшенная модель для словарей, имело смысл переделать и этот кодер. Это оказалось не так просто - модификация ash из dictpack3 была рассчитана на латинский текст (а здесь русский) и попутно оказалось, что порядок слов в ca.fdb не идеален - встречаются даже дубли. К счастью, таких ошибок немного, и достаточно оказалось при ограничении лексикографического порядка не обнулять вероятности "невозможных" символов, а просто делать их очень маленькими. Плюс, если ca.fdb и словарь, то очень специфический, так что в варианте fltca1 ash его сжимал не лучшим образом (рекордное значение выдал, совсем уж на удивление, ppmy_9A8), да и его "переворачивание" ухудшало сжатие.

Тем не менее, адаптированный вариант "словарного" ash позволил получить уже 47860 - причем именно на перевернутом файле; потребовавшая дополнительной мороки версия для прямого порядка слов выдала 47976.

Вот, в общем: http://compression.ru/sh/fltca2.rar

...Интересно только, почему я не додумался вставить парсинг словаря в ppmy_9A8 - надо будет попробовать ;).