Algorithme de Raita
From Wikipedia, the free encyclopedia
L'algorithme de Raita est un algorithme de recherche de sous-chaîne publié par Tim Raita en 1992[1]. Il est une variation de l'algorithme de Boyer-Moore-Horspool pour en améliorer la performance. En pratique, Raita est plus rapide que Boyer-Moore-Horspool sur de très grands textes, ou sur des alphabets réduits tel l'ADN.
Dans la suite, on notera T le texte de recherche, P la sous-chaîne recherchée et ∑ l'alphabet.
Le pré-traitement de la sous-chaîne P est identique à Boyer-Moore. Comme Boyer-Moore-Horspool la comparaison commence au dernier caractère, mais deux autres comparaisons sont ensuite effectuées, au premier caractère puis au caractère milieu, avant de comparer le reste des caractères[2],[3]
Complexité
La complexité en espace de l'algorithme est , le pré-traitement a une complexité en temps en et la recherche a une complexité en temps en .
