Compresión Shannon-Fano

El método de Shannon-Fano fue propuesto por Claude Elwood Shannon en 1.948 y desarrollado por Roberto Mario Fano al año siguiente. Su utilidad principal es la compresión de datos. Se basa en la probabilidad de aparición de cada símbolo en el mensaje, para ello crea un conjunto de símbolos contenidos en el mensaje que se utilizan como prefijo, esto garantiza que todas las longitudes de palabras del código están a un bit de su ideal teórico, pero en ocasiones no produce prefijos óptimos.

Ejemplo.

Tomamos un mensaje cualquiera:

 Claude Elwood Shannon
Shannon
Roberto Mario Fano
Fano

“En un lugar de la mancha de cuyo nombre no quiero acordarme, no ha mucho tiempo que vivía un hidalgo de los de lanza en astillero, adarga antigua, rocín flaco y galgo corredor. Una olla de algo más vaca que carnero, salpicón las más noches, duelos y quebrantos los sábados, lentejas los viernes, algún palomino de añadidura los domingos, consumían las tres partes de su hacienda.”

 

Calculamos la frecuencia de los símbolos que aparen en el mensaje.

 

Frecuencia de Símbolos
ASCII Símbolo Ocurrencias Frecuencia
65 17,195767
97 a 40 13,5135135
111 o 31 10,472973
101 e 28 9,45945946
110 n 24 8,10810811
108 l 22 7,43243243
115 s 22 7,43243243
114 r 18 6,08108108
100 d 17 5,74324324
117 u 15 5,06756757
99 c 13 4,39189189
105 i 12 4,05405405
109 m 10 3,37837838
103 g 9 3,04054054
116 t 7 2,36486486
104 h 6 2,02702703
112 p 4 1,35135135
113 q 4 1,35135135
118 v 4 1,35135135
98 b 3 1,01351351
121 y 3 1,01351351
102 f 1 0,33783784
106 j 1 0,33783784
122 z 1 0,33783784
241 ñ 1 0,33783784

 

Para simplificar, del ejemplo tomamos los 5 primeros símbolos y los dividimos en 2 grupos:

           Grupo 1 [ ” ” + a ]
           Grupo 2 [ o + e + n ]
Bits
Símbolo Ocurrencias 1 2 3
65 0 0
a 40 0 1
o 31 1 0
e 28 1 1 0
n 24 1 1 1

 

A los símbolos de la mitad superior (Grupo 1 ) le asignamos un 0, a la inferior se le asigna 1. Después repetimos la acción incorporando nuevos 0 y 1 hasta que cada símbolo se represente en binario de forma distinta.

 

Representamos la tabla como un árbol binario

 

Calculamos los bits del mensaje codificado.

Para representar 5 caracteres sin codificar necesitaríamos 3 bits, pero al codificarlos hemos disminuido la necesidad de utilizar un bit de los dos primeros símbolos, calculamos los totales:

 

Símbolo Ocurrencias Entropía Entropía en el mensaje Bit Código Bit Mensaje Bit sin codificación
65 0,43 28,38 2 130 195
a 40 0,35 15,33 2 80 120
o 31 0,30 9,65 2 62 93
e 28 0,27 7,34 3 84 84
n 24 0,25 6,06 3 72 72
Total 191 0,50 1,61 12 428 564

 

La diferencia, en el ejemplo, para los primeros 5 símbolos son 136 bits menos, un 24,1% menor. Para el texto propuesto el número mínimo de bits sería 5, os dejamos que calculéis el resultado.

 

Código Java.

Programa en Java que se ha utilizado para obtener los datos para el ejemplo.

 

Programa en Java Compresión Shannon-Fano
Programa en Java Compresión Shannon-Fano