Сжатие: поиск повторов и потеря части данных

КАК УСТРОЕНО ВСЁ - приложение C

Сжатие данных: почему файлы можно уменьшить - и до какого предела

Как ZIP находит повторы, почему JPEG выбрасывает часть картинки и отчего уже сжатый файл не сжимается повторно

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

🔁 Главная идея: избыточность

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

Возьмём простой пример. Представьте, что нужно записать строку: «аааааааааа» - десять букв «а» подряд. Можно записать все десять. А можно записать: «10 раз а» - и это займёт меньше места, неся ровно ту же информацию. Именно на этом принципе построено всё сжатие без потерь.

📦 Сжатие без потерь: данные восстанавливаются точно

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

Кодирование повторов

Самый простой алгоритм - RLE (Run-Length Encoding - кодирование длин серий). Вместо того чтобы хранить «белый, белый, белый, белый, белый, белый», он хранит «6 белых». Хорошо работает для изображений с большими однотонными областями - например, для скриншотов с белым фоном или простой графики. Плохо работает для фотографий, где почти нет одинаковых соседних пикселей.

Словарное сжатие

Алгоритмы семейства LZ (по именам авторов - Лемпел и Зив, 1977 год) работают хитрее. Они строят словарь из уже встреченных последовательностей байт и заменяют повторные вхождения ссылками на словарь. Встретили слово «компьютер» - добавили в словарь. Встретили снова - записали не само слово, а короткую ссылку: «то же, что запись номер 47». Чем длиннее файл и чем больше в нём повторов - тем лучше сжатие.

На этом принципе построены ZIP, gzip, форматы PNG и многие другие. Текстовый файл сжимается в несколько раз - в нём много повторяющихся слов. Исходный код программы - тоже хорошо: ключевые слова языка встречаются постоянно. Уже сжатый файл - почти не сжимается: словарь не находит повторов там, где их нет.

Коды Хаффмана: частые символы - короче

Ещё один классический приём - кодирование Хаффмана. Идея: зачем тратить одинаковое количество битов на все символы, если одни встречаются гораздо чаще других? В русском тексте буква «о» встречается намного чаще, чем «ъ». Если «о» закодировать двумя битами, а «ъ» - двенадцатью - суммарно файл станет меньше, хотя каждый символ кодируется по-разному.

Это та же логика, что и в азбуке Морзе: точка - самый короткий сигнал, буква «е» - самая частая в английском. Хаффман формализовал этот принцип математически и доказал, что его метод даёт оптимальный результат для данного распределения символов. Коды Хаффмана используются внутри ZIP, JPEG, MP3 и многих других форматов.

📌 Предел сжатия без потерь: Математик Клод Шеннон в 1948 году доказал, что у любого файла есть нижний предел сжатия - энтропия. Это количество «настоящей» информации в файле, которую нельзя выразить короче без потерь. Если файл уже сжат до энтропии - дальше некуда. Именно поэтому повторное сжатие ZIP-архива почти не даёт результата: первое сжатие уже убрало всю избыточность.

🎨 Сжатие с потерями: выбрасываем то, чего не заметят

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

JPEG: фотографии

JPEG разбивает изображение на блоки 8×8 пикселей и применяет к каждому математическое преобразование - дискретное косинусное преобразование (ДКП). Оно раскладывает блок на набор волн разных частот: грубые контуры - это низкие частоты, мелкие детали - высокие. Затем JPEG выбрасывает высокочастотные компоненты - те самые мелкие детали, которые глаз плохо различает. Чем сильнее «качество» снижено - тем больше выброшено, тем меньше файл и тем заметнее артефакты.

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

MP3 и AAC: звук

Алгоритмы сжатия звука эксплуатируют особенности человеческого слуха. Ухо плохо слышит тихий звук, если рядом играет громкий - это явление называется маскировкой. MP3 анализирует звуковой сигнал, определяет, какие частоты маскируются другими, и кодирует их с меньшей точностью или не кодирует вовсе. Частоты выше 16-18 кГц большинство взрослых людей и вовсе не слышат - их тоже можно выбросить. В результате файл уменьшается в 10 раз при почти неразличимой разнице в звучании.

Видео: межкадровое сжатие

Видео сжимается особенно эффективно, потому что между соседними кадрами обычно очень мало различий. Если камера снимает человека на фоне стены - стена почти не меняется от кадра к кадру. Видеокодеки вроде H.264 и H.265 хранят не каждый кадр целиком, а только разницу между кадрами. Полный кадр сохраняется раз в несколько секунд - он называется ключевым кадром, или I-фреймом. Остальные кадры хранят только то, что изменилось: «объект сдвинулся на 12 пикселей вправо», «этот блок теперь темнее на 5%». Это и есть причина, по которой сцены с резкими монтажными склейками или быстрым движением «бьются» при низком битрейте - там много различий между кадрами, и кодек не успевает.

Формат	Тип сжатия	Для чего	Степень сжатия
ZIP, gzip	Без потерь (LZ + Хаффман)	Любые файлы, архивы	2-10× для текста, почти 1× для уже сжатых
PNG	Без потерь	Изображения с текстом, скриншоты, графика	2-5× для простой графики
JPEG	С потерями (ДКП)	Фотографии	10-20× при хорошем качестве
MP3, AAC	С потерями (психоакустика)	Музыка, подкасты	~10× по сравнению с WAV
H.264, H.265	С потерями (межкадровое)	Видео	100-1000× по сравнению с несжатым
FLAC	Без потерь	Музыка в максимальном качестве	~2× по сравнению с WAV

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

🔗 Сжатие и всё, что мы уже знаем

Сжатие пронизывает весь стек, который мы разбирали в цикле. Файловая система хранит сжатые файлы на диске. Браузер получает сжатые HTML и CSS по сети - сервер сжимает их gzip или Brotli перед отправкой, браузер распаковывает на лету. Видеокарта декодирует сжатые видеопотоки с YouTube - именно для этого в GPU есть специальный аппаратный декодер, чтобы не нагружать основной процессор. Фотографии в мессенджере пересжимаются на сервере перед доставкой - отсюда потеря качества при пересылке.

Каждый раз, когда данные куда-то передаются или где-то хранятся, вопрос сжатия незримо присутствует: что можно выбросить без потерь, что - с потерями, и до какого предела. Ответ всегда один и тот же - до предела энтропии.

ANY.BY

Нужна помощь с техникой? Привозите - диагностика при заказе ремонта бесплатна. Контакты и запись.

Сжать строку двумя способами и увидеть, где выигрыша нет Интерактив: серии символов, словарь повторов и случайный набор, который не сжимается ни тем, ни другим. Открыть демо →

Приложение C. Сжатие данных: почему файлы можно уменьшить