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