Адские тиски правосудия

Косякин Антон

Xakep, номер #066, стр. 066-112-2

RLE

Для начала рассмотрим, на мой взгляд, самый древний алгоритм - RLE (групповое кодирование). Уверен, что если ты интересовался работой архиваторов и размышлял на тему сжатия, то первое, что тебе пришло в голову, как раз и был этот алгоритм. Он очень прост в теории и еще проще в реализации. Суть этого метода кодирования в поиске и замене одинаковых цепочек байт парами "счетчик, значение". Одна из его реализаций такова: в файле ищут наименее часто встречающийся байт и называют его префиксом. Затем делают замены цепочек одинаковых символов тройками "префикс, счетчик, значение". Если этот байт встречается в исходном файле один или два раза подряд - его заменяют парой "префикс, 1" или "префикс, 2". А неиспользованную пару "префикс, 0" - вполне можно использовать как признак конца упакованных данных.

Если мы пытаемся сжать exe-файл, то можно искать и кодировать последовательности типа AxAyAz..., которые довольно часто встречаются в ресурсах (строки в Unicode). Также этот алгоритм используется в форматах PCX, TIFF, BMP. Интересно, что если в некоторых файлах PCX изменить порядок цветов в палитре изображения, то степень архивации существенно возрастет.

LZ-семейство

Более чем уверен, что метод RLE-кодирования тебе не совсем пришелся по душе - уж очень все просто. И неэффективно. Развитием этого метода является целое семейство алгоритмов, именуемых LZ-алгоритмами.

Существует неверное представление, что за понятием LZ-метода стоит один-единственный алгоритм. Это не так. Первые статьи Зива и Лемпеля были глубоко теоретическими, и лишь последующие переложения других авторов дали более доступное представление.

Итак, в методе Зива-Лемпеля кодируемый текст разбивается на небольшие строки, каждая из которых составлена из одной из предыдущих строк (также заранее предопределена пустая строка, имеющая код 0) и еще одного символа. Чтобы немного отойти от скучного и нудного повествования, приведу пример. Пусть нам нужно закодировать строку "пусть_нам_нужно_закодировать_строку" :):

Закодированная строка

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

п у с т ь _ н а м _н уж но _ з ак о д и р ов ат ь_ ст ро к у<EOF>

0п 0у 0с 0т 0ь 0_ 0н 0а 0м 6н 2ж 7о 6з 0з 8к 0о 0д 0и 0р 16в 8т 5_ 3т 19о 0к 2<EOF>

Вверху записаны номера строк, затем сами строки, а далее - представление каждой из них в виде пар (номер_предыдущей_строки, дополняющий_символ). Как видно из примера, вначале образовалось 9 строк длины 1, затем 10-я буква совпала с 6-й строкой, поэтому 10-я строка имеет длину 2 и составлена из 6-й строки и буквы "н". Аналогично 11-я и 12-я строки. Дальше, думаю, разберешься и сам :). В данном случае сжатия особо не получилось - кодируемая строка была очень короткой. Но при увеличении длины исходной строки приведенный выше алгоритм заработает, даю слово.

Собственно подход к сжатию данных был впервые обнародован в 1977 г., но в 1984 человек по имени Тэрри Вэлч (Terry Welch) опубликовал усовершенствованный вариант метода (LZW-сжатие). И снова алгоритм на удивление прост. Если говорить коротко, то LZW-сжатие заменяет строки символов некоторыми кодами, что делается без какого-либо анализа входного текста. Вместо этого при добавлении каждой новой строки символов просматривается таблица строк. Сжатие происходит, когда код заменяет строку символов. Коды, получаемые на выходе данного алгоритма, могут быть любой длины, но они должны содержать больше бит, чем единичный символ. Первые 256 кодов (когда используются 8-битные символы) изначально соответствуют стандартному набору ASCII символов. А остальные коды уже соответствуют обрабатываемым алгоритмом строкам.