// Codage Tunstall – compression optimale variable-vers-longueur fixe
Associe des séquences de longueur variable à des codes de longueur fixe.
Le dictionnaire est construit à partir de la distribution de probabilité des symboles.
Les codes de longueur fixe permettent un décodage simple et rapide.
Le codage Tunstall construit un dictionnaire de séquences de longueur variable associées à des codes binaires de longueur fixe. À partir de symboles uniques, on étend itérativement la séquence la plus probable en ajoutant chaque symbole de l'alphabet. On obtient ainsi un code variable-vers-fixe optimal où les séquences les plus probables reçoivent leurs propres mots de code.
Texte : 'aabaa' avec P(a)=0.8, P(b)=0.2 Construction du dictionnaire (codes sur 3 bits) : Initial : a, b Étendre 'a' : aa, ab Étendre 'aa' : aaa, aab Étendre 'ab' : aba, abb Dictionnaire final (8 codes) : aaa → 000 aab → 001 aba → 010 abb → 011 aa → 100 ab → 101 a → 110 b → 111 Encodage : 'aabaa' → 001 100 (aab + aa)
Le codage Tunstall est une méthode de codage entropique de type variable-vers-fixe. Contrairement à Huffman (fixe-vers-variable), Tunstall associe des séquences de longueur variable à des mots de code de longueur fixe, ce qui le rend idéal pour les applications nécessitant un débit de sortie constant.
Huffman : entrée fixe → sortie variable (par ex. 'a' → '0', 'b' → '10'). Tunstall : entrée variable → sortie fixe (par ex. 'aa' → '000', 'ab' → '001'). Tunstall est mieux adapté au matériel et à la synchronisation, mais offre généralement des taux de compression légèrement inférieurs.
On commence par des symboles uniques. Puis on répète : 1) trouver la séquence la plus probable, 2) la retirer et ajouter toutes les extensions possibles en ajoutant un symbole, 3) continuer jusqu'à atteindre la taille de dictionnaire souhaitée (2^n pour des codes sur n bits).
Le codage Tunstall est utilisé pour la compression de la parole, le codage d'images et partout où un débit de sortie fixe est nécessaire. Il est particulièrement utile dans les implémentations matérielles et les systèmes temps réel, où des codes de longueur variable compliqueraient la synchronisation.