« Transformée Burrows Wheeler » : différence entre les versions
Aucun résumé des modifications |
Aucun résumé des modifications |
||
| Ligne 13 : | Ligne 13 : | ||
Prenons le mot ''ABRACADABRA''. |
Prenons le mot ''ABRACADABRA''. |
||
Voici les étapes à suivre : |
|||
La matrice de rotation associé est la suivante : |
|||
1. On créer la matrice des rotations |
|||
<pre><code> |
|||
ABRACADABRA |
ABRACADABRA |
||
BRACADABRAA |
BRACADABRAA |
||
| Ligne 26 : | Ligne 28 : | ||
RAABRACADAB |
RAABRACADAB |
||
AABRACADABR |
AABRACADABR |
||
</code></pre> |
|||
2. On trie les lignes suivant un certain ordre. Ici, par ordre alphabétique |
|||
== Algorithme == |
== Algorithme == |
||
Version du 15 mai 2020 à 13:33
La transformée de Burrows-Wheeler (aussi appelé BWT) est la seconde étape, mais pas des moindres, de l'algorithme de compression bzip2. C'est d'ailleurs l'un des deux principaux rouages de l'algorithme d'après son auteur :
bzip2 compresses files using the Burrows-Wheeler block sorting text compression algorithm, and Huffman coding.
- Julian Seward
Utilisation
Cette transformée est utilisée pour faire apparaître des motifs redondants, ce qui aide à la compression avec l'encoding d'Huffman.
Principe de fonctionnement
La transformé de Burrows-Wheeler se construit à partir d'une matrice de permutations des lettres du mot (ou d'une séquence d'octet de façon général).
Prenons le mot ABRACADABRA. Voici les étapes à suivre :
1. On créer la matrice des rotations
<code> ABRACADABRA BRACADABRAA RACADABRAAB ACADABRAABR CADABRAABRA ADABRAABRAC DABRAABRACA ABRAABRACAD BRAABRACADA RAABRACADAB AABRACADABR </code>
2. On trie les lignes suivant un certain ordre. Ici, par ordre alphabétique