Сжатие данных с помощью ZIP

В PGP используется пакет сжатия данных, называемый ZIP, авторами которого являются Жан-луп Галли (Jean-loup Gailly), Марк Адлер (Mark Adler) и Ричард Уэлз (Richard Wales). ZIP является свободно распространяемым пакетом, написанным на языке С, выполняемым как утилита на UNIX и в некоторых других системах. ZIP функционально равноценен PKZIP, широко доступному условно бесплатному пакету для систем под управлением Windows, разработанному PKWARE, Inc. Алгоритм ZIP обеспечивает, возможно, наиболее часто используемую технику сжатия данных, позволяя межплатформенный обмен данными: бесплатные и условно бесплатные версии ZIP доступны для Macintosh и других систем так же, как для Windows и UNIX.

Алгоритм ZIP и ему подобные появились в результате исследований Джейкоба Зива (Jacob Ziv) и Абрахама Лемпела (Abraham Lempel). В 1977 году они описали технологию, основанную на использовании буфера скользящего окна, содержащего текст, обработка которого выполнялась последней. Этот алгоритм обычно называют LZ77. Версия именно такого алгоритма используется в схеме сжатия ZIP (PKZIP, gzip, zipit и т.д.).

Алгоритм LZ77 и его варианты основаны на том факте, что слова и фразы внутри потока текста (или структуры изображения в случае GIF), вероятнее всего, повторяются. Когда это имеет место, повторная последовательность может быть заменена коротким кодом. Программа сжатия находит такие повторения и строит коды прямо по ходу выполнения, чтобы заменить повторную последовательность. В дальнейшем коды применяются повторно, чтобы обработать новые последовательности. Алгоритм должен быть определен таким образом, чтобы программа декомпрессии данных могла построить правильное отображение кодов в последовательности исходных данных.

Перед тем как приступить к детальному описанию LZ77, рассмотрим простой пример. Возьмем бессмысленную фразу the brown fox jumped over the brown foxy jumping frog, длина которой равна 53 октетам (байтам), или 424 битам. Алгоритм обрабатывает этот текст слева направо. Сначала каждый символ отображается в 9-битовый двоичный код, складывающийся из двоичной единицы, далее следует 8-битовый ASCII-код символа. В ходе дальнейшего выполнения алгоритм ищет повторяющиеся последовательности. Когда встречается повторение, алгоритм продолжает сканирование до конца повторяющейся последовательности. Другими словами, каждый раз, когда встречается повторение, алгоритм включает в повторяющуюся последовательность столько символов, сколько максимально возможно. Здесь первой найденной последовательностью является the brown fox. Эта последовательность заменяется указателем на предыдущую последовательность и данными о длине последовательности. В данном случае встретившаяся выше последовательность the brown fox находится на 26 символов раньше и длина этой последовательности равна 13 символам. Для данного примера выберем два варианта кодирования: 8-битовый указатель и 4-битовое значение длины или 12-битовый указатель и 6-битовое значение длины; 2-битовый заголовок указывает, какой вариант был выбран: значение 00 обозначает первый вариант, а 01 — второй. Таким образом, второе вхождение последовательности the brown fox кодируется в виде <00_bx26_d><13_d>, или 00 00011010 1101.

Оставшаяся часть сжатого сообщения складывается из буквы у, последовательности <00_b><27_d><5_d>, которая заменяет последовательность из символа пробела и следующих за ним символов jump, а также последовательности символов ing frog.

Соответствующее отображение сжатия представлено на рис. 10.8. Сжатое сообщение состоит из 35 9-битовых символов и двух кодов, в сумме это 35x9 + 2 х 14 = 343 бита. В сравнении с 424 битами несжатого сообщения это дает ко-эффициент сжатия, равный 1,24.