Dokumentografické informační systémy

 

Komprese

 

Koprese využívá faktu, že informace, obsažená v jednom znaku textu, je menší, než množství bitů, kterými je běžně reprezentována. Objem dat, který text v paměti zabírá je možné snížit, pokud se zvolí vhodnější reprezentace.

 

Definice:

 

Kódem rozumíme trojici

 

K=(A,C,f), kde

 

A={a1, a2, ..., an} je zdrojová abeceda, |A|=n

C={c1, c2, ..., cm} je cílová abeceda, |C|=m, obvykle C={0,1}

f: A® C+ je prosté kódové zobrazení znaků z abecedy A do prostoru slov v abecedě C.

 

funkci f lze rozšířit na kódování zpráv (textů nad abecedou A) takto:

 

f(ai1ai2...aik) def= f(ai1)f(ai2)...f(aik)

 

Poznámka:

 

Pojem kód se někdy používá pro obor hodnot funkce f, tedy pro množinu kódových slov.

 

Definice:

 

Kód K je jednoznačně dekódovatelný, právě když pro každý řetěz YÎ C+ existuje nejvýše jeden řetěz XÎ A+ takový, že f(X)=Y.

 

Příklad:

 

Kód K=({0,1,2,3},{0,1},f), kde f(0)=0, f(1)=1, f(2)=10, f(3)=11 - t.j. binární kódování čísel - není jednoznačně dekódovatelný, protože

 

f(21)=101=f(101)

 

Definice:

 

Kód K je prefixový, právě když žádné kódové slovo f(ai) není vlastním prefixem jiného kódového slova f(aj).

 

Příklad:

 

Kód K=({0,1,2,3},{0,1},f), kde f(0)=0, f(1)=10, f(2)=110, f(3)=111 je prefixový.

 

Definice:

 

Kód K je blokový (délky k), právě když mají všechna kódová slova délku k.

 

Příklad:

 

Kód K=({0,1,2,3},{0,1},f), kde f(0)=00, f(1)=01, f(2)=10, f(3)=11 je blokový kód (délky 2).

 

Tvrzení:

 

Každý blokový kód je zároveň kódem prefixovým.

 

Tvrzení:

 

Každý prefixový kód je jednoznačně dekódovatelný.

 

Definice:

 

Kód K je dekódovatelný po znacích, pokud je možné po přečtení prvních znaků tvořících kód f(ai) jednoznačně zdrojový znak ai.

 

Příklad:

 

Kód K=({a,b,c,d},{0,1},f), kde f(a)=0, f(b)=01, f(c)= 011, f(d)=111 není dekódovatelný znak po znaku, ale je jednoznačně dekódovatelný. Pokud je zakódovaný text ve tvaru

 

011111111...

 

je nutné přečíst celou zprávu, aby bylo možné rozhodnout, zda kód prvního znaku je 0, 01, nebo 011.

 

Tvrzení:

 

Dekódovatelné znak po znaku jsou právě prefixové kódy.

 

Entropie a Redundance

 

Definice:

 

Nechť A={a1, a2, ..., an} je zdrojová abeceda. Nechť pravděpodobnost výskytu znaku ai v textu je rovna hodnotě pi.

 

P(A) = (p1, p2, ..., pn) nazveme pravděpodobnostním rozdělením A.

 

Definice:

 

Entropie (míra informace) znaku ai v textu je rovna hodnotě bitů.

 

Tedy čím je výskyt zanku v textu méně pravděpodobný, tím více informace jeho výskyt v textu nese.

 

Definice:

 

 

 

 

Definice:

 

Nechť kód K(A,C,f) přiřazuje znakům aiÎ A kódová slova délek |f(ai)| = di.

 

 

 

Z teorie informace plyne, že vždy platí

 

 

Definice:

 

Kód je optimální, pokud má v dané třídě kódů minimální redundanci.

 

Kódování přirozených čísel

 

Kódování čísel přináší některé problémy, neboť jich je nekonečně mnoho (kódujeme čísla, nikoli jejich zápis). Je potřeba navrhnout kódování shopné zobrazit nekonečně mnoho čísel pomocí cílové abecedy tak aby kódovaná zpráva byla jednoznačně dekódovatelná po jednotlivých číslech.

 

Fibonacciho kódování.

 

Fibonnaciiho čísla Fi (řádu 2) jsou rekurzivně definována takto:

 

 

Začátek této nekonečné řady tedy vypadá následovně:

 

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

 

Fibonacciho kódování je založeno na myšlence, že každé číslo lze zapsat jako součet některých fibonacciho čísel řádu dvě.

 

Např. 10010=3+8+89=F11+F5+F3

 

Pokud se pro binární zápis čísla použijí místo mocnin čísla 2 právě Fibonacciho čísla, dostaneme zápis

 

10010=1*F11+0*F10+0*F9+0*F8+0*F7+0*F6+1*F5+0*F4+1*F3+0*F2+0*F1=10000010100F

 

Zápis není jednoznačný díky definici Fibonacciho čísel,

 

Např. 10010=1+2+3+5+34+55=F10+ F9+F4+ F3+F2+F1=1100001111F

 

Existuje však právě jeden zápis, ve kterém se nevyskytují dvě jedničky za sebou.

 

Definice:

 

Nechť kde

Fibonacciho kódem čísla n je kódové slovo , a proto se vynechává. Přidání jedničky na konec kódového slova zaručuje to, že kód je prefixový (v žádném kódovém slově se uprostřed slova dvě jedničky za sebou nevyskytují).

 

Kódy čísel 1 až 9 jsou uvedeny v následující tabulce.

 

 

Protože fibonacciho čísla rostou exponenciálně o základu přibližně , znamená to, že délka kódu pro číslo N je rovna přibližně .

 

Eliasovy kódy.

 

Elias definoval řadu kódů.

 

 

 

Kód alfa je příliš dlouhý.

 

 

Binární kód není jednoznačně dekódovatelný.

 

 

Kód beta začíná vždy jedničkou a je proto možné ji vynechat

 

 

Ani modifikovaný binární kód není jednoznačně dekódovatelný.

 

 

 

Tento kód je sice jednoznačně dekódovatelný, ale je ternární.

 

 

Gama kód je kompozicí unárního a modifikovaného binárního kódu.

 

Každý bit kódu je vložen mezi dva bity kódu

 

Silně značené bity jsou z kódu , slabě značené bity z kódu .

Výhodné je, že jazyk je regulární.

 

 

Přeuspořádáním bitů kódu gama vznikne kód

 

 

 

Silně značené bity jsou z kódu , slabě značené bity z kódu .

Poslední jedničku kódu lze chápat jako první jedničku kódu který je podtržen.

 

Tento kód je pro člověka lépe čitelný, není regulární.

 

 

Delta kód je obdobou modifikovaného gama kódu, ale pro reprezentaci délky kódu používá kód gama.

 

 

Poslední jedničku kódu lze opět chápat jako první jedničku kódu .

 

 

Silně značené bity jsou z kódu , slabě značené bity z kódu .

 

Omega kód je výhodný pro reprezentaci velmi vysokých čísel. Tento kód lze vytvořit pomocí následujícího kódovacího algoritmu:

 

K := ‘0’;

while > 0 do

begin

K := b (N).K;

N := ;

end;

 

Každý kód je ukončen nulou. Pravá skupina číslic s výjimkou kódu pro číslo 1 reprezentuje kód b (N). Každá předcházející skupina potom reprezentuje délku následující skupiny - zmenšenou o jedna - pomocí kódu beta. První skupina má délku 2.

 

Dekódování spočívá postupném načítání beta kódů. První má délku dva, každý následující má délku určenou předchozí skupinou zvětšenou o jedničku. Čtení končí v okamžiku, kdy se jako první bit skupiny přečte nula, protože kód beta vždy začíná jedničkou. Hodnota poslední skupiny určuje velikost čísla N.

 

 

Silně značené bity jsou z kódu .

 

Kódování textu

 

Huffmanovo kódování.

 

Huffman navrhl konstrukci prefixového kódu abecedy A s nejmenší možnou redundancí.

 

Postup je popsán následující rekurzivní procedurou:

 

 

 

Příklad:

 

Konstrukce kódu pro abecedu A={u,v,w,x,y,z}

s rozložením pravděpodobností P=.

 

 

Každý vrchol je označen znakem, který reprezentuje (buď jednoduchým znakem, pokud se jedná o původní znak abecedy A - list stromu, nebo složeným, pokus jedná o znak některé redukované abecedy), a pravděpodobností výskytu v textu.

Ohodnocení hran od kořene k uzlu představuje kód příslušného znaku.

 

f(u) = 0000

f(v) = 0001

f(w) = 001

f(x) = 010

f(y) = 011

f(z) = 1

 

Poznámka:

 

Při konstrukci Huffmanova kódu lze používat četnosti znaků (počty výskytů) v textu místo pravděpodobností.

 

Poznámka:

 

Při kompresi textů v přirozeném jazyce je výhodnější (ale na druhou stranu paměťově náročnější) zvolit za informační jednotku ne znak textu, ale slovo v textu. Různých slov je podstatně více než různých znaků, (odtud paměťová náročnost), ale jejich pravděpodobnostní rozložení je nerovnoměrnější (odtud větší úspora místa na disku).

 

Modelování dat.

 

Při kompresi pracuje kompresní algoritmus s množinou údajů, například s rozložením pravděpodobností výskytů jednotlivých znaků, které umožňují vlastní kompresi provést.

Aby bylo možné data opět zrekonstruovat do původní podoby, musí mít dekompresní algoritmus k dispozici stejný model dat.

 

 

Existují tři základní možnosti, jak zajistit shodu obou modelů

 

 

Výše popsané Huffmanovo kódování patří mezi semiadaptivní algoritmy, tj. pravděpodobnostní rozložení znaků se spočte pro každý text zvlášť a kódovací strom se uloží ke komprimovaným datům. Méně často se používá ve statické podobě, kdy se všechny texty kódují pomocí stejného pravděpodobnostního rozložení.

 

Adaptivní Huffmanovo kódování.

 

Adaptivní algoritmus pro vytváření hufmannova kódu (FGK algoritmus) byl navržen autory Fallerem, Gallagerem a Knuthem.

 

FGK využívá tzv. sourozenecké vlastnosti huffmanova stromu. Uzly ve stromě lze seřadit podle neklesající pravděpodobnosti výskytu odpovídajících znaků tak, aby sourozenci vždy následovali bezprostředně za sebou.

 

Na obrázku k předchozímu příkladu je možné uzly seřadit po vrstvách zleva doprava a zdola nahoru.

 

Dostaneme uspořádání uzlů

 

u, v, uv, w, x, y, uvw, xy, uvwxy, z, uvwxyz

 

s pravděpodobnostmi postupně

 

1/32, 2/32, 3/32, 3/32, 4/32, 5/32, 6/32, 9/32, 15/32, 17/32, 32/32.

 

FGK Algoritmus pracuje s četnostmi znaků místo s pravděpodobnostmi.

 

Komprese textu používá následující algoritmus.

 

 

Dekomprese probíhá analogicky:

 

 

Je důležité aby oba algoritmy vyšly ze stejného počátečního stromu.

 

Vlastní úprava stromu sleduje větev stromu od aktualizovaného listu ke kořeni a postupně opravuje četnosti uzlů. Je však potřeba zachovat sourozeneckou vlastnost stromu. využívá se proto uspořádání uzlů dle četnosti.

 

Uzel := Zpracovaný_uzel;

while Uzel <> Root do begin

  1. Zaměň Uzel i s případným podstromem za poslední uzel dle uspořádání se stejnou četností;
  2. Zvyš četnost Uzlu o jedna {tím se neporuší uspořádání}
  3. Uzel := Předek(Uzel)

end;

 

Příklad:

 

Nechť je dán následující Huffmanův strom

 

 

Kódovaným znakem je znak z.

Znak z je zakódován jako 1011.

Protože znak z má četnost 3 jako jediný, není potřeba nic prohazovat, četnost se zvýší o jedna a postoupí se o patro výše.

 

 

Posledním uzlem s četností 5 je uzel u, je tedy potřeba provést záměnu, poté zvýšit hodnotu uzlu yz a postoupit o patro výše.

 

 

Posledním uzlem s četností 11 je uzel x, je tedy potřeba provést záměnu, poté zvýšit hodnotu uzlu yzv a postoupit o patro výše.

 

 

Není potřeba provést záměnu, stačí zvýšit hodnotu uzlu yzvwux.

 

 

Podle tohoto stromu by byl např. následující znak z kódován jako 001.

 

Na začátku není známo, jaká jednotky budou posílány. To je možné vyřešit tak, že na začátku obsahuje strom pouze jeden speciální uzel s nulovou frekvencí.

 

Pokud se ve zprávě objeví nový znak, ja zakódován jako kód nulového uzlu (na začátku prázdný kód) a uložen jako dvojice (kód_nulového_uzlu, původní_znak).

Nulový uzel získá dva potomky: jedním je uzel reprezentující nový znak a druhým nový nulový uzel.

 

Algoritmus kódováni je možné modifikovat tak, aby kódy znaků méně závisely na starých datech. Například je možné čítače četností vždy po N zakódovaných znacích vynásobit nějakým číslem p < 1.

 

Aritmetické kódování.

 

Huffmanův kód dává výsledek, kdy se redundance rovná nule pouze v případě, že pravděpodobnosti výskytu jednotlivých znaků jsou rovny záporným mocninám dvou. V jiných případech může být díky celočíselné velikosti kódů jednotlivých znaků redundance relativně vysoká.

 

Nedostatek odstraňuje aritmetické kódování, které reprezentuje textovou zprávu pomocí intervalu.

 

Na počátku je dán interval <0; 1). Každý další znak textu zmenší tento interval, přičemž málo pravděpodobné znaky (znaky z větší entropií) zmenší interval více než znaky častější.

 

Po zakódování celého textu získáme interval <L; H), který bude reprezentován libovolným číslem ležícím v tomto intervalu. Jako reprezentant se vybírá číslo s nejmensím počtem cifer (binárně).

 

 

 

zmenší na interval <L+W*cpi, L+W*(cpi+pi)).

L := L+W*cpi

W := W*pi

 

Příklad:

 

Je dána abeceda {a, b, c, d}

s pravděpodobnostmi 1/2, 1/4, 1/8, 1/8 , binárně 0.1, 0.01, 0.001, 0.001

 

 

Kódujeme text ‘abac’.

 

<0, 1) --a--> <0; 0.1) <0; 1/2)

<0, 0.1) --b--> <0.01; 0.011) <1/4; 3/8)

<0.01; 0.011) --a--> <0.01; 0.0101) <1/4; 5/16)

<0.01; 0.0101) --c--> <0.010011; 0.0100111) <19/64; 23/64)

 

nejkratším reprezentantem je číslo 0.010011, a zakódovaná zpráva má proto tvar 010011 (každé číslo z intervalu <0; 1) má celou část rovnou nule a proto je možné ji neukládat.

 

Dekódování zprávy:

 

 

Je nutné pamatovat na to, že při dekompresi je možné zužovat interval stále a generovat další a další znaky původního textu - například číslo 0 je v uvedeném příkladě reprezentantem libovolně dlouhé posloupnosti znaků a. Je tedy nutné nějakým způsobem dekodéru sdělit délku posloupnosti.

 

Potenciálním nebezpečím je vzrůstání délky mezí intervalů pří kódování nad únosnou mez, ja však možné délku mezí intervalu průběžně redukovat. Například po zakódování znaku b v uvedeném přikladu je jasné, že reprezentant intervalu musí začínat 01. Je možné tyto bity zapsat na výstup a zkrátit tak meze intervalu.

 

<0, 1) --a--> <0.0; 0.1) výstup: l

<0.0, 0.1) --b--> <0.010; 0.011) výstup: 01

<0.0; 0.1) --a--> <0.00; 0.01) výstup: 010

<0.0; 0.1) --c--> <0.0110; 0.0111) výstup: 010011

<0.0; 0.1) : :

: : :

: : :

 

Je možné také meze intervalu zaokrouhlovat na pevný počet míst, za předpokladu, že zaokrouhlování probíhá při kódování i dekódování stejně.

 

Během kódování je možné upravovat pravděpodobnosti znaků a realizovat adaptivní aritmetické kódování.

 

Kódování s konečným kontextem.

 

Při kompresi lze využit faktu, že pravděpodobnost výskytu znaků se liší v závislosti na předchozím znaku. Např. relativní pravděpodobnost výskytu znaku ‘p’ za znakem ‘k’ bude menší, než relativní pravděpodobnost výskytu znaku ‘p’ za znakem ‘o’.

 

Pokud chceme použít kontext délky k, sestrojíme konečný automat, se stavy reprezentujícími k-tice znaků abecedy.

 

Přechodová funkce

 

V každém stavu automatu je uschována informace o pravděpodobnostech výskytu znaků abecedy s uvedeným kontextem.

 

Komprese slovníků

 

Pro kompresi abecedních slovníků lze použít jednoduchou metodu POM (Prefix Omitting Method).

 

V této metodě je každé slovo w ve slovníku nahraženo dvojicí (n, suffix), kde n je počet znaků shodných s předchozím slovem ve slovníku a suffix je zbytek slova w po odtržení prvních n znaků.