ALGORITHMES PARALLÉLES POUR LA RECHERCHE PAR DICTIONNAIRE

Abstract

Dans ce travail, nous nous sommes intéressés au problème de la recherche par dictionnaire, en particulier aux algorithmes multi-motifs d’Aho-Corasick et de Rabin Karp. En raison de la croissance des données textuelle et de la quantité d’information à traiter, alors il existe un fort besoin d’algorithme efficace en termes d’espace aussi bien que de temps pour un traitement rapide et non couteux de ces données. C’est la raison pour laquelle l’implémentation des deux algorithmes doit répondre à ces deux critères :  Pour l’algorithme d’Aho-Corasick, nous effectuons une implémentation succincte que nous parallélisons afin d’optimiser le coût mémoire et d’accélérer les calculs.  Pour l’algorithme de Rabin-Karp, nous effectuons une implémentation d’une table de hachage par la méthode de linear probing (essai linéaire) en appliquant le parallélisme pour améliorer le calcul de la fonction de hachage. Nous avons effectué des tests sur ces algorithmes pour étudier l’efficacité de ces implémentations. Ces tests ont montré que nos algorithmes sont efficaces en pratique en termes de temps de calcul et d’espace. Mots-clés : la recherche par dictionnaire, multi-motifs, succincte, parallélisme, table de hachage, linear probing, fonction de hachage.

In this work, we are interested in dictionary matching problem, in particular, in the multi pattern algorithms Aho-Corasick and Rabin Karp. Due to the growth of textual data and of the amount of information to be handled, there is a strong need for an efficient algorithm in terms of space as well as time for a fast and optimal data processing. This is why the implementation of both algorithms must meet these criteria:  For Aho-Corasick algorithm, we implement a succinct version that will be parallelize in order to optimize memory cost and speedup the process.  For Rabin Karp algorithm, we use linear probing method to implement the hash table that will be parallelize to improve the calculation time of the hash function. We perform a set of tests on this algorithms to study the efficiency of this implementation. The results show that the algorithms are efficient in practice in terms of computing time and memory space. Keywords: dictionary matching, multi pattern, succinct, parallelize, linear probing, hash table, hash function.