Saltar a contenido

Boyer-Moore

La búsqueda de patrones (string searching) es un problema fundamental en computación. Si bien el método de "fuerza bruta" (comparar el patrón en cada posición posible del texto) funciona, su lentitud \(O(n \cdot m)\) lo hace impráctico. El algoritmo Boyer-Moore, desarrollado por Robert S. Boyer y J Strother Moore en 1977, ofrece una solución drásticamente más rápida.

A diferencia de la mayoría de algoritmos que comparan el texto de izquierda a derecha, la idea central de Boyer-Moore es comparar el patrón contra el texto de derecha a izquierda.

Descripción

El algoritmo Boyer-Moore es un algoritmo de búsqueda exacta para un solo patrón. Su eficiencia proviene de la capacidad de realizar "saltos" largos a través del texto cada vez que se encuentra un desajuste.

Esto se logra pre-procesando el patrón (de longitud \(m\)) para construir dos "tablas" que implementan dos heurísticas:

  1. La Heurística del Carácter Erróneo (Bad Character Heuristic): Permite un salto basado en el carácter del texto que causó el desajuste.
  2. La Heurística del Sufijo Bueno (Good Suffix Heuristic): Permite un salto basado en la parte del patrón que sí logró coincidir antes del desajuste.

En cada paso, el algoritmo calcula el salto propuesto por ambas heurísticas y toma el máximo de los dos, asegurando un avance rápido y seguro.

Funcionamiento

El objetivo del algoritmo es encontrar todas las ocurrencias de un patrón \(P\) de longitud \(m\) dentro de un texto \(T\) de longitud \(n\).

La complejidad del pre-cálculo (construir las dos tablas) es de \(O(m + |\Sigma|)\), donde \(|\Sigma|\) es el tamaño del alfabeto.

La complejidad de la búsqueda tiene un mejor caso de \(O(n/m)\), que es extraordinariamente rápido (por ejemplo, si el último carácter del patrón no aparece en el texto). El peor caso, aunque raro en la práctica, es de \(O(n \cdot m)\), pero con la implementación completa de la heurística del sufijo bueno (como la que tienes), el peor caso se garantiza en \(O(n)\).

A continuación, presentamos el algoritmo:

  1. Alinear el patrón \(P\) con el inicio del texto \(T\).
  2. Comparar de derecha a izquierda (desde el índice \(j = m-1\) hasta \(0\)).
  3. Si hay un desajuste en el índice \(j\) (el carácter T[i+j] no coincide con P[j]):
  4. Calcular salto_bch: Usar la Heurística del Carácter Erróneo. Miramos el carácter del texto que falló (T[i+j]). Buscamos su última aparición en el patrón (usando la tabla_bch). El salto se calcula para alinear esa última aparición con el carácter del texto. Si el carácter no está en el patrón, el salto es \(j+1\), moviendo el patrón completamente más allá del desajuste.
  5. Calcular salto_gsh: Usar la Heurística del Sufijo Bueno. Miramos la parte del patrón que sí coincidió (el "sufijo bueno", P[j+1...m-1]). Buscamos la última aparición de este sufijo en otra parte del patrón (usando la tabla_gsh) y calculamos el salto para alinearla.
  6. Avanzar: Mover el patrón hacia adelante max(salto_bch, salto_gsh, 1) posiciones.
  7. Si no hay desajuste (se llega a \(j < 0\)):
  8. Se ha encontrado una coincidencia. Se reporta el índice \(i\).
  9. Avanzar: Mover el patrón usando la tabla_gsh para el caso de una coincidencia completa (para encontrar la siguiente posible ocurrencia).
  10. Repetir desde el paso 2 hasta que el patrón sobrepase el final del texto.

Pre-cálculo y Almacenamiento

A diferencia de Huffman, donde el árbol debe almacenarse, en Boyer-Moore el "conocimiento" del patrón se almacena en dos tablas de pre-cálculo. Estas tablas solo dependen del patrón y se generan una vez antes de que comience la búsqueda.

  • Tabla de Carácter Erróneo (BCH): Generalmente es un diccionario o un array que mapea cada carácter del alfabeto a su última posición (índice) dentro del patrón. Si un carácter no aparece, se le asigna -1.
  • Tabla de Sufijo Bueno (GSH): Es un array de tamaño \(m\) (la longitud del patrón) que almacena el tamaño del salto para cada posible posición de desajuste \(j\). tabla_gsh[j] contiene el salto a realizar si el desajuste ocurre en j y el sufijo P[j+1...m-1] coincidió.

Implementación

A continuación se presenta una implementación en Python3 del algoritmo descrito anteriormente. Esta implementación incluye ambas heurísticas para ser robusta.

def construir_tabla_caracter_erroneo(patron):
    """
    Construye la tabla de Carácter Erróneo (Bad Character Heuristic)
    Almacena la última posición de cada carácter del patrón.
    """
    tabla = {}
    for i, c in enumerate(patron):
        tabla[c] = i
    return tabla


def construir_tabla_sufijo_bueno(patron):
    """
    Construye la tabla de Sufijo Bueno (Good Suffix Heuristic)
    Esta tabla indica cuánto desplazar el patrón cuando ocurre un desajuste
    basado en sufijos que coinciden.
    """
    m = len(patron)
    salto = [0] * m
    frontera = [0] * m

    # Paso 1: calcular fronteras (similar a KMP)
    i = m
    j = m + 1
    frontera[i - 1] = j
    while i > 0:
        while j <= m and patron[i - 1] != patron[j - 1 if j - 1 < m else 0]:
            if salto[j - 1 if j - 1 < m else 0] == 0:
                salto[j - 1 if j - 1 < m else 0] = j - i
            j = frontera[j - 1 if j - 1 < m else 0]
        i -= 1
        j -= 1
        frontera[i - 1 if i - 1 >= 0 else 0] = j

    # Paso 2: llenar las posiciones restantes
    j = frontera[0]
    for i in range(m):
        if salto[i] == 0:
            salto[i] = j
        if i == j:
            j = frontera[j]

    return salto


def boyer_moore(texto, patron):
    """
    Implementa el algoritmo Boyer-Moore de búsqueda de patrones.
    Utiliza las heurísticas de Carácter Erróneo y Sufijo Bueno.
    """
    n = len(texto)
    m = len(patron)
    if m == 0:
        return []

    # --- Pre-cálculo ---
    tabla_bch = construir_tabla_caracter_erroneo(patron)
    tabla_gsh = construir_tabla_sufijo_bueno(patron)

    resultados = []
    i = 0  # Índice del texto donde se alinea el patrón

    while i <= n - m:
        j = m - 1  # Índice dentro del patrón (desde el final hacia atrás)

        # Comparar de derecha a izquierda
        while j >= 0 and texto[i + j] == patron[j]:
            j -= 1

        if j < 0:
            # --- Coincidencia completa ---
            resultados.append(i)
            i += tabla_gsh[0] if m > 1 else 1
        else:
            # --- Desajuste ---
            caracter_erroneo = texto[i + j]
            # Regla de Carácter Erróneo
            ultimo_indice = tabla_bch.get(caracter_erroneo, -1)
            salto_bch = j - ultimo_indice

            # Regla de Sufijo Bueno
            salto_gsh = tabla_gsh[j] if j < m else 1

            # Avanzar el máximo entre ambas reglas
            i += max(salto_bch, salto_gsh, 1)

    return resultados

Ejemplo de ejecución

Ahora veremos cómo se realiza la búsqueda sobre el mensaje T = "HERE_IS_A_SIMPLE_EXAMPLE" con el patrón P = "EXAMPLE".

Primero, se pre-calculan las tablas para el patrón P = "EXAMPLE" (longitud \(m=7\)).

Tabla de Carácter Erróneo (BCH):

{'E': 6, 'X': 1, 'A': 2, 'M': 3, 'P': 4, 'L': 5}

(Nota: 'E' aparece en 0 y 6, la tabla guarda el último: 6)

Tabla de Sufijo Bueno (GSH):

(El resultado de la función construir_tabla_sufijo_bueno("EXAMPLE"))

Ejecución:

Alineación 1:

T: H E R E _ I S _ A _ S I M P L E _ E X A M P L E

P: E X A M P L E

Comparación (derecha a izquierda): P[6] ('E') vs T[6] ('S'). ¡Desajuste!

j = 6. Carácter erróneo del texto: 'S'.

salto_bch: 'S' no está en tabla_bch (devuelve -1). Salto = j - (-1) = 6 - (-1) = 7.

salto_gsh: Sufijo bueno es (vacío). Salto = tabla_gsh[6].

Se toma el max(7, salto_gsh). Saltamos 7 posiciones.

Alineación 2:

T: H E R E _ I S _ A _ S I M P L E _ E X A M P L E

P:         E X A M P L E

Comparación: P[6] ('E') vs T[13] ('P') → desajuste.

j = 6. Carácter erróneo del texto: 'P'.

salto_bch: 'P' está en tabla_bch en índice 4. Salto = j - 4 = 6 - 4 = 2.

salto_gsh: Sufijo bueno es "". Salto = tabla_gsh[6].

Se toma el max(2, salto_gsh). Saltamos 2 posiciones.

Alineación 3:

T: H E R E _ I S _ A _ S I M P L E _ E X A M P L E

P:           E X A M P L E

Comparación: P[6] ('E') vs T[15] ('M') → desajuste.

j = 6. Carácter erróneo del texto: 'M'.

salto_bch: 'M' está en tabla_bch en 3. Salto = 6 - 3 = 3.

Saltamos 3 posiciones.

Alineación 4:

T: H E R E _ I S _ A _ S I M P L E _ E X A M P L E

P:                 E X A M P L E

Comparación: P[6] ('E') vs T[18] ('E') → coincide.

Comparación: P[5] ('L') vs T[17] ('L') → coincide ... (todas coinciden)

j llega a -1. ¡Coincidencia encontrada en el índice 18!

Se avanza según tabla_gsh[0] para buscar más coincidencias.

Aplicaciones

Debido a su excelente rendimiento en la práctica (especialmente con alfabetos grandes como ASCII), Boyer-Moore es un estándar industrial.

  • Es la base de la utilidad grep en sistemas UNIX/Linux.

  • Se utiliza en la función "Buscar" (Ctrl+F) de muchos editores de texto y procesadores de palabras.

  • Implementado en bibliotecas estándar de muchos lenguajes para la búsqueda de subcadenas.

  • Usado en bioinformática (para buscar secuencias de ADN) y en sistemas de detección de intrusos (para buscar firmas de virus en el tráfico de red).

  • Algo interesante es que su rendimiento mejora a medida que el patrón es más largo y el alfabeto es más grande, lo cual es contraintuitivo pero es una consecuencia directa de que las heurísticas permiten saltos más grandes.

Referencias

  • Boyer, R. S., & Moore, J. S. (1977). A fast string searching algorithm. Communications of the ACM, 20(10), 762–772.

  • Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.). MIT Press.

  • Gusfield, D. (1997). Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press.