Codes de Huffman et de Fano
Vérifiez la condition du préfixe (Fano), construisez un code de Huffman, vérifiez le décodage unique et trouvez le code le plus court pour une nouvelle lettre.
Le calculateur de codes de Fano et de Huffman vérifie la condition du préfixe (Fano), construit un code de Huffman optimal à partir des fréquences des symboles ou d'un texte, vérifie le caractère uniquement décodable et trouve le code le plus court pour une nouvelle lettre.
La condition du préfixe
Aucun mot de code ne doit être le début (préfixe) d'un autre. Le message se décode alors de façon unique et immédiate. Si la condition inverse est vérifiée — aucun mot n'est la fin d'un autre — le message se décode aussi de façon unique, mais à partir de la fin.
Code de Huffman
Les deux symboles de plus petites fréquences sont regroupés en un nœud, et ainsi de suite jusqu'à ce qu'il ne reste qu'un arbre ; la branche de gauche vaut 0, celle de droite 1. Les symboles fréquents reçoivent des codes courts et la longueur totale du message est minimale.
Décodage unique
Si la condition du préfixe n'est pas remplie, l'unicité se vérifie avec l'algorithme de Sardinas–Patterson : on cherche les suffixes « pendants » et on vérifie si l'un d'eux est égal à un mot de code.
Exemple. Codes A — 00, B — 010, C — 011, D — 101. Un code pour une nouvelle lettre : aucun mot de 1 bit ne convient (0 commence A, 1 commence D) ; parmi les mots de 2 bits, seul 11 convient.
Calculateurs associés
Commentaires
Aucun commentaire pour le moment.