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

Question

Я понимаю алгоритмы LZ77 и LZ78. Я прочитал о LZ4 here и here и нашел code for it.

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

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

Answer 1

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

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

сравнения, DEFLATE получает лучшее сжатие, но сжимает и разжимает медленнее, и алгоритмы с высокой степенью сжатия, как LZMA, bzip2, LZHAM или brotli стремятся занять еще больше времени (хотя Brotli at its faster settings can compete with zlib). Существует множество вариаций среди алгоритмов с высоким сжатием, но в широком смысле они склонны захватывать избыточность на большие расстояния, более эффективно использовать контекст, чтобы определить, какие байты вероятны, и использовать более компактные, но более медленные способы выражения своих результатов в битах.

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

Обратите внимание, что даже быстрый компрессор может не позволять одному сердечнику насыщать большую полосу пропускания, такую ​​как SSD или быстрые каналы в центре обработки данных. Есть еще более быстрые компрессоры с более низкими коэффициентами, иногда используемые для temporarily pack data in RAM. WKdm и Density являются двумя такими компрессорами, и иногда специализированное оборудование может обеспечить очень быстрое сжатие, например, в Samsung's Exynos chips или Intel's QuickAssist technology.

Если вы заинтересованы в сжатии более LZ4, но с меньшим процессорным временем, чем спуск, автор LZ4 (Yann Collet) написал библиотеку под названием Zstd; при его стабильном выпуске, Facebook posted about how they use it. Он использует finite state machines, а не коды Хаффмана, для энтропийного кодирования; Хотел бы я сказать больше о деталях, но сначала я должен был прочитать, чтобы узнать о них. Apple написала lzfse на тех же принципах. Несколько лет назад Google опубликовала библиотеку под названием gipfeli, хотя она, похоже, не очень сильно тянула. Существуют также проекты, направленные на более быстрое сжатие в формате Zlib, например SLZ и patches to zlib by CloudFlare and Intel.

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

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

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