antoxa950 30 окт 2017 в 02:02

Broo — алгоритм сжатия без потерь. Улучшения

9 мин

17K

C*C++*Алгоритмы*Программирование*

+17

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

muxa_ru 30 окт 2017 в 03:32

Если это просто архиватор, то причём тут "без потерь" ?

Есть архиваторы у которых есть потери?

Tallefer 30 окт 2017 в 03:49

Это не архиватор, это алгоритм же. :)
Думаю, они для 7зипа сделают плагин, это проще всего, учитывая основу их алгоритма.

Myxach 30 окт 2017 в 09:18

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

RomanArzumanyan 30 окт 2017 в 12:33

Есть алгоритмы сжатия с потерями (например, косинусное преобразование с обрезанием частот и квантованием для изображений). Грубо говоря, JPEG — это архиватор картинок с потерями.

Те алгоритмы, что не привязаны к специфической области, как правило, сжимают без потерь.

Tallefer 30 окт 2017 в 03:33

А плагин для 7зипа будет?

antoxa950 30 окт 2017 в 14:52

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

Kirhgoff 30 окт 2017 в 08:17

«все ящерицы обладают высокой скоростью передвижения» — вообще, хамелеоны очень медленные, по сравнению с обычными ящерицами. И ходят они странненько. Вот тут, например: www.youtube.com/watch?v=qcKsrnr3Z64

igormich88 30 окт 2017 в 12:32

Зато они быстро и эффективно «распаковывают» свой язык. www.youtube.com/watch?v=dm1iHi-38kk

YaMishar 30 окт 2017 в 08:28

Я не понял — с одной стороны ориентированы на скорость сжатия, с другой стороны по скорости проигрывают почти всем и существенно.
К примеру в 8ом тесте имеет 5.8МБ/с при 17-21 у непосредственных соседей по таблице. А zstd показывает вообще запредельные 257 при сравнимом сжатии.
Хотя распаковка быстраяЮ да. То есть этот алгоритм скорее не для пользователей, а производителей контента?

MamontsevDS 30 окт 2017 в 10:10

Так на скорость распаковки же ориентирован алгоритм.

antoxa950 30 окт 2017 в 14:55

Верно. Но и упаковкой мы займемся, пока что, это не самая приоритетная задача.

Godless 30 окт 2017 в 09:07

del

BelBES 30 окт 2017 в 10:39

Хм, несколько лет назад имел дело со сжатием без потерь и на тот момент ТОП'овыми алгоритмами были алгоритмы семейства PAQ… а тут я их в табличке даже не вижу, неужели появилось что-то жмущее принципиально лучше?

antoxa950 30 окт 2017 в 19:15

Не могу сказать, появилось ли что-то принципиально лучше, так как не обладаю данной информацией.
В lzbench было просто интегрировать алгоритм, а так же, список алгоритмов который поддерживает из коробки, нас устраивает, на данный момент.
Если есть пожелание включить в бенч какой-то конкретный алгоритм, то в следующих сравнениях постараемся расширить список участников.

a5b 31 окт 2017 в 18:35

PAQ — лидеры по степени сжатия и часто лидеры по медленности работы, см. правильные таблички и описания в Large Text Compression Benchmark от автора PAQ
http://mattmahoney.net/dc/text.html

Для достижения высокого сжатия PAQ* используют множество моделей и смешивают контексты ("CM") от разных моделей (подробнее — в книге http://mattmahoney.net/dc/dce.html). Все модели работают и при упаковки и при распаковке — скорость работы в обоих случаях близкая. Больше моделей — лучше степень сжатия и медленнее работа. Быстрые методы zpaq (не CM) дают 300-400 нс/байт (~3 МБ/с), CM методы — менее 1 МБ/с http://mattmahoney.net/dc/text.html#1422

Сам тест https://github.com/inikep/lzbench больше нацелен на быстрые алгоритмы, и алгоритмы с быстрой распаковкой (из семейства LZ*), это не соревнование по достижению наивысшей степени сжатия. PAQ (CM) для них видимо слишком медленный.

В таблицах сравнения Broo не хватает "zstd -3" — он жмет несколько лучше, чем "zstd -1", но так же быстр на распаковке (и немного медленнее на упаковке). Если нужна высокая скорость — есть многопоточный вариант pzstd. Если нужна еще большая степень сжатия — у zstd уровни можно изменять до 22 (достаточно универсальный алгоритм), он быстрее и эффективнее классических zlib 1-9: https://raw.githubusercontent.com/facebook/zstd/master/doc/images/Cspeed4.png и https://raw.githubusercontent.com/facebook/zstd/master/doc/images/DCspeed5.png (на таких картинках лучше видны возможности алгоритмов).
Как мне кажется, zstd уже успешно решает задачи, изначально поставленные автором перед Broo: https://habrahabr.ru/post/322978/ "Не привязан к типам файлов, Хороший коэффициент сжатия, Быстрая скорость распаковки", и при этом имеет режимы с высокой скоростью сжатия.

a5b 31 окт 2017 в 18:50

Еще интересный вариант сравнения у автора zstd в блоге — http://fastcompression.blogspot.ru/2015/01/zstd-stronger-compression-algorithm.html
http://fastcompression.blogspot.ru/2011/04/comparing-compressors-new-ranking.html
http://fastcompression.blogspot.ru/p/compression-benchmark.html

Для каналов передачи данных с разной скоростью рассчитывается общее время упаковки, пересылки и распаковки; но график строится не по абсолютной скорости (где плохо видна разница между алгоритмами), а в относительных единицах (100 — самый быстрый алгоритм для данного канала)

Transmission speed ranking:
2011 год http://sd-1.archive-host.com/membres/images/182754578/SpeedRankUpdated.png
zstd: http://2.bp.blogspot.com/-gE8B0wCfox4/VMKJFyaDO4I/AAAAAAAABHU/064aGYoNTBY/s1600/TransRank.png
На быстрых каналах предпочтительнее lz4, медленнее 50-60 МБ/с оптимальным получился zstd.

antoxa950 1 ноя 2017 в 01:10

Про различные уровни у zstd знаем и не однократно прогоняли не только на -3 но и на -22. А так же, не только с zstd. Да, согласен, zstd хорошо с этим справляется, но у нас не стоит задача вытеснуть кого-то из сегмента или применять алгоритм в каких-то конкретных целях. На данный момент стараемся выжать из него все что можно, а потом посмотреть под какие задачи больше всего подходит и будет ли кто-то заинтересован в его использовании.
Спасибо большое за информацию.

Tallefer 2 ноя 2017 в 02:32

Очень хорошо, что гоняли зстд. Найти нишу можно так: подобрать список самых распространенных «бутылочных горлышек», например: скорость передачи — юсб, сата, вайфай — это для, так скажем, домашнего сервера или бэкапов; еще можно разные CDN погонять — это уже вариант самописного клиента, например игрового, где надо быстро патчи разворачивать. Ну в общем, на таких стыках много интересного происходит и не всегда самые популярные оказываются самыми полезными… :)

antoxa950 2 ноя 2017 в 18:38

С нишей будем определяться чуть позже, еще есть чем заниматься и что улучшать.

AaAAxzz 30 окт 2017 в 19:00

А как же Вы бенчмарк запустили? В lzbench нет этого алгоритма, подскажите где найти его?

вывод консоли

>lzbench171 -l



Available compressors for -e option:

all - alias for all available compressors

fast - alias for compressors with compression speed over 100 MB/s (default)

opt - compressors with optimal parsing (slow compression, fast decompression)

lzo / ucl - aliases for all levels of given compressors

blosclz 2015-11-10 [1-9]

brieflz 1.1.0

brotli 2017-03-10 [0-11]

brotli22 2017-03-10 [0-11]

brotli24 2017-03-10 [0-11]

crush 1.0 [0-2]

csc 2016-10-13 [1-5]

density 0.12.5 beta [1-3]