Boyer-Moore

Lo que cubre este capítulo

KMP y Rabin-Karp leen cada carácter del texto. Boyer-Moore lee menos caracteres de los que el texto tiene — es el raro algoritmo genuinamente sublineal, que examina solo una fracción de los caracteres sobre los que busca, y la consecuencia contraintuitiva es que un patrón más largo lo hace más rápido. Lo logra con dos ideas: alinea el patrón contra el texto y compara de derecha a izquierda, y ante un mismatch usa lo que acaba de ver para deslizar el patrón hacia adelante con un salto demostrablemente seguro — muchas veces brincándose montones de caracteres sin siquiera mirarlos. Cuando el carácter que falló no aparece en el patrón, Boyer-Moore se salta la longitud completa del patrón de un solo golpe. Este capítulo construye la regla del mal carácter (bad-character), observa al patrón brincar a lo largo de un texto y mide la ganancia: con un patrón largo examinó 24 veces menos caracteres que KMP. Este es el motor que vive dentro de grep.

Un poco de historia

Robert Boyer y J Strother Moore publicaron el algoritmo en 1977 — el mismo año que KMP, un año notable para la búsqueda de cadenas — mientras trabajaban en el Stanford Research Institute y SRI. Su artículo hacía una afirmación que sonaba imposible: un algoritmo de búsqueda cuyo tiempo de ejecución disminuye conforme el patrón crece, porque un patrón más largo permite saltos más grandes. Eso puso de cabeza la intuición ingenua (más patrón, más trabajo). El algoritmo completo combina dos reglas de desplazamiento — la del mal carácter que construimos aquí y otra más sutil llamada "buen sufijo" — y el análisis del peor caso tardó años en cerrarse: la versión original podía ser $O(n \cdot m)$ en casos adversariales, y fue Zvi Galil en 1979, y después otros, quien agregó refinamientos que garantizan tiempo lineal en el peor caso. Pero la versión práctica, sobre todo la variante simplificada Boyer-Moore-Horspool, se volvió el estándar de la búsqueda de texto real porque sobre texto ordinario con un alfabeto grande simplemente no hay nada más rápido. Cuando corres grep, un descendiente de Boyer-Moore es el que hace el trabajo.

La intuición

Alinea el patrón con el inicio del texto, pero compara desde la derecha. Mira el carácter del texto que queda bajo el último carácter del patrón. Si coinciden, avanza a la izquierda y compara el siguiente par; si logras coincidir hasta el inicio del patrón, encontraste una ocurrencia. Pero normalmente vas a chocar con un mismatch rapidito, y ahí es donde está la magia. Supón que el carácter del texto que falló es c. Pregúntate: ¿dónde aparece c dentro del patrón? Si aparece en algún lado, desliza el patrón a la derecha para que esa ocurrencia de c quede justo debajo de esta c del texto — no tiene caso probar alineaciones que no pondrían ahí un carácter que coincida. Si c no aparece en el patrón, entonces ninguna alineación que se traslape con esa c puede coincidir, así que desliza el patrón completamente más allá de ella — un salto de la longitud completa del patrón.

Esa es la regla del mal carácter, y su poder crece con el tamaño del alfabeto y la longitud del patrón. Sobre texto en inglés o sobre DNA, la mayoría de los caracteres que sondeas no van a estar en el lugar correcto del patrón, así que la mayoría de las ventanas se descartan con una sola comparación y un salto grande. El patrón patina sobre el texto tocando quizá un carácter de cada m. Compáralo con KMP, que pacientemente lee cada carácter del texto de izquierda a derecha: KMP nunca se salta nada, así que examina los n completos. Boyer-Moore se salta agresivamente, así que examina $\approx n/m$ en entradas favorables. El recorrido de derecha a izquierda es lo que hace posible el salto — al revisar primero el final del patrón, un solo mismatch te informa sobre toda una ventana de alineaciones.

Complejidad: cómo escala

El mejor caso de Boyer-Moore es $O(n/m)$ — cuando el último carácter del patrón sigue fallando contra caracteres del texto que no están en el patrón, cada sondeo dispara un salto de longitud completa, así que toca apenas unos $n/m$ caracteres. Su promedio sobre texto aleatorio con un alfabeto de tamaño $\sigma$ es sublineal, más o menos $O(n/\min(m, \sigma))$. La regla del mal carácter por sí sola tiene un peor caso $O(n \cdot m)$ (con entrada repetitiva y adversarial, la némesis de KMP pero en versión "saltos"); agregar la regla del buen sufijo, o usar el refinamiento de Galil, restaura el peor caso lineal. Construir la tabla de bad-character cuesta $O(\sigma + m)$. El enfrentamiento muestra el comportamiento característico directamente — caracteres examinados conforme el patrón se alarga, Boyer-Moore contra KMP:

Mira las dos líneas. La de KMP es plana — examina alrededor de 100,000 caracteres (el texto completo) sin importar qué tan largo sea el patrón, porque nunca se salta nada. La línea de Boyer-Moore baja: entre más largo el patrón, más grandes sus saltos y menos caracteres mira. Con un patrón de longitud 64 examinó unos 4,200 caracteres contra los 100,000 de KMP — 24 veces menos, y siguiendo a la baja. Esta es la gráfica que captura por qué Boyer-Moore es especial: es el único algoritmo de búsqueda importante donde el trabajo baja conforme el patrón del problema crece, porque toda su estrategia consiste en usar la longitud del patrón como licencia para saltar. Sobre un alfabeto grande, eso lo convierte en el ganador práctico de la búsqueda de texto real.

En qué es bueno y en qué no

Boyer-Moore es la herramienta correcta para buscar texto sobre un alfabeto razonablemente grande — lenguaje natural, código fuente, flujos de bytes en general — que es casi toda la búsqueda del día a día. Su promedio sublineal lo vuelve el default en grep, en el "buscar" de los editores de texto y en las rutinas de subcadenas de los runtimes de lenguajes. Entre más largo el patrón, más gana, así que brilla para encontrar cadenas fijas largas. Y no necesita preprocesar el texto (solo el patrón, que es chico), así que es ideal para buscar en archivos enormes o en streams que no puedes indexar de antemano.

Donde encaja menos es con alfabetos pequeños, donde la regla del mal carácter pierde fuerza: sobre datos binarios o DNA (alfabeto de 2 o 4), el carácter que falla casi siempre está en algún lugar del patrón, así que los saltos son cortos y la ventaja de Boyer-Moore sobre KMP se encoge (la regla del buen sufijo ayuda aquí, y existen algoritmos especializados). Su forma con solo bad-character tiene un peor caso cuadrático, así que con entrada adversarial o no confiable conviene la versión completa o un algoritmo con garantía lineal. Para múltiples patrones, Aho-Corasick (el siguiente capítulo) es mejor; para streaming donde no puedes ir y venir libremente, el recorrido estrictamente hacia adelante de KMP encaja mejor. Y, como siempre, para una búsqueda de una sola vez en código de aplicación simplemente llamarías str.find — que por dentro es, de hecho, un pariente de Boyer-Moore.

Los datos, o las entradas

El enfrentamiento busca dentro de un texto aleatorio de 100,000 caracteres sobre el alfabeto de 26 letras, usando patrones de longitud creciente, y cuenta cuántos caracteres del texto examinan Boyer-Moore y KMP — la medida directa de cuánto se saltan. La correctitud se verifica con tres mil pares aleatorios de texto/patrón sobre alfabetos de tamaño 2 a 26: los resultados de Boyer-Moore deben coincidir exactamente con el str.find nativo de Python. La animación corre Boyer-Moore buscando abcd dentro de zzzzabcdyabcd, escogido para que los caracteres que fallan (z, y) no estén en el patrón y disparen brincos de longitud completa que puedes ver.

Constrúyelo, una función a la vez

La tabla de bad-character — la ocurrencia más a la derecha de cada carácter dentro del patrón:

def last_occurrence(pattern):
    """For each character, the index of its RIGHTMOST occurrence in the pattern. This is the
    bad-character table: when a mismatch happens at a text character c, this tells us where c
    could line up inside the pattern, so we can slide the pattern to align them (or leap past
    c entirely if it never appears)."""
    last = {}
    for i, ch in enumerate(pattern):
        last[ch] = i                             # later positions overwrite earlier → rightmost wins
    return last

Y la búsqueda — comparación de derecha a izquierda, salto hacia adelante ante un mismatch:

def boyer_moore(text, pattern):
    """Find every occurrence of `pattern` in `text` using the bad-character rule. Align the
    pattern, compare right-to-left; on a mismatch at text character c, shift the pattern forward
    so c's rightmost occurrence in the pattern lines up under it (never less than 1). Characters
    the shift jumps over are never examined — the source of the sublinear behavior. Returns
    (matches, examined) where `examined` counts text characters actually looked at."""
    n, m = len(text), len(pattern)
    if m == 0:
        return list(range(n + 1)), 0
    if m > n:
        return [], 0
    last = last_occurrence(pattern)
    matches, examined = [], 0
    i = 0                                        # index in text where the pattern's left end sits
    while i <= n - m:
        j = m - 1                                # start comparing from the RIGHT end of the pattern
        while j >= 0:
            examined += 1
            if text[i + j] != pattern[j]:
                break
            j -= 1
        if j < 0:                                # ran off the left end → full match
            matches.append(i)
            i += 1                               # shift by one to find overlapping matches
        else:
            c = text[i + j]                      # the mismatching text character
            shift = j - last.get(c, -1)          # align c with its rightmost spot in the pattern
            i += max(1, shift)                   # never stall; skip the chars in between unexamined
    return matches, examined

Míralo funcionar

Aquí está Boyer-Moore buscando abcd (abajo) dentro de zzzzabcdyabcd (arriba). Fíjate en el primer movimiento: el patrón se alinea al inicio y la primera comparación ocurre en el extremo derecho del patrón — posición 3 del texto, una z. Como z no aparece para nada en abcd, ninguna alineación que se traslape con esa z podría coincidir jamás, así que el patrón brinca su longitud completa hacia adelante, saltándose las posiciones 0–3 sin examinarlas nunca. Cae justo sobre abcd y coincide, de derecha a izquierda, en cuatro comparaciones. Después la solitaria y (también ausente del patrón) dispara otro brinco completo hasta el segundo abcd. El patrón patina sobre el texto tocando apenas un puñado de sus trece caracteres — azul es el carácter que se está comparando, verde el sufijo que ya coincidió, rojo un mismatch que lanza un salto:

El código completo

La pestaña "desde cero" es Boyer-Moore con la regla del mal carácter; la pestaña de librería es KMP, el contraste que lee todos los caracteres y que se usa para verificar la correctitud y contar examinaciones en el enfrentamiento, más la referencia con str.find. Cambia entre ellas para ver las dos filosofías — leer todo (KMP) contra saltar agresivamente (Boyer-Moore).

"""Boyer-Moore — the substring search that reads FEWER than n characters. KMP and Rabin-Karp
both examine every character of the text. Boyer-Moore examines a fraction of them, which is
why it (and its variants) sit inside grep, and why the counterintuitive rule holds: the LONGER
the pattern, the FASTER the search.

The trick is two ideas working together. First, it aligns the pattern with the text and compares
RIGHT TO LEFT — from the end of the pattern backward. Second, on a mismatch it uses what it just
saw to slide the pattern FORWARD by as much as is provably safe, often skipping over many text
characters without ever looking at them. This chapter builds the core "bad-character rule": when
a text character doesn't match, look at where (if anywhere) that character appears in the pattern,
and shift so those line up — or, if the character isn't in the pattern at all, leap the whole
pattern length past it. On a large alphabet that means most windows are dismissed after a single
comparison, and the search runs in sublinear time on average.
"""


# region: bad_char
def last_occurrence(pattern):
    """For each character, the index of its RIGHTMOST occurrence in the pattern. This is the
    bad-character table: when a mismatch happens at a text character c, this tells us where c
    could line up inside the pattern, so we can slide the pattern to align them (or leap past
    c entirely if it never appears)."""
    last = {}
    for i, ch in enumerate(pattern):
        last[ch] = i                             # later positions overwrite earlier → rightmost wins
    return last
# endregion


# region: boyer_moore
def boyer_moore(text, pattern):
    """Find every occurrence of `pattern` in `text` using the bad-character rule. Align the
    pattern, compare right-to-left; on a mismatch at text character c, shift the pattern forward
    so c's rightmost occurrence in the pattern lines up under it (never less than 1). Characters
    the shift jumps over are never examined — the source of the sublinear behavior. Returns
    (matches, examined) where `examined` counts text characters actually looked at."""
    n, m = len(text), len(pattern)
    if m == 0:
        return list(range(n + 1)), 0
    if m > n:
        return [], 0
    last = last_occurrence(pattern)
    matches, examined = [], 0
    i = 0                                        # index in text where the pattern's left end sits
    while i <= n - m:
        j = m - 1                                # start comparing from the RIGHT end of the pattern
        while j >= 0:
            examined += 1
            if text[i + j] != pattern[j]:
                break
            j -= 1
        if j < 0:                                # ran off the left end → full match
            matches.append(i)
            i += 1                               # shift by one to find overlapping matches
        else:
            c = text[i + j]                      # the mismatching text character
            shift = j - last.get(c, -1)          # align c with its rightmost spot in the pattern
            i += max(1, shift)                   # never stall; skip the chars in between unexamined
    return matches, examined
# endregion

"""The library counterpart and the contrast. Python's `str.find` (C, a two-way hybrid) is the
correctness reference. The instructive contrast is KMP from two chapters ago: KMP examines every
one of the n text characters (it's O(n) and never skips), while Boyer-Moore skips ahead and
examines fewer than n on average. Counting characters examined by each is what reveals
Boyer-Moore's sublinear behavior — and why real tools like grep are built on it.

`kmp_search` below returns matches AND its examined-character count, for the head-to-head.
"""


# region: kmp
def _prefix(pattern):
    m = len(pattern)
    lps = [0] * m
    k = 0
    for i in range(1, m):
        while k > 0 and pattern[i] != pattern[k]:
            k = lps[k - 1]
        if pattern[i] == pattern[k]:
            k += 1
        lps[i] = k
    return lps


def kmp_search(text, pattern):
    """KMP with an examined-character counter. It reads every text character (advancing i through
    all n), so its count is ~n regardless of pattern length — the flat baseline Boyer-Moore beats
    by skipping. Returns (matches, examined)."""
    if not pattern:
        return list(range(len(text) + 1)), 0
    lps = _prefix(pattern)
    matches, examined, j = [], 0, 0
    for i in range(len(text)):
        examined += 1                            # KMP looks at every text character exactly once here
        while j > 0 and text[i] != pattern[j]:
            j = lps[j - 1]
        if text[i] == pattern[j]:
            j += 1
        if j == len(pattern):
            matches.append(i - j + 1)
            j = lps[j - 1]
    return matches, examined
# endregion


# region: builtin
def find_all_builtin(text, pattern):
    """All occurrences via str.find — the trusted correctness reference."""
    if not pattern:
        return list(range(len(text) + 1))
    out, i = [], text.find(pattern)
    while i != -1:
        out.append(i)
        i = text.find(pattern, i + 1)
    return out
# endregion

Desde cero vs librería

Boyer-Moore contra KMP es un estudio de dos estrategias opuestas para el mismo problema, y ninguna es simplemente "mejor". KMP es parejo: lineal, determinista, examina cada carácter, nunca peor que $O(n)$ — el algoritmo que quieres cuando el peor caso importa o cuando el alfabeto es diminuto. Boyer-Moore es oportunista: apuesta a que la mayoría de las alineaciones se pueden descartar con un vistazo y un brinco grande, lo cual paga muchísimo con alfabetos grandes y patrones largos, pero puede degradarse con entrada repetitiva y adversarial. La línea descendente del enfrentamiento es la firma de esa apuesta saliendo bien. Es la misma tensión entre caso promedio y peor caso que vimos con quicksort (promedio rápido, peor caso cuadrático) contra merge sort (parejo) — y la respuesta práctica es la misma: ten claro en qué régimen estás. ¿Texto real sobre un alfabeto grande? Boyer-Moore, y por eso grep lo usa. ¿Entrada no confiable o un alfabeto diminuto? Una garantía lineal. En producción str.find elige un híbrido por ti; construir Boyer-Moore tú mismo es lo que convierte el "patrón más largo, búsqueda más rápida" en un hecho que mediste en lugar de una paradoja.

Dónde te lo vas a encontrar

Boyer-Moore y sus variantes son la búsqueda de subcadenas del mundo real. GNU grep usa Boyer-Moore-Horspool (y Commentz-Walter, un Boyer-Moore multipatrón, para varias cadenas fijas) — su famosa velocidad viene de saltarse entrada que nunca lee. Los editores de texto y los IDEs lo usan para el buscar-en-archivo. Muchas librerías estándar de lenguajes implementan indexOf/find/str.find con algoritmos de la familia Boyer-Moore o con híbridos de dos vías. Los antivirus y los detectores de intrusiones lo usan (junto con extensiones multipatrón) para cazar firmas. Aparece en análisis de logs, en rutinas de búsqueda de bytes tipo memmem metidas hasta el fondo de los sistemas operativos y en cualquier lugar donde haya que escanear grandes volúmenes de texto o datos binarios en busca de patrones fijos. Si alguna vez te sorprendió lo rápido que grep se come un archivo enorme, esta capacidad de saltar es la razón.

Puntos clave

Boyer-Moore busca comparando el patrón contra el texto de derecha a izquierda y, ante un mismatch, desplazando el patrón hacia adelante para alinear el carácter ofensor del texto con su ocurrencia más a la derecha en el patrón — brincando la longitud completa del patrón cuando ese carácter no está. Esto le permite examinar menos de $n$ caracteres, corriendo sublinealmente en promedio, con la propiedad singular de que un patrón más largo se busca más rápido (24× menos examinaciones que KMP con un patrón de longitud 64). La regla del mal carácter por sí sola tiene un peor caso cuadrático, curado por la regla del buen sufijo; la variante simplificada de Horspool es lo que en realidad traen la mayoría de las herramientas reales, incluido grep.

La trilogía de patrón único — el autómata de KMP, la huella digital de Rabin-Karp, los saltos de Boyer-Moore — queda completa: tres filosofías distintas para encontrar un solo patrón. Los siguientes dos capítulos cambian la pregunta. Los suffix arrays (el que sigue) preprocesan el texto mismo hacia un índice consultable, de modo que después de una construcción en $O(n \log n)$, cualquier patrón se puede encontrar en $O(m \log n)$ — el trade correcto cuando vas a buscar muchas veces sobre el mismo texto. Y Aho-Corasick construye un solo autómata para hacer match de miles de patrones a la vez. El campo se mueve de "buscar en un texto una vez" a "indexar un texto, o hacer match de muchos patrones" — los problemas que escalan.