Kodado de Huffman
En Komputado kaj Informa teorio, Huffman-kodo estas speciala speco de optimuma prefiksa kodo, kiu estas ofte uzata por senperda datumkompaktigo. La procezo trovi aŭ uzi tian kodon estas kodado de Huffman, algoritmo evoluigita fare de David A. Huffman.
La eligo de la algoritmo de Huffman povas esti rigardata kiel tabelo de variabla longo por kodigi fontsimbolon (ekzemple signon en dosiero). La algoritmo derivas ĉi tiun tabelon el la taksita probableco aŭ ofteco de okazo (pezo) por ĉiu ebla valoro de la fontsimbolo. Kiel en aliaj metodoj de entropia kodado, pli oftaj simboloj ĝenerale estas reprezentataj uzante malpli da bitoj ol malpli oftaj simboloj. La metodo de Huffman povas esti efike realigita, trovante kodon en tempo lineara al la nombro de eniraj pezoj se ĉi tiuj pezoj estas ordigitaj. Tamen, kvankam ĝi estas optimuma inter metodoj kodigantaj simbolojn po unu, Huffman-kodado ne ĉiam estas optimuma inter ĉiuj densigaj metodoj - ĝi estas anstataŭigita per aritmetika kodado aŭ asimetriaj numeralaj sistemoj se pli bona densigeco estas postulata.
Priskribo de la algoritmo
redaktiEnigo
redaktiAro de simboloj kun iliaj pezoj (ofte pezo de simbolo estas proporcia al probableco aŭ ofteco de simbolo en teksto).
Eligo
redaktiKodado en formo de tabelo, kie al ĉiu eniga simbolo rilatas prefikso-libera duuma kodo kun minimuma longeco. La kodoj formas duuman arbon kun minimuma vojo de la radiko laŭ pezoj. En la arbo ĉiuj folioj estas enigaj simboloj, ĉiu el du branĉoj havas etikedon 0 aŭ 1, la etikedoj laŭ vojo el radiko ĝis folio-simbolo estas Huffman-kodo de tiu simbolo.
Ekzemplo
redaktiNi prenu tekston "bonan tagon". Ĝi havas 7 diversajn signojn (inkludante spaceton), kun oftecoj de ĉiu:
b - 1, o - 2, n - 3, a - 2, spaceto - 1, t - 1, g - 1.
Oni komencas konstrui Huffman-arbon per ordigo de la oftecoj.
spaceto - 1, t - 1, b - 1, g - 1, o - 2, a - 2, n - 3.
Por ĉiu el ili konstruu verticon de arbo (folion) kun nomo = simbolo kaj pezo = ofteco.
El tiu ĉi listo de verticoj elprenu du malplej pezajn, kaj kreu novan verticon kun pezo = sumo de pezoj de la du prenitaj verticoj. Aldonu la du verticojn kiel infanojn al la nova vertico, kaj enlistigu la novan verticon laŭ ĝia pezo.
Ripetu ĝis en la listo restas nur unu vertico - ĝi estas la radiko de Huffman-arbo. En la bildo ĉiu nefolia vertico havas pezon kaj biton 0 (maldekstra) aŭ 1 (dekstra) en krampoj.
La bitoj laŭ vojo de la radiko ĝis iu simbolo estas ĝia kodo.
La rezulta tabelo de kodoj estas:
| simbolo | ofteco | kodo |
|---|---|---|
| n | 3 | 01 |
| o | 2 | 11 |
| a | 2 | 001 |
| b | 1 | 100 |
| g | 1 | 101 |
| t | 1 | 0000 |
| ' ' | 1 | 0001 |
La eniga teksto do estas kodita jene:
| b | o | n | a | n | t | a | g | o | n | ||||||||||||||||||||
| 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 |
Malkodado
redaktiLa procezo de malkodado estas simpla serĉo en la arbo komencante de la radiko, ĉiu bito en la kodita teksto montras kiun branĉon elekti: 0 estas maldekstra, 1 estas dekstra.
Trajtoj de la kodado
redaktiLa kodado de Huffman estas optimuma, se enigaj pezoj estas oftecoj (aŭ probablecoj) de simboloj en kodata teksto.
La kodado de Huffman estas prefikso-libera, tio signifas: la kodoj estas diverslongaj, tamen neniu kodo en la tabelo estas prefikso de alia kodo.
Aplikado de la kodado
redaktiEkzistas kelkaj modifoj kaj plibonigoj de la baza algoritmo de Huffman. La prefiksa kodado estas vaste uzata en komputado por densigi datumojn. Tio estas pro la simpleco de la algoritmo, bona rapideco, kaj manko de patentaj limigoj. La algoritmo uziĝas en programo Gzip, en plurmediaj kodekoj kiel JPEG kaj MP3.