 |
| Главная |
| Программы |
| Статьи |
| Разное |
| Форум |
| Контакты |
Теория сжатия данных
Как часто ты слышишь про архивацию, архиваторы, кодеки, мультимедиа компрессоры? Думаю, что ты с ними сталкиваешься на каждом шагу и на то можно приводить множество примеров, начиная от банального использования 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 не используются. Можно ввести следующее обозначение:
| CODE NOW! |
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-ники и так далее.
Достоинства:
- простота реализации.
- малые объемы занимаемой памяти при архивации.
Примерная реализация алгоритма будет иметь вид как на врезке.
Метод Лемпела-Зива
А это совершенно иной подход, основанный не на частости появления байт в тексте, а на повторении слов или части слов в пакуемом тексте. То есть если слово или его участок повторяется, то оно заменяется ссылкой на предыдущее слово, в итоге текстовые данные опять же удается неслабо сжать. Архиватор работает в один проход и составляет лишь словарь, основанный на повторяющихся участках текста. Эффективность сжатия здесь зависит лишь он размеров текстового файла и числа повторений. Маленькие файлы, а тем более отдельные строки сжимать данным алгоритмом сам понимаешь бессмысленно, потому для сжатия каждой строчки массива логов аськи он вряд ли подойдет, а вот для 2 мегового лога одним файлом - самое то :) Алгоритмы реализации можно найти также на любом языке. Кое что ты также найдешь на диске к журналу :) О данном алгоритме ты мог кстати и не слышать, а вот об алгоритме LZW не слышать просто нельзя, так как в свое время он был сильно популярен и на его основе создавалось множество архиваторов. Как ни странно современные архиваторы в большинстве своем также применяют этот алгоритм совместно с Хаффманом для сжатия текстовых файлов. Еще данный алгоритм используется в некоторых форматах графических файлов (в частности всем известный и юзаемый GIF сжимается именно алгоритмом LZW). Теперь думаю нелишним будет сказать пару слов об аббривиатуре. Думаю даже человек не знающий о сжатии абсолютно ничего способен понять, что LZ производное от имен главных разработчиков (Jakob Ziv и Abraham Lempel)... вопрос в том, что за буква W? А все дело вот в чем. Ребята, создавшие алго не спешили его патентовать и его использовать начали абсолютно все, в том числе и разработчики Unix (кто не знает что это такое бежит читать раздел Юниксоид в Xakep’е). Один из них, Терри Велч, вел разработку упаковщика 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 мегабайт в секунду при распаковке и даже поддерживает новомодный HT в 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. Здесь можно скачать библиотеку или сорцы депакера. Также имеется возможность купить либу для коммерческого юзанья, правда за 29 баков.
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. Внушает? Беги качай и не забудь удалить рар (шутка).
Приложения
Распаковщик aplib на сях - как все просто
| CODE NOW! |
| 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); } |
Одна из реализаций метода Хаффмана от VVS Soft Group.
| CODE NOW! |
| 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; |
| отсутствуют |
| :: Последние обновления :: |
| 04.09.2011 Долгожданный релиз VB Decompiler. Масса улучшений декомпиляции Native Code. Значительно расширенна и обновлена справочная система на русском и английском языках. |
| 20.12.2010 DotFix Software поздравляет наших клиентов и посетителей сайта с наступающим Новым Годом и рождеством! Желаем приятно провести праздники и успехов в новом году! |
| 28.11.2010 Выпущена новая версия защиты DotFix NiceProtect. Основные изменения коснулись обфускатора Delphi программ. Теперь имеется полная поддержка Tab и Page контролов на формах, что обеспечивает максимальную совместимость обфускации с Delphi XE программами. |
| 21.10.2010 Обновлен декомпилятор Visual Basic программ до версии 8.1. Декомпиляция P-Code программ становится все более идеальной, также проделана большая работа по улучшению анализа Native Code и .NET приложений. |
| 16.09.2009 Полностью обновлен движок сайта! Теперь все ссылки имеют читаемый понятный вид, разного рода глюки на страницах убраны. И теперь сайт полноценно работает на второй версии нашего движка. |
Движок сайта: DotFix Engine v0.2 Администрация сайта: |