Dataskillnad
Inom datavetenskap och informationsteori producerar dataskillnad eller differentiell komprimering en teknisk beskrivning av skillnaden mellan två uppsättningar data - en källa och ett mål. Formellt tar en dataskillnadsalgoritm som indatakälldata och måldata och producerar skillnadsdata så att givet källdata och skillnadsdata kan man rekonstruera måldata ("lappa" källan med skillnaden för att producera målet ) .
Exempel
Ett av de mest kända exemplen på dataskillnad är verktyget diff , som producerar rad-för-rad-skillnader för textfiler (och i vissa implementeringar, binära filer , vilket är ett allmänt särskiljningsverktyg). Skillnad mellan generella binära filer går under rubriken deltakodning , med ett allmänt använt exempel är algoritmen som används i rsync . Ett standardiserat generiskt differensformat är VCDIFF , implementerat i sådana verktyg som Xdelta version 3. Ett högeffektivt (små patchfiler) differensprogram är bsdiff, som använder bzip2 som ett sista komprimeringssteg på det genererade deltat.
Bekymmer
Huvudproblemen för dataskillnad är användbarhet och utrymmeseffektivitet (patchstorlek).
Om man helt enkelt vill rekonstruera målet givet källan och plåstret, kan man helt enkelt inkludera hela målet i plåstret och "applicera" plåstret genom att kassera källan och mata ut målet som har inkluderats i plåstret; på liknande sätt, om källan och målet har samma storlek kan man skapa en enkel patch genom att XORing källa och mål. I båda dessa fall kommer plåstret att vara lika stort som målet. Som dessa exempel visar, om det enda problemet är rekonstruktion av målet, är detta enkelt att göra, på bekostnad av en stor lapp, och huvudproblemet för allmänt ändamål med binär differens är att minska lappstorleken.
Speciellt för strukturerad data har man andra bekymmer, som till stor del faller under "användbarhet" – om man till exempel jämför två dokument vill man i allmänhet veta vilka avsnitt som har ändrats eller om vissa avsnitt har flyttats runt – man vill förstå hur dokumenten skiljer sig åt. Till exempel "här ändrades 'katt' till 'hund' och punkt 13 flyttades till punkt 14". Man kanske också vill ha robusta skillnader – till exempel om två dokument A och B skiljer sig åt i punkt 13, kan man vilja kunna tillämpa denna patch även om man har ändrat punkt 7 i A. Ett exempel på detta är olika , som visar vilka rader som ändrats och var kontextformatet tillåter robusthet och förbättrar mänsklig läsbarhet.
Andra problem inkluderar beräkningseffektivitet, som för datakomprimering – att hitta en liten patch kan vara mycket tids- och minneskrävande.
Bästa resultat uppstår när man har kunskap om data som jämförs och andra begränsningar: diff är designad för radorienterade textfiler, särskilt källkod, och fungerar bäst för dessa; rsync - algoritmen används baserat på att källa och mål finns över ett nätverk från varandra och kommunikationen är långsam, så den minimerar data som måste överföras; och uppdateringarna för Google Chrome använder en algoritm som är anpassad till arkivet och det körbara formatet för programmets data.
Anslutning med datakomprimering
Datakomprimering kan ses som ett specialfall av dataskillnad – datadifferentiering består av att producera en skillnad givet en källa och ett mål , med patchning som producerar ett mål givet en källa och en skillnad, medan datakomprimering består av att producera en komprimerad fil givet en mål, och dekomprimering består av att producera ett mål endast med en komprimerad fil. Således kan man betrakta datakomprimering som data som skiljer sig med tomma källdata, den komprimerade filen motsvarar en "skillnad från ingenting". Detta är samma sak som att betrakta absolut entropi (motsvarande datakomprimering) som ett specialfall av relativ entropi (motsvarande dataskillnad) utan initial data.
När man vill betona sambandet kan man använda termen differentiell komprimering för att hänvisa till dataskillnad.
En ordbok som översätter mellan terminologin för de två fälten ges som:
kompression | skiljer sig åt |
---|---|
ingen | källa |
okomprimerad | mål |
komprimerad | skillnad, delta |
kompression | skiljer sig åt |
dekompression | lappning |