"É como procurar agulha num palheiro."

Quantas vezes a palavra algoritmo aparece nesta página?

Busca de palavras em um texto
(string searching)

(Veja os verbetes String searching algorithm e Boyer-Moore string search algorithm na Wikipedia.)

Dizemos que um vetor  a[1..m]  casa com um vetor  b[j..k]  se  a[1] = b[j],  a[2] = b[j+1],  … ,  a[m] = b[k];  é claro que devemos ter m-1 = k-j.    Um sufixo de um vetor b[1..k] é qualquer segmento  b[j..k]  do vetor;  é claro que 1 ≤ j ≤ k.    Dizemos que um vetor  a[1..m] ocorre em b[1..n]  se existe k no intervalo m..n tal que

a[1..m] casa com um sufixo de b[1..k].

Exemplos: A figura especifica alguns pares a, b.  O sinal ^ marca posições k tais que a casa com um sufixo de b[1..k].

 

e

s

p

e

c

i

f

i

c

a

A

f

i

g

u

r

a

e

s

p

e

c

i

f

i

c

a

a

l

g

u

n

s

^

									3	1	4	1	5	9
3	1	3	1	4	3	1	4	1	3	1	4	1	5	9	3	1	4	1	5	9	2	6	3	1	4
														^						^

T

A

C

T

A

G

T

A

G

T

A

T

A

T

A

T

A

T

A

T

A

C

T

A

C

T

A

G

T

A

G

^

^

O problema

Esta página estuda alguns algoritmos para o seguinte problema, conhecido como string matching:

Dados vetores a[1..m] e b[1..n], encontrar o número de ocorrências de a em b.

É conveniente dizer que o vetor a[1..m] é uma palavra e o vetor b[1..n] é um texto.  Nosso problema consiste, então, em contar o número de ocorrências de uma palavra em um texto.

Se m > n então o número de ocorrências é zero. Para garantir que o número de ocorrências seja finito, suporemos sempre que m ≥ 1.

Há duas questões triviais que convém esclarecer desde já. Para procurar a palavra a, podemos varrer o texto b da esquerda para a direita ou da direita para a esquerda. As duas alternativas são equivalentes; mas vamos adotar sempre a primeira: comparar a com b[1..m], depois com b[2..m+1], e assim por diante.

A comparação de a com um sufixo b[1..k] também pode ser feita da esquerda para a direita ou da direita para a esquerda. Em geral, as duas alternativas são equivalentes, mas um dos algoritmos que veremos adiante exige que a comparação seja feita na direção contrária à da varredura do texto. Por isso, adotaremos sempre comparação da direita para a esquerda: primeiro a[m] com b[k], depois a[m-1] com b[k-1], e assim por diante.

O algoritmo trivial

A seguinte função resolve o problema da maneira mais óbvia. Pacientemente, ela tenta casar a com b[1..m], depois com b[2..m+1], e assim por diante. O código supõe que os elementos de a e b são caracteres:

// Recebe vetores a[1..m] e b[1..n] com m >= 1 e n >= 0
// e devolve o número de ocorrências de a em b.

int 
trivial (unsigned char a[], int m,
         unsigned char b[], int n) 
{
   int i, j, k, occors = 0;
   for (k = m; k <= n; ++k) {
      i = m, j = k;
      while (i >= 1 && a[i] == b[j]) 
         --i, --j;   
      if (i < 1) ++occors;
   }
   return occors;
}

A função faz no máximo  m·n  comparações entre elementos de a e b e portanto consome tempo proporcional a mn no pior caso.  Desafio: resolver o problema fazendo menos comparações entre a palavra e o texto.

Exercícios

Primeiro algoritmo de Boyer-Moore

Suponha agora que o conjunto a que pertencem todos os elementos de a e de b é conhecido de antemão. Este conjunto é o "alfabeto" do problema. Se o alfabeto é conhecido de antemão, é possível fazer um algoritmo mais rápido que o trivial.

A ideia do algoritmo inventado por R.S. Boyer e J.S. Moore ("A fast string searching algorithm", Communications of the ACM, 20, p.762-772, 1977) é simples. Suponha que acabamos de comparar a com o sufixo apropriado de b[1..k] (o resultado da comparação não importa).  Feito isso, não é necessário comparar a com o sufixo de b[1..k+1]:  podemos tratar imediatamente de

b[1..k+d],

com d escolhido de tal modo que b[k+1] fique emparelhado com a última ocorrência da letra b[k+1] em a.

No exemplo abaixo, marcamos com | as posições que fazem o papel de k+d. No caso em que há casamento, a marca | foi trocada por ^.

X

C

B

A

B

X

C

B

A

A

X

B

C

B

A

B

X

|

|

|

|

^

|

B

C

B

A

B

C

B

A

B

C

B

A

B

C

B

A

B

C

B

A

B

C

B

A

Para implementar a ideia, basta fazer um pré-processamento da palavra a que determine, para cada letra l do alfabeto, a posição da última ocorrência de l em a. Esta última posição será denotada por ult[l].  Supondo que o alfabeto é o conjunto de todos os 256 caracteres, teremos

 

l	... > ? @ A B C D E F ...
ult[l]	... 0 0 0 4 3 2 0 0 0 ...

1	2	3	4
B	C	B	A

Segue o código do primeiro algoritmo de Boyer e Moore. O primeiro processo iterativo trata do pré-processamento da palavra e o segundo cuida de contar as ocorrêcias da palavra no texto.

// Recebe vetores a[1..m] e b[1..n] de caracteres,
// com m >= 1 e n >= 0, e devolve
// o número de ocorrências de a em b.

int 
boyermoore1 (unsigned char a[], int m,
             unsigned char b[], int n) 
{
   int ult[256];
   int i, j, k, occors;

   // pré-processamento da palavra a
   for (i = 0; i < 256; ++i)  ult[i] = 0;
   for (i = 1; i <=  m; ++i)  ult[a[i]] = i;

   // busca da palavra a no texto b
   occors = 0;
   k = m;
   while (k <= n) {
      i = m, j = k;
      while (i >= 1 && a[i] == b[j]) 
         --i, --j;   
      if (i < 1) ++occors;
      if (k == n) break;
      k += m - ult[b[k+1]] + 1;
   }
   return occors;
}

Exercícios

Segundo algoritmo de Boyer-Moore

O segundo algoritmo de Boyer-Moore, ao contrário do primeiro, não precisa conhecer o alfabeto de antemão. Em compensação, precisa comparar a palavra com o texto da direita para a esquerda: primeiro a[m] com b[k], depois a[m-1] com b[k-1], e assim por diante.

Suponha que já descobrimos que a[h..m] casa com um sufixo de b[1..k].  Suponha também, a título de exemplo, que a[h..m] não casa

com  a[h-1..m-1],  nem com  a[h-2..m-2]  e nem com  a[h-3..m-3].

É fácil deduzir então, sem fazer quaisquer comparações adicionais entre a e b, que a[1..m] não casa com o sufixo apropriado

de b[1..k+1],  nem de b[1..k+2],  nem de b[1..k+3].

Portanto, só precisamos verificar o sufixo de b[1..k+4].  Em particular, será preciso verificar se a[h-4..m-4] casa com b[k-m+h..k], e isto é o mesmo que verificar se a[h-4..m-4] casa com a[h..m].

Suponha, para completar o exemplo, que a[1..m] de fato casa com um sufixo de b[1..k+4].  Se h-4 ≥ 1 então a[h..m] casa com um sufixo de a[1..m-4].

k

-

-

-

-

-

-

C

B

A

*

C

B

A

-

-

-

-

-

1

h

m

&

C

B

A

*

C

B

A

&

C

B

A

*

C

B

A

Por outro lado, se h-4 < 1 então a[1..m-4] casa com um sufixo de a[h..m].

k

-

-

-

-

C

B

A

*

C

B

A

-

-

-

-

-

-

-

1

h

m

B

A

*

C

B

A

B

A

*

C

B

A

Este exemplo sugere que a implementação da ideia deve começar com um pré-processamento da palavra a:  para cada h em 1..m, calcule o maior k em 1..m-1 tal que

• a[h..m] casa com um sufixo de a[1..k]   ou
• a[1..k] casa com um sufixo de a[h..m].

Na falta de um termo melhor, diremos que esse valor máximo de k é o alcance de h.   Eis alguns exemplos da função alcance:

1	2	3	4	5	6		h		6 5 4 3 2 1
C	A	A	B	A	A		alcance[h]		5 3 0 0 0 0

1	2	3	4	5	6	7	8		h		8 7 6 5 4 3 2 1
B	A	-	B	A	*	B	A		alcance[h]		5 5 2 2 2 2 2 2

1	2	3	4	5	6	7	8	9	10	11		h		11 10 9 8 7 6 5 4 3 2 1
B	A	-	B	A	*	B	A	*	B	A		alcance[h]		8  8 8 8 8 2 2 2 2 2 2

Podemos examinar agora o código do segundo algoritmo de Boyer-Moore:

// Recebe uma palavra a[1..m] com 1 <= m <= MAXm e
// um texto b[1..n] e devolve o número de ocorrências
// de a em b.

int 
boyermoore2 (unsigned char a[], int m,
             unsigned char b[], int n) 
{
   int alcance[MAXm];
   int occors, h, k, i, j, k;

   // pré-processamento da palavra a
   k = m-1;
   i = m, j = k;
   while (i >= h && j >= 1)
      if (a[i] == a[j]) --i, --j;
      else i = m, j = --k; 
   alcance[h] = k;

   // busca da palavra a no texto b
   occors = 0;
   k = m;
   while (k <= n) {
      i = m, j = k;
      while (i >= 1 && a[i] == b[j]) 
         --i, --j;   
      if (i < 1) ++occors;
      if (i == m) k += 1;
      else k += m - alcance[i+1];
   }
   return occors;
}  

Exercícios

Terceiro algoritmo de Boyer-Moore

O terceiro algoritmo de Boyer-Moore é uma fusão dos dois anteriores: a cada passo, o algoritmo escolhe o maior dos deslocamentos ditados pelas tabelas ult e alcance.   [Este é o algoritmo de Boyer-Moore propriamente dito. A distinção que fizemos acima entre primeiro e segundo algoritmos é apenas didática.]

O algoritmo consome mn unidades de tempo no pior caso. Mas o pior caso é bem mais raro que o do algoritmo trivial. No caso médio, o terceiro algoritmo de Boyer-Moore consome tempo proporcional a n.  (Ou seja, em média, cada elemento de b é comparado com um número de elementos de a que não depende do valor de m.)

A definição da tabela alcance pode ser aperfeiçoada de tal maneira que o terceiro algoritmo consuma apenas m²+6n unidades de tempo, mesmo no pior caso.

Exercícios