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

GPcH (admin@dotfix.net)

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

Метод RLE

Алгоритм Run Length Encoding применяется в формате изображений PCX (Помнишь такой? Использовался для сохранения черно-белых изображений) и работает вот так. Исходное изображение, представляющее собой цепочку байт, исследуется на наличие повторяющихся цепочек данных. Если изображение черно-белое, то длина таких цепочек может быть очень большой. Вот и работа для алгоритма по компрессии данных: вместо цепочки байт вставляется сначала счетчик повторений, потом собственно повторяемое значение. Так как в изображении всего два цвета и счетчик повторений занимает шесть бит, вполне реально ужать такую цепочку до одного байта. Классная компрессия, правда? Нет, неправда :(. Как бы ни был прост описанный метод, он не годится для полноцветной графики, тем более для сжатия фотографий. Его ниша — сжатие черно-белых чертежей.

Метод JPEG

Разработан группой специалистов по сжатию фотографий Joint Photographic Expert Group. До сих пор не имеет особенных конкурентов в области сжатия изображений фотографического качества. Метод основан на дискретном косиносуидальном преобразовании участков 8*8 матрицы изображения. Изображение раскладывается по амплитудам некоторых частот с последующим квантованием. Идет учет характеристик человеческого зрения, что делает потери качества незаметными «на глаз», зато достигается высокий уровень сжатия. Так как алгоритм стандартизован ISO, он поддерживается многими языками программирования и не требует сторонних компонентов или исходников. Грех не попользоваться :).

Сжатие бинарных данных

Нелишним будет напомнить, что все описанные алгоритмы неспособны хорошо сжать файл, имеющий если не всю кодировку символов, то почти всю. К таким файлам относятся, в первую очередь, программы, библиотеки и драйверы. Если ты внимательно читал Спец по крэкингу, то помнишь мою статью — обзор упаковщиков приложений и прочего бинарного кода. Я описал много всего, но на самом деле упаковщиков раз в десять больше :). Откуда же столько? Неужели толпа алгоритмов была разработана программистами? Неужели мы настолько продвинулись, что каждый в силах написать пакер для eхе'шников? Есть три распространенных алгоритма, все кому не лень пользуются ими и даже в справке к пакеру не пишут, что использовали чужой алгоритм сжатия :). Однако мы отвлеклись. Поговорим непосредственно об алгоритмах: aplib, jcalg и новомодный lzma. Самый простой и удобный из них — aplib, самое лучшее сжатие — lzma. Для логичности поближе рассмотрим последний, как самый перспективный на сегодняшний день.