Дельта-кодування

Дельта-кодування (англ. 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 це лічильник
 У циклі:
 *додавання до цього елемента значення попереднього елемента
 *збереження значення цього елемента

Див. також