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

Дельта-кодирование (англ. 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 дельта-кодирования и декодирования:

void delta_encode(unsigned char *buffer, int length) { 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]; } }

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

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