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

Для термина «Кодирование» см. также другие значения.

Дельта-кодирование (англ. Delta encoding) — способ представления данных в виде разницы (дельты) между последовательными данными вместо самих данных.

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

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

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

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

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

Diff-кодирование

Не стоит путать дельта-кодирование с diff-кодированием. Если дельта-кодирование находит разницу между элементами одной последовательности, то diff-кодирование сравнивает два разных источника данных, указывая различия между ними. Diff-кодирование реализовано в стандартной Unix-утилите diff, а также для сокращения объема интернет-трафика в протоколе HTTP согласно RFC 3229.

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

Следующий код на Си осуществляет простую форму in-place дельта-кодирования и декодирования:

#include <sys/types.h>              //include sys/types.h for size_t
                                        
void delta_encode(char *bp, size_t n=0)    //char *bp is enecoding char array 
{                                   
	char last = 0, tmp;             //last is last symbol, the difference to the next will be calculated from it

	for (size_t i = 0; i < n; ++i) {       //cycle for delta enecrypt
		tmp = bp[i];                       
		bp[i] -= last;                    //enecrypt this symbol, 0 for first element
		last = tmp;
	}
}

void delta_decode(char *bp, size_t n=0)   //decrypter for delta symbol arry
{                                       
    char last = 0;                                                                              
	for (int i = 0; i < n; ++i) {           //cycle for decrypting
		bp[i] += last;                  //enecrypt this file
		last = bp[i];                   
	}
}

Документация:

   В функции delta_encode:
       *функция принимает массив и длину массива как аргументы, если длина не была передана, то массив не обрабатывается
       *инициализируются переменные tmp, для сохранения последнего элемента и last для хранения последнего числа.
       *инициализация цикла, где i это счетчик.
       В цикле
           *сохранение символа под номером i в массиве
           *вычисление разницы между элементом под номером i и i-1, первый элемент не меняется, и присвоение разницы этому элементу
           *изменение значение last на значение элемента i до изменения
   В функции delta_decode
       *инициализация переменной для хранения последнего символа
       *инициализация цикла, где i это счетчик
       В цикле:
           *добавление к этому элементу значение предыдущего элемента
           *сохранение значение этого элемента

См. также

• Дельта-модуляция

Отрывок, характеризующий Дельта-кодирование

Противно своей привычке опаздывать, Пьер в этот день вместо восьми без 10 ти минут, приехал к Бергам в восемь часов без четверти.
Берги, припася, что нужно было для вечера, уже готовы были к приему гостей.
В новом, чистом, светлом, убранном бюстиками и картинками и новой мебелью, кабинете сидел Берг с женою. Берг, в новеньком, застегнутом мундире сидел возле жены, объясняя ей, что всегда можно и должно иметь знакомства людей, которые выше себя, потому что тогда только есть приятность от знакомств. – «Переймешь что нибудь, можешь попросить о чем нибудь. Вот посмотри, как я жил с первых чинов (Берг жизнь свою считал не годами, а высочайшими наградами). Мои товарищи теперь еще ничто, а я на ваканции полкового командира, я имею счастье быть вашим мужем (он встал и поцеловал руку Веры, но по пути к ней отогнул угол заворотившегося ковра). И чем я приобрел всё это? Главное умением выбирать свои знакомства. Само собой разумеется, что надо быть добродетельным и аккуратным».
Берг улыбнулся с сознанием своего превосходства над слабой женщиной и замолчал, подумав, что всё таки эта милая жена его есть слабая женщина, которая не может постигнуть всего того, что составляет достоинство мужчины, – ein Mann zu sein [быть мужчиной]. Вера в то же время также улыбнулась с сознанием своего превосходства над добродетельным, хорошим мужем, но который всё таки ошибочно, как и все мужчины, по понятию Веры, понимал жизнь. Берг, судя по своей жене, считал всех женщин слабыми и глупыми. Вера, судя по одному своему мужу и распространяя это замечание, полагала, что все мужчины приписывают только себе разум, а вместе с тем ничего не понимают, горды и эгоисты.
Берг встал и, обняв свою жену осторожно, чтобы не измять кружевную пелеринку, за которую он дорого заплатил, поцеловал ее в середину губ.
– Одно только, чтобы у нас не было так скоро детей, – сказал он по бессознательной для себя филиации идей.
– Да, – отвечала Вера, – я совсем этого не желаю. Надо жить для общества.
– Точно такая была на княгине Юсуповой, – сказал Берг, с счастливой и доброй улыбкой, указывая на пелеринку.
В это время доложили о приезде графа Безухого. Оба супруга переглянулись самодовольной улыбкой, каждый себе приписывая честь этого посещения.
«Вот что значит уметь делать знакомства, подумал Берг, вот что значит уметь держать себя!»
– Только пожалуйста, когда я занимаю гостей, – сказала Вера, – ты не перебивай меня, потому что я знаю чем занять каждого, и в каком обществе что надо говорить.
Берг тоже улыбнулся.
– Нельзя же: иногда с мужчинами мужской разговор должен быть, – сказал он.
Пьер был принят в новенькой гостиной, в которой нигде сесть нельзя было, не нарушив симметрии, чистоты и порядка, и потому весьма понятно было и не странно, что Берг великодушно предлагал разрушить симметрию кресла, или дивана для дорогого гостя, и видимо находясь сам в этом отношении в болезненной нерешительности, предложил решение этого вопроса выбору гостя. Пьер расстроил симметрию, подвинув себе стул, и тотчас же Берг и Вера начали вечер, перебивая один другого и занимая гостя.
Вера, решив в своем уме, что Пьера надо занимать разговором о французском посольстве, тотчас же начала этот разговор. Берг, решив, что надобен и мужской разговор, перебил речь жены, затрогивая вопрос о войне с Австриею и невольно с общего разговора соскочил на личные соображения о тех предложениях, которые ему были деланы для участия в австрийском походе, и о тех причинах, почему он не принял их. Несмотря на то, что разговор был очень нескладный, и что Вера сердилась за вмешательство мужского элемента, оба супруга с удовольствием чувствовали, что, несмотря на то, что был только один гость, вечер был начат очень хорошо, и что вечер был, как две капли воды похож на всякий другой вечер с разговорами, чаем и зажженными свечами.
Вскоре приехал Борис, старый товарищ Берга. Он с некоторым оттенком превосходства и покровительства обращался с Бергом и Верой. За Борисом приехала дама с полковником, потом сам генерал, потом Ростовы, и вечер уже совершенно, несомненно стал похож на все вечера. Берг с Верой не могли удерживать радостной улыбки при виде этого движения по гостиной, при звуке этого бессвязного говора, шуршанья платьев и поклонов. Всё было, как и у всех, особенно похож был генерал, похваливший квартиру, потрепавший по плечу Берга, и с отеческим самоуправством распорядившийся постановкой бостонного стола. Генерал подсел к графу Илье Андреичу, как к самому знатному из гостей после себя. Старички с старичками, молодые с молодыми, хозяйка у чайного стола, на котором были точно такие же печенья в серебряной корзинке, какие были у Паниных на вечере, всё было совершенно так же, как у других.