> mtf | move | front <
// Move-to-Front - Réorganisation dynamique de la liste pour une meilleure compression
Auto-adaptatif
S’adapte automatiquement aux motifs locaux des données.
Exploite la localité
Les symboles récents reçoivent des indices plus petits pour une meilleure compression.
Partie de bzip2
Utilisé après la BWT dans la chaîne de compression bzip2.
>> informations techniques
Comment fonctionne MTF:
MTF maintient une liste de tous les symboles possibles. Lors de l’encodage d’un symbole, on émet sa position actuelle dans la liste, puis on le déplace en tête. Ainsi, les symboles récemment utilisés obtiennent de petits indices, ce qui se compresse mieux avec une codification entropique ultérieure.
Exemple d’encodage:
Texte : "banana" Liste initiale : [a,b,c,d,...] "b" : indice 1, déplacer b→tête [b,a,c,d,...] "a" : indice 1, déplacer a→tête [a,b,c,d,...] "n" : indice 13, déplacer n→tête [n,a,b,c,...] "a" : indice 1, déplacer a→tête [a,n,b,c,...] "n" : indice 1, déplacer n→tête [n,a,b,c,...] "a" : indice 1, déplacer a→tête [a,n,b,c,...] Sortie : [1,1,13,1,1,1]
Pourquoi utiliser MTF:
- >Améliore la redondance locale
- >Fonctionne avec BWT
- >Implémentation simple
- >Transformation réversible
- >S’adapte aux motifs
>> foire aux questions
Qu’est-ce que l’encodage Move-to-Front ?
MTF est un algorithme de transformation de données qui encode chaque symbole comme son indice dans une liste mise à jour dynamiquement. Après l’encodage, chaque symbole est déplacé en tête de liste, de sorte que les symboles fréquents aient de petits indices.
Pourquoi utiliser MTF avec BWT ?
La BWT regroupe les contextes similaires et crée des répétitions locales. MTF transforme ensuite ces répétitions en petits nombres (beaucoup de 0 et de 1), qui se compressent très bien avec la codification par plages ou la codification de Huffman.
Comment fonctionne la liste MTF ?
La liste commence avec les 256 valeurs d’octet possibles dans l’ordre. Au fur et à mesure de l’encodage, les symboles utilisés sont déplacés en tête. Les symboles récemment utilisés restent près du début avec de petits indices, tandis que les symboles rares se déplacent vers des indices plus grands.
MTF vs autres transformations ?
MTF est conçu spécifiquement pour être utilisé après BWT. Il est peu efficace seul, mais excellent pour transformer la sortie de BWT en une forme très compressible. Il est plus simple que la codification arithmétique, mais moins optimal.