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.

• 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].

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.

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 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 é 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.

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.

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 k₁, P é comparado com T até o caractere c de T. Então se P é deslocado até k₂ até que seu fim à esquerda esteja entre c e k₁, na próxima fase de comparação um prefixo de P deve combinar com a substring T[(k₂ - n)..k₁]. Mesmo se as comparações forem até posição k₁ de T, uma ocorrência de P pode ser gravada sem comparação explicita passada por k₁. 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,^[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]

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.

def alphabet_index(c):
    """
    Returns the index of the given character in the English alphabet, counting from 0.
    """
    return ord(c.lower()) - 97 # 'a' is ASCII character 97

def match_length(S, idx1, idx2):
    """
    Returns the length of the match of the substrings of S beginning at idx1 and idx2.
    """
    if idx1 == idx2:
        return len(S) - idx1
    match_count = 0
    while idx1 < len(S) and idx2 < len(S) and S[idx1] == S[idx2]:
        match_count += 1
        idx1 += 1
        idx2 += 1
    return match_count

def fundamental_preprocess(S):
    """
    Returns Z, the Fundamental Preprocessing of S. Z[i] is the length of the substring
    beginning at i which is also a prefix of S. This pre-processing is done in O(n) time,
    where n is the length of S.
    """
    if len(S) == 0: # Handles case of empty string
        return []
    if len(S) == 1: # Handles case of single-character string
        return [1]
    z = [0 for x in S]
    z[0] = len(S)
    z[1] = match_length(S, 0, 1)
    for i in range(2, 1+z[1]): # Optimization from exercise 1-5
        z[i] = z[1]-i+1
    # Defines lower and upper limits of z-box
    l = 0
    r = 0
    for i in range(2+z[1], len(S)):
        if i <= r: # i falls within existing z-box
            k = i-l
            b = z[k]
            a = r-i+1
            if b < a: # b ends within existing z-box
                z[i] = b
            else: # b ends at or after the end of the z-box, we need to do an explicit match to the right of the z-box
                z[i] = b+match_length(S, a, r+1)
                l = i
                r = i+z[i]-1
        else: # i does not reside within existing z-box
            z[i] = match_length(S, 0, i)
            if z[i] > 0:
                l = i
                r = i+z[i]-1
    return z

def bad_character_table(S):
    """
    Generates R for S, which is an array indexed by the position of some character c in the
    English alphabet. At that index in R is an array of length |S|+1, specifying for each
    index i in S (plus the index after S) the next location of character c encountered when
    traversing S from right to left starting at i. This is used for a constant-time lookup
    for the bad character rule in the Boyer-Moore string search algorithm, although it has
    a much larger size than non-constant-time solutions.
    """
    if len(S) == 0:
        return [[] for a in range(26)]
    R = [[-1] for a in range(26)]
    alpha = [-1 for a in range(26)]
    for i, c in enumerate(S):
        alpha[alphabet_index(c)] = i
        for j, a in enumerate(alpha):
            R[j].append(a)
    return R

def good_suffix_table(S):
    """
    Generates L for S, an array used in the implementation of the strong good suffix rule.
    L[i] = k, the largest position in S such that S[i:] (the suffix of S starting at i) matches
    a suffix of S[:k] (a substring in S ending at k). Used in Boyer-Moore, L gives an amount to
    shift P relative to T such that no instances of P in T are skipped and a suffix of P[:L[i]]
    matches the substring of T matched by a suffix of P in the previous match attempt.
    Specifically, if the mismatch took place at position i-1 in P, the shift magnitude is given
    by the equation len(P) - L[i]. In the case that L[i] = -1, the full shift table is used.
    Since only proper suffixes matter, L[0] = -1.
    """
    L = [-1 for c in S]
    N = fundamental_preprocess(S[::-1]) # S[::-1] reverses S
    N.reverse()
    for j in range(0, len(S)-1):
        i = len(S) - N[j]
        if i != len(S):
            L[i] = j
    return L

def full_shift_table(S):
    """
    Generates F for S, an array used in a special case of the good suffix rule in the Boyer-Moore
    string search algorithm. F[i] is the length of the longest suffix of S[i:] that is also a
    prefix of S. In the cases it is used, the shift magnitude of the pattern P relative to the
    text T is len(P) - F[i] for a mismatch occurring at i-1.
    """
    F = [0 for c in S]
    Z = fundamental_preprocess(S)
    longest = 0
    for i, zv in enumerate(reversed(Z)):
        longest = max(zv, longest) if zv == i+1 else longest
        F[-i-1] = longest
    return F

def string_search(P, T):
    """
    Implementation of the Boyer-Moore string search algorithm. This finds all occurrences of P
    in T, and incorporates numerous ways of pre-processing the pattern to determine the optimal
    amount to shift the string and skip comparisons. In practice it runs in O(m) (and even
    sublinear) time, where m is the length of T. This implementation performs a case-insensitive
    search on ASCII alphabetic characters, spaces not included.
    """
    if len(P) == 0 or len(T) == 0 or len(T) < len(P):
        return []

    matches = []

    # Preprocessing
    R = bad_character_table(P)
    L = good_suffix_table(P)
    F = full_shift_table(P)

    k = len(P) - 1      # Represents alignment of end of P relative to T
    previous_k = -1     # Represents alignment in previous phase (Galil's rule)
    while k < len(T):
        i = len(P) - 1  # Character to compare in P
        h = k           # Character to compare in T
        while i >= 0 and h > previous_k and P[i] == T[h]:   # Matches starting from end of P
            i -= 1
            h -= 1
        if i == -1 or h == previous_k:  # Match has been found (Galil's rule)
            matches.append(k - len(P) + 1)
            k += len(P)-F[1] if len(P) > 1 else 1
        else:   # No match, shift by max of bad character and good suffix rules
            char_shift = i - R[alphabet_index(T[h])][i]
            if i+1 == len(P):   # Mismatch happened on first attempt
                suffix_shift = 1
            elif L[i+1] == -1:   # Matched suffix does not appear anywhere in P
                suffix_shift = len(P) - F[i+1]
            else:               # Matched suffix appears in P
                suffix_shift = len(P) - L[i+1]
            shift = max(char_shift, suffix_shift)
            previous_k = k if shift >= i+1 else previous_k  # Galil's rule
            k += shift
    return matches

#include <stdint.h>
#include <stdlib.h>

#define ALPHABET_LEN 256
#define NOT_FOUND patlen
#define max(a, b) ((a < b) ? b : a)

// delta1 table: delta1[c] contains the distance between the last
// character of pat and the rightmost occurrence of c in pat.
// If c does not occur in pat, then delta1[c] = patlen.
// If c is at string[i] and c != pat[patlen-1], we can
// safely shift i over by delta1[c], which is the minimum distance
// needed to shift pat forward to get string[i] lined up
// with some character in pat.
// this algorithm runs in alphabet_len+patlen time.
void make_delta1(int *delta1, uint8_t *pat, int32_t patlen) {
    int i;
    for (i=0; i < ALPHABET_LEN; i++) {
        delta1[i] = NOT_FOUND;
    }
    for (i=0; i < patlen-1; i++) {
        delta1[pat[i]] = patlen-1 - i;
    }
}

// true if the suffix of word starting from word[pos] is a prefix
// of word
int is_prefix(uint8_t *word, int wordlen, int pos) {
    int i;
    int suffixlen = wordlen - pos;
    // could also use the strncmp() library function here
    for (i = 0; i < suffixlen; i++) {
        if (word[i] != word[pos+i]) {
            return 0;
        }
    }
    return 1;
}

// length of the longest suffix of word ending on word[pos].
// suffix_length("dddbcabc", 8, 4) = 2
int suffix_length(uint8_t *word, int wordlen, int pos) {
    int i;
    // increment suffix length i to the first mismatch or beginning
    // of the word
    for (i = 0; (word[pos-i] == word[wordlen-1-i]) && (i < pos); i++);
    return i;
}

// delta2 table: given a mismatch at pat[pos], we want to align
// with the next possible full match could be based on what we
// know about pat[pos+1] to pat[patlen-1].
//
// In case 1:
// pat[pos+1] to pat[patlen-1] does not occur elsewhere in pat,
// the next plausible match starts at or after the mismatch.
// If, within the substring pat[pos+1 .. patlen-1], lies a prefix
// of pat, the next plausible match is here (if there are multiple
// prefixes in the substring, pick the longest). Otherwise, the
// next plausible match starts past the character aligned with
// pat[patlen-1].
//
// In case 2:
// pat[pos+1] to pat[patlen-1] does occur elsewhere in pat. The
// mismatch tells us that we are not looking at the end of a match.
// We may, however, be looking at the middle of a match.
//
// The first loop, which takes care of case 1, is analogous to
// the KMP table, adapted for a 'backwards' scan order with the
// additional restriction that the substrings it considers as
// potential prefixes are all suffixes. In the worst case scenario
// pat consists of the same letter repeated, so every suffix is
// a prefix. This loop alone is not sufficient, however:
// Suppose that pat is "ABYXCDBYX", and text is ".....ABYXCDEYX".
// We will match X, Y, and find B != E. There is no prefix of pat
// in the suffix "YX", so the first loop tells us to skip forward
// by 9 characters.
// Although superficially similar to the KMP table, the KMP table
// relies on information about the beginning of the partial match
// that the BM algorithm does not have.
//
// The second loop addresses case 2. Since suffix_length may not be
// unique, we want to take the minimum value, which will tell us
// how far away the closest potential match is.
void make_delta2(int *delta2, uint8_t *pat, int32_t patlen) {
    int p;
    int last_prefix_index = patlen-1;

    // first loop
    for (p=patlen-1; p>=0; p--) {
        if (is_prefix(pat, patlen, p+1)) {
            last_prefix_index = p+1;
        }
        delta2[p] = last_prefix_index + (patlen-1 - p);
    }

    // second loop
    for (p=0; p < patlen-1; p++) {
        int slen = suffix_length(pat, patlen, p);
        if (pat[p - slen] != pat[patlen-1 - slen]) {
            delta2[patlen-1 - slen] = patlen-1 - p + slen;
        }
    }
}

uint8_t* boyer_moore (uint8_t *string, uint32_t stringlen, uint8_t *pat, uint32_t patlen) {
    int i;
    int delta1[ALPHABET_LEN];
    int *delta2 = (int *)malloc(patlen * sizeof(int));
    make_delta1(delta1, pat, patlen);
    make_delta2(delta2, pat, patlen);

    // The empty pattern must be considered specially
    if (patlen == 0) return string;

    i = patlen-1;
    while (i < stringlen) {
        int j = patlen-1;
        while (j >= 0 && (string[i] == pat[j])) {
            --i;
            --j;
        }
        if (j < 0) {
            free(delta2);
            return (string + i+1);
        }

        i += max(delta1[string[i]], delta2[j]);
    }
    free(delta2);
    return NULL;
}

    /**
     * Returns the index within this string of the first occurrence of the
     * specified substring. If it is not a substring, return -1.
     *
     * @param haystack The string to be scanned
     * @param needle The target string to search
     * @return The start index of the substring
     */
    public static int indexOf(char[] haystack, char[] needle) {
        if (needle.length == 0) {
            return 0;
        }
        int charTable[] = makeCharTable(needle);
        int offsetTable[] = makeOffsetTable(needle);
        for (int i = needle.length - 1, j; i < haystack.length;) {
            for (j = needle.length - 1; needle[j] == haystack[i]; --i, --j) {
                if (j == 0) {
                    return i;
                }
            }
            // i += needle.length - j; // For naive method
            i += Math.max(offsetTable[needle.length - 1 - j], charTable[haystack[i]]);
        }
        return -1;
    }

    /**
     * Makes the jump table based on the mismatched character information.
     */
    private static int[] makeCharTable(char[] needle) {
        final int ALPHABET_SIZE = 256;
        int[] table = new int[ALPHABET_SIZE];
        for (int i = 0; i < table.length; ++i) {
            table[i] = needle.length;
        }
        for (int i = 0; i < needle.length - 1; ++i) {
            table[needle[i]] = needle.length - 1 - i;
        }
        return table;
    }

    /**
     * Makes the jump table based on the scan offset which mismatch occurs.
     */
    private static int[] makeOffsetTable(char[] needle) {
        int[] table = new int[needle.length];
        int lastPrefixPosition = needle.length;
        for (int i = needle.length - 1; i >= 0; --i) {
            if (isPrefix(needle, i + 1)) {
                lastPrefixPosition = i + 1;
            }
            table[needle.length - 1 - i] = lastPrefixPosition - i + needle.length - 1;
        }
        for (int i = 0; i < needle.length - 1; ++i) {
            int slen = suffixLength(needle, i);
            table[slen] = needle.length - 1 - i + slen;
        }
        return table;
    }

    /**
     * Is needle[p:end] a prefix of needle?
     */
    private static boolean isPrefix(char[] needle, int p) {
        for (int i = p, j = 0; i < needle.length; ++i, ++j) {
            if (needle[i] != needle[j]) {
                return false;
            }
        }
        return true;
    }

    /**
     * Returns the maximum length of the substring ends at p and is a suffix.
     */
    private static int suffixLength(char[] needle, int p) {
        int len = 0;
        for (int i = p, j = needle.length - 1;
                 i >= 0 && needle[i] == needle[j]; --i, --j) {
            len += 1;
        }
        return len;
    }

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.

• Knuth–Morris–Pratt string search algorithm
• Boyer–Moore–Horspool string search algorithm
• Apostolico–Giancarlo string search algorithm
• Aho–Corasick multi-pattern string search algorithm
• Rabin–Karp multi-pattern string search algorithm
• Suffix trees

Referências

• Original paper on the Boyer-Moore algorithm
• An example of the Boyer-Moore algorithm from the homepage of J Strother Moore, co-inventor of the algorithm
• Richard Cole's 1991 paper proving runtime linearity