Сжатие данных: от кода Хаффмана до zstd
Текст «Войны и мира» в UTF-8 занимает около 3,2 МБ. Команда gzip сжимает его до 1,2 МБ — почти втрое. HTML-страница типичного сайта проходит через Brotli и уменьшается в 5–7 раз, прежде чем браузер получит первый байт. Образ Docker, ядро Linux, бэкап базы данных — всё хранится и передаётся в сжатом виде. Сжатие настолько вездесуще, что мы его не замечаем.
Но за ним стоит красивая теория с жёстким ограничением: существует предел, за которй не может перешагнуть ни один алгоритм сжатия данных. Понимание этого предела — ключ к пониманию того, почему одни данные сжимаются в десятки раз, а другие не сжимаются вовсе, и почему gzip, придуманный в 1992 году, до сих пор работает на большинстве серверов планеты.
Простейшая идея: сжимать повторы
Интуиция подсказывает: если в данных есть повторяющиеся фрагменты, их можно записать короче. Самый наивный подход — RLE (Run-Length Encoding), кодирование длин серий: вместо AAAAAABBB написать 6A3B.
// RLE: кодирование длин серий
fn rle_encode(data: &[u8]) -> Vec<u8> {
let mut result = Vec::new();
let mut i = 0;
while i < data.len() {
let ch = data[i];
let mut count = 1u8;
while i + (count as usize) < data.len()
&& data[i + (count as usize)] == ch
&& count < 9
{
count += 1;
}
result.push(b'0' + count);
result.push(ch);
i += count as usize;
}
result
}
Вход: "AAABBBCCDDDDDDEEEF" (18 байт) RLE: "3A3B2C6D3E1F" (12 байт, 67 %)
RLE работает отлично на данных с длинными сериями одинаковых байт, например, на изображениях с большими однотонными областями. Но на обычном тексте он бесполезен: в слове "hello" нет длинных повторов, и RLE только увеличит размер. Нужен другой подход.
Энтропия: сколько информации в ваших данных
В 1948 году Клод Шеннон опубликовал статью «A Mathematical Theory of Communication» и ввёл понятие, которое определило всю дальнейшую теорию сжатия — энтропию:
H = −Σ P(xᵢ) × log₂(P(xᵢ))
Энтропия H — среднее количество бит информации на символ. Что это значит на практике? Посчитаем:
fn shannon_entropy(data: &[u8]) -> f64 {
let mut freq = [0usize; 256];
for &b in data {
freq[b as usize] += 1;
}
let len = data.len() as f64;
let mut h = 0.0;
for &f in &freq {
if f > 0 {
let p = f as f64 / len;
h -= p * p.log2();
}
}
h
}
"aaaaaaaaaa" H = 0.000 бит/символ "aababcabcd" H = 1.846 бит/символ "hello world" H = 2.845 бит/символ "abcdefghij" H = 3.322 бит/символ
Строка из одних a имеет энтропию 0. Зная первый символ, вы знаете все остальные. Строка из десяти различных символов имеет самую большую энтропию для этого алфавита: log₂(10) ≈ 3,32 бита. Каждый символ несёт максимум информации, предсказать следующий невозможно.
Теорема Шеннона о кодировании источника утверждает: никакой алгоритм без потерь не может сжать данные ниже их энтропии. Это фундаментальный предел, как скорость света для передачи сигнала.
Английский текст имеет энтропию около 1–1,5 бит на символ (с учётом частотности пар и троек букв). ASCII использует 8 бит на символ. Разница — 5–7 крат — это и есть теоретический запас для сжатия.
Код Хаффмана: частые символы — короткие коды
В 1952 году студент MIT Дэвид Хаффман получил от профессора Роберта Фано задание на курсовую: придумать способ закодировать набор символов двоичными последовательностями так, чтобы итоговое сообщение занимало как можно меньше бит. Фано сам работал над этим совместно с Шенноном, и их метод (Shannon–Fano coding) давал хорошие, но не оптимальные результаты. Хаффман нашёл решение, строя кодовое дерево снизу вверх — от наименее частых символов к наиболее частым.
Идея: частым символам — короткие коды, редким — длинные. Возьмём строку "abracadabra":
// Частотный анализ "abracadabra"
let text = b"abracadabra";
let mut freq: HashMap<u8, usize> = HashMap::new();
for &b in text.iter() {
*freq.entry(b).or_insert(0) += 1;
}
'a': 5 (45 %) → код: 0 (1 бит) 'b': 2 (18 %) → код: 10 (2 бита) 'r': 2 (18 %) → код: 110 (3 бита) 'c': 1 ( 9 %) → код: 1110 (4 бита) 'd': 1 ( 9 %) → код: 1111 (4 бита)
В ASCII каждый символ занимает 8 бит, и "abracadabra" — это 88 бит. С кодом Хаффмана: 5×1 + 2×2 + 2×3 + 1×4 + 1×4 = 23 бита. Сжатие в 3,8 раза.
Ключевое свойство — префиксность: ни один код не является началом другого. Код 0 (для a) не начинает код 10 (для b) — потому что 0 это полный код, а 10 начинается с 1. Благодаря этому поток бит можно декодировать однозначно, без разделителей: 010011011101111010 → a b r a c a d a b r a.
Код Хаффмана оказался строго оптимальным среди префиксных кодов. Работу засчитали как курсовую с освобождением от финального экзамена.
LZ77: сжимать не символы, а повторы подстрок
Алгоритм Хаффмана работает с частотами отдельных символов. Но в реальных данных избыточность проявляется на уровне целых фрагментов: повторяются слова, конструкции, паттерны. В 1977 году Абрахам Лемпель и Яков Зив предложили принципиально другой подход.
Алгоритм LZ77 поддерживает скользящее окно — буфер уже обработанных данных. Когда в потоке встречается фрагмент, который уже есть в окне, вместо самого фрагмента записывается ссылка: «вернись на N байт назад и скопируй M байт».
Вход: A B C A B C A B C
───────
совпадение с позиции 0, длина 6
Выход: A B C (ссылка: смещение=3, длина=6)
Девять байт превращаются в три литерала и одну ссылку. На длинных текстах с повторяющимися словами и фразами это даёт серьёзное сжатие.
LZ77 не требует предварительного анализа всех данных, он работает потоково, обрабатывая вход слева направо. В 1978 году Лемпель и Зив опубликовали LZ78, использующий явный словарь вместо окна. На основе LZ78 Терри Уэлч создал LZW (1984), ставший основой GIF. LZW был запатентован, что в итоге привело к созданию формата PNG как свободной альтернативы.
DEFLATE: объединяя два подхода
Следующий логичный шаг — совместить оба метода. Именно это сделал Фил Кац, программист из Милуоки, в алгоритме DEFLATE для своего архиватора PKZIP 2.0:
- LZ77 находит повторяющиеся подстроки и заменяет их ссылками.
- Код Хаффмана кодирует получившийся поток — и литералы, и ссылки — присваивая частым элементам короткие коды.
В итоге получается двухступенчатая схема: сначала устраняем повторы на уровне подстрок, потом оптимизируем кодирование оставшегося. Каждый этап ловит свой вид избыточности.
DEFLATE стал основой трёх популярных форматов: gzip (1992) для HTTP и логов, ZIP для архивов, PNG для изображений. Жан-лу Гайи и Марк Адлер реализовали его в библиотеке zlib (1995), которая стала одной из самых распространённых библиотек в истории. Спецификация зафиксирована в RFC 1951 (1996).
Сжатие gzip сегодня выполняется в одну строка кода:
// Go: сжатие gzip из стандартной библиотеки
data := []byte(strings.Repeat("Hello, World! ", 500)) // 7000 байт
var buf bytes.Buffer
w := gzip.NewWriter(&buf)
w.Write(data)
w.Close()
// Результат: 7000 → 63 байт (0.9 %)
// Уровни сжатия: скорость vs степень // BestSpeed (1): 7000 → 65 байт // Default (6): 7000 → 63 байт // BestCompression (9): 7000 → 63 байт
Обратите внимание: разница между уровнями 1 и 9 по размеру — всего 2 байта, а по времени — в разы. Уровень по умолчанию выбран не случайно.
Теоретический потолок: почему универсальный компрессор невозможен
Раз DEFLATE сжимает текст в десятки раз, может, можно сжать ещё? А потом сжать результат? И так до бесконечности?
Нет. И доказательство элементарно.
Строк длины n бит существует ровно 2^n. Строк длины меньше n бит — всего 2^n − 1. По принципу Дирихле невозможно каждой строке длины n сопоставить уникальную строку меньшей длины — «ящиков» не хватает. Любой алгоритм, который сжимает одни строки, обязан увеличивать другие.
В 1960-х годах три учёных независимо пришли к одному и тому же выводу. Рэй Соломонофф (1960), Андрей Колмогоров (1965) и Грегори Хейтин (1969) определили алгоритмическую сложность строки как длину кратчайшей программы, которая её порождает. Из этого определения следует: большинство строк несжимаемы. Случайная строка с высокой вероятностью не содержит закономерностей, которые можно было бы использовать, и это, собственно, формальное определение случайности.
Хейтин описал результат так: «Берём теорию информации Шеннона и теорию вычислимости Тьюринга, помещаем в шейкер для коктейлей и энергично перемешиваем».
На практике это значит: хорошо сжимается то, что содержит закономерности (текст, код, логи, изображения с плавными градиентами). Случайные данные — шифрованные файлы, хорошо сжатые архивы, белый шум — не сжимаются вообще. Попытка сжать уже сжатый файл обычно увеличивает его размер (из-за метаданных формата).
ZIP-бомбы: сжатие как оружие
Ограничение DEFLATE — максимальная степень сжатия не более 1032:1. Но формат ZIP позволяет вкладывать архивы в архивы. Классическая ZIP-бомба 42.zip использует именно это: файл размером 42 КБ содержит пять уровней вложенных ZIP-архивов, по 16 файлов на каждом уровне. На нижнем уровне каждый файл распаковывается до 4,3 ГБ. Итого после полной распаковки — ~4,5 петабайт. Цель — вывести из строя антивирус или любую программу, которая рекурсивно распаковывает архивы.
Защита казалась простой: ограничить глубину рекурсивной распаковки. Но в 2019 году Дэвид Фифилд представил на конференции USENIX WOOT нерекурсивную ZIP-бомбу. Его метод использует особенность формата ZIP: несколько файловых записей в центральном каталоге могут ссылаться на один и тот же блок сжатых данных. Результат — квадратичный рост размера при распаковке за один проход, без вложенности.
42 КБ → 5,5 ГБ (степень 129 000:1) 10 МБ → 281 ТБ (степень 28 000 000:1) 46 МБ → 4,5 ПБ (с расширениями Zip64)
Всё это — стандартный DEFLATE, один уровень вложенности, никакой рекурсии. Знание того, как работает сжатие, позволяет и защищаться, и атаковать.
От gzip к zstd: смена поколений
gzip, созданный Гайи и Адлером в 1992 году, продержался стандартом HTTP-сжатия и сжатия логов тридцать лет. Он прост, надёжен и поддерживается буквально везде. Но за это время процессоры изменились неузнаваемо, а алгоритм — нет. Появились замены.
Zstandard (Янн Колле, 2016)
Янн Колле, инженер Meta, создал zstd — алгоритм на основе словарного сжатия и конечных автоматов (FSE — Finite State Entropy), оптимизированный под параллельное исполнение на современных CPU. При том же уровне сжатия zstd в 3–5 раз быстрее gzip. При той же скорости сжимает лучше.
- Linux kernel 4.14 (2017) — сжатие модулей;
- Arch Linux (2020) — переход с xz на zstd для пакетов;
- AWS S3 — внутреннее сжатие (~30 % экономия на экзабайтах данных);
- Chrome 123 и Firefox 126 (2024) —
Content-Encoding: zstd; - ; Windows 11 (октябрь 2023) — поддержка в Проводнике.
Колле также создал и алгоритм LZ4, оптимизированный под скорость декомпрессии: более 4 ГБ/с на одном ядре. LZ4 используется в ядре Linux, ZFS, десятках баз данных. Он же создал и xxHash. Забавный факт: LZ4 начинался как побочный проект, когда Колле работал в маркетинговом отделе телеком-компании Orange.
Brotli (Google, 2015)
Жирки Алакуйала и Золтан Сабадка из Google создали Brotli изначально для сжатия веб-шрифтов (WOFF2), а затем обобщили для HTTP. Ключевая идея — предопределённый словарь из часто встречающихся фрагментов HTML, CSS и JavaScript. Для статических ресурсов Brotli даёт лучшую степень сжатия, чем gzip и zstd, но медленнее на высоких уровнях компрессии.
По данным HTTP Archive (январь 2024): Brotli и gzip используются примерно поровну (~40 % каждый), zstd растёт (~2 %), около 11 % ответов не сжаты.
Сжатие в Go, Rust и Zig
Go: всё в стандартной библиотеке
Go включает compress/gzip, compress/zlib, compress/flate (DEFLATE), compress/lzw и compress/bzip2 (только декомпрессия). Для продакшена часто используют klauspost/compress, совместимый по API, но в 2–5 раз быстрее. Этот же пакет содержит чистую реализацию zstd на Go.
import "compress/gzip" // Сжатие var buf bytes.Buffer w := gzip.NewWriter(&buf) w.Write(data) w.Close() // Распаковка r, _ := gzip.NewReader(&buf) io.Copy(os.Stdout, r)
Rust: экосистема крейтов
Крейт flate2 — обёртка над DEFLATE с четырьмя бэкендами: miniz_oxide (чистый Rust, по умолчанию), zlib-rs (чистый Rust, самый быстрый), zlib-ng (C через FFI) и cloudflare_zlib.
Отдельного упоминания заслуживает zlib-rs — проект, финансируемый ISRG (создатели Let’s Encrypt). В феврале 2025 года он обогнал zlib-ng: декомпрессия на 6–10 % быстрее, компрессия на 6 % быстрее на уровне по умолчанию. Чистый Rust, без unsafe в горячих путях, с автоматическим обнаружением SIMD.
Zig: минимализм
В Zig 0.12 стандартная библиотека содержала std.compress с поддержкой deflate, gzip, zlib, xz и zstd. В Zig 0.15 компрессия была удалена (декомпрессия осталась) как часть масштабного пересмотра системы ввода-вывода. Сообщество создало библиотеку comprezz, извлечённую из стандартной библиотеки 0.14 и адаптированную под новые интерфейсы.
Полные примеры: compress_demo.rs, compress_demo.go, compress_demo.zig.
Что выбрать на практике
При выборе алгоритма сжатия ключевой вопрос — где узкое место. Если вы отдаёте статические ресурсы по HTTP (JavaScript-бандлы, CSS, шрифты), имеет смысл сжать их один раз Brotli на максимальном уровне и закешировать результат. Время компрессии здесь не критично — файл сжимается при деплое, а отдаётся тысячам клиентов.
Для динамических ответов, которые генерируются на лету, расклад другой. Здесь важна скорость сжатия, и zstd на уровне 3–5 даёт лучший баланс: сжимает не хуже gzip-9, но в разы быстрее. gzip при этом остаётся разумным fallback — его понимают все клиенты, включая древние.
Для архивов и бэкапов zstd заменяет gzip практически во всех сценариях. Если же критична скорость распаковки (игровые ресурсы, которые нужно загрузить за кадр, swap-раздел, горячий кеш), стоит посмотреть на LZ4 — он жертвует степенью сжатия, но декомпрессирует со скоростью более 4 ГБ/с.
Отдельная ловушка — уровни сжатия. Между уровнями 1 и 6 разница в размере ощутима. Между 6 и 9 почти незаметна, а разница по времени — в разы. Уровень по умолчанию в большинстве реализаций выбран не случайно. Он уже находится в точке, где дальнейшее повышение уровня почти не уменьшает размер, но заметно замедляет процесс.
И, наконец, не пытайтесь сжимать уже сжатое. JPEG, MP4, зашифрованные файлы, архивы внутри архивов — всё это данные с высокой энтропией, в которых закономерностей для компрессора не осталось. Попытка дожать их только добавит метаданные формата и увеличит размер.
Заключение
Сжатие данных — область, где теория и практика связаны напрямую. Шеннон определил предел в 1948 году. Хаффман приблизился к нему в 1952-м. Лемпель и Зив добавили словарный подход в 1977-м. DEFLATE объединил оба метода в 1990-х и держится стандартом до сих пор.
Zstd — первая замена, набравшая критическую массу: от ядра Linux до браузеров и облачных хранилищ. Но фундаментальный результат Колмогорова остаётся: универсального компрессора не существует. Каждый алгоритм — компромисс между степенью сжатия, скоростью и объёмом памяти. Выбирайте тот, который соответствует вашей задаче.
Источники
- A Mathematical Theory of Communication (Shannon, 1948) — статья Шеннона
- A Method for the Construction of Minimum-Redundancy Codes (Huffman, 1952) — код Хаффмана
- A Universal Algorithm for Sequential Data Compression (Ziv & Lempel, 1977) — LZ77
- RFC 1951: DEFLATE Compressed Data Format Specification — спецификация DEFLATE
- A better zip bomb (David Fifield, 2019) — нерекурсивная ZIP-бомба
- Zstandard (GitHub) — исходный код zstd
- zlib-rs is faster than C (2025) — результаты zlib-rs
- Kolmogorov Complexity (Wikipedia) — алгоритмическая сложность
- Choosing Between gzip, Brotli and zStandard (Paul Calvano, 2024) — сравнение алгоритмов для веба