Recherche pratique d’un mot dans un texte

Nous présentons de nouveaux algorithmes de recherche d’un mot dans un texte, efficaces en pratique, obtenus par deux approches différentes.

• La première approche consiste à introduire du parallèlisme de registre, c’est-à-dire à utiliser le parallélisme intrinsèque des mots machine des ordinateurs, dans des algorithmes optimaux mais thèoriques. On obtient alors des algorithmes simples, facile à implémenter et très rapides en pratique. De plus, ces algorithmes permettent des extensions que les algorithmes originaux ne permettent pas.
• La deuxième approche, plus thèorique, est basée sur une nouvelle structure de données, l’oracle des facteurs, que nous présentons en détails. Cette nouvelle structure permet d’\obtenir des algorithmes haut-niveau (c’est-à-dire ne dépendant pas de la taille des mots machines du microprocesseur), rapides, simples à implémenter et peu gourmands en place mémoire.