Для начала результаты тестов:
где параметр -l задаёт MinMatchLen. rzip и lzp протестированы только с MinMatchLen=32

а теперь что это такое: нередко сжимаемые данные содержат повторы на больших расстояниях, которые алгоритмы вроде lzma не в силах обнаружить в силу сравнительно малого размера своего словаря. такие алгоритмы, как rzip и lzp, позволяют использовать под словарь более половины доступной памяти, что значительно улучшает обнаружение повторов. REP - препроцессор, который можно считать усовершенствованным вариантом RZIP, находящий куда больше повторяющихся строк и работающий гораздо быстрее при больших значениях MinMatchLen. в своём архиваторе я заменил им использование LZP для препроцессинга бинарных файлов, так что теперь этот препроцессинг стал практически "бесплатным". к сожалению, он не очень-то подходит для препроцессинга текстовых файлов, поскольку его выход (в формате LZ77) сжимается куда хуже, чем выход LZP

Исходники и win32 executable: http://www.haskell.org/bz/rep.zip



ну а теперь технические подробности алгоритма:

Этот алгоритм является разновидностью LZ77, т.е. он находит повторяющиеся строки во входных данных, и кодирует их как (len,offset). Его особенностью является ориентация на поиск совпадений достаточно большой длины на большом расстоянии. Поэтому он весьма эффективно использует память - как правило, для структур поиска требуется не более 25% от размера окна поиска. При этом он находит практически все совпадения если минимальная длина (MinLen) искомых строк - 512 байт, и порядка 98% - в одном моём эксперименте на поиск совпадений с длиной от 32 байт. На практике этот алгоритм нацелен на использование в качестве препроцессора, уменьшающего избыточность файла и/или находящего сопадения на таких дистанциях, которые недоступны основному алгоритму упаковки, и в этом качестве он конкурирует с такими алгоритмами, как LZP by Ilya Grebnev и RZIP. При этом, как показывают эксперименты, для препроцессора оптимальная величина минимальной искомой строки находится именно в этих пределах - 32-512 байт. Этот алгоритм находит куда больше совпадений, чем LZP/RZIP, и кроме того, его скорость работы увеличивается при увеличении MinLen.

Алгоритм реализуется функциями REPEncode() и REPDecode(), и использует сочетание идей из LZP, RZIP и моих собственных. Поиск совпадений ведётся в скользящем окне - входные данные считываются блоками по 1/16 от размера буфера, и это означает что в любой момент времени как минимум 15/16 буфера содержат предыдущие данные, которые сканируются в поисках совпадений. Для упрощения алгоритма ни входные блоки, ни совпадения не могут пересекать границу буфера.

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

Подбор наилучшей формулы для скользящего хеширования был отдельным приключением. В конце концов простая формула hash = p[-1] + PRIME*p[-2] + PRIME*PRIME*p[-3] + ..., где PRIME - простое число, оказалась самой быстрой и дающей весьма равномерное распределение. Разумеется, все вычисления идут по модулю 1<<32, любезно предоставленному нам процессором

Далее, были использованы дополнительные меры для уменьшения требований к памяти и увеличения скорости. Рассмотрим к примеру работу алгоритма для MinLen=512. Поскольку любой 512-байтный блок включает в себя 256-байтный блок, начинающийся с позиции, кратной 256, то нам достаточно вставлять в хеш-таблицу ссылки только на эти блоки и искать совпадение только с ними. Разумеется, при проверке совпадения мы не ограничиваемся в точности 256 байтами, а пытаемся продолжить его как можно дальше в обе стороны. Именно это и позволяет значительно уменьшить расход памяти при гарантированном нахождения почти всех совпадений - во всяком случае, когда MinLen достаточно велико.

Однако можно пойти ещё дальше - вместо того, чтобы вставлять в хеш-таблицу каждый 256-й блок, но искать каждый-каждый, мы можем например вставлять каждый 32-й, а искать каждый 8-й, или вставлять каждый 2-й, а искать каждый 128-й. Разумеется, оптимумом будет вставлять и искать каждый 16-й блок. Точнее говоря, нужно вставлять один блок через каждые 16 байт, а искать первые 16 блоков из каждых 256, то есть вставляем блоки, начинающиеся с позиций 0, 16, 32..., а ищем блоки, начинающиеся с позиций 0, 1, 2..., 15, 256. 257... Таким образом, для MinLen=512 достигается 8-кратное ускорение работы (за счёт 8-кратного уменьшения количества обращений в память) по сравнению с прямолинейной реализацией - правда, за счёт увеличения требований к памяти (с 1/64 размера буфера до 1/4, что на мой взгляд вполне приемлемо).

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

В алгоритме используется хеширование с прямой адресацией, без вторичного хеширования, что делает реализацию очень простой. Значение хеш-функции от 256-байтного блока (в общем случае размер этого блока - L=MinLen/2) используется как индекс в хеш-таблице (hasharr[hash&HashMask]), при коллизиях новый блок просто заменяет более ранний. На практике это (практически) не ведёт к деградации компрессии. Ещё раз подчеркну, что этот алгоритм, в отличие от полноценных LZ77 реализаций, ищет не оптимальное (самое длинное) совпадение, а проверяет лишь одну ссылку - на последний блок, который занял этот хеш-слот, и чья КС, следовательно, предположительно совпадает с КС текущего блока.

Размер хеша (HashSize): при разработке алгоритма я предполагал, что он должен быть в 2-4 раза больше количества элементов, которые в него придётся вставлять. Однако на практике оказалось, что вполне достаточно иметь то же самое кол-во слотов, а для MinLen=32 - даже вчетверо (!) меньшее. то есть, например, для 32 мб блока при MinLen=512 в хеш вставляется каждый 16-й 256-байтный блок и общее количество вставляемых элементов - 32млн/16=2млн, т.е. 8 мб, и хеш создаётся именно такого размера. Для MinLen=32 общее количество элементов 32млн/4=8млн, но мы создаём хеш-таблицу вчетверо меньше, то есть получаются те же самые 8 мб. Таким образом, подбираемый алгоритмом автоматически размер хеш-таблицы никогда не превосходит 1/4 размера входного буфера. Если вы хотите установить другое значение - то используйте параметр HashBits (опцию -h). Увеличение HashSize при небольших MinLen способно немного увеличить степень сжатия.

Amplifier: как было описано выше, при поиске проверяется только часть блоков, которой бы с гарантией хватило для нахождения всех строк с длиной >=MinLen - будь у нас идеальное хеширование. Однако наше хеширование неидеально, и часть потенциальных хитов из-за этого теряется. Параметр Amplifier (опция -a) позволяет затребовать тестирование большего числа блоков (в эти самые Amplifier раз). Таким образом, для максимально тщательного поиска можно просто установить Amplifier в достаточно большое значение, скажем 99. Разумеется, это уменьшает скорость и лишь ненамного увеличивает сжатие.

Barrier и SmallestLen: некоторые алгоритмы, в частности ppmd, выигрывают, если препроцессор использует меньшее значение MinLen для больших дистанций. Эти два параметра позволяют установить двухступенчатую границу отбора совпадений, например "в первом мегабайте - MinLen=128, далее MinLen=32" задаётся через MinLen=128, Barrier=1<<20, SmallestLen=32 (опции -l128 -d1048576 -s32). При этом поиск строк настраивается, ес-но, на нахождение строк с длиной от SmallestLen вместо MinLen.

References for RZIP algorithm explanation and implementations:
http://samba.org/~tridge/phd_thesis.pdf
http://rzip.samba.org/ftp/rzip/rzip-2.1.tar.gz
http://ck.kolivas.org/apps/lrzip/lrzip-0.18.tar.bz2
http://www.edcassa-ict.nl/lrzip.zip
http://www.edcassa-ict.nl/rzip21.zip

TAYLOR, R., JANA, R., AND GRIGG, M. 1997. Checksum testing of remote
synchronisation tool. Technical Report 0627 (November), Defence Science and
Technology Organisation, Canberra, Australia. (p.72)


References for LZP algorithm implementations:
http://magicssoft.ru/content/download/G ... pIISRC.zip
http://www.compression.ru/ds/lzp.rar

_________________
bulat_z##mail.ru