Algorithme de Raita

L'algorithme de Raita est un algorithme de recherche de sous-chaîne publié par Tim Raita en 1992. 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.

Description

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^,

Complexité

La complexité en espace de l'algorithme est ${\displaystyle O(|\Sigma |)}$, le pré-traitement a une complexité en temps en ${\displaystyle O(P+|\Sigma |)}$ et la recherche a une complexité en temps en ${\displaystyle O(|T|\times |\Sigma |)}$.

Animation

• Applet animation and Description for Raita Algorithm

Notes et références

Liens externes

• Portail de l'informatique théorique