Временная сложность
Лучший: O(n)
Средний: O(n · W)
Худший: O(n · W)
LZ77 — это словарный алгоритм сжатия, изобретённый Абрахамом Лемпелем и Якобом Зивом в 1977 году. Вместо фиксированного кодового словаря он использует скользящее окно недавно обработанных данных в качестве динамического словаря.
Как работает:
1. Поддерживает буфер поиска (уже закодированное окно) и буфер предварительного просмотра
2. Находит самый длинный префикс буфера предварительного просмотра, который также встречается в окне
3. Выдаёт тройку (offset, length, next):
- offset — насколько далеко назад начинается совпадение
- length — количество символов для копирования
- next — буквальный символ после совпадения (или пустое значение в конце файла, EOF)
4. Сдвигает окно вперёд на length + 1 и повторяет процесс
Почему это работает:
Повторяющиеся фразы (слова, шаблоны, подстроки) часто встречаются в тексте и структурированных данных. Ссылка на предыдущие данные в окне позволяет представить длинную последовательность короткой ссылкой. Поток троек декодируется однозначно: данные копируются с указанного offset, а затем добавляется буквальный символ.
Временная сложность:
Лучшая: O(n) при использовании скользящих хешей или продвинутых алгоритмов поиска совпадений
Средняя: O(n · W) при наивном поиске (W = размер окна)
Худшая: O(n · W)
Пространственная сложность: O(W) для окна
Свойства:
- Метод словарного сжатия без потерь со скользящим окном
- Основа DEFLATE (gzip, ZIP, PNG), который объединяет LZ77 с алгоритмом Хаффмана
- Размер окна определяет компромисс между степенью сжатия, использованием памяти и затратами на поиск
- Хорошо обрабатывает повторяющиеся подстроки; случайные данные практически не сжимаются
LZ77 превратил идею «искать недавние повторы» в практическую основу большинства повседневных архивов без потерь.
Похожие алгоритмы
Частые вопросы
- Что такое LZ77?
- LZ77 — это словарный алгоритм сжатия, изобретённый Абрахамом Лемпелем и Якобом Зивом в 1977 году. Вместо фиксированного кодового словаря он использует скользящее окно недавно обработанных данных в качестве динамического словаря.
- Какова сложность LZ77?
- Время (среднее): O(n · W) при наивном поиске (W = размер окна) · Память: O(W)
- Для кого предназначена визуализация LZ77?
- Визуализация LZ77 рассчитана на средний уровень в категории «Сжатие данных». Полезна для студентов, подготовки к собеседованиям и практического изучения.
- Какие алгоритмы связаны с LZ77?
- В той же категории (Сжатие данных) вы можете изучить: Run-Length Encoding, LZW, Huffman Coding. Каждый из них имеет интерактивную визуализацию.