Codificare Delta

Codificarea Delta este o modalitate de stocare sau transmitere a datelor folosind diferențele dintre datele secvențiale, mai degrabă decât pe fișierul complet. Codificarea Delta este uneori numită compresie Delta , în special atunci când este necesar istoricul modificărilor (de exemplu, în proiectele software ).

Diferențele sunt înregistrate în fișiere discrete numite „delta” sau „diff”. Deoarece modificările sunt de obicei mici, codificarea delta reduce foarte mult redundanța datelor. Seturile de delte unice sunt mult mai eficiente din punct de vedere spațial decât echivalentele lor necodificate.

(Codificarea Delta nu trebuie confundată cu codificarea Delta Elias ).

Descriere

Poate că cel mai simplu exemplu este stocarea octeților ca diferențe (delta) între valorile secvențiale, în loc de stocarea valorilor simple: în loc de secvența '2, 4, 6, 9, 7', s-ar putea stoca secvența în codarea delta '2, 2 , 2, 3, -2 '. Acest lucru nu este foarte util atunci când este utilizat singur, dar poate crește compresia datelor. Pentru a înțelege cum, să presupunem o codificare cu lungime fixă (în realitate, codările pentru compresie sunt cu lungime variabilă): secvența originală are nevoie de 5 biți (1 bit de semn și 4 biți pentru a codifica numărul 9 ), în timp ce delta de codificare are nevoie de 3 biți (1 bit de semn și 2 biți pentru a codifica numărul 3 ). Evident, câștigul este posibil numai dacă variația este „netedă”, ceea ce este departe de a fi general în seturile de date.

Fișierele IFF și formatul de sunet 8SVX aplică această codificare datelor brute care codifică sunetul înainte de a aplica compresia. Din păcate, nici toate sunetele de 8 biți nu sunt comprimate cu avantaj, iar utilizarea codificării delta este chiar mai mică în sunetele de 16 biți. În consecință, algoritmii de compresie utilizează codificarea delta numai atunci când este mai bună compresia. Cu toate acestea, în compresia video, compresia delta poate reduce dimensiunea considerabil.

Un delta poate fi definit în două moduri, delta simetrică și delta directă . O delta simetrică poate fi exprimată ca $\Delta (v_{1},v_{2})=(v_{1}\backslash v_{2})\cup (v_{2}\backslash v_{1})$ ${\ displaystyle \ Delta (v_ {1}, v_ {2}) = (v_ {1} \ backslash v_ {2}) \ cup (v_ {2} \ backslash v_ {1})}$ ${\ displaystyle \ Delta (v_ {1}, v_ {2}) = (v_ {1} \ backslash v_ {2}) \ cup (v_ {2} \ backslash v_ {1})}$ unde este $v_{1}$ ${\ displaystyle v_ {1}}$ $v_1$ Și $v_{2}$ ${\ displaystyle v_ {2}}$ $v_ {2}$ reprezintă două versiuni succesive.

O delta directă , numită și alegere, este o secvență de operații elementare de alegere care, atunci când este aplicată unei versiuni $v_{1}$ ${\ displaystyle v_ {1}}$ $v_1$ returnează o altă versiune $v_{2}$ ${\ displaystyle v_ {2}}$ $v_ {2}$ (notați corespondența cu jurnalele de tranzacții din bazele de date).

O variație a codificării delta, care codifică diferențele dintre prefixe sau sufixe ale șirurilor , se numește codificare incrementală . Este deosebit de eficient pentru listele ordonate cu mici diferențe între șiruri, cum ar fi o listă de cuvinte dintr-un dicționar .

Într-o transmisie de rețea codificată delta în care este disponibilă doar o copie a fișierului la fiecare capăt al canalului de comunicații, sunt utilizate coduri speciale de verificare a erorilor pentru a afla ce părți ale fișierului s-au schimbat de la versiunea anterioară.

Natura datelor care trebuie codificate afectează eficiența unui anumit algoritm de compresie. Compresia Delta funcționează cel mai bine atunci când datele au variații mici sau constante; pentru un set de date neordonate, această metodă poate oferi o compresie redusă sau deloc.

Următorul cod C face codarea și decodarea delta simple.

 void delta_encode ( char * buffer , lungime int )
 {
   char t = 0 ;
   caracter original ;
   int i ;
   pentru ( i = 0 ; i < lungime ; i ++ )
   {
     original = tampon [ i ];
     tampon [ i ] - = t ;
     t = original ;
   }
 }
 
 void delta_decode ( char * buffer , lungime int )
 {
   char t = 0 ;
   int i ;
   pentru ( i = 0 ; i < lungime ; i ++ )
   {
     tampon [ i ] + = t ;
     t = tampon [ i ];
   }
 }

Un alt exemplu de utilizare a codificării delta este conținut în RFC 3229 , „Delta coding in ' HTTP ” („Delta coding in HTTP”), în care „ IETF propune ca serverele HTTP să poată trimite actualizări de pagini web sub forma o diferență între versiuni, care ar trebui să reducă traficul pe Internet , deoarece majoritatea paginilor se schimbă încet în timp, mai degrabă decât să fie rescrise în mod repetat:

Acest document descrie modul în care codificarea delta poate fi acceptată ca o extensie compatibilă la HTTP / 1.1.

Multe solicitări ale protocolului de transport hipertext (HTTP) determină recuperarea copiilor de resurse ușor modificate pentru care există deja o copie în cache . Cercetările au arătat că acest tip de actualizare a modificărilor este frecventă și că modificările sunt de obicei mult mai mici decât dimensiunea în ansamblu. În aceste cazuri, HTTP ar face o utilizare mult mai eficientă a lățimii de bandă dacă ar putea trimite o descriere minimă a modificărilor, mai degrabă decât o copie completă a resursei.

Elemente conexe

linkuri externe

RFC 3229 - Codificare Delta în HTTP
RFC 3284 - Formatul de date de diferențiere și compresie generice VCDIFF