В этой статье описан алгоритм работы моего словарного препроцессора DICT, достигающего значительно лучших результатов, чем LIPT и XML-WRT, и выводящего сжатие текстов на принципиально новый уровень. Для начала приведу результаты тестов (столбцы - метод сжатия, размер архива, время упаковки, время распаковки):



А теперь файл, благоприятствующий xml-wrt и ppmvc - хорошо сжимающаяся документация в html формате:



(имейте в виду, что результаты XML-WRT немного занижены из-за использования им словарей меньшего размера). Все тесты были проведены на процессоре с частотой 1 ГГц




Существуют две широко известные программы словарного препроцессинга.

Во-первых, LIPT, которая состоит из двух частей - первая набирает статистику на большом кол-ве текстов и в конце концов составляет список слов, отсортированный в порядке убывания их употребляемости. Вторая часть кодирует файлы, используя этот словарь, заменяя слова их 1-3 байтовыми кодами. Поскольку коды назначаются словам в порядке убывания частоты, то часто встречающиеся слова получают более короткие коды. Кроме того, первый байт в 2-3 байтовом коде отражает частоту слова, что также увеличивает степень сжатия. К сожалению, эта схема требует таскать с собой достаточно большой словарь, и эффективна только для слов, которые в этот словарь догадались включить

Вторая схема реализована в xml-wrt, который помимо xml-специфичных трюков, способен несколько улучшить сжатие и обычных текстовых файлов. В этой схеме словарь собирается динамически, а точнее - используется двухпроходный алгоритм. На первом этапе создаётся список слов, встречащихся как минимум N раз (N=6..60), на втором этапе этот список слов выводится в выходной поток, и вслед за ним - файл, где эти слова заменены на их коды, создаваемые, как я понял, по тому же принципу, что и в LIPT


Моя программа реализует третью схему, которая показала большую эффективность, чем первые две. Что особенно интересно - хронологически именно моя схема была первой (97-й год), и только закрытость программы привела к тому, что её потенциал оказался неиспользуемым

Основана эта схема на идеях из другого моего упаковщика, CM - единственной в мире программы статического контекстного моделирования. Т.е. она сначала собирает статистику по всему файлу (блоку), выводит её в выходной поток, и затем кодирует блок в соответствии с известным распределением вероятности символов в различных контекстах. Опубликованная реализация CM имела очень серьёзный недостаток - она пыталась создать полное дерево контекстов заранее заданной глубины, и это дерево содержало массу избыточной информации о контекстах, встречающихся всего 1-2 раза, но в то же время не включало информацию о частых контекстах большей длины. Очевидным решением этой проблемы было создавать контексты динамически, при достижении родительским контекстом некоторого кол-ва посещений. Хотя эта идея так и не была реализована в CM, я воспользовался ею в своём словарном алгоритме

В lipt/xml-wrt словом считается последовательность латинских букв, и это слово продолжается до тех пор, пока не встретится символ другого типа. Это упрощает их алгоритм, но уменьшает степень сжатия. В отличие от этого, в моей программе при разборе текста находится самая длинная последовательность _любых_ символов, уже занесённая в словарь. Если эта последовательность уже встречалась 10 или более раз, в словарь заносится "слово" на один байт длиннее. Рассмотрим, например, как этот алгоритм будет обрабатывать бесконечную последовательность звёздочек. Сначала в словарь будет занесено слово "*", после десяти его повторений, т.е. на 11-м байте - слово "*", после десяти его повторений, т.е. уже на 31-м байте - слово "***" и т.д.

Как видите, схема очень напоминает lzw, однако с куда более жёсткими правилами добавления в словарь новых слов. Хотя я и сказал выше, что допускается последовательность любых символов, но в действительности есть очень важная эвристика - все символы делятся на два класса - от 0 до 32, и от 33 до 255, и слово может включать символы только из одного класса. Таким образом, всё "форматирование" текста в виде последовательностей пробелов, табуляций и новых строк, оказывается сосредоточенно в одних "словах", а реальное содержимое - в других, а схема динамического роста слов позволяет держать в словаре слова не слишком короткие (имеющие очень много появлений), но и не слишком длинные и редкие слова - всё регулируется автоматически

Впрочем, из-за того, что символы разбиты на два класса, всё же некоторые слова встречаются очень часто. К примеру, в отформатированном по первому столбцу текстовом файле часто будет встречаться слово CR+LF, поскольку после него уже идут символы другого класса и это слово не может быть расширено несмотря на свой очень большой счётчик повторений

Для представления словаря используется классическая PATRICIA с инкрементальным хешированием. Т.е. все слова отображаются в огромную хеш-таблицу, и хеш-код слова "abcd" вычисляется по хеш-коду слова "abc" и символу 'd'. Поскольку мы можем себе позволить некоторую небрежность на этом этапе, каждый элемент хеш-таблицы хранит всего лишь двухбайтный ключ для обнаружения [большинства] коллизий, и двухбайтный счётчик слова. В список же слов, который будет необходим на втором этапе, мы только заносим новые слова, но никак его не используем



После того, как мы таким образом создали на первом проходе динамический словарь, происходит его чистка. Несмотря на строгость критериев занесения слов, их кол-во всё же оказывается очень велико (порядка 200-500 тысяч на 30-мегабайтном файле), и опыт показывает, что выводить все эти слова в выходной файл - занятие невыгодное (хотя я не пробовал строить словарь динамически в распаковщике - может, это будет выгодно?)

Поэтому из всех этих слов остаются только имеющие больше 50 повторов. Это порядка 10 тысяч слов, которые кодируются всего 50 килобайтами в выходном потоке. Декодер, таким образом, получает готовый список слов, и поэтому имеет очень высокую скорость работы, близкую к скорости вычисления CRC

Во втором проходе тоже есть свои тонкости. Во-первых, по условиям построения дерева слов, в нём трудно найти слова, имеющие частоту больше 10 Поэтому важным моментом является то, что при поиске "хороших" слов дерево обходится снизу вверх, и частоты слов, которые удаляются из словаря, отдаются их "родителям". Таким образом, если к пример слово "birth" втречается в тексте 200 раз, то при построении словаря в нём окажутся его всевозможные "сыновья", включая "birth,", "birthday" и т.д., а частота самого слова "birth" так и останется на отметке 10. Однако если эти производные слова имеют слишком малую встречаемость, то в процессе усечения дерева их частоты отойдут к "birth" и оно всё же будет включено в словарь

Вторая идея заключается в том, что если в тексте часто встречается скажем слово "http://www.sun.com/download/j2ee.jar", то его частота окажется размазана между его частичными префиксами в силу алгоритма построения словаря. И таким образом, вышеописанный алгоритм может счесть достаточно хорошим, скажем, только слово "http://www.su", что не очень-то здорово. Для исключения этой ситуации частоты слов, имеющих только одного ребёнка (ака детерминированных контекстов), отдаются этому единственному ребёнку. Небольшая спекуляция, но на практике это работает

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

Четвёртая, и весьма очевидная идея, заключается в сортировке словаря в лексикографическом порядке и использовании известного алгоритма дифференциального кодирования упорядоченного словаря для уменьшения его размера. Именно это и позволяет упихнуть десяток тысяч немаленьких слов всего в 50 кб


При создании алгоритма большое внимание было уделено оптимизации по скорости и памяти, поэтому его выгодно применять даже с быстрыми методами сжатия (скажем, rar -m2 или 7zip -mx3), где достигается увеличение сжатия на 10-30%. Но главным, конечно, являются результаты в режимах максимального сжатия lzma, ppmd, ppmonstr, где препроцессор увеличивает сжатие на 2-10%, а для lzma и ppmonstr также ускоряет его в 2-4 раза. Фактически, применение этого препроцессора позволяет вывести любой архиватор на принципиально новый уровень. Результаты, показываемые им, значительно лучше, чем у LIPT и XML-WRT, за исключением XML файлов, где XML-WRT использует множество специфичных для этого формата приёмов и обходит DICT

Интересным моментом является сравнение DICT+PPMD с PPMVC. Фактически, оба алгоритма схожм в том, что они позволяют решить проблему неэффективности PPMD на высокоизбыточных файлах вследствие фиксированной длины используемого контекста. PPMVC улучшает сжатие высокоизбыточных файлов, но работает медленней и ухудшает сжатие на обычных текстах. В то же время последовательность dict+lzp+ppmd на всех моих тестах показывала стабильно высокий результат. Похоже, что эти препроцессоры ухитряются "съесть" всю избыточность, и приводить разнородные файлы к довольно близкому уровню энтропии, что решает одну из известных проблем PPMD - зависимость оптимального порядка модели от уровня энтропии конкретных входных данных! Как результат, даже на высокоизбыточных входных файлах, эта "тройка" сжимает быстрее и лучше чистого PPMVC, и уступает всего 0.1% от размера сжатого файла сочетанию dict+lzp+ppmvc


Алгоритм распространяется на условиях GPL лицензии, и я буду рад продать разработчикам коммерческих архиваторов лицензию на использование препроцессора в их программах. В настоящее время я работаю над включением его в свой собственный архиватор, что позволит ему не просто стать номером 1 в мире, но ещё и значительно оторваться от конкурентов



ps: хотя я приаттачил к статье исходники и исполняемый файл препроцессора, наверно немного найдётся людей, желающих его испытывать в таком виде. Простые смертные могут использовать для этого мой архиватор. Командная строка:

arc create a srcfile -t -m5

Также можете попробовать -m5x и -m5p, хотя для последнего метода сжатия потребуется ppmonstr.exe в PATH. Желающие насладиться более изощрёнными техниками камасутры могут почитать описание опций display, logfile, print-config и попробовать, скажем, вот такую команду:

arc a a srcfile -m0=dict:p+lzp:64mb:32:h22+pmm:16:400mb

Сcылки для загрузки:
http://www.haskell.org/bz/dict.zip
http://www.haskell.org/bz/FreeArc-win32.zip

_________________
bulat_z##mail.ru

Ошибка : Архиватор вернул код завершения -1073741819
Упаковка из-под FAR. Вываливается при всех -mX, где m>3. Данные - Fate 2005 (файлы выдернуты из инсталлера). Памяти (судя по вашим данным) - выше крыши.

Какие будут мысли?

Вот так всю малину и портят
Мне, на самом деле, хотелось бы ещё для BWT результаты увидеть

>Мне, на самом деле, хотелось бы ещё для BWT результаты увидеть

попробуй сам. у меня результаты получились неуйстойчивые - где-то выигрыш, где-то проигрыш (использовался grzip). в приницпе, opendak я загрузмл, но в моих тестах grzip идёт как быстрый упаковщиек, который грех портить такими сравнительно меджддленными препроцессорами. если dak может конкурировать по сжатию с ppmd на 64-128 метрах памяти - будет другое дело

>Ошибка : Архиватор вернул код завершения -1073741819

даже не знаю. у меня никогда сбоев не было. попробуй отдельные алгоритмы сжатия (-m4bx/-m4tx/-m4b/-m4t/-mlzma/-mppmd/-mgrzip/-mdict/-mlzp) и скажи на чём сбоит на чём нет. если есть не очень большие файлы на которых проявляется ошибка - присылай их мне. в пределах нескольких мб

_________________
bulat_z##mail.ru

исправил ошибку, обновил FreeArc. но предупреждаю - чудес не бывает, и lzma не способен сжать лучше, чем сжимает lzma


что касается OpenDark - то он с препроцессором работает в разы быстрее. но до grzip -l всё равно не дотягивает ни по скорости, ни по сжатию

_________________
bulat_z##mail.ru

>Похоже, что эти препроцессоры ухитряются "съесть" всю избыточность, и приводить разнородные файлы к довольно близкому уровню энтропии

собственно говоря, ничто не мешает прверить это предположение:


как видите, если в первоначальных файлах разброс энтропии был 6 раз, то после препроцессинга он уменьшился до 2-х раз



>Данные - Fate 2005 (файлы выдернуты из инсталлера

поясню своё предыдущее замечание. dict не способен улучшить сжатие нетекстовых файлов, и поэтому он на них даже не применяется. остаётся чистый lzma - точно такой же, как и в 7-zip

_________________
bulat_z##mail.ru

Гхм! Разница в 10-60 кб на 10мб - несущественна, при условии 7-кратной скорости, которая наблюдается при сравнениее 7-Zip.Ultra и ARC -m6.

p.S. После 7-Zip-а на средней системк - невозможно работать. В случаи с вашим архиватором - этих проблем нет.


А где обновление? Тотже файл вроде...

Словарь русских слов
Источник - http://www.mibeditor.wand.ru/russian.zip


Словарь английских слов
Источник - http://www.mibprogs.nm.ru/mibeditor/engdic.zip

может лучше на "ты"?

текстовые файлы прграмма ест-но жмёт лучше и быстрее. моё замечание относилось именно к ресурсам игрушек

и кроме того, быстрая упаковка может иметь в качестве обратной стороны медленную распаковку, требующую к тому же много памяти. вы про это не забываете?

_________________
bulat_z##mail.ru

>А где обновление? Тотже файл вроде...

архив за 5-е число. размер exe остался тот же, ну так такм и изменений на 2 копейки

_________________
bulat_z##mail.ru

А я игрушки и имел в виду, когда говорил о 60кб на 10мб b 7-микратной скорости.

Тем более куда меньшее ресурсопотребление (на глаз). Учитывая, что пираты и причисленные к ним игроделы маниакально пересели на 7-zip. Народ просто вынужден иметь для установки игры более мощную систему, чем требуется для самой игры.

у меня такое подозрение, что ты сравниваешь программу на текстовых файлах, и потом делаешь вывод, что и на ресурсах к игрушке она будет в 7 раз быстрее?

_________________
bulat_z##mail.ru

Выложить результаты сравнения на GEX/Fate 2005?

На Gex (что-то около 70 мегабайт) - 7-Zip меньше на 68kb, вот только потратил почти 20 минут против 3 с мелочью, да и работать на компе после него было уже нельзя

выложи. и перепроверь их сначала. не должно такого быть. 7zip 4.43, надеюсь?

хотя есть пара подозрений - lzp препроцессор, и exe препроцессор, используемый на всех файлах, в отличие от 7z. первое в принципе, могло дать такой результат

попробуй с опцией -mlzma:32mb:max:bt4:128/6t - это то же, что и -m6, но с отключением lzp-препроцессора для бинарных файлов. если результаты получатся как у 7-zip, я по крайней мере пойму в чём дело

>да и работать на компе после него было уже нельзя

это из-за того, что в ultra используется примерно 800 мб памяти. попробуй 7z -mx9 -md=32m

ну теперь до меня дошло - 7zip у тебя тормозил из-за своппинга. уменьшишь словарь - и всё будет ок


kvark, я разобрался почему результаты столь слабые с bwt. это из-за того, что у меня используются 1- и 2-байтовые коды для слов, и 2-байтовые могут заканчиваться _любым_ символом. ес-но, это разбавляет контексты всякой ерундой, и страдает от этого в первую очередь BWT (во вторую наверное PPM). без 2-байтовых кодов (опция -1 у dict) проигрыша никогда не бывает, но и выигрыш очень слабый, где-то 1-2%. возможно, я над этим поработаю. в идеале конечно, кодер должен работать с 2-байтовыми элементами

_________________
bulat_z##mail.ru

жаль, что так...
будем ждать апдейтов