Codificação de Shannon-Fano
A codificação de Shannon-Fano é um método de estatístico de compressão sem perda de dados que gera códigos de tamanho variável para cada símbolo dos conjunto de dados a ser comprimido de acordo com sua probabilidade de ocorrência. Este método foi descrito em 1948 por Claude Shannon em seu famoso artigo "A Mathematical Theory of Communication" e atribuído à Robert Fano. O método é anterior ao de codificação de Huffman, e apesar de bastante eficiente e prático, gera resultados sub-ótimos.
A construção do código a ser usado para a compressão segue um algoritmo bastante simples. Inicia-se com o levantamento das probabilidades de ocorrência de cada símbolo. Para efeitos práticos, a contagem do número de ocorrências de cada símbolo nos dados a serem comprimidos é o suficiente. Ordena-se então esta lista de probabilidades em ordem decrescente e separa-se a lista em duas partes de forma que cada uma dessas partes tenha aproximadamente a mesma probabilidade (i.e. a soma da probabilidade de cada símbolo de uma parte seja o mais próximo possível de 50%). A cada uma dessas partes atribui-se o primeiro dígito como sendo 0 (primeira parte) ou 1 (segunda parte). A cada metade que tiver mais de um dígito aplica-se o mesmo processo, concatenando os dígitos atribuídos em cada etapa. A seqüencia de dígitos que cada símbolo obteve nesse processo (os dígitos correspondentes a cada metade de que ele fez parte) são concatenados em ordem para formar o seu código.
Para demonstrar o algoritmo em uma situação prática, vamos comprimir a cadeia de exemplo: AAAAAABBBBBCCCCDDDEEF. Se usarmos a forma padrão onde o tamanho da representação de cada caractere é fixo, a menor codificação que podemos utilizar para representá-la em binário é de três bits por caractere. Assim temos a seguinte codificação: Gerando assim a os bits 000000000000000000001001001001001010010010010011011011100100101 para representar nossa seqüencia original. Isso dá 63 bits de comprimento. Para usar o código de Shannon-Fano e comprimir esta seqüência precisamos primeiro identificar os códigos de cada caractere usado, segundo o algoritmo mostrado acima. O primeiro passo é contar as ocorrências de cada símbolo na cadeia a ser comprimida. Com isso temos: Agora aplicamos o algoritmo nesses dados, identificando a codificação de cada caractere. O quadro abaixo mostra o funcionamento desse algoritmo, onde cada divisão dos conjuntos está devidamente ilustrada.
