Episode Distance

Definición

Sea \(A\) un texto de largo \(n\) y \(P\) un “episodio” (patrón) de largo \(m\). Se dice que un substring o ventana \(A[i,j]\) de \(A\) contiene a P como subsecuencia si:

\[ \forall k \in \{ 1,\dots,m\}\ \exists p_1,p_2,\dots,p_m \ , \ i \leq p_1 < p_2 < \dots < p_k \leq j \ : \ A[p_k] = P[k] \]

Es decir, existe un conjunto de índices ordenados dentro del substring que corresponden a las posiciones de los caracteres de \(P\) , sin necesariamente ser consecutivos, pero obedeciendo su orden original.

Se define la distancia de episodio como el tamaño del substring mínimo que contenga a \(P\) como subsecuencia, según la definición anterior. Permite medir qué tan disperso o compacto se encuentra \(P\) dentro del texto.

Ejemplo

Sean un string A = abxcaydbe y un patrón P = abe. Encontrar una ventana de A sería recorrer linealmente marcando las primeras ocurrencias de cada carácter de P.

A[0] = a, luego A[1] = b y finalmente A[8] = e, entonces la ventana que contiene a P en A[0,8], de largo 9. Sin embargo, ¿existe una ventana más pequeña que contenga a P como subsecuencia?
Si se empieza a recorrer desde A[2] = x, la primera a es A[4], seguida por b en A[6] y finalmente por c en A[8]. Por lo tanto A[4,8], de largo 5, es la ventana que contiene a P como subsecuencia y su tamaño es mínimo. Esto define la distancia de episodio del patrón P en el texto A como 5.

Esto posiciona al problema de la búsqueda de la ventana mínima que contenga al patrón como subsecuencia, también llamado episode matching, como un problema de interés.

Utilidades

Uno de los usos de la distancia de episodio se observa al realizar data mining temporal, analizando secuencias de eventos en el tiempo. Imaginemos una secuencia “ruidosa” de eventos en un determinado contexto, por ejemplo, una persona interactuando con una página web de compra de artículos. Una secuencia de compra ideal serían todos los eventos relevantes consecutivos:

''Añadir al carro'' -> ''Checkout'' -> ''Confirmación de pago''

Sin embargo, esta secuencia de eventos se ve interrumpida por más eventos intermedios, por ejemplo:

''Añadir al carro'' -> ''Ver producto relacionado'' -> ''Revisar reseñas'' -> ...
... -> ''Checkout'' -> ''Agregar cupón de descuento'' -> ''Confirmación de pago''.

Estos eventos intermedios no son relevantes dentro de la secuencia de interés, pero también se ven registrados en el log de la página para otros usos.

Detectar qué tan dispersos se encuentran los eventos permitiría discernir varios detalles relevantes a ellos, como la presencia de distractores en la interfaz de la página web, impidiendo un proceso expedito de compra, o la falta de información accesible, forzando al cliente a regresar a páginas anteriores buscando información, entre otros.

Este uso se puede extender a otra áreas como la ciberseguridad, rastreando secuencias de posibles ataques a un sistema, o en bioinformática, buscando secuencias de reacciones que nunca suceden de manera consecutiva, sino que se encuentran rodeadas de otros procesos no relacionados en un sistema complejo de reacciones.

Algoritmo

Una opción de algoritmo para el problema de episode matching se basa en la siguiente premisa:

“Para cada posible posición inicial \(i\), se puede obtener de manera greedy el índice \(j\) más pequeño tal que \(A[i,j]\) contenga a \(P\) como subsecuencia. Luego, la distancia de episodio es la posición inicial (\(i\)) mínima de todas las posibles posiciones iniciales de \(j-1+i.\)”

Para ello, se precomputa una tabla de “próximas ocurrencias”, con el objetivo de realizar consultas sobre ella más adelante:

Construcción de tabla de “próximas ocurrencias”:

Para cada carácter \(c\) del alfabeto \(\Sigma\), next[i][c] es el mínimo índice \(i > j\) tal que A[j] = c, o -1 en caso de que \(j\) no exista.

Se computa la tabla desde el final del texto, definiendo todos los valores a -1 inicialmente. Para cada posición \(i\), se copian todos los valores desde next[i+1] y se actualiza next[i][A[i]] = i+1.

Utilizando la tabla:

Para cada posición inicial \(i\), se “escanea” el patrón \(P[i,m]\) (indexando desde 1), utilizando la tabla:

Se inicializa pos = i + 1.
Para cada carácter \(P[k]\), se redefine pos = next[pos - 1][P[k]]. Si pos = -1, significa que no es posible encontrar \(P[k]\) desde este inicio. Por lo tanto se rompe el loop.
Cuando el loop termine exitosamente, el último valor de pos da la posición final \(j\), y la ventana sería \([i,j]\), de largo \(j - i\).

De aquí se extrae el largo mínimo de ventana entre todos los \(i\) válidos.

Obteniendo la distancia de episodio:

Finalmente, la distancia de episodio es el largo de ventana mínimo entre todos los \(i\) válidos, o -1 en caso de que \(P\) no sea subsecuencia de \(A\).

Complejidad temporal y espacial

Dado que la tabla se computa evaluando todas las posiciones del texto por cada elemento del alfabeto, el proceso de precomputación tiene complejidad \(\mathcal{O}(n\cdot|\Sigma|)\), que para casos de alfabetos pequeños es simplemente \(\mathcal{O}(n)\). La complejidad espacial también es proporcional al largo del texto y el tamaño del alfabeto, al ser una matriz de \(n\times |\Sigma|\).

Por otro lado, el proceso de consulta una vez precomputada tiene complejidad \(\mathcal{O}(m)\)., dado que depende del largo del patrón , consultando a la tabla una vez por cada carácter, reiniciando una cantidad finita de veces en caso de no encontrar ocurrencias. Al ser una consu

Implementación

A continuación se presenta un pseudocódigo y una implementación de C++ del algoritmo anteriormente descrito, para el caso de un alfabeto pequeño (ASCII). Cabe destacar que este algoritmo es solo una posible solución, y que existen otras soluciones recomendadas para alfabetos muy grandes (i.e. Unicode).

Pseudocódigo

Implementación

#include <climits>
#include <iostream>
#include <vector>

using namespace std;

// Obtener distancia de episodio: largo de ventana mínimo en A tal que contiene a P como
// subsecuencia
int episode_distance(string A, string P) {
    int n = A.size(), m = P.size();
    int INF = INT_MAX;
    int best = INF;

    // Precomputar tabla de próximas ocurrencias
    vector<vector<int>> next(n + 2, vector<int>(256, -1));
    //Se utiliza ASCII como alfabeto de referencia
    for (int c = 0; c < 256; c++) next[n][c] = next[n + 1][c] = -1;

    for (int i = n - 1; i >= 0; i--) {
        next[i] = next[i + 1];
        next[i][(unsigned char)A[i]] = i + 1; // almacena posiciones indexando desde 1
    }

    // Para cada inicio de A, se intenta encontrar P como subsecuencia
    for (int start = 0; start < n; start++) {
        int pos = start + 1; // próxima posición inicial de A (indexado desde 1)
        bool ok = true;
        for (char ch : P) {
            pos = next[pos - 1][(unsigned char)ch];
            if (pos == -1) { ok = false; break; }
        }
        if (ok) {
            int end = pos; // posición final (indexado desde 1)
            best = min(best, end - start);
        }
    }

    return (best == INF) ? -1 : best;
}

int main() {
    string T = "abbacbcacbbc";
    string P = "abc";

    int dist = episode_distance(T, P);

    if (dist == -1)
        cout << "Pattern not found as subsequence\n";
    else
        cout << "Episode distance = " << dist << "\n";
}

El output de esta implementación es el siguiente:

Episode distance = 4

Referencias

Das, G., Fleischer, R., Gąsieniec, L., Gunopulos, D., & Kärkkäinen, J. (1997). Episode matching. Annual Symposium on Combinatorial Pattern Matching (pp. 12–27). Springer, Berlin, Heidelberg.
Mannila, H., Toivonen, H., & Verkamo, A. I. (1997). Discovery of frequent episodes in event sequences. Data Mining and Knowledge Discovery, 1(3), 259–289.