Codage de Shannon-Fano

Ce calculateur en ligne produit le codage de Shannon-Fano pour un ensemble de symboles suivant leurs probabilités données. Un peu de théorie est disponible sous le calculateur.

Codage de Shannon-Fano



Tableau de probabilité des symboles

	Nom	Valeur
			

Précision de calcul

Chiffres après la virgule décimale : 2

Calculer

Longueur pondérée du chemin

 

Entropie de Shannon

 

Le fichier est très volumineux; un ralentissement du navigateur peut se produire pendant le chargement et la création.

Télécharger 

 Lien  sauvegarder  Widget

Codage de Shannon-Fano

Dans le domaine de la compression de données, le codage de Shannon-Fano, nommé après Claude Shannon et Robert Fano, est une technique pour construire un code préfixe basé sur un ensemble de symboles et leurs probabilités (estimées ou mesurées). Elle est sous-optimale dans le sens qu'elle n'atteint pas la longueur de mot prévu la plus petite possible comme Codage de Huffman.

Dans le codage de Shannon–Fano, les symboles sont arrangés du plus probables au moins probables puis divisés en deux ensembles dont les probabilités totales sont aussi proches possibles de l'égalité. Ensuite, tous les symboles sont associés avec le premier chiffre de leurs codes : les symboles du premier ensemble reçoivent "0" et les symboles du second ensemble reçoivent "1". Tant que des ensembles avec plus d'un membre restent, la même processus est répété sur ces ensembles, afin de déterminer les chiffres suivants de leurs cordes. Lorsqu'un ensemble a été réduit à un symbole, ceci signifie que le code du symbole est complet et ne formera plus le préfixe du code d'un autre symbole.

L'algorithme produit un codage de la longueur des variables assez efficace ; lorsque deux ensembles plus petits sont produits par un partitionnement ont en fait une probabilité égale, le bit d'information utilisé pour les distingués est alors utilisés le plus efficacement possible. Malheureusement, Shannon-Fato ne produit pas toujours des codes de préfixe optimaux : l'ensemble des probabilités {0,35, 0,17, 0,17, 0,16, 0,15} est un exemple d'ensemble qui assignera des codes non-optimaux avec le codage de Shannon-Fano.

Pour cette raison, Shannon-Fano n'est presque jamais utilisé ; Codage de Huffman est presque aussi simple en termes de calculs et produit des codes de préfixe qui atteignent toujours la longueur de mot prévu la plus petite, sous la contrainte que chaque symbole soit représenté par un code formé d'un nombre entier de bits.¹