Résumé:
Dans le cadre de notre travail, on s'est int eress e au fameux probl eme de compression
de donn ees. La Transform ee de Burrows-Wheeler [1] (BWT) est l'un des outils
les plus reconnu dans la r esolution de ce probl eme. Mais sa construction est vraiment
co^uteuse que sa soit en terme de m emoire ou en terme de temps de calcul. Pour cela on a
d evelopp e un algorithme parall ele qui vise principalement la diminution de l'espace
de travail ainsi que le temps d'ex ecution construisant un tableau de su xe qui sert a
calculer la Transform ee d'une mani ere e cace.
Les tests et comparaisons e ectu e sur des impl ementations existantes d ej a et sur notre
impl ementation montre bien l'e cacit e de cette derni ere surtout en terme d'espace de
travail et aussi en temps d'ex ecution qui est acceptable.
Mots cl es: compression de donn ees, Transform ee de Burrows-Wheeler, BWT, algorithme
parall ele, diminution de l'espace de travail, tableau de su xe, e cace. As part of our work, we have focused on the famous problem of data compression.
The Burrows-Wheeler Transform [1] (BWT) is one of the most recognized tools in
solving this problem. But its construction is really expensive, whether in terms of memory
or computing time. For this purpose, we have developed a parallel algorithm that
mainly aims to reduce the workspace and the execution time by building a su x
array which serves to calculate the BWT e ciently.
The tests performed on our implementation show its e ciency in terms of workspace and
also execution time that is acceptable.
Keywords: data compression, Burrows-Wheeler Transform, BWT, parallel algorithm,reduce
the workspace, su x array, e ciently.
