Дельта-кодирование - это способ хранения или передачи данных в виде различий (дельт) между последовательными данными, а не полными файлами; в более общем смысле это называется различием данных . Дельта-кодирование иногда называют дельта-сжатием , особенно когда требуется архивирование истории изменений (например, в программном обеспечении для контроля версий ).
Различия записываются в отдельные файлы, называемые «дельтами» или «различиями». В ситуациях, когда различия незначительны - например, изменение нескольких слов в большом документе или изменение нескольких записей в большой таблице - дельта-кодирование значительно снижает избыточность данных. Коллекции уникальных дельт значительно более компактны, чем их некодированные эквиваленты.
С логической точки зрения разница между двумя значениями данных - это информация, необходимая для получения одного значения из другого - см. Относительную энтропию . Разницу между идентичными значениями (при некоторой эквивалентности ) часто называют 0 или нейтральным элементом .
Простой пример
Возможно, самый простой пример - это сохранение значений байтов в виде разностей (дельт) между последовательными значениями, а не самих значений. Таким образом, вместо 2, 4, 6, 9, 7 мы будем хранить 2, 2, 2, 3, −2. Это уменьшает дисперсию (диапазон) значений при коррелировании соседних выборок, позволяя использовать меньшее количество бит для одних и тех же данных. Формат звука IFF 8SVX применяет это кодирование к необработанным звуковым данным перед применением к ним сжатия. К сожалению, даже не все 8-битные звуковые сэмплы сжимаются лучше при дельта-кодировании, а удобство использования дельта-кодирования еще меньше для 16-битных и лучших сэмплов. Поэтому алгоритмы сжатия часто выбирают дельта-кодирование только тогда, когда сжатие лучше, чем без него. Однако при сжатии видео дельта-кадры могут значительно уменьшить размер кадра и используются практически в каждом кодеке сжатия видео .
Определение
Дельта может быть определена двумя способами: симметричная дельта и направленная дельта . Симметрична дельта может быть выражена как
где а также представляют две версии.
Направлена дельта , которая также называется изменением, представляет собой последовательность операций (элементарные) изменений , которые, при применении к одной версии, дает другую версию (обратите внимание на соответствие журналам транзакций в базах данных). В компьютерных реализациях они обычно принимают форму языка с двумя командами: копировать данные из v1 и записывать буквальные данные .
Варианты
Вариант кодирования дельты , которая кодирует различия между префиксами или суффиксами из строк называются инкрементным кодированием . Это особенно эффективно для отсортированных списков с небольшими различиями между строками, таких как список слов из словаря .
Проблемы реализации
Природа кодируемых данных влияет на эффективность конкретного алгоритма сжатия.
Дельта-кодирование работает лучше всего, когда данные имеют небольшие или постоянные вариации; для несортированного набора данных сжатие с помощью этого метода может быть незначительным или невозможным.
При дельта-кодированной передаче по сети, где на каждом конце канала связи доступна только одна копия файла, используются специальные коды контроля ошибок , чтобы определить, какие части файла были изменены по сравнению с его предыдущей версией. Например, rsync использует алгоритм скользящей контрольной суммы , основанный на контрольной сумме Марка Адлера adler-32 .
Пример кода C
Следующий код C выполняет простую форму дельта-кодирования и декодирования последовательности символов:
недействительный delta_encode ( беззнаковое символ * буфер , INT длина ) { беззнакового символ последнего = 0 ; for ( int я = 0 ; я < длина ; я ++ ) { беззнаковый символ текущий = буфер [ я ]; buffer [ i ] = current - последний ; последний = текущий ; } }недействительный delta_decode ( беззнаковое символ * буфер , INT длина ) { беззнакового символ последнего = 0 ; for ( int я = 0 ; я < длина ; я ++ ) { беззнаковый символ дельты = буфер [ я ]; буфер [ i ] = дельта + последний ; последний = буфер [ я ]; } }
Примеры
Дельта-кодирование в 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 Package Manager основана на сильно модифицированный bsdiff , который может использовать хэш - таблицу для сравнения. [8] FreeBSD также использует bsdiff для обновлений. [9]
Начиная с версии 4.3 bsdiff в 2005 году для нее были произведены различные улучшения и исправления. Google поддерживает несколько версий кода для каждого из своих продуктов. [10] FreeBSD принимает многие совместимые с Google изменения, в основном исправления уязвимостей и переход на более быструю divsufsort
процедуру сортировки суффиксов. [11] В Debian есть ряд настроек производительности программы. [12]
ddelta - это переработанная версия bsdiff, предлагаемая для использования в дельта-обновлениях Debian. Среди других улучшений эффективности он использует скользящее окно для снижения затрат на память и процессор. [13]
Смотрите также
- Различие данных
- Перемежающиеся дельты
- Система контроля исходного кода
- Проблема исправления строки в строку
- Xdelta : дельта-кодировщик с открытым исходным кодом
Рекомендации
- ^ "rproxy: введение" . rproxy.samba.org .
- ^ http://www.2brightsparks.com/bb/viewtopic.php?t=4473
- ^ https://www.bvckup2.com/support/forum/topic/739
- ^ http://www.eggheadcafe.com/software/aspnet/33678264/delta-copying.aspx [ постоянная мертвая ссылка ]
- ^ «Git - документация в формате pack» . Документация Git . Проверено 13 января 2020 года .
- ^ Спецификация общего формата различий
- ^ Колин Персиваль, Наивные различия исполняемого кода, http://www.daemonology.net/bsdiff/ , 2003.
- ^ "rpmdelta / delta.c" . rpm-программное-управление. 3 июля 2019 . Проверено 13 января 2020 года .
- ^ Аноним (май 2016 г.). «НЕКРИПТАНАЛИТИЧЕСКИЕ АТАКИ НА КОМПОНЕНТЫ ОБНОВЛЕНИЯ FREEBSD» . GitHub Gist .
- ^ "xtraeme / bsdiff-chromium: README.chromium" . GitHub . 2012 г.; "кабачок / третья_партия / bsdiff / README.chromium - хром / src" . Git в Google .; "Android / платформа / внешний / bsdiff /" . Git в Google .
- ^ "История для freebsd / usr.bin / bsdiff" . GitHub .
- ^ «Пакет: bsdiff» . Отслеживание обновлений Debian .
- ^ Клод, Джулиан. "юлиан-клоде / дделта" . GitHub . Проверено 13 января 2020 года .
Внешние ссылки
- RFC 3229 - Дельта-кодирование в HTTP