Esta página trata de encontrar as ocorrências de uma palavra (tipicamente curta) em um texto (tipicamente longo). A página é inspirada nas seções 1 e 3, capítulo 32, de CLRS. Veja também as seções 6.6 e 6.7 de KT e o verbete String searching algorithm na Wikipedia.
Dizemos que um vetor P[1..m] ocorre em um vetor T[1..n] se existe un índice k tal que P[1..m] = T[k−m+1 .. k], isto é, se P[1] = T[k−m+1], etc., P[m−1] = T[k−1] e P[m] = T[k]. É claro que um tal k satisfaz as desigualdades m ≤ k ≤ n. (Não confunda ocorrência com subsequência.) Nosso problema:
Encontrar todas as ocorrências de P[1..m] em T[1..n].
No contexto deste problema, dizemos que P é uma padrão ou palavra e que T é um texto. Usualmente, os elementos de P e de T são caracteres.
Dizemos que P[1..m] é um sufixo de T[1..k] se P[1..m] = T[k−m+1 .. k]. Em termos desse conceito, o problema pode ser formulado assim:
Problema da busca de palavra em texto: Dados vetores P[1..m] e T[1..n], encontrar todos os valores de k para os quais P[1..m] é sufixo de T[1..k].
Por exemplo, se P = (f g f g) e T = (e e f f g f g f g e e) então a solução do problema é a lista de índices (7, 9). A figura mostra as duas ocorrências de P em T:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| e | e | f | f | g | f | g | f | g | e | e |
| f | g | f | g | |||||||
| f | g | f | g |
É muito fácil escrever um algoritmo simples e inocente para o problema:
| Inocente (P, m, T, n) |
| 1 _ para k crescendo de m até n faça |
| 2 ____ se É-Sufixo (P, m, T, k) = 1 |
| 3 _______ então imprima k |
O subalgoritmo É-Sufixo devolve 1 se P[1..m] é sufixo de T[1..k] e devolve 0 em caso contrário. O algoritmo supõe que k ≥ m ≥ 0:
| É-Sufixo (P, m, T, k) |
| 1 _ l ← m |
| 2 _ enquanto l ≥ 1 e P[l] = T[k−m+l] faça |
| 3 ____ l ← l − 1 |
| 4 _ se l ≥ 1 |
| 5 ____ então devolva 0 |
| 6 ____ senão devolva 1 |
O consumo de tempo de É-Sufixo não depende de k. No pior caso, É-Sufixo consome Ο(m) unidades de tempo. Portanto, no pior caso, o algoritmo Inocente com argumentos (P, m, T, n) consome
Ο(nm)
unidades de tempo. Como o tamanho de uma instância do problema é n+m, o algoritmo deve ser considerado quadrático.
Gostaríamos de ter um algoritmo que consuma apenas Ο(n) unidades de tempo. Como veremos adiante, um tal algoritmo pode ser construído desde que tenhamos a oportunidade de submeter a palavra P[1..m] a um pré-processamento apropriado.
Nosso problema consiste na repetição do seguinte subproblema: decidir se P[1..m] é sufixo de T[1..k]. No que segue, vamos generalizar esse subproblema e procurar pelo
maior prefixo de P[1..m] que é sufixo de T[1..k].
O conceito de prefixo é simples: qualquer vetor P[1..i] com i ≤ m é um prefixo de P[1..m]. O caso i = 0 descreve um prefixo vazio.
Exemplo 1: A parte superior da figura é uma palavra P[1..7]. A parte inferior é um texto T[1..11]. Na última linha, em correspondência com cada posição k do texto, estão os valores de i para os quais P[1..i] é o maior prefixo de P que é sufixo de T[1..k].
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| e | f | e | f | e | g | e |
| e | f | e | f | e | f | e | g | e | f | e |
| 1 | 2 | 3 | 4 | 5 | 4 | 5 | 6 | 7 | 2 | 3 |
A figura abaixo mostra em mais detalhe que P[1..2] é o maior prefixo de P que é sufixo de T[1..10]:
| e | f | e | f | e | f | e | g | e | f | |||||
| e | f | e | f | e | g | e |
O seguinte algoritmo não será usado diretamente em nossa solução final, mas é útil para tornar as ideias mais claras. O algoritmo calcula o maior prefixo de P[1..m] que é sufixo de T[1..k]. O algoritmo supõe k ≥ m ≥ 0 e devolve o índice i que define o maior prefixo:
| Maior-Prefixo-Que-É-Sufixo (P, m, T, k) |
| 1 _ para i decrescendo de m até 1 faça |
| 2 ____ se É-Sufixo (P, i, T, k) = 1 |
| 3 _______ então devolva i |
| 4 _ devolva 0 |
Observe que É-Sufixo(P,0,T,k) = 1 e portanto o processo iterativo nas linhas 2 a 3 para depois de no máximo m+1 repetições. O consumo de tempo do algoritmo está em Ο(m2). Esse algoritmo poderia ser usado assim para resolver nosso problema de busca:
| 1 _ para k crescendo de m até n faça |
| 2 ____ q ← Maior-Prefixo-Que-É-Sufixo (P, m, T, k) |
| 3 ____ se q = m |
| 4 _______ então imprima k |
Embora correto, o código é inútil pois consome mais tempo que o algoritmo Inocente. Nas próximas seções, usaremos esse código como base para uma boa solução do problema de busca.
Suponha que conhecemos o alfabeto do problema, isto é, o conjunto de todos os possíveis valores dos elementos da palavra P[1..m] e do texto T[1..n]. (Por exemplo, o alfabeto pode ser o conjunto dos 256 caracteres da tabela ASCII.) Para cada a em A e cada q em 0..m, seja D[q, a]
| o tamanho do maior prefixo de P que é sufixo de P[1..q]a . | (*) |
Em outras palavras, D[q, a] é o maior i tal que P[1..i] é sufixo de P[1..q]a. (A expressão "P[1..q] a" representa o vetor P[1..q] seguido de um elemento de valor a na posição q+1.) Diremos que a tabela D assim definida é o autômato da palavra P.
Exemplo 2: Tome a palavra P = e f e f e g e e suponha que o alfabeto é {e,f,g}. A figura abaixo mostra o autômato D e explica o valor do elemento D[5,f] da tabela.
|
|
O seguinte algoritmo usa o autômato D para resolver o problema da busca. Ele recebe um texto T, o alfabeto A, e o autômato D da palavra P e imprime todos os valores de k para os quais P é sufixo de T[1..k]:
| Busca-De-Palavra-Em-Texto (D, m, A, T, n) |
| 1 _ q ← 0 |
| 2 _ para k crescendo de 1 até n faça |
| 3 ____ a ← T[k] |
| 4 ____ q ← D[q, a] |
| 5 ____ se q = m |
| 6 _______ então imprima k |
(Compare o código com o rascunho que fizemos acima.) Observe que algoritmo nunca compara explicitamente um elemento de P com um elemento de T!)
No início de cada iteração, imediatamente antes que k seja comprado com n na linha 2, vale o seguinte invariante:
| P[1..q] é o maior prefixo de P que é sufixo de T[1..k−1]. | (**) |
Esta propriedade vale trivialmente no início da primeira iteração. Suponha agora que ela no início de alguma iteração que não a última; vamos mostrar que ela continua valendo no início da próxima iteração.
Seja q′ o valor de D[q,a]. Pela definição (*) do autômato, P[1..q′] é sufixo de P[1..q]a. Em virtude de (**), P[1..q]a é sufixo de T[1..k]. Portanto, P[1..q′] também é sufixo de T[1..k]. Resta mostrar que q′ é o maior índice com essa propriedade.
Seja P[1..q″] um sufixo qualquer de T[1..k]; vamos mostrar que q″ ≤ q′. É claro que P[1..q″] = a e P[1..q″−1] é sufixo de T[1..k−1]. Mas T[1..k−1] = P[1..q] e portanto P[1..q″−1] é sufixo de P[1..q]. Logo, P[1..q″] é sufixo de P[1..q]a. A definição (*) da tabela D garante agora que q″ ≤ D[q,a] e portanto q″ ≤ q′, como queríamos mostrar.
É evidente que o algoritmo Busca-De-Palavra-Em-Texto consome meras Ο(n) unidades de tempo. Isso acontece tanto no pior quanto no melhor caso. Podemos dizer portanto, que o algoritmo consome Θ(n) unidades de tempo.
Resta apenas mostrar como a tabela D pode ser construída. Embora não seja muito eficiente, o seguinte algoritmo faz o serviço de maneira correta:
| Pré-Processamento (P, m, A) |
| 1 o para q crescendo de 0 até m faça |
| 2 oooo para cada a em A faça |
| 3 ooooooo D[q, a] ← Maior-Pref-Que-É-Suf (P, m, P, q, a) |
| 4 o devolva D |
O subalgoritmo Maior-Pref-Que-É-Suf é semelhante ao Maior-Prefixo-Que-É-Sufixo discutido acima. Ele recebe um elemento a do alfabeto e devolve o índice i que define o maior prefixo P[1..i] de P[1..q]a:
| Maior-Pref-Que-É-Suf (P, m, P, q, a) |
| 1 _ se q < m e P[q+1] = a |
| 2 ____ então devolva q+1 |
| 3 ____ senão para i decrescendo de q até 1 faça |
| 4 ____ senão ___ se P[i] = a e É-Sufixo (P, i−1, P, q) = 1 |
| 5 ____ senão ______ então devolva i |
| 6 ____ senão devolva 0 |
No pior caso, a linha 4 de Maior-Pref-Que-É-Suf é repetida q vezes e o consumo de tempo de todas essas repetições é Ο((q−1) + (q−2) + …) unidades de tempo. Portanto, o consumo de tempo total de Maior-Pref-Que-É-Suf está em Ο(q2).
Agora considere o consumo de Pré-Processamento. Como 02 + 12 + …+ m2 = m3, podemos dizer que, no pior caso, Pré-Processamento consome
Ο(m3|A|)
unidades de tempo. (Mas existe uma maneira sofisticada de calcular D em apenas Ο(m|A|) unidades de tempo. Veja exercício CLRS 32.4-6.)
Conclusão: a solução completa do problema consome Ο(m3|A| + n) unidades de tempo.