Как стать автором
Обновить

Комментарии 22

Mozilla — это кодовое название продукта, впоследствии названного Netspace Navigator.
Не стоит хвастаться знанием истории, когда вы сами её не знаете, да? Я так понимаю речь таки шла об браузере именно с названием Mozilla. Вот тут лежит, если вам интересно. Там, правда этих «исполняемых файлов» — десятки, было бы неплохо знать о каком из них речь…

Посмотрел на тесты. Если сравнивать с 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)
Никакого подвоха нет, так как данный алгоритм (broo) относительно молод, если грубо то 3-4 недели и это буквально самые первые результаты. К примеру на данный момент уже улучшили коэффициент сжатия, правда пока с некоторыми потерями в скорости распаковки, но в дальнейшем это будет исправлено и даже возможно ускорено.
А в чём суть предлагаемого алгоритма? Что нового? Почему называется broo?
В статье указал, что «Не используются энтропийное сжатие и словарные методы», к сожалению пока из-за некоторых соображений не могу раскрыть основную техническую идею, возможно в следующих публикациях этот вопрос будет раскрыт.
В качестве интересного факта могу привести сравнение которое не попало в публикацию. Запустил через 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), модификацию кода Хаффмана, реализующую нецелое количество бит для хранения символов.

Про алгоритмическое сжатие — знаю, а вот Хаффмана с нецелым количеством бит не представляю, раскройте тему.
Сам пока в полной мере не разбирался, но для ознакомления можете воспользоваться данной ссылкой.
Когда-то регулярно проводились сравнения архиваторов в Ru.Compress, а потом ещё был сайт:
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/ при участии нескольких авторов архиваторов.

НЛО прилетело и опубликовало эту надпись здесь
В сравнении нет zopfli так как он не поддерживается в lzbench, надо прикручивать ручками, возможно в следующий раз это будет учтено и добавлено.
Практически всю работу по статистике на себя берет lzbench, единственное что мы могли корректировать это кол-во итерация для каждого алгоритма по результатам которых выбирается лучший результат. Но так же не надо забывать, что показатели зависят и от самой ОС (перед тестами позаботился, что б ничего лишнего не было запущено).
По скорости упаковки с Вами согласен, по возможности будем думать над решением.

На данный момент вся заметка из категории
"Мы разработали очень секретный пистолет, но мы Вам его не покажем, зато он пробивает ледокол. Вдоль. Иногда."

Вас на разработку сериал Silicon Valley вдохновил? :)
Вдохновила интересная задача, но и сериал видел)
Что еще можно комбинировать и упаковывать кроме битов, когда вид данных не важен? Неужели суть алгоритма в минимизации логических функций?
Только биты. Нет.
Жаль. Задача интересная.
Работа с битами сама по себе интересная, есть некоторые наработки по анализу бит на разные зависимости, на основе чего был написан один тестовый алгоритм сжатия, который был скрещен с кодированием Хаффмана и при сжатии текста давал стабильный коэффициент сжатия в около 1.6-1.7, но это больше развлечение. Для такого сжатия текста много не надо.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий

Публикации

Истории