Calculadora de codificação de Shannon-Fano
Esta calculadora online gera codificação de Shannon-Fano baseada em um conjunto de símbolos e suas probabilidades
Esta calculadora online produz codificação de Shannon-Fano para um conjunto de símbolos de acordo com suas probabilidades. Um pouco da teoria pode ser encontrada abaixo da calculadora.
Codificação de Shannon-Fano
No campo da compressão de dados, a codificação de Shannon-Fano, em homenagem a Claude Shannon e Robert Fano, é uma técnica para construir um código de prefixo baseado em um conjunto de símbolos e suas probabilidades (estimadas ou medidas). É subótimo no sentido de que não atinge o menor comprimento de palavra de código esperado possível, como Codificação de Huffman.
Na codificação de Shannon-Fano, os símbolos são organizados em ordem do mais provável para o menos provável, e seguidamente, divididos em dois conjuntos cujas probabilidades totais são as mais próximas possíveis de serem iguais. Todos os símbolos têm, portanto, os primeiros dígitos de seus códigos atribuídos; os símbolos do primeiro conjunto recebem "0" e os símbolos do segundo conjunto recebem "1". Enquanto restarem conjuntos com mais de um membro, o mesmo processo é repetido nesses conjuntos para determinar dígitos sucessivos de seus códigos. Quando um conjunto foi reduzido a um símbolo, significa que o código do símbolo está completo e não formará o prefixo do código de nenhum outro símbolo.
O algoritmo produz codificações de comprimentos variáveis bastante eficientes; quando os dois conjuntos menores produzidos por um particionamento são de fato de probabilidade igual, o pouco de informação usada para distingui-los é usado com mais eficiência. Infelizmente, Shannon-Fano nem sempre produz ótimos códigos de prefixo; o conjunto de probabilidades {0.35, 0.17, 0.17, 0.16, 0.15} é um exemplo de um que será atribuído a códigos que não são ótimos pela codificação de Shannon-Fano.
Por esta razão, a Shannon–Fano raramente é usada; A Codificação de Huffman é quase tão simples computacionalmente e produz códigos de prefixo que sempre alcançam o menor comprimento de palavra de código esperado, sob as restrições de que cada símbolo é representado por um código formado por um número inteiro de bits.1
Comentários