UK 
EnglishТипова
Polski💾 Стиснення LZ77
Спостерігайте, як алгоритм стиснення LZ77 зі ковзним вікном кодує дані, знаходячи повторювані шаблони.
Схожі симуляції
Про стиснення LZ77
LZ77, опублікований Абрахамом Лемпелем і Джейкобом Зівом у 1977 році, — це алгоритм стиснення без втрат на основі словника, що замінює повторювані підрядки зворотними посиланнями на ковзне вікно раніше побачених даних. Кожен закодований токен — це трійка (зсув, довжина, наступний символ): зсув вказує назад у буфер пошуку, довжина повідомляє, скільки символів копіювати, а наступний символ — це перший символ, що не збігається. Ця схема «розбір-потім-посилання» не потребує заздалегідь побудованого словника — і компресор, і декомпресор відновлюють той самий неявний словник із самого потоку даних, що робить LZ77 адаптивним і універсально застосовним.
LZ77 лежить в основі деяких з найпоширеніших форматів стиснення в обчислювальній техніці: DEFLATE (використовується в ZIP і gzip) поєднує LZ77 з кодуванням Хаффмана, LZSS — вдосконалений варіант, що використовується в багатьох вбудованих системах, а сучасні формати, такі як LZ4 і Zstandard, безпосередньо походять від ідей Лемпеля-Зіва. Цей симулятор дозволяє вводити будь-який текст, регулювати розміри буфера пошуку та вікна попереднього перегляду, і спостерігати, як кодер сканує символ за символом, підсвічуючи збіглі ділянки, згенеровані токени та коефіцієнт стиснення, що змінюється.
Часті запитання
Як працює ковзне вікно LZ77?
Алгоритм підтримує два буфери поруч: буфер пошуку (історія), що містить останні S символів, уже закодованих, і буфер попереднього перегляду з наступними L символами для кодування. На кожному кроці кодер знаходить найдовший префікс буфера попереднього перегляду, який також є в буфері пошуку, записує зворотне посилання (зсув, довжина), потім переходить за межі збіглих символів плюс один буквальний наступний символ. Обидва буфери зсуваються разом — звідси «ковзне вікно».
Якого коефіцієнта стиснення зазвичай можна досягти з LZ77?
Коефіцієнт стиснення сильно залежить від надлишковості вхідних даних. Типовий англійський текст стискається приблизно до 30–40% від початкового розміру за допомогою LZ77 + Хаффман (DEFLATE). Послідовності ДНК, які часто повторюються, можуть досягти скорочення на 60–80%. Справді випадкові дані взагалі не стискаються — кожен пошук зворотного посилання зазнає невдачі, і кожен символ доводиться передавати як літерал, через що вихід стає трохи більшим за вхід через накладні витрати на токени.
Яка різниця між LZ77 і LZ78?
LZ77 використовує ковзне вікно фіксованого розміру в нещодавній вихід як неявний словник. LZ78 (1978) натомість будує явний словник фраз, що зростає протягом кодування, використовуючи токени індекс + новий символ замість токенів зсув + довжина. LZW (Велч, 1984), основа формату GIF і раннього Unix compress, — це вдосконалення LZ78, що опускає буквальний символ. Варіанти LZ77 зазвичай досягають кращого стиснення природної мови; варіанти LZ78 розбирають регулярніше і можуть бути швидшими на деякому обладнанні.
Чому більший буфер пошуку покращує стиснення?
Більший буфер пошуку дає кодеру більше історії для пошуку збігів, збільшуючи ймовірність знаходження довгого повторюваного підрядка. Теоретична межа стиснення LZ77 наближається до емпіричної ентропії джерела, коли розмір вікна прямує до нескінченності. На практиці DEFLATE використовує вікно пошуку 32 КБ; LZ4 може використовувати вікна до 64 КБ; Zstandard підтримує вікна до 2 ГБ, тому він досягає значно кращих коефіцієнтів на великих файлах з далекосяжною надлишковістю, як-от архіви вихідного коду.
Чи є LZ77 стисненням без втрат, і як відновлюються вихідні дані?
Так, LZ77 повністю без втрат. Розпакування просте: сканується потік токенів, і для кожної трійки (зсув, довжина, символ) копіюється довжина символів, починаючи з позиції (поточна_позиція_виводу − зсув) з уже декодованого вихідного буфера, а потім додається символ. Жодного словника чи додаткової інформації не потрібно, окрім самого потоку токенів. Тому декомпресор працює за O(n) час, зазвичай значно швидше за кодер, який має шукати у вікні для кожної позиції.
Що таке LZSS і як він покращує LZ77?
LZSS (Сторер і Шимянський, 1982) додає один прапорцевий біт перед кожним токеном, щоб вказати, чи це зворотне посилання, чи сирий літерал. LZ77 завжди видає трійку навіть для незбіглих символів (зсув=0, довжина=0, символ), витрачаючи біти. LZSS видає лише байт символу, коли корисного збігу немає, і опускає поле наступного символу зі зворотних посилань. Це зменшує накладні витрати для вхідних даних з низькою надлишковістю і є варіантом, що використовується в класичних форматах архівів, таких як LHA та старіших методах PKZIP.
Як DEFLATE поєднує LZ77 з кодуванням Хаффмана?
DEFLATE (RFC 1951, використовується в ZIP, gzip, PNG, zlib) виконує LZ77 з вікном пошуку 32 КБ, щоб отримати потік літералів і зворотних посилань, а потім додатково стискає цей потік двома деревами Хаффмана: одним для значень літерал/довжина (0–285) і одним для значень відстані (1–32768). Самі дерева Хаффмана стискаються кодом третього рівня. Цей двоетапний підхід — причина, чому gzip послідовно перевершує чистий LZ77: етап Хаффмана вловлює надлишковість частоти символів, яку LZ77 залишає невикористаною.
Чому LZ77 не може стиснути випадкові дані?
Випадкові дані за визначенням мають максимальну ентропію: кожен байт однаково ймовірний незалежно від контексту, тому ймовірність знаходження збігу в буфері пошуку дуже низька. Більшість токенів зводяться до (0, 0, символ) — чистих літералів — а поля зсув/довжина додають накладні витрати замість економії місця. Це не обмеження саме LZ77, а фундаментальний наслідок теорії інформації: жоден компресор без втрат не може зменшити очікувану довжину послідовності, узятої з джерела максимальної ентропії.
Яка часова складність кодування LZ77?
Наївне кодування LZ77 має складність O(n·W), де n — довжина вхідних даних, а W — розмір вікна пошуку, оскільки на кожній позиції кодер сканує все вікно для пошуку найдовшого збігу. З хеш-таблицею (як у zlib) середня складність падає до O(n), хоча найгірший випадок залишається квадратичним. Суфіксні масиви та суфіксні автомати можуть досягти O(n log n) або O(n) оптимального в найгіршому випадку розбору, як це використовується в дослідницьких компресорах на кшталт внутрішньої фази LZ у brotli.
Як LZ77 працює з бінарними даними, такими як виконувані файли чи зображення?
Виконувані бінарні файли містять повторювані послідовності інструкцій, таблиці імпорту та рядкові літерали, тому LZ77 досягає помірного стиснення (зазвичай скорочення розміру на 40–60%). Нестиснуті растрові зображення з однорідними ділянками стискаються добре (PNG використовує DEFLATE). Однак уже стиснуті дані (JPEG, MP3, MPEG) мають майже випадковий розподіл байтів після власного ентропійного кодування, тому повторне застосування LZ77 дає незначний або від'ємний виграш у стисненні — більшість архіваторів виявляють це і зберігають такі файли нестисненими.
Які сучасні формати походять від LZ77?
LZ4 (2011) надає пріоритет швидкості розпакування над коефіцієнтом стиснення, досягаючи розпакування кілька ГБ/с на сучасних процесорах, використовуючи просте 4-байтне хеш-зіставлення. Zstandard (Facebook, 2016, RFC 8878) додає скінченне ентропійне кодування (сучасний асиметричний числовий системний кодер) поверх зіставлення LZ77 і досягає коефіцієнтів, конкурентних з bzip2, зі швидкістю на кшталт LZ4. Brotli (Google, 2015, RFC 7932), що використовується в HTTP content-encoding, поєднує LZ77 зі статичною контекстною моделлю зі 120 записами та спільним словником для вебресурсів.