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

Дельта-кодирования (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-сервера должны быть способны посылать изменённые web-страницы в форме различий между версиями (дельты), что должно уменьшить трафик Internet, так как большинство страниц мало изменяются в течении времени, а не полностью переписываются повторно:

This document describes how delta encoding can be supported as a compatible extension to HTTP/1.1.
Many HTTP (Hypertext Transport Protocol) requests cause the retrieval of slightly modified instances of resources for which the client already has a cache entry. Research has shown that such modifying updates are frequent, and that the modifications are typically much smaller than the actual entity. In such cases, HTTP would make more efficient use of network bandwidth if it could transfer a minimal description of the changes, rather than the entire new instance of the resource. This is called "delta encoding."

См. также

Ссылки

  • RFC 3229 - Delta Encoding in HTTP
  • RFC 3284 - The VCDIFF Generic Differencing and Compression Data Format
 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home