Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Дельта-кодування (англ. Delta encoding) — спосіб представлення даних у вигляді різниці (дельти) між послідовними даними замість самих даних.
Простим прикладом є збереження значень байтів як різниці (дельти) між послідовними значеннями, а не самих значень. Тобто замість 2, 4, 6, 9, 7, зберігати 2, 2, 2, 3, -2. Це не дуже корисно у випадку, коли використовується саме по собі, але може допомогти в разі подальшого стиснення цих даних, в яких часто зустрічаються повторювані значення. Наприклад, у звуковому форматі це кодування застосовують до чистих звукових даних перед тим, як застосовувати до них стиснення. Тільки 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 це лічильник У циклі: *додавання до цього елемента значення попереднього елемента *збереження значення цього елемента
Див. також
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Delta koduvannya angl Delta encoding sposib predstavlennya danih u viglyadi riznici delti mizh poslidovnimi danimi zamist samih danih Prostim prikladom ye zberezhennya znachen bajtiv yak riznici delti mizh poslidovnimi znachennyami a ne samih znachen Tobto zamist 2 4 6 9 7 zberigati 2 2 2 3 2 Ce ne duzhe korisno u vipadku koli vikoristovuyetsya same po sobi ale mozhe dopomogti v razi podalshogo stisnennya cih danih v yakih chasto zustrichayutsya povtoryuvani znachennya Napriklad u zvukovomu formati ce koduvannya zastosovuyut do chistih zvukovih danih pered tim yak zastosovuvati do nih stisnennya Tilki 8 bitni zvukovi sempli dobre stiskayutsya u razi delta koduvannya a u vipadku 16 bitnih i vishe sempliv cej metod pracyuye girshe Tomu v algoritmah stisnennya chasto vibirayut delta koduvannya tilki todi koli stisnennya z nim krashe nizh bez nogo Odnak pid chas stiskuvannya video delta frejmi mozhut znachno zmenshuvati rozmir kadru i vikoristovuyutsya praktichno v kozhnomu videokodeku Variaciya delta koduvannya za yakoyi koduyutsya vidminnosti mizh prefiksami abo sufiksami ryadkiv nazivayetsya Vono osoblivo efektivne dlya vidsortovanih spiskiv z malimi vidminnostyami mizh ryadkami takih napriklad yak spisok sliv zi slovnika V delta kodovanij peredachi po merezhi de tilki odinichna kopiya fajlu dostupna na kozhnomu kinci komunikacijnogo kanalu dlya viyavlennya togo yaki chastini fajlu zminilisya z chasu poperednoyi versiyi vikoristovuyut specialni kodi vipravlennya pomilok Delta koduvannya zastosovuyut yak poperednij etap dlya bagatoh algoritmiv stisnennya napriklad RLE i v invertovanih indeksah poshukovih program Priroda danih yaki budut zakodovani znachno vplivaye na efektivnist stisnennya Delta koduvannya pidvishuye koeficiyent stisnennya v tomu vipadku koli dani mayut malu abo stalu variaciyu yak napriklad gradiyent na zobrazhenni dlya ne vidsortovanih danih koeficiyent stisnennya mozhe buti duzhe malim Delta koduvannya robit nemozhlivim dovilnij dostup do danih oskilki dlya zvernennya do elementa masivu neobhidno pidsumuvati znachennya vsih poperednih Yaksho ce vse zh potribno zastosovuyetsya blokovij variant delta koduvannya v yakomu koduyutsya bloki deyakoyi zadanoyi dovzhini Todi neobhidno lishe pidsumuvati znachennya vid pochatku bloku yakomu nalezhit shukanij element a ne vsogo fajlu Rozmir bloku vibirayetsya v zalezhnosti vid programi zazvichaj za rezultatami hronometrazhu Diff koduvannyaSlid rozriznyati delta koduvannya i diff koduvannya Delta koduvannya znahodit riznicyu mizh elementami odniyeyi poslidovnosti a diff koduvannya porivnyuye dva riznih dzherela danih vkazuyuchi vidminnosti mizh nimi Diff koduvannya realizovano v standartnij UNIX utiliti diff a takozh dlya skorochennya obsyagu internet trafiku v protokoli HTTP zgidno z RFC 3229 Priklad realizaciyiNavedenij kod movoyu Si zdijsnyuye prostu formu in place delta koduvannya i dekoduvannya void delta encode unsigned char buffer int length unsigned char last 0 for int i 0 i lt 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 lt length i unsigned char delta buffer i buffer i delta last last buffer i Dokumentaciya U funkciyi delta encode funkciya prijmaye masiv i dovzhinu masivu yak argumenti yaksho dovzhinu ne peredano to masiv ne obroblyayetsya inicializuyutsya zminni tmp dlya zberezhennya ostannogo elementa i last dlya zberigannya ostannogo chisla inicializaciya ciklu de i ce lichilnik U cikli zberezhennya simvolu pid nomerom i v masivi obchislennya riznici mizh elementom pid nomerom i i i 1 pershij element ne zminyuyetsya i prisvoyennya riznici comu elementu zmina znachennya last na znachennya elementa i do zmini U funkciyi delta decode inicializaciya zminnoyi dlya zberigannya ostannogo simvolu inicializaciya ciklu de i ce lichilnik U cikli dodavannya do cogo elementa znachennya poperednogo elementa zberezhennya znachennya cogo elementaDiv takozhDelta modulyaciya