Дэльта-кадзіраванне
Дэльта-кадзіраванне (англ.: 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];
}
}
Для паляпшэння артыкула пажадана |