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.^[1]

Algoritmo

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.

Um pseudo-algoritmo que realiza este processo se encontra a seguir:

Estruturas de dados:
conjunto: Pilha
conjunto0, conjunto1: lista ordenada ou heap.

Programa:

conjunto.empilha(alfabeto)

# Processa enquanto houver conjuntos com mais de um elemento
enquanto conjunto não estiver vazio:
   conjunto0 := conjunto.desempilha()
   conjunto1 := conjunto vazio
   max_prob := somatorio(conjunto0)
   probabilidade := 0

   # Divide em duas partes de probabilidades semelhantes
   enquanto probabilidade < (max_prob/2):
      elemento := conjunto0.remove_menor_elemento()
      conjunto1.enfileira(elemento)
      probabilidade := probabilidade   elemento.valor
   fim enquanto

   # Acrescenta um dígito no código de cada metade
   para cada elemento em conjunto0:
      concatena(elemento.código, 0)
   fim para
   para cada elemento em conjunto1:
      concatena(elemento.código, 1)
   fim para

   # repete até o conjunto estar com apenas um elemento.
   se tamanho(conjunto0) > 1
      conjunto.empilha(conjunto0)
   fim se
   se tamanho(conjunto1) > 1
      conjunto.empilha(conjunto1)
   fim se
fim enquanto'

Exemplo

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:

Caractere	A	B	C	D	E	F
Código	000	001	010	011	100	101

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:

Caractere	A	B	C	D	E	F
Contagem	6	5	4	3	2	1

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.

Símbolo	A	B	C	D	E	F
Freqüência	6	5	4	3	2	1
	0		1
	0	1	0	1
				0	1
				0	0	1
Códigos	00	01	10	110	1110	1111

A codificação final fica então sendo: 000000000000010101010110101010110110110111011101111 num total de 51 bits. Note que nesse caso a codificação tem o mesmo tamanho que se usarmos a codificação de Huffman. Em geral o método de Shannon-Fano tem resultados semelhantes ao método de Huffman, podendo ser provado que o tamanho médio dos caracteres, T, nos dois métodos obedece a seguinte relação (onde o subscrito representa a inicial do métodos)^[2]:

$T_{H}\leq T_{SF}\leq T_{H} 1$

Aplicações

O algoritmo de implode usado no PKZIP e outros compactadores de arquivos em formato ZIP usa a codificação de Shannon-Fano em conjunto com um algoritmo de janela deslizante baseado em LZ77.

Referências

↑ É possível provar que o código gerado pelo método de Huffman gera códigos livre de prefixo de tamanho ótimo para cada símbolo. Vale a pena notar que quando não se codificam símbolos diretamente, como a codificação aritmética ou os métodos baseados em dicionário (LZ77, LZ78 e derivados) podem apresentar resultados melhores em determinadas condições. Ver SALOMON, David (2000). Data Compression. The Complete Reference 2 ed. Nova Iorque: Springer. ISBN 0-387-95045-1 para uma discussão sobre a otimalidade da codificação de Huffman
↑ SALOMON, David (2000). Data Compression. The Complete Reference 2 ed. Nova Iorque: Springer. ISBN 0-387-95045-1

Bibliografia

(em inglês) SALOMON, David (2000). Data Compression. The Complete Reference 2 ed. Nova Iorque: Springer. ISBN 0-387-95045-1

Ver também

[1] É possível provar que o código gerado pelo método de Huffman gera códigos livre de prefixo de tamanho ótimo para cada símbolo. Vale a pena notar que quando não se codificam símbolos diretamente, como a codificação aritmética ou os métodos baseados em dicionário (LZ77, LZ78 e derivados) podem apresentar resultados melhores em determinadas condições. Ver SALOMON, David (2000). Data Compression. The Complete Reference 2 ed. Nova Iorque: Springer. ISBN 0-387-95045-1 para uma discussão sobre a otimalidade da codificação de Huffman

[2] SALOMON, David (2000). Data Compression. The Complete Reference 2 ed. Nova Iorque: Springer. ISBN 0-387-95045-1

[1]

[2]