Pesquisar no blog

terça-feira, 19 de janeiro de 2010

CASAMENTO DE CADEIAS DE CARACTERES


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.