Casamento de Padrões em Strings

Ver o tópico anterior Ver o tópico seguinte Ir em baixo

Casamento de Padrões em Strings

Mensagem  PauloBruzaca em Qua Out 21, 2009 11:42 am

Visão Geral

Encontrar todas as ocorrências de um padrão em um texto é um
problema que surge com frequência nos programas de edição de textos e
na internet. Em geral o texto pode ser um documento que está sendo
digitado como uma página html, e o padrão procurado é uma palavra específica fornecida pelo usuário. A esse problema damos o nome de Casamento de Padrões em String.
Casamento de Padrões é um assunto muito importante no domínio de
processamento de textos. Os algoritmos de C.P.S. são componentes
básicos usados nas execuções dos softwares práticos que existem sob a
maioria de sistemas operacionais. Além disso, enfatizam os métodos de
programação que servem como paradigmas em outros campos da ciência da
computação(projeto de sistema ou de software design). Esses algoritmos
também são usados para procurar padrões específicos em seqências de
DNA.

Definição

O Casamento de Padrões em Strings consiste em encontrar um, ou mais
geralmente, todas as ocorrências de uma palavra(chamada mais geralmente
de padrão) em um texto. Todos os algoritmos aqui apresentados dão
saídas de todas as ocorrências do padrão no texto. O padrão é denotado
por P = P[0..m − 1] e seu comprimento é igual a m. Já o texto é denotado por T = T[0..n − 1] e seu comprimento é igual a n. Os dois textos são feitos através de um conjunto finito de caráter chamado um alfabeto denotado por Σ cujo tamanho é igual a σ .
Os algoritmos utilizam um esquema de janela deslizante. Uma janela, em geral, de tamanho m
é alinhada à esquerda com o texto. Os caracteres do texto que estão
dentro da janela são comparados com os caracteres do padrão. Se todos
os caracteres do padrão casam com os caracteres do texto ou se o
casamento falha, a janela é deslocada para a direita. Esse procedimento
se repete até o lado direito de janela ultrapassar o fim do texto. Cada
tentativa de casamento está associada com um deslocamento (posição) s no texto.



Algoritmo de Força Bruta ou Ingênuo


Descrição

O algoritmo consiste em analisar em todas as posições do texto entre
0 e n-m se há a ocorrência do padrão. Após a tentativa a jenela é
deslocada à direita uma posição.

  • A complexidade desse algoritmo é O((n-m+1)m).
  • A grande desvantagem desse algoritmo é que nenhuma informação é guardada para ser usada em futuras comparações.
Código

Código:

forcaIgenua(Texto, Padrao)
  n <- |Texto|
  m <- |Padrao|
  for s <- 0 to n − m do
    if Padrao[1..m] = Texto[s+1..s+m] then
        imprime("Deslocamento válido")

Características


  • Sempre desloca uma posição à direita.
  • A comparação dos caracteres pode ser feita em qualquer ordem
  • Não existe fase de pré-processamento
  • Complexidade O(m x n)
  • O espaço extra necessário é constante

Algoritmo Rabin-Karp

Descrição

Para generalizar a abordagem, consideremos um alfabeto de d símbolos 0,1,...,d − 1.
Por exemplo, o padrão P[1..m] tem o número correspondente p. E tem o número T[s + 1..s + m] é denotado por ts. Pode-se concluir que s só é um deslocamento válido se e somente se p = ts.
Logo, se pudermos calcular p e ts rapidamente, esse algoritmo será mais eficiente do que o algoritmo de Força Bruta.
Através da regra de Horner, o cálculo de p pode ser realizado em tempo O(m):

Código:

 p = P[m] + 10(P[m − 1] + 10(P[m − 2] + ... + 10(P[2] + 10P[1])...))

O cálculo de t0 é também feito em tempo O(m) para T[1..m].t1,t2,...,tnm podem ser calculados em tempo O(n-m), pois ts+1 é derivado de ts em tempo constante:

Código:
 
 ts+1 = 10(ts-10^(m − 1) * T[s+1])+T[s+m+1]

Como exemplo, vamos considerar m = 5 e ts = 31415. Se desejarmos remover o dígito 3 e trazer o novodígito 2:

Código:
 
 ts+1 = 10(31415 - 10000.3) + 2 = 14152

Os valores de 10m − 1 são pré-calculados em tempo O(m) para termos a equação calculada em tempo constante.
Essa técnica pode apresentar problemas quando m
for muito grande. A manipulação de números grandes não é feita em tempo
constante. A solução para estes casos seria fazer tudo mod q, onde q
seria um número primo onde 10.q coubesse na palavra do computador.

Código

Código:

 Rabin-Karp(Texto, Padrao, d, q)
  n <- |Texto|
  m <- |Padrao|
  h <- dm − 1 mod q
  p <- 0
  t0 <- 0
  for i <- 1 to m do
    p <- (d.p + P[i]) mod q
    t0 <- (d.p + T[i]) mod q
  for s <- 0 to n − m do
    if P[1..m] = T[s+1..s+m] then
      print "Deslocamento válido"s
  if s < n-m then
    t(s + 1) <- (d(ts - T[s+1]h) + T[s+m+1])</math> mod q


Características


  • Existe fase de pré-processamento

    • Utiliza uma função hashing
    • Espaço extra requerido é constante
    • Complexidade O(m)
    </li>
  • Na fase de busca tem complexidade O(mn)
  • Sempre desloca a janela uma posição para a direita
  • Complexidade esperada é O(m + n)

Casamento de Padrão com Automatos Finitos

Descrição

Muitos algoritmos de casamento de padrão considera o construção de
um autômato finito.Dessa forma é possível examinar o texto T, para
encontrar todas as ocorrências do padrão P. O algoritmo de casamento de
padrão baseado nesta técnica é bastante eficiente pois examina cada
caractere do texto apenas uma vez. Portanto o tempo necessário para
examinar o texto depois que o autômato foi construído é O(n). A grande
desvantagem dessa abordagem é a construção do autômato que pode levar
tempo considerável , caso Σ se ja grande.

AUTÔMATO FINITO

Um autômato finito é um 5-tuplo(Q,q0,A,Σ,δ):


  • Q é um conjunto finito de estados
  • q0 Q e é o estado inicial
  • A Q e é o conjunto de estados de aceitação
  • Σ é o alfabeto de operação finito
  • δ é uma função Q x Σ Q, chamada de função de transição

Autômato para casamento de padrão

Existe um autômato para casamento de padrão para cada padrão P
que pode ser construído a partir do próprio padrão. O autômato deve ser
criado antes de ser usado na busca de ocorrências de padrão em um
texto.
Inicialmente, é necessário definirmos uma função auxiliar σ ,
denominada função sufixo que mapeia de sigma estrela em 0,1,..m, onde
gama de x é o tamnho do maior prefixo de P que é o sufixo de x.
Por exemplo se p = ab, σ(e) = 0 , σ (ccaca) = 1, σ(ccab) = 2.
O autômato de casamento de padrão que corresponde a um padrão P[1..m] é definido da sequinte forma:

  • O conjunto de estados Q é 0,1...m. O estado inicial q0 é o estado 0, e m é o único estado de aceitação.
  • a função de transição δ é descrita pela sequinte equação, para qualquer estado q e caractere a:
Código:

 δ(q,a) = σ (Pq a)

Para ilustrar a construção do autômato vamos considerar o padrão P = ababaca .
O autômato derivado do padrão P é mostrado abaixo. O estado 0 é
o estado inicial(em amarelo no diagrama de transição). O estado 7 (em
azul no diagrama) é o único estado de aceitção. o arco dirigido de um
estado i para um estado j rotulado com a representa δ(i,a) = j. Os
arcos direcionados para direita que formam a espinha do autômato (em
vermelho no diagrama), correspondem ao casamento entre caracteres do
padrão e do texto. Os arcos que estão direcionados a esquerda
correspondem a falhas no casamento dos caracteres de padrão e texto. No
diagrama omitimos os arcos que retornam ao estado 0.


A utilização do autômato no texto T = abababacaba é mostrado abaixo . Apenas uma ocorrência do padrão foi encontrada.
Código

Código:

Automato(T,δ,m)
  n <-  | T |
  q <- 0
  for i <- 1 to n do
    q <- δ(q,T[i])
    if q = m then
      print "Deslocamento válido" i − m


O algoritmo para efetuar o casamento, depois de gerado o automato é
simples. A estrura com apenas um laço implica em um tempo de execução
de ordem O(n), como mostra o algoritmo acima. vale salientar que esse tempo de execução não inclui o tempo necessário para calcular a função δ.
O algoritmo a seguir computa a função de transição δ a partior de um dado padrão P[1..m].

Código:
 
CalculaFunçãoTRansição(P,Σ)
  m <-  | P |
  for q <- 0 to m do
    for cada caractere a\inΣ do
      k <- min(m + 1,q + 2)
      while Pk não contém Pqa do
        k <- k - 1
        δ(q,a) <- k
    return δ


Características


  • Existe fase de pré-processamento

    • Construção de um autômato finito baseado no próprio padrão
    • Espaço extra requerido O(m|Σ|).
    • Complexidade é O(m|Σ|)
    </li>
  • Sempre deslocaa janela (de tamaho 1) de uma posição para a direita.
  • Complexidade de comparação é O(n).

Algoritmo de Knuth-Morris-Pratt

Descrição

Algoritmo foi desenvolvido por Knuth, Morris e Pratt e a grande
característca é que esse algoritmo de casamento de padrao é executado
em tempo linear. A complexidade desse algoritmo é O(n + m) por que ele evita a computação da função delta de forma ineficiente como acontece no casamento de padrões com automatos finitos. Devido a esse fato, utiliza uma função auxiliar π[1..m] que é pré-calculada a partir do padrão em tempo O(m).
A função π e chamada de Função Prefixo
que contém informação sobre como o padrão casa a si mesmo, tal
informação é utlizada para evitar testar deslocamento inúteis, como
ocorre no Forca Bruta e para evitar fazer o pré-cálculo de δ, no caso da abordagem por Automatos.
Para ilustrar a vantagem de se usar a a função prefixo, vamos então considerar o padrãp P = ababaca. E vamos confrontar esse padrão com um texto T, considerando um deslocamento s, conforme a figura abaixo:


Ao testar a ocorrência do padrão, note que a comparação para o sexto caractere do padrão falha. Logo, 5 caracteres casaram (q = 5).
Essa informação pode ser usada para determinar que certos deslocamentos
são inválidos.
Em geral o que fazemos para determinar qual o próximo deslocamento
potencialmente válido é verificar que deslocamento não fere o casamento
do padrão P consigo mesmo, ou seja, se q casaram com o deslocamento s, o próximo deslocamento potencial válido é:

Código:

 s' = s + (q - π(q))

π[q] corresponde ao maior prefixo de P que é sufixo próprio de Pq, ou seja, π[q] = max k : k < q e PkPq.

Exemplo 1

b a c b a b a b a a b c b a b / Texto
s
a b a b a c a / Padrao
a b a b a / Pq
_ _ a b a / π
Sufixo a : π = 1
Sufixo ba : Nao eh prefixo de P
Sufixo aba : π = 3
Sufixo baba : Nao eh prefixo de P
Sufixo ababa : Nao eh sufixo proprio
Logo no exemplo acima, π[5] = 3 e, consequentemente, s' = s + (5 - 3) = s + 2.


Exemplo 2



  • Texto: G C A T C G C A G A G A G T A T A C A G T A C G
  • Padrao: G C A G A G A G


  • Fase de Pre-Processamento


Calculo da Função Prefixo ( π )


  • Fase de Processamento



Numero de Comparacoes de Caracteres: 18

Código

Código:

CasadorKMP(T, P)
  n <- |T|
  m <- |P|
  π <- CalculaPrefixo(P)
  q <- 0                                      => Número de caracteres correspondentes
  for i <- 1 to n do                          => Varre o texto da esquerda para a direita
    while q > 0 and P[q+1] != T[i] do
      q <- π[q]                              => O próximo caractere não correspondente
    if P[q+1] = T[i] then
      q <- q + 1                              => O próximo caractere correspondente
    if q = m then                              => Todo o P correspondeu?
      print padrão ocorre com deslocamento i-m
      q <- π[q]                              => Procura pela próxima correspondência
Código:

CalculaPrefixo(P)
  m <- |P|
  π[1] <- 0
  k <- 0
  for q <- 2 to m do
    while k > 0 and P[k+1] != P[q] do
      k <- π[k]
    if P[k+1] = P[q] then
      k <- k + 1
    π[k] <- k
  return π

Características


  • Existe fase de pré-processamento com complexidade O(m).
  • A comparação é feita da esquerda para a direita
  • Complexidade da comparação é O(m + n).
  • Deslocamento da janela para a direita pode variar (Dependente de quantos caracteres casaram na última comparação e da função π).

Para saber mais: http://dalton.dsc.ufcg.edu.br/edados/index.php/Casamento_de_Padr%C3%B5es_em_Strings
avatar
PauloBruzaca
Moderador
Moderador

Mensagens : 21
Pontos de contribuição : 14570
Data de inscrição : 15/10/2009
Idade : 38

Ver perfil do usuário

Voltar ao Topo Ir em baixo

Ver o tópico anterior Ver o tópico seguinte Voltar ao Topo

- Tópicos similares

 
Permissão deste fórum:
Você não pode responder aos tópicos neste fórum