Nové výhodné předplatné namísto kreditů je tu! Více informací. Upravili jsme také naše provozní podmínky.
NOVINKA: Staň se datovým analytikem a získej jistotu práce, lepší plat a nové kariérní možnosti. Více informací:
Avatar
Cabernet
Člen
Avatar
Cabernet:28.4.2015 11:20

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
Tvůrce
Avatar
Odpovídá na Cabernet
Martin Dráb:28.4.2015 13:26

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í
+2,50 Kč
Řešení problému
Nahoru Odpovědět
28.4.2015 13:26
2 + 2 = 5 for extremely large values of 2
Avatar
coells
Tvůrce
Avatar
Odpovídá na Cabernet
coells:28.4.2015 14:26

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
28.4.2015 14:26
Avatar
coells
Tvůrce
Avatar
Odpovídá na Cabernet
coells:28.4.2015 14:52

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
28.4.2015 14:52
Avatar
Cabernet
Člen
Avatar
Odpovídá na coells
Cabernet:28.4.2015 15:36

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.