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.