Codificação Shannon-Fano
A codificação Shannon-Fano é um algoritmo de compressão de dados sem perdas desenvolvido por Robert Fano a partir de uma ideia de Claude Shannon .
Esta é uma codificação de entropia que produz um código de prefixo muito semelhante a um código de Huffman , embora nem sempre ótimo, ao contrário do último.
Princípio
A probabilidade de cada símbolo ser comprimido deve ser conhecida. Na maioria dos casos, frequências fixas ou ocorrências calculadas a partir dos dados a serem compactados são usadas; fala-se então de codificação Shannon-Fano semi-adaptativa (que requer duas passagens sucessivas nos dados a serem compactados: a primeira para calcular as probabilidades, a segunda para compactar estritamente falando). Também é possível usar probabilidades fixas não dependentes dos dados a serem compactados ( codificação estática ) ou probabilidades que variam conforme a compressão prossegue ( codificação adaptativa ).
O processo consiste em classificar os símbolos a serem compactados em ordem crescente de seu número de ocorrências . Em seguida, o conjunto classificado de símbolos é separado em dois grupos de forma que o número de ocorrências das duas partes seja igual ou quase igual (o número de ocorrências de um grupo sendo igual à soma das ocorrências dos diferentes símbolos de este grupo. grupo). Repetimos o processo até obter uma única árvore. Então, por exemplo, o código 0 é associado a cada ramificação rodando à esquerda e o código 1 à direita.
Comparação com a codificação de Huffman
A abordagem de codificação de Shannon-Fano é de cima para baixo: o algoritmo começa a partir do conjunto de símbolos e divide esse conjunto recursivamente até chegar às partes contendo apenas um símbolo. A desvantagem desta abordagem é que quando não é possível separar um conjunto de símbolos e dois subconjuntos de probabilidades aproximadamente iguais (ou seja, quando um dos subconjuntos é muito mais provável do que o outro), os códigos de produto não são ideais.
A codificação de Huffman tem uma abordagem bottom-up: o algoritmo parte dos símbolos e agrupa aqueles de menor probabilidade, até agrupar todos os símbolos. Esta abordagem permite obter sistematicamente um código ótimo ao nível do símbolo, no pior caso do mesmo comprimento que o código Shannon-Fano equivalente, em todos os outros casos mais curtos.
As codificações de Shannon-Fano e Huffman, no entanto, sofrem da mesma desvantagem: elas codificam símbolos em um número inteiro de bits. Uma codificação aritmética , que é ideal para bits, pode codificar símbolos em um número arbitrário de bits (incluindo 0) e atingir a entropia de Shannon .
Usos
Como a codificação de Huffman é muito semelhante à codificação de Shannon-Fano e dá melhores resultados, esta última raramente é usada hoje.
A codificação de Shannon-Fano é utilizada após a compressão pelo LZ77 , para codificação de entropia do algoritmo de implode , historicamente utilizado no formato ZIP . O algoritmo de implode foi destronado pelo algoritmo deflate , substituindo a codificação de Shannon-Fano por uma codificação de Huffman.
Veja também
Artigos relacionados
Bibliografia
- Claude Elwood Shannon, " A Mathematical Theory of Communication ", Bell System Technical Journal , vol. 27, pp. 379-423,.
- Robert Mario Fano, "A transmissão de informação", Relatório Técnico No. 65, 1949. Laboratório de Pesquisa de Eletrônica, MIT, Cambridge, EUA.