Komprese dat, rozdělení kompresních metod, princip kompresních metod (Huffmann, aritmetické kódování, LZW, JPG, fraktálová komprese)

Verze z 8. 8. 2011, 15:10 (editovat) Tester (diskuse | příspěvky) (Založena nová stránka: Tak tahle otázka je očistec. Kdo tohle všechno vysvětlí za 15 minut je borec, i když bych řekl, že je tam rozsekaj na menší otázky. Obecně: Vyhledáváme pod...)		Verze z 8. 8. 2011, 15:13 (editovat) (zrušit editaci) Tester (diskuse | příspěvky) Porovnání s novější verzí →
Řádka 1:		Řádka 1:
−	Tak tahle otázka je očistec. Kdo tohle všechno vysvětlí za 15 minut je borec, i když bych řekl, že je tam rozsekaj na menší otázky.	+	Komprese dat:
		+	Algoritmy pro kompresi dat používáme pro snížení velikosti přenášených dat
		+	z paměťových důvodů
		+	ušetření šířky pásma
		+	urychlení přenosu a zkrácení doby odezvy
		+	archivace dat, zálohy
		+	obrana proti virům
		+	distribuce software
		+	.....
−	Obecně:	+	Kvalita komprese: úrověň zmenšení, poměr komprese = před/po. Symetrické metody potřebují stejný čas ke komprimaci jako k dekomprimaci
−	Vyhledáváme podřetězec P v řetězci T. T je string s textem, P je string s maskou (pattern)	+	Rozdělení kompresních metod:
−	Podřetězec je část řetězce [i..j]. T je délky n, P je délky m.	+	Bezztrátová - po komprimaci a dekomprimaci je výsledek k nerozeznání od originálu, 100% shoda. Metody jsou méně efektivní. Použijeme na text, obecné soubory
−	Prefix je část řetězce (či podřetězce) od začátku, suffix je část řetězce (či podřetězce) od konce.	+	Ztrátová - po komprimaci a dekomprimaci je výsledek rozdílný, cílem je však aby byl co nejvíce podobný. Více efektivní. Použijeme na zvuk, obraz, video.
−	Brutální síla:	+	Metody komprese:
−	Indexem jdeme po T a kontrolujeme, jestli podřetězec začínající na tomto indexu neodpovídá P (tedy kontrolujeme m prvků od indexu směrem do prava.	+	jednoduché - založené na kódování opakujících se posloupností znaků (Run-Length Encoding - RLE)
−	V nejhorším případě O(nm), což je pomalé	+	statistické - založené na četnosti výskytu znaků v komprimovaném souboru (Huffmanovo kódování, Aritmetické kódování)
−	T: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaah	+	slovníkové - založené na kodování všech vyskytujících se posloupností (Lempel-Ziv-Welch - LZW)
−	P: aah	+	transformační - založené na ortogonálních popř. jiných transformacích (JPEG, waveletová komprese, fraktálová komprese)
−	P v T najdeme až úplně na konci, pro každé 'a' v T (kromě třetího od konce) znovu hledáme písmena P v řetězci T zcela zbytečně	+
−	Boyer-Moore (BM) algoritmus:	+	RLE:
−	V tomto algoritmu prohledáváme P od konce, a hledáme výskyt v T. Do T ukazuje index i, do P index j.	+	Nejjednodušší komprimační algoritmus, nahrazuje opakující se znaky jedním znakem a číslem vyjadřujícím počet okpakování (AAAAABBBBBCCD -> 5A5B2C1D)
		+	Pro text k ničemu, pro obraz celkem dobrá komprese (zvláště obrazy používající malou paletu barev)
		+	Problém: pokud se znak neopakuje, dochází k expanzi (ABC -> 1A1B1C) - Řešení pomocí escape sekvencí (označíme si, co je délka a co ne) a poté komprimujeme pouze opakující se znaky. Escape znak nesmí být obsažen v původním textu.
−	Mohou nastat 4 případy:	+	Huffmannovo kódování:
−	1) T[i] není v P vůbec, posuneme i dále o délku P (zarovnáme P na další písmeno v T, tedy T[i+1]	+	Statistická metoda. Vyhledáme četnosti všech znaků v řetězci a tyto znaky podle četnosti zakodujeme tak, aby nejkradší kód odpovídal nejčastějšímu znaku. Kódy jsou binární, nejčastější znak bude tedy reprezentován 1 bitem na rozdíl od 8(16) bitů potřebných pro uložení ASCII(UTF) znak.
		+	Kódy vytvoříme Huffmannovým stromem:
−	(obrázky v přednáškách jsou křivé, tak se mi to snad povedlo odstranit)	+	Jednotlivé znaky označíme jako listy stromu
−		+	Tyto listy uložíme do seznamu S (S obsahuje uzly stromu, na začátku tedy pouze listy)
		+	Seznam S seřadíme podle četnosti
		+	Vybereme z S dva prvky M,N s nejnižšími četnostmi m, n, m < n
		+	Vytvoříme uzel p, kde vlevo je M a vpravo je N, a jeho četnost bude m+n
		+	Vložíme p do S a zpět na bod 3 dokud v S není jen jeden uzel
		+	Strom samozřejmě musíme přenášet spolu s komprimovanými daty. Strom můžeme reprezentovat řetězcem tak, že jej projdeme DFS algoritmem a pro haždý vrchol uložíme 0 a pro každý list 1 a znak tohoto listu. Při načítání čteme nuly a vytváříme uzly (směrem do leva). Pokud narazíme na 1, zpíšeme písmeno, a vrátíme se do nejbližšího pravého uzlu (pravý uzel rodiče, případně nejvíce levý prvek podstromu - u rodiče vpravo)
		+	Při dekompresi procházíme strom a rekonstruujeme zprávu.
−	2) T[i] odpovídá P[j] - posuneme se v obou do leva a opakujeme (jako v brutální síle)	+	Aritmetické kódování:
		+	Také statistická metoda.
		+	Aritmetické kódování na rozdíl od jiných metod nepracuje na principu nahrazování vstupního znaku specifickým kódem. Místo toho se kódovaný vstupní proud znaků nahradí jediným reálným číslem z intervalu <0,1).
−	3) T[i] není P[j], ale T[i] je v P před indexem j -> zarovnáme P do prava tak, aby T[i] odpovídal jeho výskytu v P a opakujeme	+	Na základě pravděpodobnosti výskytu jednotlivých symbolů vstupní abecedy je každému symbolu přiřazena odpovídající poměrná část intervalu <0,1). Při kódování je pak celý interval <0,1) postupně omezován z obou stran na základě postupně přicházejících symbolů (Interval ořízneme jen na tu část, které odpovídá pravděpodovnost písmene v textu, a tento interval opět rozdělíme podle pravděpodobností pro další písmeno).
−		+
		+	Kódovaná hodnota se reprezentuje libovolným reálným číslem, které leží ve výsledném intervalu získaném po přečtení všech vstupních symbolů. Vzhledem k tomu, že z takto reprezentované hodnoty nelze při dekódování určit konec zprávy, je třeba navíc ke zprávě přidat zpeciální znak označující konec, případně musí být uložena i délka původní posloupnosti.
−	4) T[i] není P[j], ale T[i] je v P za indexem j -> posuneme se do prava o 1 a opakujeme (nemůžeme se vracet, ale ani posunout o více dále)	+	Příklad: kódujeme zprávu 'abaabcda'
−		+
−		+
−		+
−	Pokud nalezneme celý pattern, vrátíme i. Algoritmus je pro texty rychlejší, než brute force, i tak je však jeho složitost O(mn + A), kde A je velikost abecedy. Pro velké abecedy funguje rychle, ale např pro binární soubory funguje pomalu.	+
−		+
−	Dodatek: Algoritmus si v preprocesingu zjistí, na které pozici má které písmena (směrem od leva). Je-li patern tedy například "ABRAKADABRA", A dostane index 10, B dostane index 8, K = 4, D = 6 a R = 9. Pro ostatní písmena přiřadíme -1. Naimplementujeme tedy funkci Last(char input), která podle písmene vrátí tento index, a pak pro případy 3 a 4 porovnáváme Last(T[i]) a j, a tím pak víme, jestli i posunout na Last(T[i]) (pokud je Last(T[i]) < j) nebo pouze i++	+
−		+
−	Knuth‐Morris‐Pratt (KMP) algoritmus.	+
−	Jako brutal force jde zleva do prava, ale nedělá otrocky všechny porovnání. Pokud narazíme na neshodu, je možné se posunout o více než o jedno písmeno.	+
−	Otázka zní o kolik?	+
−	Odpověď, o maximální prefix P( 0 .. j-1 ), který je suffixem P( 1 .. j-1 ). Suffix a prefix se nesmí překrývat.	+
−	Proč? Protože najdeme-li kus P (od začátku, tedy prefix), víme, že znaky tohoto prefixu odpovídají textu. Je tedy netřeba je kontrolovat znovu. Může se ale stát, že konec nalezeného podřetězce je také obsažen v začátku tohoto podřetězce. Takovou shodou je samozřejmě celá nalezená část P, proto hledáme od P+1. Takže jdeme od konce nalezeného kusu P zleva a zprava, a ve chvíli, kdy nenalezneme shodu, víme, o kolik se můžeme posunout. Tohle se samozřejmě dá předpočítat do tabulky, a pak je vše O(1)	+
		+	Co z toho číst?
		+	První řádka ukazuje pravděpodovnosti písmen (ty vypočteme jako četnost písmene / písmen celkem)
		+	Dále vidíme, jak bude interval (a podintervaly) rozdeleny. 'a' jako nejpravděpodobnější písmeno dostane největší část intervalu atd...
		+	A dále už kódujeme. Jdeme zleva do prava. Přijde písmeno 'a', vybereme tedy spodní interval. Tento opět rozdělíme, a přide 'b'. Opět vybereme odpovídající interval, který rozdělíme atd.
		+	Tvýrazněná část intervalu se na obrázku vždy zazoomuje ;)
		+	Na konci máme jen jeden interval, vybereme tedy číslo , které do něj patří. Zpráva je zakódována v desetinné části tohoto čísla (a ano, celá zpráva je reprezentována jedním číslem)
−	(i.e. P[j] != T[i]), pak	+	LZW:
−	k = j‐1;	+	Z přednášek, doplněno:
−	j = F(k); // získání nové hodnoty j, kde F(k) je právě předpočítaná tabulka společných částí P	+	Slovníkový algoritmus. Využívá skupin znaků označených kódy a přenos kódů, které mají menší velikost než původní skupiny.
		+	Princip:
		+	Jednoprůchodová metoda (nevyžaduje předběžnou analýzu souboru. Ve výsledku se jen posunujeme po souboru jedním ukazatelem.)
		+	Vyhledávání opakujících se posloupností znaků, ukládání těchto posloupností do slovníku pro další použití a přiřazení jednoznakového kódu těmto posloupnostem.
		+	Kódy musí mít délku (počet bitů) větší než délka původních znaků (např. pro ASCII znaky (8 bitů) se obvykle používá délka kódu 12 bitů popř. větší. Na osmi bitech kódu by se dal uložit pouze slovník o 256 slovech(posloupnostech znaků), což odpovídá pouze počtu písmen, což je k ničemu.)
		+	Při průchodu komprimovaným souborem se vytváří slovník (počet položek slovníku odpovídá hodnotě 2(počet bitů kódu), kde prvních 2(počet bitů původních znaků) položek jsou  znaky původní abecedy a zbývající položky tvoří posloupnosti znaků obsažené v komprimovaném souboru (používáme tedy i kódy z již komprimovaného souboru k vytvýření nových kódů).
		+	Při dekompresi procházíme kódy, a podle tabulky je rozebíráme na menší a menší, až se dostaneme na elementární znaky, které vypíšeme.
−	Trie.	+	Aby to celé fungovalo, musíme slovník na dekomprimační straně "naučit" slova od menších po větší. Musíme proto na začátku souboru definovat elementární znaky, a z nich poté skládat slovník. Pro ASCII tedy prvních 256 znaků tabulky může odpovídat 1:1 ASCII abecedě, až poté následuje slovník. Pokud při dekompresi narazíme na neznámý kód, víme, že je složen z předchozích 2 kódů. Proto se jej naučíme, a příště už víme, co zapsat (případně jak jej rozložit). Tabulka na obou stranách tedy je stavěna stejně, jen používána z jiné strany (při komprimaci ukládáme kódy, pri dekomprimaci jejich znaky)
−	Trie je struktura pro předspracování textu pro pozdější rychlé vyhledávání. V každém uzlu standartní Trie je písmeno a délka cesty k vrcholu je také pozicí písmene ve slově, tedy je-li hloubka písmene 'E' v Trie rovna 3, víme, že je to třetí písmeno (např. slova Trie)	+
−	Standartní trie má v každém uzlu právě jedno písmeno. Vyhledávání je O(d * m) kde d je velikost abecedy (v každém uzlu musíme projít všechna písmena, abychom zjistili, že tam písmeno je), m je délka slova. Paměťově je Trie nejvýše složitosti O(n) kde n je délka původního textu. Pokud se slova překrývají, paměťi je potřeba méně.	+
−	Rychlost se dá na úkor paměti vylepšit tak, že v každém uzlu připravíme celou abecedu a při hledání převedeme písmeno na index v této abecedě, tím pádem záskáme v O(1) čase pointer na další písmeno ve slově.	+	Pro obrázky viz přednášky z PT, jsou celkem snadno pochopitlené, i když místo "kód" občas autor používá "znak" či "nový znak", což je trochu matoucí.
−	Komprimovaná trie:	+	JPG:
−	Jako trie, ale sklukujeme, tedy ve vrcholech stromu písmena, která jsou společná pro všechna slova, tedy pro slova 'ahoj' a 'ahojky' bude mít trie 2 vrcholy, 'ahoj' a pod ním 'ahojky'. Tuto Trie lze převést na standartní pouhým rozdělením shluků, standartní Trie převedeme na kompaktní sloučením vrcholů s rodiči, kteří mají pouze jeden odkaz na vrchol (tento vrchol)	+	V současné době patří mezi nejvíce používané komprese u obrázků
		+	Je vhodná pro komprimaci fotek, nevhodná pro např. technické výkresy (čarové výkresy) - dochází k viditelnému rozmazání (na webové aplikace pomalu převlédá png (zejména kvůli neztrátovosti a průhlednosti))
−	Pak je ještě suffixová Trie, které ukládá všechny sufixy slov, v komprimované podobě. Umožňuje vyhledávat i uprostřed slova.	+	Princip:
		+	části obrazu se transformují do frekvenční oblasti (výsledkem je matice „frekvenčních“ koeficientů, bezztrátový převod)
		+	z matice koeficientů se odstraní koeficienty odpovídající vyšším frekvencím ( rychlejší změny jasu - např. hrany v obraze, zde jsou ztáty)
		+	zbývající koeficienty se vhodným způsobem zkomprimují (huffman, aritmeticky)
−	LCS - Longest common subsequence	+
−	Tohle je skoro nemožný vysvetlit na statickym papiru....	+
−		+
−	Cílem algoritmu je najít nejdelší společný podřetězec libovolného počtu řetězců. To je problém NP-těžký, což je masakr.	+
−	My se ale omezíme na porovnávání 2 řezězců, což je v polynomiálním čase řešitelné (dynamicky).	+
−		+
−	Brutální síla by dělala to, že by našla všechny podřetězce obou řetězců, a ty porovnávala (také brutální silou) Podřetězců je však řekněme n!, brutální síla je n2, takže (n!)2. Dynamicky to lze dělat rychleji. Použijeme tedy rovnou dynamické programování, protože to nám dovoluje pamatovat si so už jsme našli, a neztrácet čas znovuobjevováním nalezeného.	+
−		+
−	Nechť Li,j = maximální délka společných řetězců končících v Ai a Bj . Vytvoříme si tedy dvojrozměrnou tabulku, do které si tyto Li,j budeme zapisovat.	+
−	Nyní, je-li písmeno na pozici i v řetězci A stejné, jako písmeno na pozici j v řetezci B, víme, že jde o společný podřetězec (délky 1). Nevíme však, zda předchozí písmena nebyla také podřetězcem (zatím)	+
−		+
−	Víme ale následující: Pokud existoval pořetezec pro indexy i-1 a j-1 (tedy pro předchozí písmena v obou řetězcích), bude v tabulce na příslušné pozici, tedy vlevo nahoře od Li,j tedy Li-1,j-1. Na této pozici je tím pádem dosavadně nalezená délka společného podřetězce, který končí na indexech i-1 a j-1. Pokud by i předchozí indexy daly stejné písmeno, musíme tuto délku dále diagonálně propagovat, a tedy	+
−		+
−	Ai = Bj -> Li,j = Li-1,j-1 + 1 -> společný řetězec končící na indexu i-1,j-1 pokračuje	+
−		+
−	Ai <> Bj -> Li,j = 0 -> není společný (pokud na i-1 a j-1 byl, na tomto indexu končí)	+
−	Takto vyplníme celou tabulku, přičemž nulté řádky budou nulové (abychom nevyšli pro první písmena z hranice pole)
−	Problém: Jak zjistit, kde je řešení nejlepší? Ano, můžeme najít maximum v tabulce, ale to je další O(M + N) operace, a máme tabulku plnou nul, toho lze využít. Algoritmus tedy modifikujeme tak, že bude zachovávat i dosavadně nejlepší nalezenou délku společného podřetězce v každém bodě. toho docílíme úpravou druhého pravidla, tedy	+	Fraktálová komprese:
−		+	Fraktál je obraz, který je matematicky popsatelný a tím jej lze libovolně přibližovat a oddalovat bez stráty informace. Také lze fraktál popsat jako soubor matematicky popsaných sebepodobných částí, jejichž spojováním dostáváme také sebepodobný obraz ve větším detailu (jako když děláme koláž z fotek, které dohromady a z dálky vypadají jako fotka)
−	Ai = Bj -> Li,j = Li-1,j-1 + 1	+
−	Ai <> Bj -> Li,j = max (Li-1,j, Li,j-1)	+
−		+
−	Nejlepší nalezené řešení je nahoře, nebo vlevo. Tím se tabulka naplní, a my budeme znát nejlepší délku v pravém spodním rohu tabulky	+
		+	Toho lze využít pro kompresi. Pokud se podíváme na libovolný obrázek, často zjistíme, že některé jeho části jsou si podobné
		+	Tyto malé kousky (frakce) lze pomocí rotace, změny velikosti a posunu otočit tak, že si budou velmi podobné (nebo dokonce budou stejné). V obrazu tedy můžeme na takový kousek mít pouze jednu, a v ostatních výskytech pouze uložit tyto operace.
−	Nyní ale nevíme, kde ta písmena jsou. Je tedy nutné si to ukládat do druhé tabulky (onačit si, kudy jsme na které pole přišli, z leva, ze shora (při zpětném průchodu pouze posun), nebo šikmo (při zpětném průchodu výpis a posun)) a následně zrekonstruovat zpětným průchodem. V přednáškách jsou šipky, ukazující kudy se budeme vracet. Při provádění pravidla 2 si samozřejmě tuto informaci musíme také propagovat, pomatujeme si tedy, odkud jsme na každé pole přišli ( v druhé tabulce si to lze označit třeba 0, 1 pro nahoru a do leva, 2 pro šikmo )	+	V praxi obrázek rozřežeme na shluky 2x2 pixely (range bloky), a pak hledáme, kde jinde v obrazu je můžeme najít (domain bloky). Domain bloky se mohou překrývat, range bloky se nepřekrývají. Postupujeme tak, že Domain blok vytvoříme jako dvojnásobek range bloku, a v obrazu postupujeme zleva do prava. V bloku uděláme průměr hodnot pixelů pod ním tak, abychom získali blok velikosti range bloku, a poté hledáme, kterému range bloku je takto zmenšený domain blok podobný. Uložíme si operace, které s domainblokem musíme udělat, aby byl range bloku podobný (rotace, překlopení, posun...) Pokud je domainblok složen z domainbloků, postupujeme rekurzivně. Tím, pomocí podobnosti, získáme komprimovaný obraz.
−		+
−	A konečně...	+
−	Vzdálenost mezi řetězci:	+
−		+
−	Hammingova metrika: na stejně dlouhé řetězce, jen je porovnáme, a v O(n) čase víme, kolik změn písmen musíme provést (Auto, Zutá = 2)	+
−	Levensteinova metrika: někdy také edit distance, máme operace změnit/přidat/odebrat písmeno, abychom dostali z jednoho řetězce ten druhý. Jde o celočíselné vyjádření podobnosti řetězců, například	+
−		+
−	P=abcdefghijkl, T=bcdeffghixkl, P odpovídá T po 3 změnách (v T přidat a, ubrat f a zaměnit x za j)	+
−		+
−	Algoritmus:	+
−	Postup podobný jako u LCS, ale	+
−	matice je D[i,j]	+
−	a prvky vyplňujeme takto	+
−		+
−	mámo 3 možné způsoby úpravy řetězce	+
−	1. P[i]=T[j] , s = D[i-1,j-1] (shoda) jinak D[i-1,j-1] + 1 (substituce, platíme cenu za změnu znaku)	+
−	2. v = D[i-1,j] + 1 (znak navíc v P, neposouváme pointer v T (při úpravách) a platíme cenu za vkládání)	+
−	3. r = D[i,j-1] + 1 (znak navíc v T, neposouváme pointer v P (při úpravách) a platíme cenu za rušení)	+
−		+
−	minimem z s, v a r  získáme pole D[i,j]	+
−		+
−		+
−	Řešení je opšt ve spodním pravém rohu a zpět postupujeme po stejných číslech (žádní změna) nebo menších (změna, jdeme-li šikmo, substituce, jdeme-li nahoru rušení, do leva vkládání)	+

---

Verze z 8. 8. 2011, 15:13

Komprese dat: Algoritmy pro kompresi dat používáme pro snížení velikosti přenášených dat z paměťových důvodů ušetření šířky pásma urychlení přenosu a zkrácení doby odezvy archivace dat, zálohy obrana proti virům distribuce software .....

Kvalita komprese: úrověň zmenšení, poměr komprese = před/po. Symetrické metody potřebují stejný čas ke komprimaci jako k dekomprimaci

Rozdělení kompresních metod: Bezztrátová - po komprimaci a dekomprimaci je výsledek k nerozeznání od originálu, 100% shoda. Metody jsou méně efektivní. Použijeme na text, obecné soubory Ztrátová - po komprimaci a dekomprimaci je výsledek rozdílný, cílem je však aby byl co nejvíce podobný. Více efektivní. Použijeme na zvuk, obraz, video.

Metody komprese: jednoduché - založené na kódování opakujících se posloupností znaků (Run-Length Encoding - RLE) statistické - založené na četnosti výskytu znaků v komprimovaném souboru (Huffmanovo kódování, Aritmetické kódování) slovníkové - založené na kodování všech vyskytujících se posloupností (Lempel-Ziv-Welch - LZW) transformační - založené na ortogonálních popř. jiných transformacích (JPEG, waveletová komprese, fraktálová komprese)

RLE: Nejjednodušší komprimační algoritmus, nahrazuje opakující se znaky jedním znakem a číslem vyjadřujícím počet okpakování (AAAAABBBBBCCD -> 5A5B2C1D) Pro text k ničemu, pro obraz celkem dobrá komprese (zvláště obrazy používající malou paletu barev) Problém: pokud se znak neopakuje, dochází k expanzi (ABC -> 1A1B1C) - Řešení pomocí escape sekvencí (označíme si, co je délka a co ne) a poté komprimujeme pouze opakující se znaky. Escape znak nesmí být obsažen v původním textu.

Huffmannovo kódování: Statistická metoda. Vyhledáme četnosti všech znaků v řetězci a tyto znaky podle četnosti zakodujeme tak, aby nejkradší kód odpovídal nejčastějšímu znaku. Kódy jsou binární, nejčastější znak bude tedy reprezentován 1 bitem na rozdíl od 8(16) bitů potřebných pro uložení ASCII(UTF) znak. Kódy vytvoříme Huffmannovým stromem:

Jednotlivé znaky označíme jako listy stromu Tyto listy uložíme do seznamu S (S obsahuje uzly stromu, na začátku tedy pouze listy) Seznam S seřadíme podle četnosti Vybereme z S dva prvky M,N s nejnižšími četnostmi m, n, m < n Vytvoříme uzel p, kde vlevo je M a vpravo je N, a jeho četnost bude m+n Vložíme p do S a zpět na bod 3 dokud v S není jen jeden uzel

Strom samozřejmě musíme přenášet spolu s komprimovanými daty. Strom můžeme reprezentovat řetězcem tak, že jej projdeme DFS algoritmem a pro haždý vrchol uložíme 0 a pro každý list 1 a znak tohoto listu. Při načítání čteme nuly a vytváříme uzly (směrem do leva). Pokud narazíme na 1, zpíšeme písmeno, a vrátíme se do nejbližšího pravého uzlu (pravý uzel rodiče, případně nejvíce levý prvek podstromu - u rodiče vpravo)

Při dekompresi procházíme strom a rekonstruujeme zprávu.

Aritmetické kódování: Také statistická metoda. Aritmetické kódování na rozdíl od jiných metod nepracuje na principu nahrazování vstupního znaku specifickým kódem. Místo toho se kódovaný vstupní proud znaků nahradí jediným reálným číslem z intervalu <0,1).

Na základě pravděpodobnosti výskytu jednotlivých symbolů vstupní abecedy je každému symbolu přiřazena odpovídající poměrná část intervalu <0,1). Při kódování je pak celý interval <0,1) postupně omezován z obou stran na základě postupně přicházejících symbolů (Interval ořízneme jen na tu část, které odpovídá pravděpodovnost písmene v textu, a tento interval opět rozdělíme podle pravděpodobností pro další písmeno).

Kódovaná hodnota se reprezentuje libovolným reálným číslem, které leží ve výsledném intervalu získaném po přečtení všech vstupních symbolů. Vzhledem k tomu, že z takto reprezentované hodnoty nelze při dekódování určit konec zprávy, je třeba navíc ke zprávě přidat zpeciální znak označující konec, případně musí být uložena i délka původní posloupnosti.

Příklad: kódujeme zprávu 'abaabcda'

Co z toho číst? První řádka ukazuje pravděpodovnosti písmen (ty vypočteme jako četnost písmene / písmen celkem) Dále vidíme, jak bude interval (a podintervaly) rozdeleny. 'a' jako nejpravděpodobnější písmeno dostane největší část intervalu atd... A dále už kódujeme. Jdeme zleva do prava. Přijde písmeno 'a', vybereme tedy spodní interval. Tento opět rozdělíme, a přide 'b'. Opět vybereme odpovídající interval, který rozdělíme atd. Tvýrazněná část intervalu se na obrázku vždy zazoomuje ;) Na konci máme jen jeden interval, vybereme tedy číslo , které do něj patří. Zpráva je zakódována v desetinné části tohoto čísla (a ano, celá zpráva je reprezentována jedním číslem)

LZW: Z přednášek, doplněno: Slovníkový algoritmus. Využívá skupin znaků označených kódy a přenos kódů, které mají menší velikost než původní skupiny. Princip: Jednoprůchodová metoda (nevyžaduje předběžnou analýzu souboru. Ve výsledku se jen posunujeme po souboru jedním ukazatelem.) Vyhledávání opakujících se posloupností znaků, ukládání těchto posloupností do slovníku pro další použití a přiřazení jednoznakového kódu těmto posloupnostem. Kódy musí mít délku (počet bitů) větší než délka původních znaků (např. pro ASCII znaky (8 bitů) se obvykle používá délka kódu 12 bitů popř. větší. Na osmi bitech kódu by se dal uložit pouze slovník o 256 slovech(posloupnostech znaků), což odpovídá pouze počtu písmen, což je k ničemu.) Při průchodu komprimovaným souborem se vytváří slovník (počet položek slovníku odpovídá hodnotě 2(počet bitů kódu), kde prvních 2(počet bitů původních znaků) položek jsou znaky původní abecedy a zbývající položky tvoří posloupnosti znaků obsažené v komprimovaném souboru (používáme tedy i kódy z již komprimovaného souboru k vytvýření nových kódů). Při dekompresi procházíme kódy, a podle tabulky je rozebíráme na menší a menší, až se dostaneme na elementární znaky, které vypíšeme.

Aby to celé fungovalo, musíme slovník na dekomprimační straně "naučit" slova od menších po větší. Musíme proto na začátku souboru definovat elementární znaky, a z nich poté skládat slovník. Pro ASCII tedy prvních 256 znaků tabulky může odpovídat 1:1 ASCII abecedě, až poté následuje slovník. Pokud při dekompresi narazíme na neznámý kód, víme, že je složen z předchozích 2 kódů. Proto se jej naučíme, a příště už víme, co zapsat (případně jak jej rozložit). Tabulka na obou stranách tedy je stavěna stejně, jen používána z jiné strany (při komprimaci ukládáme kódy, pri dekomprimaci jejich znaky)

Pro obrázky viz přednášky z PT, jsou celkem snadno pochopitlené, i když místo "kód" občas autor používá "znak" či "nový znak", což je trochu matoucí.

JPG: V současné době patří mezi nejvíce používané komprese u obrázků Je vhodná pro komprimaci fotek, nevhodná pro např. technické výkresy (čarové výkresy) - dochází k viditelnému rozmazání (na webové aplikace pomalu převlédá png (zejména kvůli neztrátovosti a průhlednosti))

Princip: části obrazu se transformují do frekvenční oblasti (výsledkem je matice „frekvenčních“ koeficientů, bezztrátový převod) z matice koeficientů se odstraní koeficienty odpovídající vyšším frekvencím ( rychlejší změny jasu - např. hrany v obraze, zde jsou ztáty) zbývající koeficienty se vhodným způsobem zkomprimují (huffman, aritmeticky)

Fraktálová komprese: Fraktál je obraz, který je matematicky popsatelný a tím jej lze libovolně přibližovat a oddalovat bez stráty informace. Také lze fraktál popsat jako soubor matematicky popsaných sebepodobných částí, jejichž spojováním dostáváme také sebepodobný obraz ve větším detailu (jako když děláme koláž z fotek, které dohromady a z dálky vypadají jako fotka)

Toho lze využít pro kompresi. Pokud se podíváme na libovolný obrázek, často zjistíme, že některé jeho části jsou si podobné

Tyto malé kousky (frakce) lze pomocí rotace, změny velikosti a posunu otočit tak, že si budou velmi podobné (nebo dokonce budou stejné). V obrazu tedy můžeme na takový kousek mít pouze jednu, a v ostatních výskytech pouze uložit tyto operace.

V praxi obrázek rozřežeme na shluky 2x2 pixely (range bloky), a pak hledáme, kde jinde v obrazu je můžeme najít (domain bloky). Domain bloky se mohou překrývat, range bloky se nepřekrývají. Postupujeme tak, že Domain blok vytvoříme jako dvojnásobek range bloku, a v obrazu postupujeme zleva do prava. V bloku uděláme průměr hodnot pixelů pod ním tak, abychom získali blok velikosti range bloku, a poté hledáme, kterému range bloku je takto zmenšený domain blok podobný. Uložíme si operace, které s domainblokem musíme udělat, aby byl range bloku podobný (rotace, překlopení, posun...) Pokud je domainblok složen z domainbloků, postupujeme rekurzivně. Tím, pomocí podobnosti, získáme komprimovaný obraz.