Kódování delta - Delta encoding

Delta kódování je způsob ukládání nebo přenosu dat ve formě rozdílů (delt) mezi sekvenčními daty spíše než kompletními soubory; obecněji se to nazývá rozdílováním dat . Delta kódování se někdy nazývá delta komprese , zejména tam, kde jsou vyžadovány archivní historie změn (např. V softwaru pro kontrolu revizí ).

Rozdíly jsou zaznamenány v diskrétních souborech nazývaných „delty“ nebo „rozdíly“. V situacích, kde jsou rozdíly malé - například změna několika slov ve velkém dokumentu nebo změna několika záznamů ve velké tabulce - kódování delta výrazně snižuje redundanci dat. Sbírky unikátních delt jsou podstatně prostorově efektivnější než jejich nekódované ekvivalenty.

Z logického hlediska je rozdílem mezi dvěma datovými hodnotami informace potřebné k získání jedné hodnoty od druhé - viz relativní entropie . Rozdíl mezi identickými hodnotami (za určité ekvivalence ) se často nazývá 0 nebo neutrální prvek.

Jednoduchý příklad

Snad nejjednodušším příkladem je ukládání hodnot bytů jako rozdílů (delt) mezi sekvenčními hodnotami, nikoli samotnými hodnotami. Místo 2, 4, 6, 9, 7 bychom tedy uložili 2, 2, 2, 3, −2. To snižuje rozptyl (rozsah) hodnot při korelaci sousedních vzorků, což umožňuje nižší využití bitů pro stejná data. Zvukový formát IFF 8SVX použije toto kódování na nezpracovaná zvuková data, než na ně použije kompresi. Bohužel ani všechny 8bitové zvukové ukázky se při kódování delta lépe nekomprimují a použitelnost kódování delta je u 16bitových a lepších samplů ještě menší. Kompresní algoritmy se proto často rozhodnou kódovat delta pouze tehdy, když je komprese lepší než bez. Při kompresi videa však delta snímky mohou výrazně snížit velikost snímků a používají se prakticky v každém kodeku pro kompresi videa .

Definice

Deltu lze definovat 2 způsoby, symetrickou deltu a směrovanou deltu . Symetrický trojúhelník může být vyjádřena jako

${\ Displaystyle \ Delta (v_ {1}, v_ {2}) = (v_ {1} \ setminus v_ {2}) \ cup (v_ {2} \ setminus v_ {1}),}$

kde a představují dvě verze. ${\ displaystyle v_ {1}}$${\ displaystyle v_ {2}}$

Směřuje delta , nazývaný také ke změně, je sled operací (elementární) změny, které, když se aplikuje na jednu verzi , se získá další verze (všimněte Korespondenční protokolů transakcí v databázích). V počítačových implementacích mají obvykle podobu jazyka se dvěma příkazy: kopírování dat z v1 a zápis doslovných dat . ${\ displaystyle v_ {1}}$${\ displaystyle v_ {2}}$

Varianty

Variace kódování, která kóduje delta rozdíly mezi předpony nebo přípony z řetězců se nazývá inkrementální kódování . Je zvláště účinný pro seřazené seznamy s malými rozdíly mezi řetězci, například seznam slov ze slovníku .

Problémy s implementací

Povaha kódovaných dat ovlivňuje účinnost konkrétního kompresního algoritmu.

Kódování Delta funguje nejlépe, když data mají malé nebo konstantní odchylky; u netříděné sady dat může být s touto metodou možná malá až žádná komprese.

Při přenosu kódovaném delta po síti, 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 kontrolu chyb, které zjišťují, které části souboru se od jeho předchozí verze změnily. Například rsync používá algoritmus postupného kontrolního součtu na základě kontrolního součtu adler-32 Marka Adlera .

Ukázka kódu C.

Následující kód C provádí jednoduchou formu kódování a dekódování delty na sekvenci znaků:

void delta_encode(unsigned char *buffer, int length)
{
    unsigned char last = 0;
    for (int i = 0; i < length; i++)
    {
        unsigned char current = buffer[i];
        buffer[i] = current - last;
        last = current;
    }
}

void delta_decode(unsigned char *buffer, int length)
{
    unsigned char last = 0;
    for (int i = 0; i < length; i++)
    {
        unsigned char delta = buffer[i];
        buffer[i] = delta + last;
        last = buffer[i];
    }
}

Příklady

Kódování delta v HTTP

Dalším příkladem použití kódování delta je RFC 3229 , „Delta encoding in HTTP“, který navrhuje, aby servery HTTP mohly odesílat aktualizované webové stránky ve formě rozdílů mezi verzemi (deltas), které by měly snížit internetový provoz, protože většina stránky se v průběhu času pomalu mění, než aby se opakovaně kompletně přepisovaly:

Tento dokument popisuje, jak lze kódování delta podporovat jako kompatibilní rozšíření HTTP/1.1.

Mnoho požadavků HTTP (Hypertext Transport Protocol) způsobuje načítání mírně upravených instancí prostředků, pro které již klient má položku mezipaměti. Výzkum ukázal, že takovéto modifikační aktualizace jsou časté a že úpravy jsou obvykle mnohem menší než skutečná entita. V takových případech by HTTP efektivněji využíval šířku pásma sítě, kdyby mohl přenášet minimální popis změn, nikoli celou novou instanci zdroje.

[...] Věříme, že by bylo možné podporovat rsync pomocí rámce „manipulace s instancemi“ popsaného dále v tomto dokumentu, ale toto nebylo podrobně rozpracováno.

Navrhovaný rámec založený na rsync byl implementován do systému rproxy jako dvojice proxy serverů HTTP. Stejně jako základní implementace založená na vcdiff se oba systémy používají jen zřídka.

Kopírování Delta

Kopírování Delta je rychlý způsob kopírování částečně změněného souboru, pokud je v cílovém umístění přítomna předchozí verze. Při kopírování delta se zkopíruje pouze změněná část souboru. Obvykle se používá v softwaru pro zálohování nebo kopírování souborů , často pro úsporu šířky pásma při kopírování mezi počítači přes soukromou síť nebo internet. Jedním pozoruhodným příkladem open-source je rsync .

Online záloha

Mnoho online zálohovacích služeb používá tuto metodiku, často známou jednoduše jako delta , aby svým uživatelům poskytlo předchozí verze stejného souboru z předchozích záloh. To snižuje související náklady, a to nejen v množství dat, která musí být uložena jako různé verze (protože celá každá změněná verze souboru musí být nabídnuta uživatelům k přístupu), ale také náklady na nahrávání (a někdy stahování) každého souboru, který byl aktualizován (pouze menší delta musí být použita, nikoli celý soubor).

Aktualizace Delta

U velkých softwarových balíků se mezi verzemi obvykle mění málo dat. Mnoho prodejců se rozhodlo použít přenosy delta, aby ušetřily čas a šířku pásma.

Diff

Diff je program pro porovnávání souborů, který se používá hlavně pro textové soubory. Ve výchozím nastavení generuje symetrické delty, které jsou reverzibilní. Dva formáty používané pro softwarové opravy , kontextové a sjednocené , poskytují další kontextové řádky, které umožňují tolerovat posuny v číslech řádků.

Git

Systém řízení zdrojového kódu Git využívá kompresi delta v pomocné operaci „ git repack “. Objekty v úložišti, které ještě nebyly komprimovány delta („volné objekty“), jsou porovnány s heuristicky zvolenou podmnožinou všech ostatních objektů a společná data a rozdíly jsou zřetězeny do „balíkového souboru“, který je poté komprimován pomocí konvenčních metody. V běžných případech použití, kdy se zdrojové nebo datové soubory mění postupně mezi potvrzeními, to může mít za následek významné úspory místa. Operace opětovného zabalení se obvykle provádí jako součást procesu „ git gc “, který se spouští automaticky, když počet uvolněných objektů nebo souborů balíku překročí nakonfigurované prahové hodnoty.

Formát je dokumentován na stránce formátu balíčku dokumentace Git. Implementuje cílenou deltu.

VCDIFF

Jeden obecný formát pro směrované delta kódování je VCDIFF, popsaný v RFC 3284 . Mezi bezplatné softwarové implementace patří Xdelta a open-vcdiff.

GDIFF

Generic Diff Format (GDIFF) je další směrovaný delta kódovací formát. Byl předložen W3C v roce 1997. V mnoha případech má VCDIFF lepší kompresní poměr než GDIFF.

bsdiff

Bsdiff je binární program diff využívající třídění podle přípon . U spustitelných souborů, které obsahují mnoho změn v adresách ukazatelů, funguje lépe než kódování typu „kopírovat a doslovně“ typu VCDIFF. Záměrem je najít způsob, jak generovat malý rozdíl, aniž byste museli analyzovat kód sestavy (jako v Google Courgette). Bsdiff toho dosáhne tím, že umožní "kopírovat" shody s chybami, které jsou poté opraveny pomocí extra "add" pole bajtových rozdílů. Protože toto pole je většinou buď nulové nebo opakované hodnoty pro změny posunu, zabírá po kompresi málo místa.

Bsdiff je užitečné pro aktualizace delta. Google používá bsdiff v Chromu a Androidu. Funkce deltarpm ve Správci balíčků RPM je založena na silně upraveném bsdiffu, který může pro shodu použít hashovací tabulku. FreeBSD také používá bsdiff pro aktualizace.

Od vydání bsdiff 4.3 v roce 2005 pro něj byla vytvořena různá vylepšení nebo opravy. Google spravuje více verzí kódu pro každý ze svých produktů. FreeBSD využívá mnoho změn kompatibilních s Googlem, zejména opravu zranitelnosti a přechod na rychlejší divsufsorttřídění přípon. Debian má v programu řadu vylepšení výkonu.

ddelta je přepis bsdiff navržený pro použití v aktualizacích Debianu delta. Mezi další vylepšení efektivity používá posuvné okno ke snížení nákladů na paměť a CPU.

Viz také

• Rozdíl dat
• Prokládané delty
• Systém řízení zdrojového kódu
• Problém s opravou řetězce na řetězec
• Xdelta : kodér delta s otevřeným zdrojovým kódem

Reference

externí odkazy

• RFC 3229 - Delta Encoding v HTTP