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

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


    Почему название "Broo"?


    image



    Есть род мелких ящериц с названием Brookesia. Как известно, все ящерицы обладают высокой скоростью передвижения, а эти, еще и небольшого размера и, вдобавок, из семейства хамелеонов.


    Мы провели некоторые аналогии:


    • Семейство хамелеонов — не привязаны к типу файлов.
    • Маленький размер — результат сжатия файлов тоже не плох.
    • Быстрая скорость перемещения — тут, конечно, с небольшой оговоркой, что только для скорости распаковки.

    Да и сокращенно получилось прикольное элегантное слово Broo.


    Брукезии (лат. Brookesia) — род ящериц из семейства хамелеонов.

    Мелкие хамелеоны. Один из маленьких видов рода, малая брукезия (Brookesia minima), считается также одной из наиболее мелких ящериц.[1]

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

    Эндемики Мадагаскара и близлежащих мелких островов. Ведут скрытный, преимущественно наземный образ жизни в лесной подстилке.

    Описание изменений


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


    Характеристики ПК


    Процессор DualCore Intel Core i3 550, 3200 MHz
    Память GoodRam 8119 Mb DDR3-1333 DDR3 SDRAM
    ОС Ubuntu 16.10 x64


    Таблицы с замерами


    Для замеров, по прежнему, используем lzbench.


    Тестовые файлы Silesia.


    С кратким описанием тестовых файлов и некоторых алгоритмов которые приводятся в таблицах, можно ознакомиться в предыдущей публикации.


    Напомним лишь о двух:


    Zstandard (Zstd) — алгоритм сжатия данных без потерь, разрабатываемый с 2015 Yann Collet при поддержке Facebook. Cочетает словарный алгоритм сжатия данных типа LZ77 и эффективное энтропийное кодирование типа tANS (FSE — Finite State Entropy), модификацию кода Хаффмана, реализующую нецелое количество бит для хранения символов.

    Brotli — основан на современном варианте алгоритма LZ77, энтропийном кодировании Хаффмана и моделировании контекста 2-го порядка.
    Предназначен для ускорения загрузки веб-страниц, поддерживается в браузерах Chrome, основанных на Chromium и в Firefox.

    Далее, 12 таблиц с замерами каждого файла из пакета silesia. Актуальная версия алгоритма Broo 1.1.


    Тест 1. Коллекция работ Чарльза Диккенса, dickens (txt).
    Имя алгоритма Скорость
    упаковки
    Скорость
    распаковки
    Размер сжатого
    файла, Байт
    % от
    оригинала
    memcpy 4029 MB/s 4034 MB/s 10192446 100.00
    broo 1.1 5.30 MB/s 298 MB/s 3779716 37.08
    lzlib 1.7 -0 7.76 MB/s 34 MB/s 3815335 37.43
    csc 2016-10-13 -1 18 MB/s 31 MB/s 4020916 39.45
    lzma 9.38 -0 13 MB/s 38 MB/s 4044850 39.68
    libdeflate 0.6 -1 85 MB/s 435 MB/s 4231543 41.52
    zstd 1.1.3 -1 143 MB/s 486 MB/s 4279273 41.98
    xpack 2016-06-02 -1 83 MB/s 359 MB/s 4282245 42.01
    brotli 0.5.2 -0 168 MB/s 178 MB/s 4401269 43.18
    zlib 1.2.8 -1 50 MB/s 195 MB/s 4585618 44.99
    broo 1.0 6.03 MB/s 265 MB/s 4750936 46.61
    gipfeli 2016-07-13 178 MB/s 254 MB/s 4955632 48.62
    yalz77 2015-09-19 -1 62 MB/s 304 MB/s 5634109 55.28
    quicklz 1.5.0 -1 250 MB/s 326 MB/s 5831353 57.21
    lzsse2 2016-05-14 -0 18 MB/s 1481 MB/s 5865705 57.55
    yappy 2014-03-22 -0 91 MB/s 1122 MB/s 6141853 60.26
    snappy 1.1.3 179 MB/s 648 MB/s 6337834 62.18
    lz4 1.7.5 264 MB/s 1652 MB/s 6428742 63.07
    lz5 2.0 -10 216 MB/s 1855 MB/s 6431869 63.10

    Тест 2. Tar архив с исполняемыми файлами Mozilla 1.0, mozilla (exe).
    Имя алгоритма Скорость
    упаковки
    Скорость
    распаковки
    Размер сжатого
    файла, Байт
    % от
    оригинала
    memcpy 3986 MB/s 4042 MB/s 51220480 100.00
    csc 2016-10-13 -1 11 MB/s 41 MB/s 15331191 29.93
    lzma 9.38 -0 17 MB/s 43 MB/s 16425272 32.07
    lzlib 1.7 -0 18 MB/s 33 MB/s 16470484 32.16
    xpack 2016-06-02 -1 76 MB/s 368 MB/s 18391874 35.91
    libdeflate 0.6 -1 92 MB/s 396 MB/s 19780124 38.62
    zstd 1.1.3 -1 209 MB/s 542 MB/s 20120459 39.28
    zlib 1.2.8 -1 53 MB/s 209 MB/s 20577226 40.17
    broo 1.1 2.66 MB/s 325 MB/s 20604283 40.23
    brotli 0.5.2 -0 217 MB/s 186 MB/s 21740128 42.44
    broo 1.0 5.11 MB/s 350 MB/s 23177220 45.25
    gipfeli 2016-07-13 236 MB/s 436 MB/s 24380558 47.60
    quicklz 1.5.0 -1 315 MB/s 368 MB/s 24756819 48.33
    yalz77 2015-09-19 -1 49 MB/s 436 MB/s 25454532 49.70
    lzsse2 2016-05-14 -0 13 MB/s 1493 MB/s 25826648 50.42
    lz4 1.7.5 437 MB/s 1876 MB/s 26435667 51.61
    snappy 1.1.3 303 MB/s 1013 MB/s 26461924 51.66
    lz5 2.0 -10 334 MB/s 2097 MB/s 27016242 52.74
    yappy 2014-03-22 -0 107 MB/s 1749 MB/s 27728218 54.14

    Тест 3. Изображение МРТ, mr (image).
    Имя алгоритма Скорость
    упаковки
    Скорость
    распаковки
    Размер сжатого
    файла, Байт
    % от
    оригинала
    memcpy 4010 MB/s 4042 MB/s 9970564 100.00
    lzlib 1.7 -0 20 MB/s 34 MB/s 3130897 31.40
    lzma 9.38 -0 16 MB/s 44 MB/s 3157626 31.67
    csc 2016-10-13 -1 12 MB/s 40 MB/s 3285805 32.96
    xpack 2016-06-02 -1 82 MB/s 323 MB/s 3526828 35.37
    libdeflate 0.6 -1 98 MB/s 428 MB/s 3750985 37.62
    zlib 1.2.8 -1 60 MB/s 227 MB/s 3828366 38.40
    zstd 1.1.3 -1 191 MB/s 637 MB/s 3829231 38.41
    brotli 0.5.2 -0 198 MB/s 185 MB/s 3975643 39.87
    broo 1.1 4.90 MB/s 329 MB/s 4042909 40.55
    gipfeli 2016-07-13 220 MB/s 395 MB/s 4702561 47.16
    broo 1.0 5.94 MB/s 305 MB/s 4741219 47.55
    quicklz 1.5.0 -1 410 MB/s 363 MB/s 4778194 47.92
    lzsse2 2016-05-14 -0 24 MB/s 1523 MB/s 5120289 51.35
    yalz77 2015-09-19 -1 58 MB/s 396 MB/s 5269368 52.85
    snappy 1.1.3 302 MB/s 912 MB/s 5419831 54.36
    lz4 1.7.5 422 MB/s 2024 MB/s 5440937 54.57
    yappy 2014-03-22 -0 108 MB/s 1609 MB/s 6454120 64.73
    lz5 2.0 -10 294 MB/s 2248 MB/s 6978486 69.99

    Тест 4. База химических структур, nci (database).
    Имя алгоритма Скорость
    упаковки
    Скорость
    распаковки
    Размер сжатого
    файла, Байт
    % от
    оригинала
    memcpy 4042 MB/s 4047 MB/s 33553445 100.00
    broo 1.1 8.57 MB/s 982 MB/s 2382623 7.10
    csc 2016-10-13 -1 39 MB/s 156 MB/s 2463773 7.34
    lzma 9.38 -0 43 MB/s 153 MB/s 2777997 8.28
    lzlib 1.7 -0 49 MB/s 103 MB/s 2868761 8.55
    zstd 1.1.3 -1 435 MB/s 915 MB/s 2884530 8.60
    broo 1.0 8.65 MB/s 1000 MB/s 2981970 8.89
    xpack 2016-06-02 -1 180 MB/s 807 MB/s 3838847 11.44
    brotli 0.5.2 -0 539 MB/s 575 MB/s 3984199 11.87
    libdeflate 0.6 -1 180 MB/s 1165 MB/s 4066913 12.12
    zlib 1.2.8 -1 122 MB/s 404 MB/s 4624597 13.78
    yalz77 2015-09-19 -1 197 MB/s 695 MB/s 5050596 15.05
    gipfeli 2016-07-13 529 MB/s 681 MB/s 5063829 15.09
    lz4 1.7.5 765 MB/s 2496 MB/s 5533040 16.49
    lz5 2.0 -10 657 MB/s 2644 MB/s 5545810 16.53
    snappy 1.1.3 560 MB/s 1452 MB/s 6146844 18.32
    quicklz 1.5.0 -1 512 MB/s 799 MB/s 6160636 18.36
    lzsse2 2016-05-14 -0 15 MB/s 2984 MB/s 6339807 18.89
    yappy 2014-03-22 -0 179 MB/s 1941 MB/s 8967562 26.73

    Тест 5. Dll файлы из Open Office.org 1.01, ooffice (exe).
    Имя алгоритма Скорость
    упаковки
    Скорость
    распаковки
    Размер сжатого
    файла, Байт
    % от
    оригинала
    memcpy 4054 MB/s 4102 MB/s 6152192 100.00
    csc 2016-10-13 -1 9.91 MB/s 29 MB/s 2301523 37.41
    lzma 9.38 -0 13 MB/s 31 MB/s 2841578 46.19
    lzlib 1.7 -0 14 MB/s 24 MB/s 2879489 46.80
    xpack 2016-06-02 -1 60 MB/s 342 MB/s 3137960 51.01
    libdeflate 0.6 -1 69 MB/s 286 MB/s 3187434 51.81
    zlib 1.2.8 -1 40 MB/s 151 MB/s 3290532 53.49
    broo 1.1 3.89 MB/s 284 MB/s 3436246 55.08
    brotli 0.5.2 -0 154 MB/s 143 MB/s 3539615 57.53
    zstd 1.1.3 -1 166 MB/s 487 MB/s 3579899 58.19
    broo 1.0 4.93 MB/s 412 MB/s 3757206 61.07
    gipfeli 2016-07-13 163 MB/s 354 MB/s 3922276 63.75
    lzsse2 2016-05-14 -0 15 MB/s 1205 MB/s 3995091 64.94
    quicklz 1.5.0 -1 234 MB/s 264 MB/s 4013859 65.24
    yalz77 2015-09-19 -1 35 MB/s 398 MB/s 4125570 67.06
    yappy 2014-03-22 -0 82 MB/s 1718 MB/s 4235687 68.85
    snappy 1.1.3 222 MB/s 889 MB/s 4271150 69.42
    lz4 1.7.5 337 MB/s 1671 MB/s 4338918 70.53
    lz5 2.0 -10 251 MB/s 1997 MB/s 4370070 71.03

    Тест 6. Пример базы данных MySQL формата из Open Source Database Benchmark, osdb.
    Имя алгоритма Скорость
    упаковки
    Скорость
    распаковки
    Размер сжатого
    файла, Байт
    % от
    оригинала
    memcpy 4095 MB/s 4073 MB/s 10085684 100.00
    csc 2016-10-13 -1 10 MB/s 38 MB/s 3317800 32.90
    lzlib 1.7 -0 19 MB/s 33 MB/s 3345965 33.18
    xpack 2016-06-02 -1 68 MB/s 475 MB/s 3752871 37.21
    zstd 1.1.3 -1 194 MB/s 585 MB/s 3770566 37.39
    broo 1.1 3.33 MB/s 486 MB/s 3862073 38.29
    libdeflate 0.6 -1 90 MB/s 470 MB/s 3896803 38.64
    brotli 0.5.2 -0 214 MB/s 224 MB/s 3910502 38.77
    lzma 9.38 -0 15 MB/s 38 MB/s 3988823 39.55
    zlib 1.2.8 -1 56 MB/s 211 MB/s 4076391 40.42
    broo 1.0 5.40 MB/s 474 MB/s 4147465 41.12
    lzsse2 2016-05-14 -0 12 MB/s 1724 MB/s 4492551 44.54
    gipfeli 2016-07-13 232 MB/s 530 MB/s 4517517 44.79
    yalz77 2015-09-19 -1 51 MB/s 596 MB/s 4570193 45.31
    lz4 1.7.5 359 MB/s 1629 MB/s 5256666 52.12
    lz5 2.0 -10 278 MB/s 1842 MB/s 5286739 52.42
    snappy 1.1.3 303 MB/s 1110 MB/s 5329321 52.84
    quicklz 1.5.0 -1 277 MB/s 330 MB/s 5496443 54.50
    yappy 2014-03-22 -0 70 MB/s 1794 MB/s 7515735 74.52

    Тест 7. Текст книги Chłopi, польского писателя Радислава Реймонта, Polish, reymont (PDF).
    Имя алгоритма Скорость
    упаковки
    Скорость
    распаковки
    Размер сжатого
    файла, Байт
    % от
    оригинала
    memcpy 4123 MB/s 4120 MB/s 6627202 100.00
    broo 1.1 6.90 MB/s 470 MB/s 1840387 27.77
    csc 2016-10-13 -1 15 MB/s 47 MB/s 1872324 28.25
    lzma 9.38 -0 15 MB/s 49 MB/s 1921954 29.00
    lzlib 1.7 -0 22 MB/s 37 MB/s 2082297 31.42
    zstd 1.1.3 -1 157 MB/s 486 MB/s 2167385 32.70
    libdeflate 0.6 -1 100 MB/s 512 MB/s 2206932 33.30
    xpack 2016-06-02 -1 97 MB/s 389 MB/s 2279716 34.40
    broo 1.0 5.10 MB/s 423 MB/s 2289019 34.54
    brotli 0.5.2 -0 212 MB/s 226 MB/s 2360732 35.62
    zlib 1.2.8 -1 59 MB/s 213 MB/s 2376430 35.86
    gipfeli 2016-07-13 222 MB/s 318 MB/s 2644916 39.91
    quicklz 1.5.0 -1 284 MB/s 399 MB/s 3003825 45.33
    yalz77 2015-09-19 -1 76 MB/s 347 MB/s 3017083 45.53
    lzsse2 2016-05-14 -0 16 MB/s 1735 MB/s 3039392 45.86
    yappy 2014-03-22 -0 119 MB/s 1252 MB/s 3161344 47.70
    lz4 1.7.5 303 MB/s 1611 MB/s 3181387 48.00
    lz5 2.0 -10 265 MB/s 1626 MB/s 3184901 48.06
    snappy 1.1.3 208 MB/s 729 MB/s 3233787 48.80

    Тест 8. Tar архив исходников Samba 2-2.3, samba (src).
    Имя алгоритма Скорость
    упаковки
    Скорость
    распаковки
    Размер сжатого
    файла, Байт
    % от
    оригинала
    memcpy 4048 MB/s 4033 MB/s 21606400 100.00
    csc 2016-10-13 -1 17 MB/s 60 MB/s 4407241 20.40
    broo 1.1 5.80 MB/s 652 MB/s 5137035 23.78
    lzlib 1.7 -0 26 MB/s 46 MB/s 5178819 23.97
    lzma 9.38 -0 21 MB/s 59 MB/s 5338935 24.71
    zstd 1.1.3 -1 257 MB/s 715 MB/s 5550637 25.69
    xpack 2016-06-02 -1 107 MB/s 568 MB/s 5669295 26.24
    libdeflate 0.6 -1 113 MB/s 615 MB/s 5922973 27.41
    brotli 0.5.2 -0 304 MB/s 285 MB/s 6084327 28.16
    broo 1.0 6.90 MB/s 650 MB/s 6186042 28.63
    zlib 1.2.8 -1 73 MB/s 276 MB/s 6329455 29.29
    gipfeli 2016-07-13 323 MB/s 426 MB/s 6810623 31.52
    yalz77 2015-09-19 -1 81 MB/s 512 MB/s 7098899 32.86
    quicklz 1.5.0 -1 366 MB/s 497 MB/s 7309452 33.83
    lzsse2 2016-05-14 -0 14 MB/s 2144 MB/s 7395737 34.23
    lz4 1.7.5 486 MB/s 2035 MB/s 7716839 35.72
    lz5 2.0 -10 398 MB/s 2246 MB/s 7927178 36.69
    snappy 1.1.3 353 MB/s 1089 MB/s 8008774 37.07
    yappy 2014-03-22 -0 123 MB/s 1769 MB/s 9183273 42.50

    Тест 9. Звездный каталог Смитсоновской астрофизической обсерватории, sao (bin).
    Имя алгоритма Скорость
    упаковки
    Скорость
    распаковки
    Размер сжатого
    файла, Байт
    % от
    оригинала
    memcpy 4096 MB/s 4114 MB/s 7251944 100.00
    lzma 9.38 -0 9.47 MB/s 22 MB/s 4923529 67.89
    lzlib 1.7 -0 10 MB/s 16 MB/s 5005573 69.02
    csc 2016-10-13 -1 5.69 MB/s 17 MB/s 5082846 70.09
    xpack 2016-06-02 -1 47 MB/s 312 MB/s 5259606 72.53
    libdeflate 0.6 -1 60 MB/s 258 MB/s 5494268 75.76
    zlib 1.2.8 -1 31 MB/s 158 MB/s 5567774 76.78
    broo 1.1 2.18 MB/s 365 MB/s 5715783 78.82
    brotli 0.5.2 -0 130 MB/s 120 MB/s 6019841 83.01
    gipfeli 2016-07-13 146 MB/s 422 MB/s 6043361 83.33
    broo 1.0 3.55 MB/s 496 MB/s 6086118 83.92
    yappy 2014-03-22 -0 68 MB/s 1709 MB/s 6201752 85.52
    zstd 1.1.3 -1 145 MB/s 483 MB/s 6254282 86.24
    yalz77 2015-09-19 -1 26 MB/s 576 MB/s 6299030 86.86
    snappy 1.1.3 212 MB/s 969 MB/s 6435266 88.74
    quicklz 1.5.0 -1 229 MB/s 222 MB/s 6498301 89.61
    lzsse2 2016-05-14 -0 15 MB/s 941 MB/s 6710542 92.53
    lz4 1.7.5 337 MB/s 2161 MB/s 6790273 93.63
    lz5 2.0 -10 236 MB/s 2501 MB/s 6792720 93.67

    Тест 10. Американский словарь английского языка Уэбстера, webster (html).
    Имя алгоритма Скорость
    упаковки
    Скорость
    распаковки
    Размер сжатого
    файла, Байт
    % от
    оригинала
    memcpy 3970 MB/s 4008 MB/s 41458703 100.00
    csc 2016-10-13 -1 13 MB/s 44 MB/s 10360155 24.99
    broo 1.1 4.83 MB/s 288 MB/s 11076158 26.72
    lzma 9.38 -0 17 MB/s 47 MB/s 12704878 30.64
    lzlib 1.7 -0 22 MB/s 38 MB/s 12727596 30.70
    zstd 1.1.3 -1 169 MB/s 531 MB/s 13738284 33.14
    libdeflate 0.6 -1 99 MB/s 524 MB/s 13839192 33.38
    broo 1.0 5.42 MB/s 266 MB/s 13854195 33.42
    xpack 2016-06-02 -1 94 MB/s 441 MB/s 14006907 33.79
    brotli 0.5.2 -0 187 MB/s 207 MB/s 14559007 35.12
    zlib 1.2.8 -1 60 MB/s 211 MB/s 14991242 36.16
    gipfeli 2016-07-13 209 MB/s 281 MB/s 16152312 38.96
    lzsse2 2016-05-14 -0 14 MB/s 1897 MB/s 17459517 42.11
    quicklz 1.5.0 -1 276 MB/s 369 MB/s 18315816 44.18
    yalz77 2015-09-19 -1 62 MB/s 315 MB/s 18435248 44.47
    yappy 2014-03-22 -0 107 MB/s 1378 MB/s 19899610 48.00
    lz4 1.7.5 317 MB/s 1593 MB/s 20139988 48.58
    lz5 2.0 -10 260 MB/s 1790 MB/s 20153547 48.61
    snappy 1.1.3 214 MB/s 765 MB/s 20206466 48.74

    Тест 11. Коллекция xml файлов, xml.
    Имя алгоритма Скорость
    упаковки
    Скорость
    распаковки
    Размер сжатого
    файла, Байт
    % от
    оригинала
    memcpy 4118 MB/s 4113 MB/s 5345280 100.00
    csc 2016-10-13 -1 27 MB/s 99 MB/s 606763 11.35
    broo 1.1 9.33 MB/s 1260 MB/s 644416 12.06
    lzma 9.38 -0 34 MB/s 108 MB/s 691236 12.93
    zstd 1.1.3 -1 363 MB/s 887 MB/s 703151 13.15
    lzlib 1.7 -0 39 MB/s 73 MB/s 741537 13.87
    broo 1.0 7.91 MB/s 1277 MB/s 800526 14.98
    brotli 0.5.2 -0 409 MB/s 451 MB/s 905757 16.94
    libdeflate 0.6 -1 143 MB/s 856 MB/s 940409 17.59
    zlib 1.2.8 -1 104 MB/s 344 MB/s 965248 18.06
    xpack 2016-06-02 -1 137 MB/s 634 MB/s 1000008 18.71
    yalz77 2015-09-19 -1 157 MB/s 666 MB/s 1067378 19.97
    gipfeli 2016-07-13 406 MB/s 527 MB/s 1100536 20.59
    quicklz 1.5.0 -1 452 MB/s 712 MB/s 1124708 21.04
    lzsse2 2016-05-14 -0 18 MB/s 2870 MB/s 1201125 22.47
    lz4 1.7.5 617 MB/s 1991 MB/s 1227495 22.96
    lz5 2.0 -10 524 MB/s 2231 MB/s 1240098 23.20
    snappy 1.1.3 414 MB/s 1196 MB/s 1308374 24.48
    yappy 2014-03-22 -0 155 MB/s 1915 MB/s 1605459 30.04

    Тест 12. Рентген изображение, x-ray (image).
    Имя алгоритма Скорость
    упаковки
    Скорость
    распаковки
    Размер сжатого
    файла, Байт
    % от
    оригинала
    memcpy 4023 MB/s 4106 MB/s 8474240 100.00
    csc 2016-10-13 -1 16 MB/s 21 MB/s 4049630 47.79
    lzlib 1.7 -0 9.85 MB/s 18 MB/s 5079274 59.94
    lzma 9.38 -0 10 MB/s 23 MB/s 5198894 61.35
    xpack 2016-06-02 -1 48 MB/s 243 MB/s 5863367 69.19
    libdeflate 0.6 -1 63 MB/s 267 MB/s 5999750 70.80
    zlib 1.2.8 -1 35 MB/s 145 MB/s 6033932 71.20
    brotli 0.5.2 -0 139 MB/s 121 MB/s 6600523 77.89
    zstd 1.1.3 -1 419 MB/s 569 MB/s 6772286 79.92
    broo 1.1 3.01 MB/s 215 MB/s 6984539 82.42
    lzsse2 2016-05-14 -0 17 MB/s 883 MB/s 7292876 86.06
    quicklz 1.5.0 -1 264 MB/s 219 MB/s 7440632 87.80
    gipfeli 2016-07-13 165 MB/s 486 MB/s 7641391 90.17
    broo 1.0 3.47 MB/s 487 MB/s 7702715 90.90
    yalz77 2015-09-19 -1 23 MB/s 491 MB/s 7933653 93.62
    snappy 1.1.3 446 MB/s 1869 MB/s 8209180 96.87
    yappy 2014-03-22 -0 59 MB/s 3200 MB/s 8328582 98.28
    lz4 1.7.5 852 MB/s 3457 MB/s 8390195 99.01
    lz5 2.0 -10 540 MB/s 4126 MB/s 8459685 99.83

    Полное сжатие Silesia.tar только с версией алгоритма Broo 1.1


    Имя алгоритма Скорость
    упаковки
    Скорость
    распаковки
    Размер сжатого
    файла, Байт
    % от
    оригинала
    memcpy 3743 MB/s 3816 MB/s 211948032 100.00
    csc 2016-10-13 -1 12 MB/s 45 MB/s 56171784 26.50
    lzlib 1.8 -0 21 MB/s 37 MB/s 63636337 30.02
    lzma 16.04 -0 17 MB/s 48 MB/s 64013817 30.20
    broo 1.1 2.10 MB/s 365 MB/s 69519802 32.80
    xpack 2016-06-02 -1 88 MB/s 434 MB/s 71073622 33.53
    libdeflate 0.7 -1 97 MB/s 494 MB/s 73319124 34.59
    zstd 1.3.1 -1 228 MB/s 591 MB/s 73640138 34.74
    zlib 1.2.11 -1 61 MB/s 228 MB/s 77251098 36.45
    brotli 2017-03-10 -0 222 MB/s 215 MB/s 78397963 36.99
    gipfeli 2016-07-13 239 MB/s 408 MB/s 87937356 41.49
    yalz77 2015-09-19 -1 62 MB/s 304 MB/s 93949225 44.33
    quicklz 1.5.0 -1 319 MB/s 391 MB/s 94732260 44.70
    lzsse2 2016-05-14 -0 0.85 MB/s 1700 MB/s 94740049 44.70
    lz4 1.7.5 139 MB/s 1885 MB/s 100881408 47.60
    snappy 1.1.4 332 MB/s 997 MB/s 102295610 48.26
    yappy 2014-03-22 -0 108 MB/s 1626 MB/s 109428074 51.63
    Поделиться публикацией

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

      +1

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


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

        0
        Это не архиватор, это алгоритм же. :)
        Думаю, они для 7зипа сделают плагин, это проще всего, учитывая основу их алгоритма.
          0
          Судя по сравнению, для архивов лучше использовать lzlib или csc, а это больше для сжатие данных, что бы потом им распаковывать и открывать каждый раз при запуске программы, как я понял.
            0
            Есть алгоритмы сжатия с потерями (например, косинусное преобразование с обрезанием частот и квантованием для изображений). Грубо говоря, JPEG — это архиватор картинок с потерями.

            Те алгоритмы, что не привязаны к специфической области, как правило, сжимают без потерь.
            0
            А плагин для 7зипа будет?
              0
              Скорее всего, но когда, не могу сказать. Сейчас состояние такое, что код упаковки практически не трогали, а выжимать из него есть что. Как только решим более приоритетные задачи, скорее всего займемся плагином.
              +1
              «все ящерицы обладают высокой скоростью передвижения» — вообще, хамелеоны очень медленные, по сравнению с обычными ящерицами. И ходят они странненько. Вот тут, например: www.youtube.com/watch?v=qcKsrnr3Z64
              0
              Я не понял — с одной стороны ориентированы на скорость сжатия, с другой стороны по скорости проигрывают почти всем и существенно.
              К примеру в 8ом тесте имеет 5.8МБ/с при 17-21 у непосредственных соседей по таблице. А zstd показывает вообще запредельные 257 при сравнимом сжатии.
              Хотя распаковка быстраяЮ да. То есть этот алгоритм скорее не для пользователей, а производителей контента?
                0
                Так на скорость распаковки же ориентирован алгоритм.
                  0
                  Верно. Но и упаковкой мы займемся, пока что, это не самая приоритетная задача.
                0
                del
                  +4

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

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

                      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/ "Не привязан к типам файлов, Хороший коэффициент сжатия, Быстрая скорость распаковки", и при этом имеет режимы с высокой скоростью сжатия.

                        0

                        Еще интересный вариант сравнения у автора 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.

                          0
                          Про различные уровни у zstd знаем и не однократно прогоняли не только на -3 но и на -22. А так же, не только с zstd. Да, согласен, zstd хорошо с этим справляется, но у нас не стоит задача вытеснуть кого-то из сегмента или применять алгоритм в каких-то конкретных целях. На данный момент стараемся выжать из него все что можно, а потом посмотреть под какие задачи больше всего подходит и будет ли кто-то заинтересован в его использовании.
                          Спасибо большое за информацию.
                            0
                            Очень хорошо, что гоняли зстд. Найти нишу можно так: подобрать список самых распространенных «бутылочных горлышек», например: скорость передачи — юсб, сата, вайфай — это для, так скажем, домашнего сервера или бэкапов; еще можно разные CDN погонять — это уже вариант самописного клиента, например игрового, где надо быстро патчи разворачивать. Ну в общем, на таких стыках много интересного происходит и не всегда самые популярные оказываются самыми полезными… :)
                              0
                              С нишей будем определяться чуть позже, еще есть чем заниматься и что улучшать.
                        0
                        А как же Вы бенчмарк запустили? В 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]

                          0
                          Сделали приватную копию репозитория lzbench и туда интегрировали. В публичном доступе, на данный момент, нет.
                          0
                          А почему такая низкая скорость сжатия Silesia.tar? Ведь отдельно по тестам скорость везде выше 2.10 MB/s
                            0
                            Из-за большего размера файла.

                          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                          Самое читаемое