« 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 35 : | Ligne 35 : | ||
== 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] |
||
* [https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform |
* [https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform Wikipedia EN] |
||
Version du 15 mai 2020 à 13:23
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