Komprese dat

Vypracoval: Radek Lano

Kódování dat s cílem zmenšit jejich objem odstranením zbytecné informace.
Data musí být možno obnovit dekódovacím algoritmem.

Základní rozdelení
bezztrátová: obnovená data jsou identická originálu
ztrátová: obnovená data jsou „rozumnou“ aproximací originálu

Funkce komprese
úspora pameti
zmenšení objemu dat pred jejich prenosem (komunikace)

Vyjádrení úspešnosti komprese
délka vstupních dat ... t bajtu
délka komprimovaných dat ... l bajtu (L bitu)
míravzorecpríklad
kompresní pomerl / t * 100%36%
kompresní faktort : l3:1
relativní komprese(t - l) / t * 100%64%
bpc (bits per character)L / t2.92 bitu

Bezztrátová komprese

Užívá se pri kompresi textových dokumentu.

Základní pojmy
Abeceda = konecná množina znaku.
Slovo (retezec, zpráva) nad abecedou A = konecná posloupnost znaku z A.
Pocet techto znaku nazýváme délkou slova (znacení |s|).
Množinu všech slov nad abecedou A znacíme A*.
Bud dána vstupní abeceda A1 a výstupní abeceda A2.
Kód = funkce f: A1* -> A2*.
Je-li funkce prostá, kód je jednoznacne dekódovatelný.

Typická strategie kódování
Vstupní retezec S rozdelíme na fráze (podretezce): S = S1...Sk.
Urcíme kódová slova f(S1),...,f(Sk).
Výsledná zakódovaná zpráva: f(S) = f(S1) f(S2) ... f(Sk).

Príklad
A1 ={a,b,c,d,e,f} A2 = {0,1}

Kód s pevnou délkou fráze a pevnou délkou kódového slova.
frázeabcdef
kódové slovo000001010011100101
Vstup: abae   Výstup: 000001000100

Kód s pevnou délkou fráze a promennou délkou kódového slova.
frázeabcdef
kódové slovo010110011111011100
Vstup: abae   Výstup: 010101101

 Slovo s' je predponou slova s = a1 a2 ... an, je-li s' = a1 a2 ... ak pro nejaké k (1≤k≤n).
Prefixový kód = žádné kódové slovo není predponou jiného kódového slova.
Každý prefixový kód (s dvouprvkovou výstupní abecedou) lze znázornit binárním stromem = prefixový strom.
Máme-li zajištenu prefixovou vlastnost kódu, není treba speciální oddelovac znaku ve výstupní abecede.

Statistické metody

Využívají toho, že nekteré znaky vstupní abecedy se v kódované zpráve vyskytují casteji.
Historický príklad: Morseova abeceda

Shannon-Fanuv kód

Claude Shannon, R.M.Fano (1949)
Situace: Je dána abeceda A a zpráva Z nad touto abecedou. Pro každý znak známe jeho cetnost f(znaku) = # výskytu znaku v Z.

Algoritmus
Usporádej znaky abecedy A dle jejich cetností.
Rozdel posloupnost znaku na dve cásti tak, aby se soucet cetností znaku v 1.cásti co nejméne lišil od souctu cetností znaku ve 2. cásti.
Kódová slova znaku z 1.cásti budou zacínat 0, kódová slova znaku z 2.cásti budou zacínat 1.
Kroky 2 a 3 aplikuj rekurzivne na každou ze 2 cástí.
Proces delení pokracuje tak dlouho, dokud každá cást neobsahuje jediný znak.

Príklad
Pro prehlednost jsou cetnosti od nejvetší po nejmenší.
znakabcde
cetnost98632

znakabcde
kódové slovo000110110111

Huffmanuv kód

David Huffman (1951)
Huffmanuv kód je optimální prefixový kód.
Situace: Je dána abeceda A a slovo S nad touto abecedou. Pro každý znak známe jeho cetnost f(znaku) = # výskytu znaku v S.
Huffmanuv kód se dosud používá v kombinaci s jinými algoritmy (napr. RLE pro komprimaci faxovaných dokumentu).

Statický model

 Pozorování
Pro každý optimální prefixový kód musí mít znaky s vetší cetností stejne dlouhá ci kratší kódová slova než znaky s menší cetností.
Pro libovolné dva znaky s nejmenšími cetnostmi existuje optimální prefixový kód, v nemž mají tyto znaky kódová slova o stejné délce, která se liší pouze v posledním bitu.

 Konstrukce Huffmanova stromu
Vstup: Množina znaku M, které se vyskytují ve vstupním slove. Cetnosti znaku (f(znaku) nenulová pro každý znak vstupního slova).

n := |M|
for i := 1 to n-1
  do
    vytvor nový vrchol v
    x := levý-syn(v) := ExtractMin(M)
    y := pravý-syn(v) := ExtractMin(M)
    f(v) := f(x) + f(y)
    Insert(M,v)
  od
return ExtractMin(M).

Príklad Huffmanova stromu
Huffmanuv strom není urcen jednoznacne!
znakabcde
cetnost4020201010

 Implementacní poznámky
Napsat funkce pro bitový vstup a výstup.
Ošetrit problém pretecení.
Pri dekompresi musí dojít k rekonstrukci stromu (stejný jako pri konstrukci).

Adaptivní Huffmanuv kód - algoritmus FGK

Faller(1973), Gallagher(1978), Knuth(1985).

Adaptivní model

 Kódování poprvé nactených znaku
1. rešení: Pri pocátecní inicializaci jsou do Huffmanova stromu vloženy všechny znaky vstupní abecedy, každý s cetností 1.
2. rešení: Pri pocátecní inicializaci je do Huffmanova stromu vložen speciální znak ESC. První výskyt znaku z je kódován jako Huffmanuv kód znaku ESC, následovaný znakem z. Poté je do Huffmanova stromu vložen nový list, odpovídající znaku z.

Aktualizace Huffmanova stromu
if v je sourozenec vrcholu ESC then
  vymen v s listem, který má nejvyšší poradí mezi vrcholy se stejnou váhou jako v
  v.váha++; v := otec(v)
fi
while v <> koren-stromu do
  vymen v s vrcholem, který má nejvyšší poradí mezi vrcholy se stejnou váhou jako v (vymení se celé podstromy)
  v.váha++; v := otec(v)
od
Je-li z poslední znak, lze ho uložit prímo do vrcholu ESC.

Algoritmus kódování
Inicializuj Huffmanuv strom (T)
repeat
  read(znak)
  if první výskyt znaku then
    write(kód(ESC))
    write(znak)
  else
    write(kód(znak))
  fi
  aktualizuj strom (T,znak)
until znak <> EOF

Algoritmus dekódování
Inicializuj Huffmanuv strom (T)
vrchol := koren_stromu
repeat
  while vrchol není list do
    read(bit)
    if bit = 0 then
      vrchol := vrchol.levý_syn
    else
      vrchol := vrchol.pravý_syn
    fi
  od
  if vrchol.znak = ESC then
    read(znak)
  else
    znak := vrchol.znak
  fi
  if znak <> EOF then
    zapiš znak na výstup
    AktualizujStrom(T,znak)
  fi
until znak = EOF

Kanonický Huffmanuv kód

RLE (Run-Length Encoding)

Jedna z nejjednodušších komprimacních metod. Predpokládá že se za sebou opakují stejné znaky. Na výstup posílá vždy jeden znak a pocet opakování znaku.

Príklad
Vstup: xxxxxxRRRRoooPPP   Výstup: 6x4R3o3P

Aritmetické kódování

C.Shannon (1948)
P.Elias (1960?), Jelinek(1968)
Pasco, Rissanen (1976)
Pennebaker, Mitchell,Langdon,Arps (1988)
Q-kodér (IBM)
Witten,Neal,Cleary (1987)
Moffat,Neil,Witten (1998)

Aritmetické kódování reprezentuje zprávu jako podinterval intervalu <0,1).
Na zacátku uvažujeme celý tento interval. Jak se zpráva prodlužuje, zpresnuje se i výsledný interval a jeho horní a dolní mez se k sobe približují.
Cím je kódovaný znak pravdepodobnejší, tím se interval zúží méne a k zápisu delšího (to znamená hrubšího) intervalu stací méne bitu.
Na konec stací zapsat libovolné císlo z výsledného intervalu.

Algoritmus kódování
Zjištení pravdepodobností P(i) výskytu jednotlivých znaku ve zdrojovém souboru.
Spoctení príslušných kumulativních pravdepodobností K(0)=0, K(i)=K(i-1)+P(i-1) a rozdelení intervalu <0,1) na podintervaly I(i) odpovídající jednotlivým znakum (serazeným podle abecedy), aby délky techto intervalu vyjadrovaly pravdepodobnosti príslušných znaku: I(i) = <K(i), K(i+1))
Uložení použitých pravdepodobností
Vlastní komprese:
Zacínáme s intervalem I = <0, 1): oznacme jeho dolní mez D(I), horní H(I) a délku intervalu L(I) = H(I) - D(I).
while (!EOF)
{
  read(i)
  I = <D(I)+K(i)*L(I), D(I)+K(i+1)*L(I))
}
write(D(I))

Algoritmus dekódování
Rekonstrukce použitých pravdepodobností
Vlastní dekomprese:
read(X) //precteme uložené reálné císlo
while (není obnovena celá zpráva)
{
  najdeme i, aby X bylo v <K(i), K(i+1))
  write(i)
  X = (X - K(i)) / P(i)
}

Softwarová realizace
Výše uvedený algoritmus je (vzhledem k práci s reálnými císly) v programátorské praxi nepoužitelný, je tedy nutné upravit ho tak, aby pracoval pouze s císly v pevné rádové cárce.
Nahrazení reálných pravdepodobností císly v pevné rádové cárce žádné vetší problémy neprinese (je treba pouze ošetrit, aby príliš malé pravdepodobnosti nepodtekly do nuly). Výsledný kód pak nemusí být optimální, ale pokud dekompresor použije stejnou reprezentaci, bude všechno OK.
Pri reprezentaci hranic aktuálního intervalu to však již tak jednoduché není: velmi brzy by totiž díky zaokrouhlovacím chybám horní a dolní mez intervalu splynuly a pak by zprávu již nikdo nemohl obnovit.
Pri kompresi se horní a dolní mez neustále približují, to ovšem znamená, že na zacátku (významnejší cást) desetinného zápisu obou mezí bude cím dál tím víc císlic shodných a dále již nemenných (až na patologické prípady jako 0.29999... a 0.30000...). Tyto císlice tedy mužeme zapsat na výstup a upravit meze intervalu, aby nedocházelo ke ztráte presnosti.

Algoritmus pracující s císly v pevné rádové cárce (císla jsou v binárním desetinném zápisu)
Zacínáme s intervalem I = <.00000, .11111>.
Oznacme jeho horní a dolní mez H(I) a D(I) a délku intervalu L(I) = H(I) - D(I).
while (!EOF)
{
  read(i)
  I = <D(I)+K(i)*L(I), D(I)+K(i+1)*L(I))
  switch
  {
    1. D=.0xxx; H=.0yyy -> D=.xxx0, H=.yyy1, write(0)
    dokud horní i dolní mez I zacíná .0...
    zapíšeme spolecnou 0 na výstup,
    posuneme zbývající cásti mezí o jedno místo vlevo
    a na uvolnené místo v dolní mezi napíšeme 0 a v horní 1
    while (shift) { write(1); shift--; }
    Pokud shift!=0 zapíšeme také shift jednotek (spolecná 0)
    a vynulujeme shift.
    2. D=.1xxx; H=.1yyy -> D=.xxx0, H=.yyy1, write(1)
    while (shift) { write(0); shift--; }
    3. D=.01xxx; H=.10yyy -> D=.0xxx0, H=.1yyy1, shift++
    "Patologický prípad:" dokud dolní mez zacíná .01... a horní .10...
    vypustíme 1 v dolní a 0 v horní mezi,
    zprava doplníme jako obvykle: .0...0 a .1...1
    a zvýšíme cítac: shift++
    Následující možnosti jsou uvedeny jen pro úplnost,
    v programu je není potreba nijak ošetrovat.
    4. D=.00xxx; H=.10yyy nebo D=.01xxx, H=.11yyy
    meze jsou od sebe vzdáleny alespon 1/4 a ke ztráte presnosti nedojde
    5. D=.1xxx, H=.0yyy
    nemuže nastat (musí být D<H)
  }
  write(D(I))
}

Tato implementace bude tím presnejší (a tím i výsledný kód kratší), cím bude používaný interval mít více rozlišitelných bodu. Proto dolní mez doplnujeme nulami a horní jednickami.
Aby mohla probehnout dekomprese, je nutné zapsat ješte nekolik bitu tak, aby zapsané císlo bylo v daných mezích. Na konci kódování (po expanzi intervalu) je jiste D < 1/2 < H. Zapíšeme-li tedy na výstup ješte jednu binární jednicku a za ní samé nuly, dekomprese probehne správne (do zkomprimovaného souboru pritom samozrejme není potreba nuly na konci vubec zapisovat - pri dekompresi si je muže program "domyslet").
Pri dekompresi nelze poznat konec souboru, je tedy potreba ješte uložit délku puvodního souboru nebo k bežne kódovaným znakum pridat ješte jeden speciální, který bude znamenat konec souboru (tím se zhorší kompresní pomer, ale lze ukázat, že jen velmi málo).
Postup dekomprese se až na nahrazení reálných císel císly v pevné rádové cárce nezmení.

Slovníkové metody

Slovníkové metody využívají faktu, že nekterá slova se ve vstupním retezci vyskytují casteji.
Místo kódování jednotlivých znaku se kódují celá slova (skupiny znaku).
Opakující se slova ukládáme do slovníku. Ve výstupním retezci jsou pak tato slova nahrazena jim odpovídajícími kódovými slovy.

Metoda LZ78 (Lempel, Ziv, 1978)
Slovník si mužeme predstavit jako tabulku, kde je v každém rádku uvedena fráze a jí odpovídající kódové slovo (císlo). Slovník musí splnovat podmínku: Je-li ve slovníku uložena nejaká fráze, pak jsou ve slovníku uloženy všechny její prefixy.

Na zacátku kódování i dekódování uložíme do slovníku všechny znaky vstupní abecedy. Tím jsme do slovníku uložili všechny jednoznakové zacátky všech možných retezcu.
Ze vstupního retezce precteme nejdelší podretezec, který se zároven vyskytuje jako fráze ve slovníku. Do výstupního retezce zapíšeme jemu odpovídající kódové slovo. A do slovníku zaradíme frázi, která vznikne z práve precteného slova pripojením následujícího znaku z ze vstupního retezce. Dále kódujeme vstupní retezec od znaku z (vcetne) pomocí rozšíreného slovníku. To provádíme stejným zpusobem, dokud není zakódován celý vstupní retezec.

To, že nalezená fráze je nejdelší možná, tj. nelze ji prodloužit, nám zarucuje prefixová vlastnost slovníku: neexistuje žádné prodloužení fráze takové, že by se výsledný retezec vyskytoval ve slovníku.

Pokud chceme pridat frázi do slovníku a on je již zcela naplnen, mužeme prestat slovník dále rozširovat nebo provedeme reorganizaci slovníku a tím uvolníme místo ve slovníku. Reorganizovat slovník znamená vypustit nekteré jeho fráze. Napríklad takové, které se vyskytovaly málo nebo se nevyskytly již delší dobu. Po reorganizaci musí mít slovník stále prefixovou vlastnost.

Zakódovaný retezec je posloupnost kódových slov (císel), která odpovídají ve slovníku príslušným frázím. Pri dekódování musíme slovník obhospodarovat stejným zpusobem, jako pri kompresi.

Predpokládejme, že máme již dekódováno slovo S1. Ze vstupního retezce precteme další kódové slovo. Pomocí slovníku jej dekódujeme a dostaneme slovo S2. Do slovníku musíme pridat frázi, která vznikne tak, že na konec slova S1 pripojíme první znak slova S2. V prípade, že je slovník plný, provedeme stejnou operaci jako pri kompresi: pokud jsme slovník reorganizovali, musíme jej nyní reorganizovat stejným zpusobem.

Fráze je do slovníku zarazována se zpoždením: chybí v nem vždy poslední fráze. Problém nastane, pokud pri kompresi byla v jednom kroku do slovníku zapsána fráze a v následujícím kroku byla okamžite použita pro zakódování dalšího slova. Pri dekompresi nebude tato fráze vcas do slovníku zarazena. Vstupní retezec pri jednom kroku kódování tedy vypadá takto: zSzSz, kde z je znak vstupní abecedy, S je slovo, fráze zS je již ve slovníku obsažena a fráze zSz ješte ve slovníku není. Pri kompresi precteme slovo zS a do slovníku zaradíme slovo zSz. V dalším kroku zakódujeme retezec zSz pomocí fráze, kterou jsme práve vložili do slovníku. Pri dekompresi ale ve chvíli, kdy chceme dekódovat kód retezce zSz, jej ješte nemáme zarazen do slovníku. Z výše uvedeného má chybející fráze ve slovníku tvar zSz, kde zS je naposledy kódované slovo.

Príklad
Vstupní abeceda A = {a,b,c}
Vstup abcabcabcbcba   Výstup 1 2 3 4 6 5 9 1
Slovník je po zpracování celého vstupního retezce zobrazen v tabulce.

Frázeabcabbccaabccabbcbbcba
Kódové slovo12345678910

 V praxi se implementace tohoto algoritmu liší velikostí použitého slovníku a zpusobu vyhledávání v nem. Nejcasteji se používá slovník o 212 položkách.

Metoda LZ77
Tato metoda využívá jako slovníku cást již zpracovaného vstupního retezce.
Predstavme si, že máme jakési prohlížecí okno, ve kterém vidíme cást již zpracované cásti vstupního retezce o velikosti N (typicky N=212). Dále máme aktuální okno o velikosti M (typicky M=24), ve kterém je práve kódované slovo. Aktuální okno ve vstupním retezci bezprostredne navazuje na prohlížecí okno. Okny pohybujeme a tím meníme obsah slovníku.

Na zacátku vyplníme prohlížecí okno mezerami a v aktuálním okne bude prvních M znaku vstupního retezce.
Ve vstupním retezci hledáme dvojici nejdelších, ale kratších než M, shodných podretezcu A a B takových, že první znak retezce A je v prohlížecím okne a B zacíná na prvním znaku v aktuálním okénku. B je fráze, kterou zakódujeme pomocí polohy A v prohlížecím okne. Kódové slovo fráze B je tvoreno trojicí (i, j, z), kde i je vzdálenost (mereno poctem znaku) prvního znaku retezce A od zacátku aktuálního okénka, j je délka retezce B a z je znak bezprostredne následující za retezcem B. Po zapsání kódového slova do výstupního retezce se obe okna posunou o j+1 znaku doprava. Jestliže neexistuje retezec A požadovaných vlastností, zapíšeme do výstupního retezce trojici (0, 0, z), kde z je první písmeno aktuálního okénka.

Príklad
Vstupní abeceda A = {a,b,c}, N=24, M=22
Vstup aababcabababbcabcaacbcbcbbab
Výstup (0, 0, a) (1, 1, b) (2, 2, c) (5, 4, a) (2, 1, b) (8, 3, c) (3, 1, a) (3, 1, b) (2, 4, b) (12, 2, Æ)

 Metoda LZSS (Lempel, Ziv, Storer, Szymanski; 1982)
Vylepšená metoda LZ77.
Nedojde-li ke shode slov délky aspon dve, komprese se nevyplatí. V prípade, že se zacátek retezce v aktuálním okénku shoduje s nejakým úsekem v prohlížecím okénku alespon ve dvou znacích, pak do výstupního retezce zapisujeme kódovací trojici, jinak pouze opíšeme první znak z aktuálního okénka.
Pri dekódování je treba rozlišit, zda se má precíst trojice nebo jediný znak.

Použitá literatura

Tomáš Dvorák: Algoritmy komprese dat
T. Novák: Algoritmy komprese dat
Jaromír Malenko: Slovníkové metody komprese dat
Tomáš Warlik: Metody komprimace dat

Další odkazy

Robert Machácek: Komprese dat (slovníkové metody)
Štepán Hrbek: Bežné algoritmy komprese dat, zvlášt Burrows-Wheeler
Hardwarová akcelerace komprimace
Matej Tenkl: Komprimace grafických údaju