Algorithme de Raita - Wikiwand
For faster navigation, this Iframe is preloading the Wikiwand page for Algorithme de Raita.

Algorithme de Raita

Un article de Wikipédia, l'encyclopédie libre.

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

{{bottomLinkPreText}} {{bottomLinkText}}
Algorithme de Raita
Listen to this article