Definição
Encontrar todas as ocorrências de um padrão em uma cadeia (caracteres). Também é chamado de casamento de cadeias ou casamento de padrões.
Aplicações
· Edição de texto
· Recuperação de informação
· Estudo de seqüência de DNA’s em biologia computacional
Notação
Para uma cadeia C[1..n] e um padrão de P [1..m], onde m <= n. Os elementos de C e P são escolhidos de um alfabeto finito.
O casamento de cadeias verifica a ocorrência do padrão P na cadeia C. Quando P e C não estão pré-processados, a complexidade do tempo é O(mn) e de espaço é O(1). Já quando apenas P é pré-processado, a complexidade do tempo é O(n) e de espaço é O(m+c). E para P e C pré-processados a complexidade de tempo é O(log n) e de espaço é O (n log n).
Quando se obtém todas as ocorrências exatas do padrão na cadeia, o casamento é chamado de exato. Existem dois enfoques para verificação dessas ocorrências:
1. Leitura dos caracteres da cadeia um a um. Utiliza-se os algoritmos KMP (Knuth-Morris-Pratt), o Shift-And exato e aproximado e o força bruta.
2. Pesquisa de P em uma janela que percorre C, pesquisando por um sufixo da janela que casa com um sufixo de P, por comparações da direita para esquerda. Utilizam-se os algoritmos BM (Boyer-Moore) e BMH (Boyer-Moore-Horspool).
KMP (Knuth-Morris-Pratt)
O KMP foi o primeiro algoritmo cujo pior caso tem complexidade de tempo linear ao tamanho da cadeia, O(n). É um dos algoritmos mais conhecidos para resolver esse problema de casamento de cadeia, porém ele apresenta uma implementação complicada e uma eficiência baixa em relação ao Shift-And e ao BMH. No KMP o algoritmo computa o sufixo mais longo de C que seja também o prefixo de P. Quando o comprimento do sufixo da janela é igual ao tamanho de P, ocorre-se o casamento.
O pré-processamento (não permite a verificação do que já foi visto) de P pode ser visto como uma construção econômica de um autômato determinístico que depois é usado para pesquisar por P em C, esse pré-processamento é a essência do algoritmo. Os passos do algoritmo são o seguinte:
1. A cadeia C é sempre incrementada não há caminho de volta;
2. Caso haja uma desigualdade na verificação das ocorrências, é consultada uma tabela (vetor) para encontrar a que distancia em P precisa-se fazer o caminho de volta;
3. Há na tabela para cada caractere de P um número correspondente a quantidade de posições que cada caractere deve voltar.
4. É importante lembrar que apenas P faz o caminho de volta.
Algoritmo KMP em C:
int kmp (char *p, char *t) {
int i=0, j=0, M=strlen(p), N=strlen(t);
init_next (p);
while ((i < N) && (j < M)){
if ((j == -1) || (t[i] == p[j])) {
i++; j++;
}
else
j = next[j];
}
if (j == M) return i - M;
return -1;
}
void init_next (char *p) {
int i = 0, j = -1, M = strlen(p);
next[0] = -1;
while (i < M){
if ((j == -1) || (p[i] == p[j])) {
i++; j++;
next[i] = j;
}
else
j = next[j];
}
}
A complexidade para a função kmp é O(n), só que este algoritmo também chama a função init_next, onde sua complexidade é O(m). Conclui-se então que complexidade do algoritmo KMP é O(n) + O(m). Só que há casos (cadeias com poucas repetições sucessivas) em que a complexidade se aproxima ao do algoritmo Força Bruta O(m x n), e há casos em que a complexidade seria igual a função init_next, ou seja, O(m).
BM (Boyer-Moore)
Esse algoritmo realiza pesquisas no padrão a ser buscado da direita para esquerda, o que torna o algoritmo muito rápido. Caso haja alguma desigualdade numa determinada comparação, é calculado um deslocamento para P onde deve ser deslizado para a direita antes que se reinicie uma nova tentativa de casamento.
Existem varias heurísticas para se determinar o deslocamento onde podem ser executadas independente e simultaneamente para calcular o deslocamento, mas só apenas a que oferecer o maior deslocamento será usado, segue abaixo dois exemplos de heurísticas:
1. Heurística Ocorrência
Alinha o ultimo elemento de P com o primeiro elemento de C em que ocorre casamento, onde a posição desse elemento de C seja maior ou igual ao tamanho de P. Com isso faz a verificação da direita para a esquerda caractere por caractere, caso haja alguma colisão, P é deslocado para o próximo elemento de C em que se case com seu ultimo elemento. E assim sucessivamente.
2. Heurística Casamento
Ocorre da mesma forma da Heurística Ocorrência, só que quando for deslocar P, irá verificar o pedaço da cadeia casado anteriormente e não apenas o último elemento.
Algoritmo BM em C:
int bm (const char *p, const char *t) {
int i, j, M = strlen(p), N = strlen(t);
i = j = M - 1;
init_skip (p);
do {
if (t[i] == p[j]) {
--i; --j;
}
else {
if (M - j > skip[t[i]])
i += M - j;
else
i += skip[t[i]];
j = M - 1;
}
} while (j >= 0 && i < N);
if (j < 0)
return i+1;
return -1;
}
void init_skip (const char *p) {
int j, M = strlen(p);
for (j = 0; j < MAXCHARS; j++)
skip[j] = M;
for (j = 0; j < M - 1; j++)
skip[p[j]] = M - j - 1;
for (j = 0; j < MAXCHARS; j++)
if (skip[j] != M)
}
Os dois tipos de heurísticas podem ser pré-computados com base apenas no padrão e no alfabeto utilizado. Assim, a complexidade para esta fase é O(m + c). O pior caso do BM é O(n + rm), onde r é o numero de casamentos, tornando ineficiente quando o numero de casamentos é grande. Enquanto isso, o melhor caso e o caso médio tem O (n/m).
Shift-And Exato
O Shift-And é muito mais rápido e muito mais simples que o KMP e pode ser estendido para permitir casamento aproximado (Shift-And Aproximado). O Shift-And utiliza um conceito muito importante que seria o de paralelismo de bit.
O paralelismo de bits é uma técnica que tira proveito do paralelismo das operações sobre os bits dentro de uma palavra de computador, onde é possível empacotar muitos valores em uma única palavra e atualizar todos numa única operação. Tirando proveito disso, o número de operações que um algoritmo realiza pode ser reduzido para até o número de bits da palavra do computador.
O Shift-And sempre mantém um conjunto de caracteres casados. Utiliza-se o paralelismo de bits justamente para atualizar esse conjunto a cada caractere lido. O primeiro passo a se fazer é criar uma tabela para armazenar o conjunto de bits, onde o nº de linhas é igual ao numero de caracteres distintos de P e o nº de colunas é igual ao tamanho de P. Exemplo: P = {teste}
R | 1 | 2 | 3 | 4 | 5 |
M[t] | 1 | 0 | 0 | 1 | 0 |
M[e] | 0 | 1 | 0 | 0 | 1 |
M[s] | 0 | 0 | 1 | 0 | 0 |
A máscara de bits em M[t] é 10010, pois o caractere t aparece nas posições 1 e 4 de P.
O valor do conjunto R é inicializado com 0 (bit do valor 0) e para cada novo valor lido R é atualizado.
O custo do Shift-And é O(n) para quando as operações são realizadas em O(1) e P cabe em poucas palavras do computador.
Algoritmo Shift-And em C:
int shiftand (const char *p, const char *t) {
const int MAXPAT = 32;
const int TABSIZE = 256;
const unsigned long ONELEFT = 0x80000000;
int i = 0, j = 0, M = strlen(p), N = strlen(t);
if (M > MAXPAT) {
cout <<"Max tamanho de P: " <<< endl;
return -1;
}
unsigned long tabela[TABSIZE];
for (i = 0; i < TABSIZE; ++i)
tabela[i] = 0;
unsigned long mascara = ONELEFT;
for (j = 0; j < M; ++j) {
tabela[p[j]] |= mascara;
mascara >>= 1;
}
unsigned long R = 0;
mascara = ONELEFT >> (M - 1);
for (i = 0 ; i < N; ++i) {
R = ((R >> 1) | 0x80000000) & tabela[t[i]];
if (R & mascara)
return i - M + 1; // sucesso
}
return -1; // fracasso
}
Shift-And Aproximado
É uma extensão do Shift-And Exato. Também utiliza o paralelismo de bit, só que este simula um autômato não-determinístico.
Esse algoritmo permite casamentos aproximados, ou seja, atribui-se uma constante para determinar o nº de erros “aceitáveis”. Com isso é possível realizar operações de inserção, substituição e retirada de caracteres de P.
A complexidade desse algoritmo chega a ser O(kn) para P típico, onde K é o nº de casamentos não realizados (erros) e n o tamanho do texto.
Conclusão
Verificou-se que para determinados algoritmos são mais eficientes que outros em certas aplicações. Por exemplo, o BM é o mais eficiente onde P tem tamanho considerável (mais de 10 caracteres) e possui um alfabeto enorme. Já o KMP mostra-se eficiente em cadeias em que os caracteres são repetidos, pode-se fazer uma analogia com a cadeia de DNA que possui apenas 4 elementos distintos. Para os demais casos Shift-And é bem mais eficiente devido ao paralelismo de bits.
