Aller au contenu
Omnikalc

Calculateur de longueur de code de Huffman

Saisissez les fréquences de quatre symboles pour obtenir la longueur moyenne du code de Huffman, l’entropie, le rendement et la taille d’un message.

Mis à jour le
Vos paramètres

Valeur hors limites

Valeur hors limites

Valeur hors limites

Valeur hors limites

symboles

Valeur hors limites

Résultats

Longueur moyenne du code de Huffman

1,8000 bits/symbole

Entropie de la source

1,7822 bits/symbole

Rendement du codage (entropie ÷ longueur moyenne)
99,01 %
Redondance (longueur moyenne − entropie)
0,0178 bits/symbole
Économie par rapport à un code fixe de 2 bits
10,0 %
Taille du message avec le code de Huffman
2 250 octets

Le calculateur de longueur de code de Huffman donne la longueur moyenne du code de Huffman, l’entropie, le rendement du codage, la redondance, l’économie par rapport à un code fixe de 2 bits et la taille d’un message pour une source de quatre symboles.

Comment se fait le calcul

  • Saisissez la fréquence de chacun des quatre symboles, en effectifs ou en pourcentages.
  • Saisissez la longueur du message en symboles.
  • Lisez la longueur moyenne, comparez-la à l’entropie et voyez la taille du message codé.

Exemple

Quatre symboles de fréquences 45, 30, 15 et 10 ont une entropie de 1,7822 bits/symbole. Le code de Huffman a une longueur moyenne de 1,8000 bits/symbole, un rendement de 99,01 % et une redondance de 0,0178 bits/symbole. Il économise 10,0 % par rapport à un code fixe de 2 bits : un message de 10000 symboles occupe 2 250 octets.

Pourquoi c’est utile

Le calculateur aide les étudiants en informatique, les programmeurs et les ingénieurs qui étudient la compression de données, vérifient un exercice sur les arbres de Huffman, ou veulent savoir à quel point un code préfixe approche la limite de l’entropie avant de choisir un schéma de codage pour un protocole ou un format de fichier.

À savoir

Utilisez les fréquences réelles des symboles dans vos données, en effectifs ou en pourcentages, toutes supérieures à zéro. Le résultat est la longueur moyenne d’un code optimal symbole par symbole, sans le coût de stockage de la table de codage ni de l’en-tête. Les données réelles présentent souvent des dépendances entre symboles que le codage arithmétique ou les méthodes à dictionnaire exploitent mieux. Pour plus de quatre symboles, la même procédure de fusion s’applique, mais ce calculateur est limité à quatre.

Outils liés

Le calculateur d’entropie de Shannon donne la limite théorique pour un nombre quelconque de symboles, celui de la surcharge de l’encodage de données montre le coût d’un codage, celui du bit de parité ajoute une détection d’erreur et celui des combinaisons dénombre les messages possibles.

Questions fréquentes

Qu’est-ce qu’un code de Huffman ?

Un code de Huffman est un code préfixe optimal : il attribue des chaînes de bits courtes aux symboles fréquents et longues aux symboles rares, de sorte que la longueur moyenne soit la plus petite possible pour un codage symbole par symbole. Il se construit en fusionnant à répétition les deux éléments les moins fréquents jusqu’à obtenir un seul arbre.

Comment la longueur moyenne est-elle calculée ici ?

Pour quatre symboles, l’algorithme de Huffman fait trois fusions. La longueur moyenne du code est la somme des poids des nœuds fusionnés, divisée par le total, plus un pour la racine. Le calculateur trie les fréquences, fusionne les deux plus petites, puis fusionne à nouveau les deux plus petites des trois éléments restants.

Comment se compare-t-elle à l’entropie ?

L’entropie H est la borne inférieure théorique de la longueur moyenne de tout code de symboles, et le codage de Huffman vérifie toujours H ≤ L < H + 1. Les deux ne sont égales que si toutes les probabilités sont des puissances de un demi. L’écart est la redondance, que l’on réduit en codant des blocs de symboles.

Le code dépend-il des fréquences exactes ?

Seulement de leur ordre et de leurs tailles relatives. Les égalités peuvent donner des arbres différents, mais la longueur moyenne est toujours la même. Utiliser les fréquences réelles de vos données donne le meilleur résultat, et un code construit pour une source est peu performant si les statistiques changent.

Ce calculateur vous a-t-il été utile ?

Merci pour votre avis !

Résultats indicatifs fournis à titre d'information. Ils ne remplacent pas l'avis d'un professionnel.