Algorithme de Raita
L'algorithme de Raita est un algorithme de recherche de sous-chaîne publié par Tim Raita en 1992. Il consiste en 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 des alphabets réduits tel l'ADN.
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é
En espace, Raita a une complexité O(|∑|).
Le pré-traitement a une complexité en temps en O(|P|+|∑|).
La recherche a une complexité en temps en O(|T|*|P|).
Implémentation
Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?
v · m Algorithmique du texte | |
|---|---|
| Recherche de sous-chaîne |
|
| Alignement de chaînes |
|
| Mesure de similarité |
|
| Arbre des suffixes | |
| Comparaisons | |
Portail de l'informatique théorique
