Lumænaut_

Búsqueda difusa de cadenas con Bitap: de lo ingenuo a lo eficiente

Un gran agradecimiento a Cassidy Williams (y su increíble boletín Cassidoo ) por el acertijo de entrevista de esta semana. ¿El reto? Implementar una búsqueda difusa de cadenas con el algoritmo Bitap — y encontrar todas las coincidencias con hasta k errores. Esta entrada recorre el problema, las matemáticas y el código — desde la mentalidad de fuerza bruta hasta la solución elegante de bit-paralelismo que convierte a Bitap en leyenda.

Si vas a subir de nivel con algoritmos de cadenas, ponte el cinturón. Escribiremos Python en el que puedas confiar — legible, comprobable y ligado al mismo modelo de distancia Levenshtein que los matchers bit-paralelos de producción se comprometen a respetar — y de paso nos aseguraremos de que entiendas de verdad por qué Bitap funciona.

El planteamiento del problema

“Dada una cadena de texto y un patrón, implementa una búsqueda difusa de cadenas usando el algoritmo Bitap que encuentre todas las posiciones del texto donde el patrón coincida con como máximo k errores (inserciones, borrados o sustituciones). Devuelve un arreglo de objetos con la posición y el número de errores de cada coincidencia.”

Ejemplo:

> fuzzySearch("the cat sat on the mat", "cat", 0);
> [{ position: 4, errors: 0 }]

> fuzzySearch("cassidoo", "cool", 1);
> []

> fuzzySearch("cassidoo", "cool", 3);
> [{ "position": 0, "errors": 3 }, { "position": 4, "errors": 3 }]
          

(Nota: Con k = 3, ambas coincidencias alinean "cool" con el trozo de texto de longitud 4 que empieza en ese índice usando tres ediciones. Levenshtein admite sustituciones y huecos; una coincidencia no es lo mismo que encontrar "cool" como subcadena literal idéntica.)

A primera vista, esto es como una “búsqueda con errores tipográficos permitidos”. Pero en lugar de devolver solo un booleano, necesitamos posiciones exactas de coincidencia junto al recuento de errores de cada una. El algoritmo Bitap (también conocido como shift-or o Baeza-Yates–Gonnet) es famoso en agrep (grep aproximado) y encaja a la perfección.

Reformulando en palabras sencillas

Imagina que construyes un “¿quisiste decir?”. El usuario escribe "cassidoo" y busca "cool". Con k=3, permites hasta tres ediciones (estilo Levenshtein). Un motor Bitap de producción decide eficientemente, al recorrer el texto en flujo, si el patrón encaja con ≤ k errores. Llevar el recuento exacto de errores al mismo ritmo puede exigir carriles extra de máscaras o un repaso final; el enunciado pide ese número explícitamente, así que la referencia más clara sigue siendo el trozo por DP que verás abajo — mientras las máscaras responden el sí/no «¿dentro del presupuesto?» a velocidad de texto completo.

Nuestro trabajo:

• Recorrer el texto carácter a carácter.
• Mantener vectores de estado (máscaras de bits) que representen qué tan bien el patrón coincide con el sufijo actual.
• Para cada inicio de ventana i, registrar {position, errors} cuando la distancia de Levenshtein entre pattern y text[i : i+m] sea ≤ k.

Convención de índices. El enunciado usa el índice de inicio i del trozo fijo text[i : i+m]. Muchas descripciones de Bitap en flujo dan el final de una coincidencia; se relacionan con m - 1 cuando ya conoces la longitud del patrón.

De lo ingenuo a la magia de los bits: un viaje

1. La línea base de fuerza bruta (distancia de Levenshtein en cada ventana)

El enfoque más directo: deslizar una ventana de tamaño len(pattern) sobre el texto, calcular la distancia de Levenshtein entre el patrón y cada ventana y quedarte con las que cumplan distancia ≤ k. La Levenshtein clásica por programación dinámica sobre dos trozos de longitud-m cuesta tiempo O(m²) por ventana, así que al deslizar la ventana obtienes O(n · m²) en total. Puedes reducir el espacio a O(m) con dos filas, pero cada ventana sigue necesitando tiempo Θ(m²) salvo que añadas estructura extra (por ejemplo una banda cuando k es pequeño). En cualquier caso, los textos largos castigan.

Bosquejémoslo: para cada índice i en text, compara pattern con text[i:i+len(pattern)] mediante programación dinámica. Es simple pero ineficiente: en cada posición se recalcula toda la matriz de distancia de edición.

def naive_fuzzy(text, pattern, k):
    results = []
    m = len(pattern)
    for i in range(len(text) - m + 1):
        dist = levenshtein(pattern, text[i:i+m])
        if dist <= k:
            results.append({"position": i, "errors": dist})
    return results

def levenshtein(a, b):
    # classic DP O(m*n) but here m is fixed
    dp = [[0]*(len(b)+1) for _ in range(len(a)+1)]
    for i in range(len(a)+1):
        dp[i][0] = i
    for j in range(len(b)+1):
        dp[0][j] = j
    for i in range(1, len(a)+1):
        for j in range(1, len(b)+1):
            cost = 0 if a[i-1] == b[j-1] else 1
            dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+cost)
    return dp[len(a)][len(b)]
            

Esto cumple el objetivo, pero cada comparación cuesta O(m²) y la repetimos hasta n veces — lejos de lo ideal para documentos grandes.

2. Entra Bitap — el algoritmo shift-or (coincidencia exacta)

Antes de la búsqueda difusa, entendamos la coincidencia exacta con Bitap. La idea: llevar la cuenta de qué prefijos del patrón todavía pueden alinearse con el sufijo reciente del texto mediante un vector de bits R en una palabra de máquina; la simulación del NFA avanza en paralelo sobre esos bits.

Convención de máscaras (shift-OR). Para cada carácter c del texto, precalcula pattern_mask[c] con un 0 en las posiciones de bit donde el patrón tiene el carácter c, y 1 en el resto (mismatch). Para cada c nuevo del texto:

• R = ((R << 1) | 1) & pattern_mask[c]

El desplazamiento avanza los candidatos; el AND borra bits donde el nuevo carácter no cuadra con el patrón. Algunos textos guardan máscaras invertidas o describen una actualización equivalente shift-AND — mismo autómata, otra polaridad de bits. Al implementarlo a partir de un artículo, mantén una convención de punta a punta. El listado exacto con k = 0 más abajo usa la actualización equivalente OR y luego desplazamiento de las fuentes clásicas en C (R |= pattern_mask[c]; R <<= 1), no la línea «desplaza y AND» mostrada arriba — mismo autómata, otro orden contable alrededor del desplazamiento.

Tamaño de palabra. Hacen falta m bits para un patrón de longitud m (más contabilidad). Si m supera el tamaño de palabra del hardware w (a menudo 64), el vector se reparte en varias palabras y cada paso cuesta del orden de ⌈m / w⌉ actualizaciones en lugar de una; las variantes difusas con varias máscaras por nivel de error escalan igual.

En la búsqueda difusa hace falta contar errores — ahí el estado ya no cabe en un solo R.

3. Bitap para búsqueda difusa (con ≤ k errores)

La idea difusa sigue en la misma familia que shift-or: mantener una pila pequeña de máscaras — una por presupuesto de errores — de modo que un flujo de texto actualice cada “frontera” de distancia de edición al unísono. La Levenshtein completa (inserciones, borrados, y sustituciones) exige las extensiones estilo Manber–Wu / Baeza-Yates–Navarro; los diseños bit a bit exactos difieren del matcher exacto porque borrar e insertar ya no son un único “xor con la máscara”.

Llevar esto al modelo Levenshtein completo no es un detalle menor: hay que combinar varias máscaras por nivel de error con una recurrencia precisa — fácil de equivocar, por eso los textos serios apoyan los diseños publicados en lugar de un bosquejo de medio folio.

En lugar de pegar un esqueleto frágil que se rompe con facilidad (la polaridad de bits y los off-by-one son despiadados), el listado que sigue implementa el mismo modelo Levenshtein que la línea base de fuerza bruta: para cada índice de inicio i, alinea pattern con el trozo de longitud-m text[i : i+m], puntúa ediciones y conserva los resultados con distancia ≤ k. Es la referencia que tus lectores pueden contrastar con pruebas; un motor tipo agrep en producción sustituiría el bucle interno por la recurrencia bit-paralela.

Una implementación correcta en Python (mismo modelo que la línea base)

Devuelve objetos {position, errors} con la forma del enunciado. Es deliberadamente sobria: primero corrección y claridad; Bitap es la vía rápida que implementa la misma puntuación por distancia que esta línea base.

def levenshtein(a, b):
    """Classic dynamic-programming edit distance."""
    dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(len(a) + 1):
        dp[i][0] = i
    for j in range(len(b) + 1):
        dp[0][j] = j
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            cost = 0 if a[i - 1] == b[j - 1] else 1
            dp[i][j] = min(
                dp[i - 1][j] + 1,
                dp[i][j - 1] + 1,
                dp[i - 1][j - 1] + cost,
            )
    return dp[len(a)][len(b)]


def fuzzy_search(text, pattern, k):
    m = len(pattern)
    if m == 0:
        return []
    results = []
    for i in range(len(text) - m + 1):
        dist = levenshtein(pattern, text[i : i + m])
        if dist <= k:
            results.append({"position": i, "errors": dist})
    return results


if __name__ == "__main__":
    print(fuzzy_search("the cat sat on the mat", "cat", 0))
    # [{'position': 4, 'errors': 0}]

    print(fuzzy_search("cassidoo", "cool", 1))
    # []

    print(fuzzy_search("cassidoo", "cool", 3))
    # [{'position': 0, 'errors': 3}, {'position': 4, 'errors': 3}]
          

Bitap exacto (k = 0) — shift-or mínimo en Python

Implementación compacta de shift-or: las máscaras de carácter usan bits en 0 donde el patrón coincide, y el registro R se actualiza con | y luego << 1 por carácter de texto. Devuelve cada índice de inicio donde un trozo de longitud m coincide exactamente con pattern. Hacen falta m + 1 bits de margen (patrones de decenas encajan holgado en CPUs de 64 bits).

def bitap_exact_positions(text, pattern):
    """Shift-or exacto: índices i con text[i : i + m] == pattern."""
    m = len(pattern)
    if m == 0:
        return []
    mask_all = (1 << (m + 1)) - 1
    alphabet = set(text) | set(pattern)
    pattern_mask = {c: mask_all for c in alphabet}
    for j in range(m):
        pattern_mask[pattern[j]] &= ~(1 << j)

    R = mask_all ^ 1
    out = []
    for idx, ch in enumerate(text):
        R |= pattern_mask.get(ch, mask_all)
        R = (R << 1) & mask_all
        if (R & (1 << m)) == 0:
            start = idx - m + 1
            if start >= 0:
                out.append(start)
    return out


if __name__ == "__main__":
    sample = "the cat sat on the mat"
    assert bitap_exact_positions(sample, "cat") == [
        hit["position"] for hit in fuzzy_search(sample, "cat", 0)
    ]
          

Cuando k = 1 en ventanas de longitud m

La Bitap difusa Levenshtein completa (k > 0) exige la recurrencia Wu–Manber / Baeza-Yates–Navarro sobre varias máscaras. Para el modelo del enunciado — dos cadenas de igual longitud m — puedes comprobar distancia ≤ 1 en tiempo O(m) con una verificación triple (una sustitución, un borrado a la izquierda, un borrado a la derecha). Coincide exactamante con Levenshtein cuando la distancia es ≤ 1; si devuelve «por encima de 1», usa el DP completo solo cuando necesites el valor exacto mayor.

def levenshtein_leq1_equal_len(a, b):
    """
    Si len(a) == len(b) y Levenshtein(a, b) <= 1, devuelve esa distancia (0 ó 1).
    Si no, devuelve None. Tiempo O(m); fácil de auditar y hacer fuzz.
    """
    if len(a) != len(b):
        raise ValueError("se esperan trozos de igual longitud en este camino rápido")
    n = len(a)
    i = 0
    while i < n and a[i] == b[i]:
        i += 1
    if i == n:
        return 0
    if a[i + 1 :] == b[i + 1 :]:
        return 1
    if a[i + 1 :] == b[i:]:
        return 1
    if a[i:] == b[i + 1 :]:
        return 1
    return None


def fuzzy_search_k1_equal_windows(text, pattern):
    m = len(pattern)
    if m == 0:
        return []
    results = []
    for i in range(len(text) - m + 1):
        d = levenshtein_leq1_equal_len(pattern, text[i : i + m])
        if d is not None:
            results.append({"position": i, "errors": d})
    return results


if __name__ == "__main__":
    assert fuzzy_search_k1_equal_windows("cassidoo", "cool") == fuzzy_search(
        "cassidoo", "cool", 1
    )
          

Junta estos listados con un motor difuso bitmask completo en tu editor y haz fuzz sobre cadenas aleatorias: si las puntuaciones divergen, el fallo está en la capa bit-paralela que añadiste al final.

Complejidad y uso en el mundo real

La implementación de referencia anterior cuesta tiempo Θ((n − m + 1) · m²) en el peor caso — justo la redundancia que los algoritmos tipo Bitap pretenden eliminar. Un Bitap difuso cuidadoso ejecuta O(n · k · ⌈m / w⌉) operaciones de palabra para longitud de texto n, presupuesto de ediciones k, longitud de patrón m y palabra de máquina w — es decir, lineal en n con factores multiplicativos en k y ⌈m/w⌉, en lugar del trabajo DP Θ(m²) por ventana del código de referencia. Los matchers difusos de producción conservan la misma semántica Levenshtein pero aplican esas actualizaciones bit-paralelas.

¿Dónde se usa Bitap? El comando Unix agrep, el pariente difuso de grep, lo lleva bajo el capó. También algunos editores de código y herramientas de búsqueda apoyan en algoritmos parecidos para la búsqueda tolerante a typos.

Para terminar

Partimos de la fuerza bruta, acercamos la lente a cómo shift-or empaqueta estados de un NFA en enteros, añadimos un Bitap exacto que funciona más una comprobación k = 1 en ventanas, y mantuvimos el trozo completo por DP como modelo de puntuación verificable del acertijo. Junta la intuición con código que puedas probar por fuzz; cuando esa base sea confiable, cualquier atajo bit-paralelo tiene que igualarla bit a bit en las distancias. La próxima vez que veas un “¿quisiste decir …?”, conocerás una forma en que podría implementarse.

¡Feliz codificación, y que tus búsquedas sean difusas como debe ser!

Referencias y lecturas adicionales

• Ricardo Baeza-Yates and Gaston H. Gonnet — "A New Approach to Text Searching" — artículo original de Communications of the ACM que abre la línea de trabajo Bitap / shift-or.
• Algoritmo Bitap (Wikipedia) — panorámica breve de variantes exactas y difusas, con la intuición habitual de las máscaras.
• Gene Myers — «A fast bit-vector algorithm for approximate string matching based on dynamic programming» — tratamiento clásico con vectores de bits; buen contexto junto al shift-or Bitap.

¿Aún no tienes suficiente de Lumænaut_? Lee esto...

• Puliendo LeetCode — Día 1: Two Sum — recorrido amigable desde fuerza bruta hasta una solución O(n) con mapa hash.
• Los 8 paradigmas de algoritmos — ocho modelos mentales que repetirás en problemas, entrevistas y código de producción.
• Episodio 2: Todo lo que no sé sobre bloggear — la bitácora entre bastidores: dominios, SEO y aprender en público.