Búsqueda ingenua y KMP

Lo que cubre este capítulo

Encontrar un patrón dentro de un texto es una de las operaciones que más se ejecutan en computación: cada caja de búsqueda, cada grep, cada Ctrl-F lo hace. El método obvio es probar el patrón en cada posición y comparar carácter por carácter, y funciona, pero tiene un modo de falla feo: con la entrada equivocada vuelve a revisar los mismos caracteres del texto una y otra vez, y eso cuesta O(n·m). El algoritmo de Knuth-Morris-Pratt arregla esto con una sola idea: cuando ocurre un mismatch después de que varios caracteres ya coincidieron, esos caracteres coincidentes son información, un prefijo conocido del patrón, y puedes usarlos para deslizar el patrón hacia adelante más de una posición sin releer texto por el que ya pasaste. El puntero del texto nunca retrocede. Este capítulo construye el matcher ingenuo, luego KMP y su función de fallo precalculada, observa cómo el patrón se desliza sobre un texto sin rebobinar, y mide la diferencia con una entrada adversaria: 25 veces menos comparaciones de caracteres.

Un poco de historia

El algoritmo se publicó en 1977 por Donald Knuth, James Morris y Vaughan Pratt, pero su descubrimiento fue una convergencia a tres bandas que vale la pena contar. Morris lo había deducido en 1970 mientras escribía un editor de texto y le fastidiaba el retroceso de la búsqueda ingenua; Pratt desarrolló ideas relacionadas; y Knuth, estudiando un teorema de Stephen Cook sobre qué lenguajes podía reconocer en tiempo lineal cierto tipo de autómata, derivó esencialmente el mismo algoritmo desde la pura teoría. Cuando los tres se dieron cuenta de que habían encontrado lo mismo por separado, publicaron juntos. Ese origen —una ruta desde el fastidio práctico de un editor lento, otra desde la teoría de autómatas— ilustra bien que KMP en realidad se trata de una máquina: la función de fallo convierte el patrón en un autómata finito que lee el texto una sola vez, de izquierda a derecha, sin rebobinar nunca. Fue el primer algoritmo de búsqueda de subcadenas demostrado lineal en el peor caso, y abrió el campo del matching eficiente de cadenas que explora el resto de este nivel.

La intuición

Mira fallar al matcher ingenuo. Buscando ababc en abababca, hace match con abab y luego choca con un mismatch en el quinto carácter. La respuesta ingenua es encogerse de hombros, deslizar el patrón una posición a la derecha y empezar a comparar desde cero, releyendo caracteres del texto que ya había mirado. Pero eso es un desperdicio, porque sabe que los últimos cuatro caracteres del texto eran abab, y puede razonar sobre lo que eso implica sin releerlos. El prefijo abab tiene un prefijo propio (ab) que es igual a su sufijo (ab), lo que significa que después del mismatch el patrón puede deslizarse para que esos dos caracteres queden alineados y el matching se reanude desde el tercer carácter del patrón: sin rebobinar, sin volver a comparar.

Ese razonamiento queda capturado, una sola vez, en la función de fallo (o función de prefijo): para cada posición del patrón, la longitud del prefijo propio más largo del patrón-hasta-ahí que también es sufijo de él. Cuando ocurre un mismatch después de haber coincidido j caracteres, la tabla dice "puedes actuar como si hubieran coincidido lps[j-1] caracteres": el patrón se desliza hacia adelante j - lps[j-1] posiciones y el puntero del texto se queda donde está. Lo bonito es que la función de fallo se construye aplicando esta misma lógica del patrón contra sí mismo, en O(m). Una vez que la tienes, la búsqueda es un solo barrido de izquierda a derecha del texto donde i nunca hace más que aumentar: cada carácter del texto se mira esencialmente una vez, lo que da O(n). El patrón se vuelve una pequeña máquina de estados, y el texto fluye a través de ella.

Complejidad: cómo escala

KMP es $O(n + m)$: $O(m)$ para construir la tabla de fallo y $O(n)$ para recorrer el texto, porque el puntero del texto i avanza monótonamente por los n caracteres y el puntero del patrón j, aunque puede retroceder, retrocede un total acotado por lo que avanzó — un argumento amortizado que mantiene lineal todo el barrido. El matcher ingenuo es $O(n \cdot m)$ en el peor caso. Y ese peor caso no es exótico; es un texto y un patrón muy repetitivos, exactamente lo que aparece en ADN, en logs, en cualquier dato de alfabeto pequeño. El enfrentamiento corre la entrada adversaria clásica: un texto de puras a y un patrón de a terminado en una b, lo que obliga al matcher ingenuo a re-escanear casi todo el patrón en cada posición:

Con un texto de 8000 caracteres y un patrón de 50, el matcher ingenuo hizo cerca de 398,000 comparaciones de caracteres mientras que KMP hizo unas 16,000 — unas 25 veces menos, y la brecha se ensancha conforme crece la longitud del patrón, porque el costo del ingenuo es $n \cdot m$ mientras que el de KMP es $n + m$. La línea del ingenuo sube en picada; la de KMP apenas se levanta. Esa diferencia es el valor de no rebobinar nunca: con entrada adversaria el ingenuo relee cada carácter del texto hasta m veces, KMP lo lee esencialmente una. Con texto aleatorio sobre un alfabeto grande los dos quedan más parejos (los mismatches llegan rápido, así que el ingenuo rara vez se mete profundo en el patrón), pero la garantía de KMP —lineal sin importar la entrada— es lo que lo hace seguro donde el ingenuo es una bomba cuadrática latente.

En qué es bueno y en qué no

KMP es la herramienta correcta cuando necesitas una búsqueda de un solo patrón garantizada lineal y no puedes arriesgarte al estallido cuadrático del ingenuo: datos en streaming donde ves cada carácter una vez y no puedes rebobinar, sistemas de tiempo real donde importa la latencia del peor caso, o texto muy repetitivo (secuencias biológicas, logs de sensores, protocolos binarios) donde el ingenuo de verdad se degrada. Su función de fallo es además un objeto reutilizable con valor propio: revela la estructura periódica de una cadena (el periodo más corto de s es len(s) - lps[-1]), lo que resuelve toda una familia de problemas de periodicidad de cadenas, y la visión de autómata está detrás de los matchers de patrones en streaming y en hardware.

Donde KMP no es el más rápido es en la búsqueda de texto común sobre un alfabeto grande, donde Boyer-Moore (próximos capítulos) suele ser más veloz en la práctica porque salta hacia adelante escaneando el patrón de derecha a izquierda y puede brincarse muchos caracteres de un jalón: KMP examina cada carácter del texto, Boyer-Moore a menudo examina una fracción de ellos. Para varios patrones a la vez, Aho-Corasick generaliza el autómata de KMP y es la elección correcta. Y en código del día a día simplemente llamarías a str.find, cuya implementación en C usa un algoritmo híbrido que normalmente es más rápido que un KMP hecho a mano. El papel de KMP es ser el cimiento lineal garantizado y la puerta conceptual, no necesariamente el campeón de velocidad.

Los datos, o las entradas

El enfrentamiento corre el caso adversario canónico —un texto con n copias de a y un patrón de 49 a seguidas de una b— y cuenta comparaciones de caracteres de KMP contra el matcher ingenuo conforme crece n, aislando la brecha cuadrático-contra-lineal. La corrección se verifica duro: con dos mil pares aleatorios de texto/patrón sobre varios alfabetos, las posiciones de match de KMP deben ser iguales tanto a las del str.find integrado de Python como a las del matcher ingenuo, y la función de fallo se verifica por separado contra su definición por fuerza bruta (el prefijo-sufijo realmente más largo en cada posición). La animación corre KMP buscando ababc en abababca, dibujando el texto y el patrón deslizante como dos filas de caracteres.

Constrúyelo, una función a la vez

La función de fallo — toda la astucia, el patrón comparado contra sí mismo:

def prefix_function(pattern):
    """The failure table. lps[i] = length of the longest proper prefix of pattern[:i+1] that
    is also a suffix of it. Built in O(m) by extending the previous longest prefix-suffix and
    falling back through the table on mismatch — the same trick the search itself uses, run on
    the pattern against itself. This is the whole cleverness of KMP; the search is easy once
    you have it."""
    m = len(pattern)
    lps = [0] * m
    k = 0                                        # length of the current longest prefix-suffix
    for i in range(1, m):
        while k > 0 and pattern[i] != pattern[k]:
            k = lps[k - 1]                        # fall back to the next-best prefix-suffix
        if pattern[i] == pattern[k]:
            k += 1
        lps[i] = k
    return lps

Y la búsqueda que la usa — un solo barrido donde el puntero del texto nunca rebobina:

def kmp_search(text, pattern):
    """Every start index where `pattern` occurs in `text`. Walk the text with pointer i (never
    decreasing) and the pattern with pointer j; on a mismatch, slide the pattern using the
    failure table (j = lps[j-1]) instead of resetting to 0 and rewinding i. O(n + m). Returns
    (match_positions, comparisons) — the comparison count exposes why it beats naive search."""
    if not pattern:
        return list(range(len(text) + 1)), 0
    lps = prefix_function(pattern)
    matches = []
    comparisons = 0
    j = 0                                        # how many pattern chars currently match
    for i in range(len(text)):                   # i, the text pointer, only ever increases
        while j > 0 and text[i] != pattern[j]:
            comparisons += 1
            j = lps[j - 1]                        # use the table to slide, don't rewind i
        comparisons += 1
        if text[i] == pattern[j]:
            j += 1
        if j == len(pattern):
            matches.append(i - j + 1)             # full match ending at i
            j = lps[j - 1]                        # keep scanning for overlapping matches
    return matches, comparisons

Míralo funcionar

Aquí está KMP buscando ababc (fila de abajo) en abababca (fila de arriba). Azul es el carácter que se está comparando en este paso; verde son las celdas que coincidieron en la alineación actual; rojo es un mismatch. Fíjate en lo que pasa en el primer mismatch: después de que abab coincide, la quinta comparación falla, pero en vez de deslizar el patrón un paso y releer, KMP consulta la tabla de fallo y desliza el patrón para que su prefijo ab se alinee con el ab que ya había coincidido, reanudando desde en medio del patrón sin que el puntero del texto se mueva hacia atrás. El patrón parece brincar hacia adelante más de una posición. Unas comparaciones después se engancha con el match completo en la posición 2. Los caracteres del texto, arriba, se leen esencialmente una sola vez: el patrón hace todo el deslizamiento:

El código completo

La pestaña "desde cero" es KMP con su función de fallo; la pestaña de librería es el matcher ingenuo contra el que se compara (y la referencia str.find integrada que se usa para verificar la corrección). Cámbiate entre ellas: la versión ingenua es más corta, y esa brevedad es justamente la trampa: es simple porque relee, y releer es lo que la hace cuadrática.

"""Knuth-Morris-Pratt (KMP) — find every occurrence of a pattern in a text without ever
backing up in the text. The naive way to search slides the pattern one position and, on a
mismatch, throws away everything it just learned and re-compares from scratch — which on
adversarial input costs O(n·m). KMP's insight is that a mismatch is not ignorance: the
characters that DID match are a known prefix of the pattern, and that prefix often overlaps
a suffix of itself, so the pattern can be slid forward by more than one without missing
anything, and the text pointer never moves backward.

The magic is a small precomputed table, the PREFIX FUNCTION (or "failure function"): for
each position in the pattern, the length of the longest proper prefix that is also a suffix
of the pattern up to that point. That table says, on a mismatch after matching j characters,
"you can resume as if j' < j characters had matched" — skipping the re-comparisons the naive
search would redo. Build the table in O(m), scan in O(n), and matching is O(n+m).
"""


# region: prefix_function
def prefix_function(pattern):
    """The failure table. lps[i] = length of the longest proper prefix of pattern[:i+1] that
    is also a suffix of it. Built in O(m) by extending the previous longest prefix-suffix and
    falling back through the table on mismatch — the same trick the search itself uses, run on
    the pattern against itself. This is the whole cleverness of KMP; the search is easy once
    you have it."""
    m = len(pattern)
    lps = [0] * m
    k = 0                                        # length of the current longest prefix-suffix
    for i in range(1, m):
        while k > 0 and pattern[i] != pattern[k]:
            k = lps[k - 1]                        # fall back to the next-best prefix-suffix
        if pattern[i] == pattern[k]:
            k += 1
        lps[i] = k
    return lps
# endregion


# region: kmp_search
def kmp_search(text, pattern):
    """Every start index where `pattern` occurs in `text`. Walk the text with pointer i (never
    decreasing) and the pattern with pointer j; on a mismatch, slide the pattern using the
    failure table (j = lps[j-1]) instead of resetting to 0 and rewinding i. O(n + m). Returns
    (match_positions, comparisons) — the comparison count exposes why it beats naive search."""
    if not pattern:
        return list(range(len(text) + 1)), 0
    lps = prefix_function(pattern)
    matches = []
    comparisons = 0
    j = 0                                        # how many pattern chars currently match
    for i in range(len(text)):                   # i, the text pointer, only ever increases
        while j > 0 and text[i] != pattern[j]:
            comparisons += 1
            j = lps[j - 1]                        # use the table to slide, don't rewind i
        comparisons += 1
        if text[i] == pattern[j]:
            j += 1
        if j == len(pattern):
            matches.append(i - j + 1)             # full match ending at i
            j = lps[j - 1]                        # keep scanning for overlapping matches
    return matches, comparisons
# endregion

"""The library counterpart and the contrast. In real code you never hand-roll substring
search — you use Python's built-in, which is C-fast:

    text.find(pattern)          # first occurrence, or -1
    pattern in text             # membership
    [m.start() for m in re.finditer(re.escape(pattern), text)]   # all occurrences

CPython's `str.find` uses a hybrid of Crochemore-Perrin ("two-way") and Boyer-Moore-Horspool
ideas, not textbook KMP, but the guarantee is the same linear-time worst case. `find_all_builtin`
below wraps it as the correctness reference (all occurrences). `naive_search` is the contrast
that makes KMP's point — the straightforward O(n·m) method that rewinds and re-compares, whose
comparison count blows up on adversarial input.
"""


# region: naive
def naive_search(text, pattern):
    """The obvious algorithm: try the pattern at every start position, comparing left to right,
    and on any mismatch abandon this position and try the next — re-examining text characters it
    already looked at. O(n·m) worst case. Returns (match_positions, comparisons)."""
    n, m = len(text), len(pattern)
    if m == 0:
        return list(range(n + 1)), 0
    matches, comparisons = [], 0
    for start in range(n - m + 1):
        k = 0
        while k < m:
            comparisons += 1
            if text[start + k] != pattern[k]:
                break                             # mismatch → give up, slide by one, redo from k=0
            k += 1
        if k == m:
            matches.append(start)
    return matches, comparisons
# endregion


# region: builtin
def find_all_builtin(text, pattern):
    """All occurrences via Python's built-in str.find — the trusted reference for correctness."""
    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)             # +1 allows overlapping matches
    return out
# endregion

Desde cero vs librería

La comparación aquí es KMP contra el matcher ingenuo, y es un ejemplo limpio de un tema recurrente: el algoritmo más simple no está mal, está frágil. La búsqueda ingenua da respuestas correctas y muchas veces es perfectamente rápida — con texto en inglés aleatorio rara vez avanza más de uno o dos caracteres dentro del patrón antes de un mismatch, así que su costo práctico es casi lineal. Pero no tiene piso: dale entrada repetitiva y se degrada a cuadrático en silencio, el mismo riesgo de cuadrático latente que usar Dijkstra con aristas negativas o el pivote equivocado en quicksort. KMP cambia un poco de precálculo y una tabla por una garantía: lineal, siempre, sea cual sea la entrada. Ese es el trade-off de ingeniería que la literatura de string matching sigue haciendo: paga un setup O(m) para comprar una cota de peor caso. En producción llamarías a str.find, cuyo híbrido compilado le gana a un KMP a nivel de Python; construir KMP tú mismo es lo que hace que la función de fallo —reutilizada, en formas más ricas, por Boyer-Moore y Aho-Corasick más adelante— sea algo que entiendes en lugar de algo que invocas.

Dónde te lo vas a encontrar de verdad

KMP y su función de fallo corren por todo el procesamiento de texto. grep, los editores de texto y las cajas de búsqueda usan matching en tiempo lineal (a menudo Boyer-Moore o híbridos, con la garantía de KMP como respaldo). Las herramientas de bioinformática buscan en secuencias de ADN y proteínas, exactamente los datos repetitivos de alfabeto pequeño donde la búsqueda ingenua se colapsa. Los sistemas de detección de intrusos y los antivirus escanean flujos de red buscando patrones de firma en una sola pasada, algo que la propiedad de no-rebobinar de KMP hace posible sobre datos en streaming. La función de fallo por sí sola aparece dondequiera que importe la periodicidad de una cadena: encontrar la unidad repetitiva más pequeña de una cadena, detectar repeticiones en tándem, compresión de cadenas. Y KMP es el padre conceptual de Aho-Corasick, el matcher multi-patrón detrás de muchas de estas mismas herramientas. Donde sea que haya que encontrar un solo patrón en un flujo con garantía de peor caso, KMP es el cimiento.

Puntos clave

KMP encuentra todas las ocurrencias de un patrón en $O(n+m)$ precalculando una función de fallo —el prefijo propio más largo que también es sufijo en cada posición— y usándola, ante un mismatch, para deslizar el patrón hacia adelante sin rebobinar nunca el puntero del texto. La tabla de fallo se construye con la misma lógica corrida sobre el patrón contra sí mismo, y el barrido lineal se sigue de un argumento amortizado: el puntero del patrón solo puede retroceder tanto como avanzó. Contra el matcher ingenuo $O(n·m)$ hizo 25 veces menos comparaciones con entrada adversaria, cambiando un pequeño precálculo por una garantía de peor caso que el método ingenuo no puede ofrecer.

El siguiente capítulo ataca el mismo problema desde un ángulo completamente distinto. Rabin-Karp convierte cada ventana de longitud m del texto en un número usando un rolling hash y compara números en lugar de cadenas — normalmente O(n+m), ocasionalmente engañado por colisiones de hash, y especialmente adecuado para buscar muchos patrones o patrones bidimensionales a la vez. Donde KMP es un autómata determinista, Rabin-Karp es una huella probabilística, y el contraste entre ambos es el contraste entre las dos grandes estrategias de búsqueda en cadenas.