Bitap: el algoritmo de coincidencia de cadenas que aprovecha los bits de la CPU

El blog de Jo3‑L publica una exposición del algoritmo bitap (también llamado shift‑and). Parte de la comparación con los clásicos Boyer‑Moore y Knuth‑Morris‑Pratt, pero se centra en casos donde el patrón tiene menos caracteres que el ancho de una palabra de máquina.

El punto de partida es la implementación más simple: recorrer la cadena de texto T y, para cada posición, comparar carácter a carácter con el patrón P. El código en Go muestra cómo devolver el índice del primer emparejamiento o ‑1 si no existe. A continuación, el autor plantea una variante streaming, que no necesita cargar todo el texto en memoria. Mantiene un conjunto de coincidencias en progreso y, al leer cada nuevo carácter, avanza los estados que esperan ese carácter y descarta los demás. La versión inicial usa una estructura con la subcadena restante del patrón.

Para simplificar, sustituye la subcadena por un índice j que indica la posición del siguiente carácter a comparar. El algoritmo sigue siendo un bucle anidado, pero ahora la lista de estados contiene solo enteros entre 0 y len(P). La siguiente optimización es el verdadero salto: si el patrón cabe en 64 bits, se pueden representar todos los estados activos como un solo entero de 64 bits. Cada bit j indica si el estado j está activo. Al leer un carácter, se actualiza el bitset con una operación OR para iniciar una nueva coincidencia y se recorre cada bit activo para comprobar si el carácter coincide con P[j].

Aunque esta versión todavía implica un bucle interno, el autor muestra que con una manipulación de bits más astuta es posible eliminarlo por completo. El artículo se corta antes de presentar la fórmula final, pero deja clara la dirección: usar máscaras pre‑calculadas para cada carácter del alfabeto y actualizar el bitset con una única operación de desplazamiento y AND. El resultado es un algoritmo que procesa el texto en una sola pasada, con coste O(n) y una constante muy baja para patrones cortos.

Este enfoque es útil en sistemas embebidos, analizadores de logs en tiempo real o cualquier aplicación donde la latencia de búsqueda sea crítica y el patrón sea breve. La implementación en Go sirve como referencia práctica y puede adaptarse a otros lenguajes que soporten operaciones bit‑wise sobre enteros de 64 bits.

En resumen, el algoritmo bitap combina la claridad conceptual de la búsqueda ingenua con la eficiencia de la manipulación de bits, ofreciendo una solución elegante para coincidencias de patrones cortos en flujos de datos continuos.