Интернет магазин китайских планшетных компьютеров

Компьютеры - Дельта-кодирование

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

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

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

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

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

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

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

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

#include <sys/types.h>
 
void
delta_encode
{
        char last = 0, tmp;
        int i;
 
        for  {
                tmp = bp;
                bp -= last;
                last = tmp;
        }
}
 
void
delta_decode
{
        char last = 0;
        int i;
 
        for  {
                bp += last;
                last = bp;
        }
}