Дельта-кодування — Вікіпедія

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

Простим прикладом є збереження значень байтів як різниці (дельти) між послідовними значеннями, а не самих значень. Тобто замість 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 дельта-кодування і декодування:

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

• Дельта-модуляція