Codificació Shannon-Fano

Codificació Shannon-Fano, en el camp de la compressió de senyes, la codificació Shannon-Fano és una tècnica per a construir un còdic prefixe basat en un conjunt de símbols i les seues provabilitats (estimades o mides). No és òptim en el sentit de que no conseguix la menor llongitut de paraula còdic esperada possible com en la codificació Huffman; encara que a diferència de la codificació Huffman, garantisa que totes les llongituts de paraules de còdic estan a un bit del seu ideal teòric – logP(x). La tècnica va ser proposta per Claude Elwood Shannon, en “Una Teoria Matemàtica de la Comunicació”, el seu artícul de 1948 introduint el camp de la teoria de l'informació. El método va ser atribuït a Robert Fano, qui posteriorment ho va publicar com un informe tècnic. La codificació Shannon-Fano no deu confondre's en la codificació Shannon, método de codificació usat per a provar la teorema de Shannon de la codificació sense soroll, ni en la codificació Shannon-Fano-Elias (també coneguda com a codificació Elias), el precursor de la codificació aritmètica.

En la codificació Shannon-Fano, els símbols s'ordenen del més a lo manco provable, i es dividixen en dos subconjunts les provabilitats totals dels quals són tan pròximes a ser iguals com siga possible. A continuació tots els símbols tindran el primer dígit dels seus còdics assignats; els de el primer subconjunt rebran el “0” i els de el segon el “1”. Mentres existixca algun subconjunt en més d'un terme, es repetirà el mateix procés per a determinar els successius dígits dels seus còdics. Quan un dels subconjunts ha segut reduït a un símbol, açò significa que el còdic del símbol és complet i que no formarà el prefix del còdic de cap atre símbol.

L'algoritme funciona, i produïx codificació de llongitut variable prou eficients; quan els dos subconjunts produïts per una divisió tenen la mateixa provabilitat, ya que el bit d'informació usat per a distinguir-los s'usa més eficientemente.

Desafortunadament, Shannon-Fano no produïx sempre còdics prefixos òptims; el conjunt de provabilitats {0.35, 0.17, 0.17, 0.16, 0.15} és un eixemple d'açò.

Per esta raó, Shannon-Fano a penes s'usa; la codificació Huffman és casi tan computacionalment simple i produïx còdics prefixos que sempre conseguixen la menor llongitut esperada de paraula de còdic, baix la restricció de que cada símbol és representat per un còdic format per un número integral de bits. Esta és una restricció a sovint innecessària, ya que els còdics seran empaquetats d'un extrem a un atre en llargues seqüències. I considerem grups de còdics en un instant, símbol a símbol la codificació Huff solament és òptima si les provabilitats de que els símbols siguen independents i estan elevades a un mig, p.i., 21/2. En la majoria de les situacions, la codificació aritmètica pot produir major compressió general que Huffman o que Shannon-Fano, ya que pot codificar en número fraccionario de bits, més propencs al contingut real d'informació de cada símbol. No obstant, la codificació aritmètica reemplaçat a la de Huffman de la manera que esta sobrepassa a Shannon-Fano, ya que la codificació aritmètica és més costosa computacionalment i perque està subjecta a múltiples paleses.

La codificació Shannon-Fano s'usa en el método de compressió IMPLODE, que és part del format dels archius ZIP.

L'algoritme Shannon-Fano

Un arbre Shannon-Fano es construïx d'acort a una especificació dissenyada per a definir una taula de còdics efectiva. L'algoritme actual és simple:

1. Per a una llista de símbols donada, crear la seua corresponent llista de provabilitats o de freqüències d'aparició de manera que es conega la freqüència relativa d'ocurrència de cada símbol.
2. Ordenar les llistes de símbols d'acort a la freqüència, en els símbols d'ocurrència més freqüent a l'esquerra i els menys comuns a la dreta.
3. Dividir la llista en dos parts, fent la freqüència total de la mitat esquerra lo més pròxima possible a la de la mitat dreta.
4. Assignar a la mitat esquerra el dígit binario “0”, i a la mitat dreta el dígit “1”. Açò significa que els còdics per als símbols en la primera mitat escomençaran en “0”, i que els còdics de la segona mitat escomençaran per “1”.

1. Aplicar recursivamente els passos 3 i 4 a cada una de les dos mitats, subdividiéndolas en grups i afegint bits als còdics fins que cada símbol es correspon en un full de l'arbre.

Eixemple

L'eixemple mostra la construcció d'un còdic Shannon per a un chicotet alfabet. Els cinc símbols que poden ser codificats tenen la següent freqüència.

Símbol	A ! B	C	D	I
Freqüència	15	7	6	6	5

Tots els símbols són ordenats per freqüència, d'esquerra a dreta. Dividint entre B i C obtenim un total de 17 en el grup de la dreta i 22 en el de l'esquerra. Açò minimisa la diferència total entre els dos grups. En esta divisió, A i B tindran abdós un còdic que escomençarà en el bit 0, i C, D i I en el bit 1. Seguidament, la mitat esquerra de l'arbre es subdivide en A i B, lo que posa a A en un full en el còdic 00 i a B en una atra en el còdic 01. Despuix de quatre divisions, terminem l'arbre de còdics. Al final, els símbols de l'arbre en freqüències més altes tenen tots còdics de 2 bits, i els atres dos símbols en menor freqüència tenen còdics de 3 bits, com es veu en la taula inferior.

Símbol	A ! B	C	D	I
Còdic	00	01	10	110	111

Notes

Este artícul és una traducció parcial de "Shannon-Fano coding", trobat en Wikipedia English

Referències

• C.E. Shannon, "A Mathematical Theory of Communication
• Archivat el 15 de juliol de 1998 archivat en Wayback Machine.", Bell System Technical Journal, vol. 27, pp. 379-423, July 1948.
• R.M. Fano, "The transmission of information", Technical Report No. 65, 1949. Research Laboratory of Electronics, M.I.T., Cambridge (Mass.), USA.

Vore també

• Codificació Huffman
• Compressió de senyes