Рады Вас приветствовать. Прошел почти год с момента публикации последней статьи и мы готовы рассказать, что происходило с самим алгоритмом и как тут замешано дельта-кодирование.
Вступление
После выпуска статьи об улучшениях алгоритма 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.
Развитие получают только те продукты, у которых есть спрос на рынке. Поэтому, будем рады вашим комментариям. Мы также создали телеграм-канал.
Спасибо.
Комментарии (18)
eugene_bb
04.10.2018 00:03Для кодирования изображений, было бы интересно посмотреть, что если иметь базу из множества предгенерированных бэкграундов (проанализировать фотобанк и т.п.) и кодировать только разницу между набором бэкрундов и изображением.
Типа говорим возми бэкраунд #534, со смещением 50 пикселов сверху, прозрачность 0.75 и повернуть на 25 градусов, добавь сверху бэкграунд #1203 со смещением -40 пикселов и поверни на -10 градусов потом вычти что получится из оригинального изображения и что останется закодируй через PNG.
Места сейчас много и можно локально загрузить и хранить например 1GB прегенерированных бэкраундов — например по 320x320 и масштабировать их к требуемому разрешению.
Понятно что процесс сжатия будет не быстым, но скорость декодирования почти что не пострадает.
Интересно будет ли выгода в результате.Deosis
04.10.2018 08:31Вы описали почти копию алгоритма фрактального сжатия.
Вместо фотобанка используется само исходное изображение.
Таким образом, хранится лишь маленький кусочек изображения и набор инструкцию по восстановлению остальной части.
При этом сжатие требует в тысячи раз больше времени, чем распаковка.eugene_bb
04.10.2018 16:34Ну разговор про дельта сжатие, поэтому и интересно как раз с точки зрения того что дельта предзагружается и хранится на клиентской машине.
В принципе такой же способ хранить заранее предгенерированные словари для архивирования многословных форматов, типа HTML, CSS и т.п.
т.е мы анализируем существующие сайты, строим много-много словарей для дельта кодирования, после этого разделяем файл на две части, первая стандартная часть и вторая кастомный контент. К первой применяем один из существующих словарей, а вторую архивируем стандартным способом.
Вопрос в том что будет ли существенная разница или нет.
werklop
04.10.2018 11:45+1Эм… Вы изобрели пегого дудочника?
antoxa950 Автор
04.10.2018 12:11+1Если Вы имеете в виду такой же революционный алгоритм, как и Пегий дудочник из сериала «Кремниевая долина», то я не готов его назвать революционным, но при сравнении с Xdelta3 преимущество у DBroo. А Xdelta3, на сколько мне известно, является одним из лучших в этом направлении.
domix32
04.10.2018 12:31А код-то покажут? Или бинари позапускать-побенчить?
antoxa950 Автор
04.10.2018 14:37Код — нет. На счет бинарей пока не знаю.
domix32
04.10.2018 22:39Так, а в чем профит статьи? Деталей алгоритма нет, кода нет, продукта с алгоритмом тоже. На две статьи сравниваем популярные алгоритмы сжатия со сферическими конями на конкретном железе. «Где ваши доказательства?» как говорится.
Какой план на выпуск это все в поля? На каких условиях хотя бы сильно на вскидку: open source/ freeware или как bpg только open source или только бинарные поставки?
SadOcean
04.10.2018 18:51Дельта кодирование применяется в сжатии видео (целиком запоминаются опорные кадры, а движущееся изображение между ними сохраняется в виде разницы) и аудио (Так как звук представляет физический процесс, он не может изменяться бесконечно быстро/медленно, поэтому хотя дискретизация, условно, может иметь 1024 значения (10 бит), моментальные значения не изменяются сразу на такую величину, поэтому можно хранить не последовательность значений по 10 бит, а последовательность дельт по 8 и эффективнее паковать)
eugenex15
05.10.2018 09:11Как-то это самое дельта-кодирование
Во время спектрумов выдумал (лет минус 25), пытаясь изобрести новый метод сжатия.
Будучи знакомым с литературой Р.Е. Кричевского и алгоритмами адаптивного хафмана и lz.
Но энтропия взяла свое!
maximw
Такое кодирование, возможно, применяется в бекапах, обновлении данных, типа антивирусных баз.