Внутренности алгоритмов компрессии: LZ77, Huffman, ANS
В Модуле 01 мы сравнили четыре алгоритма компрессии — Snappy, LZ4, Zstd, GZIP — по скорости и степени сжатия. Мы узнали какой выбрать, но не почему они так отличаются.
Этот урок — внутрь алгоритмов. Мы разберём три фундаментальных техники, из которых строятся все четыре алгоритма: LZ77 (поиск повторов), Huffman coding (частотные коды), и ANS (инновация Zstd). Понимание внутренностей объясняет, почему Zstd настраивается на 22 уровнях, а Snappy — нет, и почему LZ4 быстрее Snappy при похожем подходе.
LZ77: скользящее окно и поиск повторов
LZ77 (Lempel–Ziv, 1977) — фундаментальная идея, которую используют все четыре алгоритма. Принцип: если последовательность байтов уже встречалась раньше в потоке — вместо повторной записи укажи ссылку (offset + length) на предыдущее вхождение.
Вход: A B C D A B C X A B C D A B C Y
Входная строка для компрессии. LZ77 обрабатывает слева направо, поддерживая скользящее окно уже обработанных данных.Итог: [A][B][C][D] + (4,3) + [X] + (8,7) + [Y] = ~12 байт вместо 16
Итог: 16 символов (16 байт) → 4 литерала + 2 ссылки + 1 литерал + 1 ссылка = ~12 байт. Экономия ~25%. На реальных данных с длинными повторами экономия значительно больше.Три параметра определяют эффективность LZ77:
- Размер окна — сколько байт назад алгоритм ищет совпадения. Больше окно → больше шанс найти длинный match → лучше сжатие. Но: больше памяти и CPU на поиск.
- Минимальная длина match — обычно 3–4 байта. Ссылка (offset + length) сама занимает 2–3 байта — если совпадение короче, ссылка дороже литералов.
- Алгоритм поиска — как быстро находить совпадения в окне. Наивный O(n×w) — слишком медленно. Hash table — O(1) lookup.
Все четыре алгоритма (Snappy, LZ4, Zstd, GZIP) используют LZ77 как первую фазу. Разница — в размере окна, алгоритме поиска, и в том, что происходит после: Snappy и LZ4 на этом останавливаются, а Zstd и GZIP добавляют вторую фазу — энтропийное кодирование.
Huffman Coding: частотные коды
Huffman coding (1952) — вторая фундаментальная техника. Идея: символы с высокой частотой кодируются короткими битовыми последовательностями, редкие — длинными. Условие: никакой код не является префиксом другого (prefix-free code).
Частоты: A=45 B=25 C=15 D=10 E=5 (100 символов)
Входные данные: строка из 100 символов. Частоты: A — 45 раз, B — 25, C — 15, D — 10, E — 5. Фиксированный код (3 бит/символ) = 300 бит. Хаффман может лучше.Итого: 200 бит вместо 300 (фиксированный 3 бита/символ). Экономия 33%
A: 45×1 = 45 бит. B: 25×2 = 50. C: 15×3 = 45. D: 10×4 = 40. E: 5×4 = 20. Итого: 200 бит vs 300 при фиксированном коде. Экономия 33%.Huffman в GZIP и DEFLATE
GZIP использует DEFLATE — комбинацию LZ77 + Huffman. Сначала LZ77 находит повторы и генерирует поток символов (литералы + ссылки offset/length). Затем Huffman кодирует этот поток:
Raw данные
Сырые данные. Могут быть любого типа — после column encoding это уже сжатые байты.LZ77 (окно 32 KB)
Фаза 1: LZ77. Скользящее окно 32 KB. Находит повторяющиеся последовательности, заменяет на (offset, length) ссылки. Выход: смесь литералов и ссылок.Huffman coding
Фаза 2: Huffman coding. Подсчитать частоты литералов и length-символов в выходе LZ77. Построить дерево Хаффмана. Закодировать каждый символ переменным числом бит.Сжатый поток + Huffman table
Сжатый выход: Huffman-таблица (описание дерева) + закодированный поток бит. Декодер читает таблицу, восстанавливает дерево, декодирует поток побитово.Huffman — оптимальный prefix code: каждый символ кодируется целым числом бит. Символ с вероятностью 0.33 получает 2 бита (оптимально: log₂(3) ≈ 1.58 бит). Потеря: до 1 бита на символ. Для алфавита из 256 символов это мало, но для потока из 3–4 уникальных значений (типично после LZ77) — заметная неэффективность.
ANS: инновация Zstd
ANS (Asymmetric Numeral Systems, Jarek Duda, 2007–2014) — инновация, которая сделала Zstd возможным. Ключевое преимущество: ANS кодирует символы дробным числом бит, устраняя потерю “целых бит” Хаффмана.
Как ANS достигает дробных бит
Ключевая идея ANS: вместо кодирования каждого символа отдельно, ANS кумулятивно кодирует поток символов в одно большое число (state). Каждый новый символ трансформирует state по формуле, которая добавляет ровно -log₂(P) бит информации:
state = начальное значение
Начальное состояние: state = 0 (или фиксированное начальное значение). Символы обрабатываются последовательно — каждый символ изменяет state.Финальный state = все символы, закодированные в одно число
В конце потока: state содержит всю информацию обо всех символах. Записывается как одно число. Декодер читает state и извлекает символы в обратном порядке (LIFO). Практически: state периодически сбрасывается в выходной буфер, когда превышает порог.ANS — это теоретически оптимальный энтропийный кодер: средняя длина кода точно совпадает с энтропией Шеннона (при достаточной точности таблиц). Huffman всегда тратит как минимум 1 бит на символ — даже если символ несёт 0.01 бит информации. Для потоков с сильно неравномерным распределением (типично после LZ77) разница между ANS и Huffman может составлять 10–30% размера выходного файла.
Zstd: LZ77 + ANS + адаптивный поиск
Теперь можно понять, почему Zstd настраивается на 22 уровнях, а Snappy — нет. Zstd — это pipeline из трёх компонентов, и каждый имеет настраиваемые параметры:
Почему 22 уровня
22 уровня Zstd — это комбинаторное пространство из: стратегии поиска (5 вариантов) × размера окна (10+ значений) × глубины поиска × параметров ANS таблиц. Уровни — предустановленные точки на кривой speed/ratio.
LZ4 vs Snappy: почему LZ4 быстрее
LZ4 и Snappy используют одинаковый подход — только LZ77, без энтропийного кодирования. Но LZ4 обычно быстрее при лучшем сжатии. Причины — в деталях формата:
Парадокс: LZ4 проще и при этом лучше. Snappy потратил байты формата на поддержку 4 GB offsets и CRC checksums. В реальности: offsets > 64 KB крайне редки (данные обычно блоки по 1–256 KB), а CRC можно проверять на уровне storage (HDFS, S3). LZ4 убрал ненужное и выиграл по обоим метрикам.
Сводная таблица: из чего построены алгоритмы
Почему это важно для data engineering
Понимание внутренностей даёт практические знания:
Ключевые выводы
- LZ77 — фундамент всех четырёх алгоритмов. Ищет повторяющиеся последовательности в скользящем окне и заменяет на ссылки (offset + length).
- Huffman coding — энтропийный кодер GZIP/DEFLATE. Каждый символ = целое число бит. Оптимален для алфавита из 256 символов, но теряет до 1 бит на символ при skewed distribution.
- ANS — инновация Zstd. Кодирует дробные биты, достигая энтропии Шеннона. Дает Zstd 10–30% преимущества над GZIP при той же стратегии LZ77.
- Zstd = LZ77 (5 стратегий поиска) + tANS (дробные биты). 22 уровня — комбинация размера окна, глубины поиска, и стратегии. Уровень 1 ≈ Snappy по скорости, уровень 22 ≈ лучше GZIP-9 по сжатию.
- LZ4 быстрее Snappy за счёт упрощённого формата: один тип токена (нет switch), фиксированный 2-byte offset (нет branching), нет CRC overhead.
- Хороший encoding снижает ценность компрессии: если dictionary + delta + bit-packing уже убрали избыточность, разница между Zstd и LZ4 минимальна.