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

GPcH (admin@dotfix.net)

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

Ранее каждый символ кодировался восемью битами. Чтобы получить код символа, необходимо двигаться с низа дерева к его вершине по веткам. Если идешь направо по ветке, пиши «1», если налево — «0». В итоге, двигаясь по веткам, ты рано или поздно наткнешься на один из исходных символов. То, что мы записали, двигаясь по веткам, и есть его код. Как видишь, код символов, встречающихся часто, занимает меньше объема, чем код встречающихся реже. Твоя задача — составить коды для всех символов. Теперь, зная коды, заменяй ими все символы в тексте. Все! Текст заархивирован. Однако обидно, что таблицу кодов символов нужно сохранить вместе с заархивированным текстом. Соответственно, размер увеличится, но ненамного, особенно если сам файл до архивации занимал много места. Вывод так и напрашивается: не стоит применять метод Хаффмана, если размер файла небольшой.

Теперь обратный процесс. У тебя есть дерево и заархивированный текст. Считываешь первый бит. Если он 0, идешь влево. Если 1 — вправо снизу дерева. В итоге, считывая следующие биты, ты рано или поздно наткнешься на какой-нибудь символ — это и есть символ исходного текста. Получил первый символ? Не останавливайся на достигнутом, опускайся вниз дерева и считывай следующий бит. В результате мы получим всю последовательность исходных символов.

Основные недостатки этого метода:

- приходится таскать с собой дерево Хаффмана;

- приходится сканировать текст два раза (первый — при подсчете частот появления символов, второй — при архивации);

- мизерная степень сжатия файлов, содержащих почти все символы;

- возня с Ascii-таблицами, например с exe'шниками, obj'никами и т.д.

Достоинства:

- простота реализации;

- малые объемы занимаемой памяти при архивации.

Примерная реализация алгоритма — на врезке.

Метод Лемпела-Зива

Этот метод использует совершенно иной подход, основанный не на частотности появления байт в тексте, а на повторении слов или части слов в пакуемом тексте. Если слово или его участок текста повторяется, то оно заменяется ссылкой на предыдущее слово, в итоге удается неслабо сжать текстовые данные. Архиватор работает в один проход и составляет лишь словарь, основанный на повторяющихся участках текста. Эффективность сжатия здесь зависит лишь от размеров текстового файла и числа повторений. Бессмысленно сжимать этим алгоритмом маленькие файлы, а тем более отдельные строки, поэтому он вряд ли подойдет для сжатия каждой строчки массива логов аськи. Для 2 Мб лога одним файлом — самое то :). Алгоритмы реализации можно найти также на любом языке. Кое-что ты также найдешь на диске к журналу :). О данном алгоритме, в принципе, слышал не каждый, в отличие от LZW, когда-то он очень популярного. На его основе создавалось множество архиваторов. Как ни странно, современные архиваторы в большинстве своем также применяют этот алгоритм совместно с методом Хаффманом для сжатия текстовых файлов. LZW используется в некоторых форматах графических файлов (например всем известный и широко используемый GIF сжимается именно алгоритмом LZW). Если говорить о происхождении этой аббревиатуры, несложно догадаться, что LZ — производное от имен главных разработчиков (Jakob Ziv и Abraham Lempel). Откуда же буква W? Создатели алгоритма не спешили патентовать его, поэтому им пользовался кто угодно, в том числе разработчики Unix. Один из таких ребят, Терри Велч, вел разработку упаковщика compress. Соответственно, по мере изменения пакера он изменял и LZW-движок, всячески оптимизируя его. Так что Велч навсегда остался в истории и занес свое часть своего имени в аббревиатура алгоритма. Позже, конечно, алгоритм модифицировался и не раз, но так как модификации носили в основном незначительный характер, авторы добавлений не стали расширять аббревиатуру. Вот такая история :).