Сжатие без потерь

Как объём уменьшается, а данные остаются те же

Работает сжатие не с «лишними байтами», а с избыточностью — предсказуемостью данных. В русском тексте буква «о» встречается примерно в сто раз чаще, чем «ф»; в скане накладной подряд идут тысячи одинаковых белых пикселей; в логе сервера строка «HTTP/1.1 200» повторяется в каждой второй записи. Алгоритм описывает частое короткими кодами, редкое — длинными, а повторы заменяет ссылкой на предыдущее вхождение. Ни один бит смысла при этом не выбрасывается, поэтому распаковка возвращает исходный файл байт в байт — это и отличает подход от сжатия с потерями, где часть информации удаляется навсегда.

Три механизма закрывают почти всю практику. RLE (run-length encoding) заменяет серию одинаковых значений парой «значение + счётчик»: 400 белых пикселей превращаются в четыре байта. Код Хаффмана (1952) строит дерево, где самый частый символ получает 1–2 бита вместо восьми. Словарные методы LZ77 и LZ78 (1977 и 1978 годы, Абрахам Лемпель и Яаков Зив) держат окно уже просмотренных данных и вместо повторного фрагмента пишут тройку «отступ назад, длина, следующий символ».

Промышленный стандарт DEFLATE (RFC 1951) соединяет LZ77 и Хаффмана: окно поиска 32 КБ, длина совпадения от 3 до 258 байт, поверх — энтропийное кодирование получившихся литералов и ссылок. Именно DEFLATE лежит внутри ZIP, gzip и PNG, поэтому один и тот же движок сжимает и архив, и картинку.

Предел задаёт энтропия Шеннона: если источник выдаёт восемь равновероятных символов, меньше трёх бит на символ не выйдет никаким алгоритмом. Отсюда следствие, которое регулярно обнаруживают заново: архив, сжатый второй раз, обычно становится чуть больше — избыточность уже выбрана, а служебные заголовки добавляются. И более общее правило от принципа Дирихле: программы, сжимающей любой вход, не существует — если какие-то файлы уменьшаются, другие обязаны расти.

Рабочий набор форматов и алгоритмов

Выбор идёт по треугольнику «плотность — скорость упаковки — скорость распаковки», и разные задачи выбирают разные углы.

• DEFLATE (ZIP, gzip, zlib) — универсальный компромисс с 1990-х. Понимается всем и везде, распаковка десятки-сотни МБ/с, плотность средняя.
• bzip2 — преобразование Барроуза-Уилера плюс Хаффман. Плотнее gzip на текстах, но заметно медленнее, сейчас вытесняется.
• LZMA / LZMA2 (7z, xz) — большое окно (до сотен мегабайт) и контекстное арифметическое кодирование. Отличная плотность на дистрибутивах и дампах, дорогая упаковка.
• Brotli (RFC 7932) — придуман для веба, несёт встроенный словарь из типовых фрагментов HTML, CSS и JS. На уровне 11 обычно ощутимо плотнее gzip на текстовых ответах, поэтому используется в HTTP-заголовке Content-Encoding.
• Zstandard (RFC 8478) — конечные автоматы вместо классической арифметики; на низких уровнях распаковывается сотнями мегабайт в секунду, поддерживает обучаемые словари для потока мелких однотипных сообщений.

Отдельная ветка — предметно-ориентированные схемы. PNG перед DEFLATE прогоняет строки через фильтры (Sub, Up, Average, Paeth), превращая градиент в почти нулевые разности. FLAC и ALAC предсказывают следующий отсчёт звука по предыдущим и кодируют только ошибку предсказания, ужимая WAV примерно вдвое без единого изменённого сэмпла. Форматы вроде GIF и TIFF LZW работают по словарной схеме. Конкретные реализации для звука и видео разобраны в термине кодек.

Что это значит для QR- и штрих-кодов

Первое правило: картинку кода экспортируют в форматы без потерь. PNG, SVG, PDF, EPS сохраняют чёрный модуль чёрным, а границу — резкой. JPEG вокруг каждого перепада яркости оставляет ореол, и на мелком коде сканер начинает ошибаться. По той же причине для печати предпочтителен векторный QR-код: у него вообще нет пикселей, масштабирование не портит края.

Второе: внутри самого QR-кода сжатия нет. Спецификация ISO/IEC 18004 не предусматривает архивации полезной нагрузки, есть только режимы кодирования, которые упаковывают символы плотнее восьми бит. Цифровой режим тратит 10 бит на три цифры (около 3,33 бита на символ), алфавитно-цифровой — 11 бит на два символа (5,5 бита), байтовый — честные 8 бит на байт. Отсюда практический вывод: 7089 цифр против 2953 байт произвольного текста при максимальной версии 40 и уровне коррекции L. Подробности о ёмкости QR-кода объясняют, почему длинный URL сразу поднимает версию символа и делает модули мельче.

Третье: роль архиватора для кода выполняет короткая ссылка. Заменив адрес на 180 символов ссылкой на 25, вы уменьшаете символ на несколько версий, а сканирование с расстояния становится устойчивее. Сгенерировать такой код можно в генераторе QR-кодов, где длина payload видна сразу.

И четвёртое, о чём часто путаются: контрольная сумма и хеш к сжатию отношения не имеют. CRC-32 или SHA-256 сокращают файл до фиксированных 4 или 32 байт, но восстановить из них исходные данные невозможно — это односторонняя свёртка для проверки целостности. Не является сжатием и коррекция ошибок по Риду-Соломону: она, наоборот, добавляет избыточные кодовые слова, чтобы код читался с повреждённой поверхности. Теоретический предел, ниже которого без потерь ужать не получится, задаёт энтропия информации.

Частые вопросы

Насколько сильно сжимаются обычные файлы?

Диапазон широкий и зависит от типа данных. Текст, HTML, CSV и логи обычно уменьшаются в 3–10 раз: в них много повторов. Исполняемые файлы и базы — примерно вдвое. Уже сжатые данные (JPEG, MP3, MP4, ZIP внутри ZIP) практически не поддаются: выигрыш редко превышает несколько процентов, потому что избыточность из них уже выбрана.

Почему архив, сжатый повторно, стал больше?

После первого прохода данные близки к случайным: частоты символов выровнены, повторов нет. Второй проход не находит избыточности, но всё равно дописывает заголовок формата, таблицы и контрольные суммы. Отсюда прирост в несколько сотен байт. Правило простое: сжимать имеет смысл один раз, дальше меняют алгоритм, а не количество проходов.

Можно ли сжать данные, которые кладут в QR-код?

Технически можно упаковать текст архиватором и записать результат в байтовом режиме, но читать такой код будет только ваше приложение: обычная камера покажет бессмысленный набор символов. Для публичных кодов работает другой приём — сократить саму полезную нагрузку: короткая ссылка, отказ от лишних UTM-хвостов, цифровые данные вместо смешанных.

В каком формате сохранять готовый код для типографии?

Вектор — SVG, PDF или EPS, растр — PNG с разрешением от 300 dpi для печати. JPEG для кодов не годится: его артефакты размывают границы модулей и добавляют ореолы, из-за чего мелкий код на упаковке читается хуже. Если макет уже пришёл в JPEG, лучше сгенерировать код заново, а не пересохранять испорченный файл.

Чем сжатие отличается от кодирования и шифрования?

Сжатие убирает избыточность и уменьшает объём, кодирование меняет форму представления без цели уменьшить размер (Base64, наоборот, растит объём на треть), шифрование делает данные нечитаемыми без ключа. Порядок операций важен: сжимают до шифрования, потому что шифротекст статистически неотличим от случайного и уже не сжимается.