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

Материал из Википедии — свободной энциклопедии

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

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

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

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

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

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

void delta_encode(char *buffer, int length)
{
  char t = 0;
  char original;
  int i;
  for(i = 0; i < length; i++)
  {
    original = buffer[i];
    buffer[i] -= t;
    t = original;
  }
}

void delta_decode(char *buffer, int length)
{
  char t = 0;
  int i;
  for(i = 0; i < length; i++)
  {
    buffer[i] += t;
    t = buffer[i];
  }
}

Другой случай использования дельта-кодирования — это стандарт RFC 3229, «Delta encoding in HTTP» (Дельта-кодирование в протоколе HTTP), который предлагает что, HTTP-серверы должны быть способны посылать изменённые веб-страницы в форме различий между версиями (дельты), что должно уменьшить трафик Интернета, так как большинство страниц мало изменяются в течении времени, а не полностью переписываются повторно.

[править] См. также

• Алгоритм
• Сжатие данных
• Структура данных
• Дельта-модуляция
• Энтропийное кодирование
• Список алгоритмов

[править] Ссылки

• RFC 3229 — Delta Encoding in HTTP
• RFC 3284 — The VCDIFF Generic Differencing and Compression Data Format