Алгоритмы сжатия

GPcH (admin@dotfix.net)

Спецвыпуск: Хакер, номер #062, стр. 062-062-4

Алгоритм LZMA

Был разработан в 2001 году на основе уже известного нам LZ77 (непатентованный предшественник LZW). Расшифровывается так: Lempel-Ziv-Markov chain-Algorithm. В наше время используется в архиваторе 7zip и в куче китайских exe-упаковщиков. Основное отличие от LZ77 — переменный размер формируемого пакером словаря: может достигать 4 Гб, но и распаковка при этом потребует гору памяти. Также алгоритм использует хэш цепочки и формирует деревья бинарного и Patricia-типа. Patricia — это никакая не Патрисия :), а Practical Algorithm to Retrieve Information Coded in Alphanumeric, описанный еще в 1968 году Дональдом Моррисом и используемый для построения ассоциативных целочисленных массивов древовидного типа. Для сжатия бинарных данных lzma использует BCJ/BCJ2-алгоритм, способный разбирать 32-битные команды и анализировать call'ы и jmp'ы на код, благодаря этому улучшается сжатие с учетом архитектуры x86-процессоров. Несмотря на то, что алгоритм, по сути, дизассемблирует программу, он работает довольно быстро: 1 Mб в секунду на Pentium II при сжатии и 10 Мб в секунду при распаковке, даже поддерживается новомодный HT в Pentium-процессорах. Если ты решил обратиться к услугам данного алгоритма, порадую тебя тем, что его исходники портированы под многие ОС, а не только под Windows. Автор даже не требует отчислений за использование алгоритма в коммерческих программах, а лишь ставит условие, согласно которому запрещается модифицировать алгоритм. Авторы aplib просят более $20 за коммерческое использование, а исходников все равно не дают. Так что lzma — лучший выбор.

Тип: WWW

www.compression.ru — луЧший российский сайт по сжатию данных. тут ты найдешь гору информации и исходников практиЧески по всем алгоритмам. размах сайта просто поражает. исходники разбиты даже на категории по Языкам. есть отрывки из книги «методы сжатиЯ данных». в общем, если найдешь российский сайт по сжатию мощнее этого, пришли мне ссылоЧку :).

www.7-zip.org — сайт автора архиватора 7zip. помимо самого архиватора, тут можно найти исходник алгоритма lzma и поЧитать самую свежую информацию по нему. если решишь попользоватьсЯ, оЧень рекомендую заглЯнуть в лицензию — она оЧень лоЯльна.

www.bitsum.com/jcalg1.htm — страниЧка посвЯщена алгоритму jcalg1. дано подробное описание по использованию и таблица сравнениЯ. особенно радует лицензионное соглашение: «this library may be used freely in any and for any application».