InfElmTetel10

Ez az oldal a korábbi SCH wikiről lett áthozva.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor, kérlek, javíts rajta egy rövid szerkesztéssel!

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót.

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 $f:\alpha \longmapsto \{0,1\}^{*}$ bináris prefix kód optimális akkor feltehetjük a következő három tulandoság teljesülését (az $x_{i}\in \alpha$ forrásbetűket indexeljük valószínűségek szerint csökkenő sorrendben: $p(x_{1})\geq p(x_{2})\geq ...\geq p(x_{n})$ )

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

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

• $|f(x_{1})|\leq |f(x_{2})|\leq ...\leq |f(x_{n})|$
  
• $|f(x_{n-1})|=|f(x_{n})|$
  
• $f(x_{n-1})f(x_{n})$ 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 $\{p(x_{1}),p(x_{2}),...,p(x_{n})\}$ valószínűségi eloszláshoz.

Tegyük fel, hogy

• a Huffman kód fenti feltételei teljesülnek, és
• az $\{p(x_{1}),p(x_{2}),...,p(x_{n-1})+p(x_{n})\}$ valószínűségi eloszláshoz ismert egy g optimális bináris prefix kód, (ahol az $x_{n-1}$ és $x_{n}$ forrásbetűket összevontuk egy $p(x_{n-1})+p(x_{n})$ valószínűségű ${\bar {x}}_{n-1}$ betűbe.

ekkor a $g({\bar {x}}_{n-1})$ 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: $X={a_{1},\ldots ,a_{k}}$
• Építünk egy Huffman-fát, melyben minden szimbólum $1$ 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 $k$. 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:
  
  • Megvizsgáljuk teljesül-e a testvérpár tulajdonság. (*)
    
  • Ha nem, helyreállítjuk:
    
    • Két azonos súlyú csúcs a részfáikkal együtt megcserélhető
      
    • Két levél a súlyukkal együtt megcserélhető
      

(*) Testvérpár tulajdonság:
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.
Lásd. Tk. 25-26 oldalán a példa.

-- Sales - 2006.06.23.