> lz77 | sliding | window <
// LZ77 – сжатие с использованием скользящего окна и словарных ссылок
Словарное кодирование
Использует ссылки по смещению и длине для повторяющихся шаблонов.
Скользящее окно
Поддерживает подвижное окно поиска наиболее длинных совпадений.
Базовый алгоритм
Лежит в основе ZIP, GZIP, DEFLATE и PNG.
>> техническая информация
Как работает LZ77:
LZ77 поддерживает скользящее окно из недавно просмотренных данных. Для каждой позиции алгоритм ищет в окне самую длинную совпадающую подстроку. Если совпадение найдено, выводится ссылка (смещение, длина, следующий символ). Если нет — выводится литерал (0,0,символ). Так повторяющиеся участки заменяются короткими ссылками, обеспечивая без потерь сжатие.
Пример LZ77:
Text: "ABCABCABC" Window=4, Lookahead=4 Position 0: 'A' - no match → (0,0,A) Position 1: 'B' - no match → (0,0,B) Position 2: 'C' - no match → (0,0,C) Position 3: 'ABC' - matches at offset 3 → (3,3,A) Position 7: 'BC' - matches at offset 3 → (3,2,) Output: (0,0,A)(0,0,B)(0,0,C)(3,3,A)(3,2,)
Зачем использовать LZ77?:
- ▸Без потерь сжатие данных
- ▸Не требует предварительного знания формата данных
- ▸Адаптируется к структуре данных
- ▸Относительно простая реализация
- ▸Основа многих современных алгоритмов сжатия
>> часто задаваемые вопросы
Что такое LZ77?
LZ77 — универсальный алгоритм без потерь сжатия данных, опубликованный Абрахамом Лемпелем и Яковом Зивом в 1977 году. Он заменяет повторяющиеся последовательности в потоке данных ссылками на более ранние вхождения в несжатом потоке.
Как работает скользящее окно?
Скользящее окно состоит из буфера поиска (уже обработанные данные) и буфера lookahead (данные, подлежащие сжатию). Алгоритм ищет в буфере поиска самое длинное совпадение с началом lookahead, а затем выводит ссылку или литерал.
LZ77 и современные алгоритмы сжатия?
LZ77 лежит в основе многих современных методов сжатия. DEFLATE, используемый в ZIP и GZIP, сочетает LZ77 и кодирование Хаффмана. LZSS уменьшает избыточность LZ77, а LZ78 и LZW строят словарь по‑другому, сохраняя похожие принципы.
Какие размеры окна подходят лучше всего?
Для общих данных типичные размеры окна составляют 32–64 КБ. Большие окна находят больше совпадений, но требуют больше памяти и времени. DEFLATE использует окно 32 КБ. Буфер lookahead обычно равен 256–512 байтам. Оптимальный размер зависит от характера повторений в ваших данных.
// Разобранный пример
| # | Offset | Length | Next | Output |
|---|---|---|---|---|
| 1 | 0 | 0 | a | a |
| 2 | 0 | 0 | b | b |
| 3 | 0 | 0 | r | r |
| 4 | 3 | 1 | c | a + c |
| 5 | 2 | 1 | d | a + d |
| 6 | 7 | 4 | — | abra |
// Примеры кода
Input abracadabra (positions 0..10)
Token (offset, length, next)
offset = distance back into the window, length = bytes copied
Decode copy `length` bytes starting `offset` back, then append `next`
(the copy may overlap its own output, e.g. (1,5,x) repeats a byte)
Window the sliding search buffer; deflate/gzip use 32 KiB
>> Другие вопросы
В: Что означает тройка (смещение, длина, символ)?
О: Смещение — на сколько назад в уже просмотренном окне, длина — сколько байт копировать, символ — следующий новый байт. Декодер так шаг за шагом восстанавливает вывод.
В: Почему копия может перекрываться?
О: Если смещение меньше длины, копия читает только что записанные байты. Так получаются повторы: (1, 5, x) даёт пять раз предыдущий символ.
В: Где применяется LZ77?
О: LZ77 лежит в основе DEFLATE (gzip, zlib, PNG, ZIP) и, в вариантах, LZ4, Snappy, Zstandard и Brotli. Размер окна и стратегия поиска определяют степень сжатия и скорость.