Algoritmo KMP para busca de substring

Livro de Sedgewick e Wayne: parte da sec.5.3, p.758.  Website do livro: resumo sec.5.3, slides.  Código fonte, documentação, e dados de teste de todos os programas do livro: veja algs4.cs.​princeton.edu​/code/.

Esta página discute o algoritmo descoberto por Knuth, Morris e Pratt para o problema da busca de substring.  Esse algoritmo introduz o conceito de autômato de estados, que é fundamental em várias áreas da Computação.  A página termina com uma breve indicação de outros algoritmos para o problema.

Ideia básica do algoritmo

• Considere o texto  ABAAAABAAAAAAAAA  e o padrão  BAAAAAAAAA.  Depois de detectar um conflito na posição  i  do texo, é desnecessário retroceder i pois isso não produziria casamento algum:

  

• Ideia geral:  Quando encontramos um conflito entre txt[i] e pat[j], não é necessário retroceder i e passar a comparar txt[i-j+1..] com pat[0..].  Basta
  • encontrar o comprimento do maior prefixo de pat[0..] que é sufixo de txt[..i],
  • ou seja, encontrar o maior k tal que pat[0..k-1] é igual a txt[i-k+1..i],
  • e passar a comparar txt[i+1..] com pat[k..].
• Exemplo com texto  CAABAABAAAA  e padrão  AABAAA:  depois do conflito entre txt[6] e pat[5], não precisamos retroceder no texto:  podemos continuar e comparar txt[7..] com pat[3..]:

                        C A A B A A B A A A A
     uma tentativa:       A A B A A A
  não precisa tentar:       A A B A A A
    não precisa tentar:       A A B A A A
       próxima tentativa:       A A B A A A
  

• O algoritmo KMP examina os caracteres de txt um a um, da esquerda para a direita, sem nunca retroceder. Em cada iteração, o algoritmo sabe qual posição  k  de pat deve ser emparelhada com a próxima posição i+1 de txt.  Em outras palavras, no fim de cada iteração, o algoritmo sabe qual índice  k  deve fazer o papel de j na próxima iteração.
• Para fazer isso, o algoritmo KMP usa uma tabela dfa[][] que armazena os índices mágicos k.  (O nome da tabela deriva da expressão deterministic finite-state automaton.)  As colunas da tabela são indexadas pelos índices 0..M-1 do padrão e as linhas são indexadas pelo alfabeto, que é o conjunto de todos os caracteres do texto e do padrão.
• O código da busca KMP é formalmente semelhante ao da segunda versão do algoritmo de força bruta:

  public int search(String txt) {
     int j, M = pat.length();
     int i, N = txt.length();
  
     for (i = 0, j = 0; i < N && j < M; i++)
        j = dfa[txt.charAt(i)][j];
  
     if (j == M) return i - M;
     else return N;
  }
  

• O programa Java algs4.cs.princeton.edu/lectures/search.jar no website do livro ilustra o funcionamento do KMP.
• Exemplo de tabela  dfa[][]  para o alfabeto   A B C   e o padrão  ABABAC.   O valor 4 de dfa[B][5], por exemplo, diz  depois de comparar pat[5] com um caractere B no texto, você deve comparar pat[4] com o próximo caractere do texto.

                       0 1 2 3 4 5
  
                  A    1 1 3 1 5 1
                  B    0 2 0 4 0 4
                  C    0 0 0 0 0 6
  

• Em termos mais técnicos, depois de comparar txt[i] com pat[j], você deve comparar txt[i+1] com  pat[dfa[txt[i]][j]].
• Por exemplo, se txt[i] == pat[j] então dfa[txt[i]][j] == j+1.
• Exemplo: rastro da busca do padrão ABABAC num texto:

  

• Podemos dizer que o método search() de KMP tem os seguintes invariantes: imediatamente antes do teste i < N && j < M ,
  1. pat não ocorre em txt[0..i-1],
  2. pat[0..k] é diferente de txt[i-k..i] para todo k no conjunto j+1..M-1,
  3. pat[0..j-1] é igual a txt[i-j..i-1].

• Por que os exemplos parecem tão artificiais?  Resposta: exemplos mais naturais teriam que ser muito mais compridos. (Pensando bem, os exemplos não são tão artificiais assim: pense em genomas e DNA.)

Exercícios 1

1. Quais são os invariantes do método search() do KMP?

Autômato de estados determinístico (DFA)

• A tabela dfa[][] representa uma máquina imaginária conhecida como autômato de estados (deterministic finite-state automaton, DFA).  Os estados do autômato correspondem aos índices 0..M-1 de pat.  (Também há um estado final M.)  Para cada estado e cada caractere do alfabeto, há uma transição que leva desse estado a um outro. 
• Exemplo para alfabeto  A B C  e padrão ABABAC:

  

• O algoritmo KMP simula o funcionamento do autômato de estados.  O autômato começa no estado 0 e lê os caracteres do texto, um de cada vez, da esquerda para a direita, mudando para um novo estado cada vez que lê um caractere do texto.  Se atingir o estado M, dizemos que o autômato reconheceu ou aceitou o padrão. Se chegar ao fim do texto sem atingir o estado M, sabemos que o padrão não ocorre no texto.
• O autômato está no estado j se acabou de casar os j primeiros caracteres do padrão com um segmento do texto, ou seja, se acabou de casar pat[0..j-1] com txt[i-j..i-1].
• Para cada estado j, a transição que corresponde ao caractere  pat[j]  é de casamento e leva ao estado j+1.  Todas as outras transições que começam no estado j são de conflito e levam a um estado  ≤ j.
• O website do livro tem um video (algs4.cs.​princeton.edu/​lectures/​53DemoKnuthMorrisPratt.mov) que ilustra o funcionamento do autômato acima.
• O autômato de estados é uma ideia muito importante (em compilação, na teoria da computação, etc.).

Construção do DFA

• Como construir o autômato DFA, isto é, como calcular a tabela dfa[][]?
• Suponha que pat[0..j] é igual a txt[i-j..i] exceto no último caractere.  Como txt[i-j..i-1] e pat[0..j-1] são idênticos, podemos dispensar txt e fazer os cálculos usando apenas pat e testando todos os valores que txt[i] poderia ter.
• Assim, podemos pré-processar o padrão pat antes de conhecer o texto txt, desde que o alfabeto de txt seja conhecido.  Para qualquer caractere c do alfabeto e qualquer j em 0..M-1, o valor de  dfa[c][j]  é o comprimento do maior prefixo de pat[0..j] que é sufixo de pat[0..j-1]+c.   (A expressão s+c representa o resultado de acrescentar o caractere c ao final da string s.)
• Uma implementação literal dessa definição faria cerca de RM³ comparações entre caracteres para calcular a tabela dfa[][], sendo R o número de caracteres do alfabeto.  Mas é possível calcular a tabela de maneira bem mais eficiente, como mostra a discussão a seguir.

Exercícios 2

1. Importante.  Escreva um algoritmo do tipo força bruta que receba pat e o alfabeto do texto e construa a tabela dfa[][].  Comparar o resultado com o do método KMP() do livro.

Construção eficiente do DFA

• Suponha que pat[0..j] é igual a txt[i-j..i] exceto no último caractere.  Queremos saber em que estado o DFA estaria se retrocedessemos o índice i para i-j+1, ou seja, se o autômato partisse do estado 0 e lesse o texto txt[i-j+1..i].  Uma vez calculado esse estado X, podemos reiniciar o DFA nesse estado como se i tivesse retrocedido.
• Como txt[i-j+1..i-1] é igual a pat[1..j-1], podemos calcular o estado de reinício X sem conhecer o texto.
• Exemplo: padrão ABABAC e alfabeto  A B C :

  

• Exemplo: Construção o autômato para o padrão ABABAC e o alfabeto  A B C :

  

• A segunda parte do video algs4.cs.​princeton.edu/​lectures/​53DemoKnuthMorrisPratt.mov (no website do livro) ilustra a construção do DFA no exemplo acima.
• Código (surpreendentemente curto) da construção do DFA no algoritmo KMP  (o alfabeto é 0..R-1):

  dfa[pat.charAt(0)][0] = 1;
  for (int X = 0, j = 1; j < M; j++) {
     for (int c = 0; c < R; c++)
        dfa[c][j] = dfa[c][X];     // copia casos de conflito
  
     dfa[pat.charAt(j)][j] = j+1;  // define casos de casamento
     X = dfa[pat.charAt(j)][X];    // atualiza estado de reinício
  }
  

Código completo do algoritmo KMP

• Algorithm 5.6: KMP (Knuth-Morris-Pratt) substring search para alfabeto ASCII estendido:

  public class KMP {
  
     private String pat;
     private int[][] dfa;
  
     // Construtor (pré-processamento): calcula autômato dfa[][]
     public KMP(String pat) {
        this.pat = pat;
        int M = pat.length();
        int R = 256;
        dfa = new int[R][M];
        dfa[pat.charAt(0)][0] = 1;
  
        for (int X = 0, j = 1; j < M; j++) {
           // calcula dfa[][j]
           for (int c = 0; c < R; c++)
              dfa[c][j] = dfa[c][X];
           dfa[pat.charAt(j)][j] = j+1;
           X = dfa[pat.charAt(j)][X];
        }
     }
     
     // Simula funcionamento do DFA sobre o texto txt
     public int search(String txt) {
        int j, M = pat.length();
        int i, N = txt.length();
  
        for (i = 0, j = 0; i < N && j < M; i++)
           j = dfa[txt.charAt(i)][j];
        if (j == M) return i - M;
        else        return N;
     }
  
     // Cliente de teste
     public static void main(String[] args) {
        String pat = args[0];
        String txt = args[1];
        KMP kmp = new KMP(pat);
        StdOut.println("text:    " + txt);
        int offset = kmp.search(txt);
        StdOut.print("pattern: ");
        for (int i = 0; i < offset; i++)
           StdOut.print(" ");
        StdOut.println(pat);
     }
  
  }
  

• O construtor KMP() constrói uma instância específica para procurar um determinado padrão (em qualquer texto dado).
• Saída de um teste:

  % java KMP AACAA AABRAACADABRAACAADABRA
  text:    AABRAACADABRAACAADABRA
  pattern:             AACAA
  

• Veja documentação completa da classe KMP do livro. Veja o código completo em algs4/KMP.java.

Desempenho do KMP

• O algoritmo KMP é linear:  faz apenas M comparações entre caracteres para construir o DFA e depois no máximo N comparações entre caracteres para procurar o padrão.
• Proposição N.  O algoritmo KMP examina não mais que M + N caracteres.
• Se levarmos em conta o tamanho do alfabeto, R, o consumo de tempo para construir o DFA é MR .

Exercícios 3

1. (SW 5.3.2)  Dê a tabela dfa[][] do algoritmo KMP para o padrão  A A A A A A A A A.  Faça um desenho do DFA.
2. (SW 5.3.3)  Dê a tabela dfa[][] do algoritmo KMP para o padrão  A B R A C A D A B R A.  (Suponha que o alfabeto é  A B C D R .)  Faça um desenho do DFA.
3. (SW 5.3.17)  Mostre o autômato dfa[][] do algoritmo KMP para o alfabeto  A B C  e os seguintes padrões:
   • A A A A A A B
   • A A C A A A B
   • A B A B A B A B
   • A B A A B A A A B A A A B
   • A B A A B C A B A A B C B
4. (SW 5.3.8)  Acrescente à classe KMP um método count() que conte o número de ocorrências do padrão.  (Por exemplo, o padrão  abcab  ocorre duas vezes no texto  xxxabcabcabxxxx.)  Acrescente um método searchAll() que imprima todas as ocorrências.
5. (SW 5.3.24.b) Todas as ocorrências. Acrescente à classe KMP um método findAll() que devolve um Iterable<Integer> que permita ao cliente iterar sobre os inícios de todas as ocorrêcias do padrão no texto.
6. (SW 5.3.14)  Escreva uma versão da classe KMP que use vetores de caracteres em lugar do tipo String para representar o padrão e o texto.
7. (SW 5.3.25a) Streaming. Acrescente à classe KMP um método search() que receba um fluxo de entrada do tipo In como argumento e procure pelo padrão pat no fluxo de entrada especificado. Não use variáveis de instância adicionais (em particular, não armazene qualquer trecho do texto na memória).
8. (SW 5.3.26) Rotação cíclica. Escreva um programa que receba duas strings e decida se uma é rotação cíclica da outra. (Por exemplo, example é rotação cíclica de ampleex.)
9. (SW 5.3.27) Repetições em série. Uma repetição em série de uma string-base b em uma string s é uma substring de s que tenha pelo menos duas cópias consecutivas (sem sobreposição) de b.  Implemente um algoritmo de tempo linear que receba strings b e s e devolva o índice do início da mais longa repetição em série de b em s.  Por exemplo, seu programa deve devolver 3 quando b é  abcab  e s é  abcabcababcababcabcab.
10. (SW 5.3.37) KMP para texto aleatório. Escreva um cliente que receba inteiros M, N e T e execute o seguinte experimento T vezes: Gere um padrão aleatório de comprimento M e um texto aleatório de comprimento N e conte o número de comparações entre caracteres executado por KMP ao procurar o padrão no texto.  Imprima a média das contagens dos T experimentos.

 

---

Qual algoritmo de busca de substring é melhor?

• O algoritmo de força bruta (página anterior) é bom se o padrão e o texto não tiverem muitas auto-repetições.
• O algoritmo KMP é rápido e tem a vantagem de nunca retroceder sobre o texto, o que é importante se o texto for dado como um fluxo contínuo (streaming).
• O algoritmo de Boyer-Moore é provavelmente o mais rápido na prática. Não vou tratar do algoritmo aqui, mas você pode encontrá-lo no livro.
• O algoritmo de Rabin-Karp (próxima página) é rápido mas pode dar resultados errados (com baixissima probabilidade).

Exercícios 4

1. (SW 5.3.4) M brancos consecutivos. Escreva um método eficiente que receba um texto txt e um inteiro M e devolva a posição da primeira ocorrência de M brancos consecutivos no texto. Se não há uma tal ocorrência, devolva txt.length().  Estime o número de comparações de caracteres que seu método faz no pior caso e para um txt típico.

Próximo passo?

• Que acontece se o padrão não é apenas uma string mas um conjunto de strings descrito por uma expressão regular  como  A*|(A*BA*BA*)*  ou  ((A*B|AC)D),  por exemplo?
• Essa generalização do problema de busca é muito importante. A solução envolve o conceito de autômato de estados não determinístico.
• A solução do problema leva a aplicativos como o célebre grep.
• Veja a seção 5.4 (Regular Expressions) do livro.