« Transformée Burrows Wheeler » : différence entre les versions
Aller à la navigation
Aller à la recherche
Aucun résumé des modifications |
Aucun résumé des modifications |
||
| Ligne 3 : | Ligne 3 : | ||
<blockquote> |
<blockquote> |
||
<p>bzip2 compresses files using the Burrows-Wheeler block sorting text compression algorithm, and Huffman coding.</p> |
<p>bzip2 compresses files using the Burrows-Wheeler block sorting text compression algorithm, and Huffman coding.</p> |
||
- Julian Seward |
<p>- Julian Seward</p> |
||
</blockquote> |
</blockquote> |
||
| Ligne 10 : | Ligne 10 : | ||
== Principe de fonctionnement == |
== 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''. |
|||
La matrice de rotation associé est la suivante : |
|||
ABRACADABRA |
|||
BRACADABRAA |
|||
RACADABRAAB |
|||
ACADABRAABR |
|||
CADABRAABRA |
|||
ADABRAABRAC |
|||
DABRAABRACA |
|||
ABRAABRACAD |
|||
BRAABRACADA |
|||
RAABRACADAB |
|||
AABRACADABR |
|||
== Algorithme == |
== Algorithme == |
||
| Ligne 16 : | Ligne 32 : | ||
=== Implémentation avancé === |
=== Implémentation avancé === |
||
== Sources == |
|||
* [https://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-124.pdf A block sorting lossless data compression algorithm] |
|||
* [https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform Wikipedian EN] |
|||
Version du 15 mai 2020 à 13:22
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. La matrice de rotation associé est la suivante :
ABRACADABRA BRACADABRAA RACADABRAAB ACADABRAABR CADABRAABRA ADABRAABRAC DABRAABRACA ABRAABRACAD BRAABRACADA RAABRACADAB AABRACADABR