Codage de Huffman
Ce calculateur en ligne génère l'encodage de Huffman pour une fréquence données d'occurrence de symboles.
Cette page existe grâce aux efforts des personnes suivantes :
 | Timur
|
Gaulthier Marrel
|
Ce contenu est sous License Creative Commons Attribution/Partage à l'Identique 3.0(Unported). Cela signifie que vous pouvez redistribuer ou modifier librement ce contenu avec les mêmes modalités de licence et que vous devez créditer l'auteur original en plaçant un lien hypertexte de votre site vers l'œuvre https://fr.planetcalc.com/2481/. Vous ne pouvez pas modifier (le cas échéant) les références dans le contenu de l'œuvre originale.
Ce calculateur en ligne génère l'encodage de Huffman pour une fréquence données d'occurrence de symboles.
Une courte description de l'encodage de Huffman est sous le calculateur.
Codage de Huffman
Tableau de probabilité des symboles
| Nom | Valeur | ||
|---|---|---|---|
Issue de wikipedia
En sciences informatiques et dans la théorie de l’information, l’encodage de Huffman est un algorithme d’encodage entropiques utilisé pour la compression de données dans perte. Le terme se réfère à l’utilisation d’un tableau de codage de longueur variable pour encoder un symbole source (tel qu'un caractère dans un fichier) où le tableau de codage de longueur variable a été dérivé d’une certaine manière basée sur la probabilité estimée d’occurrence de chaque valeur possible du symbole source. Le codage a été inventé par David Albert Huffman, lors de sa thèse de doctorat au MIT. L'algorithme a été publié en 1952 dans l'article “A Method for the Construction of Minimum-Redundancy Codes”
Le codage de Huffman utilise une méthode spécifique pour choisir la représentation de chaque symbole, résultant en un préfixe (parfois appelé « code préfixe » qui est la chaîne de bits représentant un symbole particulier qui n’est jamais le préfixe ou la chaîne représentant un autre symbole) qui exprime les symboles sources les plus communs un utilisant des chaînes de bits plus courtes que celles utilisées pour les symboles plus rares. Huffman a pu concevoir la méthode de compression de ce type la plus efficace : aucune autre modélisation de symboles sources individuels vers une chaîne de bits unique ne produira un résultat de taille moyenne plus petite lorsque la fréquence des symboles actuels est en accord avec celle utilisée pour créer le code.
Le codage de Huffman est une méthode tellement répandue pour créer des préfixes que le terme "Codage de Huffman" est très utilisé en tant que synonyme de "code préfixe » même lorsqu'un tel code n’est pas produit par l’algorithme de Huffman.
Le principe du codage de Huffman repose sur la création d’un arbre binaire composé de nœuds. Au début, tous les nœuds sont des feuilles qui contienne le symbole en lui-même, le poids (fréquence d’apparition) du symbole et, parfois, un lien vers un nœud parent qui facilite la lecture du code (en sens inverse) en comment depuis une feuille. Les nœuds internes contiennent le poids du symbole, les liens vers les deux nœuds enfants et parfois le lien vers un nœud parent. Comme convention commune, le bit '0' représente l’enfant de gauche et le bit '1' celui de droite. Un arbre fini a jusqu'à n feuilles et n-1 nœuds internes. Un arbre de Huffman qui omet les symboles non utilisés produits la longueur de code la plus optimale.
Cette procédure débute principalement avec les feuilles contenant les probabilités du symbole qu'elles représentent, puis un nouveau nœud dont les enfants sont les 2 nœuds où les propriétés les plus petites sont créées afin que la probabilité du nouveau nœud soit égale à la somme des probabilités des enfants. Lorsque les 2 nœuds précédents sont fusionnés en un seul nœud (donc plus pris en considération) et avec le nouveau nœud étant considéré, la procédure est répétée jusqu'à ce qu'il ne reste qu'un seul nœud, l’arbre de Huffman.
commentaires