Автор: Сергей Чубченко. Дата публикации: 16.03.2006
Как часто Вы слышите про архивацию, архиваторы, кодеки, мультимедиа компрессоры? Думаю, что Вы с ними сталкиваетесь на каждом шагу и на то можно приводить множество примеров, начиная от банального использования WinRAR’а и заканчивая поиски в интернете малоизвестного кодека-декомпрессора для просмотра какого нибудь видео файла. В этой статье я не буду загружать Вас рассказами где искать компрессоры и как их использовать. Здесь я пожалуй посвящу Вас в саму методику упаковки, с чего начали расти ее корни и возможно прочитав данный материал Вы зададитесь целью написать свой собственный архиватор обобщив имеющиеся идеи в что-то более новое и мощное. Пожалуй начнем.
Как возникла идея
Пока не существовало компьютеров - об экономии места никто не задумывался, более того все силы были направлены на криптографию и основные исследования в области данных в основном велись в сторону их шифрования. Это продолжалось начиная еще с эпохи таких древних цивилизаций как Рим, Греция и существовало всегда, так как люди вечно что-то, да скрывали друг от друга. Многое поменялось с созданием первых ЭВМ, размеры которых были вне всякой критики, а объемы жестких дисков были меньше, чем даже ПЗУ в первых мобильных телефонах. Тут то весь прогрессивный мир и задумался на тему, как же все таки в такой маленький объем памяти поместить как можно больше полезных документов. В это время ученые и начали предлагать свои наработки, но большинство из этих теорем лишь могли доказать возможность сжатия тех или иных данных, о сжатии же и тем более расжатии без потерь особо речи не шло. Так постепенно и родился энтропийный анализ данных, позволяющий оценить компактность хранения информации и возможность ее сжатия. Постепенно идеи начали воплощать в реальность. Была предложена идея сжатия путем подсчета частоты появления тех или иных байт в тексте. Ее суть состояла в том что текст первоначально оценивается упаковщиком, считается частота появления в тексте каждой буквы, встречающейся в нем, частота повторения участков текста и так далее, составляется таблица этих самых частот и по ней уже вторым проходом происходит упаковка/распаковка. Этот метод надолго засел в умах разработчиков. Идеальной его реализацией можно считать алгоритм Хаффмана и его последующие доработки. Вкратце рассмотрим этот метод.
Метод Хаффмана
Как известно, текстовый файл состоит из фиксированного набора символов. Например, возьмём эту статью. В ней используются маленькие и большие буквы русского алфавита, знаки препинания. То есть, количество используемых символов меньше, чем 256(Ascii таблица). Но компьютер, всё равно сохранит текстовый файл в 8 битной кодировке (2^8=256). Значит, больше половины символов Ascii таблицы вообще не используются. Наша задача - сделать так, чтобы использовались как можно больше символов. К примеру, имеем Ascii таблицу, состоящую из 10 символов (0,1,2,3,4,5,6,7,8,9). У нас есть текст "00112233011223322113". Как видишь, символы 4,5,6,7,8,9 не используются. Можно ввести следующее обозначение:
Таким образом, наш текст можно записать в виде: "0123456789". То есть, как видим, текст теперь занимает в 2 раза меньше, чем был. В нём используются все допустимые символы. Чтобы получить исходный текст, необходимо согласно обозначению, заменить обратно символы на их комбинацию. Теперь, когда мы поняли смысл метода Хаффмана, пожалуй рассмотрим его детальнее.
Сначала в тексте подсчитывается количество повторяющихся символов. К примеру, символ "А" повторяется 100 раз, символ "В" повторяется 300 раз и так далее. Далее символы сортируются по убыванию или возрастания согласно их количеству появления в тексте. Потом составляется дерево Хаффмана на подобии наших символов, которые обозначали их комбинацию("00" - 0,"11" - 1 и так далее). Только дерево Хаффмана призвано максимально уменьшить количество символов в заархивированном тексте, поэтому оно составляется несколько иначе. Мы уже отсортировали символы, согласно их количеству. Теперь берём символ с наименьшей частотой появления и объединяем его с символом, стоящим на втором месте. Получаем новый символ с частотой появления равной сумме частот, входящих в него символов. Далее делаем то же самое с другими символами (объединённые символы со счетов не сбрасывай). В конце-концов у нам получится один символ с частотой появления равной размеру файла. Теперь посмотрим, что получилось. Раньше у нас каждый символ кодировался восемью битами. Теперь, чтобы получить код символа, необходимо двигаться с низу дерева к её вершине по веткам, если идёшь направо по ветке, пиши 1, если налево 0. В итоге, двигаясь по веткам, мы рано или поздно наткнёмся на один из исходных символов. То что мы записали, двигаясь по веткам и будет его код. Как видим, у символов, которые часто встречаются код занимает меньше, чем у тех, которые встречаются реже. Наша задача составить коды для всех символов. Теперь, зная коды, заменяем на них все символы в тексте. Всё! Текст заархивирован. Что самое обидное, таблицу кодов символов надо сохранить вместе с заархивированным текстом. Это увеличит размер, но не на много, если сам файл до архивации занимал много места. Вывод напрашивается сам собой: метод Хаффмана не стоит применять, если размер файл мал. Теперь обратный процесс. У нас есть дерево и заархивированный текст. Считываем первый бит, если он 0, идёшь влево, если 1 вправо с низу дерева. В итоге, считывая следующие биты, мы рано или поздно наткнемся на какой-нибудь символ. Это и будет символ исходного текста. Получили первый символ, не останавливайтесь на достигнутом, опускайтесь вниз дерева и считывайте следующий бит. В итоге, мы получим всю последовательность исходного текста.
Основные недостатки этого метода:
Достоинства:
Примерная реализация алгоритма будет иметь вид как в приложении 1.
Метод Лемпела-Зива
А это совершенно иной подход, основанный не на частости появления байт в тексте, а на повторении слов или части слов в пакуемом тексте. То есть если слово или его участок повторяется, то оно заменяется ссылкой на предыдущее слово, в итоге текстовые данные опять же удается неслабо сжать. Архиватор работает в один проход и составляет лишь словарь, основанный на повторяющихся участках текста. Эффективность сжатия здесь зависит лишь он размеров текстового файла и числа повторений. Маленькие файлы, а тем более отдельные строки сжимать данным алгоритмом сами понимаете бессмысленно, потому для сжатия каждой строчки массива логов аськи он вряд ли подойдет, а вот для 2 мегового лога одним файлом - самое то. Алгоритмы реализации можно найти также на любом языке. О данном алгоритме Вы могли кстати и не слышать, а вот об алгоритме LZW не слышать было просто нереально, так как в свое время он был сильно популярен и на его основе создавалось множество архиваторов. Как ни странно современные архиваторы в большинстве своем также применяют этот алгоритм совместно с Хаффманом для сжатия текстовых файлов. Еще данный алгоритм используется в некоторых форматах графических файлов (в частности всем известный и используемый формат GIF сжимается именно алгоритмом LZW). Теперь думаю нелишним будет сказать пару слов об аббривиатуре. Думаю даже человек не знающий о сжатии абсолютно ничего, способен понять, что LZ производное от имен главных разработчиков (Jakob Ziv и Abraham Lempel)... вопрос в том, что за буква W? А все дело вот в чем. Ребята, создавшие алгоритм не спешили его патентовать и его использовать начали абсолютно все, в том числе и разработчики Unix. Один из них, Терри Велч, вел разработку упаковщика compress и соответственно по мере изменения пакера изменял и LZW движок, всячески оптимизируя его, тем самым навсегда оставшись в истории, занеся свое имя третьим в аббревиатуру алгоритма. Потом конечно алгоритм не раз модифицировался, но так как модификации носили в основном незначительный характер, авторы добавлений не стали расширять аббревиатуру. Вот такая вот история.
Метод RLE
Раз уж мы заговорили об изображениях, думаю нелишним будет рассказать про алгоритм Run Length Encoding. Он применяется в формате изображений PCX (помните еще такой? он использовался для сохранения черно-белых изображений) и работает вот как. Исходное изображение, представляющее цепочку байт, исследуется на наличие повторяющихся цепочек данных. Если изображение черно-белое, то длинна таких цепочек может быть очень большой. Это и использует алгоритм для компрессии данных, вместо цепочки байт вставляя сначала счетчик повторений, потом собственно повторяемое значение. Так как цвета 2 и счетчик повторений занимает 6 бит, то такую цепочку вполне реально ужать в 1 байт. Классная компрессия, правда? А вот и не очень :( Для полноцветной графики, а уж тем более для сжатия фотографий он не годится, потому его ниша - сжатие черно-белых чертежей.
Метод JPEG
Разработан он был группой специалистов по сжатию фотографий Joint Photographic Expert Group. До сих пор у него нет особенных конкурентов в области сжатия изображений фотографического качества. Метод основан на дискретном косинусоидальном преобразовании участков 8*8 матрицы изображения. При этом изображение раскладывается по амплитудам некоторых частот с последующим квантованием с учетом характеристик человеческого зрения, что дает малую видимую потерю качества, зато высокий уровень сжатия. Так как алгоритм стандартизован ISO он поддерживается многими языками программирования без использования сторонних компонентов или исходников, потому грех не использовать его везде где только можно.
Сжатие бинарных данных
Я думаю нелишним напомнить, что все описанные выше алгоритмы не способны хорошо сжать файл имеющий если не всю кодировку символов, то почти всю. К таким файлам относятся в первую очередь программы, библиотеки и драйвера. Возможно Вы помните мою статью Обзор упаковщиков приложений и прочего бинарного кода. Их там я описал очень много, причем их раз в 10 больше. Откуда же столько? Неужто столько алгоритмов было разработано программистами? Неуж-то мы настолько продвинулись, что каждый в силах написать пакер для экзешников? А вот и нет, просто есть 3 распространенных алгоритма, которые все активно используют и даже не пишут в справке к пакеру, что использовали не свой алгоритм сжатия. Но это мы отвлеклись. Давайте поговорим непосредственно об этих алгоритмах. Алгоритмы эти - aplib, jcalg и новомодный lzma. Самый простой и удобный из них - aplib, самое лучшее сжатие имеет lzma. Логичным будет поближе рассмотреть последний, как самый перспективный на сегодняшний день.
Алгоритм 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 Mb в секунду на Pentium II при сжатии и 10 мегабайт в секунду при распаковке и даже поддерживает новомодный Hyper Threading в Pentium процессорах. Если Вы решили заюзать данный алгоритм обрадую - его исходники портированы под многие ОС, а не только под винду. При этом автор даже не требует отчислений за использование алгоритма в коммерческих программах, а лишь ставит условие, что при этом модифицировать алгоритм нельзя. Это очень полезно, ведь авторы aplib за коммерческое использование просят более 20 долларов, при этом все равно не дают исходники. Потому lzma - лучший выбор.
Интернет Вам в помощь
Если Вы заинтересовались темой, то лучшим помощником будет первоисточник, потому рекомендую почитать следующие сайты:
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.
www.ibsensoftware.com - сайт авторов aplib. Здесь можно скачать библиотеку или сорцы депакера. Также имеется возможность купить библиотеку для коммерческого использования.
http://en.wikipedia.org - несмотря на то что это просто энциклопедия - именно в ней очень подробно рассмотрены многие алгоритмы сжатия, рассказано про их авторов и даны архиполезные перекрестные ссылки на описание различных технологий, используемых при построении того или иного алгоритма. Короче, просто обязана быть у Вас в закладках.
Чтобы Вы не искали в энциклопедии каждый алгоритм - вот ссылка:
http://en.wikipedia.org/wiki/Category:Lossless_compression_algorithms
Сайты популярных архиваторов:
www.rarlab.com - лучший на мой взгляд архиватор. Постоянно развивается.
www.7-zip.org - лучший по сжатию архиватор. Имеются порты под линукс. Распространяется бесплатно, потому и рекламы его почти нет.
www.winace.com - неплохой, но уже почти забытый. Причина тому - нет динамики развития, присущей WinRAR, а сжатие слабее чем у 7zip
www.winzip.com - ну про zip думаю знают все. Единственный архиватор который есть у всех и даже встроен в винду. Сжатие конечно не супер, но это стандарт дефакто для распространения архивов в сети интернет.
www.powerarchiver.com - довольно мощный пакер. Сжимает в формате 7zip, при этом платный - стоит около $20
www.izarc.org - ну наконец-то, единственный путевый пакер, который можно получить абсолютно бесплатно. При всем при этом имеется поддержка таких форматов как 7-ZIP, A, ACE, ARC, ARJ, B64, BH, BIN, BZ2, BZA, C2D, CAB, CDI, CPIO, DEB, ENC, GCA, GZ, GZA, HA, IMG, ISO, JAR, LHA, LIB, LZH, MDF, MBF, MIM, NRG, PAK, PDI, PK3, RAR, RPM, TAR, TAZ, TBZ, TGZ, TZ, UUE, WAR, XXE, YZ1, Z, ZIP, ZOO. Внушает?
Приложение 1: Распаковщик aplib на сях - как все просто
Приложение 2: Одна из реализаций метода Хаффмана от VVS Soft Group.
Теория сжатия данных
Как часто Вы слышите про архивацию, архиваторы, кодеки, мультимедиа компрессоры? Думаю, что Вы с ними сталкиваетесь на каждом шагу и на то можно приводить множество примеров, начиная от банального использования WinRAR’а и заканчивая поиски в интернете малоизвестного кодека-декомпрессора для просмотра какого нибудь видео файла. В этой статье я не буду загружать Вас рассказами где искать компрессоры и как их использовать. Здесь я пожалуй посвящу Вас в саму методику упаковки, с чего начали расти ее корни и возможно прочитав данный материал Вы зададитесь целью написать свой собственный архиватор обобщив имеющиеся идеи в что-то более новое и мощное. Пожалуй начнем.
Как возникла идея
Пока не существовало компьютеров - об экономии места никто не задумывался, более того все силы были направлены на криптографию и основные исследования в области данных в основном велись в сторону их шифрования. Это продолжалось начиная еще с эпохи таких древних цивилизаций как Рим, Греция и существовало всегда, так как люди вечно что-то, да скрывали друг от друга. Многое поменялось с созданием первых ЭВМ, размеры которых были вне всякой критики, а объемы жестких дисков были меньше, чем даже ПЗУ в первых мобильных телефонах. Тут то весь прогрессивный мир и задумался на тему, как же все таки в такой маленький объем памяти поместить как можно больше полезных документов. В это время ученые и начали предлагать свои наработки, но большинство из этих теорем лишь могли доказать возможность сжатия тех или иных данных, о сжатии же и тем более расжатии без потерь особо речи не шло. Так постепенно и родился энтропийный анализ данных, позволяющий оценить компактность хранения информации и возможность ее сжатия. Постепенно идеи начали воплощать в реальность. Была предложена идея сжатия путем подсчета частоты появления тех или иных байт в тексте. Ее суть состояла в том что текст первоначально оценивается упаковщиком, считается частота появления в тексте каждой буквы, встречающейся в нем, частота повторения участков текста и так далее, составляется таблица этих самых частот и по ней уже вторым проходом происходит упаковка/распаковка. Этот метод надолго засел в умах разработчиков. Идеальной его реализацией можно считать алгоритм Хаффмана и его последующие доработки. Вкратце рассмотрим этот метод.
Метод Хаффмана
Как известно, текстовый файл состоит из фиксированного набора символов. Например, возьмём эту статью. В ней используются маленькие и большие буквы русского алфавита, знаки препинания. То есть, количество используемых символов меньше, чем 256(Ascii таблица). Но компьютер, всё равно сохранит текстовый файл в 8 битной кодировке (2^8=256). Значит, больше половины символов Ascii таблицы вообще не используются. Наша задача - сделать так, чтобы использовались как можно больше символов. К примеру, имеем Ascii таблицу, состоящую из 10 символов (0,1,2,3,4,5,6,7,8,9). У нас есть текст "00112233011223322113". Как видишь, символы 4,5,6,7,8,9 не используются. Можно ввести следующее обозначение:
00 - 0
11 - 1
22 - 2
33 - 3
01 - 4
12 - 5
23 - 6
32 - 7
21 - 8
13 - 9
Таким образом, наш текст можно записать в виде: "0123456789". То есть, как видим, текст теперь занимает в 2 раза меньше, чем был. В нём используются все допустимые символы. Чтобы получить исходный текст, необходимо согласно обозначению, заменить обратно символы на их комбинацию. Теперь, когда мы поняли смысл метода Хаффмана, пожалуй рассмотрим его детальнее.
Сначала в тексте подсчитывается количество повторяющихся символов. К примеру, символ "А" повторяется 100 раз, символ "В" повторяется 300 раз и так далее. Далее символы сортируются по убыванию или возрастания согласно их количеству появления в тексте. Потом составляется дерево Хаффмана на подобии наших символов, которые обозначали их комбинацию("00" - 0,"11" - 1 и так далее). Только дерево Хаффмана призвано максимально уменьшить количество символов в заархивированном тексте, поэтому оно составляется несколько иначе. Мы уже отсортировали символы, согласно их количеству. Теперь берём символ с наименьшей частотой появления и объединяем его с символом, стоящим на втором месте. Получаем новый символ с частотой появления равной сумме частот, входящих в него символов. Далее делаем то же самое с другими символами (объединённые символы со счетов не сбрасывай). В конце-концов у нам получится один символ с частотой появления равной размеру файла. Теперь посмотрим, что получилось. Раньше у нас каждый символ кодировался восемью битами. Теперь, чтобы получить код символа, необходимо двигаться с низу дерева к её вершине по веткам, если идёшь направо по ветке, пиши 1, если налево 0. В итоге, двигаясь по веткам, мы рано или поздно наткнёмся на один из исходных символов. То что мы записали, двигаясь по веткам и будет его код. Как видим, у символов, которые часто встречаются код занимает меньше, чем у тех, которые встречаются реже. Наша задача составить коды для всех символов. Теперь, зная коды, заменяем на них все символы в тексте. Всё! Текст заархивирован. Что самое обидное, таблицу кодов символов надо сохранить вместе с заархивированным текстом. Это увеличит размер, но не на много, если сам файл до архивации занимал много места. Вывод напрашивается сам собой: метод Хаффмана не стоит применять, если размер файл мал. Теперь обратный процесс. У нас есть дерево и заархивированный текст. Считываем первый бит, если он 0, идёшь влево, если 1 вправо с низу дерева. В итоге, считывая следующие биты, мы рано или поздно наткнемся на какой-нибудь символ. Это и будет символ исходного текста. Получили первый символ, не останавливайтесь на достигнутом, опускайтесь вниз дерева и считывайте следующий бит. В итоге, мы получим всю последовательность исходного текста.
Основные недостатки этого метода:
- приходится таскать с собой дерево Хаффмана;
- приходится сканировать текст 2 раза. Первый при подсчёте частот появления символов, второй при архивации;
- мизерная степень сжатия файлов, содержащих почти все символы Ascii-таблицы. Например, exe-шники, obj файлы и так далее.
Достоинства:
- простота реализации;
- малые объемы занимаемой памяти при архивации.
Примерная реализация алгоритма будет иметь вид как в приложении 1.
Метод Лемпела-Зива
А это совершенно иной подход, основанный не на частости появления байт в тексте, а на повторении слов или части слов в пакуемом тексте. То есть если слово или его участок повторяется, то оно заменяется ссылкой на предыдущее слово, в итоге текстовые данные опять же удается неслабо сжать. Архиватор работает в один проход и составляет лишь словарь, основанный на повторяющихся участках текста. Эффективность сжатия здесь зависит лишь он размеров текстового файла и числа повторений. Маленькие файлы, а тем более отдельные строки сжимать данным алгоритмом сами понимаете бессмысленно, потому для сжатия каждой строчки массива логов аськи он вряд ли подойдет, а вот для 2 мегового лога одним файлом - самое то. Алгоритмы реализации можно найти также на любом языке. О данном алгоритме Вы могли кстати и не слышать, а вот об алгоритме LZW не слышать было просто нереально, так как в свое время он был сильно популярен и на его основе создавалось множество архиваторов. Как ни странно современные архиваторы в большинстве своем также применяют этот алгоритм совместно с Хаффманом для сжатия текстовых файлов. Еще данный алгоритм используется в некоторых форматах графических файлов (в частности всем известный и используемый формат GIF сжимается именно алгоритмом LZW). Теперь думаю нелишним будет сказать пару слов об аббривиатуре. Думаю даже человек не знающий о сжатии абсолютно ничего, способен понять, что LZ производное от имен главных разработчиков (Jakob Ziv и Abraham Lempel)... вопрос в том, что за буква W? А все дело вот в чем. Ребята, создавшие алгоритм не спешили его патентовать и его использовать начали абсолютно все, в том числе и разработчики Unix. Один из них, Терри Велч, вел разработку упаковщика compress и соответственно по мере изменения пакера изменял и LZW движок, всячески оптимизируя его, тем самым навсегда оставшись в истории, занеся свое имя третьим в аббревиатуру алгоритма. Потом конечно алгоритм не раз модифицировался, но так как модификации носили в основном незначительный характер, авторы добавлений не стали расширять аббревиатуру. Вот такая вот история.
Метод RLE
Раз уж мы заговорили об изображениях, думаю нелишним будет рассказать про алгоритм Run Length Encoding. Он применяется в формате изображений PCX (помните еще такой? он использовался для сохранения черно-белых изображений) и работает вот как. Исходное изображение, представляющее цепочку байт, исследуется на наличие повторяющихся цепочек данных. Если изображение черно-белое, то длинна таких цепочек может быть очень большой. Это и использует алгоритм для компрессии данных, вместо цепочки байт вставляя сначала счетчик повторений, потом собственно повторяемое значение. Так как цвета 2 и счетчик повторений занимает 6 бит, то такую цепочку вполне реально ужать в 1 байт. Классная компрессия, правда? А вот и не очень :( Для полноцветной графики, а уж тем более для сжатия фотографий он не годится, потому его ниша - сжатие черно-белых чертежей.
Метод JPEG
Разработан он был группой специалистов по сжатию фотографий Joint Photographic Expert Group. До сих пор у него нет особенных конкурентов в области сжатия изображений фотографического качества. Метод основан на дискретном косинусоидальном преобразовании участков 8*8 матрицы изображения. При этом изображение раскладывается по амплитудам некоторых частот с последующим квантованием с учетом характеристик человеческого зрения, что дает малую видимую потерю качества, зато высокий уровень сжатия. Так как алгоритм стандартизован ISO он поддерживается многими языками программирования без использования сторонних компонентов или исходников, потому грех не использовать его везде где только можно.
Сжатие бинарных данных
Я думаю нелишним напомнить, что все описанные выше алгоритмы не способны хорошо сжать файл имеющий если не всю кодировку символов, то почти всю. К таким файлам относятся в первую очередь программы, библиотеки и драйвера. Возможно Вы помните мою статью Обзор упаковщиков приложений и прочего бинарного кода. Их там я описал очень много, причем их раз в 10 больше. Откуда же столько? Неужто столько алгоритмов было разработано программистами? Неуж-то мы настолько продвинулись, что каждый в силах написать пакер для экзешников? А вот и нет, просто есть 3 распространенных алгоритма, которые все активно используют и даже не пишут в справке к пакеру, что использовали не свой алгоритм сжатия. Но это мы отвлеклись. Давайте поговорим непосредственно об этих алгоритмах. Алгоритмы эти - aplib, jcalg и новомодный lzma. Самый простой и удобный из них - aplib, самое лучшее сжатие имеет lzma. Логичным будет поближе рассмотреть последний, как самый перспективный на сегодняшний день.
Алгоритм 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 Mb в секунду на Pentium II при сжатии и 10 мегабайт в секунду при распаковке и даже поддерживает новомодный Hyper Threading в Pentium процессорах. Если Вы решили заюзать данный алгоритм обрадую - его исходники портированы под многие ОС, а не только под винду. При этом автор даже не требует отчислений за использование алгоритма в коммерческих программах, а лишь ставит условие, что при этом модифицировать алгоритм нельзя. Это очень полезно, ведь авторы aplib за коммерческое использование просят более 20 долларов, при этом все равно не дают исходники. Потому lzma - лучший выбор.
Интернет Вам в помощь
Если Вы заинтересовались темой, то лучшим помощником будет первоисточник, потому рекомендую почитать следующие сайты:
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.
www.ibsensoftware.com - сайт авторов aplib. Здесь можно скачать библиотеку или сорцы депакера. Также имеется возможность купить библиотеку для коммерческого использования.
http://en.wikipedia.org - несмотря на то что это просто энциклопедия - именно в ней очень подробно рассмотрены многие алгоритмы сжатия, рассказано про их авторов и даны архиполезные перекрестные ссылки на описание различных технологий, используемых при построении того или иного алгоритма. Короче, просто обязана быть у Вас в закладках.
Чтобы Вы не искали в энциклопедии каждый алгоритм - вот ссылка:
http://en.wikipedia.org/wiki/Category:Lossless_compression_algorithms
Сайты популярных архиваторов:
www.rarlab.com - лучший на мой взгляд архиватор. Постоянно развивается.
www.7-zip.org - лучший по сжатию архиватор. Имеются порты под линукс. Распространяется бесплатно, потому и рекламы его почти нет.
www.winace.com - неплохой, но уже почти забытый. Причина тому - нет динамики развития, присущей WinRAR, а сжатие слабее чем у 7zip
www.winzip.com - ну про zip думаю знают все. Единственный архиватор который есть у всех и даже встроен в винду. Сжатие конечно не супер, но это стандарт дефакто для распространения архивов в сети интернет.
www.powerarchiver.com - довольно мощный пакер. Сжимает в формате 7zip, при этом платный - стоит около $20
www.izarc.org - ну наконец-то, единственный путевый пакер, который можно получить абсолютно бесплатно. При всем при этом имеется поддержка таких форматов как 7-ZIP, A, ACE, ARC, ARJ, B64, BH, BIN, BZ2, BZA, C2D, CAB, CDI, CPIO, DEB, ENC, GCA, GZ, GZA, HA, IMG, ISO, JAR, LHA, LIB, LZH, MDF, MBF, MIM, NRG, PAK, PDI, PK3, RAR, RPM, TAR, TAZ, TBZ, TGZ, TZ, UUE, WAR, XXE, YZ1, Z, ZIP, ZOO. Внушает?
Приложение 1: Распаковщик aplib на сях - как все просто
unsigned int aP_depack(unsigned char *source, unsigned char *destination)
{
unsigned int offs, len, R0, LWM;
int done; int i; aP_d_input = source;
aP_d_output = destination; LWM = 0;
aP_d_tagpos = 0; *aP_d_output = *aP_d_input;
aP_d_output++; aP_d_input++; done = 0;
while (!done)
{ if (aP_d_getbit()) { if (aP_d_getbit()) {
if (aP_d_getbit())
{
offs = 0;
for (i = 4; i; i--) offs = (offs << 1) + aP_d_getbit();
if (offs)
{
*aP_d_output = *(aP_d_output - offs);
aP_d_output++;
} else {
*aP_d_output = 0x00;
aP_d_output++;
}
LWM = 0;
} else {
offs = *aP_d_input;
aP_d_input++;
len = 2 + (offs & 0x0001);
offs >>= 1;
if (offs)
{
for (; len; len--)
{
*aP_d_output = *(aP_d_output - offs);
aP_d_output++;
}
} else done = 1;
R0 = offs;
LWM = 1;
}
} else {
offs = aP_d_getgamma();
if ((LWM == 0) && (offs == 2))
{
offs = R0;
len = aP_d_getgamma();
for (; len; len--)
{
*aP_d_output = *(aP_d_output - offs);
aP_d_output++;
}
} else {
if (LWM == 0) offs -= 3; else offs -= 2;
offs <<= 8;
offs += *aP_d_input;
aP_d_input++;
len = aP_d_getgamma();
if (offs >= 32000) len++;
if (offs >= 1280) len++;
if (offs < 128) len += 2;
for (; len; len--)
{
*aP_d_output = *(aP_d_output - offs);
aP_d_output++;
}
R0 = offs;
}
LWM = 1;
}
} else { *aP_d_output = *aP_d_input;
aP_d_output++; aP_d_input++;
LWM = 0; } }
return (aP_d_output - destination);
}
Приложение 2: Одна из реализаций метода Хаффмана от VVS Soft Group.
procedure PakOneByte;
{ --- сжатие и пересылка в выходной буфер одного байта --- }
Var Mask : word;
Tail : boolean;
begin
CRC:=CRC XOR InBuf[InCounter];
Mask:=CodeTable[InBuf[InCounter]]^.BiteChain SHR CounterBite;
OutWord:=OutWord OR Mask;
CounterBite:=CounterBite+CodeTable[InBuf[InCounter]]^.LengthBiteChain;
If CounterBite>15 then Tail:=True else Tail:=False;
While CounterBite>7 do
begin
OutBuf[OutCounter]:=Hi(OutWord);
Inc(OutCounter);
If OutCounter=(SizeOf(OutBuf)-4) then
begin
BlockWrite(OutputF,OutBuf,OutCounter,NumWritten);
OutCounter:=0;
end;
CounterBite:=CounterBite-8;
If CounterBite<>0 then OutWord:=OutWord SHL 8 else OutWord:=0;
end;
If Tail then
begin
Mask:=CodeTable[InBuf[InCounter]]^.BiteChain SHL
(CodeTable[InBuf[InCounter]]^.LengthBiteChain-CounterBite);
OutWord:=OutWord OR Mask;
end;
Inc(InCounter);
If (InCounter=(SizeOf(InBuf))) or (InCounter=NumRead) then
begin
InCounter:=0;
BlockRead(InputF,InBuf,SizeOf(InBuf),NumRead);
end;
end;
procedure PakFile;
{ --- процедура непосредственного сжатия файла --- }
begin
ResetFile;
SearchNameInArchiv;
If NormalWork then
begin
BlockRead(InputF,InBuf,SizeOf(InBuf),NumRead);
OutWord:=0;
CounterBite:=0;
OutCounter:=0;
InCounter:=0;
CRC:=0;
CreateCodeArchiv;
While (NumRead<>0) do PakOneByte;
OutBuf[OutCounter]:=Hi(OutWord);
Inc(OutCounter);
OutBuf[OutCounter]:=CRC;
Inc(OutCounter);
BlockWrite(OutputF,OutBuf,OutCounter,NumWritten);
DisposeCodeTable;
ClosePakFile;
end;
end;
Комментарии |
| отсутствуют |
Добавление комментария |