Algorithmes paralléles efficaces pour la construction de la transformées Burrows-Wheeler

Abstract

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.