La compression sans perte est limitée par la quantité de redondance qu'une méthode peut percevoir. Les méthodes de la famille LZ et le codage de Huffman atteignent chacun un palier sur du texte ordinaire.
Le rapport DEC de Burrows et Wheeler de 1994 décrivait une transformation par tri de blocs : lister toutes les rotations du bloc, les trier, puis émettre la dernière colonne. Comme les rotations partagent des suffixes, les caractères identiques se regroupent, et une courte passe de codage par plages (run-length) et move-to-front réduit cela à très peu de symboles.
La transformation est inversible : c'est donc un réarrangement, non une perte. Le résultat a alimenté bzip2, qui compressait le texte plus efficacement que les outils contemporains et a fait de cette technique la référence pour une compression lente mais dense.
Trier les rotations du bloc afin que les voisins se ressemblent
Le tri des rotations rapproche les symboles identiques là où le contexte est le même.
Le codage par plages et move-to-front trouve ensuite de longues séquences peu coûteuses.
La transformation est une permutation, donc la décompression est exacte.
Elle fonctionne sur toute structure répétée, et n'est donc pas adaptée à un seul type de fichier.
Avant de compresser, réordonnez les données afin que les symboles identiques se retrouvent côte à côte. Une transformation qui regroupe les parties prévisibles peut rendre un compresseur ordinaire nettement plus puissant.
Suites
La transformation de Burrows-Wheeler est devenue le moteur de bzip2, puis la base du FM-index, qui recherche des sous-chaînes et cartographie des génomes. La même idée alimente aujourd'hui les outils d'alignement bioinformatique à haut débit.
VÉRIFIEZ LES SOURCES
Les sources
- A block-sorting lossless data compression algorithm DEC Systems Research Center Research Report 124 · web.stanford.edu
- Burrows-Wheeler transform Wikipedia · en.wikipedia.org