Rabin-Karp y rolling hash

De qué trata este capítulo

KMP buscaba comparando caracteres de forma astuta. Rabin-Karp hace algo completamente distinto: compara números. Convierte el patrón en un solo entero con un hash, luego desliza una ventana sobre el texto convirtiendo cada ventana de longitud m en otro entero, y donde el número de la ventana sea igual al número del patrón, seguramente encontraste una coincidencia — una verificación rápida de caracteres lo confirma. Comparar dos enteros es una sola operación sin importar qué tan largas sean las cadenas, así que la búsqueda es rápida si puedes calcular el hash de cada ventana barato. La magia que lo hace barato es el rolling hash: cuando la ventana se desliza un carácter a la derecha, actualizas su hash en tiempo constante en lugar de recalcularlo desde cero. Este capítulo construye el rolling hash, muestra por qué el módulo hace que las colisiones sean astronómicamente raras, y demuestra el superpoder real de Rabin-Karp — buscar cientos de patrones en una sola pasada, donde KMP tendría que recorrer el texto una vez por patrón. En el enfrentamiento, eso es 200 veces más rápido.

Un poco de historia

Michael Rabin y Richard Karp presentaron el algoritmo en 1987, y su importancia no estuvo tanto en la velocidad bruta para un patrón — KMP ya la tenía — sino en una idea nueva: aplicar aleatorización y hashing al matching de cadenas. Rabin fue uno de los fundadores de la teoría de algoritmos aleatorizados (su trabajo sobre pruebas probabilísticas de primalidad es de la misma época), y Rabin-Karp es un pequeño ejemplo hermoso de esa filosofía: aceptar una probabilidad ínfima de error (una colisión de hash) a cambio de simplicidad y de una capacidad que los algoritmos deterministas no tienen. La técnica del rolling hash que usaron terminó siendo una de las ideas más reutilizables de toda la computación — ese mismo truco de fingerprinting mueve la transferencia delta de rsync, el chunking definido por contenido en sistemas de respaldo y deduplicación, los detectores de plagio y las heurísticas de diff de Git. Rabin-Karp es donde la mayoría conoce el rolling hash por primera vez, y el rolling hash acabó siendo más grande que el algoritmo.

La intuición

Asigna a cada carácter un valor numérico y lee una cadena como un número en cierta base — "abc" se vuelve, digamos, a·B² + b·B + c para una base B. Eso es un hash polinomial, y dos cadenas distintas casi siempre producen números distintos (reducimos módulo un primo grande para mantener los números acotados, y esa es la única fuente de posibles colisiones). Ahora el plan ingenuo es claro: calcula el hash del patrón una vez, y para cada ventana del texto calcula su hash y compara. Pero calcular el hash de una ventana desde cero cuesta O(m), y hay n ventanas, así que eso es O(n·m) — nada mejor que el matching ingenuo.

El rolling hash elimina ese desperdicio. Mira dos ventanas adyacentes: comparten todo excepto un carácter en cada extremo. Cuando la ventana se desliza una posición a la derecha, el carácter más a la izquierda sale y un carácter nuevo entra por la derecha. Su hash cambia de una forma predecible y en O(1): resta la contribución del carácter que sale (su valor por la base elevada a la longitud de la ventana), multiplica el resto por la base para recorrer a todos un lugar, y suma el carácter nuevo. Una resta, una multiplicación y una suma — el hash de la siguiente ventana a partir del de la actual, sin mirar los m−2 caracteres de en medio. Así cada ventana cuesta O(1) de hashear, todo el barrido es O(n), y el matching queda en O(n+m) esperado. Cuando hay coincidencia de hash haces una comparación honesta de caracteres para descartar la colisión rara, y listo.

Complejidad: cómo escala

Rabin-Karp es $O(n + m)$ esperado: $O(m)$ para hashear el patrón y la primera ventana, luego $O(1)$ por deslizamiento para $n$ ventanas, más el costo de verificación, que es despreciable cuando las colisiones son raras. Su peor caso es $O(n \cdot m)$ — si un adversario fabrica muchas colisiones de hash, cada ventana dispara una verificación completa de caracteres — pero con un módulo bueno y suficientemente aleatorio eso es astronómicamente improbable con entradas reales (la prueba de correctitud corrió dos mil búsquedas con cero colisiones espurias). Para un solo patrón, esto no es mejor asintóticamente que KMP, y en la práctica es más lento, porque KMP es determinista y no hashea. La ventaja real de Rabin-Karp aparece con muchos patrones, que es lo que mide el enfrentamiento — buscando k patrones de la misma longitud, Rabin-Karp en una pasada contra KMP corrido k veces:

Para un solo patrón los dos son comparables (KMP hasta saca ventaja, por ser determinista). Pero mira lo que pasa conforme crece la cantidad de patrones: el tiempo de KMP sube linealmente con k, porque tiene que barrer los 200,000 caracteres del texto completo una vez por cada patrón, mientras que Rabin-Karp barre el texto una sola vez y checa el hash de cada ventana contra un conjunto con los k hashes de patrones en O(1). Con 800 patrones, Rabin-Karp terminó en unos 29 ms y KMP-por-patrón se tardó 5.8 segundos — 200 veces más rápido. Ese es el premio de convertir cadenas en números: un número se puede buscar en un hash set, así que una sola pasada responde "¿esta ventana coincide con alguno de mis patrones?" tan barato como responde "¿coincide con este?".

En qué es bueno y en qué no

Rabin-Karp brilla donde hashear una ventana rinde a lo largo de muchas comparaciones. Su uso estelar es la búsqueda multi-patrón: escáneres de virus, firmas de detección de intrusos y filtros de spam que cazan muchas cadenas fijas a la vez checan el hash de cada ventana del texto contra un conjunto de hashes de patrones en una sola pasada. Se extiende de forma natural al matching de patrones en dos dimensiones (encontrar un parche de imagen de a×b dentro de una imagen más grande, hasheando filas y luego columnas), algo que KMP no hace con gracia. Y el rolling hash por sí solo — independiente de la búsqueda — es el caballito de batalla del fingerprinting: rsync y los sistemas de respaldo encuentran bloques que coinciden entre archivos rodando un hash para localizar chunks compartidos; las herramientas de plagio y detección de duplicados generan fingerprints de subcadenas traslapadas; Git usa ideas de rolling hash en su diff y en su empaquetado. Aprender Rabin-Karp es en realidad aprender el rolling hash, que es el premio más valioso.

Donde Rabin-Karp es la herramienta equivocada es en búsqueda exacta de un solo patrón sobre entradas adversariales o no confiables, donde su naturaleza probabilística y su peor caso cuadrático son desventajas que KMP y Boyer-Moore evitan. El requisito de que todos los patrones midan lo mismo para la búsqueda multi-patrón es una restricción real (patrones de distintas longitudes necesitan un rolling hash por longitud, o una estructura diferente), y para conjuntos de patrones grandes o dinámicos la herramienta correcta es Aho-Corasick (un capítulo posterior), que construye un solo autómata para todos los patrones de cualquier longitud. Y en código cotidiano de un solo patrón simplemente llamarías a str.find. El nicho de Rabin-Karp es muchos patrones, multi-dimensional y fingerprinting — no ganarle a KMP en su propio juego de un patrón.

Los datos, o las entradas

El enfrentamiento busca en un texto aleatorio de 200,000 caracteres una cantidad creciente de patrones de longitud 8, midiendo la pasada multi-patrón única de Rabin-Karp contra correr KMP una vez por patrón. La correctitud se checa de dos formas: en dos mil búsquedas aleatorias las coincidencias de Rabin-Karp deben ser iguales a las de str.find de Python (y la corrida reporta cuántas colisiones espurias ocurrieron — cero, lo que confirma el módulo), y la búsqueda multi-patrón debe coincidir con correr KMP sobre cada patrón por separado. La animación corre una búsqueda de un solo patrón de abc en aabbaabca usando un módulo deliberadamente diminuto (101) para que los números del hash sean chicos y legibles — el código real usa un primo enorme, pero el chiquito muestra la aritmética del roll con claridad.

Constrúyelo, una función a la vez

El rolling hash y la búsqueda de un solo patrón — hashea una vez, luego rueda en O(1):

def _hash(s):
    """The polynomial hash of a whole string: s[0]*BASE^(m-1) + ... + s[m-1], mod MOD. This is
    the string read as a big base-256 number, reduced modulo a prime to keep it bounded."""
    h = 0
    for ch in s:
        h = (h * BASE + ord(ch)) % MOD
    return h


def rabin_karp(text, pattern):
    """Find every occurrence of `pattern` in `text` with a rolling hash. Hash the pattern and
    the first window once; then slide, updating the window hash in O(1) each step; on a hash
    match, VERIFY the characters (to rule out the rare collision). O(n+m) expected. Returns
    (matches, spurious) where `spurious` counts hash matches that failed verification — the
    collisions the modulus is chosen to make vanishingly rare."""
    n, m = len(text), len(pattern)
    if m == 0:
        return list(range(n + 1)), 0
    if m > n:
        return [], 0
    high = pow(BASE, m - 1, MOD)                 # BASE^(m-1): the weight of the leftmost char
    ph = _hash(pattern)
    wh = _hash(text[:m])                         # hash of the first window
    matches, spurious = [], 0
    for i in range(n - m + 1):
        if wh == ph:                             # numbers agree → probable match
            if text[i:i + m] == pattern:         # confirm with a real character comparison
                matches.append(i)
            else:
                spurious += 1                    # a hash collision, not a real match
        if i < n - m:                            # roll the window forward by one, in O(1)
            wh = ((wh - ord(text[i]) * high) * BASE + ord(text[i + m])) % MOD
    return matches, spurious

Y el superpoder — muchos patrones en una sola pasada, mediante un conjunto de hashes de patrones:

def rabin_karp_multi(text, patterns):
    """Rabin-Karp's superpower: search for MANY patterns of the same length in a single pass.
    Hash every pattern into a dict (hash → patterns), then roll one hash across the text and,
    at each window, look up its hash in the dict — O(1) — verifying any candidates. One sweep
    of the text finds all k patterns, where running a single-pattern search k times would sweep
    it k times. Returns {pattern: [positions]}."""
    m = len(next(iter(patterns)))
    assert all(len(p) == m for p in patterns), "multi-search needs equal-length patterns"
    by_hash = {}
    for p in patterns:
        by_hash.setdefault(_hash(p), []).append(p)
    n = len(text)
    found = {p: [] for p in patterns}
    if m > n:
        return found
    high = pow(BASE, m - 1, MOD)
    wh = _hash(text[:m])
    for i in range(n - m + 1):
        if wh in by_hash:                        # this window matches some pattern's hash
            window = text[i:i + m]
            for p in by_hash[wh]:
                if window == p:
                    found[p].append(i)
        if i < n - m:
            wh = ((wh - ord(text[i]) * high) * BASE + ord(text[i + m])) % MOD
    return found

Míralo funcionar

Aquí está Rabin-Karp buscando abc en aabbaabca, con un hash de juguete (cada letra es un dígito chico, módulo 101) para que puedas leer los números. El patrón abc hashea a 22. La ventana azul se desliza por el texto un carácter a la vez; en cada paso, el carácter verde es el que acaba de entrar por la derecha y el rojo es el que acaba de salir — los únicos dos que el rolling hash necesita para actualizar el número en O(1). Observa cómo cambia el hash de la ventana con cada roll, comparado contra 22. La mayoría de las ventanas no coinciden y siguen rodando; cuando la ventana sobre abc por fin hashea a 22, una verificación rápida de caracteres confirma que es una coincidencia real y no una colisión, en la posición 5. Los caracteres de en medio de la ventana nunca se releen — ese es todo el punto de rodar:

El código completo

La pestaña "desde cero" es Rabin-Karp — rolling hash, búsqueda de un solo patrón y la pasada multi-patrón; la pestaña de librería es KMP del capítulo pasado, usado tanto para checar correctitud como para el costo por patrón en el enfrentamiento, más la referencia con str.find. Cambia entre ellas.

"""Rabin-Karp — substring search by HASHING. KMP compared characters; Rabin-Karp compares
numbers. Turn the pattern into a single number (a hash of its characters), then slide a
window across the text turning each length-m window into a number too, and wherever the
window's number equals the pattern's number, you've probably found a match — verify it
character by character to be sure. Comparing two integers is O(1), so if you can compute each
window's hash cheaply, the whole search is fast.

The trick that makes it cheap is a ROLLING HASH: when the window slides one character right,
you don't recompute its hash from scratch (that would be O(m) per window, O(n·m) overall).
Instead you update it in O(1) — subtract the contribution of the character leaving on the
left, shift, and add the character entering on the right. That's the whole idea, and it has
a superpower KMP lacks: to search for MANY patterns of the same length at once, you hash the
text windows just once and check each against a whole SET of pattern hashes.
"""

BASE = 256          # treat the string as a base-256 number (one byte per char)
MOD = (1 << 61) - 1  # a large Mersenne prime → collisions astronomically unlikely


# region: rolling_hash
def _hash(s):
    """The polynomial hash of a whole string: s[0]*BASE^(m-1) + ... + s[m-1], mod MOD. This is
    the string read as a big base-256 number, reduced modulo a prime to keep it bounded."""
    h = 0
    for ch in s:
        h = (h * BASE + ord(ch)) % MOD
    return h


def rabin_karp(text, pattern):
    """Find every occurrence of `pattern` in `text` with a rolling hash. Hash the pattern and
    the first window once; then slide, updating the window hash in O(1) each step; on a hash
    match, VERIFY the characters (to rule out the rare collision). O(n+m) expected. Returns
    (matches, spurious) where `spurious` counts hash matches that failed verification — the
    collisions the modulus is chosen to make vanishingly rare."""
    n, m = len(text), len(pattern)
    if m == 0:
        return list(range(n + 1)), 0
    if m > n:
        return [], 0
    high = pow(BASE, m - 1, MOD)                 # BASE^(m-1): the weight of the leftmost char
    ph = _hash(pattern)
    wh = _hash(text[:m])                         # hash of the first window
    matches, spurious = [], 0
    for i in range(n - m + 1):
        if wh == ph:                             # numbers agree → probable match
            if text[i:i + m] == pattern:         # confirm with a real character comparison
                matches.append(i)
            else:
                spurious += 1                    # a hash collision, not a real match
        if i < n - m:                            # roll the window forward by one, in O(1)
            wh = ((wh - ord(text[i]) * high) * BASE + ord(text[i + m])) % MOD
    return matches, spurious
# endregion


# region: multi
def rabin_karp_multi(text, patterns):
    """Rabin-Karp's superpower: search for MANY patterns of the same length in a single pass.
    Hash every pattern into a dict (hash → patterns), then roll one hash across the text and,
    at each window, look up its hash in the dict — O(1) — verifying any candidates. One sweep
    of the text finds all k patterns, where running a single-pattern search k times would sweep
    it k times. Returns {pattern: [positions]}."""
    m = len(next(iter(patterns)))
    assert all(len(p) == m for p in patterns), "multi-search needs equal-length patterns"
    by_hash = {}
    for p in patterns:
        by_hash.setdefault(_hash(p), []).append(p)
    n = len(text)
    found = {p: [] for p in patterns}
    if m > n:
        return found
    high = pow(BASE, m - 1, MOD)
    wh = _hash(text[:m])
    for i in range(n - m + 1):
        if wh in by_hash:                        # this window matches some pattern's hash
            window = text[i:i + m]
            for p in by_hash[wh]:
                if window == p:
                    found[p].append(i)
        if i < n - m:
            wh = ((wh - ord(text[i]) * high) * BASE + ord(text[i + m])) % MOD
    return found
# endregion

"""The library counterpart and the contrast. For a single pattern you'd use Python's built-in
`str.find` (C, hybrid two-way) — that's the correctness reference. The instructive contrast for
Rabin-Karp's multi-pattern superpower is KMP from last chapter: to search for k patterns with a
single-pattern algorithm, you run it k times, sweeping the text once per pattern. Rabin-Karp
sweeps once for all k.

`kmp_search` below is last chapter's KMP, used both to cross-check correctness and to time the
"k separate searches" strategy against Rabin-Karp's single multi-pattern pass. (For genuinely
large pattern sets, the right tool is Aho-Corasick, a later chapter — Rabin-Karp multi-search is
the simplest way to see why one pass beats k.)
"""


# 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):
    """Last chapter's linear-time single-pattern search — the deterministic contrast to
    Rabin-Karp's hashing, and the per-pattern cost when searching a set the naive way."""
    if not pattern:
        return list(range(len(text) + 1))
    lps = _prefix(pattern)
    matches, j = [], 0
    for i in range(len(text)):
        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
# 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

Rabin-Karp y KMP resuelven el mismo problema de un solo patrón con filosofías opuestas, y el contraste es la lección. KMP es determinista: nunca se equivoca, y explota la estructura del patrón. Rabin-Karp es probabilístico: acepta una probabilidad de $10^{-18}$ de colisión (que de todos modos la verificación atrapa) a cambio de convertir cadenas en números — y los números se pueden hashear, checar como pertenencia a un conjunto y comparar en O(1) sin importar su longitud, que es lo que desbloquea la búsqueda multi-patrón y multi-dimensional. Ese es un intercambio general que vale la pena interiorizar: la aleatorización y el hashing muchas veces te compran capacidades, no nada más velocidad — la habilidad de generar fingerprints, deduplicar y comparar en lote — que los métodos deterministas no igualan tan fácil. Para un solo patrón usarías str.find; para muchos patrones irías por Aho-Corasick o, para lo más simple que funciona, exactamente esto. Construir tú mismo el rolling hash es lo que después te hace legibles a rsync y al chunking definido por contenido — al final todos son esta misma actualización en O(1).

Dónde te lo vas a encontrar

El rolling hash es una de las ideas más desplegadas del software de sistemas. rsync y la deduplicación de respaldos en la nube lo usan para encontrar bloques coincidentes entre archivos sin transferirlos, rodando un hash para detectar contenido compartido incluso cuando los datos se recorren. El chunking definido por contenido (en respaldos, registries de contenedores y el empaquetado de Git) usa fronteras basadas en rolling hash para partir archivos en chunks estables. Los detectores de plagio y la búsqueda de casi-duplicados generan fingerprints de documentos con rolling hashes traslapados (la técnica de "winnowing"). Los motores de detección de intrusos y antivirus hacen match de muchas firmas a la vez con hashing multi-patrón estilo Rabin-Karp. La bioinformática lo usa para indexar k-mers de ADN. Y es un básico de la programación competitiva para igualdad de cadenas y matching en 2-D. Donde sea que necesites comparar o hacer fingerprint de subcadenas de forma barata y en volumen, hay un rolling hash haciendo el trabajo.

Puntos clave

Rabin-Karp busca hasheando: un rolling hash polinomial convierte cada ventana de texto de longitud m en un número en O(1) por deslizamiento, se comparan números en lugar de cadenas, y una verificación de caracteres confirma cada coincidencia de hash para atrapar la colisión astronómicamente rara — O(n+m) esperado. Para un patrón es una alternativa probabilística a KMP sin ventaja asintótica, pero sus fortalezas son únicas: buscar muchos patrones de igual longitud en una sola pasada (200× más rápido que KMP-por-patrón con 800 patrones), matching en dos dimensiones y — lo más valioso — el rolling hash mismo, la primitiva de fingerprinting detrás de rsync, la deduplicación y la detección de plagio.

El siguiente capítulo vuelve a la búsqueda determinista de un solo patrón, pero le da la vuelta a la dirección del escaneo. Boyer-Moore hace match del patrón de derecha a izquierda y, cuando falla, usa lo que aprendió para saltar hacia adelante muchos caracteres de golpe — muchas veces brincándose tramos enteros del texto, de modo que examina menos de n caracteres en promedio. Donde KMP y Rabin-Karp leen cada carácter del texto, Boyer-Moore lee solo una fracción, y por eso es el algoritmo que vive dentro de grep.