bzip3: новый архиватор, который сжимает все версии Perl5 до 546 МБ

Недавно я обрабатывал сжатые .jsonl файлы (формат JSON lines). Я обнаружил, что lzma дает гораздо лучшее сжатие, чем gzip или bzip2, что помогает с затратами на архивирование, но с ним сложно работать, так как поддержка со стороны программного обеспечения недостаточна. Я использую duckdb, который прозрачно поддерживает gzip. Существует расширение для bzip2, но не для lzma или bzip3.

В итоге я использовал gzip, потому что он лучше всего поддерживается используемым мной ПО и, скорее всего, будет поддерживаться в ПО, которое я приму в будущем. Но он дал худшие результаты сжатия из всех опробованных вариантов. Эти цифры по bzip3 определенно вызывают у меня FOMO...

Бенчмарки нечестные, до такой степени, что выглядят подтасованными. Размер блока для bzip3 установлен в 512 МБ, а размер окна для zstd оставлен по умолчанию (8 МБ, насколько я знаю, для высоких уровней). Таким образом, в этом корпусе, который состоит из всех версий исходного кода Perl, объединенных вместе, окно слишком мало, чтобы увидеть все идентичные файлы и просто сопоставить их.

Кроме того, корпуса, состоящие из очень длинных повторений, — это почти лучший сценарий для компрессоров на основе BWT.

Если мы сопоставим размер окна zstd с размером окна bzip3, мы получим радикально другие результаты:

% gzcat *.gz | time zstd -T8 -16 | wc -c # базовый уровень

2819113884

zstd -T8 -16 2054.50s user 3.47s system 783% cpu 4:22.80 total

% gzcat *.gz | time zstd -T8 -16 --long=29 | wc -c

196405076

zstd -T8 -16 --long=29 1083.06s user 2.41s system 783% cpu 2:18.55 total

Почти в 15 раз меньше, чем базовый уровень, и более чем в 2 раза меньше, чем bzip3, а время CPU сокращается вдвое (поскольку длинные совпадения находятся раньше, работы меньше).

(Базовое число немного отличается, потому что у меня нет точного набора версий Perl, использованного автором)

Кроме того, в тестах с использованием lrzip, где размер окна становится менее важным, zstd вообще не сравнивается.

Интересный непреднамеренный тест — зайти на https://github.com/iczelia/bzip3/releases и посмотреть, насколько bzip3 сжимает свои собственные релизные архивы; и зайти на https://github.com/iczelia/bzip3/blob/master/.github/workflo... чтобы увидеть, какие параметры были выбраны для других компрессоров.

Я думаю, что сюда следует включить тесты zstd с большими окнами и режимом длинных дистанций. Я не удивлюсь, если используемое окно меньше, чем отдельный tar-файл версии, что препятствует полезному сжатию.

> Однако сложность алгоритмов и, в частности, наличие различных особых случаев в коде, которые возникают с очень низкой, но ненулевой вероятностью, не позволяют исключить возможность наличия ошибок в программе.

Похоже, это хороший тестовый пример для формализации + ИИ?

Я думаю, что алгоритмы сжатия созрели для значительного улучшения с помощью LLM. Это идеальная задача для замкнутого цикла оценки, и можно просто позволить агенту пробовать разные варианты.

Неприятно использовать такое имя, когда оно не создано авторами bzip. По какой-то причине разработчики открытого ПО любят использовать имена, которые могут нарушать товарные знаки, вместо того чтобы придумать что-то уникальное.