Projeto de Algoritmos  |  Linguagem C  |  Índice  |  English

Busca de palavras em um texto

Procurar uma palavra num texto é uma atividade corriqueira. No contexto computacional, esse problema é conhecido como substring searching ou string matching e pode ser formulado assim:

Encontrar todas 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 não vamos supor que os vetores são strings, ou seja, que terminam com um byte nulo.

Em muitas aplicações (e nos exemplos abaixo), os elementos de a e b representam caracteres ASCII e assim cada byte pertence ao conjunto 0 . . 127.  Em outras aplicações, os elementos de a e b representam caracteres Unicode em código UTF-8 (e portanto cada caractere pode corresponder a mais de um byte).  Em geral, entretanto, não há restrições sobre os elementos de a e b: cada elemento é um byte com valor entre 0 e 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.

Procurar por um determinado vírus de software num arquivo digital, por exemplo, é, essencialmente, um problema de busca de uma palavra (o vírus) num texto (o arquivo).  No caso do processamento de código genético, por exemplo, os elementos dos vetores são as letras A, C, G, e T.  A figura destaca uma ocorrência da palavra TACTA no texto GTAG…TAG:

Terminologia e decisões de projeto

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 que especificam segmentos desses vetores.  Finalmente, vamos nos restringir à versão simplificada do problema que pede apenas um número como resposta:

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

Se m > n, 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:

• 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 terminal do vetor, ou seja, qualquer segmento da forma  b[j . . k];
• a expressão a[1 . . m] casa com um sufixo de b[1 . . k] será usada como abreviatura de a[1 . . m] casa com b[k−m+1 . . k];
• um vetor  a[1 . . m] ocorre em b[1 . . n]  se existe k tal que a[1 . . m] casa com um sufixo de b[1 . . k].

Note que duas ocorrências de a em b podem se sobrepor. Por exemplo, as duas ocorrências de BABA em XBABABAX se sobrepõem.

Exemplos.  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):

Direções de varredura.  Qualquer algoritmo que procure uma palavra num texto deverá executar uma varredura (= scan) do texto.  Para procurar as ocorrências de uma palavra a num texto b, poderíamos varrer 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.

Para um k fixo, 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. 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

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[1..m] com b[1..m], depois com b[2..m+1], e assim por diante:

typedef unsigned char byte;

// 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 (byte a[], int m, byte 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 da esquerda para a direita ao longo do texto b, como no seguinte exemplo:

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

Primeiro algoritmo de Boyer-Moore

Um alfabeto de uma instância do nosso problema é qualquer conjunto de bytes que contém todos os elementos dos vetores a e b.  Dadas nossas convenções, 0..255 é um alfabeto de qualquer instância do problema. Mas algumas instâncias podem ter um alfabeto menor, como 0..127 no caso de caracteres ASCII, ou como  65 67 71 84  no caso das aplicações à genética.

R.S. Boyer e J.S. Moore tiveram a engenhosa ideia de usar uma tabela auxiliar, indexada 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 um certo 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 substituída por ↓ :

Para implementar a ideia, basta pré-processar a palavra  a  de modo a 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 ...

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.

typedef unsigned char byte;

// 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 (byte a[], int m,
             byte 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) k += 1;
      else k += m - ult[b[k+1]] + 1;
   }
   return ocorrs;
}

Esse é o primeiro algoritmo de Boyer-Moore.

Exercícios 3

Segundo algoritmo de Boyer-Moore

O segundo algoritmo de Boyer-Moore, ao contrário do primeiro, não precisa conhecer o alfabeto de a e b explicitamente. Ademais, o segundo algoritmo 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.

Imagine que a palavra a[1..m] é  &CBA*CBA .  Suponha que acabamos de descobrir que a[1..m] não casa com um sufixo de b[1..k] e estamos nos preparando para verificar se a[1..m] casa com um sufixo de b[1..k+1].  Agora compare a palavra com ela mesma e observe 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].

No nosso exemplo, m vale 8, h vale 6 e  CBA  não casa com  *CB  nem com  A*C  nem com  BA*:

É fácil deduzir daí, 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]

(faça uma figura!).  Portanto, o próximo passo deve tentar casar a[1..m] com um sufixo de b[1..k+4].  Como parte dessa tentativa, devemos comparar 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] é igual a a[h..m].

Para completar a ilustração, 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].

Por outro lado, se h-4 < 1 então a[1..m-4] casa com um sufixo de a[h..m]. Para ilustrar essa alternativa, suponha que a palavra é  BA*CBA :

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  ⚠

• 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 pulo, ou jump, de h.  Eis alguns exemplos de palavras com a correspondente tabela jump:

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

typedef unsigned char byte;

// 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 (byte a[], int m,
             byte b[], int n) 
{
   int *jump = malloc ((m+1) * sizeof (int));
   // usaremos jump[1..m]

   // 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;
      jump[h--] = k;
   }
   while (h >= 1)
      jump[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 - jump[i+1];
   }
   return ocorrs;
}  

Segue uma versão 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;
   jump[h--] = k;
}

Exercícios 4

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 jump.  (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 m² 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 é tão raro que 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 jump 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