Algoritmo de Rabin-Karp para busca de substring

Livro de Sedgewick e Wayne: fim da sec.5.3, p.774.  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 trata de um algoritmo probabilístico de impressão digital para o problema substring search.

Algoritmo RK

• O algoritmo RK, inventado por M. Rabin e R. Karp, encontra um padrão num texto.  O algoritmo também é conhecido como busca por impressão digital (fingerprint search).
• O algoritmo Rabin-Karp compara padrão com texto indiretamente:  procura um segmento do texto que tenha o mesmo valor hash do padrão.
• O algoritmo usa hashing modular;  digamos que o módulo é Q.
• Exemplo: encontrar padrão  26535  no texto  3141592653589793  usando módulo Q = 997:

  

• Exemplo mais interessante: procure 12345 nos primeiros 100 mil dígitos da expansão decimal do número π.
• Rascunho (muito grosseiro) do algoritmo de Rabin-Karp:

  private int search(String pat, String txt) {
     int M = pat.length();
     int N = txt.length();
     long patHash = hash(pat, M);
  
     for (int i = 0; i <= N - M; i++) {
        long txtHash = hash(txt.subtring(i, i+M), M);
        if (patHash == txtHash)
           return i; // ocorrência? colisão?
     }
     return N; // nenhuma ocorrência
  }
  

• Se hash do padrão é diferente do hash de todos os segmentos do texto então o padrão não ocorre no texto.  A recíproca não vale pois pode haver colisão (duas strings diferentes podem ter o mesmo hash).

Resolvendo as dificuldades técnicas

• Notação: o padrão tem M caracteres, o texto tem N caracteres, o alfabeto tem R caracteres  (0 … R−1).
• Por exemplo, R = 10 (alfabeto de dígitos decimais) ou R = 256 (alfabeto ASCII estendido).
• Dificuldade 1:  Como calcular o hash de um padrão pat longo (que não cabe em um int, por exemplo)?  Pergunta análoga: qual a maneira mais rápida de calcular  4R³ + 7R² + 3R¹ + 5 ?
  • Não:   4 × R × R × R + 7 × R × R + 3 × R + 5
  • Sim:   ((4 × R + 7) × R + 3) × R + 5

  Algoritmo de Horner para calcular o hash de uma string s[0..M-1]:

  private long hash(String s, int M) {
     long h = 0;
     for (int j = 0; j < M; j++)
        h = (h * R + s.charAt(j)) % Q;
     return h;
  }
  

• Exemplo para o padrão 26535 com R = 10 e Q = 997:

  

• Dificuldade 2:  Como calcular eficientemente o hash dos segmentos consecutivos do texto txt?
• Digamos que  t_i  é  txt[i]  e  x_i  é o inteiro representado por t_i t_i+1 … t_i+M−1 .  Então
  • x_i−1 = t_i−1 R^M−1 + t_i R^M−2 + t_i+1 R^M−3 + … + t_i+M−2 R⁰
  • x_i−1 = t_i−1 R^M−1 + t_i R^M−1 + t_i+1 R^M−2 + … + t_i+M−2 R¹ + t_i+M−1 R⁰
• Logo,    x_i  =  (x_i−1  −  t_i−1 R^M−1) R  +  t_i+M−1 .
• Exemplo com M = 5, R = 10  e  texto  4 1 5 9 2 6 5 …

  

• Conclusão: podemos calcular o hash de um segmento do texto a partir do hash do segmento anterior em tempo constante (independente de M):

  x_i%Q   =   (x_i−1%Q − t_i−1 R^M−1) R  +  t_i+M−1 .

• Qual o valor de Q?  Escolha Q igual a um primo grande para minimizar a chance de colisões.
• Dificuldade 3:  Cálculos com números grandes podem produzir overflow. Isso produz números negativos. Hashing modular não gosta de números negativos. Solução:
  • use um tipo-de-dados capaz de armazenar Q²,
  • na prática, escolha Q que caiba em int (por exemplo, 2³¹−1 é primo!) e faça contas em long,
  • tome o resto da divisão por Q depois de cada operação aritmética,
  • some Q aos resultados intermediários quando necessário.
• Exemplos de cálculo  mod 997:

  (10000 + 535) * 1000  =  (30 + 535) * 3
                        =   565 * 3
                        =   1695
                        =   698 
  
  508 - 3 * 10000  =  508 - 3 * (30)
                   =  508 + 3 * (-30)
                   =  508 + 3 * (997 - 30)
                   =  508 + 3 * 967
                   =  508 + 907
                   =  418
  

• Resumo: hash de x_i a partir do hash de x_i−1:

  x_i%Q  =  ((x_i−1%Q + t_i−1 (Q − R^M−1%Q)) × R  +  t_i+M−1) % Q .

• Exemplo com  R = 10,  Q = 997  e portanto  (R^M−1%Q) = 30 = RM :

  

Exercícios 1

1. Suponha que o tipo int do meu computador é capaz de armazenar apenas números no intervalo -1000000..99999. Mostre como calcular o valor da expressão ((929 - 9*155)*62 + 55) % 997 sem correr o risco de overflow.
2. (SW 5.3.23)  Escreva um programa rápido que leia caracteres da entrada padrão, um a um, e diga, a cada instante, se a string lida até o momento é um palíndromo. (Dois exemplos de palíndromos:   anilina  e  sopapos.)  Use as mesmas ideias do algoritmo de Rabin-Karp.
3. Seja R um número inteiro positivo e (d_n, d_n−1, … , d₁, d₀) uma sequência de números do conjunto {0,1, … , R−1}. Para cada i, (d_i, d_i−1, … , d₁, d₀) representa um número x_i na base R, sendo d_i o dígito mais significativo e d₀ o menos significativo. Mostre como calcular x_n a partir de x_n−1 eficientemente. Ignore a possibilidade de overflow aritmético.

Implementação do algoritmo RK

• Algoritmo de Rabin-Karp para busca de substring. Esta é a versão Monte Carlo (veja abaixo). Supõe que o alfabeto é ASCII estendido:

  public class RabinKarp {
  
     private String pat;  
     private long patHash;  // hash do padrão
     private int M;
     private long Q;
     private int R = 256;
     private long RM;
  
     public RabinKarp(String pat) {
        this.pat = pat;
        M = pat.length();
        Q = longRandomPrime();
        RM = 1;
        for (int i = 1; i <= M-1; i++) // calcula R^(M-1)%Q
           RM = (R * RM) % Q;
        patHash = hash(pat, M);
     }
  
     private long hash(String key, int M) {
        long h = 0;
        for (int j = 0; j < M; j++)
           h = (R * h + key.charAt(j)) % Q;
        return h;
     }
  
     private int search(String txt) {
        int N = txt.length();
        long txtHash = hash(txt, M);
        if (patHash == txtHash && check(txt, 0)) // casamento
           return 0; 
        for (int i = 1; i <= N - M; i++) {
           txtHash = (txtHash + Q - RM*txt.charAt(i-1) % Q) % Q;
           txtHash = (txtHash * R + txt.charAt(i+M-1)) % Q;
           if (patHash == txtHash)
              if (check(txt, i)) 
                 return i; // casamento
        }
        return N; // nenhum casamento
     }
  
     public boolean check(String txt, int i) { 
        return true; // Monte Carlo
     } 
  }
  

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

Exercícios 2

1. (SW 5.3.33) Primos aleatórios. Implemente o método longRandomPrime() na classe RabinKarp.  Dica: Um número aleatório de n dígitos é primo com probabilidade proporcional a 1/n.

Versões Monte Carlo e Las Vegas

• A versão acima do algoritmo Rabin-Karp é do tipo Monte Carlo:  ao encontrar um segmento de txt que parece ser igual a pat (porque tem o mesmo hash), a versão aposta que resolveu o problema.
• Há uma versão do tipo Las Vegas:  ao encontrar um segmento de txt que parece ser igual a pat (porque tem o mesmo hash), compara as duas strings e continua a busca se a comparação falhar.  Para obter essa versão, troque o método check() acima por

     public boolean check(String txt, int i) { 
        for (int j = 0; j < M; j++) 
           if (pat.charAt(j) != txt.charAt(i + j)) 
              return false; 
        return true;
     }
  

• A versão Monte Carlo pode dar resposta errada, mas a probabilidade desse evento é muito baixa (se Q for um primo grande).  O consumo de tempo da versão Monte Carlo é linear, ou seja, proporcional a N.
• A versão Las Vegas sempre dá resposta certa mas seu consumo de tempo pode não ser linear: no pior caso, o consumo é proporcional a MN (como o do algoritmo de força bruta), embora a probabilidade desse evento seja muito baixa.
• Propriedade P. A versão Monte Carlo do algoritmo de Rabin-Karp é linear e dá a resposta correta com altíssima probabilidade. A versão Las Vegas sempre dá a resposta correta e é linear com altíssima probabilidade.

Exercícios 3

1. (SW 5.3.25b) Fluxo contínuo (streaming). Acrescente à classe RabinKarp 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).
2. (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.)
3. (SW 5.3.32) Contagem de substrings de comprimento L. Escreva um programa que leia um texto da entrada padrão e calculate o número de substrings de comprimento L distintas que o texto contém.  Por exemplo, o texto cgcgggcgcg tem cinco substrings de comprimento 3 distintas:  cgc, cgg, gcg, ggc, e ggg.  Dica: Insira cada substring de comprimento L em uma tabela de símbolos. Use ideias análogas às do algoritmo de Rabin-Karp.

Exercícios sobre busca de substring

1. (SW 5.3.36) Texto aleatório. Escreva um programa que receba inteiros M e N como argumentos, gere uma string aleatória txt de comprimento N sobre o alfabeto  0 1  e depois conte o número de ocorrências em txt da substring formada pelos M últimos caracteres de txt.  Nota: O melhor algoritmo para o problema pode depender do valor de M.
2. (SW 5.3.39) Comparação de algoritmos. Escreva um programa que cronometre os quatro métodos de busca de substring — força bruta, Knuth-Morris-Pratt, Rabin-Karp Monte Carlo, e Rabin-Karp Las Vegas — na execução da tarefa de procurar a string abaixo no livro tale.txt.  Discuta até que ponto seus resultados confirmam as previsões teóricas sobre o desempenho dos algoritmos.

        it is a far far better thing that i do than i have ever done