Разница: LZ77 против LZ4 против LZ4HC (алгоритмы сжатия)?

Question

Я понимаю алгоритмы LZ77 и LZ78. Я читал о LZ4 здесь и здесь и нашел код для него.

Эти ссылки описывают формат блока LZ4. Но было бы замечательно, если бы кто-то мог объяснить (или направить меня к какому-нибудь источнику объяснения):

• Чем LZ4 отличается от LZ77?
• Чем LZ4HC отличается от LZ4?
• Какая идея делает алгоритм LZ4HC таким быстрым?

Answer 1

LZ4 создан для быстрого сжатия, со скоростью сотни МБ / с на ядро. Он подходит для приложений, где требуется сжатие, которое очень дешево: например, вы пытаетесь сделать сетевой или дисковый формат более компактным, но не можете позволить себе тратить кучу процессорного времени на сжатие. Это в семье, например, с Snappy и LZO.

Естественной точкой сравнения является алгоритм DEFLATE в zlib, который использует кодирование LZ77 и Хаффмана и используется в форматах gzip,.ZIP и.PNG, а также во многих других местах для подсчета.

Эти быстрые компрессоры отличаются тем, что:

1. Они используют код обнаружения повторения, который работает быстрее (часто это простая хеш-таблица без обнаружения коллизий), но не ищет несколько возможных совпадений для поиска лучшего (что займет время, но приведет к более высокому сжатию) и не может найти какой-нибудь короткий Матчи.
2. Они только пытаются сжимать повторы во входных данных - они не пытаются использовать некоторые байты как более распространенные, чем другие.
3. Точно связанные с 2, они генерируют байты вывода за раз, а не биты; разрешение кодирования дробной части байта иногда допускало бы большее сжатие, но для кодирования и декодирования потребовалось бы больше операций ЦП (возможно, смещение битов, маскирование и ветвление).
4. Много практической работы было сделано для быстрой реализации их на современных процессорах.

Для сравнения, DEFLATE получает лучшее сжатие, но сжимает и распаковывает медленнее, а алгоритмы с высоким сжатием, такие как LZMA, bzip2, LZHAM или brotli, имеют тенденцию занимать еще больше времени (хотя Brotli при более быстрых настройках может конкурировать с zlib). Алгоритмы с высокой степенью сжатия сильно различаются, но в целом они, как правило, фиксируют избыточность на больших расстояниях, используют больше контекста для определения вероятности байтов и используют более компактные, но более медленные способы для выражения своих результатов в битах.

LZ4HC - это вариант LZ4 с "высокой степенью сжатия", который, как мне кажется, меняет точку 1 выше - компрессор находит более одного совпадения между текущими и прошлыми данными и ищет наилучшее совпадение, чтобы обеспечить малую производительность. Это улучшает степень сжатия, но снижает скорость сжатия по сравнению с LZ4. Тем не менее, скорость декомпрессии не пострадает, так что если вы сжимаете один раз и много раз распаковываете и, в основном, хотите очень дешевую декомпрессию, LZ4HC будет иметь смысл.

Обратите внимание, что даже быстрый компрессор может не позволить одному ядру насыщать большую полосу пропускания, как это обеспечивается SSD или быстрыми ссылками в центре данных. Существуют даже более быстрые компрессоры с более низкими коэффициентами, которые иногда используются для временной упаковки данных в ОЗУ. WKdm и Density - два таких компрессора; одна черта, которую они разделяют, заключается в действии 4-байтовых машинных слов ввода за раз, а не отдельных байтов. Иногда специализированное оборудование может обеспечить очень быстрое сжатие, как в чипах Samsung Exynos или технологии Intel QuickAssist.

Если вы заинтересованы в сжатии больше, чем LZ4, но с меньшим временем процессора, чем в deflate, автор LZ4 (Yann Collet) написал библиотеку под названием Zstd; в своем стабильном выпуске Facebook опубликовал информацию о том, как они его используют. Он использует конечные автоматы, а не коды Хаффмана, для энтропийного кодирования; Я не эксперт в этом деле, но, по крайней мере, алгоритм подробно описан в RFC. Самые быстрые режимы ZSTD сейчас приближаются к LZ4 по соотношению и скорости. Apple написала lzfse по схожим принципам. Несколько лет назад Google опубликовал библиотеку под названием gipfeli, хотя, похоже, она не набирала оборотов. Существуют также проекты, направленные на более быстрое сжатие в формате Zlib, такие как SLZ и исправления для zlib от CloudFlare и Intel.

По сравнению с самыми быстрыми компрессорами эти "средние" упаковщики добавляют форму энтропийного кодирования, то есть они используют преимущество того, что некоторые байты являются более распространенными, чем другие, и (по сути) помещают меньше битов в вывод для более общего байта. ценности.

Если основной проблемой является задержка, а не общее время ЦП, и вы сжимаете один длинный поток, есть инструменты для параллельного сжатия, такие как pigz и -T опция создания потоков для инструмента командной строки zstd. (Существуют также различные экспериментальные упаковщики, но они существуют больше, чтобы раздвинуть границы скорости или плотности, а не для использования сегодня.)

Итак, в общем, у вас есть довольно хороший спектр альтернативных компрессоров для различных приложений: LZ4 (или даже более слабые компрессоры памяти) для сжатия в реальном времени, DEFLATE как старый стандарт для сбалансированного сжатия и Zstd как активно разработанная новая альтернатива, а также brotli и другие для высокой компрессии. По мере того, как вы переходите от LZ4 к DEFLATE, чтобы повысить уровень своих усилий, вы сможете прогнозировать и кодировать данные, а также повышать степень сжатия за счет некоторой скорости.