Letní zábavička bezeztrátové balení

Důležité kompresní algoritmy Je léto, a tedy čas jako stvořený k zamyšlení o tom, jak je to na tom světě zaříze...


Důležité kompresní algoritmy
Je léto, a tedy čas jako stvořený k zamyšlení o tom, jak je to na tom světě
zařízeno, že něco se k balení přímo nabízí a neúspěch je téměř vyloučen,
zatímco na něčem jiném by si vylámal zuby i bzip...
Budeme se zabývat algoritmy na bezztrátovou kompresi. Takové algoritmy jsou
používány v různých archivačních programech, u nichž požadujeme přesnou
reprodukci původních dat.
Ke kompresi multimediálních dat se používají ztrátové metody, kde stačí, aby
reprodukovaná data dostatečně přesně aproximovala ta původní (například na
fotografii si ani nevšimneme, že některé body mají trochu jiný odstín), zvláště
když je tato nepřesnost vyvážena podstatným zlepšením kompresního poměru.
Přestože tedy bezztrátové metody samy o sobě nejsou vhodné ke kompresi obrazu
či zvuku, používají se ke zlepšení kompresního poměru jako součást metod
ztrátových.
Zkomprimovat nějaká data znamená najít a odstranit z nich redundanci, která
nenese žádnou (v případě ztrátové komprese pak jen malou) informaci. Když se
žádnou takovou redundanci najít nepodaří, budeme rádi, když se data alespoň
příliš neprodlouží.
Vezměme si takový obyčejný textový soubor. Ten obsahuje několik zdrojů
redundance:
Některé znaky jsou častější (mezera, samohlásky) než jiné, některé se v něm
vůbec nevyskytují. Tohoto faktu si všímají zejména statistické metody.
Znaky nejsou poskládány náhodně, ale do nějakých skupin. Slov, která dávají
smysl, je mnohem méně než všech možností, jak poskládat písmena za sebe. Této
vlastnosti si všímají zejména slovníkové metody.
Po některých písmenech častěji následují některá písmena než jiná. Toho
využívají kontextové metody.
Mohli bychom najít i další zajímavé vlastnosti. Například po přídavném jménu
často následuje jméno podstatné takovými věcmi se baví lingvisté.
Je zřejmé, že tedy pro každý (bezztrátový) algoritmus existují vstupní data
(není potřeba je hledat takových je většina), která se nepodaří zkomprimovat
ani o jediný bit. Naštěstí obvykle nepracujeme s výstupem náhodného generátoru,
ale s daty, která mají nějaký řád.
Komprese dat se dá rozdělit do dvou kroků. Jedním je modelování, kterým se
snažíme odhadnout strukturu dat a případně ji nějak vhodně změnit. Druhým
krokem je pak kódování, které se snaží zapsat výsledek modelování tak, aby
zabíral co nejméně místa (k tomu využívá informace z modelování např.
pravděpodobnosti symbolů).
Statistické metody
Statistické metody využívají rozdílné četnosti jednotlivých symbolů (tedy např.
ASCII znaků nebo i celých slov) ve zdrojovém souboru a snaží se symboly s
častějším výskytem kódovat menším počtem bitů tak, aby se průměrná délka kódu
(a tím i výsledného souboru) zkrátila.
Tyto metody si tedy nevšímají uspořádání symbolů (to je úkolem modelování), ale
jen jejich četnosti. Pokud je tedy použijeme samostatně, bude modelování pouze
poskytovat informace o rozložení pravděpodobností jednotlivých symbolů. Častěji
se však používají ke kódování výstupu jiných metod.
U statických verzí se tyto pravděpodobnosti během kódování celého vstupu nijak
nemění. Nemusí však být v modelu přímo "zadrátované", ale mohou to být nějaké
jeho parametry, které se nejprve nastaví přečtením vstupních dat. Nevýhodou
tedy je, že musíme vstup procházet vícekrát, navíc musíme zjištěné parametry
uložit ke kódovaným datům.
Adaptivní verze mění rozložení pravděpodobností podle již zpracované části
vstupu. Mohou tak zohlednit změny ve struktuře vstupu, a zlepšit tak kompresní
poměr (může se však snadno stát, že dosáhnou pravého opaku). Nevýhodou je, že
jsou výpočetně náročnější.
Huffmanovo kódování
Přiřazuje často se vyskytujícím symbolům kratší kódy (např. pět bitů místo
původních osmi) a naopak. Algoritmus, jak nejlépe přiřadit kódy jednotlivým
symbolům, byl navržen Davidem Huffmanem roku 1952.
Postup komprese
Zjistíme četnosti jednotlivých symbolů (znaků) ve vstupním souboru.
Postupně spojujeme vždy dva symboly s nejmenší četností do nových symbolů,
jejichž četnost je součtem původních četností. Stavíme tedy binární stromeček
od listů ke kořeni.
Do výsledného souboru uložíme vybudovaný stromeček.
Každý vstupní symbol zakódujeme jako cestu, kterou se k němu dostaneme od
kořene stromečku (například 0 = vlevo, 1 = vpravo).
Vybudovali jsme tak prefixový kód (kód žádného symbolu není prefixem kódu
jiného symbolu), ten zřejmě můžeme jednoznačně dekódovat. Z postupu stavby
stromečku je vidět, že záleží na uspořádání symbolů a pořadí výběru symbolů se
stejnou četností. Protože však vždy dostaneme kód se stejnou průměrnou délkou,
můžeme této volnosti využít k úspornějšímu uložení stromečku.
Adaptivní verze
Při kódování a dekódování se stromeček upravuje po každém zpracovaném znaku.
Tím může dojít k situaci, že je potřeba zakódovat znak, který se dosud ve
vstupu nevyskytl. Tuto situaci můžeme řešit tím, že na začátku kódování dáme do
stromečku všechny symboly, nebo tak, že začneme se stromečkem obsahujícím
speciální symbol, který budeme používat k uvození nových znaků. Občas můžeme
četnosti symbolů zmenšit na polovinu a stromeček postavit znovu, tím zamezíme
přetečení a navíc tak usnadníme adaptaci na změnu ve složení vstupu.
Na úpravu stromečku můžeme použít algoritmy Vitterův nebo FGK (podle autorů
Fallera, Gallaghera a Knutha), které nemusí dávat optimální kód, ale jsou
poměrně rychlé. Druhou možností je udržovat stromeček stále správně postavený,
což je však poněkud zdlouhavé.
Shannon-Fanovo kódování
Je předchůdcem Huffmanova kódování, od něhož se liší pouze postupem stavby
stromečku. Pochází od pánů Shannona, Wearwera a Fana a je z roku 1949.
Stromeček je stavěn od kořene k listům: množinu symbolů postupně dělíme na dvě
skupiny tak, aby součty četností v obou skupinách byly přibližně stejné.
Skončíme, až se skupiny rozpadnou na jednotlivé znaky.
Aritmetické kódování
Nevýhodou Huffmanova kódování bylo, že přiřazovalo symbolům kódy celočíselné
délky. Takový přístup dával optimální výsledky, jestliže oba synové libovolného
vrcholu měli vždy stejné četnosti. Pokud jsme naopak kódovali např. dva symboly
s pravděpodobnostmi výskytu 0.9 a 0.1, Huffmanovo kódování přiřadilo oběma
symbolům kódy délky jeden bit, a tím k žádné kompresi nedošlo.
Situace by se trochu zlepšila kódováním n-tic symbolů, k zaokrouhlování na celé
bity by tak docházelo méně často, ale problém by se pouze posunul. Navíc by
došlo k exponenciálnímu nárůstu počtu symbolů a s tím by ruku v ruce vzrostly i
paměťové nároky. Rafinovaným vylepšením tohoto postupu je právě aritmetické
kódování, které umožňuje kódovat celou zprávu jako jediné kódové slovo.
Komprese teorie
Zjistíme pravděpodobnosti výskytů jednotlivých symbolů na vstupu. Začínáme s
omezeným intervalem <0,1).
Rozdělíme stávající interval na podintervaly, které budou reprezentovat
jednotlivé symboly. Délky těchto podintervalů určíme tak, aby byly ve stejném
poměru jako pravděpodobnosti jim příslušejících symbolů.
Symbol na vstupu kódujeme tak, že od stávajícího intervalu přejdeme k
podintervalu, který tomuto symbolu přísluší. Dokud je co kódovat, pokračujeme
předchozím bodem. Rozdělujeme tak tedy stále kratší a kratší intervaly.
Na výstup uložíme libovolné číslo ze stávajícího intervalu.
Popsaný postup má bohužel pouze teoretický význam, ukazuje totiž cestu, jak
dosáhnout teoretického minima délky statisticky zakódované zprávy veličiny
nazývané entropie. Problémem je, že k implementaci tohoto postupu bychom
potřebovali (téměř) nekonečně přesnou aritmetiku, jinak by zaokrouhlovací chyby
naše snažení zcela znehodnotily již po zakódování několika prvních znaků.
Praktická implementace
V průběhu komprese se dolní a horní mez neustále přibližují. Musíme tedy
zajistit dostatečnou přesnost výpočtů, aby bylo možné tento interval rozdělit
na potřebný počet podintervalů bez nebezpečí, že by některé splynuly.
Pokud zápis obou mezí začíná stejnou číslicí, můžeme ji zapsat na výstup a
posunout zápis mezí o jedno místo vlevo. Délka intervalu se tak zdvojnásobí.
Situaci se společnou nulou odpovídá obrázek vlevo.
Může se stát, že se dolní mez bude přibližovat k 1/2 zleva a horní zprava.
Pokud tedy bude dolní mez začínat .01 a horní .10, můžeme z dolní meze vypustit
tuto jedničku, z horní nulu a zbytek zápisu opět posunout vlevo. Tím délku
intervalu opět zdvojnásobíme, viz obrázek vpravo. Počet takto vypuštěných cifer
si budeme pamatovat, a až se dostaneme do stavu se společnou první číslicí,
zapíšeme na výstup nejen ji, ale i všechny vypuštěné číslice. Budeme tedy
zapisovat nulu následovanou jedničkami nebo jedničku následovanou nulami.
Pokud k žádnému z těchto případů nedojde, bude délka intervalu alespoň 1/4 a
ztráty přesnosti se bát nemusíme. K zaokrouhlování samozřejmě stále dochází a
tím se proti teoretickým výsledkům trochu zhoršuje kompresní poměr, ale
nepřijdeme o možnost jednoznačného dekódování výsledku.
Uvedené úpravy provádějí lineární expanzi intervalu, a výpočet tedy nijak
nenarušují. Bylo by barbarstvím (které by jistě bylo potrestáno zhoršením
kompresního poměru) zbytečně si zužovat interval, proto se prázdné místo v
zápisu dolní meze doplňuje nulami a v horní jedničkami.
Modifikace
Algoritmus můžeme samozřejmě upravit na adaptivní verzi, musíme však počítat s
dalším zpomalením již tak pomalého kódování. Velmi zajímavým vylepšením je tzv.
kvazi-aritmetické kódování, které se snaží zachytit všechny možné stavy
kompresoru a přechody mezi nimi. K tomu je potřeba poněkud omezit přesnost
výpočtů, aby byl počet stavů únosný. Následkem toho sice dojde k malému
zhoršení kompresního poměru, to je však vyváženo podstatným zrychlením komprese
i dekomprese.
Slovníkové metody
Jde o modely založené na předpokladu, že skupiny symbolů se často opakují.
Slovníkové metody nahrazují opakující se skupiny symbolů (tzv. fráze) odkazem
na nějaký předchozí výskyt, proto se jim také říká substituční. Nejdůležitější
algoritmy, jak takové fráze najít a kódovat, publikovali Jakob Ziv a Abraham
Lempel v letech 1977 a 1978.
LZ78, LZW
Kompresory založené na tomto principu postupně vytvářejí slovník použitých
frází a jejich opakování pak nahradí odkazem do slovníku a zároveň do slovníku
přidají novou frázi, která vznikne prodloužením právě použité fráze. Dále je
popsán algoritmus LZW pocházející od Terry Welsche z roku 1984, původně určený
k hardwarové implementaci do diskových řadičů.
Komprese
Začínáme se slovníkem obsahujícím jen samostatné znaky a frází složenou z
prvního znaku vstupu. Vždy, když přečteme další znak, zjistíme, zda je fráze
prodloužená o tento znak ve slovníku. Pokud ano, frázi prodloužíme a
pokračujeme dalším znakem. Pokud ne, zapíšeme na výstup kód fráze (její
pořadové číslo ve slovníku) a jako novou frázi vezmeme dotyčný znak.
Pokud se slovník zaplní dříve, než je přečten celý soubor, můžeme například
slovník zmrazit a už ho nerozšiřovat. Jinou možností je celý slovník smazat a
začít ho plnit znovu.
Dekomprese
Postup je zřejmý z algoritmu komprese. Čteme kódy frází, jejich plné znění
zapisujeme na výstup a do slovníku přidáváme frázi prodlouženou o první znak
následující fráze. Může se však stát zajímavá věc máme dekódovat frázi, která
ještě není ve slovníku. To se opravdu stát může, zkuste si vstup AAAB. Oprava
je opravdu jednoduchá, stačí do slovníku přidat posledně dekódovanou frázi
prodlouženou o její první znak.
Modifikace
Nejprve poznámka ke kódování. Vzhledem k tomu, že slovník se plní od nejnižších
pozic, je výhodné začít kódy ukládat např. pouze 9bitově, a teprve když se
slovník více zaplní, postupně přidávat další bity. Slovník dekompresoru se
totiž plní stejně, a tak dekompresor snadno pozná, kdy začít číst kódy 10bitově.
Někdy se pro zlepšení účinnosti místo smazání slovníku používá algoritmus LRU
(last-recently-used) pro odstranění nepoužívaných řetězců ze slovníku. Dalším
vylepšením je neprodlužovat frázi připojením jediného znaku, ale celé
následující fráze. Můžeme také spekulovat nad tím, jestli budeme moci další
frází zakódovat více znaků, za cenu (menšího) zkrácení současné fráze.
LZ77
Metoda je založená na tzv. posuvném okně, které obsahuje konec (několik
kilobytů) přečteného vstupu. V tomto okně se snažíme najít co nejdelší kopii
řetězce, který je zrovna na vstupu, a nahradit ho odkazem do posuvného okna.
Posuvné okno má dvě části: prohlížecí a aktuální okno. Na začátku nastavíme
posuvné okno tak, aby začátek vstupu byl v aktuálním okně. Na inicializaci
prohlížecího okna nezáleží (jen musí být stejný při dekompresi). V posuvném
okně vždy najdeme co nejdelší předponu řetězce z aktuálního okna začínající v
prohlížecím okně a zakódujeme ji jako trojici: pozice v prohlížecím okně, délka
předpony a první znak, kterým se vstup liší. Následně posuneme okno o
zakódovanou část a hledáme další předponu.
Od tohoto algoritmu je odvozeno několik modifikací, které se liší kódováním
výstupu. Jednou možností je kódovat <1, pozice, délka> nebo <0, znak> podle
toho, co je výhodnější. Dalším vylepšením je kódovat pozici v okně a délku
statickým Huffmanovým kódem.
Další metody kontextové kódování
Jde o modelování závislostí mezi znakem a jeho předchůdci. Statistické metody
si vůbec nevšímaly pořadí znaků. Tuto nevýhodu můžeme odstranit tak, že každý
znak budeme kódovat podle pravděpodobnosti jeho výskytu v kontextu několika
předchozích znaků. Tím se zohlední, že např. po znacích stů mnohem častěji
následuje l než třeba e, které se jinak vyskytuje mnohem častěji.
Nic však není zadarmo, a tak za zlepšení kompresního poměru platíme mnohem
většími paměťovými nároky. Situace se trochu zlepší, když si budeme udržovat
rozdělení pravděpodobnosti znaků jen pro některé (častější) kontexty. Když daný
kontext nenajdeme, budeme hledat kontext o jeden znak kratší atd.
Třídění bloků
Třídění bloků je velice zajímavý model kontextových závislostí. Jde vlastně o
transformaci, kterou jako kompresní metodu publikovali roku 1994 Burrows a
Wheeler (proto je někdy označovaná jako BWT).
Vezmeme (dostatečně dlouhý desítky až stovky kilobytů) blok textu, vyrobíme
všechna cyklická posunutí tohoto textu a lexikograficky je setřídíme do
pomyslné matice. Výstupem transformace je pak poslední sloupec této matice a
navíc číslo řádku, kam byl v matici zatříděn původní text. Tyto informace stačí
k rekonstrukci původního textu.
Slova, která se v bloku opakovala, budou zatříděna blízko sebe. Vezměme si
třeba slovo který a podívejme se na poslední sloupec řádků začínajících terý...
Vznikne zde tedy skupina písmen k, občas proložených nějakými jinými písmeny
(např. ze slova úterý).
Poslední sloupec tedy můžeme kódovat algoritmem move-to-front: máme pole všech
různých znaků a každý znak kódujeme jeho pozicí v tomto poli a zároveň tento
znak přesuneme na začátek pole. Ve výsledku tedy budou převažovat nuly a malá
čísla. Můžeme tedy s úspěchem použít např. aritmetické kódování.
Závěr
Pokud budete nějaký algoritmus používat ve svém softwaru, zjistěte si, jestli
některý z nich není patentován (případně je-li tento patent platný i v ČR)
předem upozorňuji, že situace je značně nepřehledná. V Americe je totiž možné
patentovat snad úplně všechno a nechat si za používání platit (to je případ
aritmetického kódování, LZW a dalších). Tato skutečnost sice platí pouze v USA,
ale nová iniciativa Evropské komise hovoří o možnosti zavést podobné zákony i
na starém kontinentu. Trochu se proto bojím dne, kdy si nějaká "firma" nechá
patentovat nuly a jedničky a za jejich používání bude chtít platit.
Závěrem všem přeji hodně úspěchů při balení a co nejlepší kompresní poměr.
0 2115 / alsn









Komentáře
K tomuto článku není připojena žádná diskuze, nebo byla zakázána.