Diferențierea datelor - Data differencing

În informatică și teoria informației , diferențierea datelor sau compresia diferențială produce o descriere tehnică a diferenței dintre două seturi de date - o sursă și o țintă. În mod formal, un algoritm de diferențiere a datelor ia ca sursă de intrare și date țintă și produce date de diferență astfel încât, având în vedere datele sursă și datele de diferență, se pot reconstrui datele țintă („ corecția ” sursei cu diferența pentru a produce ținta) .

Exemple

Unul dintre cele mai cunoscute exemple de diferențiere a datelor este utilitarul diff , care produce diferențe linie cu linie a fișierelor text (și în unele implementări, fișiere binare , fiind astfel un instrument de diferențiere cu scop general). Diferențierea fișierelor binare generale intră sub rubrica codării delta , un exemplu utilizat pe scară largă fiind algoritmul utilizat în rsync . Un format de diferențiere generic standardizat este VCDIFF , implementat în utilități precum versiunea Xdelta 3. Un program de diferențiere de înaltă eficiență (fișiere de patch-uri mici) este bsdiff, care folosește bzip2 ca etapă finală de compresie pe delta generată.

Preocupări

Principalele preocupări pentru diferențierea datelor sunt utilizabilitatea și eficiența spațiului (dimensiunea patch-urilor).

Dacă cineva dorește pur și simplu să reconstruiască ținta având în vedere sursa și patch-ul, se poate include pur și simplu întreaga țintă în patch și să „aplice” patch-ul aruncând sursa și scoțând ținta care a fost inclusă în patch; în mod similar, dacă sursa și ținta au aceeași dimensiune, se poate crea un patch simplu prin sursa și ținta XORing . În ambele cazuri, patch-ul va fi la fel de mare ca ținta. După cum arată aceste exemple, dacă singura preocupare este reconstrucția țintei, aceasta se face cu ușurință, în detrimentul unui patch mare, iar principala preocupare pentru diferențierea binară de uz general este reducerea dimensiunii patch-urilor.

În special pentru datele structurate, există alte preocupări, care se încadrează în mare măsură în „utilizare” - de exemplu, dacă se compară două documente, se dorește în general să știe ce secțiuni s-au modificat sau dacă unele secțiuni au fost mutate - se dorește să înțeleagă modul în care diferă documentele. De exemplu, „aici„ pisica ”a fost schimbată în„ câine ”, iar paragraful 13 a fost mutat la paragraful 14”. S-ar putea să doriți, de asemenea, să aveți diferențe solide - de exemplu, dacă două documente A și B diferă în paragraful 13, s-ar putea dori să puteți aplica acest patch chiar dacă unul a schimbat paragraful 7 din A. Un exemplu în acest sens este în , care arată ce linii s-au schimbat și unde formatul contextului permite robustete și îmbunătățește lizibilitatea umană.

Alte preocupări includ eficiența computațională, în ceea ce privește compresia datelor - găsirea unui patch mic poate necesita mult timp și memorie.

Cele mai bune rezultate apar atunci când se cunoaște datele comparate și alte constrângeri: diff este conceput pentru fișiere text orientate pe linie, în special cod sursă, și funcționează cel mai bine pentru acestea; rsync algoritmul este utilizat în funcție de sursă și țintă fiind într - o rețea de comunicare între ele și fiind lent, astfel că minimizează datele care trebuie transmise; iar actualizările pentru Google Chrome utilizează un algoritm personalizat pentru arhiva și formatul executabil al datelor programului.

Conexiune cu compresie de date

Comprimarea datelor poate fi văzută ca un caz special de diferențiere a datelor - diferențierea datelor constă în producerea unei diferențe date cu o sursă și o țintă , cu patch-uri producând o țintă dată cu o sursă și o diferență, în timp ce compresia datelor constă în producerea unui fișier comprimat având o target, iar decompresia constă în producerea unui target dat doar unui fișier comprimat. Astfel, se poate considera compresia datelor ca diferențierea datelor cu datele sursă goale, fișierul comprimat corespunzând unei „diferențe de nimic”. Acesta este același lucru cu considerarea entropiei absolute (corespunzătoare compresiei datelor) ca un caz special de entropie relativă (corespunzătoare diferențierii datelor) fără date inițiale.

Când se dorește sublinierea conexiunii, se poate folosi termenul de compresie diferențială pentru a se referi la diferențierea datelor.

Un dicționar care traduce între terminologia celor două câmpuri este dat ca:

Referințe