Algoritmo de busca de expressões Boyer-Moore

Em ciência da computação, o algoritmo de busca de expressões Boyer-Moore (Boyer-Moore string search algorithm) é um eficiente algoritmo de busca que é o padrão de qualidade para busca prática de expressões em literatura. Foi desenvolvido por Robert S. Boyer e J Strother Moore em 1977.[1] O algoritmo pré-processa a string sendo procurada (o padrão), mas não a string em que é feito a busca (o texto). É ainda bem aproveitado para aplicações em que o padrão é muito menor do que o texto ou onde persiste por multiplas buscas. O algoritmo BM (Boyer-Moore) usa informação reunida durante o passo de pré-processamento para pular seções do texto, resultando em um constante fator baixo do que muitos outros algoritmos. Em geral, o algoritmo roda mais rápido de acordo com o tamanho do padrão aumenta. As características chaves do algoritmo são combinar na cauda do padrão ao invés da cabeça, e pular pelo texto em deslocamentos de multiplos caracteres ao invés de procurar cada caractere no texto.

Definições

editar
A N P A N M A N -
P A N - - - - - -
- P A N - - - - -
- - P A N - - - -
- - - P A N - - -
- - - - P A N - -
- - - - - P A N -
Alinhamentos do padrão PAN ao texto ANPANMAN, de k=3 até k=8. Uma combinação ocorre em k=5.
  • S[i] denota o caractere no índice i da string S, contando a partir de 1.
  • S[i..j] denota a substring da string S começando no índice i e terminando em j, incluído.
  • Um prefixo de S é uma substring S[1..i] para algum i entre [1, n], onde n é o tamanho de S.
  • Um sufixo de S é uma substring S[i..n] para algum i entre [1, n], onde n é o tamanho de S.
  • A string a ser procurada é chamada de padrão e é denotada por P. Seu tamanho é n.
  • A string em que pesquisamos é chamada de texto e é denotada por T. Seu tamanho é m.
  • Um alinhamento de P até T é um índice k em T até que o último caractere de P esteja alinhado com índice k em T.
  • Uma combinação ou ocorrência de P acontece no alinhamento se P é equivalente a T[(k-n+1)..k].

Descrição

editar

O algoritmo BM busca por ocorrências de P em T realizando comparações explícitas de caracteres em diferentes alinhamentos. Diferente de uma busca por força bruta em todos os alinhamentos (que são m - n + 1), BM usa informação ganha pelo pré-processamento P para pular quantos alinhamentos forem possíveis.

Antes da introdução desse algoritmo, o caminho usado para buscas em texto era examinar cada caractere do texto pelo primeiro caractere do padrão. Uma vez encontrado, os caracteres subsequentes do texto seriam comparados com os caracteres do padrão. Se nenhuma combinação acontecia, então o texto seria checado de novo caractere por caractere em uma tentativa de achar uma combinação. Assim quase todo caractere em um texto precisa ser examinado.

A chave dentro deste algoritmo é que se o final do padrão é comparado com o texto, então pular pelo texto pode ser feito ao invés de checar cada caractere dele. O motivo disso funcionar é que alinhando o padrão com o texto, o último caractere do padrão é comparado com o caractere do texto. Se os caracteres não baterem, não existe necessidade de continuar buscando por trás pelo padrão. Se o caractere em um texto não combina com nenhum dos caracteres do padrão, então o próximo caractere a ser verificado no texto está localizado a n caracteres de distância pelo texto,onde n é o tamanho do padrão, se o caractere está no padrão, então um deslocamento parcial do padrão pelo texto é feito para alinhar o caractere encontrado e o processo é repetido. O movimento pelo texto em deslocamentos para fazer comparações ao invés de checar cada caractere no texto diminui o número de comparações que deve ser feito, o que é a chave para aumentar a eficiência do algoritmo.

Mais formalmente, o algoritmo começa pelo alinhamento k = n, então o começo de P é alinhado com o começo de T. Caracteres em P e T são então comparados começando pelo índice n em P e k em T, movendo de trás para frente: as strings são comparadas a partir do fim de P até o início de P. As comparações continuam até que ou o início de P é alcançado ( o que significa que é uma combinação) ou uma falha na comparação aconteça fazendo com que o alinhamento pule para a direita de acordo com o valor máximo permitido por um número de regras. As comparações são realizadas novamente no novo alinhamento, e o processo repete até que o alinhamento pule após o fim de T, o que significa que nenhuma combinação será encontrada.

As regras de deslocamento são implementadas como tabelas de consulta em tempo constante, usando tabelas geradas durante o pré-processamento de P.

Regras de Deslocamento

editar

Um deslocamento é calculado aplicando duas regras: a regra do caractere errado e a do sufixo correto. O atual compensamento por deslocamento é o máximo de deslocamentos calculados por estas regras.

A Regra de Caractere Errado

editar

Descrição

editar
- - - - X - - K - - -
A N P A N M A N A M -
- N N A A M A N - - -
- - - N N A A M A N -
Demonstração da regra de caractere errado com padrão NNAAMAN.

A regra de caractere errado considera o caractere em T em que o processo de comparação falhou (assumindo que tal falha ocorreu). A próxima ocorrência desse caractere à esquerda em P é encontrada, e um deslocamento que traz essa ocorrência em alinhamento com a não ocorrência de combinação em T é proposta. Se o caractere que não combina não ocorre na esquerda de P, um deslocamento é proposto que move inteiramente em P passando o ponto que não combinou.

Pré-processamento

editar

Métodos variam na forma exata em que a tabela para a regra de caractere errado deveria ter, mas uma simples solução de consulta em tempo constante é a seguinte: criar uma tabela 2D que seja indexada primeiro pelo índice do caractere c em um alfabeto e segundo pelo índice i no padrão. Essa consulta resultará a ocorrência de c em P com o índice mais próximo j < i ou -1 se não existe tal ocorrência. O deslocamento proposto será então i - j, com O(1) como tempo de consulta e O(kn) de espaço, assumindo um alfabeto finito de tamanho k.

A Regra do Sufixo Correto

editar

Descrição

editar
- - - - X - - K - - - - -
M A N P A N A M A N A P -
A N A M P N A M - - - - -
- - - - A N A M P N A M -
Demonstração da regra do sufixo correto com padrão ANAMPNAM.

A regra do sufixo correto é marcadamente mais complexa em ambos conceito e implementação do que a regra do caractere errado. É a razão das comparações começarem pelo final do padrão ao invés do início, e é formalmente descrito assim:[2]

Suponha que para um dado alinhamento de P e T, uma substring t de T combina com um sufixo de P, mas uma não combinação ocorre na próxima comparação para a esquerda. Então encontre, se existir, a cópia mais a direita t' de t em P tal que t' não é um sufixo de P e o caractere para a esquerda de t' em P difere do caractere à esquerda de t em P. Desloque P para a direita para que a substring t' em P alinhe-se com a substring t em T. Se t' não existir, então desloque o fim da esquerda de P até o fim de t em T o mínimo possível para que o prefixo do padrão deslocado combine um sufixo de t em T. Se tal deslocamento não for possível, então desloque P por n posições para a direita. Se uma ocorrência de P é encontrada, então desloque P o mínimo possível para que o prefixo apropriado do P deslocado combine com um sufixo da ocorrência de P em T. Se tal deslocamento não for possível, então desloque P por n posições, isso é, desloque P por t.

Pré-processamento

editar

A regra de sufixo correto possui duas tabelas: uma para uso em caso geral, e outra para uso quando ou o caso geral retorne nenhum resultado significativo ou uma combinação ocorre. Estas tabelas serão designadas L e H respectivamente. As definições delas são:[2]

Para cada i, L[i] é maior posição menor que n tal que string P[i..n] combine um sufixo de P[1..L[i]] e que o caractere que precede aquele sufixo não seja igual a P[i-1]. L[i] é definido como zero se não existe posição satisfazendo a condição.

Deixe H[i] denotar o tamanho do maior sufixo de P[i..n] que também é prefixo de P, se existir. Se não existir, deixe H[i] ser zero.

Ambas as tabelas são construidas em tempo O(n) e usadas em espaço O(n). O alinhamento de deslocamento para índice i em P é dado por n - L[i] ou n - H[i]. H deveria somente ser usada se L[i] é zero ou uma combinação foi encontrada.

A Regra de Galil

editar

Uma simples mas importante otimização da BM foi feita por Galil em 1979.[3] Diferente de deslocamento, a regra de Galil trata de aumentar a velocidade das comparações feitas atualmente em cada alinhamento pulando seções que são conhecidas para combinar. Suponha que em um alinhamento k1, P é comparado com T até o caractere c de T. Então se P é deslocado até k2 até que seu fim à esquerda esteja entre c e k1, na próxima fase de comparação um prefixo de P deve combinar com a substring T[(k2 - n)..k1]. Mesmo se as comparações forem até posição k1 de T, uma ocorrência de P pode ser gravada sem comparação explicita passada por k1. Além do mais, para melhorar a eficiência de Boyer-Moore, a regra Galil é requerida para provar execução em tempo linear no pior caso.

Performance

editar

O algoritmo BM como foi apresentado no documento original tem como pior caso o tempo de O(n+m) somente se o padrão não aparecer no texto. Isso foi primeiramente provado por Knuth, Morris, e Pratt em 1977,[4] seguido por Guibas e Odlyzko em 1980[5] com um limitante superior de 5m comparações no pior caso. Richard Cole deu uma prova com um limitante superior de 3m comparações no pior caso em 1991.[6]

Quando o padrão ocorre no texto, o tempo de execução do algoritmo original é O(nm) no pior caso. É fácil de ver que quando ambos o padrão e o texto consiste solenemente do mesmo caractere repedito. Entretanto, a inclusão da regra de Galil resulta em uma execuação linear entre todos os casos.[3][6]

Implementações

editar

Existem várias implementações em diferentes linguagens de programação. Em C++, Boost providencia a generic Boyer–Moore search implementação genérica da busca Boyer-Moore usando a biblioteca Algorithm. em Go (programming language) existe uma implementação em search.go. D (programming language) usa um BoyerMooreFinder para predizer combinações bases como alcance como uma parte da Phobos Runtime Library.

Abaixo existem alguns exemplos de implementação.

Variantes

editar

O algoritmo BMH (Boyer-Moore-Horspool) é uma simplificação do algoritmo BM usando apenas a regra do caractere errado.

O algoritmo AG (Apostolico-Giancarlo) aumenta o precesso de checagem quando uma combinação ocorre no dado alinhamento pulando comparações explicitas de caracteres. Isso usa informação recolhida durante o pré-processamento do padrão em conjunção com os tamanhos das combinações de sufixo gravadas em cada tentativa de combinar. Guardar os tamanhos das combinações dos sufixos requer uma tabela adicional igual em tamanho com o texto sendo pesquisado.

Ver também

editar

Referências

  1. Boyer, Robert S.; Moore, J Strother (outubro de 1977). «A Fast String Searching Algorithm.». New York, NY, USA: Association for Computing Machinery. Comm. ACM. 20 (10): 762–772. ISSN 0001-0782. doi:10.1145/359842.359859 
  2. a b Gusfield, Dan (1999) [1997], «Chapter 2 - Exact Matching: Classical Comparison-Based Methods», Algorithms on Strings, Trees, and Sequences, ISBN 0521585198 1 ed. , Cambridge University Press, pp. 19–21 
  3. a b Galil, Z. (setembro de 1979). «On improving the worst case running time of the Boyer-Moore string matching algorithm». New York, NY, USA: Association for Computing Machinery. Comm. ACM. 22 (9): 505–508. ISSN 0001-0782. doi:10.1145/359146.359148 
  4. Knuth, Donald; Morris, James H.; Pratt, Vaughan (1977). «Fast pattern matching in strings». SIAM Journal on Computing. 6 (2): 323–350. doi:10.1137/0206024 
  5. Guibas, Odlyzko; Odlyzko, Andrew (1977). «A new proof of the linearity of the Boyer-Moore string searching algorithm». Washington, DC, USA: IEEE Computer Society. Proceedings of the 18th Annual Symposium on Foundations of Computer Science: 189–195. doi:10.1109/SFCS.1977.3 
  6. a b Cole, Richard (setembro de 1991). «Tight bounds on the complexity of the Boyer-Moore string matching algorithm». Philadelphia, PA, USA: Society for Industrial and Applied Mathematics. Proceedings of the 2nd annual ACM-SIAM symposium on Discrete algorithms: 224–233. ISBN 0-89791-376-0 

Ligações externas

editar