> tunstall | variable | fixe <
// Codage Tunstall – compression optimale variable-vers-longueur fixe
Encodage V2F
Associe des séquences de longueur variable à des codes de longueur fixe.
Basé sur les probabilités
Le dictionnaire est construit à partir de la distribution de probabilité des symboles.
Décodage simple
Les codes de longueur fixe permettent un décodage simple et rapide.
>> informations techniques
Comment fonctionne le codage Tunstall:
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.
Exemple Tunstall:
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)
Pourquoi utiliser le codage Tunstall ?:
- ▸Codes de sortie de longueur fixe
- ▸Implémentation simple du décodeur
- ▸Aucun problème de synchronisation
- ▸Adapté aux implémentations matérielles
- ▸Optimal pour les sources sans mémoire
>> foire aux questions
Qu'est-ce que le codage Tunstall ?
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.
Tunstall vs codage Huffman ?
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.
Comment le dictionnaire est-il construit ?
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).
Où le codage Tunstall est-il utilisé ?
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.