Delta kódování je způsob reprezentace dat jako rozdíl ( delta ) mezi po sobě jdoucími daty namísto dat samotných.
Snad nejjednodušším příkladem je uložit hodnoty bajtů jako rozdíly (delty) mezi po sobě jdoucími hodnotami, na rozdíl od hodnot samotných. Takže místo 2, 4, 6, 9, 7 uložíme 2, 2, 2, 3, −2. To není příliš užitečné, když se používá samostatně, ale může být užitečné, pokud potřebujete dále komprimovat tato data, která mají často duplicitní hodnoty. Například zvukový formát IFF 8SVX aplikuje toto kódování na čistá zvuková data před použitím komprese. Pouze 8bitové audio vzorky se v případě delta kódování dobře komprimují a v případě 16bitových a vyšších vzorků tato metoda funguje hůře. Proto kompresní algoritmy často volí delta kódování pouze tehdy, když je komprese s ním lepší než bez něj. Při kompresi videa však mohou delta snímky výrazně snížit velikost snímku a používají se téměř v každém video kodeku.
Variace delta kódování, která kóduje rozdíly mezi předponami nebo příponami řetězců , se nazývá inkrementální kódování . Je zvláště efektivní pro seřazené seznamy s malými rozdíly mezi řetězci, jako je seznam slov ze slovníku .
Při síťovém přenosu s delta kódováním, kde je na každém konci komunikačního kanálu k dispozici pouze jedna kopie souboru, se používají speciální kódy pro opravu chyb ke zjištění, které části souboru se od předchozí verze změnily.
Delta kódování se používá jako předběžný krok pro mnoho kompresních algoritmů, jako je RLE , a v indexech invertovaných vyhledávačů. Povaha dat, která mají být zakódována, značně ovlivňuje účinnost komprese. Delta kódování zvyšuje kompresní poměr , když data mají malou nebo konstantní variaci (jako je gradient v obrázku); u dat generovaných generátorem náhodných čísel s rovnoměrným rozdělením se kompresní faktor příliš nezmění.
Delta kódování znemožňuje náhodný přístup k datům, protože pro přístup k prvku pole je nutné sečíst hodnoty všech předchozích. Pokud je to přesto nutné, používá se bloková verze delta kódování, ve které jsou zakódovány bloky určité délky. Poté je nutné pouze sečíst hodnoty od začátku bloku, do kterého požadovaný prvek patří, nikoli však celý soubor. Velikost bloku se volí v závislosti na aplikaci, obvykle na základě výsledků časování.
Je třeba rozlišovat mezi delta kódováním a rozdílovým kódováním . Delta kódování najde rozdíl mezi prvky stejné sekvence, zatímco rozdílové kódování porovnává dva různé zdroje dat a ukazuje rozdíly mezi nimi. Kódování rozdílů je implementováno ve standardní unixové utilitě diff a také pro snížení množství internetového provozu v protokolu HTTP podle RFC 3229 .
Následující kód C implementuje jednoduchou formu místního delta kódování a dekódování:
void delta_encode ( unsigned char * buffer , int length ) { unsigned char last = 0 ; for ( int i = 0 ; i < délka ; i ++ ) { unsigned char current = buffer [ i ]; buffer [ i ] = aktuální - poslední ; poslední = aktuální ; } } void delta_decode ( unsigned char * buffer , int length ) { unsigned char last = 0 ; for ( int i = 0 ; i < délka ; i ++ ) { unsigned char delta = buffer [ i ]; buffer [ i ] = delta + poslední ; poslední = vyrovnávací paměť [ i ]; } }Dokumentace:
Ve funkci delta_encode: *funkce bere pole a délku pole jako argumenty, pokud délka nebyla předána, pole se nezpracuje *Proměnné current jsou inicializovány pro uložení posledního prvku a last pro uložení posledního čísla. *inicializace smyčky, kde i je čítač. V cyklu *uložení znaku na čísle i v poli *vypočítejte rozdíl mezi číslem prvku i a i-1, první prvek se nemění, a přiřaďte rozdíl tomuto prvku *změňte hodnotu last na hodnotu prvku i před změnou Ve funkci delta_decode *inicializace proměnné pro uložení posledního znaku *inicializace smyčky, kde i je čítač Ve smyčce: *přidání hodnoty předchozího prvku k tomuto prvku *uložte hodnotu tohoto prvku| Kompresní metody | |||||||
|---|---|---|---|---|---|---|---|
| Teorie |
| ||||||
| Bezztrátový |
| ||||||
| Zvuk |
| ||||||
| snímky |
| ||||||
| Video |
| ||||||
| Systémy řízení verzí ( kategorie ) | |
|---|---|
| Pouze místní | |
| Klient-server | |
| Distribuováno | |