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

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

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

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

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

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

Определение

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

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

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

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

Варианты

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

Проблемы реализации

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

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

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

Пример кода C

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

пустота delta_encode(беззнаковый char *буфер, int длина){    беззнаковый char последний = 0;    за (int я = 0; я < длина; я++)    {        беззнаковый char Текущий = буфер[я];        буфер[я] = Текущий - последний;        последний = Текущий;    }}пустота delta_decode(беззнаковый char *буфер, int длина){    беззнаковый char последний = 0;    за (int я = 0; я < длина; я++)    {        беззнаковый char дельта = буфер[я];        буфер[я] = дельта + последний;        последний = буфер[я];    }}

Примеры

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

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

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

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

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

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

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

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

Дельта-обновления

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

Diff

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

Git

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

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

VCDIFF

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

GDIFF

Generic Diff Format (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]

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

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

Смотрите также

Различие данных
Перемежающиеся дельты
Система контроля исходного кода
Проблема исправления строки в строку
Xdelta: дельта-кодировщик с открытым исходным кодом

внешняя ссылка

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

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

[2] ttp://www.2brightsparks.com/bb/viewtopic.php?t=4473

[3] ttps://www.bvckup2.com/support/forum/topic/739

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

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

[6] Спецификация универсального формата различий

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

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

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

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

[11] "История для freebsd / usr.bin / bsdiff". GitHub.

[12] "Пакет: bsdiff". Отслеживание обновлений Debian.

[13] Клод, Джулиан. "Джулиан-Клоде / Дделта". GitHub. Получено 13 января 2020.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]