Esta página trata de cadeias de caracteres (= strings). Suporemos que cada caracter ocupa apenas 1 byte e usa a tabela de codificação ISO-LATIN-1. Em geral, usaremos apenas o subconjunto ASCII da tabela. (Veja minhas notas sobre Caracteres e tabela ASCII e Esquemas de codificação.)
Esta página é um resumo da seção 12.7 do livro de Sedgewick.
Um sufixo
de uma cadeia de caracteres s
é qualquer cadeia da forma &s[i] ,
sendo i um inteiro menor ou igual ao comprimento de s.
Como se sabe, &s[i]
é o mesmo que s+i
e portanto representa a parte de s
da posição i em diante.
Um prefixo de uma cadeia s é a cadeia que obteríamos se trocássemos um dos caracteres de s por '\0'. Portanto, um prefixo é a parte de s que vai até uma certa posição. Em particular, s é prefixo de s. Eis uma função que decide se uma cadeia s é prefixo de uma cadeia t. Trata-se de uma variante da função strcmp da biblioteca padrão string:
typedef char *string; // Devolve 0 se s for prefixo de t. Devolve // um número negativo se s não é prefixo // de t mas é menor que t no sentido // lexicográfico. Devolve um número positivo // se s é maior que t no sentido // lexicográfico (é claro que nesse caso s // não é prefixo de t). int prefixcmp (string s, string t) { int i; for (i = 0; s[i] == t[i]; i++) if (s[i] == '\0') return 0; // 3 if (s[i] == '\0') return 0; // 4 else return s[i] - t[i]; // 5 }
A linha 3 cuida do caso em que s e t são iguais. A linha 4 cuida do caso em que s é prefixo de t mas não é igual a t. A linha 5 cuida dos demais casos. (Note que a função está correta mesmo que o comprimento de s seja maior que o comprimento de t.)
int pref (string s, string t) {
int i = 0;
while (1) {
if (s[i] == '\0') return 0;
if (s[i] == t[i]) ++i;
else return s[i] - t[i];
}
}
Dizemos que uma cadeia s ocorre em uma cadeia t (ou que s é um segmento de t) se s é um prefixo de um sufixo de t. Em outras palavras, s ocorre em t se existe um indice k tal que
s é prefixo de t + k .
Dizemos também, nesse caso, que s casa com t a partir da posição k.
Exemplos: No exemplo a seguir, a cadeia s (segunda linha) casa com a cadeia t (primeira linha) a partir da posição marcada com o sinal ∨:
∨ R u b i ã o f i t a v a a e n s e a d a , - a e n s e a Mais um exemplo:
∨ 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
Este capítulo pretende estudar alguns algoritmos para o seguinte problema, conhecido como string matching:
Problema: Encontrar uma ocorrência de uma cadeia s em uma cadeia t.
No contexto deste problema, diz-se que s é uma palavra e t um texto. Assim, o problema consiste em encontrar uma palavra num texto. O problema pode ter variações, como a de encontrar todas as ocorrêcias de uma palavra em um texto.
A seguinte função resolve o problema da maneira mais óbvia. Pacientemente, ela verifica se a palavra s é prefixo do texto t, se é prefixo do texto t+1, e assim por diante. (Já examinamos essa função em outra ocasião.)
#include <string.h> typedef char *string;
// Devolve a posição de uma ocorrência da
// palavra s no texto t. Se não existe
// ocorrência alguma, devolve -1.
int trivial (string s, string t) {
int k, m = strlen(s), n = strlen(t);
for (k = 0; k <= n - m; ++k)
if (prefixcmp(s, t + k) == 0)
return k;
return -1;
}
Observe como a coisa funciona bem até mesmo quando m == 0 ou quando n == 0 ou quando m > n. Isso é um bom sinal!
O consumo de tempo da função é proporcional ao número de comparações entre um caracter de s e um caracter de t. E esse número é
no máximo m·n .
Desafio: resolver o problema fazendo menos comparações entre a palavra e o texto.
Boyer e Moore
descobriram uma maneira de acelerar o algoritmo trivial.
O algoritmo de Boyer-Moore depende do conhecimento prévio do
alfabeto
do problema,
ou seja, do conjunto dos caracteres usados na palavra e no texto.
Vamos supor aqui que o alfabeto é o conjunto de todos os 256 caracteres
ISO-LATIN-1.
O algoritmo é baseado na seguinte ideia. Suponha que acabamos de verificar que s não é prefixo do texto t + k. Se a palavra s tem comprimento m e o caracter t[k+m] não ocorre em s então s certamente não é prefixo de t + k+1, nem de t + k+2, … , nem de t + k+m. A próxima tentativa deve verificar se s é prefixo de t + k+m+1.
Essa ideia é estendida como segue. Seja u o índice da última ocorrência do caracter t[k+m] em s (se o caracter não ocorre em s então u = -1). Suponha que acabamos de verificar que s não é prefixo de t + k. O próximo passo deve verificar se s é prefixo de
t + k+m-u.
A seguinte figura mostra os únicos alinhamentos da palavra BCBA com o texto em que precisamos verificar se há casamento.
| 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 essa ideia, basta fazer um pré-processamento da palavra que determine, para cada caracter c do alfabeto, a última ocorrência, digamos ult[c], de c em s. Para a palavra BCBA, por exemplo, teremos
| 0 | 1 | 2 | 3 |
| B | C | B | A |
| c | ... > ? @ A B C D E F ... |
| ult[c] | ... -1 -1 -1 3 2 1 -1 -1 -1 ... |
Eis o código (surpreendentemente simples) da função:
// Devolve a posição de uma ocorrência da // palavra s no texto t. Se não existe // ocorrência alguma, devolve -1. int boyermoore (string s, string t) { int ult[256]; int c, i, j, k; int m = strlen(s), n = strlen(t); // pré-processamento da palavra for (c = 0; c < 256; ++c) ult[c] = -1; for (i = 0; i < m; ++i) ult[s[i]] = i; // busca da palavra no texto k = 0; while (k <= n - m) { if (prefixcmp(s, t + k) == 0) return k; k += m - ult[t[k+m]]; } return -1; }
ult[t[k+m]]por
ult[t[k+m-1]]? Que ajustes é preciso fazer no pré-processamento para que a função continue correta?
||||||||
IIIIIIIIIIIAABBXXAABBXXAAIIIIIIII
^^^^^^^^
Esta seção é inspirada no programa 12.10 de Sedgewick.
Imagine que queremos buscar muitas palavras diferentes em um mesmo texto. Nesse caso vale a pena fazer um pré-processamento do texto para que as buscas sejam rápidas.
O pré-processamento do texto consiste na construção de uma árvore de busca de todos os sufixos do texto. A árvore será representada de uma maneira mais simples que as estudadas anteriormente. Os nós de nossa árvore serão os inteiros do intervalo 0..n-1, sendo n o comprimento do texto. A chave de cada nó k é a cadeia t+k. Os filhos esquerdo e direito de k serão left[k] e right[k] respectivamente. Portanto, a árvore toda será representada pelos vetores left[0..n-1] e right[0..n-1].
Eis um exemplo em que o texto t é a cadeia "dbgacehf":
nó 0 1 2 3 4 5 6 7
chave dbgacehf bgacehf gacehf acehf cehf ehf hf f
left 1 3 5 - - - - -
right 2 4 6 - - 7 - -
0
/ \
1 2
/ \ / \
3 4 5 6
\
7
O programa tem duas fases. A primeira constrói a árvore de busca:
int *left, *right; // Constrói a árvore de busca para o texto t. // void indexing (string t) { int n = strlen(t); left = malloc(n * sizeof (int)); right = malloc(n * sizeof (int)); for (k = 0; k < n; k++) left[k] = right[k] = -1; for (k = 0; k < n; k++) insert(k); } // Insere o nó k na árvore de busca do texto. // void insert(int k) { int h = 0; while (1) { if (prefixcmp(t+k, t+h) < 0) { if (left[h] == -1) { left[h] = k; break; } h = left[h]; } else { if (right[h] == -1) { right[h] = k; break; } h = right[h]; } } }
A segunda fase do programa faz a busca de uma palavra s no texto t usando a representação (left, right) do texto:
// Devolve o indice a partir do qual há uma
// ocorrência de s no texto. Devolve -1 se
// não houver ocorrência alguma.
//
int search (string s) {
int h = 0;
do {
int cmp = prefixcmp(s, t + h);
if (cmp == 0) return h;
if (cmp < 0) h = left[h];
else h = right[h];
} while (h != -1);
return -1;
}
O consumo de tempo do programa é proporcional ao número de comparações entre caracteres (cada execução da função prefixcmp pode envolver até n-1 tais comparações). Quanto vale esse número?
Digamos que o texto tem n caracteres do texto e suponha que a árvore do texto (construída pelas sucessivas chamadas de insert), é bem equilibrada. Suponha ainda que cada execução de prefixcmp implica em algumas poucas comparações entre caracteres, digamos não mais que 10. Então a construção da árvore consome no máximo 10 n lg(n) comparações entre caracteres e cada busca de uma palavra no texto consome no máximo 10 lg(n) comparações entre caracteres.