Comments 22
Посмотрел на тесты. Если сравнивать с zstd 1.1.3 -1, то broo как-то не впечатляет. zstd лучше по всем показателям в большинстве тестов (9 из 12). В почем подвох?
Тест 4. База химических структур, database
У zstd немного меньше скорости распаковки (915MB/s против 1000 Mb/s).
Тест 9. Звездный каталог Смитсоновской астрофизической обсерватории, bin
У zstd немного меньше скорость распаковки (483 MB/s против 496 MB/s) и коэффециент сжатия (86.24% против 83.92%).
- Тест 11. Коллекция xml файлов, xml
У zstd меньше скорость распаковки (887 MB/s против 1277 MB/s)
В качестве интересного факта могу привести сравнение которое не попало в публикацию. Запустил через lzbench на упаковку wav файл для zstd и broo, получил такие результаты:
Compr. name Compress. Decompress. Compr. size Ratio
zstd 667 MB/s 1434 MB/s 38199106 97.83
broo 1.84 MB/s 3334 MB/s 38652661 98.99
Как на мой взгляд 1% разницы в степени сжатия не должен был критично повлиять на скорость распаковки, по этому это показывает некоторые плюсы алгоритма.
По поводу названия, с Вашего позволения я б раскрыл этот вопрос в следующей публикации, но это не критично по этому если все же есть сильное желание узнать, могу ответить в следующем комментарии.
Спасибо за комментарий.
П.С. Алгоритм является увлечением которым занимаемся в свободное время и не позиционируем как ярым конкурентом какому либо из перечисленных алгоритмов, получили интересные показатели и возникла идея поделиться. Фактически, его основная цель это находить всю возможную избыточность и упаковывать, другими словами задача была разбита на 2 этапа, свой алгоритм поиска избыточности и свой вариант оптимальной упаковки.
И, кстати, результаты бенчмарков тоже нужно как-то проанализовать: 12 сравнений с десятком алгоритмов по четырём параметрам — крайне трудно интерпретируемый объём данных.
tANS (FSE — Finite State Entropy), модификацию кода Хаффмана, реализующую нецелое количество бит для хранения символов.
Про алгоритмическое сжатие — знаю, а вот Хаффмана с нецелым количеством бит не представляю, раскройте тему.
Compression
Жалко, что это дело забросили.
Есть современные сравнения архиваторов:
http://mattmahoney.net/dc/text.html "Large Text Compression Benchmark" (2016) — … first 10^9 bytes of the XML text dump of the English version of Wikipedia on Mar. 3, 2006. (рекорд за cmix — https://github.com/byronknoll/cmix = http://www.byronknoll.com/cmix.html — 128-121 МБ на 1 ГБ дампа, но оочень низкая скорость как упаковки так и распаковки)
https://github.com/powturbo/TurboBench (сравнивается ряд быстрых алгоритмов)
https://quixdb.github.io/squash-benchmark/ (2015, Squash Compression Benchmark, 28 наборов, 46 вариантов 29 алгоритмов, несколько машин: x86_64 / arm)
У Matt Mahoney в разделе сжатия данных http://mattmahoney.net/dc/ есть много интересных материалов: книга http://mattmahoney.net/dc/dce.html Data Compression Explained (2013), http://mattmahoney.net/dc/calgary.html Calgary Compression Challenge (2010, уже 580170 байт, PPMd; 551 кб у cmix), собственный архиватор ZPAQ http://mattmahoney.net/dc/zpaq.html (2016, 643 кб на Calgary), http://mattmahoney.net/dc/barf.html — рекурсивный архиватор, сжимающий все (размер данных внутри выходного файла всегда меньше чем у входного; используется 257 методов!)
Обсуждения архиваторов продолжаются на http://encode.ru/ при участии нескольких авторов архиваторов.
Практически всю работу по статистике на себя берет lzbench, единственное что мы могли корректировать это кол-во итерация для каждого алгоритма по результатам которых выбирается лучший результат. Но так же не надо забывать, что показатели зависят и от самой ОС (перед тестами позаботился, что б ничего лишнего не было запущено).
По скорости упаковки с Вами согласен, по возможности будем думать над решением.
На данный момент вся заметка из категории
"Мы разработали очень секретный пистолет, но мы Вам его не покажем, зато он пробивает ледокол. Вдоль. Иногда."
Рождение нового алгоритма по имени Broo и сравнение с Brotli и остальными