Aula 12_CasPadrao_Alg Força Bruta_Rabin Karp

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Lívia N. Andrade
Processamento de Cadeias de Caracteres
Casamento Exato
Consiste em obter todas as ocorrências exatas do padrão no texto.
	Ex.: ocorrência exata do padrão teste.
Dois enfoques, dependendo da forma como P é pesquisado em T:
leitura dos caracteres do texto um a um: algoritmos força bruta, Knuth-Morris-Pratt e Shift-And.
pesquisa de P em uma janela que desliza ao longo de T, pesquisando por um sufixo da janela que casa com um sufixo de P, por comparações da direita para a esquerda: algoritmos Boyer-Moore e Boyer-Moore-Horspool.
Algoritmo 
Força Bruta
Definições
Algoritmo mais simples para casamento de cadeias;
P e T não são conhecidos ‘a priori’ (não são pré-processados);
A idéia do algoritmo consiste em tentar casar qualquer subcadeia no texto de comprimento m com o padrão.
Definições
Algoritmo mais simples para casamento de cadeias;
P e T não são conhecidos ‘a priori’ (não são pré-processados);
A idéia do algoritmo consiste em tentar casar qualquer subcadeia no texto de comprimento m com o padrão.
Definições
Algoritmo mais simples para casamento de cadeias;
P e T não são conhecidos ‘a priori’ (não são pré-processados);
A idéia do algoritmo consiste em tentar casar qualquer subcadeia no texto de comprimento m com o padrão.
Definições
Algoritmo mais simples para casamento de cadeias;
P e T não são conhecidos ‘a priori’ (não são pré-processados);
A idéia do algoritmo consiste em tentar casar qualquer subcadeia no texto de comprimento m com o padrão.
Força Bruta
Idéia básica de funcionamento:
	
Considerando o padrão P a ser encontrado no texto T e i como a posição de início da comparação na cadeia, são feitas comparações iniciando da primeira posição de T 
 P[1] = T[1]; P[2] = T[2]; P[3] = T[3] …
.
T [1]
P [1]
Força Bruta
Idéia básica de funcionamento:
	
Considerando o padrão P a ser encontrado no texto T e i como a posição de início da comparação na cadeia, são feitas comparações iniciando da primeira posição de T 
 P[1] = T[1]; P[2] = T[2]; P[3] = T[3] …
Se a comparação informar que os caracteres são diferentes, o algoritmo pára a análise, verifica qual é a posição de inicio e soma um a este valor, continuando as comparações da posição seguinte do texto 
 P[1] = T[2]; P[2] = T[3]; P[3] = T[4] … 
Força Bruta
Idéia básica de funcionamento:
	
Considerando o padrão P a ser encontrado no texto T e i como a posição de início da comparação na cadeia, são feitas comparações iniciando da primeira posição de T 
 P[1] = T[1]; P[2] = T[2]; P[3] = T[3] …
Se a comparação informar que os caracteres são diferentes, o algoritmo pára a análise, verifica qual é a posição de inicio e soma um a este valor, continuando as comparações da posição seguinte do texto 
 P[1] = T[2]; P[2] = T[3]; P[3] = T[4] … 
T [2]
P [1]
Força Bruta
Força Bruta
	Este algoritmo possui o menor desempenho, pois faz verificações de forma exaustiva, sem utilizar comparações previas para melhorar o desempenho.
Considerações sobre o algoritmo
Algoritmo 
Rabin Karp
Definições
Criado por Michael Rabin e Richard Karp, o algoritmo é uma melhoria do algoritmo de força bruta;
Baseado em uma teoria de números, o algoritmo utiliza uma função hash para localizar strings em textos.
A idéia do algoritmo consiste em tentar casar qualquer subcadeia no texto de comprimento m com o padrão.
Algoritmo Rabin Karp
Princípio: tratar o texto como dados numéricos e não realizar comparações diretamente entre os caracteres.
O padrão P ocorre no texto T se o valor calculado para P for igual ao valor calculado para qualquer substring X de T, de tamanho m, tal que | X | = | P |
Algoritmo Rabin Karp
A idéia principal é:
	Se duas cadeias de letras forem iguais, os seus valores hash também deverão ser iguais. 
	
	Desta forma, deve-se calcular o valor hash do padrão a ser procurado e, após isto, iniciar a comparação com o valor hash do texto de referencia.
Pré-processamento do P
A
D
A
P
∑ = {A, B, C, ... , Z}* código ASCII 
base = 101
B
A
B
A
D
B
A
A
D
D
A
Texto
97
100
Pré-processamento do P
A
D
A
P
∑ = {A, B, C, ... , Z}* código ASCII 
base = 101
Calculando o valor hash do Padrão
	
	P[1] * 1012 + P[2] * 1011 + P[3] * 1010
	 97 * 1012 + 100 * 101 + 97 
	
	
B
A
B
A
D
B
A
A
D
D
A
Texto
97
100
Pré-processamento do P
A
D
A
P
∑ = {A, B, C, ... , Z}* código ASCII 
base = 101
Calculando o valor hash do Padrão
	
	P[1] * 1012 + P[2] * 1011 + P[3] * 1010
	 97 * 1012 + 100 * 101 + 97 
	 989594 + 10100 + 97
	
B
A
B
A
D
B
A
A
D
D
A
Texto
97
100
999694
Executando o algoritmo
A
D
A
P
B
A
B
A
A
D
B
A
D
A
D
Texto
999694
Calculando o valor hash do Texto BAB	
	 98 * 1012 + 97 * 1011 + 98 * 1010
	 98 * 1012 + 97 * 101 + 98 
	 999698 + 9797 + 98
1009593
Valores diferentes. Não ocorreu casamento de padrão
Executando o algoritmo
A
D
A
P
B
A
B
A
A
D
B
A
D
A
D
Texto
999694
	(1009593 - 98 * 1012 ) * 101 + 97
999492
Calculando o valor hash do Texto ABA	
	 97 * 1012 + 98 * 1011 + 97 * 1010
	
Valor hash de BAB
Valores do primeiro caractere
Valor do último caractere
Valores diferentes. Não ocorreu casamento de padrão
Executando o algoritmo
A
D
A
P
B
A
B
A
A
D
B
A
D
A
D
Texto
B
A
D
A
D
A
999694
BAD	
(999492 - 97 * 1012 ) * 101 + 100
1009595
Processamento de Cadeias de Caracteres: Algoritmo Rabin Karp
D
A
D
A
D
B
B
A
D
B
A
D
A
D
A
Executando o algoritmo
A
D
A
P
B
A
B
A
A
D
B
A
D
A
D
Texto
B
A
D
A
D
A
999694
ADA	
(1009595 - 98 * 1012 ) * 101 + 97
999694 – 989497) * 101 + 100
1029997
999694
Processamento de Cadeias de Caracteres: Algoritmo Rabin Karp
D
A
D
A
D
B
B
A
D
B
A
D
A
D
A
Problemas com o algoritmo
Os valores das transformações de P e das substrings de T são muito grande, quando m e |∑| são muito longos 
Solução 1: reduzir esses valores a uma faixa controlada, utilizando módulo de um número q, por exemplo.
Novo problema: um mesmo valor pode representar substrings distintas.
Solução 2: ocorrendo um provável casamento de P com uma substring X de T, cada caractere de P deve ser comparado a cada caractere de X, para verificar se o casamento realmente acontece.
Exemplo
Valor hash igual. Inicia-se uma comparação entre cada caractere.
Função retorna falso pois a sequência das letras não é igual. 
Exemplo
Valores hash e a ordem das letras são iguais...
Função termina a execução e retorna a posição como resposta.
	Mesmo que este algoritmo possua o pior desempenho para O(mn) e tenha desempenho inferior para pesquisa de padrões simples, o método possui a vantagem na busca de padrões compostos, tendo assim uma grande aplicação como validação de rotinas para análise de plágio.
		Pseudocódigo do 
			Algoritmo Rabin Karp
		Notação:
n: número de caracteres do texto;
m: número de caracteres da palavra;
b: cardinalidade do alfabeto Σ ;
q: número primo, como: 16647133;
T: string do texto;
P: string da palavra.
Inicialização das variáveis utilizadas no código. É importante ressaltar que a implementação da função hash é arbitrária;
Iteração com índice relacionado à cardinalidade da palavra. O bloco inicializa o hash (p) da palavra e do texto, hash (t);
Neste bloco tem-se a iteração de comparação; 
Se a comparação da linha 16 for válida temos a possibilidade da substring encontrada ser a procurada.
Uma comparação extra (linha 18) é realizada para confirmar o resultado; comparando os caracteres da substring com a palavra.
 
Palavras iguais, retorna a posição da palavra.
Senão, temos um novo valor de hash(t) para a substring, realizando a iteração até encontrar a(s) palavra(s) ou se esgotar o texto.
Bibliografias consultadas
Livros:
ZIVIANI, Nivio, Projeto de algoritmos com implementação em Pascal e C, 3a. edição, Editora Thomson, 2011
CORMEN, T. H., LEISERSON & RIVEST, R. L. Algoritmos: teoria e prática, Editora Campus, 2002.