> shannon | fano | entropía <
// Shannon-Fano – Codificación de entropía descendente para compresión de datos
Basado en entropía
Utiliza teoría de la información para generar códigos eficientes de longitud variable.
Enfoque descendente
Divide recursivamente los símbolos en grupos con probabilidades similares.
Algoritmo histórico
Método pionero que influyó en muchas técnicas modernas de compresión.
>> información técnica
Cómo funciona Shannon-Fano:
La codificación Shannon-Fano ordena los símbolos por frecuencia y los divide recursivamente en dos grupos con probabilidades totales lo más parecidas posible. Cada división añade un bit al código (0 a la izquierda, 1 a la derecha). El resultado es un código prefijo de longitud variable.
Proceso de codificación:
Texto: "AAABBCD" Frecuencias: A:3, B:2, C:1, D:1 División: [A] | [B,C,D] Códigos: A: 0 B: 10 C: 110 D: 111 Codificado: 0 0 0 10 10 110 111
Por qué usar Shannon-Fano:
- >Fácil de implementar
- >Buenos índices de compresión
- >Importancia histórica
- >Útil para aprendizaje
- >Códigos prefijo
>> preguntas frecuentes
¿Qué es la codificación Shannon-Fano?
La codificación Shannon-Fano es una técnica de codificación por entropía desarrollada por Claude Shannon y Robert Fano en la década de 1940. Fue uno de los primeros algoritmos en usar códigos de longitud variable basados en la probabilidad de los símbolos.
¿Shannon-Fano o Huffman?
Ambos generan códigos de longitud variable, pero Huffman es óptimo y produce la longitud media de código más corta. Shannon-Fano es más sencillo, aunque puede generar códigos ligeramente más largos. Huffman construye el árbol de abajo hacia arriba, Shannon-Fano de arriba hacia abajo.
¿Cómo funciona la división de símbolos?
Los símbolos se ordenan por frecuencia y se dividen en dos grupos con probabilidades totales lo más cercanas posible. El proceso se repite de forma recursiva hasta que cada grupo contiene solo un símbolo.
¿Sigue utilizándose Shannon-Fano?
Shannon-Fano se usa hoy principalmente con fines históricos y educativos. En la práctica fue reemplazado en gran medida por la codificación de Huffman, que garantiza la optimalidad. Aun así, sigue siendo valioso para entender los conceptos básicos de la compresión.
// Ejemplo resuelto
| Symbol | Freq | Code | Bits |
|---|---|---|---|
| A | 15 | 00 | 2 |
| B | 7 | 01 | 2 |
| C | 6 | 10 | 2 |
| D | 6 | 110 | 3 |
| E | 5 | 111 | 3 |
// Ejemplos de código
Frequencies A=15 B=7 C=6 D=6 E=5 (39 symbols)
1. Sort symbols by frequency (descending).
2. Split the list where the two halves' totals are closest:
{A,B}=22 | {C,D,E}=17 -> first bit 0 / 1
3. Recurse on each half until single symbols remain:
{A}|{B} -> 00, 01 {C}|{D,E} -> 10, 11.. then {D}|{E} -> 110, 111
Total 15*2 + 7*2 + 6*2 + 6*3 + 5*3 = 89 bits
Huffman on the same data: A=1 bit, others 3 bits -> 87 bits
>> Más preguntas
P: ¿En qué se diferencia Shannon-Fano de Huffman?
R: Shannon-Fano divide la lista ordenada de arriba abajo en dos mitades de frecuencia lo más igual posible; Huffman construye el árbol de abajo arriba fusionando los símbolos más raros. Huffman es óptimo demostrablemente; Shannon-Fano no siempre.
P: ¿Es Shannon-Fano siempre óptimo?
R: No. En el ejemplo necesita 89 bits frente a 87 de Huffman. Ambos dan códigos libres de prefijo, pero la regla de división de Shannon-Fano puede elegir cortes poco favorables.
P: ¿Dónde se usa Shannon-Fano?
R: Sobre todo como método histórico y didáctico (Claude Shannon y Robert Fano, 1948/49). Una variante está en el algoritmo IMPLODE del formato ZIP; los compresores modernos usan Huffman o codificación aritmética.