Ois,
No nosso encontro de ontem conversamos sobre Busca de substring (Substring Search no algs4)
Na maior parte do tempo falamos sobre o algoritmo KMP para busca de substring, mas nos últimos 5 minutos finais vomitei comentários sobre o algoritmo de Boyer-Moore e sobre o algoritmo de Rabin-Karp. A seguir está um resumo da história.
A propósito, pretendo colocar uma questão sobre Boyer-Moore na nossa próxima e última provinha de MAC0323.
Estude a versão de Boyer-Moore que estão nas notas de aula.
Você deve saber seu consumo de tempo e em particular a bad charactere rule.
Suponha que txt
e pat
são strings e que n = txt.length()
e m = pat.length()
.
Tipicamente n
é muuiiitooo maior que m
.
Pré-processamos a string txt
e construímos o vetor de sufixos de txt
a fim de responder rapidamente consultas como:
- uma dada string
pat
está emtxt
? - qual o número de ocorrências de uma dada string
pat
emtxt
? - encontrar uma substring mais longa que se repete em
txt
(LRS = longest repeated substring).
Em busca de substrings a atriz principal é pat
.
Tipicamente estamos interessados em responder consultas como:
encontrar uma (todas) ocorrências de (uma dada)
pat
em uma dada stringtxt
.
O algoritmo força-bruta faz o serviço em tempo O
(
n
)
no melhor caso e O
(
n
m
)
no pior caso.
Se fizéssemos um paralelo com ordenação, o algoritmo força-bruta seria talvez ordenação por inserção.
KMP, devido a um pré-processamento de pat
que constrói uma representação de um autômato finito determinístico (DFA), encontra pat
em txt
em tempo linear no pior caso O
(
n
+
m
)
.
Se fizéssemos um paralelo com ordenação, o KMP
seria o Heapsort
devido ao seu consumo de tempo ótimo.
Boyer-Moore é um algoritmo muito simples que utiliza alguma heurística como bad character para encontra pat
em txt
em tempo O
(
n
m
)
no pior caso mas no melhor caso seu consumo de tempo é O
(
n
/
m
)
, ou seja sublinear.
Frequentemente Boyer-Moore faz o serviço sem olhar todos os caracteres de txt
.
Se fizéssemos um paralelo com ordenação, Boyer-Moore seria o Quicksort
devido a sua simplicidade e eficiência comprovada no dia a dia.
No código da função strstr()
da glibc
encontramos o comentário:
/* We use the Two-Way string matching algorithm, which guarantees
linear complexity with constant space. Additionally, for long
needles, we also use a bad character shift table similar to the
Boyer-Moore algorithm to achieve improved (potentially sub-linear)
performance.
See http://www-igm.univ-mlv.fr/~lecroq/string/node26.html#SECTION00260
and http://en.wikipedia.org/wiki/Boyer-Moore_string_search_algorithm
*/
Finalmente, Rabin-Karp tem outra baita ideia!
É particularmente útil quando pat
é grande.
A ideia é calcular hash(pat)
e comparar esse valor com hash(janela)
onde janela
é uma substring de txt
de comprimento m
.
A sacada é que a medida que a janela
anda em txt
o valor de hash()
da nova janela muda pouco e pode ser calculado em tempo constante!
Ao encontrar uma janela
de txt
que parece ser igual a pat
(porque tem o mesmo hash
), o algoritmo compara pat
e a janela
.
O legal de Rabin-Karp é que pat
pode ser bidimensional: por exemplo uma imagem sendo procurada em outra imagem txt
.