Avatar
Cabernet
Člen
Avatar
Cabernet:

Zdravim,

mam otazku ohladom tvorenia Huffmanoveho stromu pri kompresii udajov. Viem ako sa takyto strom tvori ale nejako mi to nedava zmysel. Napr. vystupom takeho stromu moze byt:

znak - kodovanie

A - 0
C - 10
B - 111
D - 110

No a nie je skoda ze nevyuzivame mensie zakodovanie? nebolo by to lepsie takto?

A - 0
C - 1
B - 01
D - 11

Odpovědět 28.4.2015 11:20
Think different
Avatar
Martin Dráb
Redaktor
Avatar
Odpovídá na Cabernet
Martin Dráb:

U toho menšího zakódování bys měl problém s jeho zpětným dekódováním. Jak poznáš, že máš přečíst jenom jeden bit (znaky A a C) nebo dva (B a D)?

U Huffmanova kódování ti tento problém nenastane. V ideálním případě se navíc v kódovaném textu (pro tvůj případ) vyskytují znaky B a D málo často v porovnání s C (a zvláště pak s A).

Akceptované řešení
+20 Zkušeností
+1 bodů
Řešení problému
Nahoru Odpovědět  +1 28.4.2015 13:26
2 + 2 = 5 for extremely large values of 2
Avatar
coells
Redaktor
Avatar
Odpovídá na Cabernet
coells:

Je to škoda, také existuje lepší kódování, aritmetické kódování.
Jenže bylo mnoho let chráněno patentem, který vypršel až nedávno.

Vezmi si třeba svůj Huffmanův kód (tím myslím ten korektní), který bys zkonstruoval například pro zprávu AAAACCDB
Výsledek by byl 00001010110111, to je 14 bitů

Tvůj nekorektní kód by sice dal 0000111101, což je jen 10 bitů, ale místo původní zprávy bys dekódoval AAAADDB.

V aritmetickém kódování bys stejnou zprávu kódoval 000000000001, což je jen 12 bitů.

Dále platí, že Huffmanův kód je optimální v případě, že frekvence prvků je mocnina 2, tedy F(p) = 2^-i, ale obecně není Huffman moc efektivní, zatímco aritmetické kódování je.

 
Nahoru Odpovědět  +1 28.4.2015 14:26
Avatar
coells
Redaktor
Avatar
Odpovídá na Cabernet
coells:

A ještě abych tě trochu zaujal, můžeš si zkusit zakódovat Huffmanovým kódem tuhle zprávu: AAAAAAAAAB.

Aritmetické kódování skončí na 011 :-)

 
Nahoru Odpovědět  +1 28.4.2015 14:52
Avatar
Cabernet
Člen
Avatar
Odpovídá na coells
Cabernet:

Vypada to zaujimavo, idem sa s tym pohrat, uvidim aku to da kompresiu. Vdaka

Nahoru Odpovědět 28.4.2015 15:36
Think different
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 5 zpráv z 5.