Résumé:
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.
