Busca de palavras em um texto

É como procurar agulha num palheiro.
provérbio

Quantas vezes a palavra algoritmo aparece neste capítulo?

O seguinte problema, conhecido como substring searching ou string matching, está embutido em uma infinidade de importantes problemas práticos:

Encontrar as ocorrências de um dado vetor  a  em um dado vetor  b.

Suporemos que os elementos dos vetores são bytes (embora o problema faça sentido para vetores de qualquer outro tipo). Mas é melhor não supor que os vetores são strings, pois não vamos exigir que terminem com um byte nulo.

unsigned char *a;
unsigned char *b;

Em muitas aplicações, os elementos de ab representam caracteres ASCII (portanto, o primeiro bit de cada byte vale 0 e assim cada byte pertence ao conjunto 0..127).  Em outras aplicações, ab representam sequências de caracteres Unicode em código UTF-8 (portanto, cada caractere é representado por 1, 2, 3 ou 4 bytes consecutivos e cada byte pertence ao conjunto 0..247).  Em geral, entretanto, não há restrição sobre os valores dos bytes: cada um pertence ao conjunto 0..255.

Diremos que o vetor a é uma palavra (mesmo que não represente uma palavra em português ou inglês no sentido usual) e o vetor b é um texto.  O problema consiste, então, em encontrar as ocorrências de uma palavra em um texto.

A seguinte figura sugere uma aplicação ao processamento de código genético.  Nesse caso, os elementos dos vetores são as letras A, C, GT.  A figura destaca uma ocorrência da palavra TACTA no texto GTAG...TAG:

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
T A C T A

Convenções e terminologia

Já tomamos a decisão de tratar apenas de vetores de bytes. Tomaremos outra decisão de projeto: a palavra e o texto serão indexados a partir de 1 (e não a partir de 0) a fim de simplificar ligeiramente as expressões envolvendo segmentos desses vetores.  Além disso, adotaremos a seguinte formulação simplificada do problema:

Encontrar o número de ocorrências de uma palavra a[1..m] em um texto b[1..n].

Se m > n, por exemplo, o número de ocorrências de a em b é zero. Para garantir que o número de ocorrências seja finito, suporemos sempre que m ≥ 1.

Convém adotar a seguinte terminologia ao tratar do problema:

Nos exemplos a seguir, o sinal ↓ indica as posições  k  em que o vetor a (linha inferior) casa com um sufixo do vetor b[1..k] (linha superior):

U m   v e t o r   a   o c o r r e   e m   b   s e
o c o r r e   e  
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
3 1 4 1 5 9
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
T A C T A

Qualquer algoritmo para o problema envolve uma varredura (= scan) do texto.  Poderíamos varrer b da esquerda para a direita ou da direita para a esquerda ao procurar as ocorrências de a.  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 elemento-a-elemento de a[1..m] com um sufixo de b[1..k] poderia 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, a comparação elemento-a-elemento será sempre feita da direita para a esquerda: primeiro a[m] com b[k], depois a[m-1] com b[k-1], e assim por diante.

Exercícios 1

  1. Quantas vezes a palavra  AAA  ocorre no texto  AAAAA?
  2. Quais são os bytes que representam os caracteres  A, C, GT?
  3. Faça uma figura semelhante às exibidas acima para mostrar uma ocorrência do vetor  ação  no vetor  notação binária. (Note que cada pequena caixa representa um byte.)
  4. Discuta (vagamente, em termos gerais) a seguinte afirmação: qualquer algoritmo para a versão simplificada do problema pode ser modificado de modo a resolver a versão mais geral.

Algoritmo inocente

A seguinte função resolve o problema (da busca de uma palavra em um texto) da maneira mais óbvia e direta. Pacientemente, ela tenta casar a com b[1..m], depois com b[2..m+1], e assim por diante:

// 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 
inocente (unsigned char a[], int m,
          unsigned char b[], int n) 
{
   int ocorrs = 0;
   for (int k = m; k <= n; ++k) {
      // a[1..m] casa com b[k-m+1..k]?
      int i = m, j = k;
      while (i >= 1 && a[i] == b[j]) 
         --i, --j;   
      if (i < 1) ++ocorrs;
   }
   return ocorrs;
}

Podemos imaginar que, a cada iteração, a palavra a desliza para a direita ao longo do texto b, como no seguinte exemplo:

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
etc.

No pior caso, a função inocente compara cada elemento de a com cada elemento de b e portanto consome tempo proporcional a

m n .

Será possível resolver o problema sem comparar cada elemento de a com cada elemento de b?

Exercícios 2

  1. O algoritmo inocente funciona corretamente quando m > n?  Que acontece se tentarmos executar a função com argumento m igual a 0?
  2. Dê um exemplo em que o algoritmo inocente faz o maior número possível de comparações entre elementos de a e b. Qual é esse número exatamente?
  3. Solução do problema original.  Modifique a função inocente de modo que ela resolva a versão original do problema da busca de palavra em texto: para cada ocorrência de a em b, imprima o índice j tal que a[1..m] casa com b[j..m+j-1].
  4. Espaços consecutivos (preparação para Boyer-Moore).  Escreva uma função que receba um vetor de bytes b[1..n] e um inteiro m e devolva a posição da primeira ocorrência de m espaços (bytes 32) consecutivos em b.  (Você pode imaginar que os elementos de b representam caracteres ASCII, embora isso seja irrelevante.) Escreva a função mais eficiente que puder.

Primeiro algoritmo de Boyer-Moore

Um alfabeto de uma instância do problema é qualquer conjunto de bytes que contém todos os elementos dos vetores abÉ claro que toda instância admite o alfabeto 0..255. Mas algumas instâncias podem ter um alfabeto menor, como 0..127 no caso de caracteres ASCII, ou  ACGT  no caso das aplicações à genética.

R.S. Boyer e J.S. Moore tiveram a engenhosa ideia de usar um vetor indexado pelo alfabeto para acelerar o algoritmo inocente.  Suponha que já comparamos a[1..m] com um sufixo de b[1..k]. Agora, podemos saltar algumas iterações do algoritmo inocente e passar a comparar a[1..m] com um sufixo de

b[1..k+d]

para algum d positivo.  O valor de d é escolhido de tal modo que a posição k+1 de b fique emparelhada com a última ocorrência (contando da esquerda para a direita) do byte b[k+1] em a[1..m].   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  e lembrar, para cada letra f do alfabeto, ⚠ a posição da última ocorrência (contando da esquerda para direita) de f em a.  Essa posição será denotada por ult[f].  Se o alfabeto do exemplo anterior é o conjunto dos 128 caracteres ASCII, teremos

    f     ... = > ? @ A B C D E F G ...
ult[f]    ... 0 0 0 0 4 3 2 0 0 0 0 ...
1 2 3 4
B C B A

Segue uma implementação do algoritmo.  O primeiro processo iterativo faz o pré-processamento da palavra e o segundo cuida de contar as ocorrências da palavra no texto.

// Recebe vetores a[1..m] e b[1..n] de
// bytes, 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]; // o alfabeto é 0..255

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

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

Esse é o primeiro algoritmo de Boyer-Moore.

Exercícios 3

  1. Responda rápido: o seguinte fragmento de código funciona corretamente?
    unsigned char f;
    for (f = 0; f < 256; ++f) ult[f] = 0;
    
  2. ⚠ Que acontece na linha k += m - ult[b[k+1]] + 1 se o byte b[k+1] não ocorre em a[1..m]?  Que acontece se b[k+1] for igual a a[m]?
  3. Prove que a fase de pré-processamento na função boyermoore1 preenche corretamente a tabela ult.
  4. A seguinte variante do código da busca da palavra a no texto b está correta?
    ocorrs = 0; k = m;
    while (k <= n) {
       i = m, j = k;
       while (i >= 1 && a[i] == b[j]) --i, --j;   
       if (i < 1) ++ocorrs;
       kk = k+1;                                 
       while (kk <= n && ult[b[kk]] == 0) ++kk;  
       if (kk > n) break;                       
       k += m - ult[b[kk]] + kk - k;
    }
    return ocorrs;
    
  5. ⚠ Analise a seguinte variante da função boyermoore1. Mostre que ela é tão boa quanto a versão acima.
    int ult[256];
    for (int i = 0; i < 256; ++i) ult[i] = 0;
    for (int i = 1; i <   m; ++i) ult[a[i]] = i;
    int ocorrs = 0, k = m;
    while (k <= n) {
       int i = m, j = k;
       while (i >= 1 && a[i] == b[j]) 
          --i, --j;   
       if (i < 1) ++ocorrs;
       k += m - ult[b[k]];
    }
    return ocorrs;
    

Segundo algoritmo de Boyer-Moore

O segundo algoritmo de Boyer-Moore, ao contrário do primeiro, não precisa conhecer o alfabeto explicitamente. Em compensação, é essencial que compare 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.

Considere o seguinte exemplo. Suponha que já descobrimos que a[h..m] casa com um sufixo de b[1..k].  Suponha também ⚠ que a[h..m] não casa

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

(Note que estamos comparando a[h..m] com segmentos do próprio vetor a[1..m]!)

  1   h   m
  & C B A * C B A
          & C B A * C B A

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

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

Portanto, no próximo passo, devemos tentar casar a[1..m] com um um sufixo de b[1..k+4].  Em particular, devemos tentar casar a[h-4..m-4] com b[k-m+h..k]. Mas isso é o mesmo que verificar se a[h-4..m-4] casa com a[h..m], uma vez que, por hipótese, b[k-m+h..k] casa com a[h..m].

Para completar o exemplo acima, suponha 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

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

Na falta de um termo melhor, diremos que esse valor máximo de k é o alcance de h.   Eis alguns exemplos de palavras com a correspondente 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

Depois dessa preparação, podemos examinar a implementação do segundo algoritmo de Boyer-Moore:

// Recebe uma palavra a[1..m] com 1 <= m e
// um texto b[1..n]. 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 = malloc ((m+1) * sizeof (int));

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

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

Segue uma variante mais compacta e eficiente do pré-processamento:

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

Outra variante:

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

Ou ainda:

// pré-processamento da palavra a
k = m-1;
r = 0;
for (h = m; h >= 1; --h) {
   while (m-r >= h && k-r >= 1)
      if (a[m-r] == a[k-r]) ++r;
      else r = 0, k--;
   alcance[h] = k;
}

Exercícios 4

  1. Mostre que a fase de pré-processamento na função boyermoore2 preenche corretamente a tabela alcance.   Mostre que essa fase consome m2 unidades de tempo no pior caso.
  2. Use a função boyermoore2 para contar o número de ocorrências da palavra  ABCBCCABC  no texto  ABCCBAABCABCBCCABC.

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 dois deslocamentos: aquele ditado pela tabela ult e aquele dado pela tabela alcance.   (Esse é o algoritmo de Boyer-Moore propriamente dito. A distinção que fizemos acima entre primeiro e segundo algoritmos é apenas didática.)

O pré-processamento consome m2 unidades de tempo. Infelizmente, a fase de busca consome m n unidades de tempo no pior caso, tal como no algoritmo inocente.

Mas o pior caso é bem mais raro que o do algoritmo inocente.  Assim, no caso médio, típico de aplicações práticas, o terceiro algoritmo de Boyer-Moore consome tempo proporcional a  n  e independente de m.  Ou seja, em média, cada elemento do texto é comparado com apenas alguns poucos elemento da palavra, qualquer que seja o comprimento da palavra.

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

Exercícios 5

  1. Implemente o terceiro algoritmo de Boyer-Moore.
  2. Testes.  Compare, experimentalmente, o desempenho do terceiro algoritmo de Boyer-Moore com o do algoritmo inocente.  Invente pares palavra/texto interessantes para fazer os testes.  Você pode usar o arquivo br-utf8.txt da Lista de todas as palavras do português brasileiro para fazer testes. Também pode usar o livro Quincas Borba de Machado de Assis. Também pode usar o A Tale of Two Cities de Charles Dickens.
  3. Desafio.  Investigue as alterações que devem ser feitas na definição da tabela alcance para que o terceiro algoritmo de Boyer-Moore faça no máximo 6n comparações entre elementos da palavra e do texto na fase de busca.
  4. Escreva uma função que receba vetores b[1..n], a[1..m] e x[1..p] e substitua por x cada ocorrência de a em b.
  5. Busca com curinga.  Suponha que o caractere # tem um significado especial dentro da palavra: ele representa 0 ou mais ocorrências de qualquer outro caractere (ou seja, # é um curinga ou wildcard). Exemplos:
    • a palavra A#B#C casa com qualquer segmento do texto que comece com A, termine com C e tenha um B em algum lugar entre A e C;
    • a palavra  x#[#]#=#;  casa com  x[i] = x[i-1] + 1;  e também com  x2[i]=x[i-1]+1; y= z;.

    Escreva uma função que busque uma palavra em um texto interpretando o curinga # como sugerido acima.

  6. ⚠ Familiarize-se com o poderoso utilitário grep, que faz busca com caracteres curinga, expressões regulares, e muito mais.

Perguntas e respostas