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

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

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

С логической точки зрения разница между двумя значениями данных — это информация, необходимая для получения одного значения из другого — см. относительную энтропию . Разницу между одинаковыми значениями (при некоторой эквивалентности ) часто называют 0 или нейтральным элементом.

Простой пример [ править ]

Возможно, самым простым примером является сохранение значений байтов как разностей (дельт) между последовательными значениями, а не самих значений. Итак, вместо 2, 4, 6, 9, 7 мы будем хранить 2, 2, 2, 3, −2. Это уменьшает дисперсию (диапазон) значений, когда соседние выборки коррелируют, позволяя использовать меньше битов для одних и тех же данных. Звуковой формат IFF 8SVX применяет это кодирование к необработанным звуковым данным перед применением к ним сжатия. Даже не все 8-битные звуковые сэмплы сжимаются лучше при дельта-кодировании, а удобство использования дельта-кодирования еще меньше для 16-битных и более лучших сэмплов. Поэтому алгоритмы сжатия часто выбирают дельта-кодирование только тогда, когда сжатие лучше, чем без него. Однако при сжатии видео дельта-кадры могут значительно уменьшить размер кадра и используются практически во всех кодеках сжатия видео .

Определение [ править ]

Дельта может быть определена двумя способами: симметричная дельта и направленная дельта . Симметричную дельту можно выразить как

\Delta (v_{1},v_{2})=(v_{1}\setminus v_{2})\cup (v_{2}\setminus v_{1}),

где $v_{1}$ и $v_{2}$ представляют две версии.

, Направленная дельта также называемая изменением, представляет собой последовательность (элементарных) операций изменения, которые при применении к одной версии $v_{1}$ , дает другую версию $v_{2}$ (обратите внимание на соответствие журналам транзакций в базах данных). В компьютерных реализациях они обычно принимают форму языка с двумя командами: копировать данные из v1 и записывать литеральные данные .

Варианты [ править ]

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

Проблемы реализации [ править ]

Характер данных, подлежащих кодированию, влияет на эффективность конкретного алгоритма сжатия.

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

При передаче по сети с дельта-кодированием, где на каждом конце канала связи доступна только одна копия файла, используются специальные коды контроля ошибок , чтобы определить, какие части файла изменились со времени его предыдущей версии. Например, rsync использует алгоритм скользящей контрольной суммы, Марка Адлера основанный на контрольной сумме adler-32 .

Пример кода C [ править ]

Следующий код C выполняет простую форму дельта-кодирования и декодирования последовательности символов:

void delta_encode(unsigned char *buffer, int length)
{
    unsigned char last = 0;
    for (int i = 0; i < length; i++)
    {
        unsigned char current = buffer[i];
        buffer[i] = current - last;
        last = current;
    }
}

void delta_decode(unsigned char *buffer, int length)
{
    unsigned char last = 0;
    for (int i = 0; i < length; i++)
    {
        unsigned char delta = buffer[i];
        buffer[i] = delta + last;
        last = buffer[i];
    }
}

Примеры [ править ]

Двоичное дельта-сжатие [ править ]

Двоичное дельта-сжатие — это технология, используемая при развертывании программного обеспечения для распространения исправлений .

Дельта-кодирование в HTTP [ править ]

Другим примером использования дельта-кодирования является RFC 3229 «Дельта-кодирование в HTTP», в котором предлагается, чтобы HTTP- серверы могли отправлять обновленные веб-страницы в виде различий между версиями (дельты), что должно уменьшить интернет-трафик, поскольку большинство страницы со временем меняются медленно, а не полностью переписываются неоднократно:

В этом документе описывается, как можно поддерживать дельта-кодирование в качестве совместимого расширения HTTP/1.1.
Многие запросы HTTP (гипертекстового транспортного протокола) вызывают получение слегка измененных экземпляров ресурсов, для которых у клиента уже есть запись в кэше. Исследования показали, что такие модифицирующие обновления происходят часто и что изменения обычно намного меньше, чем сам объект. В таких случаях HTTP мог бы более эффективно использовать пропускную способность сети, если бы мог передавать минимальное описание изменений, а не весь новый экземпляр ресурса.
[...] Мы считаем, что можно поддерживать rsync с использованием структуры «манипулирования экземплярами», описанной ниже в этом документе, но это не было детально проработано.

Предложенная платформа на основе rsync была реализована в системе rproxy в виде пары HTTP-прокси. ^[1] Как и базовая реализация на основе vcdiff, обе системы используются редко.

Дельта-копирование [ править ]

Дельта-копирование — это быстрый способ копирования файла, который частично изменен, если в месте назначения присутствует предыдущая версия. При дельта-копировании копируется только измененная часть файла. Обычно он используется в программном обеспечении для резервного копирования или копирования файлов , часто для экономии полосы пропускания при копировании между компьютерами через частную сеть или Интернет. Одним из ярких примеров с открытым исходным кодом является rsync . ^[2]^[3]^[4]

Онлайн-резервное копирование [ править ]

Многие службы онлайн-резервного копирования используют эту методологию, часто известную просто как дельты , чтобы предоставить своим пользователям предыдущие версии одного и того же файла из предыдущих резервных копий. Это снижает сопутствующие затраты не только на объем данных, которые необходимо хранить в разных версиях (поскольку каждая измененная версия файла должна быть доступна пользователям целиком), но и на затраты на загрузку (и иногда загрузка) каждого обновленного файла (при этом необходимо использовать только меньшую дельту, а не весь файл).

Дельта-обновления [ править ]

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

Разница [ править ]

Diff — это программа сравнения файлов, которая в основном используется для текстовых файлов. По умолчанию он генерирует симметричные дельты, которые являются обратимыми. Два формата, используемые для исправлений программного обеспечения , context и unified , предоставляют дополнительные строки контекста, которые позволяют допускать сдвиги в номере строки.

Гит [ править ]

Система управления исходным кодом Git использует дельта-сжатие во вспомогательной операции « git repack ». Объекты в репозитории, которые еще не были подвергнуты дельта-сжатию («свободные объекты»), сравниваются с эвристически выбранным подмножеством всех других объектов, а общие данные и различия объединяются в «пакетный файл», который затем сжимается с использованием традиционных методов. методы. В распространенных случаях использования, когда исходные файлы или файлы данных изменяются постепенно между фиксациями, это может привести к значительной экономии места. Операция переупаковки обычно выполняется как часть процесса « git gc », который запускается автоматически, когда количество незакрепленных объектов или файлов упаковки превышает настроенные пороговые значения.

Формат описан на странице формата пакета документации Git. Он реализует направленную дельту. ^[5]

VCDIFF [ править ]

Одним из общих форматов направленного дельта-кодирования является VCDIFF, описанный в RFC 3284 . Реализации бесплатного программного обеспечения включают Xdelta и open-vcdiff.

ГДИФФ [ править ]

Общий формат различий (GDIFF) — это еще один формат направленного дельта-кодирования. Он был представлен W3C в 1997 году. ^[6] Во многих случаях VCDIFF имеет лучшую степень сжатия, чем GDIFF.

bsdiff [ править ]

Bsdiff — это программа двоичного сравнения, использующая суффиксную сортировку . Для исполняемых файлов, которые содержат много изменений в адресах указателей, он работает лучше, чем кодирование «копирование и литерал» типа VCDIFF. Цель состоит в том, чтобы найти способ генерировать небольшие различия без необходимости анализа ассемблерного кода (как в Google Courgette). Bsdiff достигает этого, позволяя «копировать» совпадения с ошибками, которые затем исправляются с помощью дополнительного «добавляющего» массива побайтовых различий. Поскольку этот массив в основном представляет собой либо ноль, либо повторяющиеся значения для изменений смещения, после сжатия он занимает мало места. ^[7]

Bsdiff полезен для разностных обновлений. Google использует bsdiff в Chromium и Android. Функция deltarpm менеджера пакетов RPM основана на сильно модифицированном bsdiff, который может использовать для сопоставления хеш-таблицу. ^[8] FreeBSD также использует bsdiff для обновлений. ^[9]

С момента выпуска bsdiff 4.3 в 2005 году для него были внесены различные улучшения и исправления. Google поддерживает несколько версий кода для каждого из своих продуктов. ^[10] FreeBSD содержит многие совместимые изменения Google, в основном исправление уязвимостей и переход на более быструю версию. divsufsort процедура сортировки суффиксов. ^[11] В Debian есть ряд настроек производительности программы. ^[12]

ddelta — это переписанная версия bsdiff, предложенная для использования в дельта-обновлениях Debian. Помимо других улучшений эффективности, он использует скользящее окно для снижения затрат на память и процессор. ^[13]

См. также [ править ]

Различие данных — метод сжатия изменений с течением времени.
Чередование дельт — метод, используемый SCCS для хранения всех редакций файла.
Система контроля исходного кода - система контроля версий, предназначенная для отслеживания изменений в исходном коде.
Проблема построчной коррекции
Xdelta : дельта-кодер с открытым исходным кодом.

Ссылки [ править ]

^ «rproxy: введение» . rproxy.samba.org .
^ «Запрос на функцию: дельта-копирование — 2BrightSparks» . Архивировано из оригинала 13 марта 2016 г. Проверено 29 апреля 2016 г.
^ «Bvckup 2 | Форум | Как работает дельта-копирование» .
^ http://www.eggheadcafe.com/software/aspnet/33678264/delta-copying.aspx ^{[ постоянная мертвая ссылка ]}
^ «Git — документация в формате пакета» . Git-документация . Проверено 13 января 2020 г. .
^ «Общая спецификация формата различий» . www.w3.org .
^ Колин Персиваль, Наивные различия исполняемого кода, http://www.daemonology.net/bsdiff/ , 2003.
^ "rpmdelta/delta.c" . управление программным обеспечением rpm. 3 июля 2019 года . Проверено 13 января 2020 г. .
^ Аноним (май 2016 г.). «НЕКРИПТАНАЛИТИЧЕСКИЕ АТАКИ НА КОМПОНЕНТЫ ОБНОВЛЕНИЯ FREEBSD» . GitHub суть .
^ «xtraeme/bsdiff-chromium: README.chromium» . Гитхаб . 2012г .; «кабачок/третья_партия/bsdiff/README.chromium — chromium/src» . Git в Google . ; "Android/платформа/внешний/bsdiff/" . Git в Google .
^ «История freebsd/usr.bin/bsdiff» . Гитхаб .
^ «Пакет: bsdiff» . Трекер обновлений Debian .
^ Глобус, Джулиан. "Юлиан-Клоде/ддельта" . Гитхаб . Проверено 13 января 2020 г. .

Внешние ссылки [ править ]

RFC 3229 – Дельта-кодирование в HTTP

[1] «rproxy: введение» . rproxy.samba.org .

[2] «Запрос на функцию: дельта-копирование — 2BrightSparks» . Архивировано из оригинала 13 марта 2016 г. Проверено 29 апреля 2016 г.

[3] «Bvckup 2 | Форум | Как работает дельта-копирование» .

[4] ttp://www.eggheadcafe.com/software/aspnet/33678264/delta-copying.aspx ^{[ постоянная мертвая ссылка ]}

[5] «Git — документация в формате пакета» . Git-документация . Проверено 13 января 2020 г. .

[6] «Общая спецификация формата различий» . www.w3.org .

[7] Колин Персиваль, Наивные различия исполняемого кода, http://www.daemonology.net/bsdiff/ , 2003.

[8] "rpmdelta/delta.c" . управление программным обеспечением rpm. 3 июля 2019 года . Проверено 13 января 2020 г. .

[9] Аноним (май 2016 г.). «НЕКРИПТАНАЛИТИЧЕСКИЕ АТАКИ НА КОМПОНЕНТЫ ОБНОВЛЕНИЯ FREEBSD» . GitHub суть .

[10] «xtraeme/bsdiff-chromium: README.chromium» . Гитхаб . 2012г .; «кабачок/третья_партия/bsdiff/README.chromium — chromium/src» . Git в Google . ; "Android/платформа/внешний/bsdiff/" . Git в Google .

[11] «История freebsd/usr.bin/bsdiff» . Гитхаб .

[12] «Пакет: bsdiff» . Трекер обновлений Debian .

[13] Глобус, Джулиан. "Юлиан-Клоде/ддельта" . Гитхаб . Проверено 13 января 2020 г. .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]