Fórum de discussão

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 patsã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á em txt?
• qual o número de ocorrências de uma dada string pat em txt?
• 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 string txt.

O algoritmo força-bruta faz o serviço em tempo O(n) no melhor caso e O(nm) 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(nm) 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.