Shannon-Fano Coding

Definición:

La codificación de Shannon-Fano, nombrada en honor a Claude Shannon y Robert Fano, fue el primer algoritmo para construir un conjunto de códigos de tamaño variable óptimos. Comenzamos con un conjunto de n símbolos con probabilidades conocidas (o frecuencias) de ocurrencia. Los símbolos se organizan inicialmente en orden descendente de sus probabilidades. Luego, el conjunto de símbolos se divide en dos subconjuntos que tienen las mismas (o casi las mismas) probabilidades. Todos los símbolos en un subconjunto reciben códigos que comienzan con un 0, mientras que los códigos de los símbolos en el otro subconjunto comienzan con un 1. Luego, cada subconjunto se divide recursivamente en dos subsubconjuntos de probabilidades aproximadamente iguales, y el segundo bit de todos los códigos se determina de manera similar. Cuando un subconjunto contiene solo dos símbolos, sus códigos se distinguen agregando un bit más a cada uno. El proceso continúa hasta que ya no quedan subconjuntos.

Ejemplos de aplicación:

• Transmisión de Voz en Comunicaciones Telefónicas: En sistemas de transmisión de voz, donde la eficiencia en el uso del ancho de banda es crítica, la codificación de Shannon-Fano podría utilizarse para comprimir señales de audio. Al asignar códigos más cortos a los fonemas o sonidos más comunes, se logra una representación más compacta de la información de voz, lo que puede resultar en una transmisión más eficiente y un uso reducido de recursos de red.
• Compresión de Imágenes en Sistemas Embebidos: En entornos con recursos limitados, como sistemas embebidos, la codificación de Shannon-Fano podría aplicarse a la compresión de imágenes. Al asignar códigos de longitud variable a los píxeles de una imagen en función de su probabilidad de ocurrencia, se puede lograr una representación más compacta de la imagen. Esto podría ser útil en dispositivos con restricciones de almacenamiento o ancho de banda, como cámaras embebidas o sistemas de monitoreo remoto.

Implementación:

Implementación básica de la codificación en C++

#include <iostream>
#include <vector>
#include <algorithm>

struct Symbol {
    char symbol;
    double probability;
    std::string code;
};

bool compareSymbols(const Symbol& a, const Symbol& b) {
    return a.probability > b.probability;
}

void shannonFano(std::vector<Symbol>& symbols, int start, int end) {
    if (start == end - 1) {
        return;
    }

    std::sort(symbols.begin() + start, symbols.begin() + end, compareSymbols);

    double sumLeft = symbols[start].probability;
    double sumRight = 0;

    int splitIndex = start + 1;
    double minDifference = std::abs(sumLeft - sumRight);

    while (splitIndex < end - 1) {
        sumRight += symbols[splitIndex].probability;
        double difference = std::abs(sumLeft - sumRight);

        if (difference < minDifference) {
            minDifference = difference;
            splitIndex++;
        } else {
            break;
        }
    }

    for (int i = start; i < splitIndex; ++i) {
        symbols[i].code += '0';
    }

    for (int i = splitIndex; i < end; ++i) {
        symbols[i].code += '1';
    }

    shannonFano(symbols, start, splitIndex);
    shannonFano(symbols, splitIndex, end);
}

int main() {
    //ejemplo de prueba
    std::vector<Symbol> symbols = {
        {'A', 0.3, ""},
        {'B', 0.25, ""},
        {'C', 0.2, ""},
        {'D', 0.12, ""},
        {'E', 0.08, ""},
        {'F', 0.05, ""}
    };

    shannonFano(symbols, 0, symbols.size());

    for (const Symbol& symbol : symbols) {
        std::cout << "Symbol: " << symbol.symbol << ", Probability: " << symbol.probability
                  << ", Code: " << symbol.code << std::endl;
    }

    return 0;
}

Referencias:

• David Salomon (2007). Data Compression The Complete Reference.
• https://www.geeksforgeeks.org/shannon-fano-algorithm-for-data-compression/