Quase diariamente precisamos encontrar as ocorrências de alguma palavra em algum texto. A palavra é tipicamente curta e o texto é tipicamente muito longo. O texto pode pertencer a alguma língua natural, a uma linguagem de programação, a um código genético, etc. Os exemplos são muitos. Esta página discute um bom algoritmo para o problema.
A página é inspirada nas seções 1 e 3, capítulo 32, de CLRS.
Dizemos que um vetor P[1 .. m] ocorre em um vetor T[1 .. n] se o primeiro vetor é um segmento do segundo, ou seja, se existe um índice k tal que
P[1 .. m] = T[k−m+1 .. k] .
Esta expressão deve ser entendida assim: P[1] = T[k−m+1], P[2] = T[k−m+2], etc., P[m−1] = T[k−1] e P[m] = T[k]. É claro que um tal k satisfaz as desigualdades m ≤ k ≤ n. Nosso missão: encontrar todas as ocorrências de P[1 .. m] em T[1 .. n].
No contexto deste problema, dizemos que P é uma padrão (= pattern) ou palavra e que T é um texto. Usualmente, os elementos de P e de T são caracteres; mas podem ser números ou quaisquer outros objetos.
Se P[1 .. m] = T[k−m+1 .. k], dizemos que P[1 .. m] é um sufixo de T[1 .. k]. Em termos desse conceito, nosso 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].
Exemplo A: 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 de m até n |
| 2 .ooo se É-Sufixo (P, m, T, k) = 1 |
| 3 .oooooo imprima k |
O subalgoritmo É-Sufixo devolve 1 se P[1 .. m] é sufixo de T[1 .. k] e devolve 0 em caso contrário. O subalgoritmo 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] |
| 3 .ooo l := l − 1 |
| 4 . se l ≥ 1 |
| 5 .ooo devolva 0 |
| 6 . senão devolva 1 |
No pior caso, É-Sufixo consome Ο(m) unidades de tempo. (O consumo de tempo não depende de k.) Portanto, no pior caso, o algoritmo Inocente com argumentos (P, m, T, n) consome
Ο(n m)
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.
enquanto P[l] = T[k−m+l] e l ≥ 1?
Nosso problema consiste na repetição do subproblema de 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 corresponde ao prefixo vazio.
Exemplo B: A parte superior da figura abaixo é 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 a seguir 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 calcula o maior prefixo de P[1 .. m] que é sufixo de T[1 .. k]. (O algoritmo não será usado diretamente em nossa solução final do problema de busca, mas é útil para tornar as ideias mais claras.) O algoritmo supõe que 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 |
| 2 .ooo se É-Sufixo (P, i, T, k) = 1 |
| 3 .oooooo devolva i e pare |
| 4 . devolva 0 |
Observe que É-Sufixo (P, 0, T, k) = 1 e portanto o processo iterativo nas linhas 2 a 3 cessa depois de no máximo m+1 repetições. O consumo de tempo do algoritmo está em Ο(m²). Esse algoritmo poderia ser usado da seguinte maneira para resolver nosso problema de busca:
| 1 . para k crescendo de m até n |
| 2 .ooo q := Maior-Prefixo-Que-É-Sufixo (P, m, T, k) |
| 3 .ooo se q = m |
| 4 .oooooo 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 solução eficiente 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.) O alfabeto doproblema será denotado por A. 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 a
na posição q+1.)
Diremos que a tabela D assim definida é o autômato
(= automaton)
da palavra P.
Exemplo C: 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 |
| 3 .ooo a := T[k] |
| 4 .ooo q := D[q, a] |
| 5 .ooo se q = m |
| 6 .oooooo 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!)
Correção do algoritmo. 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 vale 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.
Desempenho. É 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.
para k crescendo de 1 até n−m+1?
para k de m até n?
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 . para q crescendo de 0 até m |
| 2 .oo para cada a em A |
| 3 .oooo D[q, a] := Maior-Pref-Que-É-Suf (P, m, P, q, a) |
| 4 . 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 .oo devolva q+1 e pare |
| 3 . para i decrescendo de q até 1 |
| 4 .oo se P[i] = a e É-Sufixo (P, i−1, P, q) = 1 |
| 5 .ooooo devolva i e pare |
| 6 . devolva 0 |
Cada execução de É-Sufixo na linha 4 de Maior-Pref-Que-É-Suf consome Ο(i) unidades de tempo. No pior caso, a linha 4 é executada para i = q, q−1, … , 1. Portanto, o consumo de tempo total de Maior-Pref-Que-É-Suf está em Ο(q+(q−1)+ … +1), ou seja, em Ο(q²).
Agora considere o consumo de Pré-Processamento. Como q cresce de 0 até m e 0²+1²+ … +m² = (2m³+3m²+m)/6, podemos dizer que, no pior caso, Pré-Processamento consome Ο(m³⎮A⎮) unidades de tempo. (Mas existe uma maneira sofisticada de calcular D que consome apenas Ο(m⎮A⎮) unidades de tempo. Veja exercício CLRS 32.4-6.)
compactado algoritmo Busca-de-Palavra-em-Texto. Sua versão deve fazer o pré-processamento da palavra e em seguida encontrar as ocorrências da palavra no texto. Seu algoritmo não deve invocar nenhum outro. Procure escrever código simples e elegante.
A solução completa do problema da busca de palavra em texto, que consiste em Pré-Processamento seguido de Busca-de-Palavra-em-Texto, consome
Ο(m³⎮A⎮ + n)
unidades de tempo. Tipicamente, a palavra e o alfabeto são muito menores que o texto, ou seja, m e ⎮A⎮ são muito menores que n. Assim, faz sentido restringir o problema às instâncias em que m³⎮A⎮ = Ο(n). Nesse caso, o consumo de tempo total se reduz a Ο(n) e o algoritmo pode ser considerado linear.