Я понимаю алгоритмы LZ77 и LZ78. Я читал о LZ4 здесь и здесь и нашел код для него.
Эти ссылки описывают формат блока LZ4. Но было бы здорово, если бы кто-нибудь мог объяснить (или направить меня на объяснение некоторых ресурсов):
LZ4 построен для быстрого сжатия, например, более 400 МБ/с на ядро. Это подходит для приложений, где вы хотите, чтобы сжатие было очень дешевым: например, вы пытаетесь сделать компакт-диск в сети или на диске более компактным, но не можете позволить себе потратить кучу времени процессора на сжатие. Это в семье с, например, snappy и LZO. Эти алгоритмы отличаются от популярного DEFLATE, потому что:
Для сравнения, DEFLATE получает лучшее сжатие, но сжимает и распаковывает медленнее, а алгоритмы с высоким сжатием, такие как LZMA, bzip2, LZHAM, или brotli имеют тенденцию занимать еще больше времени (хотя Brotli с более быстрыми настройками может конкурировать с zlib). Там много вариаций среди алгоритмов с высоким сжатием, но в целом они стремятся захватить избыточность на большие расстояния, использовать больше преимуществ контекста, чтобы определить, какие байты вероятны, и использовать более компактные, но более медленные способы выражения своих результатов в битах.
LZ4HC - это вариант с высоким сжатием LZ4, который, я считаю, меняет точку 1 выше - компрессор пытается найти все повторения и выбрать "лучший", чтобы обеспечить малый выходной сигнал. Это улучшает коэффициент сжатия, но снижает скорость сжатия по сравнению с LZ4. Скорость декомпрессии не повреждена, поэтому, если вы сжимаете один раз и разжимаете много раз и в основном хотите очень дешевую декомпрессию, LZ4HC имеет смысл.
Обратите внимание, что даже быстрый компрессор может не позволять одному ядру насыщать большую пропускную способность, как это обеспечивается SSD или быстрыми каналами в центре обработки данных. Есть еще более быстрые компрессоры с более низкими коэффициентами, иногда используемые для временно упаковывать данные в ОЗУ. WKdm и Density - два таких компрессоры, а иногда и специализированное оборудование может добиться очень быстрого сжатия, например, чипы Samsung Exynos или Технология Intel QuickAssist.
Если вам интересно сжать больше, чем LZ4, но с меньшим количеством процессорного времени, чем спуск, автор LZ4 (Yann Collet) написал библиотеку под названием Zstd; на своем стабильном выпуске Facebook опубликовал информацию о том, как они его используют. Он использует конечные автоматы, а не коды Хаффмана, для энтропийного кодирования; Хотел бы я сказать больше о деталях, но сначала я должен был прочитать, чтобы узнать о них. Apple написала lzfse на тех же принципах. Несколько лет назад Google опубликовала библиотеку под названием gipfeli, хотя она, похоже, не сильно тянула. Существуют также проекты, направленные на ускорение сжатия в формате Zlib, например SLZ и для zlib от CloudFlare и Intel.
По сравнению с самыми быстрыми компрессорами эти "средние" упаковщики добавляют форму энтропийного кодирования, то есть они используют преимущества того, как некоторые байты более распространены, чем другие, и (по сути) помещают меньшее количество бит в результат для более общие байтовые значения.
Если ваша проблема связана с задержкой, а не общим временем процессора, и вы сжимаете один длинный поток, есть инструменты для параллельного сжатия, например pigz и pzstd. (Есть различные экспериментальные упаковщики там тоже, но они существуют больше, чтобы продвигать границы по скорости или плотности, а не для использования сегодня.)
Итак, у вас есть довольно хороший спектр альтернативных компрессоров для разных приложений: LZ4 (или даже более слабые компрессоры памяти) для сжатия в реальном времени, DEFLATE - как старый стандарт для сбалансированного сжатия, а Zstd и lzfse - как новые альтернативы, и brotli и другие для высокого сжатия. Когда вы переходите с LZ4 через DEFLATE, чтобы бродить, вы накладываете больше усилий для прогнозирования и кодирования данных и получения большего сжатия из-за некоторой скорости.