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

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

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

(deil@real.xakep.ru)

Архивируем без компонентов

Убежден на все 99%, что ты уже давно пристрастился к использованию различных архиваторов, таких как WinRAR, bzip2 и другие. А ты никогда не задумывался, как они устроены, как работают, а главное - почему? :) Если тебе это интересно, то ты попал по адресу! Ничего особо сложного я, к сожалению, сейчас поведать не смогу, но основами и классикой архивирования с радостью поделюсь.

Вступление

Как ты понимаешь, сжатие сокращает объем пространства, требуемого для хранения файлов в твоем железном друге, а также количество времени, необходимого для передачи данных по сетям. Это форма кодирования. Кроме сжатия, другими целями кодирования также являются поиск и устранение ошибок, шифрование. Но они, в большинстве случаев, противоположны сжатию - увеличивают избыточность данных, добавляя дополнительную информацию.

О сжатии

Сегодня мы рассмотрим обратимое сжатие (без наличия помех), т.е. сжатие, при котором первоначальный текст может быть в точности восстановлен из сжатого состояния. Наряду с ним существует также и необратимое, ущербное сжатие :), которое используется для цифровой записи аналоговых сигналов, таких как речь, музыка, рисунки.

Одним из самых ранних и хорошо известных методов сжатия является алгоритм Хаффмана. Идея его заключается в том, чтобы подсчитать долю каждого символа в исходном тексте (файле) и сопоставить самому часто встречающемуся символу наиболее короткую запись. То есть не по 1 байту (8 бит) на каждый символ, а, например, по 3-4 бита на самые частые символы, и по 10-16 на самые редкие. Как ни странно, это работает! И даже легко реализуется :). Однако, в конце 70-х годов прошлого века, благодаря двум важным идеям, этот алгоритм был вытеснен. Одна идея заключалась в открытии метода арифметического кодирования, имеющего похожий алгоритм, но и обладающего некоторыми важными свойствами, благодаря которым достигалось значительное превосходство в сжатии. Другим новшеством был метод Зива-Лемпеля, тоже дающий хорошую степень сжатия, но использующий совершенно другой подход. Все эти техники со времен открытия значительно развились и усовершенствовались, и их комбинации легли в основу многих популярных архиваторов, которыми мы все так любим пользоваться.

Чуть ближе к телу

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

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