Дельта-кодирование — это способ хранения или передачи данных в виде различий (дельт) между последовательными данными, а не полными файлами; в более общем смысле это известно как различие данных . Дельта-кодирование иногда называют дельта-сжатием , особенно там, где требуется архивная история изменений (например, в программном обеспечении контроля версий ).
Различия записываются в отдельные файлы, называемые «дельтами» или «diffs». В ситуациях, когда различия невелики (например, изменение нескольких слов в большом документе или изменение нескольких записей в большой таблице), дельта-кодирование значительно снижает избыточность данных. Коллекции уникальных дельт существенно более эффективны по пространству, чем их некодированные эквиваленты.
С логической точки зрения разница между двумя значениями данных — это информация, необходимая для получения одного значения из другого — см. относительную энтропию . Разницу между одинаковыми значениями (при некоторой эквивалентности ) часто называют 0 или нейтральным элементом.
Возможно, самым простым примером является сохранение значений байтов как разностей (дельт) между последовательными значениями, а не самих значений. Итак, вместо 2, 4, 6, 9, 7 мы будем хранить 2, 2, 2, 3, −2. Это уменьшает дисперсию (диапазон) значений, когда соседние выборки коррелируют, позволяя использовать меньше битов для одних и тех же данных. Звуковой формат IFF 8SVX применяет это кодирование к необработанным звуковым данным перед применением к ним сжатия. Даже не все 8-битные звуковые сэмплы сжимаются лучше при дельта-кодировании, а удобство использования дельта-кодирования еще меньше для 16-битных и более лучших сэмплов. Поэтому алгоритмы сжатия часто выбирают дельта-кодирование только тогда, когда сжатие лучше, чем без него. Однако при сжатии видео дельта-кадры могут значительно уменьшить размер кадра и используются практически во всех кодеках сжатия видео .
Дельта может быть определена двумя способами: симметричная дельта и направленная дельта . Симметричную дельту можно выразить как
где и представляют две версии.
Направленная дельта , также называемая изменением, представляет собой последовательность (элементарных) операций изменения, которая при применении к одной версии дает другую версию (обратите внимание на соответствие журналам транзакций в базах данных). В компьютерных реализациях они обычно принимают форму языка с двумя командами: копировать данные из v1 и записывать литеральные данные .
Вариант дельта-кодирования, который кодирует различия между префиксами или суффиксами строк , называется инкрементным кодированием . Это особенно эффективно для отсортированных списков с небольшими различиями между строками, например списка слов из словаря .
Характер данных, подлежащих кодированию, влияет на эффективность конкретного алгоритма сжатия.
Дельта-кодирование работает лучше всего, когда данные имеют небольшие или постоянные вариации; для несортированного набора данных с помощью этого метода сжатие может быть практически невозможным.
При передаче по сети с дельта-кодированием, где на каждом конце канала связи доступна только одна копия файла, используются специальные коды контроля ошибок , чтобы определить, какие части файла изменились со времени его предыдущей версии. Например, rsync использует алгоритм скользящей контрольной суммы , основанный на контрольной сумме adler-32 Марка Адлера .
Следующий код C выполняет простую форму дельта-кодирования и декодирования последовательности символов:
void delta_encode ( беззнаковый символ * буфер , длина целого числа ) { беззнаковый символ последний = 0 ; for ( int я = 0 ; я < длина ; я ++ ) { беззнаковый символ текущий = буфер [ я ]; буфер [ i ] = текущий - последний ; последний = текущий ; } } void delta_decode ( беззнаковый символ * буфер , длина целого числа ) { беззнаковый символ последний = 0 ; for ( int я = 0 ; я < длина ; я ++ ) { unsigned char delta = буфер [ я ]; буфер [ i ] = дельта + последний ; последний = буфер [ я ]; } } Другим примером использования дельта-кодирования является 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, описанный в RFC 3284. Свободные программные реализации включают Xdelta и open-vcdiff.
Общий формат различий (GDIFF) — это еще один формат направленного дельта-кодирования. Он был представлен W3C в 1997 году. [6] Во многих случаях VCDIFF имеет лучшую степень сжатия, чем GDIFF.
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]