Введение

Тип метода передачи данных

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

Простой пример

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

Определение

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

Варианты

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

Вопросы внедрения

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

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

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

Онлайн резервная копия

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

Обновления дельты

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

Различие

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

Убирайся .

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

ВКДИФФ

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

ГДИФФ

Формат GDIFF (Generic Diff Format) — это ещё один формат кодирования с использованием направленных дельт. Он был представлен в W3C в 1997 году. Во многих случаях VCDIFF обеспечивает более высокую степень сжатия, чем GDIFF.

bsdiff (различие)

Bsdiff — это программа для двоичного сравнения, использующая сортировку суффиксов. Для исполняемых файлов, содержащих множество изменений в адресах указателей, она работает эффективнее, чем кодировки типа VCDIFF, основанные на "копировании и литералах". Цель разработки — найти способ создания небольшого патча без необходимости разбора ассемблерного кода (как в Google Courgette). Bsdiff достигает этого, допуская "копирование" с ошибками, которые затем исправляются с помощью дополнительного массива "добавлений", содержащего побайтовые различия. Поскольку этот массив в основном состоит из нулей или повторяющихся значений для изменений смещения, он занимает мало места после сжатия. Bsdiff полезен для создания дельта-обновлений. Google использует bsdiff в Chromium и Android. Функция deltarpm в RPM Package Manager основана на значительно модифицированной версии bsdiff, которая может использовать хеш-таблицу для поиска соответствий. FreeBSD также использует bsdiff для обновлений. С момента выхода версии 4.3 в 2005 году было внесено множество улучшений и исправлений. Google поддерживает несколько версий кода для каждого из своих продуктов. FreeBSD использует многие изменения, совместимые с Google, в основном исправление уязвимости и переход к более быстрому алгоритму сортировки суффиксов. Debian внес ряд оптимизаций производительности в программу. ddelta — это переписанная версия bsdiff, предлагаемая для использования в дельта-обновлениях Debian. Среди прочих улучшений эффективности она использует скользящее окно для снижения потребления памяти и вычислительных ресурсов.