Deltakodning är ett sätt att representera data som en skillnad ( delta ) mellan konsekutiva data istället för själva data.
Det kanske enklaste exemplet är att lagra bytevärden som skillnader (deltas) mellan på varandra följande värden, i motsats till värdena själva. Så istället för 2, 4, 6, 9, 7 lagrar vi 2, 2, 2, 3, −2. Detta är inte särskilt användbart när det används på egen hand, men det kan vara användbart om du behöver komprimera denna data ytterligare, som ofta har dubbla värden. Till exempel tillämpar ljudformatet IFF 8SVX denna kodning på rena ljuddata innan komprimering tillämpas på den. Endast 8-bitars ljudsampel komprimeras bra vid deltakodning, och i fallet med 16-bitars och högre sampel fungerar denna metod sämre. Därför väljer komprimeringsalgoritmer ofta deltakodning endast när komprimeringen är bättre med den än utan den. Vid videokomprimering kan deltaramar dock minska bildstorleken avsevärt och används i nästan varje videocodec.
En variant av deltakodning som kodar skillnader mellan strängprefix eller suffix kallas inkrementell kodning . Det är särskilt effektivt för sorterade listor med små skillnader mellan strängar, till exempel en lista med ord från en ordbok .
Vid deltakodad nätverksöverföring, där endast en enda kopia av filen finns tillgänglig i varje ände av kommunikationskanalen, används speciella felkorrigeringskoder för att upptäcka vilka delar av filen som har ändrats sedan den tidigare versionen.
Delta-kodning används som ett preliminärt steg för många komprimeringsalgoritmer, som RLE , och i inverterade sökmotorindex. Typen av data som ska kodas påverkar i hög grad effektiviteten av komprimeringen. Deltakodning ökar komprimeringsförhållandet när data har liten eller konstant variation (som en gradient i en bild); för data som genereras av en slumptalsgenerator med en enhetlig fördelning kommer komprimeringsfaktorn inte att förändras mycket.
Deltakodning gör det omöjligt att slumpmässigt komma åt data, eftersom för att komma åt ett arrayelement är det nödvändigt att summera värdena för alla tidigare. Om det ändå är nödvändigt används en blockversion av deltakodning, i vilken block av en viss längd kodas. Då är det bara nödvändigt att summera värdena från början av blocket som det nödvändiga elementet tillhör, men inte hela filen. Blockstorleken väljs beroende på applikation, vanligtvis baserat på timingresultat.
En skillnad bör göras mellan deltakodning och diff-kodning . Delta-kodning hittar skillnaden mellan element i samma sekvens, medan diff-kodning jämför två olika datakällor, vilket indikerar skillnaderna mellan dem. Diff-kodning är implementerad i standard Unix - verktygsdiff , samt för att minska mängden Internettrafik i HTTP-protokollet enligt RFC 3229 .
Följande C -kod implementerar en enkel form av in-place delta-kodning och avkodning:
void delta_encode ( osignerad char * buffert , int längd ) { osignerad char last = 0 ; för ( int i = 0 ; i < längd ; i ++ ) { osignerad char current = buffert [ i ]; buffert [ i ] = nuvarande - sista ; sista = aktuell ; } } void delta_decode ( osignerad char * buffert , int längd ) { osignerad char last = 0 ; för ( int i = 0 ; i < längd ; i ++ ) { osignerad char delta = buffert [ i ]; buffert [ i ] = delta + sista ; sista = buffert [ i ]; } }Dokumentation:
I delta_encode-funktionen: *funktionen tar en array och längden på arrayen som argument, om längden inte passerades så bearbetas inte arrayen *De aktuella variablerna initieras för att lagra det sista elementet och sist för att lagra det sista numret. *loopinitiering, där i är en räknare. I en cykel *lagring av tecknet vid nummer i i arrayen *beräkna skillnaden mellan elementnummer i och i-1, det första elementet ändras inte, och tilldela skillnaden till detta element *ändra värdet av last till värdet av element i före ändringen I delta_decode-funktionen *initiering av en variabel för att lagra det sista tecknet *loopinitiering, där i är en räknare I en slinga: *att lägga till värdet av det föregående elementet till detta element *spara värdet på detta element| Kompressionsmetoder _ | |||||||
|---|---|---|---|---|---|---|---|
| Teori |
| ||||||
| Förlust mindre |
| ||||||
| Audio |
| ||||||
| Bilder |
| ||||||
| Video |
| ||||||
| Versionskontrollsystem ( kategori ) | |
|---|---|
| Endast lokalt | |
| Klient-server | |
| Distribuerad | |