Datadifferensiering - Data differencing

I datavitenskap og informasjonsteori produserer datadifferensiering eller differensialkomprimering en teknisk beskrivelse av forskjellen mellom to datasett - en kilde og et mål. Formelt tar en datadifferensieringsalgoritme som inngangskildedata og måldata, og produserer forskjellsdata slik at gitt kildedataene og differansedataene, kan man rekonstruere måldataene (" lappe " kilden med forskjellen for å produsere målet) .

Eksempler

Et av de mest kjente eksemplene på datadifferensiering er diff- verktøyet, som produserer linje-for-linje-forskjeller mellom tekstfiler (og i noen implementeringer binære filer , og dermed er et forskjellig verktøy for generell bruk). Differensiering av generelle binære filer går under rubrikken delta-koding , med et mye brukt eksempel som algoritmen som brukes i rsync . Et standardisert generisk differensieringsformat er VCDIFF , implementert i slike verktøy som Xdelta versjon 3. Et høyeffektivt (lite patch filer) differensieringsprogram er bsdiff, som bruker bzip2 som et siste kompresjonstrinn på det genererte deltaet.

Bekymringer

Hovedproblemer for dataavvik er brukervennlighet og plasseffektivitet (lappestørrelse).

Hvis man bare ønsker å rekonstruere målet gitt kilden og lappen, kan man ganske enkelt inkludere hele målet i lappen og "bruke" lappen ved å kaste kilden og legge ut målet som er inkludert i lappen; på samme måte, hvis kilden og målet har samme størrelse, kan man lage en enkel oppdatering av XORing kilde og mål. I begge disse tilfellene vil lappen være like stor som målet. Som disse eksemplene viser, hvis det eneste problemet er rekonstruksjon av målet, gjøres dette enkelt, på bekostning av et stort plaster, og hovedproblemet for generell binær differensiering er å redusere oppdateringsstørrelsen.

Spesielt for strukturerte data har man andre bekymringer, som i stor grad faller inn under "brukervennlighet" - for eksempel hvis man sammenligner to dokumenter, vil man generelt vite hvilke seksjoner som har endret seg, eller om noen seksjoner er flyttet rundt - man ønsker å forstå hvordan dokumentene er forskjellige. For eksempel ble "her" katt "endret til" hund ", og avsnitt 13 ble flyttet til avsnitt 14". Man kan også ønske å ha sterke forskjeller - for eksempel hvis to dokumenter A og B skiller seg ut i paragraf 13, kan man ønske å kunne bruke denne oppdateringen selv om man har endret avsnitt 7 i A. Et eksempel på dette er i forskjell , som viser hvilke linjer som ble endret, og hvor kontekstformatet tillater robusthet og forbedrer menneskelig lesbarhet.

Andre bekymringer inkluderer beregningseffektivitet, som for datakomprimering - å finne en liten oppdatering kan være svært tid og minneintensiv.

De beste resultatene oppstår når man har kunnskap om dataene som sammenlignes og andre begrensninger: diff er designet for linjeorienterte tekstfiler, spesielt kildekode, og fungerer best for disse; den rsync algoritme brukes basert på kilde og mål blir over et nettverk fra hverandre, og kommunikasjon blir langsom, slik at den minimerer data som skal overføres; og oppdateringene for Google Chrome bruker en algoritme tilpasset arkivet og det kjørbare formatet til programmets data.

Forbindelse med datakomprimering

Datakomprimering kan sees på som et spesielt tilfelle av datadifferensiering - datadifferensiering består i å produsere en forskjell gitt en kilde og et mål , med lapping som produserer et mål gitt en kilde og en forskjell, mens datakomprimering består i å produsere en komprimert fil gitt en mål, og dekompresjon består av å produsere et mål gitt bare en komprimert fil. Dermed kan man vurdere datakomprimering som data som skiller seg ut med tomme kildedata, den komprimerte filen tilsvarer en "forskjell fra ingenting". Dette er det samme som å vurdere absolutt entropi (tilsvarende datakomprimering) som et spesielt tilfelle av relativ entropi (tilsvarende datadifferensiering) uten innledende data.

Når man ønsker å understreke forbindelsen, kan man bruke begrepet differensialkomprimering for å referere til datadifferensiering.

En ordbok som oversettes mellom terminologien til de to feltene er gitt som:

Referanser