Вывод вперёд: LZ77 — это алгоритм словарного сжатия на основе скользящего окна, основная идея которого — "использовать исторические данные как словарь, при обнаружении повторяющегося содержимого ссылаться на него". При кодировании выводится триплет (distance, length, next_char): обратный ход на distance символов для поиска совпадения, длина совпадения length, следующий несовпадающий символ next_char. На примере строки "abracadabra" из 11 символов, после кодирования LZ77 требуется всего 5 триплетов для представления, что даёт значительный эффект сжатия. LZ77 является ключевым компонентом DEFLATE (ZIP/GZIP/PNG) и общим предком современных алгоритмов сжатия LZSS/LZMA/LZ4. Ниже мы начнём с принципа скользящего окна и постепенно продемонстрируем процесс кодирования.
Если вы не очень знакомы с принципом кодирования Хаффмана, рекомендуется сначала прочитать Подробное объяснение принципа кодирования Хаффмана: основа алгоритмов сжатия.
1. Что такое словарное сжатие
Алгоритмы сжатия делятся на два основных направления: статистическое кодирование (например, кодирование Хаффмана) назначает символам коды переменной длины в соответствии с частотой; словарное сжатие заменяет повторяющееся содержимое "указателями-ссылками". LZ77 принадлежит к направлению словарного сжатия, он не создаёт заранее таблицу словаря, а использует уже обработанные исторические данные как неявный словарь — при обнаружении повторяющегося содержимого использует "указатель обратного хода" для ссылки на позицию, где оно ранее встречалось.
| Направление сжатия | Основной принцип | Представительные алгоритмы | Преимущества | Недостатки |
|---|---|---|---|---|
| Статистическое кодирование | Назначение кодов переменной длины по частоте | Хаффман, арифметическое кодирование | Приближение к энтропийному пределу | Не справляется с длинными повторами |
| Словарное сжатие | Замена повторяющегося содержимого ссылками | LZ77, LZW, LZMA | Хорошо справляется с повторяющимися шаблонами | Неэффективно для случайных данных |
| Гибридное кодирование | Словарь + статистика, два этапа | DEFLATE, ZSTD | Оптимальное комбинирование | Сложная реализация |
| Преобразующее кодирование | Преобразование в частотную область с квантованием | DCT(JPEG), DWT | Высокая эффективность сжатия с потерями | Потеря информации |
На практике самые популярные алгоритмы сжатия — это почти всегда "гибридное кодирование": сначала LZ77 устраняет повторяющиеся шаблоны, затем Хаффман выполняет частотное сжатие остатков. DEFLATE — это классическая комбинация LZ77 + Хаффмана, широко используемая в ZIP, GZIP, PNG.
2. Подробное объяснение принципа алгоритма LZ77
Основа LZ77 — механизм скользящего окна. Окно разделено на две части: буфер поиска (уже обработанные исторические данные) и буфер предварительного просмотра (данные для обработки). При кодировании берётся фрагмент из буфера предварительного просмотра, в буфере поиска ищется самое длинное совпадение, если найдено — выводится триплет, если нет — выводится исходный символ.
1. Структура скользящего окна
Размер скользящего окна напрямую определяет эффект сжатия — чем больше окно, тем больше исторических данных можно просмотреть при обратном ходе, тем выше вероятность совпадения. Размеры окон разных алгоритмов сильно различаются.
| Алгоритм | Буфер поиска | Буфер предварительного просмотра | Максимальная длина совпадения | Типичный сценарий |
|---|---|---|---|---|
| LZ77 (оригинальный) | Несколько KB | Десятки байт | 16 байт | Учебный пример |
| DEFLATE | 32KB | 258 байт | 258 байт | ZIP/GZIP/PNG |
| LZMA | 8MB (настраиваемый) | 273 байта | 273 байта | Архивация 7z/xz |
| LZ4 | 64KB | Без ограничений | Без ограничений | Сжатие в реальном времени |
| ZSTD | 8MB (максимум 1GB) | Без ограничений | Без ограничений | Современное универсальное использование |
2. Формат кодирования триплетов
Единица вывода LZ77 — триплет (distance, length, next_char), значение трёх полей показано в таблице ниже.
| Поле | Значение | Диапазон значений (DEFLATE) | Бит кодирования | Пример |
|---|---|---|---|---|
| distance | Расстояние обратного хода (сколько символов назад искать совпадение) | 1–32768 | 15 bit | distance=10 → 10 символов назад |
| length | Длина совпадения (сколько символов совпадают подряд) | 3–258 | 8 bit | length=5 → совпадение 5 символов |
| next_char | Следующий символ после совпадения | 0–255 | 8 bit | next_char='d' → ASCII 100 |
Гениальность триплета в том, что после окончания совпадения выводится ещё один next_char, что гарантирует, что кодировщик всегда может продвинуться вперёд хотя бы на 1 символ и не застрянет. Если не найдено никакого совпадения (length=0), distance и length оба равны 0, выводится только next_char — это эквивалентно деградации до хранения исходного символа.
3. Стратегия поиска совпадений
Поиск совпадений — это узкое место производительности LZ77: берётся фрагмент из буфера предварительного просмотра, в буфере поиска ищется самое длинное совпадение. Грубый поиск имеет сложность O(n×m), реальные реализации используют хеш-таблицы или суффиксные деревья для ускорения.
| Стратегия поиска | Структура данных | Сложность поиска | Пространственные затраты | Типичное применение |
|---|---|---|---|---|
| Грубый поиск | Нет | O(n×m) | Нет | Учебный пример |
| Хеш-цепочки | Хеш-таблица + связный список | O(n) в среднем | Низкие | zlib (DEFLATE) |
| Хеш-корзины | Хеш-таблица + массив | O(1) в среднем | Средние | LZ4 |
| Суффиксное дерево | Суффиксное дерево/суффиксный массив | O(n) в худшем случае | Высокие | LZMA |
3. Практический пример: демонстрация кодирования "abracadabra"
Выполним полное кодирование строки "abracadabra" (11 символов) с помощью LZ77. Начальное состояние: буфер поиска пуст, буфер предварительного просмотра содержит всю строку. Посканируем позицию за позицией, ища самое длинное совпадение в исторических данных.
Исходный текст: a b r a c a d a b r a
Процесс кодирования:
| Шаг | Текущая позиция | Содержимое lookahead | Поиск в буфере поиска | Выходной триплет | Описание |
|---|---|---|---|---|---|
| 1 | Позиция 1 | abracadabra | Пусто, совпадений нет | (0, 0, 'a') | Первый символ, вывод напрямую |
| 2 | Позиция 2 | bracadabra | "a", "b" не найдено | (0, 0, 'b') | Первое появление, вывод напрямую |
| 3 | Позиция 3 | racadabra | "ab", "r" не найдено | (0, 0, 'r') | Первое появление, вывод напрямую |
| 4 | Позиция 4 | acadabra | "abr" найдено "a" | (0, 0, 'a') | "a" найдено, но продолжения нет |
| 5 | Позиция 5 | cadabra | В "abra" нет "c" | (0, 0, 'c') | Первое появление, вывод напрямую |
| 6 | Позиция 6 | adabra | В "abrac" найдено "a" | (0, 0, 'a') | "a" совпало, но продолжения нет |
| 7 | Позиция 7 | dabra | В "abraca" нет "d" | (0, 0, 'd') | Первое появление, вывод напрямую |
| 8 | Позиция 8 | abra | Откат на 7 — найдено "abra" | (7, 4, end) | Совпадение "abra" 4 символа |
Сравнение эффективности кодирования:
| Метод кодирования | Число выходных единиц | Бит на единицу | Всего бит | Экономия vs оригинала |
|---|---|---|---|---|
| ASCII оригинал | 11 символов | 8 | 88 | — (базовый) |
| LZ77 (без оптимизации) | 8 триплетов | 31 (ср.) | 248 | -182% (расширение) |
| LZ77 (оптимизация флагов) | 8 единиц | 12 (ср.) | 96 | -9% (лёгкое расширение) |
| LZ77 + Huffman | 8 единиц | 4,5 (ср.) | 36 | 59% |
Анализ результатов: чистый LZ77 для коротких строк может давать расширение (триплет занимает больше места, чем исходный символ) — именно поэтому LZ77 обычно комбинируют с кодированием Хаффмана; DEFLATE — это LZ77 + Huffman. В примере с "abracadabra" ключевая точка сжатия — позиция 8 с совпадением "abra" (distance=7, length=4): четыре символа описываются одним триплетом. Для более длинных текстов с большим числом повторов (исходный код, логи) эффект сжатия LZ77 заметно возрастает.
4. Варианты LZ77 и современная эволюция
После предложения LZ77 в 1977 году появилось множество вариантов, каждый из которых оптимизировал определённый аспект для конкретного сценария. В таблице ниже сравниваются основные члены семейства LZ77.
| Алгоритм | Ключевое улучшение | Степень сжатия | Скорость сжатия | Скорость распаковки | Типичное применение |
|---|---|---|---|---|---|
| LZ77 (оригинал) | Триплетное кодирование | Низкая | Медленно | Средне | Обучение |
| LZSS | Флаги для разделения совпадений/литералов | Средняя | Средне | Быстро | Ранние системы |
| DEFLATE | LZSS + Huffman в два прохода | Выше среднего | Средне | Быстро | ZIP/GZIP/PNG |
| LZMA | Большое окно + range coding + оптимальный разбор | Высокая | Медленно | Средне | 7z/xz архивы |
| LZ4 | Жертвует степенью ради скорости | Низкая | Очень быстро | Очень быстро (4 ГБ/с) | Реальное время / ядро |
| LZW | Явный словарь (без скользящего окна) | Средняя | Быстро | Быстро | GIF/TIFF |
| ZSTD | Вариант LZ77 + FSE + словари | Высокая | Быстро | Очень быстро | Современное общее |
С точки зрения тенденций эволюции, современные алгоритмы (ZSTD, brotli) значительно повысили скорость при сохранении высокой степени сжатия, постепенно заменяя DEFLATE как новый стандарт. Но основная идея LZ77 — словарные ссылки со скользящим окном — остаётся неизменной, все варианты строятся на этой основе.
| Сценарий | Рекомендуемый алгоритм | Обоснование | Типовая степень сжатия |
|---|---|---|---|
| Архивация файлов | LZMA (xz) | Максимальная степень, скорость не важна | 70–85% |
| Общее сжатие | ZSTD | Баланс степени и скорости | 60–80% |
| Передача в реальном времени | LZ4 | Распаковка 4 ГБ/с, минимальная задержка | 50–65% |
| Web-передача | DEFLATE/GZIP | Лучшая совместимость, поддержка всеми браузерами | 50–70% |
| Графические форматы | DEFLATE (PNG) | Сжатие без потерь, подходит для графики | 50–75% |
| Данные в памяти | LZ4 | Низкая нагрузка на CPU, подходит для частого сжатия | 50–65% |
О конкретном применении DEFLATE в формате PNG можно прочитать в Подробное объяснение принципа сжатия PNG. О разнице между сжатием без потерь и сжатием с потерями можно прочитать в Сжатие без потерь vs сжатие с потерями: ключевые различия.
5. Часто задаваемые вопросы FAQ
Q1: Что такое алгоритм LZ77?
LZ77 — это алгоритм словарного сжатия на основе скользящего окна, предложенный Лемпелом и Зивом в 1977 году. Основная идея: использовать ранее обработанные данные как словарь, при обнаружении повторяющегося содержимого заменять исходные данные триплетом (distance, length, next_char), где distance — расстояние обратного хода, length — длина совпадения, next_char — следующий символ после совпадения. LZ77 является ключевым компонентом DEFLATE (ZIP/GZIP/PNG) и предком современных алгоритмов LZSS/LZMA/LZ4.
Q2: Что означает скользящее окно в LZ77?
Скользящее окно — это ключевая структура данных LZ77, разделённая на буфер поиска (уже обработанные исторические данные) и буфер предварительного просмотра (данные для обработки). При кодировании берётся фрагмент из буфера предварительного просмотра и ищется самое длинное совпадение в буфере поиска. Типичный размер окна — 32KB (стандарт DEFLATE), чем больше окно, тем выше вероятность совпадения, но больше потребление памяти. Размер окна определяет верхний предел максимального расстояния обратного хода distance.
Q3: В чём разница между LZ77 и LZ78?
LZ77 использует скользящее окно как неявный словарь, совпадающее содержимое напрямую ссылается на исторические данные без отдельного хранения словаря; LZ78 использует явную таблицу словаря, сохраняя номера уже встреченных строк как записи словаря, при кодировании выводится индекс словаря. LZ77 лучше подходит для данных с локальными повторами (например, текст), LZ78 — для данных с глобальными повторами. На практике потомки LZ77 (DEFLATE/LZMA/LZ4) гораздо популярнее потомков LZ78 (LZW).
Q4: Какой из LZ77, LZMA, LZ4 имеет самую высокую степень сжатия?
Рейтинг степени сжатия: LZMA > LZ77(DEFLATE) > LZ4. LZMA использует большее окно (по умолчанию 8MB), более оптимальные алгоритмы совпадения и интервальное кодирование, самая высокая степень сжатия, но самая низкая скорость; DEFLATE с окном 32KB + Хаффман, средняя степень сжатия и скорость; LZ4 жертвует степенью сжатия ради максимальной скорости, самая низкая степень сжатия, но скорость распаковки до 4GB/s. Выбор зависит от сценария: для архивации — LZMA, для общего использования — DEFLATE/ZSTD, для реального времени — LZ4.
Заключение
LZ77 — это родоначальник алгоритмов словарного сжатия, основной принцип — "скользящее окно + триплетные ссылки": использовать исторические данные как неявный словарь, при обнаружении повторяющегося содержимого выводить триплет (distance, length, next_char). Чистый LZ77 может приводить к увеличению размера для коротких текстов, но в комбинации с кодированием Хаффмана (DEFLATE) становится стандартным решением для сжатия ZIP/GZIP/PNG. Современные варианты LZMA преследуют максимальную степень сжатия, LZ4 — максимальную скорость, ZSTD — баланс обоих.
Ключевые три момента для понимания LZ77: первое — скользящее окно определяет диапазон совпадений (DEFLATE 32KB, LZMA 8MB), второе — триплет является базовой единицей кодирования (обратный ход + длина + следующий символ), третье — стратегия поиска совпадений определяет производительность (хеш-цепочки самые быстрые, суффиксные деревья самые оптимальные). Гибридное кодирование LZ77 + Хаффман — золотой стандарт современного сжатия без потерь.
Связанные рекомендации
Нужно сжать файлы? Попробуйте SmartSlim
Основан на собственном движке сжатия Rust, поддерживает 10 основных категорий и более 40 форматов, включая PDF/изображения/видео/Office/OFD, локальное сжатие без передачи данных.