Algoritmo de busca de expressões Boyer-Moore
Em ciência da computação, o algoritmo de busca de expressões Boyer-Moore é 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. O algoritmo pré-processa a string sendo procurada, mas não a string em que é feito a busca. É 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.
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.
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
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. 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
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: 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.
Uma simples mas importante otimização da BM foi feita por Galil em 1979. 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.
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, seguido por Guibas e Odlyzko em 1980 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. 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.
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.
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.
