Чем отличаются алгоритмы сжатия LZ77 и Хаффмана в алгоритме DEFLATE?

Алгоритмы LZ77 и Хаффмана отличаются подходами к сжатию данных, которые используются в алгоритме Deflate. github.com stackoverflow.com

LZ77 ищет повторяющиеся последовательности символов и заменяет их ссылками на предшествующие вхождения в данных. www.ai-futureschool.com Алгоритм использует скользящее окно — область фиксированного размера, в которой запоминает недавние данные. github.com LZ77 записывает не весь текст заново, а просто указывает: «возьми тот же фрагмент, что был чуть раньше». github.com

Хаффман основывается на частоте появления символов в исходных данных. www.ai-futureschool.com Алгоритм строит бинарное дерево, в котором символы с более высокой частотой располагаются ближе к корню, а символы с низкой частотой — дальше. www.ai-futureschool.com Каждый символ получает уникальный код, который состоит из последовательности бит, где более частые символы имеют короткие коды, а редкие — длинные. www.ai-futureschool.com

Таким образом, LZ77 фокусируется на замене повторяющихся строк, а Хаффман — на замене символов новыми символами, основываясь на частоте их использования. ru.wikipedia.org ru.ruwiki.ru

Комбинация этих алгоритмов в Deflate позволяет получить лучшее сжатие, чем любой из них по отдельности. stackoverflow.com LZ77 сжимает исходный файл в промежуточную последовательность буквенных обозначений и «элементов копирования», а затем Хаффман дополнительно сжимает эту промежуточную последовательность. stackoverflow.com