Algoritmo de Aho-Corasick

El algoritmo de Aho-Corasick nos permite buscar rápidamente múltiples patrones en un texto. Al conjunto de strings patrón también se lo llama un diccionario. Denotaremos por $m$ la longitud total de los strings que lo componen y por $k$ el tamaño del alfabeto. El algoritmo construye un autómata de estados finitos basado en un trie en tiempo $O(m k)$ y luego lo usa para procesar el texto.

El algoritmo fue propuesto por Alfred Aho y Margaret Corasick en 1975.

Construcción del trie

Un trie basado en las palabras "Java", "Rad", "Rand", "Rau", "Raum" y "Rose".
La imagen de [nd](https://de.wikipedia.org/wiki/Benutzer:Nd) se distribuye bajo la licencia CC BY-SA 3.0 .

Formalmente, un trie es un árbol con raíz, donde cada arista del árbol está etiquetada con alguna letra y las aristas salientes de un vértice tienen etiquetas distintas.

Identificaremos cada vértice del trie con el string formado por las etiquetas del camino desde la raíz hasta ese vértice.

Cada vértice también tendrá una bandera $\text{output}$ que se activará si el vértice corresponde a un patrón del diccionario.

En consecuencia, un trie para un conjunto de strings es un trie tal que cada vértice $\text{output}$ corresponde a un string del conjunto y, recíprocamente, cada string del conjunto corresponde a un vértice $\text{output}$ .

Describimos ahora cómo construir un trie para un conjunto dado de strings en tiempo lineal respecto de su longitud total.

Introducimos una estructura para los vértices del árbol:


const int K = 26;

struct Vertex {
    int next[K];
    bool output = false;

    Vertex() {
        fill(begin(next), end(next), -1);
    }
};

vector<Vertex> trie(1);

Aquí almacenamos el trie como un arreglo de $\text{Vertex}$ . Cada $\text{Vertex}$ contiene la bandera $\text{output}$ y las aristas en forma de un arreglo $\text{next}[]$ , donde $\text{next}[i]$ es el índice del vértice al que llegamos al seguir el carácter $i$ , o $-1$ si no existe esa arista. Inicialmente, el trie consiste en un solo vértice — la raíz — con índice $0$ .

Ahora implementamos una función que agregará un string $s$ al trie. La implementación es simple: empezamos en el nodo raíz y, mientras existan aristas correspondientes a los caracteres de $s$ , las seguimos. Si no hay arista para un carácter, generamos un nuevo vértice y lo conectamos con una arista. Al final del proceso marcamos el último vértice con la bandera $\text{output}$ .


void add_string(string const& s) {
    int v = 0;
    for (char ch : s) {
        int c = ch - 'a';
        if (trie[v].next[c] == -1) {
            trie[v].next[c] = trie.size();
            trie.emplace_back();
        }
        v = trie[v].next[c];
    }
    trie[v].output = true;
}

Esta implementación obviamente corre en tiempo lineal, y como cada vértice almacena $k$ enlaces, usará $O(m k)$ de memoria.

Es posible reducir el consumo de memoria a $O(m)$ usando un mapa en lugar de un arreglo en cada vértice. Sin embargo, esto aumentará la complejidad temporal a $O(m \log k)$ .

Construcción de un autómata

Supongamos que hemos construido un trie para el conjunto dado de strings. Ahora mirémoslo desde otro ángulo. Si observamos cualquier vértice, el string que le corresponde es un prefijo de uno o más strings del conjunto; así, cada vértice del trie se puede interpretar como una posición en uno o más strings del conjunto.

De hecho, los vértices del trie se pueden interpretar como estados de un autómata finito determinista. Desde cualquier estado podemos transicionar — usando alguna letra de entrada — a otros estados, es decir, a otra posición en el conjunto de strings. Por ejemplo, si en el diccionario hay un solo string $abc$ , y estamos parados en el vértice $ab$ , entonces usando la letra $c$ podemos ir al vértice $abc$ .

Así podemos entender las aristas del trie como transiciones en un autómata según la letra correspondiente. Sin embargo, en un autómata necesitamos tener transiciones para cada combinación de un estado y una letra. Si intentamos realizar una transición usando una letra y no hay arista correspondiente en el trie, de todos modos debemos ir a algún estado.

Más precisamente, supongamos que estamos en un estado correspondiente a un string $t$ , y queremos transicionar a un estado distinto usando el carácter $c$ . Si hay una arista etiquetada con esta letra $c$ , entonces podemos simplemente recorrer esa arista y obtener el vértice correspondiente a $t + c$ . Si no hay tal arista, como queremos mantener el invariante de que el estado actual es el matching parcial más largo en el string procesado, debemos encontrar el string más largo en el trie que sea un sufijo propio del string $t$ , e intentar realizar una transición desde allí.

Por ejemplo, sea el trie construido con los strings $ab$ y $bc$ , y estamos actualmente en el vértice correspondiente a $ab$ , que también es un vértice $\text{output}$ . Para transicionar con la letra $c$ , nos vemos forzados a ir al estado correspondiente al string $b$ , y desde allí seguir la arista con la letra $c$ .

Un autómata de Aho-Corasick basado en las palabras "a", "ab", "bc", "bca", "c" y "caa".
Las flechas azules son enlaces de sufijo, las verdes son enlaces terminales.

Un enlace de sufijo (suffix link) de un vértice $p$ es una arista que apunta al sufijo propio más largo del string correspondiente al vértice $p$ . El único caso especial es la raíz del trie, cuyo enlace de sufijo apuntará a sí misma. Ahora podemos reformular el enunciado sobre las transiciones en el autómata así: mientras no haya transición desde el vértice actual del trie usando la letra actual (o hasta que lleguemos a la raíz), seguimos el enlace de sufijo.

Así redujimos el problema de construir un autómata al problema de encontrar los enlaces de sufijo de todos los vértices del trie. Sin embargo, construiremos estos enlaces de sufijo, curiosamente, usando las transiciones construidas en el autómata.

Los enlaces de sufijo del vértice raíz y de todos sus hijos inmediatos apuntan al vértice raíz. Para cualquier vértice $v$ más profundo en el árbol, podemos calcular el enlace de sufijo de la siguiente manera: si $p$ es el ancestro de $v$ y $c$ es la letra que etiqueta la arista de $p$ a $v$ , vamos a $p$ , luego seguimos su enlace de sufijo y realizamos la transición con la letra $c$ desde allí.

Así, el problema de encontrar las transiciones se redujo al problema de encontrar enlaces de sufijo, y el problema de encontrar enlaces de sufijo se redujo al de encontrar un enlace de sufijo y una transición, salvo para vértices más cercanos a la raíz. Tenemos entonces una dependencia recursiva que podemos resolver en tiempo lineal.

Pasemos a la implementación. Nótese que ahora almacenaremos el ancestro $p$ y el carácter $pch$ de la arista de $p$ a $v$ para cada vértice $v$ . Además, en cada vértice almacenaremos el enlace de sufijo $\text{link}$ (o $-1$ si aún no se ha calculado), y en el arreglo $\text{go}[k]$ las transiciones de la máquina para cada símbolo (de nuevo $-1$ si aún no se ha calculado).


const int K = 26;

struct Vertex {
    int next[K];
    bool output = false;
    int p = -1;
    char pch;
    int link = -1;
    int go[K];

    Vertex(int p=-1, char ch='$') : p(p), pch(ch) {
        fill(begin(next), end(next), -1);
        fill(begin(go), end(go), -1);
    }
};

vector<Vertex> t(1);

void add_string(string const& s) {
    int v = 0;
    for (char ch : s) {
        int c = ch - 'a';
        if (t[v].next[c] == -1) {
            t[v].next[c] = t.size();
            t.emplace_back(v, ch);
        }
        v = t[v].next[c];
    }
    t[v].output = true;
}

int go(int v, char ch);

int get_link(int v) {
    if (t[v].link == -1) {
        if (v == 0 || t[v].p == 0)
            t[v].link = 0;
        else
            t[v].link = go(get_link(t[v].p), t[v].pch);
    }
    return t[v].link;
}

int go(int v, char ch) {
    int c = ch - 'a';
    if (t[v].go[c] == -1) {
        if (t[v].next[c] != -1)
            t[v].go[c] = t[v].next[c];
        else
            t[v].go[c] = v == 0 ? 0 : go(get_link(v), ch);
    }
    return t[v].go[c];
}

Es fácil ver que, gracias a la memoización de los enlaces de sufijo y las transiciones, el tiempo total para encontrar todos los enlaces de sufijo y las transiciones será lineal.

Para una ilustración del concepto, consultar la diapositiva número 103 de las diapositivas de Stanford .

Construcción basada en BFS

En lugar de calcular transiciones y enlaces de sufijo con llamadas recursivas a go y get_link, es posible calcularlos de abajo hacia arriba empezando desde la raíz. (De hecho, cuando el diccionario consiste en un solo string, obtenemos el conocido algoritmo de Knuth-Morris-Pratt.)

Este enfoque tendrá algunas ventajas sobre el descrito arriba, ya que, en lugar de la longitud total $m$ , su tiempo de ejecución depende solo del número de vértices $n$ del trie. Además, es posible adaptarlo a alfabetos grandes usando una estructura de datos de arreglo persistente, haciendo así que el tiempo de construcción sea $O(n \log k)$ en lugar de $O(mk)$ , lo cual es una mejora significativa dado que $m$ puede llegar hasta $n^2$ .

Podemos razonar inductivamente usando el hecho de que BFS desde la raíz recorre los vértices en orden de longitud creciente. Podemos asumir que cuando estamos en un vértice $v$ , su enlace de sufijo $u = link[v]$ ya está calculado con éxito, y que para todos los vértices de menor longitud las transiciones desde ellos también están completamente calculadas.

Supongamos que en este momento estamos en un vértice $v$ y consideramos un carácter $c$ . Esencialmente tenemos dos casos:

$go[v][c] = -1$ . En este caso, podemos asignar $go[v][c] = go[u][c]$ , que ya se conoce por la hipótesis de inducción;
$go[v][c] = w \neq -1$ . En este caso, podemos asignar $link[w] = go[u][c]$ .

De este modo, gastamos $O(1)$ de tiempo por cada par de un vértice y un carácter, lo que da un tiempo de ejecución $O(nk)$ . El overhead principal aquí es que copiamos muchas transiciones de $u$ en el primer caso, mientras que las transiciones del segundo caso forman el trie y suman $n$ sobre todos los vértices. Para evitar copiar $go[u][c]$ , podemos usar una estructura de datos de arreglo persistente, con la cual inicialmente copiamos $go[u]$ en $go[v]$ y luego solo actualizamos los valores de los caracteres en los que la transición diferiría. Esto lleva al algoritmo $O(n \log k)$ .

Aplicaciones

Encontrar todos los strings de un conjunto dado en un texto

Se nos da un conjunto de strings y un texto. Tenemos que imprimir todas las ocurrencias de todos los strings del conjunto en el texto dado en $O(\text{len} + \text{ans})$ , donde $\text{len}$ es la longitud del texto y $\text{ans}$ es el tamaño de la respuesta.

Construimos un autómata para este conjunto de strings. Ahora procesaremos el texto letra por letra usando el autómata, empezando en la raíz del trie. Si en algún momento estamos en el estado $v$ y la siguiente letra es $c$ , entonces transicionamos al siguiente estado con $\text{go}(v, c)$ , aumentando así la longitud de la subcadena de matching actual en $1$ , o disminuyéndola al seguir un enlace de sufijo.

¿Cómo podemos saber, para un estado $v$ , si hay algún matching con strings del conjunto? Primero, es claro que si estamos parados en un vértice $\text{output}$ , entonces el string correspondiente al vértice termina en esta posición del texto. Sin embargo, este no es de ningún modo el único caso posible de lograr un matching: si podemos alcanzar uno o más vértices $\text{output}$ moviéndonos por los enlaces de sufijo, entonces también habrá un matching correspondiente a cada vértice $\text{output}$ encontrado. Un ejemplo simple que demuestra esta situación se puede crear usando el conjunto de strings ${dabce, abc, bc}$ y el texto $dabc$ .

Así, si almacenamos en cada vértice $\text{output}$ el índice del string correspondiente (o la lista de índices si aparecen strings duplicados en el conjunto), entonces podemos encontrar en tiempo $O(n)$ los índices de todos los strings que hacen matching con el estado actual, simplemente siguiendo los enlaces de sufijo desde el vértice actual hasta la raíz. Esta no es la solución más eficiente, ya que da una complejidad total de $O(n ~ \text{len})$ . Sin embargo, esto se puede optimizar calculando y almacenando el vértice $\text{output}$ más cercano que se puede alcanzar usando enlaces de sufijo (esto a veces se llama enlace de salida o exit link). Este valor lo podemos calcular de forma perezosa en tiempo lineal. Así, para cada vértice podemos avanzar en tiempo $O(1)$ al siguiente vértice marcado en el camino de enlaces de sufijo, es decir, al siguiente matching. Así, para cada matching gastamos $O(1)$ de tiempo, y por lo tanto alcanzamos la complejidad $O(\text{len} + \text{ans})$ .

Si solo se quiere contar las ocurrencias y no encontrar los índices mismos, se puede calcular el número de vértices marcados en el camino de enlaces de sufijo para cada vértice $v$ . Esto se puede calcular en tiempo $O(n)$ en total. Así podemos sumar todos los matchings en $O(\text{len})$ .

Encontrar el string lexicográficamente más pequeño de una longitud dada que no hace matching con ninguno de los strings dados

Se da un conjunto de strings y una longitud $L$ . Tenemos que encontrar un string de longitud $L$ que no contenga ninguno de los strings, y obtener el lexicográficamente más pequeño de tales strings.

Podemos construir el autómata para el conjunto de strings. Recordemos que los vértices $\text{output}$ son los estados en los que tenemos un matching con un string del conjunto. Como en esta tarea tenemos que evitar matchings, no se nos permite entrar a tales estados. Por otro lado, podemos entrar a todos los demás vértices. Así, eliminamos todos los vértices “malos” de la máquina, y en el grafo restante del autómata encontramos el camino lexicográficamente más pequeño de longitud $L$ . Esta tarea se puede resolver en $O(L)$ por ejemplo con búsqueda en profundidad.

Encontrar el string más corto que contiene todos los strings dados

Aquí usamos las mismas ideas. Para cada vértice almacenamos una máscara que denota los strings que hacen matching en este estado. Entonces el problema se puede reformular así: estando inicialmente en el estado $(v = \text{root},~ \text{mask} = 0)$ , queremos alcanzar el estado $(v,~ \text{mask} = 2^n - 1)$ , donde $n$ es el número de strings del conjunto. Cuando transicionamos de un estado a otro usando una letra, actualizamos la máscara en consecuencia. Ejecutando una búsqueda en anchura podemos encontrar un camino al estado $(v,~ \text{mask} = 2^n - 1)$ de menor longitud.

Encontrar el string lexicográficamente más pequeño de longitud $L$ que contiene $k$ strings {data-toc-label=“Encontrar el string lexicográficamente más pequeño de longitud L que contiene k strings”}

Como en el problema anterior, calculamos para cada vértice el número de matchings que le corresponden (es decir, el número de vértices marcados alcanzables usando enlaces de sufijo). Reformulamos el problema: el estado actual está determinado por una terna de números $(v,~ \text{len},~ \text{cnt})$ , y queremos alcanzar desde el estado $(\text{root},~ 0,~ 0)$ el estado $(v,~ L,~ k)$ , donde $v$ puede ser cualquier vértice. Así podemos encontrar tal camino usando búsqueda en profundidad (y si la búsqueda mira las aristas en su orden natural, entonces el camino encontrado será automáticamente el lexicográficamente más pequeño).

Problemas

Referencias

Stanford’s CS166 - Aho-Corasick Automata (Condensed )