Top Qs
Chronologie
Chat
Contexte
Algorithme de Knuth-Morris-Pratt
De Wikipédia, l'encyclopédie libre
Remove ads
En informatique, l'algorithme de Knuth-Morris-Pratt (ou d'une manière plus courte l'algorithme KMP) est un algorithme de recherche de sous-chaîne de caractères. Il permet de trouver les occurrences d'une chaîne (ou aussi appelé motif) dans un texte avec une complexité linéaire dans le pire cas, où et sont respectivement les longueurs (nombres de caractères) de la chaîne et du texte et est une notation asymptotique de Landau. De plus la constante dans le ne dépend pas de la taille de l'alphabet[1].

Sa particularité réside en un prétraitement de la chaîne, qui fournit une information suffisante pour déterminer où continuer la recherche en cas de non-correspondance. Ainsi l'algorithme ne ré-examine pas les caractères qui ont été vus précédemment, et donc limite le nombre de comparaisons nécessaires. Plus précisément, la complexité du prétraitement est en , et la recherche proprement dite est en .
L'algorithme a été conçu en 1970[2] par Knuth et Pratt, et dans un autre contexte, par Morris, et publié conjointement en 1977[3]. Indépendamment Matiyasevich[4],[5] avait déjà obtenu dès 1969 un algorithme similaire, codé par une machine de Turing à deux dimensions[pas clair], en étudiant un problème de reconnaissance d'occurrence de chaîne.
Remove ads
Contexte
L'approche naïve de recherche d'une chaîne consiste à décaler la chaîne le long du texte , de gauche à droite d'une lettre à chaque étape. A chaque fois, on compare la chaîne et la portion du texte . Voici le pseudo-code de l'algorithme naïf (cf. Section 32.1 p. 908 dans [6]) :
fonction rechercheNaïve(T, P) pour s = 0 à |T| - |P| si P = T[s+1..s+|P|] afficher "la chaîne P apparaît avec le décalage" s
Dans le pire cas, l'approche naïve a un coût qui est , où est la longueur du motif et la longueur du texte [7]. En effet, la comparaison est en , qui dans un corps de boucle qui s'exécute fois.
Remove ads
Principe
Résumé
Contexte
L'algorithme de Knuth-Morris-Pratt améliore l'approche naïve en utilisant l'information acquise lors des comparaisons lettre à lettre réalisées dans les comparaisons . Ainsi, on peut décaler le motif de plus d'une lettre à chaque étape.
Exemple
Supposons que la chaîne est ABABACA
et que le texte est ABABAABCBAB
(cf. p. 923 dans [6]). Au début on compare le motif avec le début ABABAAB
. Les cinq premières lettres ABABA
coïncident mais à la 6e position, les caractères différent :
T : ABABAABCBAB P : ABABACA ^
Sachant que le début ABABA
du motif correspond, la question est : quel est le plus petit décalage qui fait coïncider les caractères avant le curseur ^ ? On sait que décaler de 1 lettre n'aboutira pas, cela reviendrait à aligner le début ABAB
avec BABA
qui sont différents. Par contre, décaler de 2 lettres est prometteur car on retrouve le début ABA
(que l'on appelle préfixe) du motif à la fin (suffixe) du texte déjà lu :
T : ABABAABCBAB P : ABABACA
Fonction préfixe
La fin du texte déjà lu correspond à la fin de la portion du motif qui coïncide. On se ramène donc à l'étude du motif. En particulier, pour tout préfixe du motif , on cherche la longueur du plus long préfixe de qui est aussi suffixe de . Plus ce plus long préfixe/suffixe est court, plus on décale. Dans l'exemple ci-dessus, vaut 3 car le mot ABA est le plus long qui est préfixe propre et suffixe propre de . La fonction s'appelle fonction préfixe (cf. p. 922 dans [6]). Voici la table qui donne les valeurs de pour le motif ABABACA
:
Structure de l'algorithme
L'algorithme de Knuth-Morris-Pratt est composée de deux phases.
- Calcul de la fonction préfixe. L'algorithme construit la fonction préfixe ;
- Phase de recherche. A l'instar de l'algorithme naïf, on recherche le motif dans le texte mais en utilisant la fonction préfixe pour connaître le décalage.
Remove ads
Phase de recherche
Résumé
Contexte

Pseudo-code
Voici un pseudo-code de la phase de recherche (cf. p. 924 dans [6]), où l'on suppose que les indices des chaînes de caractères (autant le motif que le texte ) commencent à 1 :
entrée : π fonction préfixe correspondante à P P chaîne à chercher (motif, ou aiguille) T texte sortie : toutes les positions où on trouve P dans T fonction phaseRecherche(π, P, T) q := 0 pour i = 1 à |T| tant que q > 0 et P[q+1] ≠ T[i] q = π[q] si P[q+1] = T[i] q = q + 1 si q = |P| afficher "le motif apparaît en position" i - |P| q = π[q]
On suppose que la fonction préfixe π est déjà calculée. Dans l'algorithme ci-dessus, i désigne la position courante dans le texte T. La variable q, elle, désigne le nombre de caractères qui coïncident. La notation q est la même que pour désigner un état d'un automate fini, puisque l'algorithme de Knuth-Morris-Pratt s'introduit parfois avec l'exécution d'un automate fini[6]. La différence i - q représente la position dans T du début du motif P glissant sur T.
Explication
Avec la boucle pour i = 1 à |T|, on parcourt toutes les lettres de T. Avec la boucle tant que q > 0 et P[q+1] ≠ T[i], on glisse le motif vers la droite jusqu'à avoir atteint la position i (q = 0) ou jusqu'à avoir un égalité des lettres courantes dans le motif et texte (P[q+1] = T[i]). En cas d'égalité, on augmente la partie qui coïncide (en vert dans l'image) en incrémentant q. Si q = |P|, cela signifie que tout le motif coïncide. L'affectation q = π[q] dans ce cas est présente pour glisser le motif afin de poursuivre la recherche.
Complexité temporelle
Dans la boucle tant que, i - q augmente strictement. A chaque tour de la boucle pour, i augmente strictement alors que i - q augmente ou stagne. Donc 2i - q augmente strictement à chaque tour de boucle (pour ou tant que). Donc l'algorithme est en .
Remove ads
Calcul de la fonction préfixe
Résumé
Contexte
Décrivons maintenant comment calculer la fonction préfixe π.
Pseudo-code
On a . Pour , le calcul de s'obtient grâce aux valeurs de avec grâce à la relation de récurrence suivante (cf. corollaire 32.7, p. 926 dans [6]) :
- si
- si
où .
Cette relation permet d'obtenir un algorithme de programmation dynamique[8] pour calculer la fonction préfixe comme le montre le pseudo-code suivant (adapté de celui de Cormen et al., p. 924 dans [6]) :
entrée : P chaîne à chercher (motif, ou aiguille) sortie : la fonction de préfixe π associée à P fonction calculFonctionPrefixe(P) soit π[1..|P|] un tableau π[1] := 0 pour q = 2 à |P| k := π[q-1] tant que k > 0 et P[k+1] ≠ P[q] k := π[k] si P[k+1] = P[q] π[q] := k + 1 sinon π[q] := 0 renvoyer π
Cormen et al. (p. 924 dans [6]) présente l'algorithme suivant, qui est équivalent au pseudo-code précédent, mais qui montre que le calcul de la fonction préfixe est similaire à une "phase de recherche" du motif P sur lui-même, en utilisant les valeurs de π[k] déjà calculées :
entrée : P chaîne à chercher (motif, ou aiguille) sortie : la fonction de préfixe π associée à P fonction calculFonctionPrefixe(P) soit π[1..|P|] un tableau π[1] := 0 k := 0 pour q = 2 à |P| // ici k = π[q-1] tant que k > 0 et P[k+1] ≠ P[q] k := π[k] si P[k+1] = P[q] k := k + 1 π[q] := k renvoyer π
Complexité temporelle
Comme l'algorithme de calcul de la fonction préfixe est similaire à une phase de recherche du motif dans lui-même. De ce fait, l'analyse de complexité est similaire et sa complexité temporelle est en O(|P|).
Remove ads
Généralisation à plusieurs motifs
L'algorithme d'Aho-Corasick généralise l'algorithme de Knuth-Morris-Pratt à la recherche simultanée de plusieurs motifs (voir p. 367, Section 10.3 dans [9]). Pour l'algorithme d'Aho-Corasick la fonction préfixe devient arborescente et est défini sur un trie.
Notes et références
Voir aussi
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads