Алгоритм сжатия без потерь Broo и дельта-кодирование, сравнение с Xdelta3. Развитие домашнего проекта

    Рады Вас приветствовать. Прошел почти год с момента публикации последней статьи и мы готовы рассказать, что происходило с самим алгоритмом и как тут замешано дельта-кодирование.


    image


    Вступление


    После выпуска статьи об улучшениях алгоритма Broo, мы столкнулись с преградой в улучшении уровня компрессии и производительности, а именно нельзя было улучшить уровень компрессии не ухудшив скорость распаковки и наоборот. Сразу сделаю оговорку, улучшения были сделаны без ущерба для других характеристик алгоритма, но эти изменения незначительные, дальше мы напишем об этих изменениях. Так вот, после, мы задумались, где мы можем применить накопленную экспертизу и знания в похожем направлении. И выбор пал на дельта-кодирование.


    Что такое дельта-кодирование?


    Дельта-кодирование (англ. Delta encoding) — способ представления данных в виде разницы (дельты) между последовательными данными вместо самих данных.

    На практике, если алгоритмы сжатия позволяют уменьшить размер файла и хранить или пересылать его без каких либо зависимостей от других файлов, то алгоритмы дельта-кодирования позволяют построить патч(разницу) меньшего размера на основе двух файлов (набора данных) и применив патч для файла (набора данных) 1 — получить файл (набора данных) 2.


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


    Если Вы знаете где еще применяется дельта-кодирование, то напишите в комментариях.


    Об изменениях в алгоритме Broo


    Как мы и говорили, их немного:


    • Добавлена поддержка файлов размером 2^64 для x64 и 2^32 для x32.
    • Улучшен коэффициент сжатия.

    Эти изменения все еще находятся на стадии экспериментирования и отладки. Основная проблема — после добавления поддержки больших файлов, на 20% упала скорость распаковки, что для нас недопустимо. Так что поиск решения нами все еще ведется.


    Ниже приведем только одну таблицу сравнений старой версии алгоритма, экспериментальной и некоторые уровни zstd. Файл "xml" из предыдущей статьи.


    Процессор: Intel i7-7700HQ


    Память: DDR4-2400


    Имя алгоритма Скорость упаковки Скорость распаковки Размер сжатого файла, Байт % оторигинала
    memcpy 17460 MB/s 17194 MB/s 5345280 100.00
    zstd 1.3.1 -6 141 MB/s 1311 MB/s 585810 10.96
    broo 1.2 11 MB/s 1905 MB/s 606838 11.35
    zstd 1.3.1 -5 196 MB/s 1207 MB/s 619510 11.59
    zstd 1.3.1 -4 357 MB/s 1214 MB/s 637587 11.93
    zstd 1.3.1 -3 366 MB/s 1220 MB/s 639073 11.96
    broo 1.1 14 MB/s 2005 MB/s 643084 12.03
    zstd 1.3.1 -2 394 MB/s 1108 MB/s 690508 12.92
    zstd 1.3.1 -1 479 MB/s 1213 MB/s 703093 13.15

    Как и множество алгоритмов, скорость работы зависит от процессора, как мы можем видеть в таблице, скорость распаковки более чем в 1.5 раза быстрее чем у zstd первого уровня, на процессоре Intel i7-7700HQ. В то время как на старом Intel i3-550 скорость распаковки была приблизительно равна скорости распаковки zstd, можно посмотреть сравнительные таблицы тут.


    Это говорит о том, что можно выполнить более плотную интеграцию с отдельными процессорами. Зависит от специфики задачи.


    Дельта-кодирование и Broo


    Как вы уже могли догадаться, мы разработали свой алгоритм дельта-кодирования и дали ему название DBroo (Delta Broo).


    Основные характеристики и особенности:


    • Поддержка файлов размером 2^64 для x64 и 2^32 для x32.
    • Работа с бинарными данными.
    • Допускается частичное изменение опорного файла, к которому будет применяться патч.

    Есть готовые решения, такие как diff, bsdiff, xdelta и другие. Была цель найти лучшего (а также доступного) в этом направлении и тягаться с ним. Чисто экспериментальным способом главным конкурентом оказался Xdelta3. Выдает неплохое сжатие и достаточно быструю скорость применения патча. Также Xdelta3 используется для обновлений CyanogenMod (ныне LineageOS).


    Теперь посмотрим на таблицу сравнения DBroo и Xdelta3. В качестве опорного файла используется "xml", а в качестве нового файла тот же но измененный случайным образом.


    Имя алгоритма Скорость создания патча Скорость применения патча Размер патча, байт % от оригинала
    memcpy 18052 MB/s 18665 MB/s 5326823 100.00
    Xdelta3 -9 + lzma 5.40 MB/s 306 MB/s 106542 2.00
    Xdelta3 -6 + lzma 20 MB/s 310 MB/s 121916 2,28
    DBroo 1.0 7.40 MB/s 1600.00 MB/s 123052 2.31
    Xdelta3 -9 7.00 MB/s 688.24 MB/s 179732 3.37
    Xdelta3 -6 36.71 MB/s 694.09 MB/s 201681 3.78
    Xdelta3 -3 59.22 MB/s 637.43 MB/s 237218 4.45
    Xdelta3 -2 72.73 MB/s 582.75 MB/s 279223 5.24
    Xdelta3 -1 81.43 MB/s 540.53 MB/s 478824 8.9

    P. S.


    Развитие получают только те продукты, у которых есть спрос на рынке. Поэтому, будем рады вашим комментариям. Мы также создали телеграм-канал.


    Спасибо.

    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

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

      0
      Такое кодирование, возможно, применяется в бекапах, обновлении данных, типа антивирусных баз.
        0

        Теги Си и С++ зачем? Где код?

          0
          Исправил. Спасибо.
        • НЛО прилетело и опубликовало эту надпись здесь
            0

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

            • НЛО прилетело и опубликовало эту надпись здесь
            +1
            Эм… Вы изобрели пегого дудочника?
              +1
              Если Вы имеете в виду такой же революционный алгоритм, как и Пегий дудочник из сериала «Кремниевая долина», то я не готов его назвать революционным, но при сравнении с Xdelta3 преимущество у DBroo. А Xdelta3, на сколько мне известно, является одним из лучших в этом направлении.
                +1
                Это была просто шутка, исходя из названия)
                  0
                  Тогда да))) Ищем теперь инкубатор)
              +1
              А код-то покажут? Или бинари позапускать-побенчить?
                0
                Код — нет. На счет бинарей пока не знаю.
                  +1
                  Так, а в чем профит статьи? Деталей алгоритма нет, кода нет, продукта с алгоритмом тоже. На две статьи сравниваем популярные алгоритмы сжатия со сферическими конями на конкретном железе. «Где ваши доказательства?» как говорится.
                  Какой план на выпуск это все в поля? На каких условиях хотя бы сильно на вскидку: open source/ freeware или как bpg только open source или только бинарные поставки?
                    0
                    Про лицензию тоже пока не думали, так как думаем что это не конечный результат и еще будет дорабатываться.

                    Профит статьи отобразить прогресс и возможно это может заинтересовать компании которые уже используют похожее или только собираются. Я думаю, что сам алгоритм или продукт на основе него будет ориентирован на рынок b2b.

                    По поводу пруфов, если вам они нужны не только для того, что б убедиться в правдивости информации которую изложили выше, а еще и потому что хотели бы использовать где-то у себя, тогда какие вам нужны доказательства?
                    Говорю сразу, идея и код раскрываться не будут.
                      0
                      Тогда где тэг «Я пиарюсь»?
                        0
                        Т.Е. это абсолютно голословная статья для пира чтобы привлечь покупателей? Тогда почему он не в хабе «Я пиарюсь»?

                        Ведь никаких фактор не предоставлено. Алгоритма нет. Тесты есть только у вас и никто подтвердить и проверить их не может. Если это для того чтобы заинтересовать то отправьте в «я пиарюсь» и тогда все норм
                          0
                          На деле это выглядит просто балабольством. Вы просто пукнули в лужу, извиняюсь. Просто взгляните на ваш текст со стороны, без обид. Вы просто что-то говорите и думаете что все поверят просто так или для чего вы статью тогда кидаете? Или вы считаете что бизнес купит алгоритм по этой статье которая не имеет никаких доказательств?
                        0
                        Это тогда о чем статья? О цифрах? В чем разница между выдуманной статьей?
                          0
                          Ответ выше.
                      0
                      Очень круто!
                        0
                        Дельта кодирование применяется в сжатии видео (целиком запоминаются опорные кадры, а движущееся изображение между ними сохраняется в виде разницы) и аудио (Так как звук представляет физический процесс, он не может изменяться бесконечно быстро/медленно, поэтому хотя дискретизация, условно, может иметь 1024 значения (10 бит), моментальные значения не изменяются сразу на такую величину, поэтому можно хранить не последовательность значений по 10 бит, а последовательность дельт по 8 и эффективнее паковать)
                          0
                          На скорость декодирования как-то такое повлияет?
                            0
                            Я знаком с принципом поверхностно.
                            Чистое дельта-кодирование может быть даже лучше. Чистая выгода — и по памяти и по производительности. Но это возможно только при специфических данных. Условно, звук на 98% можно упаковать дельта кодированием, но 2% содержат пики, которые не влезают в диапазон — для них нужно делать исключения, это уже может быть медленнее, чем воспроизводить поток.
                            Для видео требуются дополнительные операции для построения промежуточных изображений — это наверняка медленнее.
                            Ну и современные форматы применяют не один метод компрессии — достраиваемые картинки скорее всего еще и упакованы каким нибудь частотным алгоритмом с потерей качества и его обработка тоже не дается бесплатно. Сами эти алгоритмы тоже могут использовать дельта-кодирование.
                            Компрессию применяют для сжатия данных (оптимизация по размеру) ценой ухудшения по другим направлениям (больше вычислений от процессора или больше оперативной памяти для промежуточных данных и построения финального распакованного результата) — обычно все имеет цену.

                            Другое дело, что, к примеру, блочная компрессия текстур поддерживается железом на низком уровне — соответственно текстура меньше весит на диске, меньше весит в оперативной и видео памяти, быстрее грузится, а распаковывается прямо при рендере (и эту нагрузку на себя берет видеокарта) — получается выгода на всех этапах.
                              0
                              В первую очередь — спасибо за предыдущий комментарий. Натолкнули на мысли попробовать поработать с аудио и видео.
                              Во вторых, уже успели частично поработать с аудио и видео. По поводу аудио файлов, я пока не вижу применения дельта-кодирования, так как в аудио все идет одним потоком и нет каких то опорных данных которые изменяются с течением времени.
                              Но тем ни менее по текущим наработкам получилось тестовые wav файлы сжать до размера уровня flac, к примеру 30мб wav файла упаковываются в 21мб, что равняются размеру туго же файла упакованным в flac. Но это без использования дельта-кодирования, пока не вижу применения ему в аудио.

                              В видео чуть другая история, есть кадры которые могут выступать опорными и тут уже можно использовать дельта-кодирование. Первые результаты показали сжатие порядка 20% (если мне не изменяет память) от опорного кадра без какой-либо предварительной подготовки данных.
                                0
                                Ну по поводу аудио есть два замечания.
                                Во первых, опорных кадров может и не быть.
                                Например, есть у нас аудио поток в дискретизации 1024 уровней. Мы выставляем первый кадр в 0, либо в реальное значение с дискретизацией 1024.
                                А потом начинаем каждое следующее значение шифровать дельтой на 256 или 128 от предыдущего, пытаясь приблизиться к реальному значению. Иногда будут значения, отличающиеся больше, чем на 256. Они будут чуть сглаживаться (значения 0,1,0,1024,1023,1025,860 превратятся 0,1,0,255,512,768,860) — если это не скажется фатально на качестве звука — вполне рабочий метод.
                                Во вторых, можно использовать как опорные кадры периодические либо пиковые.
                                Например, каждый 1000, либо каждый, у которого уровень отличается больше, чем на 256. Одно из значений, условно ff мы берем на спец символ, с помощью которого кодируем, что этот кадр — опорный, либо этот кадр — пиковый. Он задается честно, значением от 0 до 1024. Собственно это может быть одним и тем же — механизм упаковки выбирает опорные кадры на свое усмотрение, а для распаковщика они выглядят одинаково.
                          0
                          Как-то это самое дельта-кодирование
                          Во время спектрумов выдумал (лет минус 25), пытаясь изобрести новый метод сжатия.
                          Будучи знакомым с литературой Р.Е. Кричевского и алгоритмами адаптивного хафмана и lz.
                          Но энтропия взяла свое!

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

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