Дэльта-кадзіраванне

Дэльта-кадзіраванне (англ.: 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 дэльта-кадзіравання і дэкадзіравання:

#include <sys/types.h>

void
delta_encode(char *bp, size_t n)
{
	char last = 0, tmp;
	int i;

	for (i = 0; i < n; ++i) {
		tmp = bp[i];
		bp[i] -= last;
		last = tmp;
	}
}

void
delta_decode(char *bp, size_t n)
{
	char last = 0;
	int i;

	for (i = 0; i < n; ++i) {
		bp[i] += last;
		last = bp[i];
	}
}