LZ77, LZW і Deflate

Коротко: LZ77 і LZW — словникові методи стиснення: вони замінюють повтори короткими посиланнями на вже зустрінуті дані. Deflate поєднує LZ77 із кодуванням Гаффмана.

Докладніше: Deflate використовується в ZIP, gzip, PNG і стисненні HTTP. Це найпоширеніший метод стиснення взагалі.

Подробиці

• LZ77: Тримає «вікно» з останніх кілобайтів. Зустрівши повтор, кодувальник пише (відстань, довжина) замість байтів. abcabcabc перетворюється на abc плюс «скопіювати 6 символів з відстані 3».
• LZW: На ходу будує словник із послідовностей символів і виводить лише індекси. Застосовується в GIF і раннього TIFF. Патентні питання колись сповільнювали його поширення.
• Deflate: LZ77 дає літерали та посилання, потім Гаффман кодує часті символи коротко. Вікно 32 КіБ.
• Наступники: Zstandard і Brotli досягають кращих коефіцієнтів за вищої швидкості, див. Brotli і Zstandard.
• Межа стиснення: Випадкові або вже стиснені дані майже не зменшити.

Див. також: Стиснення