algorithm Introduction à l'algorithme de Knuth-Morris-Pratt (KMP)


Exemple

Supposons que nous ayons un texte et un motif . Nous devons déterminer si le modèle existe ou non dans le texte. Par exemple:

+-------+---+---+---+---+---+---+---+---+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+-------+---+---+---+---+---+---+---+---+
|  Text | a | b | c | b | c | g | l | x |
+-------+---+---+---+---+---+---+---+---+

+---------+---+---+---+---+
| Index   | 0 | 1 | 2 | 3 |
+---------+---+---+---+---+
| Pattern | b | c | g | l |
+---------+---+---+---+---+

Ce modèle existe dans le texte . Donc, notre recherche de sous-chaîne doit retourner 3 , l’index de la position à partir de laquelle ce modèle commence. Alors, comment fonctionne notre procédure de recherche de sous-chaîne par force brute?

Ce que nous faisons habituellement est: nous partons du 0ème index du texte et du 0ème index de notre * pattern et nous comparons Text [0] avec Pattern [0] . Comme ils ne correspondent pas, nous allons au prochain index de notre texte et nous comparons Text [1] avec Pattern [0] . Comme il s'agit d'une correspondance, nous incrémentons également l'index de notre modèle et l'index du texte . Nous comparons Text [2] avec Pattern [1] . Ils sont aussi un match. En suivant la même procédure que précédemment, nous comparons maintenant Text [3] avec Pattern [2] . Comme ils ne correspondent pas, nous partons de la position suivante où nous avons commencé à trouver le match. C'est l'index 2 du texte . Nous comparons Text [2] avec Pattern [0] . Ils ne correspondent pas. Puis en incrémentant l’index du Text , on compare Text [3] avec Pattern [0] . Ils correspondent. De nouveau Text [4] et Pattern [1] correspondent, Text [5] et Pattern [2] correspondent et Text [6] et Pattern [3] correspondent. Comme nous avons atteint la fin de notre modèle , nous retournons maintenant l’index à partir duquel notre correspondance a commencé, à savoir 3 . Si notre modèle était: bcgll , cela signifie que si le modèle n'existait pas dans notre texte , notre recherche devrait renvoyer une exception ou -1 ou toute autre valeur prédéfinie. Nous pouvons clairement voir que, dans le pire des cas, cet algorithme prendrait O(mn) temps où m est la longueur du texte et n la longueur du motif . Comment pouvons-nous réduire cette complexité temporelle? C'est là que l'algorithme de recherche de sous-chaîne KMP entre en jeu.

L' algorithme de recherche de chaînes Knuth-Morris-Pratt ou l' algorithme KMP recherche les occurrences d'un "motif" dans un "texte" principal en utilisant l'observation selon laquelle, en cas d'incompatibilité, le mot lui-même contient suffisamment d'informations pour déterminer où , contournant ainsi le réexamen des caractères précédemment appariés. L'algorithme a été conçu en 1970 par Donuld Knuth et Vaughan Pratt et indépendamment par James H. Morris . Le trio l'a publié conjointement en 1977.

Étendons notre exemple Text and Pattern pour une meilleure compréhension:

+-------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| Index |0 |1 |2 |3 |4 |5 |6 |7 |8 |9 |10|11|12|13|14|15|16|17|18|19|20|21|22|
+-------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|  Text |a |b |c |x |a |b |c |d |a |b |x |a |b |c |d |a |b |c |d |a |b |c |y |
+-------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

+---------+---+---+---+---+---+---+---+---+
|  Index  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---------+---+---+---+---+---+---+---+---+
| Pattern | a | b | c | d | a | b | c | y |
+---------+---+---+---+---+---+---+---+---+

Au début, nos correspondances textuelles et graphiques jusqu’à l’index 2 . Le texte [3] et le motif [3] ne correspondent pas. Notre objectif est donc de ne pas revenir en arrière dans ce texte , c’est-à-dire qu’en cas de non-concordance, nous ne voulons pas que notre correspondance reprenne à partir de la position avec laquelle nous avons commencé à correspondre. Pour y parvenir, nous chercherons un suffixe dans notre Pattern juste avant que notre discordance ne se produise (sous-chaîne abc ), qui est également un préfixe de la sous-chaîne de notre Pattern . Pour notre exemple, puisque tous les caractères sont uniques, il n'y a pas de suffixe, c'est le préfixe de notre sous-chaîne correspondante. Donc, cela signifie que notre prochaine comparaison commencera à partir de l’index 0 . Attends un peu, tu comprendras pourquoi nous avons fait ça. Ensuite, nous comparons Text [3] avec Pattern [0] et cela ne correspond pas. Après cela, pour Text from index 4 to index 9 et pour Pattern de l'index 0 à l'index 5 , nous trouvons une correspondance. Nous trouvons un décalage dans Text [10] et Pattern [6] . Nous prenons donc la sous-chaîne de Pattern juste avant le point où la discordance se produit (sous-chaîne abcdabc ), nous vérifions un suffixe, qui est aussi un préfixe de cette sous-chaîne. Nous pouvons voir ici que ab est à la fois le suffixe et le préfixe de cette sous-chaîne. Ce que cela signifie, puisque nous avons comparé jusqu'à Text [10] , les caractères juste avant la disparité sont ab . On peut en déduire que puisque ab est aussi un préfixe de la sous-chaîne que nous avons prise, il n'est pas nécessaire de vérifier à nouveau ab et le prochain contrôle peut commencer par Text [10] et Pattern [2] . Nous n'avons pas eu à revenir sur l'ensemble du texte , nous pouvons commencer directement à partir de l'endroit où notre inadéquation s'est produite. Maintenant, nous vérifions Text [10] et Pattern [2] , car il ne correspond pas, et la sous-chaîne avant mismatch ( abc ) ne contient pas de suffixe qui est aussi un préfixe, nous vérifions Text [10] et Pattern [0] , ils ne correspondent pas. Après cela pour le texte de l'index 11 à l'index 17 et pour le motif de l'index 0 à l'index 6 . Nous trouvons une disparité dans Text [18] et Pattern [7] . Donc, encore une fois, nous vérifions la sous-chaîne avant la non-concordance (sous-chaîne abcdabc ) et trouvons que abc est à la fois le suffixe et le préfixe. Donc, puisque nous avons fait correspondre jusqu'à Pattern [7] , abc doit être avant Text [18] . Cela signifie que nous n'avons pas besoin de comparer jusqu'à ce que Text [17] et notre comparaison commence par Text [18] et Pattern [3] . Nous allons donc trouver une correspondance et nous retournerons 15 qui est notre index de départ du match. Voici comment notre recherche de sous-chaînes KMP fonctionne en utilisant les informations de suffixe et de préfixe.

Maintenant, comment pouvons-nous calculer efficacement si le suffixe est le même que le préfixe et à quel moment démarrer le contrôle s’il ya une incohérence de caractère entre le texte et le motif . Regardons un exemple:

+---------+---+---+---+---+---+---+---+---+
|  Index  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---------+---+---+---+---+---+---+---+---+
| Pattern | a | b | c | d | a | b | c | a |
+---------+---+---+---+---+---+---+---+---+

Nous allons générer un tableau contenant les informations requises. Appelons le tableau S. La taille du tableau sera la même que la longueur du motif. Puisque la première lettre du Pattern ne peut être le suffixe d'aucun préfixe, nous allons mettre S [0] = 0 . Nous prenons d'abord i = 1 et j = 0 . A chaque étape, nous comparons le motif [i] et le motif [j] et incrémentons i . S'il y a une correspondance, on met S [i] = j + 1 et l'incrément j , s'il y a une discordance, on vérifie la position précédente de j (si disponible) et on met j = S [j-1] (si j n'est pas égal à 0 ), nous continuons à le faire jusqu'à ce que S [j] ne corresponde pas à S [i] ou que j ne devienne pas 0 . Pour le dernier, nous mettons S [i] = 0 . Pour notre exemple:

            j   i
+---------+---+---+---+---+---+---+---+---+
|  Index  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---------+---+---+---+---+---+---+---+---+
| Pattern | a | b | c | d | a | b | c | a |
+---------+---+---+---+---+---+---+---+---+

Pattern [j] et Pattern [i] ne correspondent pas, donc nous incrémentons i et comme j vaut 0 , nous ne vérifions pas la valeur précédente et mettons Pattern [i] = 0 . Si nous continuons à incrémenter i , pour i = 4 , nous obtiendrons une correspondance, nous avons donc mis S [i] = S [4] = j + 1 = 0 + 1 = 1 et incrémenté j et i . Notre tableau ressemblera à:

                j               i
+---------+---+---+---+---+---+---+---+---+
|  Index  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---------+---+---+---+---+---+---+---+---+
| Pattern | a | b | c | d | a | b | c | a |
+---------+---+---+---+---+---+---+---+---+
|    S    | 0 | 0 | 0 | 0 | 1 |   |   |   |
+---------+---+---+---+---+---+---+---+---+

Comme Pattern [1] et Pattern [5] correspondent, nous mettons S [i] = S [5] = j + 1 = 1 + 1 = 2 . Si nous continuons, nous trouverons une incompatibilité pour j = 3 et i = 7 . Puisque j n'est pas égal à 0 , on met j = S [j-1] . Et nous comparerons les caractères à i et j sont identiques ou non, puisqu'ils sont identiques, nous allons mettre S [i] = j + 1. Notre tableau terminé ressemblera à:

+---------+---+---+---+---+---+---+---+---+
|    S    | 0 | 0 | 0 | 0 | 1 | 2 | 3 | 1 |
+---------+---+---+---+---+---+---+---+---+

Ceci est notre tableau requis. Ici, une valeur non nulle de S [i] signifie qu'il y a un suffixe de longueur S [i] identique au préfixe dans cette sous-chaîne (sous-chaîne de 0 à i ) et la comparaison suivante commencera à partir de S [i] + 1 position du Motif Notre algorithme pour générer le tableau ressemblerait à ceci:

Procedure GenerateSuffixArray(Pattern):
i := 1
j := 0
n := Pattern.length
while i is less than n
    if Pattern[i] is equal to Pattern[j]
        S[i] := j + 1
        j := j + 1
        i := i + 1
    else
        if j is not equal to 0
            j := S[j-1]
        else
            S[i] := 0
            i := i + 1
        end if
    end if
end while

La complexité temporelle pour construire ce tableau est O(n) et la complexité de l'espace est également O(n) . Pour vous assurer que vous avez bien compris l’algorithme, essayez de générer un tableau pour le motif aabaabaa et vérifiez si le résultat correspond à celui- ci.

Faisons maintenant une recherche de sous-chaîne à l'aide de l'exemple suivant:

+---------+---+---+---+---+---+---+---+---+---+---+---+---+
|  Index  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |10 |11 |
+---------+---+---+---+---+---+---+---+---+---+---+---+---+
|   Text  | a | b | x | a | b | c | a | b | c | a | b | y |
+---------+---+---+---+---+---+---+---+---+---+---+---+---+

+---------+---+---+---+---+---+---+
|  Index  | 0 | 1 | 2 | 3 | 4 | 5 |
+---------+---+---+---+---+---+---+
| Pattern | a | b | c | a | b | y |
+---------+---+---+---+---+---+---+
|    S    | 0 | 0 | 0 | 1 | 2 | 0 |
+---------+---+---+---+---+---+---+

Nous avons un texte , un motif et un tableau pré-calculé S en utilisant notre logique définie précédemment. Nous comparons Text [0] et Pattern [0] et ils sont identiques. Le texte [1] et le motif [1] sont identiques. Le texte [2] et le motif [2] ne sont pas identiques. Nous vérifions la valeur à la position juste avant la disparité. Puisque S [1] vaut 0 , il n'y a pas de suffixe identique au préfixe de notre sous-chaîne et notre comparaison commence à la position S [1] , qui est 0 . Donc, le Pattern [0] n'est pas le même que Text [2] , donc nous continuons. Le texte [3] est identique au motif [0] et il y a une correspondance jusqu'à Texte [8] et Motif [5] . Nous revenons en arrière dans le tableau S et trouvons 2 . Cela signifie donc qu'il y a un préfixe de longueur 2 qui est aussi le suffixe de cette sous-chaîne ( abcab) qui est ab . Cela signifie également qu'il y a un ab avant Text [8] . Nous pouvons donc ignorer en toute sécurité Pattern [0] et Pattern [1] et commencer notre prochaine comparaison avec Pattern [2] et Text [8] . Si nous continuons, nous trouverons le motif dans le texte . Notre procédure ressemblera à:

Procedure KMP(Text, Pattern)
GenerateSuffixArray(Pattern)
m := Text.Length
n := Pattern.Length
i := 0
j := 0
while i is less than m
    if Pattern[j] is equal to Text[i]
        j := j + 1
        i := i + 1
    if j is equal to n
        Return (j-i)
    else if i < m and Pattern[j] is not equal t Text[i]
        if j is not equal to 0
            j = S[j-1]
        else
            i := i + 1
        end if
    end if
end while
Return -1

La complexité temporelle de cet algorithme en dehors du calcul du tableau de suffixes est O(m) . Puisque GenerateSuffixArray prend O(n) , la complexité temporelle totale de l’algorithme KMP est: O(m+n) .

PS: Si vous voulez trouver plusieurs occurrences de Pattern dans le texte , au lieu de retourner la valeur, imprimez-la / stockez-la et définissez j := S[j-1] . Conservez également un flag pour savoir si vous avez trouvé une occurrence ou non et gérez-la en conséquence.