Algorithme de Raita
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.
Description
[modifier | modifier le code]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é
[modifier | modifier le code]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 .
Animation
[modifier | modifier le code]Notes et références
[modifier | modifier le code]- ↑ Timo Raita, « Tuning the boyer‐moore‐horspool string searching algorithm », Software: Practice and Experience, vol. 22, no 10, , p. 879–884 (DOI 10.1002/spe.4380221006, lire en ligne, consulté le ).
- ↑ Christian Charras, Thierry Lecroq, « Algorithme de Raita », Exact string matching algorithms, Laboratoire d'Informatique de Rouen (consulté le ).
- ↑ P. D. Smith, « On tuning the boyer-moore-horspool string searching algorithm », Software: Practice and Experience, vol. 24, no 4, , p. 435–436 (DOI 10.1002/spe.4380240408, lire en ligne, consulté le )
Liens externes
[modifier | modifier le code]
