Временная сложность
O(n · W)
DEFLATE — это алгоритм сжатия без потерь, используемый внутри gzip, ZIP и PNG. Это не один отдельный приём, а целый процесс, объединяющий две идеи, которые можно изучать отдельно на этом сайте: поиск совпадений в словаре LZ77 и кодирование Хаффмана.
Как это работает:
1. Сканирование LZ77 — поиск повторяющихся подстрок в скользящем окне и создание токенов (смещение, длина, следующий символ)
2. Поток символов — преобразование этих токенов в последовательность символов (маркеры совпадений + литералы)
3. Кодирование Хаффмана — создание более коротких битовых кодов для символов, которые встречаются чаще
4. Битовый поток — замена каждого символа соответствующим кодом; затем gzip добавляет заголовок и контрольную сумму
Почему это работает:
LZ77 устраняет избыточность типа «эту фразу я уже произносил». Хаффман устраняет избыточность типа «некоторые символы встречаются редко». Вместе они сжимают и повторяющуюся структуру, и неравномерность частот — значительно эффективнее, чем каждый метод по отдельности, особенно для обычного текста и веб-ресурсов.
Временная сложность:
В основном зависит от поиска совпадений: O(n · W) при наивном подходе; в реальном gzip значительно быстрее благодаря цепочкам хешей и отложенному сопоставлению
Этап Хаффмана: O(k log k), где k — количество различных символов в блоке
Пространственная сложность: O(W + k) для скользящего окна и таблиц кодов
Свойства:
- Блочный алгоритм сжатия без потерь (RFC 1951)
- Используется в gzip (RFC 1952), zlib, ZIP и PNG IDAT
- Реальные реализации используют фиксированные или динамические деревья Хаффмана и отдельные коды расстояний — эта страница объясняет общий процесс, а не все детали RFC
- Простая модель для запоминания: сначала словарь, затем энтропия
Если запомнить только одно предложение: gzip — это в основном DEFLATE, а DEFLATE — это LZ77, передающий данные кодировщику Хаффмана.
Похожие алгоритмы
Частые вопросы
- Что такое DEFLATE?
- DEFLATE — это алгоритм сжатия без потерь, используемый внутри gzip, ZIP и PNG. Это не один отдельный приём, а целый процесс, объединяющий две идеи, которые можно изучать отдельно на этом сайте: поиск совпадений в словаре LZ77 и кодирование Хаффмана.
- Какова сложность DEFLATE?
- Память: O(W + k)
- Для кого предназначена визуализация DEFLATE?
- Визуализация DEFLATE рассчитана на продвинутый уровень в категории «Сжатие данных». Полезна для студентов, подготовки к собеседованиям и практического изучения.
- Какие алгоритмы связаны с DEFLATE?
- В той же категории (Сжатие данных) вы можете изучить: Run-Length Encoding, LZ77, LZW. Каждый из них имеет интерактивную визуализацию.