Entrevista técnica: Implementar la búsqueda de múltiples patrones con Aho–Corasick

Planteamiento y contexto

Este es un problema de búsqueda de múltiples patrones para filtrado de registros, detección de palabras sensibles o resaltado en editores. Sea M la longitud total de las palabras clave y N la longitud del texto; reporta el inicio de cada coincidencia y el ID de la palabra clave. El diccionario es fijo durante el preprocesamiento, el texto puede ser largo y el entrevistador espera el preprocesamiento, la complejidad del escaneo y el manejo de traslapes.

Qué evalúa el entrevistador

El entrevistador busca que extiendas el uso compartido de prefijos del trie hacia una máquina de estados finitos. Una respuesta sólida construye enlaces de fallo, hereda salidas a lo largo de los enlaces de fallo y explica por qué cada carácter provoca transiciones de estado acotadas. Una respuesta débil dice “usar un trie” pero no puede manejar el traslape de sufijos o el retroceso ante fallos de coincidencia.

Aclaraciones que conviene hacer primero

• ¿La coincidencia distingue entre mayúsculas y minúsculas, está normalizada en Unicode o se basa en bytes? La definición del carácter cambia el trie y la unidad de posición.
• ¿Deben devolverse las coincidencias que se traslapan y múltiples palabras clave que terminan en una misma posición? Esto determina si la cadena de salida es completa.
• ¿El diccionario cambia con frecuencia? Un diccionario estático se adapta a un solo autómata; un diccionario dinámico puede requerir reconstrucciones con versiones.
• ¿Las posiciones se cuentan en caracteres, bytes o unidades de código UTF-16? Coincide con el contrato del invocador.
• ¿El texto llega en fragmentos (chunks)? El escaneo entre fragmentos debe preservar el estado en lugar de reiniciarse en cada fragmento.

Estructura para responder en 30 segundos

“Insertaría cada palabra clave en un trie y luego usaría BFS para construir un enlace de fallo para cada nodo: el sufijo utilizable más largo tras un desajuste. Cada nodo combina sus propias salidas terminales con las salidas de su destino de fallo. Durante el escaneo, sigo las transiciones o los enlaces de fallo y emito las salidas del nodo actual. El preprocesamiento es lineal respecto a la longitud total de las palabras clave más la representación de aristas; el escaneo es O(N + coincidencias) y la entrada fragmentada solo necesita el estado actual del autómata.”

Respuesta detallada paso a paso

1. Construir el trie. Cada nodo almacena aristas secundarias, un enlace de fallo e IDs de palabras clave. Un nodo terminal añade un ID; no debe conservar solo uno.
2. Inicializar fallos. Los hijos directos de la raíz fallan hacia la raíz. Procesa los nodos restantes por nivel de profundidad con una cola.
3. Calcular transiciones de retroceso. Para una arista desde un nodo, sigue los enlaces de fallo del padre hasta encontrar la misma arista de carácter; de lo contrario, regresa a la raíz. Así, el escaneo nunca vuelve a comparar caracteres de texto anteriores.
4. Agregar salidas. Copia salidas del destino de fallo o almacena un enlace de salida para evitar copiar listas; se recorre un enlace de salida al reportar coincidencias.
5. Escanear el texto. Intenta una arista secundaria para cada carácter. Ante un desajuste, sigue los enlaces de fallo hasta alcanzar una arista o la raíz. Emite cada salida en el nuevo nodo; el inicio es el índice actual menos la longitud de la palabra clave más uno.
6. Manejar límites. Las palabras clave que se traslapan se emiten naturalmente. La entrada fragmentada transfiere el estado entre fragmentos. Si las coincidencias son enormes, utiliza una devolución de llamada (callback), un límite o paginación en lugar de retener todos los resultados O(coincidencias).

Usa una tabla hash para alfabetos generales y un arreglo para un alfabeto fijo pequeño cuando la memoria lo permita. Para un diccionario cambiante, construye una nueva versión en segundo plano y cambia a los lectores de forma atómica para que los escaneos nunca observen un autómata parcial.

Respuesta modelo

“Insertaría todas las palabras clave y registraría cada ID terminal, luego construiría los enlaces de fallo mediante BFS. Los hijos de la raíz fallan hacia la raíz. Para otras aristas, sigo la cadena de fallos del padre para encontrar la misma transición o retroceder a la raíz. Las salidas incluyen los IDs terminales propios del nodo y las salidas de fallo, de modo que tanto he como she se emiten al escanear she. Cada carácter del texto sigue una transición secundaria o de fallo, lo que da un tiempo de escaneo O(N + Z), donde Z es el número de coincidencias; el preprocesamiento es O(M) más el almacenamiento de aristas. El texto fragmentado conserva el estado, y las actualizaciones del diccionario construyen una nueva versión antes de realizar el cambio.”

Errores comunes

• Error: Mover tanto el puntero como el texto hacia atrás ante un desajuste → Por qué falla: Degenera en volver a escanear para cada palabra clave → Solución: Los enlaces de fallo mantienen el índice de texto monótono.
• Error: Mantener una sola salida por nodo → Por qué falla: Las palabras clave de sufijo y los puntos finales compartidos desaparecen → Solución: Fusiona salidas de fallo o mantén enlaces de salida.
• Error: Afirmar que el escaneo siempre es O(N) → Por qué falla: El simple hecho de reportar coincidencias puede costar O(Z) → Solución: Declara O(N + Z) y emite la salida en flujo continuo.
• Error: Reiniciar a la raíz en cada fragmento → Por qué falla: Las palabras clave que abarcan varios fragmentos no pueden coincidir → Solución: Transfiere el estado del autómata entre fragmentos.

Preguntas de seguimiento y respuestas

¿Por qué no ejecutar KMP por separado para cada palabra clave?

Ejecuciones separadas de KMP requieren O(KN) escaneos de texto. Aho–Corasick comparte prefijos del trie y procesa el texto una sola vez, lo cual se adapta a un diccionario fijo y un texto largo.

¿Por qué los enlaces de fallo encuentran cada coincidencia?

Apuntan al sufijo utilizable más largo. Continuar a lo largo de la cadena de fallos enumera cada sufijo que también es un prefijo de palabra clave, de modo que la agregación de salidas encuentra coincidencias anidadas y traslapadas.

¿Qué pasa si las tablas hash de los hijos agotan la memoria?

Elige arreglos para un alfabeto pequeño, tablas de aristas compactas o un trie de doble arreglo (double-array trie), y usa enlaces de salida para evitar copiar listas. Mide los recuentos de nodos y aristas antes de comprimir.

¿Puede cambiar el diccionario con frecuencia?

Crea versiones del diccionario, construye un nuevo autómata en segundo plano, valídalo y reemplaza atómicamente el puntero del lector. Mantén la versión antigua brevemente para los flujos que ya estén en progreso.