O algoritmo Knuth-Morris-Pratt (ou de forma abreviada o algoritmo KMP ) é um algoritmo de busca de substring (caractere), permitindo encontrar ocorrências de uma string em um texto com complexidade linear no pior caso. Sua particularidade está no pré-processamento da string, que fornece informações suficientes para determinar onde continuar a busca em caso de incompatibilidade. Assim, o algoritmo não reexamina os caracteres que foram vistos anteriormente e, portanto, limita o número de comparações necessárias.
O algoritmo foi projetado em 1970 por Knuth e Pratt (in) e, em outro contexto, por Morris (in) , e publicado em conjunto em 1977 . Independentemente, Matiyasevich já havia obtido em 1969 um algoritmo semelhante, codificado por uma máquina de Turing bidimensional, estudando um problema de reconhecimento de ocorrência de cordas.
Para entender a lógica do algoritmo Knuth-Morris-Pratt, faz sentido examinar a abordagem ingênua para encontrar cordas.
A string P pode ser encontrada no texto S usando o seguinte algoritmo:
Este procedimento pode ser melhorado interrompendo a comparação da segunda etapa assim que um caractere diferente for detectado.
Essa abordagem tem uma desvantagem: após uma comparação malsucedida, a próxima comparação começará na posição , desconsiderando aquelas que já ocorreram na iteração anterior, na posição . O algoritmo Knuth-Morris-Pratt primeiro examina a string P e deriva informações dela para que cada caractere não seja comparado mais de uma vez.
Para apresentar o princípio de operação do algoritmo, um exemplo particular é considerado: a string é ABCDABD e o texto é ABC ABCDAB ABCDABCDABDE .
Notações : para representar strings, este artigo usa matrizes cujos índices começam em zero. Assim, a letra C da string será anotada .
designa a posição no texto em que a string está sendo verificada e a posição do caractere atualmente verificado
O algoritmo começa testando a correspondência de caracteres um após o outro. Assim, na quarta etapa, e . é um espaço e , a correspondência não é possível.
1 2 01234567890123456789012 m : v S : ABC ABCDAB ABCDABCDABDE P : ABCDABD i : ^ 0123456Em vez de começar de novo , o algoritmo percebe que nenhum A está presente entre as posições 0 e 3, exceto para a posição 0. Consequentemente, por ter testado todos os caracteres anteriores, o algoritmo sabe que não tem chance de encontrar o início de um coincidir se ele verificar novamente. Portanto, o algoritmo avança para o próximo caractere, definindo e .
1 2 01234567890123456789012 m : v S : ABC ABCDAB ABCDABCDABDE P : ABCDABD i : ^ 0123456Uma correspondência quase completa é obtida rapidamente quando, com , a verificação falha.
1 2 01234567890123456789012 m : v S : ABC ABCDAB ABCDABCDABDE P : ABCDABD i : ^ 0123456No entanto, pouco antes do final dessa correspondência parcial, o algoritmo passou pelo padrão AB , que poderia corresponder ao início de outra correspondência. Portanto, essas informações devem ser levadas em consideração. Como o algoritmo já sabe que esses dois primeiros caracteres correspondem aos dois caracteres anteriores à posição atual, não é necessário verificá-los novamente. Assim, o algoritmo retoma seu processamento no caractere atual, com e .
1 2 01234567890123456789012 m : v S : ABC ABCDAB ABCDABCDABDE P : ABCDABD i : ^ 0123456Esta verificação falha imediatamente ( C não corresponde ao espaço em ). Como a string não contém espaços (como na primeira etapa), o algoritmo continua a busca e reinicialização .
1 2 01234567890123456789012 m : v S : ABC ABCDAB ABCDABCDABDE P : ABCDABD i : ^ 0123456Novamente, o algoritmo encontra uma correspondência parcial ABCDAB , mas o caractere após C não corresponde ao caractere final D da string.
1 2 01234567890123456789012 m : v S : ABC ABCDAB ABCDABCDABDE P : ABCDABD i : ^ 0123456Com o mesmo raciocínio de antes, o algoritmo começa novamente com , para começar na sequência de dois caracteres AB que leva à posição atual, fixando , a nova posição atual.
1 2 01234567890123456789012 m : v S : ABC ABCDAB ABCDABCDABDE P : ABCDABD i : ^ 0123456Desta vez, a correspondência é concluída, o algoritmo retorna a posição 15 (ou seja ) como a origem.
1 2 01234567890123456789012 m : v S : ABC ABCDAB ABCDABCDABDE P : ABCDABD i : ^ 0123456O exemplo anterior ilustra de forma instrutiva o princípio do algoritmo. Assume a existência de uma tabela de “correspondências parciais” (descritas a seguir), indicando onde procurar o potencial início da próxima ocorrência, caso falhe a verificação da potencial ocorrência atual. Por enquanto, este array, denotado por , pode ser pensado como uma caixa preta com a seguinte propriedade: se tivermos uma correspondência parcial de a , mas falharmos ao comparar e , a próxima ocorrência potencial começará na posição . Em particular, existe e é definido em . Dada esta tabela, o algoritmo é relativamente simples:
Esta descrição implementa o algoritmo aplicado no exemplo anterior. Cada vez que a verificação falha, a tabela é consultada para encontrar o início da próxima ocorrência potencial e os contadores são atualizados de acordo. Portanto, a verificação de caracteres nunca é executada ao contrário. Em particular, cada caractere é verificado apenas uma vez (embora possa ser descartado várias vezes como resultado das correspondências com falha. Veja abaixo a análise da eficiência do algoritmo).
O seguinte trecho de código C é uma implementação desse algoritmo para cadeias de caracteres de 8 bits. Para superar as limitações intrínsecas das tabelas em C, os índices são deslocados em uma unidade, ou seja, no código é equivalente ao da descrição acima.
código de algoritmo de busca int kmp_recherche(char *P, char *S) { extern int T[]; int m = 0; int i = 0; // Tant que l'on n'a pas atteint la fin de la chaîne S ou de la chaîne P. while (S[m + i] != '\0' && P[i] != '\0') { if (S[m + i] == P[i]) { // Si on a encore une correspondance ++i; // alors on regarde la lettre suivante } else { // sinon m += i - T[i]; /* la prochaine correspondance partielle possible est à T[i] lettre avant celle qu'on vient de regarder. */ if (i > 0) i = T[i]; /* Puisque l'on sait que les T[i]-1 premières lettres à partir de m sont bonnes, il suffit de regarder P à partir de la T[i]ème position. Pour S on peut remarquer que on m+i est maintenant égale à (m+i-T[i])+(T[i]) avec les anciennes valeurs. Ce qui montre qu'on ne retourne pas en arrière. */ } } //Quand on a fini de parcourir une des deux chaines if (P[i] == '\0') { //si la chaine P est finie alors on a trouvé une correspondance à la place m return m; } else { /* Sinon c'est qu'il n'existe pas de correspondance de P dans S donc on renvoie un nombre impossible */ return m + i; /* m est forcément le nombre de caractères de S, donc m+1 est impossible. On pourrait aussi renvoyer -1 */ } }Assumindo a existência anterior do array , a fase de “busca” do algoritmo Knuth-Morris-Pratt é de complexidade O , onde denota o comprimento de . Se excluirmos o processamento fixo adicional induzido pela entrada e saída da função, todo o processamento é executado no loop principal. Para calcular um limite no número de iterações, uma primeira observação sobre a natureza de é necessária. Por definição, é construído de forma que, se uma correspondência parcial começar a falhar ao comparar e , a próxima correspondência potencial não será iniciada antes . Em particular, a próxima correspondência potencial deve estar em uma posição maior que , para que .
Com base nesse fato, mostramos que o loop é executado na maioria das vezes. Em cada iteração, ele executa uma das duas ramificações da instrução if .
O loop termina se , o que significa, levando em consideração a convenção C que especifica que um caractere NUL designa o fim de uma string, isso . Consequentemente, cada ramificação da instrução if pode ser percorrida na maioria das vezes, visto que aumentam respectivamente ou , e , portanto , se , então , e uma vez que o aumento em cada iteração é pelo menos uma unidade, necessariamente foi verificado no passado.
Assim, o loop é executado na maioria das vezes, estabelecendo uma complexidade algorítmica em .
O objetivo desta tabela é evitar que o algoritmo teste cada caractere do texto mais de uma vez. A principal observação sobre a natureza linear da busca que permite que este algoritmo funcione é que, comparando parte do texto com uma "primeira parte" da string, é possível determinar para quais posições podem começar as possíveis ocorrências que se seguem, e que continuam a corresponder à posição atual no texto. Em outras palavras, os padrões (as sub-partes da string) são “pré-pesquisados” na string, e uma lista é estabelecida, indicando todas as posições possíveis para as quais continuar a pular um máximo de caracteres desnecessários, sem no entanto sacrificar qualquer ocorrência potencial.
Para cada posição na cadeia, precisamos determinar o comprimento do padrão inicial mais longo, que termina na posição atual, mas não permite uma correspondência completa (e, portanto, muito provavelmente falhou). Portanto, denota exatamente o comprimento do padrão inicial mais longo terminando em . Por convenção, a string vazia tem comprimento zero. Como uma falha no início da cadeia é um caso especial (a possibilidade de retrocesso não existe), colocamos , como discutido anteriormente.
Ao reconsiderar o exemplo ABCDABD apresentado anteriormente, podemos estabelecer que ele funciona segundo esse princípio e que se beneficia da mesma eficiência por esse motivo. Nós consertamos .
-1 0 1 2 3 4 5 6 i : v P[i] : A B C D A B D T[i] : -1Como só aparece no final do padrão inicial completo, também corrigimos .
-1 0 1 2 3 4 5 6 i : v P[i] : A B C D A B D T[i] : -1 0Para determinar , o algoritmo deve encontrar um padrão terminal em AB que também é um padrão inicial na cadeia. Mas o único padrão terminal possível de AB é B , que não é um padrão inicial na cadeia. Assim ,.
-1 0 1 2 3 4 5 6 i : v P[i] : A B C D A B D T[i] : -1 0 0Continuando com C , notamos que há um atalho para verificar todos os padrões de terminal. Considere que o algoritmo encontrou um padrão terminal de dois caracteres, terminando em C ; então, o primeiro caractere desse padrão é um padrão inicial de um padrão inicial na string e, portanto, um padrão inicial em si. Além disso, termina no B , para o qual sabemos que não é possível combinar. Portanto, não há necessidade de se preocupar com os padrões de comprimento de dois caracteres e, como no caso anterior, o padrão de comprimento de unidade única não corresponde. Então .
Da mesma forma para D , obtém-se .
-1 0 1 2 3 4 5 6 i : v P[i] : A B C D A B D T[i] : -1 0 0 0 0Para o próximo A , o princípio anterior nos mostra que o padrão mais longo a ser considerado contém 1 caractere e, neste caso, A corresponde . Então .
-1 0 1 2 3 4 5 6 i : v P[i] : A B C D A B D T[i] : -1 0 0 0 0 1 P : A B C D A B D P : A B C D A B DA mesma lógica é aplicado a B . Se o algoritmo tivesse encontrado um padrão começando antes do A anterior, e continuando com o B atualmente considerado, então ele próprio teria um padrão inicial correto terminando em A, embora começando antes de A , o que contradiz o fato de que l O algoritmo já descobriu que A é a primeira ocorrência de um padrão que termina aí. Como resultado, não é necessário olhar antes de A para procurar um padrão para B ali . Na verdade, ao verificá-lo, o algoritmo descobre que ele continua com B e que B é a segunda letra do padrão do qual A é a primeira letra. Por causa disso, a entrada de B em é uma unidade maior que a de A , ou seja .
-1 0 1 2 3 4 5 6 i : v P[i] : A B C D A B D T[i] : -1 0 0 0 0 1 2 P : A B C D A B D P : A B C D A B DFinalmente, o padrão continua não a B a D . As mostras argumento anterior de que, se um padrão de um maior comprimento do que 1 foi encontrado em D , então ele deve conter um padrão que termina em B . Como o padrão atual não corresponde, ele deve ser mais curto. Mas o padrão atual é um padrão inicial da string terminando na segunda posição. Portanto, esse novo padrão potencial também deve terminar na segunda posição, e já vimos que não há nenhum. Como D não é em si um padrão .
-1 0 1 2 3 4 5 6 i : v P[i] : A B C D A B D T[i] : -1 0 0 0 0 1 2 0Daí a seguinte tabela:
-1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
NO | B | VS | D | NO | B | D | ||
-1 | 0 | 0 | 0 | 0 | 1 | 2 | 0 |
O exemplo anterior ilustra a técnica geral para produzir a mesa com o mínimo de confusão possível. O princípio é o mesmo que para a pesquisa geral: a maior parte do processamento já é feita ao entrar em uma nova posição, resta pouco processamento para passar para a próxima. A descrição do algoritmo segue. Para eliminar casos especiais, a seguinte convenção é aplicada: existe e seu valor é diferente de todos os caracteres possíveis de .
O seguinte trecho de código C é uma implementação desse algoritmo. Tal como acontece com o algoritmo de pesquisa, os índices de foram aumentados em 1 para tornar o código C mais natural. A variável adicional c permite simular a existência de . Presume-se que essa função, assim como a função de pesquisa, seja chamada em uma função de nível superior, que gerencia adequadamente a alocação de memória para o array .
void kmp_tableau(char *P) { extern int T[]; int i = 0; int j = -1; char c = '\0'; //Donc c=P[-1] T[0] = j; //c'est-à-dire -1 while (P[i] != '\0') { //Tant que l'on n'a pas atteint la fin de la chaine /* ATTENTION la condition suivante est fausse, contre exemple avec la chaine "ABABABAB", il faut plutot mettre if((P[i] == P[j]) && j < ((i+(i%2))/2)) */ if (P[i] == c) { /* Si P[i]==P[j] donc si le caractère qu'on regarde est le même que le caractère suivant la fin * du dernier motif initial trouvé */ T[i + 1] = j + 1; //alors le motif est continué, et on incrémente i et j. ++j; ++i; } else if (j > 0) { //Sinon si au caractère précédent il existe un motif j = T[j]; //on va regarder le motif initial précédent qui peut correspondre a la lettre où l'on était. } else { /* Sinon j=0 ou -1, i.e. si les lettres qui précèdent la ième suivie de la ième ne peuvent * correspondre a aucun marquage initiale */ T[i + 1] = 0; //alors on indique qu'il n'y a aucun motif initial pour cette lettre. ++i; j = 0; //Cette affectation ne sert en fait que lorsque j=-1. } c = P[j]; } }No entanto, substitua int j = -1; por int j = 0;, T [0] = j; por T [0] = -1; removeria a atribuição j = 0; sem alterar o resultado do algoritmo. Ganhamos um pouco de tempo de execução, mas perdemos consistência entre as variáveis.
A complexidade do algoritmo de construção da matriz é , onde denota o comprimento de . Excepto para as botas, todo o processamento é feito na etapa n o 3. Assim, é suficiente para mostrar que este passo é executado , o que é feito depois examinando simultaneamente as quantidades e .
Tipo , isso significa que a cada passo, qualquer um, um valor menor que aumenta. Portanto, como o algoritmo para quando para após no máximo iterações da etapa n o 3, para inícios . Assim, a complexidade deste algoritmo é .
Como as duas partes do algoritmo têm complexidades de e , respectivamente , a complexidade do algoritmo como um todo é .