Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoalap|InfElmTetel10}} vissza InfelmTetelek-hez ==Huffman- és adaptív…”

2012-10-21T19:59:05Z

Új oldal, tartalma: „{{GlobalTemplate|Infoalap|InfElmTetel10}} vissza InfelmTetelek-hez <style> li {margin-top: 4px; margin-bottom: 4px;} </style> ==Huffman- és adaptív…”

Új lap

{{GlobalTemplate|Infoalap|InfElmTetel10}}

[[InfElmVizsga|vissza InfelmTetelek-hez]]
<style> li {margin-top: 4px; margin-bottom: 4px;} </style>

==Huffman- és adaptív Huffman kódolás==

===Optimális kód tulajdonságai===

Ha egy <math> f : \alpha\longmapsto \{0,1\}^* </math> bináris prefix kód ''optimális'' akkor feltehetjük a következő három tulandoság teljesülését
(az <math> x_i \in \alpha </math> forrásbetűket indexeljük valószínűségek szerint csökkenő sorrendben: <math> p(x_1) \geq p(x_2) \geq ... \geq p(x_n) </math> )

* A kisebb indexű, (tehát nagyobb valószínűségű) forrásbetűhöz rövidebb kódszó tartozik.<br>
* A két legkisebb valószínűségű forrásbetűhöz azonos hosszúságú kódszó tartozik.<br>
* A két legkisebb valószínűségű forrásbetűhöz tartozó kódszavak csak az utolsó bitben különböznek.<br>

A fenti három tulandonság formálisan:

* <math> |f(x_1)| \leq|f(x_2)| \leq... \leq|f(x_n)| </math> <br>
* <math> |f(x_{n-1})| = |f(x_n)| </math> <br>
* <math> f(x_{n-1}) f(x_n) </math> csak az utolsó bitben különbözik.

===Huffman kód konstrukciója===

====Ráhangolódás====

Tekintsünk egy X valószínűségi változót, aminek az értékét optimálisan szeretnénk kódolni bináris prefix kóddal. A következő tétel rekurzív módszert ad ennek előállítására. Egy n lehetséges értékű eloszlás kódolását visszavezetjük egy n-1 lehetséges értékű eloszlás kódolására.
A tétel azt mondja ki, hogy ha X két legkisebb valószínűségű értékét összevonnánk, egy olyan értékké, aminek a valószínűsége a két összevont érték valószínűségének az összege, és az így kapott X' valószínűségi változóra találnánk optimális bináris prefix kódot, akkor ebben a kódban az imént összevont értékhez tartozó kódszót egy nullával illetve egy egyessel kiegészítve, és ezt a két kódszót a két összevont érték kódolására használnánk, akkor ez az eredeti X valószínűségi változó egy optimális bináris prefix kódja lenne.

====Az algoritmus leírása====

TODO

====Tétel kimondása====

Optimális bináris prefix kódot keresünk a <math> \{ p(x_1), p(x_2), ... , p(x_n) \} </math> valószínűségi eloszláshoz.

Tegyük fel, hogy
* a Huffman kód fenti feltételei teljesülnek, és
* az <math> \{ p(x_1), p(x_2), ... , p(x_{n-1}) + p(x_n) \} </math> valószínűségi eloszláshoz ismert egy g optimális bináris prefix kód, (ahol az <math> x_{n-1} </math> és <math> x_n </math> forrásbetűket összevontuk egy <math> p(x_{n-1}) + p(x_n) </math> valószínűségű <math> \bar{x}_{n-1} </math> betűbe.

ekkor a <math> g(\bar{x}_{n-1}) </math> kódszót egy egyessel és egy nullával kiegészítve, a többi kódszót változatlanul hagyva az eredeti eloszlás egy optimális bináris prefix kódját kapjuk.

===Adaptív Huffman kódolás===

A Huffman kód konstruálásához ismernünk kell a forrásábécé eloszlását. Ha ez nem áll rendelkezésre, akkor a teljes kódolandó üzenetet végig kell olvasni először, és meg kell határozni a relatív gyakoriságokat, és utána ezeket felhasználva kezdődhet el a kódolás. Ez komoly késleltetést és kétszeri olvasást eredményez.

A problémár az adaptív Huffman kód adja a megoldást: minden betűt az addig kódolt üzenetrészben számított relatív gyakoriságoknak megfelelő Huffman kóddal kódol, tehát a kódolási fát folyamatosan frissíteni kell.

====Algoritmus====

Az aktuális karaktert az aktuális kóddal kódoljuk, majd az adott forrás-karakter relatív gyakoriságát növelve javítunk a kódon. Az algoritmus:

* Ismerjük a forrás szimbólumokat: <math> X = {a_1, \ldots, a_k}</math>
* Építünk egy Huffman-fát, melyben minden szimbólum <math>1</math> gyakorisággal szerepel
* Elküldjük a dekódolónak a forrás szimbólumokat, amiből ő is felépítheti a fát
* Beolvassuk a <math>k</math>. szimbólumot, ezt a lokálisan optimális kódfával kódoljuk
* Növeljük a szimbólum gyakoriságát
* Aktualizáljuk a fát:<BR>
** Megvizsgáljuk teljesül-e a testvérpár tulajdonság. (*)<BR>
** Ha nem, helyreállítjuk:<BR>
*** Két azonos súlyú csúcs a részfáikkal együtt megcserélhető<BR>
*** Két levél a súlyukkal együtt megcserélhető<BR>

(*) Testvérpár tulajdonság:<BR>
Ha a fa közös szülővel rendelkező pontpárjait a gyökértől a levelek felé fel tudjuk sorolni súlyuk szerint '''nem növekvő''' sorrendben akkor a Huffman fa optimális.<BR>
Lásd. Tk. 25-26 oldalán a példa.

-- [[SzelessZoltanTamas|Sales]] - 2006.06.23.

[[Category:Infoalap]]

InfElmTetel10 - Laptörténet

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoalap|InfElmTetel10}} vissza InfelmTetelek-hez li {margin-top: 4px; margin-bottom: 4px;} ==Huffman- és adaptív…”

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoalap|InfElmTetel10}} vissza InfelmTetelek-hez ==Huffman- és adaptív…”