« Transformée Burrows Wheeler » : différence entre les versions
Aucun résumé des modifications |
Aucun résumé des modifications |
||
| Ligne 16 : | Ligne 16 : | ||
1. On créer la matrice des rotations |
1. On créer la matrice des rotations |
||
<pre><code> |
|||
ABRACADABRA |
ABRACADABRA |
||
BRACADABRAA |
BRACADABRAA |
||
| Ligne 28 : | Ligne 28 : | ||
RAABRACADAB |
RAABRACADAB |
||
AABRACADABR |
AABRACADABR |
||
</code></pre> |
|||
2. On trie les lignes suivant un certain ordre. Ici, par ordre alphabétique |
2. On trie les lignes suivant un certain ordre. Ici, par ordre alphabétique |
||
AABRACADABR |
|||
== Algorithme == |
|||
ABRAABRACAD |
|||
ABRACADABRA |
|||
ACADABRAABR |
|||
ADABRAABRAC |
|||
BRAABRACADA |
|||
BRACADABRAA |
|||
CADABRAABRA |
|||
DABRAABRACA |
|||
RAABRACADAB |
|||
RACADABRAAB |
|||
3. On trouve la ligne contenant le mot initial, et on retiens sont indice I |
|||
| ⚫ | |||
AABRACADABR |
|||
| ⚫ | |||
ABRAABRACAD |
|||
'''ABRACADABRA I=3''' |
|||
ACADABRAABR |
|||
ADABRAABRAC |
|||
BRAABRACADA |
|||
BRACADABRAA |
|||
CADABRAABRA |
|||
DABRAABRACA |
|||
RAABRACADAB |
|||
RACADABRAAB |
|||
4. Pour finir cette transformée, nous devons avoir l'indice du mot initial et la dernière colone de la matrice : |
|||
AABRACADAB'''R''' |
|||
ABRAABRACA'''D''' |
|||
ABRACADABR'''A''' I=3 |
|||
ACADABRAAB'''R''' |
|||
ADABRAABRA'''C''' |
|||
BRAABRACAD'''A''' |
|||
BRACADABRA'''A''' |
|||
CADABRAABR'''A''' |
|||
DABRAABRAC'''A''' |
|||
RAABRACADA'''B''' |
|||
RACADABRAA'''B''' |
|||
Le résultat est donc ''3RDARCAAAABB''. On voit que dans cette exemple, quatre ''A'' se suivent ainsi que deux ''B''. Il est facile d'imaginer que sur des séquences beaucoup plus grande, il y aura suffisament de motif redondant pour que la compression soit bonne. |
|||
== Algorithmes == |
|||
variations d'algorithme... |
|||
| ⚫ | |||
grande matrice, mais limitation... |
|||
| ⚫ | |||
... donc on fait autrement |
|||
== Sources == |
== Sources == |
||
* [https://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-124.pdf A block sorting lossless data compression algorithm] |
* [https://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-124.pdf A block sorting lossless data compression algorithm] |
||
Version du 15 mai 2020 à 13:52
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
ABRACADABRA BRACADABRAA RACADABRAAB ACADABRAABR CADABRAABRA ADABRAABRAC DABRAABRACA ABRAABRACAD BRAABRACADA RAABRACADAB AABRACADABR
2. On trie les lignes suivant un certain ordre. Ici, par ordre alphabétique
AABRACADABR ABRAABRACAD ABRACADABRA ACADABRAABR ADABRAABRAC BRAABRACADA BRACADABRAA CADABRAABRA DABRAABRACA RAABRACADAB RACADABRAAB
3. On trouve la ligne contenant le mot initial, et on retiens sont indice I
AABRACADABR ABRAABRACAD ABRACADABRA I=3 ACADABRAABR ADABRAABRAC BRAABRACADA BRACADABRAA CADABRAABRA DABRAABRACA RAABRACADAB RACADABRAAB
4. Pour finir cette transformée, nous devons avoir l'indice du mot initial et la dernière colone de la matrice :
AABRACADABR ABRAABRACAD ABRACADABRA I=3 ACADABRAABR ADABRAABRAC BRAABRACADA BRACADABRAA CADABRAABRA DABRAABRACA RAABRACADAB RACADABRAAB
Le résultat est donc 3RDARCAAAABB. On voit que dans cette exemple, quatre A se suivent ainsi que deux B. Il est facile d'imaginer que sur des séquences beaucoup plus grande, il y aura suffisament de motif redondant pour que la compression soit bonne.
Algorithmes
variations d'algorithme...
Implémentation naïve
grande matrice, mais limitation...
Implémentation avancé
... donc on fait autrement