COMPRESSION.RU:   О сервере  Анонсы  Статьи+исходники  Ссылки  RU.COMPRESS  Форум 
Книга "Методы сжатия данных":   Универсальные  Изображения  Видео 
Авторские проекты: Д.Ватолин  А.Ратушняк  М.Смирнов  В.Юкин  Е.Шелвин
А.Филинский  Д.Шкарин  С.Оснач  С.Воскобойников

Индекс

о сжатии словаря [3] - paq4, update exclusion и новые результаты

24 октября 2003 - Shelwien



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

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

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

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


wi += ti/c * (ci/ti-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 - надо будет попробовать ;).