(Veja o verbete String searching algorithm na Wikipedia.)
Suponha dados os vetores a[1..m] e b[1..n]. Dizemos que a ocorre em b se existe k no intervalo m..n tal que
a[1..m] == b[k-m+1..k].
Adote a expressão "a == b[..k]" como abreviatura para "a[1..m] == b[k-m+1..k]". Podemos dizer então que a ocorre em b se a == b[..k] para algum k. [Cuidado! a expressão a==b[..k] não significa a==b[1..k].] Se a == b[..k], diremos também que o vetor a casa com b[k-m+1..k].
Poderíamos igualmente bem dizer que a ocorre em b se a==b[h..] para algum h, depois de definir a expressão "a==b[h..]" da maneira óbvia.
Exemplos: A figura especifica alguns pares a, b. O sinal ^ marca o índice k tal que a casa com b[..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 |
| ^ | ^ |
Esta página pretende estudar 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.
Em termos mais informais, o problema consiste em encontrar o número de ocorrências de uma palavra a em um texto b.
Se m > n então o número de ocorrências é zero. Para garantir que o número de ocorrências é finito, convém supor 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 a com b[2..m+1], etc.
A comparação de a com algum segmento b[k-m+1..k] de b também pode ser feita em duas direções: 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], etc.
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.
// 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, ocorre = 0;
for (k = m; k <= n; ++k) {
for (i = m, j = k; i >= 1; --i, --j)
if (a[i] != b[j]) break;
if (i < 1) ++ocorre;
}
return ocorre;
}
Quanto tempo a função consome? A função faz no máximo m·n comparações de um elemento de a com um elemento de b. Desafio: resolver o problema fazendo menos comparações entre a palavra e o texto.
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. Para fixar idéias, digamos que o alfabeto é o conjunto de todos os 256 caracteres. Neste caso, é possível fazer um algoritmo mais rápido que o trivial (R. S. Boyer e J. S. Moore, "A fast string searching algorithm", Communications of the ACM, 20, p.762, 1977).
A idéia do algoritmo é simples: Suponha que acabamos de comparar a com b[..k] (o resultado da comparação não importa). A próxima comparação não precisa acontecer necessariamente entre a e b[..k+1]: podemos passar a tratar imediatamente de
b[..k+d],
com d calculado de modo que b[k+1] fique emparelhado com a última ocorrência da letra b[k+1] em a.
Na figura abaixo, aplicamos o algoritmo a uma palavra a e um texto b. Assinalamos com ' as posições que fazem o papel de k+d. Nos casos em que há casamento, a marca ' foi trocada por ^.
| B | C | B | A | |||||||||||||
| X | C | B | A | B | X | C | B | A | A | X | B | C | B | A | B | X |
| ' | ' | ' | ' | ^ | ' |
Para implementar essa idéia, basta fazer um pré-processamento da palavra que determine, para cada letra l do alfabeto, a última ocorrência, digamos ult[l], de l em a. Para a palavra BCBA, teremos
| 1 | 2 | 3 | 4 |
| B | C | B | A |
| l | ... > ? @ A B C D E F ... |
| ult[l] | ... 0 0 0 4 3 2 0 0 0 ... |
Eis a função completa. Ela supõe que nosso alfabeto é o conjunto de todos os 256 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
boyermoore1 (unsigned char a[], int m, unsigned char b[], int n)
{
int ult[256];
int i, j, k, ocorre;
// 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
ocorre = 0;
k = m;
while (k <= n) {
for (i = m, j = k; i >= 1; --i, --j)
if (a[i] != b[j]) break;
if (i < 1) ++ocorre;
if (k+1 > n) break;
k += m - ult[b[k+1]] + 1;
}
return ocorre;
}
unsigned char i; for (i = 0; i < 256; ++i) ult[i] = 0;
while (k <= n) {
i = m, j = k;
while (i >= 1 && a[i] == b[j]) --i, --j;
if (i < 1) ++ocorre, ++k;
else k = max (j - ult[b[j]] + 1, k+1);
}
Ao contrário do primeiro algoritmo, o segundo não depende de conhecer o "alfabeto" de antemão. Por outro lado, neste segundo algoritmo é essencial fazer a comparação da 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, para um certo k, que a[h..m]==b[k-m+h..k]. Suponha agora que a[h..m] é diferente
de a[h-1..m-1], de a[h-2..m-2] e de a[h-3..m-3].
É fácil então deduzir, sem fazer quaisquer comparações adicionais entre a e b, que
a ≠ b[..k+1], a ≠ b[..k+2] e a ≠ b[..k+3].
Portanto, nossa próxima tentativa de casar a com b deve emparelhar b[k-m+h..k] com a última ocorrência de a[h..m] em a[..m-1].
Para implementar essa idéia, é preciso pré-processar a palavra e encontrar, para cada h, a última ocorrência do subpalavra a[h..m] em a[1..m-1]. Em outras palavras, trata-se de determinar o maior mm em 1..m-1 tal que
a[h..m] == a[..mm].
Na falta de um termo melhor, diremos que esse valor máximo de mm é o alcance de h.
Mas esta definição de mm está imprecisa, pois não leva em conta que a[h..m] pode não ocorrer, no sentido usual, em a[1..m-1]. A definição de ocorrência deve ser ligeiramente generalizada: se m>2 e h≤m-2, por exemplo, coincidências do tipo a[m]==a[1] e a[m-1..m]==a[1..2] contam como ocorrências de a[h..m] em a[1..m-1].
A definição exata do alcance de h é a seguinte:
mm = m-1;
ii = mm, i = m;
while (ii >= 1 && i >= h)
if (a[ii] == a[i]) --ii, --i;
else ii = --mm, i = m;
alcance[h] = mm;
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 agora examinar o código completo do segundo algoritmo de Boyer-Moore. O algoritmo de pré-processamento foi re-escrito de modo mais eficiente.
// 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 ocorre, h, mm, i, ii, j, k;
// pré-processamento da palavra a
h = mm = m;
do {
ii = --mm, i = m;
while (ii >= 1 && a[ii] == a[i])
--ii, --i;
while (h > i)
alcance[h--] = mm;
} while (ii >= 1);
while (h >= 1)
alcance[h--] = mm;
// busca da palavra a no texto b
ocorre = 0;
k = m;
while (k <= n) {
for (i = m, j = k; i >= 1; --i, --j)
if (a[i] != b[j]) break;
if (i < 1) ++ocorre;
if (i == m) k += 1;
else k += m - alcance[i+1];
}
return ocorre;
}
Escreva uma função que busque uma palavra em um texto interpretando o wildcard # como sugerido acima.