Компресія LZ77: Пошук повторень у ковзному вікні

Пошук повторів для ефективного стиснення

LZ77, розроблений Абрамом Лемплем та Якобом Зівом у 1977 році, використовує алгоритм стиснення даних шляхом заміщення повторюваних підрядків на невеликі посилання на їх попереднє місце розташування – основна ідея, що лежить в основі gzip, zlib, PNG, DEFLATE та більшості сучасних компресорів. Алгоритм переміщує двочастинне вікно по вхідним даним: пошуковий буфер вже бачених даних поза курсором, та буфер огляду майбутніх даних, які ще потрібно закодувати.

[........search buffer........][cursor][...look-ahead buffer...]
at each step: find the LONGEST match between look-ahead and search buffer
emit token (distance, length, next-literal)  then slide the window forward

Токен (відстань, довжина, літера)

Кожен крок алгоритму LZ77 генерує один токен: відстань назад до початку найкращого зіткнення, знайденого в буфері пошуку, довжину зіткнення та один літерний байт, що слідує за зіткненням. Зазвичай використовується жадібний алгоритм пошуку найдовшого зіткнення – завжди брати найдовше доступне зіткнення на позиції курсора, навіть якщо коротший зіткнення зараз може дозволити ще довше зіткнення відразу після нього; деякі реальні компресори використовують ледачий збіг, переглядаючи один байт вперед перед тим, як прийняти рішення, щоб дешево повернути частину втраченого співвідношення.

example:  "the cat sat on the mat"
encoding "the mat" late in the string can reference "the " from position 0:
token: (distance=19, length=4, literal='m') + literals "at"

Чому збій може перекриплювати себе

Це тонкість, яка заплутує неочевидні реалізації: довжина відповідності законно перевищує поточну відстань. Якщо відстань становить 3 і довжина – 8, декодер не падає — він копіює байт за байтом з 3 позицій назад, і оскільки кожен скопійований байт негайно стає доступним як джерело для наступного копіювання, результат є повторюваним шаблоном. Це єдине правило дозволяє LZ77 стискати довгі пробіли однакових коротких повторень (наприклад, 'aaaaaaaa' або повторювальний візерунок шпалер) в один маленький токен замість того, щоб потрібен був один токен на кожне повторення.

Розмір вікна – це ключовий фактор

Розмір буфера пошуку обмежує відстань, на яку можна віднестись до відповідності, тому безпосередньо впливає на стиснення даних із довготривалими повтореннями: DEFLATE (використовується в gzip, zlib та PNG) встановлює його на 32 КБ, тоді як новіші формати дозволяють значно збільшити цей розмір – Brotli до 16 МБ, а Zstandard у режимі "довготривале збігування" може охопити весь файл. Більше вікно ловить більше повторень, але потребує більше пам’яті та, безпосередньо, більш тривалий пошук; виробничі кодери використовують хеш-таблицю, засновану на кількох наступних байтах, щоб пошук відповідності займав у середньому O(1) замість лінійного сканування всього вікна.

LZ77 є лише половиною контуру

Окремий вихід LZ77 — потік (відстані, довжини, літери) токенів — не є сам собою максимально компактним, оскільки короткі відстані, загальні довжини та часті літери повинні коштувати менше біт, ніж рідкі відстані, рідкі довжини та рідкі літери. DEFLATE тому проходить вихід LZ77 через другий етап, кодування Хаффмана, яке призначає коротші бітові коди найпоширенішим токенам; цей двоетапний дизайн (відповідність словнику, а потім стиснення на основі інформації) є шаблоном, який практично кожен загальнопризначений стисник з 1977 року використовував, включаючи LZMA, Brotli та Zstandard, які в основному відрізняються тим, як вони розумно шукають відповідності та який кодер на основі інформації вони з ними попарно використовують.

LZ77 порівняно з LZ78

Алгоритм-брат LZ78 (1978) замінює ковзне вікно на явний, зростаючий словник попередньо помічених фраз, посилання на які здійснюються за індексом, а не за (відстанью, довжиною) — основа LZW, яка використовується в GIF та старих Unix компресорах. Перевага LZ77 полягає в тому, що їй не потрібна жодна явна структура словника для передачі або синхронізації; її недолік полягає в тому, що відповідність може шукати лише настільки назад, як дозволяє вікно, тоді як словник LZ78 концептуально охоплює весь до цього часу отриманий вхід.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте LZ77 Compression і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.