LZ0 - Асимметричный LZ-компрессор с декодером без malloc
Show HN: LZ0 -An asymmetric LZ compressor with ultra minimal, 0-alloc decoder
LZ0 — это экспериментальный формат сжатия и C-библиотека, которые переворачивают привычный баланс: сложность переносится с декодера на энкодер. Декодер не использует динамическую память (malloc), отличается крошечным размером (около 150 строк C или ~40 строк в минимальной версии) и распаковывает данные со скоростью сотни мегабайт в секунду. LZ0 ориентирован на небольшие и средние бинарные файлы и структурированные данные (от сотен килобайт до нескольких мегабайт). Благодаря простому битстриму и отсутствию энтропийного кодирования декодер легко встраивается в загрузчики, микроконтроллеры и ядра ОС. Энкодер использует хеш-цепочки, суффиксный массив SA-IS и разреженный DP, обеспечивая степень сжатия, сравнимую с ZX0, но за секунды вместо минут.
Перенесите сложность с декодера на энкодер — и получите сверхбыструю распаковку без единого malloc.
- nellacross
Хотелось бы увидеть более глубокое сравнение с LZ4. Декодер в стиле LZ4 можно сделать минимальным, а с помощью LZ4HC можно добиться лучшей плотности без потери скорости распаковки.
- aidenn0
Было бы неплохо увидеть бенчмарки против lz4hc -9, поскольку это ближайший конкурент как по скорости сжатия, так и по скорости распаковки.
- seb3773
Я создал LZ0 — асимметричный LZ-компрессор, нацеленный на среды, где ресурсы для распаковки жёстко ограничены (загрузчики, микроконтроллеры, загрузка встроенных ресурсов) или где простота декодера имеет первостепенное значение.
Я всегда восхищался микродекодерами вроде ZX0 Эйнара Саукаса — нулевое динамическое выделение памяти, отсутствие scratch RAM и достаточно компактные, чтобы уместиться в горстку инструкций. Загвоздка с традиционными оптимальными парсерами в том, что они часто масштабируются как O(N^2), занимая десятки секунд или минуты, как только файлы превышают несколько сотен килобайт. Я написал LZ0, чтобы сохранить тот же размер декодера, но сжимать многомегабайтные файлы за миллисекунды.
Где он находится (степень сжатия против скорости): - Плотность сжатия: превосходит LZ4/Snappy, оставаясь в пределах 1–3% от zlib/Deflate и исчерпывающего ZX0. - Скорость распаковки: 200–350 МБ/с для портативного C, 250–700 МБ/с для компактного ASM и 520–1 330 МБ/с для векторного ASM. Это до 10 раз быстрее Deflate при нулевой потребности в куче или таблицах состояний. - Пропускная способность сжатия: ~1,3–1,6 с на типичных входных данных размером 1 МБ.
Как кодировщик обходит стену O(N^2) (конвейер H2C8): - Многоуровневый поиск совпадений: двухуровневые хеш-цепочки для локальных совпадений в паре с O(N) суффиксным массивом SA-IS для глубоких дальних совпадений. - Разреженный DP-парсинг: вместо оценки каждого ребра в графе он группирует битовые затраты Элиаса гамма в математические плато, чтобы пропускать избыточные поиски.
Репозиторий поставляется с тремя реализациями декодера с нулевым выделением памяти: 1. Портативный C (`lz0dec_min.c`): ~75 строк автономного C с z […]