Смотрите также материалы:
- Предсказание по частичному совпадению (PPM)
- Арифметическое сжатие
- Сжатие с помощью грамматических моделей
- Обзоры универсальных алгоритмов сжатия данных
- Книга "Методы сжатия данных". Раздел 1 "Методы сжатия без потерь"



Экспериментальный однофайловый компрессор hipp v0.5819 (19/08/2005)
Богатов Роман, Омский государственный технический университет


Hipp v0.5819 с исходниками 59 Кб (Visual C++ 7.0)

Основные особенности (в направлении которых и ставится эксперимент):
  • двойное ограничение глубины суффиксного дерева при использовании объединения цепочек детерминированных узлов;
  • использование фиксировано-удалённых контекстов.
Суть двойного ограничения в следующем. Если реализовано объединение детерминированных узлов (ОДУ, англ. path compression), при котором размер объединённого узла остаётся постоянным при любой длине цепочки, то цепочку можно продлять за пределы первого ограничения глубины до тех пор, пока она остаётся детерминированной, не расходуя при этом память. Т.о. ОДУ + двойное ограничение являются альтернативой LZ-субмоделям, используемым совместно с контекстным моделированием для эффективной обработки больших повторяющихся блоков данных. (См. результаты экспериментов и комментарии ниже.)

Фиксировано-удалённые контексты (далее – fd-контексты, от fixed distance contexts) имеют вид x*, x**, xx*, x***, xx**, xxx*, x**** и т.д. (где х – конкретные опорные символы, * – позиции, занимаемые любыми символами), т.е. являются частным случаем разреженных контекстов (sparse contexts), когда все опорные символы сгруппированы слева и отделены от кодируемого символа с пропуском некоторого фиксированного числа символов. Распространённой практикой использования разреженных контекстов является запоминание только одного – последнего встретившегося – символа. Эксперимент с fd-контекстами заключается в учёте полной статистики по встречаемости символов в этих контекстах и увеличении степени сжатия данных с использованием этой статистики. (См. результаты экспериментов ниже.)

Hipp использует полное смешивание по следующей схеме. Веса прогнозов по сплошным контекстам (т.е. "обычным", не разреженным контекстам) рассчитываются по методу PPMY Евгения Шелвина с использованием заимствованных из PPMY таблиц коэффициентов; веса fd-контестов – по тем же формулам, но с постоянными коэффициентами; детерминированные контексты, выходящие за пределы первого ограничения глубины, обрабатываются особо. Кодирование символа происходит дихотомически (aka "унарно") c поэтапной оценкой каждого возможного значения символа и кодирования результата. Унарные вероятности моделей сплошных и fd-контекстов проходят двумерную вторичную оценку с интерполяцией (aka SSE2), реализованную Е. Шелвиным, и смешиваются с помощью также вторично оцениваемого коэффициента.

Для вторичного оценивания используются упрощённые SSE-контексты. Для сплошных контекстов - ничего нового. Для fd-контекстов и коэффициента смешивания моделей наиболее существенным компонентом является уникальный индекс шаблона fd-контекста, внёсшего наибольший вклад в совокупную оценку. В качестве двух интерполируемых аргументов используются несмешанные унарные вероятности моделей.

Наиболее существенные недоработки:
  • отсутствует какое-либо масштабирование счётчиков частот (recency scaling, rescaling);
  • реализован самый простейший метод выживания при достижении ограничения по памяти, сводящий на нет весь достигнутый к тому моменту выигрыш в сжатии;
  • примитивная схема смешивания прогнозов моделей сплошных и fd-контекстов и непроработанные SSE-контексты;
  • при использовании fd-контекстов не может быть использовано ОДУ (подружить их можно, но не так быстро, как предполагалось);
  • в случае fd-контекстов требуется дифференциация счётчиков "оптимальности" (используемых Е. Шелвиным для расчёта весов полного смешивания) в зависимости от глубины и шаблона fd-контекста;
  • прилагаемый исходный код вообще-то не планировался к опубликованию и совершенно не причёсан :о)
Результаты экспериментов. Во-первых, насчёт ОДУ (path compression). График размера суффиксного дерева в зависимости от объёма входных данных говорит сам за себя:
Path compression on Calgary Corpus 
Видим подтверждение доказанного теоретически факта: линейная зависимость расходов памяти от объёма входных данных возможна только при ОДУ.

(Изображены результаты прогона 18 файлов тестового набора Calgary Corpus при ограничении глубины MaxOrder=1706. В Calgary Corpus есть только один файл, содержащий повторяющийся блок длины больше 1706, pic, которому соответствует пик на графике в 300 Мб. Для pic полное суффиксное дерево (MaxOrder=36313) с ОДУ занимает всего 15,4 Мб; без ОДУ уже при MaxOrder=8000 занимает 926 Мб. Тот факт, что в hipp использованы 32-битные счётчики частот (~1/6 объёма дерева без ОДУ) и 18-байтовая структура узла (содержащая дополнительные параметры, вместо минимальной 5-байтовой; ~1/3 объёма дерева), не искажает качества графика. Здесь же следует отметить, что для построения дерева с ОДУ требуется меньше времени (главным образом, из-за экономии памяти), а в целом сжатие с ОДУ занимает приблизительно столько же времени, как без ОДУ.)

При реализации ОДУ использовался более сложный подход, чем замена symbol-transition на string-transition (см., например, диссертацию S. Bunton), на основе собственных структур (см. файл NodeStruct.inl). Самая большая проблема, с которой пришлось столкнуться, – это эмуляция должных значений счётчиков "оптимальности" объединённых узлов (чтобы не хранить их явно; иначе бы вся красота ОДУ сошла на нет). Реализованный метод требует два дополнительных статических массива – для счётчиков встречаемости узлов и счётчиков оптимальности – по (MaxOrder+1) элементов каждый.

Использование второго ограничения глубины суффиксного дерева (MaxOrder2, MaxOrder1<=MaxOrder2)  позволяет качественно обрабатывать файлы, содержащие большие повторяющиеся блоки, при тех же расходах памяти и небольших дополнительных затратах времени. Пример:

Исходные файлы:
  book1        768771
  book1_x10   7687710  (10 склеенных book1)
Оборудование: Pentium 4 2400MHz, 1Gb DDR400, Seagate 60Gb, Windows XP Pro + SP2.

      Параметры         Память, Время, Архив,
 запуска 
Hipp 0.5819      Мб      с      Кб

book1_x10/o4/do4         32,8     50   1758
book1_x10/o4/do256       32,8     53    314
book1_x10/o4/do1024      32,8     62    212
  Для сравнения – сжатие одного book1:
book1/o4/do4             25,6      5    209
(т.е. почти достигнут размер однократного book1)

Прочие архиваторы
(сжатие book1_x10: память, время, размер):
PAsQDa v3.9 -8          930Mb   6344    176
PAsQDa v3.9 -2           32Mb   1324   1741
Durilca v.0.4b –o64 -t1 940Mb     22    179
Durilca v.0.4b –o64     940Mb     22    199
PAQAR v4.0 -7          ~900Mb   1891    192
PAQAR v4.0 -3           ~55Mb   2054   1752
WinRK 2.0 PWCM          900Mb    870    200
PPMonstr var.I –o32     225Mb     12    201
PPMonstr var.I –o16      32Mb     23    991
PPMonstr var.I –o32      32Mb     26   1295
ash /o33 /s255          480Mb     85    203
ash /o17 /s255          186Mb     66    222
ash /o65 /s255           >1Gb     94    364
PPMd var I. –o16         89Mb      2    224
PPMd var I. –o9          26Mb      2    569
RAR 3.40 -m5                       3    212
RAR 3.40 -m5 –mc63:128t+           4    212
RAR 3.40 -m5 –mc16:32t+            4    534
Slim! v0.016 –w22                 18    216
Slim! v0.23d –o32       240Mb     52    218
Slim! v0.23d –o16       140Mb     51    230
Slim! v0.23d –o16        70Mb     81    915
EPM r9 –c128                      71   1960
EPM r9 –c064                      70   1963
EPM r9 -c999                     101   1963


Как видно из первой таблицы, благодаря ОДУ hipp использовал всего 32,8 Мб памяти для контекстного моделирования 4-го порядка (из которых суффиксное дерево занимает только 2,7 Мб; остальное – невостребованные SSE-массивы, кэширование всего файла целиком и пр.) и благодаря увеличению MaxOrder2 до 1024 "учёл" десятикратность входных данных, затратив на 25% больше времени (хотя порядок модели увеличился в 256 раз).

На обычных файлах (не являющихся склейкой одинаковых блоков :о) ситуация двоякая. Типичные благоприятный и неблагоприятный случаи на примере файлов news из Calgary Corpus и fp.log с www.maximumcompression.com:
 Using /do option. File: news
Using /do option. File: fp.log
(По вертикали – степень сжатия (ratio; отношение исходного размера к сжатому). Польза от MaxOrder2 наиболее существенна при малых значениях MaxOrder1. Провал на малых значениях MaxOrder2 объясняется примитивной функцией расчёта весов контекстов, выходящих за границы MaxOrder1, и нечувствительностью вторичной оценки к такой ситуации. В настоящей версии ненормализованный вес смешивания таких контекстов равен (частота контекста)×(длина ОДУ-цепочки)/(глубина суффиксного дерева). Но в среднем, даже при таком грубом смешивании, двойное ограничение суффиксного дерева способствует увеличению степени сжатия. См. также результаты большого теста ниже.)

Фиксировано-удалённые контексты обеспечивают существенное увеличение степени сжатия на файлах с табличной структурой (xls, dbf и т.п.), а также исполняемых файлах, и в то же время незначительно ухудшают степень сжатия при применении к "неблагоприятным" данным (например, текстам). Зависимость расходов времени и памяти от объёма входных данных при этом остаётся линейной (хотя это ни о чём не говорит – зависимость остаётся линейной даже при привлечении всех возможных разреженных контекстов ограниченной глубины :о). Смотрим зависимости степени сжатия (ratio), времени (time) и использованной памяти (used memory) от глубины сплошных контекстов (MaxOrder) и глубины fd-контекстов (fd-MaxOrder) при сжатии файлов kennedy.xls из Canterbury Corpus, obj2 и pic из Calgary Corpus:
Using /so option on kennedy.xlsUsing /so option on kennedy.xlsUsing /so option on kennedy.xls
Using /so option on obj2Using /so option on obj2Using /so option on obj2
Using /so option on picUsing /so option on picUsing /so option on pic
(На kennedy.xls и obj2 видно, что пользы от добавления даже неглубоких fd-контекстов больше, чем от произвольного увеличения глубины сплошных контекстов. Поправка: графики интерполированы по точкам с глубиной fd-контекстов 0:2:24, в то время как fd-контекстов с глубиной 1 не существует. Степень сжатия .xls-файлов часто имеет пик при ограничении глубины fd-контекстов равном 16, либо продолжает медленно расти как на pic. У исполняемых файлов (включая DLL) – стандартный пик на глубине 12. Самый "благоприятный" тип файлов из обнаруженных – cdx: увеличение степени сжатия почти вдвое уже при глубине 8. См. также результаты большого теста далее.)

Результаты большого теста. Исходные данные: годовая 1С-база одного из предприятий (207 Мб) + несколько годовых xls-отчётов (17 Мб), всего 730 файлов 21 типа. Т.к. hipp не использует никаких фильтров, не разбивает входные данные на области, не масштабирует статистику, неважно себя ведёт при дефиците памяти, не сохраняет ни имени файла, ни пути... :о), приходится делать следующий манёвр. Исходные данные консолидируются в rar-архивы без сжатия, раздельно по расширениям, с максимальным размером тома 1 Мб (например, rar a -ds -m0 -r -v1m -vn _dbf *.dbf); мелкие и одиночные файлы (с расширениями txt, rtf, xml, als, tls, cfg, st, tip, spl, log, efd, lst, id; суммарный размер 700 Кб) – в один архив. В результате исходные данные представляют собой 230 файлов (225 Мб), размером не более 1 Мб каждый, удобных к обработке однофайловым компрессором. Обратное преобразование осуществляется командой rar x *.rar.

Совокупная степень сжатия полученных томов по отдельности представлена в таблицах:
Table1
(Лучшее значение степени сжатия в первых двух столбцах выделено полужирным; лучшее по строке - красным. Здесь, во-первых, видно, что использование двойного ограничения глубины суффиксного дерева в среднем способствует увеличению степени сжатия (второй столбец). Значения глубины fd-контекстов со штрихом – эксперимент по исключению fd-контекстов с одним опорным символом, т.е. вида x*, x**, x***, x**** и т.д., являющихся самыми ресурсоёмкими и, как может показаться, наименее важными. Но небольшой выигрыш в ресурсах при этом оказался несоответственным потере в степени сжатия: совокупные результаты запуска с параметром /so16' , например, по всем показателям проигрывают более сильному и экономичному сжатию с параметром /so10.)

Два столбца с лучшими показателями hipp (без и с использованием fd-контекстов) представлены в сравнении с другими известными архиваторами:
Table2
(Тяжеловесы типа PAQAR, PAsQDa и WinRK не тестировались :о( Лучшее значение степени сжатия по строке выделено полужирным. Итоговые степени сжатия также отображены на диаграмме ниже. Как видно, рейтинг hipp с fd-контекстами в таблице обусловлен хорошим сжатием cdx и xls-файлов, составляющих почти четверть входных данных. О качестве этого результата говорит также тот факт, что по сжатию dbf-файлов, составляющих 46,6%, hipp занимает аж пятое место, что не мешает ему оставаться на третьем месте по совокупной степени сжатия.)
Compressing 225Mb
Вот ещё, какое замечание. Если б изначально исходные данные раскраивались не в 1Мб-томные архивы, а, скажем, по 2 Мб, то результаты прочих архиваторов возросли бы в большей степени, чем у hipp. Что понятно, т.к. у hipp, опять же, нет масштабирования статистики, нормальной обрезки дерева при нехватке памяти, проработанных SSE и т.д. По этим же причинам hipp не способен обеспечить заметных показателей на тестовых файлах Бергманса и т.п.

Основные выводы. Ещё раз повторюсь, что эксперимент ставился в двух направлениях: повышение степени сжатия при использовании ОДУ + двойного ограничения глубины дерева и fd-контекстов.

ОДУ, само по себе, существенно экономит память, но применимо только для "простых" суффиксных деревьев, узлы которых не содержат специфических параметров. ОДУ реализуемо, например, для узлов с обычными счётчиками встречаемости и оптимальности узла, а также при использовании простого безусловного масштабирования этих счётчиков.

Если ОДУ реализовано, то двойное ограничение глубины суффиксного дерева является готовой и удобной альтернативой LZ-субмоделям, предназначенным для обработки больших повторяющихся блоков данных. Даже такое грубое использование двойного ограничения, как в настоящей версии hipp, является серьёзным подспорьем, особенно при малых значениях MaxOrder1.

Учёт полной статистики по встречаемости символов в fd-контекстах на определённых типах данных позволяет hipp при всей его недоработанности достигать уровня сжатия хорошо проработанных лидирующих архиваторов. Вскользь упомянутый эксперимент с запрещением fd-контекстов с одним опорным символом говорит о ценности именно полной статистики по всем встречающимся символам в fd-контекстах контекстах. Хотелось бы обратить общественное внимание на то, что тема использования разреженных контекстов для универсального сжатия мало исследована и ещё меньше освещена в каких-либо публикациях.

Благодарю Бога (такого заботливого Отца), кафедру АСОИУ ОмГТУ (ставшую моей родиной) и Евгения Шелвина (за щедрое консультирование и дружбу)!

Имэйл автора для отзывов: fwd2bogatov на Яндекс.ру.

наверх

Смотрите также материалы:
- Предсказание по частичному совпадению (PPM)
- Арифметическое сжатие
- Сжатие с помощью грамматических моделей
- Обзоры универсальных алгоритмов сжатия данных
- Книга "Методы сжатия данных". Раздел 1 "Методы сжатия без потерь"