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.
• Предел сжатия: Случайные или уже сжатые данные почти не уменьшить.

См. также: Сжатие