O ALGORITMO RABIN KARP

ALGORITMO RABIN-KARP

1. Introdução

O algoritmo de Rabin-Karp é um algoritmo de String Matching (conhecido também como casamento de cadeias, correspondência de cadeias) que consiste em encontrar uma ocorrência de uma cadeia s em uma cadeia  esse processo de reconhecimento de padrões em textos é uma dificuldade que vem sendo estudada por parte de vários pesquisadores da área de ciência da computação. Os algoritmos de string matching são utilizados como componente importante para a resolução de vários problemas que surgem em diversas áreas do conhecimento, dentre os quais podem ser destacados: [pic 1]

• Análises de exames médicos para identificação da existência de tumores em tomografias, por exemplo;
• Análises agrícolas, meteorológicas, geológicas, geográficas etc., de imagens capturadas por aerofotogrametria ou por satélites;
• Biologia computacional para o reconhecimento de subsequências de nucleotídeos que compõem o DNA;  
• Processamento de textos, quando se busca encontrar as ocorrências de determinadas palavras.

1. Algoritmo de Rabin-Karp

O algoritmo de Rabin-Karp (Richard M. Karp e Michael O. Rabin, 1987), tem característica probabilística, pois ele transforma a palavra procurada em um número, seguindo determinadas regras.

O algoritmo de Rabin-Karp apresenta uma evolução ao algoritmo de Força-Bruta, ao invés de comparar a janela com o padrão caracter a caracter, é proposto usar uma comparação numérica entre os restos da divisão por um mesmo inteiro da janela e do padrão. Uma comparação apenas entre números pequenos é mais rápida que a comparação de todos os caracteres. Tudo que é necessário é processar a função de assinatura de cada substring de m-caracteres no texto e checar se é igual à assinatura da função da palavra procurada. Karp e Rabin encontraram uma forma fácil para processar estas funções de assinatura eficientemente para a função:

• h (k) = k mod q,  onde q é um número primo grande para evitar colisões.

A probabilidade de uma colisão aleatória é de  .[pic 2]

Dado um padrão P[1...m], seja p seu valor decimal correspondente. De modo semelhante, dado um texto T[1..n], seja  o valor decimal da subcadeia de comprimento m T[s + 1..s + m], para s = 0, 1, ..., n – m. Certamente,   = p se e somente se T[s + 1..s + m] = P[1..m]; assim, s é um deslocamento válido se e somente se  = p. Pode-se calcular p no tempo O(m) e todos os valores t s em um tempo total O(n – m + 1),1 poderíamos determinar todos os deslocamentos válidos s no tempo O(m) + O(n – m + 1) = O(n), comparando p com cada um dos valores . [pic 3][pic 4][pic 5][pic 6]

Podemos calcular p no tempo O(m) usando a regra de Horner:

[pic 7]

De modo semelhante, podemos calcular t˳ por T[1...m] no tempo O(m). Para calcular os valores restantes t1, t2...,  no tempo O(n – m), pode-se calcular  a partir de  em tempo constante, já que:[pic 8][pic 9][pic 10]

[pic 11]

subtrair 10m - 1T[s + 1] elimina o dígito de ordem mais alta de t, multiplicar o resultado por 10 desloca o número uma posição de dígito para a esquerda e somar T[s + m + 1] introduz o dígito de ordem baixa adequado.

Há a possibilidade também de p e  ser demasiadamente grandes para que se possa trabalhar com eles de uma forma conveniente. Se P contém m caracteres, não seria razoável considerar que cada operação aritmética para p (que tem m dígitos de comprimento) demora um “tempo constante”. Se escolhermos o módulo q como um primo tal que 10q caiba em uma palavra de computador, poderemos executar todos os cálculos necessários com aritmética de precisão simples.[pic 12]

Podemos calcular p módulo  no tempo O(m) e todos os valores  módulo q no tempo O(n – m + 1). Se escolhermos o módulo q como um primo tal que 10q caiba em uma palavra de computador, poderemos executar todos os cálculos necessários com aritmética de precisão simples. Em geral, com um alfabeto d-ário {0, 1, ... d – 1}, escolhemos q de modo que dq caiba em uma palavra de computador e ajustamos a equação de recorrência para calcular com módulo q; assim, ela se torna:[pic 13][pic 14]

[pic 15]

onde h ≡ dm - 1 (mod q) é o valor do dígito “1” na posição de ordem alta de uma janela de texto de m dígitos. Entretanto, a solução para trabalhar com módulo q não é perfeita:  ≡ p (mod q) não implica que = p. Por outro lado, se  p (mod q), então definitivamente temos que  ≠ p, de modo que o deslocamento s é não válido. Assim, podemos usar o teste ts ≡ p (mod q) como um teste heurístico rápido para eliminar deslocamentos s não válidos.[pic 16][pic 17][pic 18][pic 19]

Qualquer deslocamento s para o qual  ≡ p (mod q), deve passar por um teste adicional para verificar se s é realmente válido ou se temos apenas um acerto espúrio. Esse teste adicional verifica explicitamente a condição P[1 ... m] = T[s +1 ... s + m]. Se q é suficientemente grande, esperamos que a ocorrência de acertos espúrios seja infrequente o suficiente para que o custo da verificação extra seja baixo.[pic 20]

...