Aho-Corasick: búsqueda multi-patrón

Lo que cubre este capítulo

Los algoritmos de un solo patrón encuentran una aguja en un pajar. Aho-Corasick encuentra miles de agujas en una sola pasada. Dado un diccionario completo de patrones — firmas de virus, palabras prohibidas, reglas de detección de intrusos, un conjunto de keywords — localiza cada aparición de cada patrón en un único recorrido lineal del texto, sin importar cuántos patrones haya ni qué tan largos sean. La alternativa obvia, buscar cada patrón por separado, vuelve a leer el texto una vez por patrón; Aho-Corasick lo lee una vez y ya. Lo logra generalizando la función de fallo de KMP: de un solo patrón a un trie de todos los patrones. Acomodas los patrones en un árbol de prefijos, agregas failure links que indican a dónde retroceder cuando un carácter no extiende el match actual, y pasas el texto por el autómata resultante. Este capítulo lo construye, ve el ejemplo clásico de ushers encontrar she, he y hers de un jalón, y mide la ganancia contra la búsqueda patrón por patrón: 260 veces menos caracteres examinados.

Un poco de historia

Alfred Aho y Margaret Corasick publicaron el algoritmo en 1975 en Bell Labs, y su origen es deliciosamente concreto: se construyó para una librería de búsqueda bibliográfica, para escanear documentos buscando muchos términos de índice a la vez. Aho después co-escribiría el "Dragon Book" sobre compiladores y co-crearía AWK (la "A" es suya), pero Aho-Corasick sigue siendo uno de sus resultados más desplegados — corre dentro de fgrep, la clásica herramienta de Unix para búsqueda de cadenas fijas, que es exactamente el problema de "encuentra cualquiera de estas cadenas". El algoritmo es una generalización directa de Knuth-Morris-Pratt, publicado apenas dos años antes: la función de fallo de KMP le dice a un patrón dónde retomar después de un mismatch, y los failure links de Aho-Corasick hacen lo mismo para todo un árbol de patrones a la vez. El linaje es explícito — Aho-Corasick es lo que obtienes cuando preguntas "¿y si KMP tuviera un trie en lugar de una sola cadena?" — y volvió la búsqueda multi-patrón tan barata como la de un solo patrón, razón por la que se convirtió en la herramienta estándar para escaneo de firmas.

La intuición

Construye el algoritmo en tres capas. Primero, un trie: inserta cada patrón en un árbol de prefijos, de modo que he, she, his y hers compartan sus prefijos comunes como caminos compartidos, y el último carácter de cada patrón marque un nodo como "aquí termina un patrón". Seguir caracteres hacia abajo desde la raíz es la forma de hacer match: mientras el texto siga extendiendo un camino del trie, estás dentro de un match potencial.

Segundo, los failure links, la idea de KMP llevada al árbol. Cuando el siguiente carácter del texto no continúa el camino actual del trie, no quieres rendirte y reiniciar desde la raíz: quieres caer al sufijo propio más largo de lo que ya llevas emparejado que también sea prefijo de algún patrón, y retomar ahí. El failure link de cada nodo apunta exactamente a ese nodo. Se calculan con un recorrido por anchura, primero los nodos superficiales, porque el destino de fallo de un nodo siempre está más arriba y debe estar terminado antes de poder calcular el del nodo mismo — la misma dependencia de orden que la tabla de KMP, ahora sobre un árbol.

Tercero, los output links. Una sola posición del texto puede terminar varios patrones a la vez: llegar al nodo de hers también debería reportar he, porque he es un sufijo... no — hers contiene a he como prefijo, pero el caso sutil es she, que termina en un nodo cuyo failure link lleva a he, así que llegar a she debe reportar también he. Aho-Corasick resuelve esto fusionando el conjunto de salidas de cada nodo a lo largo de su failure link, de modo que un nodo reporta su propio patrón más todo patrón que sea sufijo de la cadena que representa. Ahora pasa el texto en una sola pasada: en cada carácter, sigue una arista goto si existe, o sigue failure links hasta que alguna exista, y emite las salidas del nodo actual. El puntero del texto nunca retrocede — un solo barrido lineal encuentra todo.

Complejidad: cómo escala

Construir el autómata es $O(\sum \text{pattern lengths})$ — un nodo del trie por cada carácter distinto de patrón, más una pasada por anchura para los failure links. Buscar es $O(n + z)$ donde $n$ es la longitud del texto y $z$ el número de matches reportados: cada carácter del texto se procesa una vez (los retrocesos por failure links son $O(1)$ amortizado por carácter, el mismo argumento que en KMP), más trabajo constante por cada match emitido. Y lo crucial: el costo de búsqueda es independiente del número de patrones — mil patrones cuestan la misma pasada única que uno. Ese es todo el punto, y el enfrentamiento lo mide directo: caracteres examinados para encontrar $k$ patrones, la pasada única de Aho-Corasick contra escanear el texto una vez por patrón:

La línea de una-pasada-por-patrón sube sin parar: cada patrón nuevo significa otro recorrido completo del texto, así que su costo crece linealmente con el número de patrones. La línea de Aho-Corasick es prácticamente plana — procesa el texto una vez sin importar cuántos patrones tenga el autómata, así que agregar patrones solo hace crecer la construcción (que es barata), no el escaneo. Con 500 patrones, Aho-Corasick examinó alrededor de 10,000 caracteres contra los 2.6 millones del enfoque patrón por patrón — 260 veces menos, y la brecha se abre más con cada patrón que agregas. Es la misma historia de "una pasada le gana a muchas pasadas" que el truco multi-patrón de Rabin-Karp, pero Aho-Corasick lo hace con patrones de cualquier longitud y con una garantía lineal limpia, y por eso es él, y no Rabin-Karp, la herramienta de producción para diccionarios grandes.

En qué es bueno y en qué no

Aho-Corasick es la herramienta definitiva para emparejar muchos patrones fijos a la vez. Sus usos son exactamente los problemas de "encuentra cualquiera de estas cadenas": motores antivirus escaneando archivos contra miles de firmas de malware, sistemas de detección de intrusos en red (Snort, Suricata) comparando flujos de paquetes contra conjuntos de reglas, filtros de spam y groserías revisando listas de palabras, la búsqueda multi-cadena de fgrep, y herramientas de bioinformática encontrando un conjunto de motifs en ADN. Como su costo de búsqueda es independiente de la cantidad de patrones y hace una sola pasada en streaming sin retroceder, es ideal para escaneo en tiempo real de alto throughput donde el diccionario de patrones es grande y fijo. Además compone bien: una vez construido, el autómata puede escanear texto ilimitado, así que construyes una vez y haces streaming para siempre.

Donde es la herramienta equivocada es con un solo patrón (KMP o Boyer-Moore son más simples, y Boyer-Moore es más rápido), o con un conjunto de patrones que cambia seguido — el autómata hay que reconstruirlo cuando los patrones cambian, aunque la construcción es barata comparada con escanear mucho texto. Su memoria crece con el tamaño total del diccionario de patrones (un nodo por carácter distinto de prefijo de patrón), lo cual para diccionarios enormes puede ser considerable, y la implementación clásica guarda un mapa goto por nodo; las versiones de producción usan representaciones compactas (tries de doble arreglo, autómatas bit-sliced) para reducirlo. Y para matching aproximado o estilo regex no aplica directamente — es matching exacto de cadenas fijas. Pero para ese nicho — muchos patrones exactos, un texto, tiempo lineal — nada le gana.

Los datos, o las entradas

El enfrentamiento fija un texto aleatorio de 5000 caracteres y busca un número creciente de patrones, contando caracteres examinados para la pasada única de Aho-Corasick contra escanear el texto una vez por patrón — así aísla la independencia respecto al número de patrones. La corrección se verifica con cientos de diccionarios y textos aleatorios: los matches de Aho-Corasick deben ser exactamente iguales al resultado de buscar cada patrón por separado con el str.find de Python. La animación corre el ejemplo de libro de texto — el diccionario {he, she, his, hers} escaneando el texto ushers — dibujando el trie e iluminando el estado actual del autómata conforme se alimenta cada carácter, disparando matches (incluido el he reportado vía failure link dentro de she) conforme se completan.

Constrúyelo, una función a la vez

El trie — inserta cada patrón, compartiendo prefijos comunes:

class AhoCorasick:
    """A trie of patterns augmented with failure and output links — the Aho-Corasick automaton."""

    def __init__(self):
        self.goto = [{}]                          # goto[node][char] -> child node; node 0 is the root
        self.fail = [0]                           # failure link per node (filled in by build)
        self.out = [set()]                        # patterns ending at this node
        self.parent = [(-1, "")]                  # (parent node, edge char) — for drawing the trie

    def add(self, word):
        """Insert one pattern, creating trie nodes for any new characters along its path."""
        node = 0
        for ch in word:
            if ch not in self.goto[node]:
                self.goto.append({})
                self.fail.append(0)
                self.out.append(set())
                self.parent.append((node, ch))
                self.goto[node][ch] = len(self.goto) - 1
            node = self.goto[node][ch]
        self.out[node].add(word)                  # this node marks the end of `word`

Los failure y output links — la idea de KMP, construida por anchura sobre el árbol:

def build(self):
    """Compute failure links by breadth-first traversal (shallower nodes first, so a node's
    failure target is already finished when we need it — the same order dependency as KMP's
    table). A node's failure link is the deepest OTHER node whose string is a proper suffix of
    this node's string. Output sets are merged along failure links, so reaching a node reports
    not just its own pattern but every pattern that is a suffix of it (that's how 'hers' also
    reports 'he')."""
    q = deque()
    for ch, nxt in self.goto[0].items():
        self.fail[nxt] = 0                     # depth-1 nodes fail to the root
        q.append(nxt)
    while q:
        u = q.popleft()
        for ch, v in self.goto[u].items():
            q.append(v)
            f = self.fail[u]                   # follow u's failure chain to find where ch continues
            while f and ch not in self.goto[f]:
                f = self.fail[f]
            self.fail[v] = self.goto[f].get(ch, 0) if self.goto[f].get(ch, 0) != v else 0
            self.out[v] |= self.out[self.fail[v]]   # inherit suffix patterns

Y la búsqueda de una sola pasada sobre el texto:

def search(self, text):
    """Scan the text once. Follow goto edges when the next character extends the current match;
    on a dead end, follow failure links (never rewinding the text) until the character fits or
    we're back at the root. At each position, the current node's output set names every pattern
    ending here. Returns (start_index, pattern) for every occurrence. O(n + matches)."""
    node = 0
    results = []
    for i, ch in enumerate(text):
        while node and ch not in self.goto[node]:
            node = self.fail[node]             # fall back, like KMP, without moving in the text
        node = self.goto[node].get(ch, 0)
        for w in self.out[node]:
            results.append((i - len(w) + 1, w))
    return sorted(results)

Míralo funcionar

Aquí está el autómata para {he, she, his, hers} escaneando el texto ushers. Los nodos marcados con rombo (color teal) son donde termina un patrón; el naranja es el estado actual del autómata. Alimenta los caracteres uno por uno: u no tiene arista desde la raíz, así que nos quedamos donde estamos; s avanza al nodo s, h a sh, e a she — y llegar a she dispara dos matches a la vez, she y he, porque el output link fusionó he en las salidas de she. Luego r no tiene arista desde she, así que el autómata sigue un failure link — cae al nodo he, que sí tiene arista r — y continúa a her; la s final llega a hers y dispara ese match. Una pasada de izquierda a derecha, el puntero del texto sin rebobinar nunca, y las tres apariciones encontradas:

El código completo

La pestaña "desde cero" es el autómata completo de Aho-Corasick — trie, failure links, fusión de salidas y búsqueda; la pestaña de librería es el enfoque de una pasada por patrón contra el que se verifica y se compite, con la llamada a pyahocorasick que usarías en producción anotada. Cambia entre ellas.

"""Aho-Corasick — find ALL occurrences of MANY patterns in one pass over the text. Rabin-Karp
could search many equal-length patterns; Aho-Corasick searches a whole dictionary of patterns of
any lengths, in a single linear scan, and it's the right tool when the pattern set is large: virus
signatures, network-intrusion rules, spam word lists, keyword filters.

It's KMP generalized from one pattern to many. First, arrange all the patterns into a TRIE (a
prefix tree) so shared prefixes are shared paths. Then add FAILURE LINKS exactly like KMP's
failure function, but on the trie: from each node, a failure link points to the node representing
the longest proper suffix of the current matched string that is also a prefix of some pattern —
where to fall back to when the next character doesn't extend the current match. Feed the text
through the resulting automaton one character at a time, following goto edges and failure links,
and OUTPUT links report every pattern that ends at the current position. One pass, O(n + total
pattern length + number of matches).
"""
from collections import deque


# region: trie
class AhoCorasick:
    """A trie of patterns augmented with failure and output links — the Aho-Corasick automaton."""

    def __init__(self):
        self.goto = [{}]                          # goto[node][char] -> child node; node 0 is the root
        self.fail = [0]                           # failure link per node (filled in by build)
        self.out = [set()]                        # patterns ending at this node
        self.parent = [(-1, "")]                  # (parent node, edge char) — for drawing the trie

    def add(self, word):
        """Insert one pattern, creating trie nodes for any new characters along its path."""
        node = 0
        for ch in word:
            if ch not in self.goto[node]:
                self.goto.append({})
                self.fail.append(0)
                self.out.append(set())
                self.parent.append((node, ch))
                self.goto[node][ch] = len(self.goto) - 1
            node = self.goto[node][ch]
        self.out[node].add(word)                  # this node marks the end of `word`
    # endregion

    # region: build
    def build(self):
        """Compute failure links by breadth-first traversal (shallower nodes first, so a node's
        failure target is already finished when we need it — the same order dependency as KMP's
        table). A node's failure link is the deepest OTHER node whose string is a proper suffix of
        this node's string. Output sets are merged along failure links, so reaching a node reports
        not just its own pattern but every pattern that is a suffix of it (that's how 'hers' also
        reports 'he')."""
        q = deque()
        for ch, nxt in self.goto[0].items():
            self.fail[nxt] = 0                     # depth-1 nodes fail to the root
            q.append(nxt)
        while q:
            u = q.popleft()
            for ch, v in self.goto[u].items():
                q.append(v)
                f = self.fail[u]                   # follow u's failure chain to find where ch continues
                while f and ch not in self.goto[f]:
                    f = self.fail[f]
                self.fail[v] = self.goto[f].get(ch, 0) if self.goto[f].get(ch, 0) != v else 0
                self.out[v] |= self.out[self.fail[v]]   # inherit suffix patterns
    # endregion

    # region: search
    def search(self, text):
        """Scan the text once. Follow goto edges when the next character extends the current match;
        on a dead end, follow failure links (never rewinding the text) until the character fits or
        we're back at the root. At each position, the current node's output set names every pattern
        ending here. Returns (start_index, pattern) for every occurrence. O(n + matches)."""
        node = 0
        results = []
        for i, ch in enumerate(text):
            while node and ch not in self.goto[node]:
                node = self.fail[node]             # fall back, like KMP, without moving in the text
            node = self.goto[node].get(ch, 0)
            for w in self.out[node]:
                results.append((i - len(w) + 1, w))
        return sorted(results)
    # endregion

"""The library counterpart and the contrast. For production multi-pattern matching you'd use a
maintained Aho-Corasick library (`pyahocorasick`, a C extension) or a regex engine's alternation:

    import ahocorasick
    A = ahocorasick.Automaton()
    for i, w in enumerate(patterns):
        A.add_word(w, (i, w))
    A.make_automaton()
    for end, (i, w) in A.iter(text):
        ...

The instructive contrast is the obvious alternative: search for each pattern SEPARATELY, one pass
over the text per pattern. `search_each` below does exactly that with str.find — the correctness
reference and the k-passes cost Aho-Corasick's single pass is timed against.
"""


# region: per_pattern
def search_each(text, patterns):
    """Find every pattern by searching for each one independently — one full scan of the text per
    pattern (k patterns → k scans). Returns the same (start, pattern) list Aho-Corasick produces,
    so it's both the correctness reference and the 'naive multi-pattern' contrast."""
    results = []
    for w in patterns:
        if not w:
            continue
        i = text.find(w)
        while i != -1:
            results.append((i, w))
            i = text.find(w, i + 1)               # +1 → overlapping occurrences
    return sorted(results)
# endregion

Desde cero vs librería

Aho-Corasick es el cierre de este bloque porque une todos sus hilos. Es la función de fallo de KMP (el primer capítulo del bloque) generalizada a un trie (el árbol de prefijos del bloque de árboles), resolviendo la versión multi-patrón del problema que insinuaba la multi-búsqueda de Rabin-Karp, con la garantía lineal limpia que la disciplina se pasó los años setenta estableciendo. La lección recurrente del bloque de cadenas queda a la vista: el matching saca su velocidad de precalcular estructura antes del escaneo — la tabla de KMP, el rolling hash de Rabin-Karp, la tabla de saltos de Boyer-Moore, el índice del suffix array y ahora el autómata de Aho-Corasick son todos la misma jugada: paga por adelantado para que el escaneo salga barato. Y el resultado de "una pasada le gana a muchas" refleja el truco multi-patrón de Rabin-Karp y las consultas amortizadas del suffix array: cuando vas a hacer mucho matching, compila el trabajo en una estructura una sola vez. En producción usarías pyahocorasick (una extensión en C) por el throughput; construir el autómata tú mismo es lo que convierte la maquinaria de failure links y fusión de salidas — la parte que es fácil de equivocar de forma sutil — en algo que entiendes en lugar de algo en lo que confías.

Dónde te lo vas a encontrar

Aho-Corasick corre dentro de la infraestructura de seguridad y de texto de la que dependes a diario. Los motores antivirus y anti-malware escanean archivos contra diccionarios de miles de firmas de bytes con él. Los sistemas de detección y prevención de intrusos en red — Snort, Suricata y los motores de inspección profunda de paquetes en los firewalls — comparan payloads de paquetes contra grandes conjuntos de reglas en tiempo real usando Aho-Corasick (y sus variantes compactas). Filtros de contenido, detectores de groserías y spam, y sistemas de prevención de fuga de datos comparan contra listas de keywords. Las herramientas de búsqueda (fgrep, grep -F con varios patrones, la ruta multi-literal de ripgrep) lo usan a él o a parientes cercanos. La bioinformática lo usa para encontrar conjuntos de motifs de ADN/proteínas, y la lingüística computacional para tokenización con diccionario. Donde sea que un flujo tenga que compararse contra muchas cadenas fijas a la vez y rápido, Aho-Corasick es casi con certeza el motor.

Puntos clave

Aho-Corasick compila un diccionario completo de patrones en un solo autómata — un trie de los patrones más failure links al estilo KMP y output links fusionados — y encuentra cada aparición de cada patrón en una pasada lineal sobre el texto, con un costo de búsqueda independiente del número de patrones (260× menos caracteres examinados que la búsqueda patrón por patrón con 500 patrones). Es la generalización multi-patrón de KMP: los failure links son la función de fallo de KMP sobre un árbol, la fusión de salidas garantiza que se reporte cada patrón que termina en una posición, y el escaneo es lineal amortizado por la misma razón que el de KMP.

Con eso cierra el bloque de cadenas — búsqueda de un solo patrón por tres vías (KMP, Rabin-Karp, Boyer-Moore), indexado de texto (suffix arrays) y matching multi-patrón (Aho-Corasick) — todos unidos por el tema de precalcular estructura para abaratar el escaneo. El libro ahora deja atrás las estructuras de datos y problemas específicos para pasar a los paradigmas que generan algoritmos: el siguiente bloque trata de las estrategias reutilizables — divide y vencerás, greedy, programación dinámica, backtracking, dos punteros — que sostienen buena parte de lo que ya construiste, haciendo explícitos los patrones que venían repitiéndose de forma implícita todo este tiempo.