Войти
Дельта-кодирование - это способ хранения или передачи данных в виде различий (дельты) между последовательными данными, а не полными файлами; в более общем смысле это известно как различие данных. Дельта-кодирование иногда называют дельта-сжатием, особенно там, где требуются архивные истории изменений (например, в программном обеспечении контроля версий ).
Различия записываются в отдельные файлы, называемые "дельтами" или "различиями". В ситуациях, когда различия невелики - например, изменение нескольких слов в большом документе или изменение нескольких записей в большой таблице - дельта-кодирование значительно снижает избыточность данных. Коллекции уникальных дельт значительно более компактны, чем их некодированные эквиваленты.
С логической точки зрения разница между двумя значениями данных - это информация, необходимая для получения одного значения из другого - см. относительная энтропия. Разница между идентичными значениями (при некоторой эквивалентности ) часто называется 0 или нейтральным элементом.
Возможно, Самый простой пример - это сохранение значений байтов как разностей (дельт) между последовательными значениями, а не самих значений. Итак, вместо 2, 4, 6, 9, 7 мы будем хранить 2, 2, 2, 3, −2. Это уменьшает дисперсию (диапазон) значений, когда соседние выборки коррелированы, обеспечивая меньшее использование бит для тех же данных. IFF 8SVX звуковой формат применяет эту кодировку к необработанным звуковым данным перед применением к ним сжатия. К сожалению, даже не все 8-битные звуковые семплы лучше сжимаются при дельта-кодировании, а удобство использования дельта-кодирования еще меньше для 16-битных и лучших семплов. Поэтому алгоритмы сжатия часто выбирают дельта-кодирование только тогда, когда сжатие лучше, чем без него. Однако при сжатии видео дельта-кадры могут значительно уменьшить размер кадра и используются практически в каждом кодеке сжатия видео .
Дельта может быть определена двумя способами: симметричная дельта и направленная дельта. Симметричная дельта может быть выражена как
где 
Направленная дельта, также называемая изменением, представляет собой последовательность (элементарных) операций изменения, которые при применении к одной версии
Вариант дельта-кодирования, который кодирует различия между префиксами или суффиксами в строк, называется инкрементное кодирование. Это особенно эффективно для отсортированных списков с небольшими различиями между строками, таких как список слов из словаря.
Природа данных, которые должны быть закодированы влияет на эффективность конкретного алгоритма сжатия.
Дельта-кодирование работает лучше всего, когда данные имеют небольшие или постоянные вариации; для несортированного набора данных сжатие с помощью этого метода может быть незначительным или невозможным.
При передаче по сети с дельта-кодированием, когда на каждом конце канала связи доступна только одна копия файла, используются специальные коды контроля ошибок для определения того, какие части файла изменились по сравнению с предыдущей версией. Например, rsync использует алгоритм скользящей контрольной суммы на основе контрольной суммы Марка Адлера adler-32.
Следующий код C выполняет простую форму дельта-кодирования и декодирования последовательности символов:
void delta_encode (unsigned char * buffer, длина int) {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]; } }Другой пример использования дельта-кодирования - RFC 3229, «Дельта-кодирование в HTTP ", который предполагает, что серверы HTTP должны иметь возможность отправлять обновленные веб-страницы в виде различий между версиями (дельты), что должно уменьшить интернет-трафик, поскольку большинство страниц со временем меняются медленно, а не полностью многократно переписано:
В этом документе описывается, как дельта-кодирование может поддерживаться в качестве совместимого расширения для HTTP / 1.1.
Многие запросы HTTP (протокол передачи гипертекста) вызывают получение слегка измененных экземпляров ресурсов, для которых у клиента уже есть запись в кеше. Исследования показали, что такие модифицирующие обновления происходят часто и что модификации обычно намного меньше, чем фактический объект. В таких случаях HTTP мог бы более эффективно использовать пропускную способность сети, если бы он мог передавать минимальное описание изменений, а не всего нового происхождение ресурса.
[...] Мы полагаем, что можно было бы поддерживать rsync, используя структуру «манипулирования экземпляром», описанную далее в этом документе, но это не было проработано в каких-либо деталях.
Предлагаемая структура на основе rsync была реализована в системе rproxy в виде пары HTTP-прокси. Как и базовая реализация на основе vcdiff, обе системы используются редко.
Дельта-копирование - это быстрый способ копирования файла, который частично изменен, когда предыдущая версия присутствует в месте назначения. При дельта-копировании копируется только измененная часть файла. Обычно он используется в программном обеспечении резервного копирования или копирования файлов, часто для экономии полосы пропускания при копировании между компьютерами через частную сеть или Интернет. Одним из примечательных примеров с открытым исходным кодом является rsync.
Многие из онлайн-сервисов резервного копирования применяют эту методологию, часто известную как дельты, чтобы дать своим пользователям предыдущие версии того же файла из предыдущих резервных копий. Это снижает сопутствующие расходы, не только в объеме данных, которые должны храниться в виде различных версий (поскольку вся измененная версия файла должна быть предложена пользователям для доступа), но также и в части затрат на загрузку (и иногда загрузка) каждого файла, который был обновлен (нужно использовать только меньшую дельту, а не весь файл).
Для больших программных пакетов обычно мало данных изменяется между версиями. Многие поставщики предпочитают использовать дельта-передачу для экономии времени и пропускной способности.
Diff - это программа сравнения файлов, которая в основном используется для текстовых файлов. По умолчанию он генерирует обратимые симметричные дельты. Два формата, используемые для программного обеспечения патчей, контекстный и унифицированный, предоставляют дополнительные контекстные строки, которые позволяют допускать сдвиги в номере строки.
Система управления исходным кодом Git использует дельта-сжатие во вспомогательной операции «git repack ». Объекты в репозитории, которые еще не были подвергнуты дельта-сжатию («свободные объекты»), сравниваются с эвристически выбранным подмножеством всех других объектов, и общие данные и различия объединяются в «пакетный файл», который затем сжимается с использованием обычных методы. В распространенных случаях использования, когда исходные файлы или файлы данных изменяются постепенно между фиксациями, это может привести к значительной экономии места. Операция переупаковки обычно выполняется как часть процесса «git gc », который запускается автоматически, когда количество незакрепленных объектов или файлов упаковки превышает настроенные пороговые значения.
Формат задокументирован на странице pack-format документации git. Он реализует направленную дельту.
Одним из общих форматов для направленного дельта-кодирования является VCDIFF, описанный в RFC 3284. Реализации бесплатного программного обеспечения включают Xdelta и open-vcdiff.
Generic Diff Format (GDIFF) - еще один формат направленного дельта-кодирования. Он был представлен на W3C в 1997 году. Во многих случаях VCDIFF имеет лучшую степень сжатия, чем GDIFF.
Bsdiff - это двоичная программа сравнения, использующая суффиксную сортировку. Для исполняемых файлов, которые содержат много изменений в адресах указателей, он работает лучше, чем "копирование и буквальное" кодирование типа VCDIFF. Намерение состоит в том, чтобы найти способ сгенерировать небольшую разницу без необходимости разбирать код сборки (как в Google Courgette). Bsdiff достигает этого, позволяя «копировать» совпадения с ошибками, которые затем исправляются с помощью дополнительного массива «добавления» побайтных различий. Поскольку этот массив в основном состоит из нулевых или повторяющихся значений для изменений смещения, он занимает мало места после сжатия.
Bsdiff полезен для дельта-обновлений. Google использует bsdiff в Chromium и Android. Функция deltarpm в диспетчере пакетов RPM основана на сильно модифицированном bsdiff, который может использовать хэш-таблицу для сопоставления. FreeBSD также использует bsdiff для обновлений.
Начиная с версии 4.3 bsdiff в 2005 году, для нее были произведены различные улучшения и исправления. Google поддерживает несколько версий кода для каждого из своих продуктов. FreeBSD принимает многие совместимые с Google изменения, в основном исправление уязвимостей и переход на более быструю процедуру сортировки суффиксов divsufsort. Debian имеет ряд настроек производительности программы.
ddelta - это переработанная версия bsdiff, предлагаемая для использования в дельта-обновлениях Debian. Среди других улучшений эффективности он использует скользящее окно для уменьшения затрат на память и ЦП.
