O ALGORITMO RABIN KARP
Por: polyanasilva18 • 8/7/2019 • Trabalho acadêmico • 2.262 Palavras (10 Páginas) • 177 Visualizações
ALGORITMO RABIN-KARP
- 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.
- 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]
...