Huffman kodigo

El Vikipedio, la libera enciklopedio.

http://pt.wikipedia.org/wiki/Codifica%C3%A7%C3%A3o_de_Huffman

Huffman arbo generita per la ĝusta frekvenco de la teksto "this is an example of a huffman tree". La oftecoj kaj kodoj de ĉiu karaktero estas sube. La kodita de tiu frazo postulas 135 bitoj (ne kalkulante la spaco necesa por la arbo mem).

Carac	Freq	Kodo
spaco	7	111
la	4	010
kaj	4	000
f	3	En 1101
h	2	En 1010
i	2	En 1000
m	2	0111
n	2	0010
s	2	En 1011
t	2	0110
l	1	11001
la	1	00110
p	1	10011
r	1	11000
u	1	00111
x	1	10010

La kodigo kodigo estas metodo de kunpremo, kiu uzas la probablo de apero de simboloj en la datuma aro al esti kompresita determini kodoj de ŝanĝiĝema longitudo por ĉiu simbolo. Ĝi estis disvolvita en 1952 de David A. Huffman kiu estis tiutempe studento de PhD ĉe MIT , kaj estis eldonita en la artikolo "Al Metodo por la Konstruo de Minimuma-Redundo Kodoj".
A duuma arbo kompleta alvoko Huffman arbo estas konstruita rekursie de la junto de la du malaltaj probablo simboloj, kiuj estas poste kombinita en simboloj kaj ĉi tiuj simboloj helpa anstataŭita en la aro de helpaj simboloj. La procezo finas kiam ĉiuj simboloj estis kunigitaj en helpa simboloj, formante duuma arbo. La arbo estas tiam trairita de asignanta valorojn al duuma 1 aŭ 0 por ĉiu rando , kaj la kodoj estas generitaj de tiu vojo.
La kodigo kodigo estas optimuma agado kiam la probabloj de la simboloj estas potencoj de du negativaj ( ). La generita kodo ankaŭ garantias esti unusenca, ĉar neniu kodo povas esti la prefikso de alia kodo.

Indekso Algoritmo 1 Ekzemplo 2 3 Bibliografio 4 Vidu ankaŭ 5 Eksteraj ligiloj

Algoritmo

Atribui la gravuloj pli oftaj duuma kodoj de pli malgranda longeco, konstruas duuma arbo bazita sur la probabloj de apero de ĉiu simbolo . En ĉi tiu arbo la folioj reprezentas la simbolojn ĉeestas en la datumojn asociitaj kun iliaj respektivaj probabloj de spritaĵo. La intera nodoj reprezentas la sumo de la probabloj de apero de ĉiu simboloj ĉeestas en ĝiaj branĉoj kaj la radiko reprezentas la sumo de la probabloj de ĉiuj simboloj en la datuma aro. La procezo komencas per la kunigo de la du malpli verŝajna simboloj, kiuj estas poste kunigis en nodo al kiu estas atribuita la sumo de iliaj probabloj. Ĉi tiu nova nodo estas tiam traktita kiel folio sur la arbo, tio estas, unu el la simboloj de la alfabeto, kaj kompare al la aliaj laŭ iliaj probablo. La procezo ripetas ĝis ĉiuj simboloj estas kunigitaj sub la radika nodo.
Ĉiu rando de la arbo estas asociita kun unu cifero duuma (0 aŭ 1). La kodo por ĉiu simbolo estas tiam difinita lauxiris sur la arbon kaj notante la ciferoj de randoj trairis de la radiko al la folio responda al la dezirata simbolo.
La algoritmo por konstruado de ĉi tiu arbo estas kiel sekvas:

 dum grandeco (alfabeto)> 1:
   S0: = retira_menor_probabilidade (alfabeto)
   S1: = retira_menor_probabilidade (alfabeto)
   X: = novo_nó
   X.filho0: S0 =
   X.filho1: S1 =
   X.probabilidade: + = S0.probabilidade S1.probabilidade
   enmetas (alfabeto, X)
 Fine dum

 X = retira_menor_símbolo (alfabeto) # je ĉi tiu punkto estas nur simbolo.

 por ĉiu folio en littukojn (X):
   kodo [folio]: = percorre_da_raiz_até_a_folha (folio)
 por fini

En ĉi tiu pseŭdo-algoritmo funkcio grandeco redonas la numeron de nodoj aŭ folioj stokitaj en nia dosieraro, tie nomitaj alfabeto. La funkcio retira_menor_símbolo (alfabeto) redonas la nodo aŭ folio malpli verŝajna en nia dosieraro kaj forigi tiun simbolon de la deponejo. La komando kreas novan nodon novo_nó malplena. La funkcio enmetas (alfabeto, X) enmetas la X simbolo en nia dosieraro kaj fine la funkcio percorre_da_raiz_até_a_folha (folio) trairas la duuma arbo de radiko al folio amasigante la valoroj asociita kun la lateroj en lia reveno valoro.
Tiel, la karaktero plej ofte havas la plej mallongan kodon kiu estas ĝuste la celo de statistikaj kunpremo. Tia estas la aliaj karakteroj, por proporcie pligrandiĝanta la nombro de bitoj kiel la propraĵo:

• La averaĝa grandeco de la karakteroj (TMC) estas donita per la sumo de la produktoj de ĉiu karaktero grandeco (T (c)) por lia limigoj probablo (P (c)). (La sama rezulto povas esti ricevita per simpla sumado de la probabloj de ĉiu interna nodo en la kodigo arbo).

En posedo de simboloj konstruita de la supra algoritmo, datuma kunpremo estas simple anstataŭante ĉiu simbolo kun lia responda kodo. Sekcio Ekzemplo montri la konstruo de arbo tretante kaj ankaŭ la kodigo de niaj datumoj uzante la aro de simboloj akiras de la arbo.

Ekzemplo

Por ilustri la funkciadon de la metodo, ni kunpremi la vico de signoj AAAAAABBBBBCCCCDDDEEF . Se ni uzi la norma formo de reprezento kie la amplekso de ĉiu signo estas fiksita, la plej malgranda kodigo ni povas uzi por reprezenti ĝin en duuma estas tri bitoj por karaktero. Tiel ni havas la sekvan kodon:

Karaktero	La	B	C	D	E	F
Kodo	000	001	010	011	100	101

Generante tiel la bitoj 000000000000000000001001001001001010010010010011011011100100101 por reprezenti nia originala vico. Tio donas al 63 bitoj longa.
Por uzi la Huffman kodo kaj kunpremi ĉi vico ni devas unue konstrui arbo Huffman sekvi la paŝojn pli supre. La unua paŝo estas kalkuli la spritaĵoj de ĉiu signo en la linio al esti kompresita. Kun ĉi tiu ni havas:

Karaktero	La	B	C	D	E	F
Grafo	6	5	4	3	2	1

Nun ni kolektos niajn Huffman arbo. En la diagramo sube oni vidas la nodoj kiuj reprezentas ĉiu simbolo, kaj markita en ruĝa la du nodoj kiuj estos kunigitaj en la unua paŝo. En kazo la nodoj E kaj F:

Ni vidas ĉi tiun duan bildon, en nigra, nodoj E kaj F kune en nodo oni nomas E + F, kaj havas la pezon egala al la sumo de la nodoj E kaj F. Ĉi tiu nova nodo estas enigita en la aro de nodoj al kiu nodoj elektos la apud aligxos. Hazarde, en ĉi tiu ekzemplo, la sekva ni estas tiu nova nodo nodo E + F kaj D, kiel montrita en la sekvanta figuro:

Daŭrigante la procezo nun aliĝi nodoj B kaj C:

La nodo A estas fine kunigitaj kun nodo D + E + F:

kaj la lasta kunigo nodoj A + D + E + F kun la Nodo B + C:

Generante nia Huffman arbo kiu estas nun severe duuma arbo:

En ĉi tiu arbo ni povas nun identigi la kodojn por ĉiu simbolo. Por ĉi tiu simple iru al la arbo kaj la simbolo "noto" por la respondaj bitoj randoj ili vojaĝis. Ekzemple, por preni la leteron D iri tra la bitoj 0 al nodo A + D + E + F, tiam iom 1 ĝis akiri D + E + F kaj tiam iom 0 denove, prenanta D. Do la Huffman kodo por la litero D estas 010 . Malsupre ni listigas Huffman kodojn por ĉiu el la simboloj ni uzas:

Karaktero	La	B	C	D	E	F
Grafo	00	10	11	010	0110	0111

Nun, por kodi nia originala vico ni havas: 000000000000101010101011111111010010010011001100111 totalizando nur 51 bitoj. Nia kunpremo estas 12 bitoj, aŭ ĉirkaŭ 20%.
En realaj kazoj la kunpremo akiris eblas multe pli alta, kiel la ofteco de tiaj simboloj estas sufiĉe granda, dum la alia estas preskaŭ nula (la vokaloj "a", "e", "i", "o" kaj "aŭ" okazi tre ofte, dum iuj literoj kiel "y", "k" aŭ "z" aperas multe malpli). Tiu granda diferenco en oftecoj faras la gravuloj pli oftaj, kaj konsekvence kun mallongaj simboloj, estas pli bone reprezentitaj ege pliigante la kunpremo rilatumo.

Bibliografio

• Okazinta, Gilbert. Datumoj Kunpremo. Tatuapé, SP: Erica, 1998. 390 p. ISBN 85-7194-110-6
• Nelson, Mark; Gailly, Jean-Loup. La datumoj Kunpremo Libro (angle). Nov-Jorko: M & T Libroj, 1996. 557 p. ISBN 1-55851-434-1
• SALOMON, Davido. Datumoj Kunpremo: La Kompleta Vikipedio (en la angla). 2nd ed. Nov-Jorko: _Springer_, 2000. ISBN 0-387-95045-1
• SALOMON, Davido. A Guide to Datumoj Kunpremo Metodoj (en la angla). Nov-Jorko: _Springer_, 2002. 295 p. ISBN 0-38795260-8
• SAYOOD, Khalid. Enkonduko al Datumoj Kunpremo (en la angla). 2nd ed. Sankta Francisko: Morgan Kauffman, 2000. 636 p. ISBN 1-55860-558-4