Как ZIP сжимает файлы и ничего не теряет

Архиватор обещает невозможное: сделать файл меньше и при этом вернуть его без единой потерянной буквы — как у него получается?

Сжатие без потерь — это не магия и не выбрасывание лишнего. Это поиск повторов и более экономная запись того, что уже есть.

Откройте любой текстовый файл, заархивируйте его в ZIP — и он похудеет в два-три раза. Распакуйте — получите ровно тот же текст, символ в символ. Никакой потери качества, в отличие от JPEG или MP3. Этот тип сжатия называют сжатием без потерь, и держится он на двух идеях, которые работают в паре.

Идея первая: не повторяйся

Представьте фразу «мама мыла раму, мама мыла окно». Слово «мама мыла» встречается дважды. Зачем хранить его второй раз целиком? Можно записать так: «мама мыла раму, вернись на 16 символов назад и возьми 9 окно». Вместо девяти букв — короткая ссылка «назад столько-то, длиной столько-то».

Именно это делает алгоритм LZ77 (по фамилиям Лемпеля и Зива, 1977 год). Он движется по файлу и держит в памяти «окно» из недавно прочитанного текста — словарь. Встретив кусок, который уже был, он заменяет его на пару чисел: (смещение, длина). Чем больше повторов, тем сильнее сжатие. Поэтому текст и код жмутся отлично, а уже сжатый JPEG — почти никак: в нём повторов почти не осталось.

Идея вторая: частым — короткие коды

В обычном файле каждый символ занимает 8 бит, независимо от того, буква это «о» (которая встречается на каждом шагу) или «ъ» (раз в сто страниц). Это расточительно. Логичнее было бы давать частым символам короткий код, а редким — длинный. Ровно так устроена азбука Морзе: у частой буквы «E» один короткий сигнал, у редкой «Q» — четыре длинных.

Этим занимаются коды Хаффмана. Алгоритм считает, как часто встречается каждый символ, и строит дерево, в котором путь до частого символа короткий, а до редкого — длинный. Получается набор кодов разной длины, и — что важно — ни один код не является началом другого, поэтому поток битов читается однозначно, без разделителей.

Deflate: две идеи вместе

Формат ZIP использует алгоритм Deflate — это и есть связка LZ77 и Хаффмана. Сначала LZ77 вычищает повторы, превращая текст в смесь обычных символов и ссылок «назад». Потом Хаффман перекодирует всё это, давая частым элементам короткие коды. Двойной удар: повторы убраны, а то, что осталось, записано максимально экономно.

import zlib

text = ("мама мыла раму " * 50).encode("utf-8")
szhato = zlib.compress(text, level=9)
print("Было байт:", len(text))
print("Стало байт:", len(szhato))
print("Во сколько раз меньше:", round(len(text) / len(szhato), 1))

Почему нельзя сжать всё подряд

Возникает соблазн: а давайте сожмём архив ещё раз, и ещё — пока не останется один байт? Не выйдет. Существует строгое математическое ограничение: нельзя обратимо сжать все возможные файлы одновременно. Если бы любой файл становился короче, то двум разным файлам в какой-то момент пришлось бы дать одинаковый сжатый код — и распаковать их однозначно стало бы невозможно. Сжатие выигрывает только на данных с закономерностями: повторами, перекосами частот, структурой. Чистый случайный шум не сжимается вообще — ему нечем платить за экономию.

Поэтому ZIP — это не волшебство, а честная сделка: он находит порядок там, где он есть, и записывает его короче. Там, где порядка нет, он честно разводит руками.