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:
“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:
| 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.
