Как устроен алгоритм сжатия ZIP: от LZ77 до дефлейта

Из чего состоит архив ZIP

ZIP — это формат-контейнер: он хранит один или несколько файлов вместе с их именами, датами и другими метаданными, а для каждого файла отдельно записывает, каким способом тот упакован. Файл внутри архива может лежать вообще без сжатия — такой режим называют store, он просто складывает байты подряд. Но на практике почти всегда используют метод deflate — он даёт заметный выигрыш в размере почти на любых данных, кроме уже сжатых. Сам формат предложил в конце 1980-х годов программист Фил Катц, и с тех пор ZIP стал одним из самых узнаваемых форматов архивов вообще.

Первый шаг — поиск повторов алгоритмом LZ77

LZ77 читает данные слева направо и держит в памяти скользящее окно — недавно обработанный кусок данных, который ещё помнится алгоритму. Для каждого нового места в потоке LZ77 пытается найти внутри этого окна самую длинную последовательность байтов, которая совпадает с тем, что идёт дальше по тексту. Если совпадение нашлось, алгоритм записывает вместо повторяющихся байтов короткую пару чисел — расстояние назад до начала совпадения и длину самого совпадения. Если ничего похожего в окне не нашлось, байт записывается как есть, без ссылки, — его называют литералом. Чем больше в данных повторов, тем больше байтов удаётся заменить компактными ссылками вместо литералов.

Пример работы LZ77 на простом тексте

Возьмём строку «мама мыла раму, а рама мыла маму» — в ней явно повторяются целые слова и их части. Дойдя до второго слова «мыла», алгоритм заглядывает в окно назад и обнаруживает точно такую же последовательность букв чуть раньше. Вместо того чтобы записывать «мыла» заново, буква за буквой, LZ77 сохраняет пару чисел — расстояние назад до первого «мыла» и длину совпадения в пять символов вместе с пробелом. То же самое происходит с «раму» и «рама»: буквы «рам» совпадают, и алгоритм экономит на них, записывая только разницу — последнюю букву «у» или «а» — отдельным литералом. Чем длиннее текст и чем чаще в нём встречаются одни и те же слова, тем заметнее становится экономия от такой замены.

Второй шаг — код Хаффмана

После работы LZ77 поток данных всё ещё состоит из байтов и ссылок, каждый из которых занимает целое число бит фиксированной длины. Код Хаффмана меняет этот принцип: он считает, как часто в потоке встречается каждое значение, и раздаёт самым частым значениям самые короткие битовые коды, а редким — более длинные. Буква, которая в тексте попадается на каждом шагу, может получить код всего из двух-трёх бит вместо привычных восьми, а редкий символ — код длиннее обычного байта. В сумме, если распределение частот заметно неравномерно, такая замена ощутимо сокращает общий объём данных.

Коды Хаффмана строят так, что ни один короткий код не является началом другого, более длинного, — это свойство называют префиксным кодом. Благодаря ему декодер читает битовый поток подряд и всегда точно знает, где заканчивается один код и начинается следующий, не запрашивая никаких дополнительных разделителей между символами.

Как deflate соединяет оба приёма

Deflate не выбирает между LZ77 и кодом Хаффмана — использует оба последовательно, один за другим. Сначала LZ77 превращает исходные данные в поток литералов и ссылок на повторы. Затем этот получившийся поток сам становится входом для кода Хаффмана, который сжимает уже его — отдельно кодирует литералы и длины совпадений, отдельно расстояния до начала повтора. По стандарту формата deflate окно поиска для LZ77 ограничено тридцатью двумя килобайтами, а длина одного найденного совпадения — числом от трёх до двухсот пятидесяти восьми байт. Совпадения короче этого предела кодировать ссылкой невыгодно. Совпадения длиннее верхней границы приходится разбивать на несколько ссылок подряд.

• LZ77 убирает повторы внутри данных и заменяет их короткими ссылками
• код Хаффмана убирает неравномерность частот и даёт частым значениям более короткие коды
• оба приёма работают на разных уровнях, поэтому вместе сжимают заметно сильнее, чем каждый по отдельности
• результат обоих шагов упаковывается в единый битовый поток внутри файла архива

Почему уже сжатые файлы почти не сжимаются

Фотографии в формате JPEG, музыка в формате MP3 и видео в сжатых форматах уже прошли через собственные алгоритмы, которые вычистили из них повторы и неравномерность заранее, ещё до попадания в архив. Байты внутри такого файла выглядят почти как случайный набор — с точки зрения LZ77 в них почти нет длинных повторов, которые стоило бы заменить ссылкой, а с точки зрения кода Хаффмана частоты разных байтовых значений распределены почти равномерно, и сокращать код не для чего. Попытка заново сжать такой файл через ZIP обычно почти ничего не даёт. Из-за служебных данных самого архива итоговый размер иногда оказывается даже чуть больше исходного.

Текстовые файлы, программный код, таблицы и логи устроены прямо противоположно. В них постоянно повторяются одни и те же слова, отступы, знаки препинания и структурные элементы, а частоты букв заметно неравномерны — некоторые буквы встречаются в разы чаще других. Такие данные архиватор сжимает сильно именно потому, что LZ77 и код Хаффмана находят в них ровно то, для чего были придуманы.

Степень сжатия и что на неё влияет

Степень сжатия обычно считают как отношение исходного размера файла к размеру после архивации — во сколько раз файл стал легче. Иногда её выражают наоборот, в процентах экономии места. На конкретное значение влияет прежде всего внутренняя избыточность данных: чем больше в файле повторов и чем более предсказуема его структура, тем сильнее сожмут его LZ77 и код Хаффмана вместе. Текст на естественном языке, исходный код программ и табличные данные обычно сжимаются в несколько раз. Уже сжатые изображения, аудио и видео дают экономию, близкую к нулю, а иногда — символическую долю процента.