Busca em texto com o método de Boyer Moore

Publicado por Danilo Azevedo em 23/07/2014

[ Hits: 5.906 ]

 


Busca em texto com o método de Boyer Moore



Algoritmo de busca de texto usando o método Boyer Moore. Baseia-se na alta probabilidade de encontrar diferenças em alfabetos grandes.

Por Danilo Azevedo Santos e Evaldo Moreira Junior
Universidade Federal da Bahia
Bacharelado em Ciências da Computação

Exemplo do artigo Boyer Moore:

        1 2 3 4 5 ...                                                       35
  String: W H I C H - F I N A L L Y - H A L T S . - - A T - T H A T - P O I N T


        1 2 3 4 5 6 7
Padrão: A T - T H A T

Fórmulas (usando o padrão):

m = tamanho da string do padrão.

delta1 (caractere que não ocorre no padrão) = m, nesse caso, 7.
delta1 (caractere que ocorre no padrão) = m - (a última ocorrência do caractere dentro do padrão).

delta2(i) = m - rpr(i) + 1
rpr(i) = última recorrência plausível

Obs.: o delta2 só é usado quando é encontrado um caractere no texto que bate com o padrão, e sempre é escolhido o máximo entre delta1 e delta2.

Cálculo do delta1:

- Delta1(A) = 7 - 6 = 1
- Delta1(T) = 7 - 7 = 0
- Delta1(-) = 4
- Delta1(H) = 2
- Delta1(c) = 7, onde c não ocorre no padrão

Cálculo do delta2:

Delta2 do último caractere sempre 1, delta2(7) = 1

  -3 -2 -1 0  1  2  3  4  5  6  7
  $  $  $  $  A  T  -  T  H  A  T
                                  1
Calcular o delta2(6): procurar o sufixo de A, que não tenha A como prefixo.
Sufixo: T
(i.e., procurar a última ocorrência de T, onde não tem um A antes dele)
Nesse caso, o T do índice 4, logo rpr(6) = 4 e:
delta2(6) = 7 - 4 + 1 = 4

  -3 -2 -1 0  1  2  3  4  5  6  7
  $  $  $  $  A  T  -  T  H  A  T
                               4  1

Calcular o delta2(5): procurar o sufixo de H, que não tenha tenha H como prefixo.
Sufixo: A T (procurar "A T" no padrão que não tenha H como prefixo)
Nesse caso, o A T no índice 1 ($ representa um caractere qualquer)
delta2(5) = 7 - 1 + 1 = 7

  -3 -2 -1 0  1  2  3  4  5  6  7
  $  $  $  $  A  T  -  T  H  A  T
                            7  4  1

Calcular o delta2(4): procurar sufixo de T, que não tenha T como prefixo.
Sufixo: H A T
Nesse caso, o H A T no índice 0 ($ representa um caractere qualquer)
delta2(4) = 7 - 0 + 1 = 8

  -3 -2 -1 0  1  2  3  4  5  6  7
  $  $  $  $  A  T  -  T  H  A  T
                         8  7  4  1

Calcular o delta2(3): ...
Sufixo: T H A T
Seguindo a mesma lógica, teríamos o seguinte alinhamento de texto:

  -3 -2 -1 0  1  2  3  4  5  6  7
  $  $  $  $  A  T  -  T  H  A  T
          T  H  A  T


E portanto, o T H A T no índice -1
delta2(3) = 7 - (-1) + 1 = 9

  -3 -2 -1 0  1  2  3  4  5  6  7
  $  $  $  $  A  T  -  T  H  A  T
                      9  8  7  4  1

Calcular o delta2(2) e delta2(1): dá trabalho.
Resultado final:

  -3 -2 -1 0  1  2  3  4  5  6  7
  $  $  $  $  A  T  -  T  H  A  T
                11 10 9  8  7  4  1

Utilizando delta1 e delta2 para achar o padrão:

  1 2 3 4 5 ...                                                       35
  W H I C H - F I N A L L Y - H A L T S . - - A T - T H A T - P O I N T
  A T - T H A T


F não ocorre no padrão, logo, delta1(F) = 7

  1 2 3 4 5 ...                                                       35
  W H I C H - F I N A L L Y - H A L T S . - - A T - T H A T - P O I N T
  A T - T H A T
              A T - T H A T


Os caracteres não batem (não utiliza delta2), utilizamos o delta1 do caractere encontrado, delta1(-) = 4:

  1 2 3 4 5 ...                                                       35
  W H I C H - F I N A L L Y - H A L T S . - - A T - T H A T - P O I N T
  A T - T H A T
              A T - T H A T
                      A T - T H A T
                |


Os caracteres batem (T e T), utilizamos o máximo entre delta1 e delta2. o sufixo é o T (paramos no A)
delta1(L) = 7 e delta2 onde o sufixo é T é 1, pegando o máximo, usamos o delta1.

P.S.: pularam-se 7 a partir do elemento que parou a comparação, o caractere A.

  1 2 3 4 5 ...                                                       35
  W H I C H - F I N A L L Y - H A L T S . - - A T - T H A T - P O I N T
  A T - T H A T
              A T - T H A T
                      A T - T H A T
                                  A T - T H A T
                      |


Os caracteres batem até o caractere A, logo, utilizamos o delta2 que tem sufixo A T (o delta2(5)= 7).
Pegamos o máximo entre o delta1(-) = 4 e delta2(5) = 7, utilizamos o delta2.

Padrão encontrado:

  1 2 3 4 5 ...                                                       35
  W H I C H - F I N A L L Y - H A L T S . - - A T - T H A T - P O I N T
  A T - T H A T
              A T - T H A T
                      A T - T H A T
                                  A T - T H A T
                                            A T - T H A T


Referência

  • Artigo: A Fast String Searching Algorithm
  • Moore, Boyer - A Fast String Searching Algorithm (Programming Techniques)
  • editor G. Manacher, S.L. Graham.

Outras dicas deste autor
Nenhuma dica encontrada.
Leitura recomendada

Intranet Corporativa Vindula - Nova versão lançada

Acessando partições NTFS (read/write) com ntfs-3g (Slackware Linux 12)

O que é Software Livre

Como instalar o seu hp-plugin? Contornando o erro

Recuperar o som no Sabayon

  

Comentários
[1] Comentário enviado por SamL em 24/07/2014 - 00:31h

Gostei, bem explicado.

[2] Comentário enviado por albfneto em 24/07/2014 - 13:02h

Gostei, favoritado.
vou fazer uma sugestão.
existem pacotes disso, compilações binárias, pacotes prontos?

[3] Comentário enviado por danilogeek em 24/07/2014 - 18:28h

Ainda estou vendo isso 'albfneto', tenho uns materiais sobre isso estou procurando no meu antigo HD,Quando encontrar postarei!

[4] Comentário enviado por danilogeek em 24/07/2014 - 18:29h

Vlw a todos!



Contribuir com comentário




Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts