> huffman | codage | optimal <
// Codage de Huffman – algorithme de compression optimal sans préfixe
>> fonctionnalités
Codes optimaux
Génère la longueur moyenne de code la plus courte pour les fréquences données.
Sans préfixe
Aucun code n'est le préfixe d'un autre, ce qui garantit un décodage sans ambiguïté.
Basé sur la fréquence
Les caractères les plus fréquents obtiennent automatiquement des codes plus courts.
>> informations techniques
Comment fonctionne le codage de Huffman
Le codage de Huffman construit un arbre binaire de bas en haut. À partir des fréquences des caractères, il combine à plusieurs reprises les deux nœuds de plus faible fréquence en un nœud parent jusqu'à ce qu'il ne reste que la racine. Les branches gauche représentent '0' et les droites '1'. Les caractères plus fréquents reçoivent des codes plus courts, ce qui produit une compression optimale pour la distribution de fréquences donnée.
Exemple de codage de Huffman
Text: "AABBBCCCC"
Frequencies:
A: 2
B: 3
C: 4
Tree Building:
1. Combine A(2) + B(3) = AB(5)
2. Combine C(4) + AB(5) = Root(9)
Tree:
Root(9)
/ \
C(4) AB(5)
/ \
A(2) B(3)
Codes:
C: 0
A: 10
B: 11
Encoded: 10 10 11 11 11 0 0 0 0
= 1010111111 0000
Pourquoi utiliser le codage de Huffman ?
- Taux de compression presque optimal
- Implémentation simple
- Base de la compression ZIP/JPEG
- Aucune perte de données
- Efficacité démontrée en pratique
>> questions fréquentes
Qu'est-ce que le codage de Huffman ?
Le codage de Huffman est un algorithme de compression optimal et sans préfixe, proposé par David A. Huffman en 1952. Il attribue des codes de longueur variable aux caractères selon leur fréquence : les caractères les plus fréquents reçoivent des codes plus courts, ce qui minimise la longueur moyenne du code.
Pourquoi parle-t-on de codes sans préfixe ?
Un code est sans préfixe lorsqu'aucun mot de code n'est le préfixe d'un autre. Par exemple, si « A » est codé par « 01 », aucun autre caractère ne peut avoir un code commençant par « 01 ». Cette propriété garantit un décodage non ambigu : on sait toujours où se termine un code et où commence le suivant, sans séparateurs supplémentaires.
Quelle est l'efficacité du codage de Huffman ?
Le codage de Huffman atteint la compression optimale pour une distribution de fréquences donnée et se situe généralement à moins d'un bit de la limite théorique d'entropie. Pour du texte en anglais, on observe souvent 60 à 70 % de compression. Il est particulièrement efficace lorsque les fréquences des caractères varient fortement.
Où utilise-t-on le codage de Huffman ?
Le codage de Huffman est utilisé dans la compression d'images JPEG, la compression de fichiers ZIP (avec LZ77 dans DEFLATE), l'audio MP3 et de nombreux autres formats. Il est souvent combiné avec d'autres algorithmes : JPEG applique Huffman après la DCT et la quantification, tandis que ZIP l'utilise après LZ77.