Ukkonen

Introducción General

El algoritmo de Ukkonen, presentado por Esko Ukkonen en 1985, es un método fundamental para resolver el problema de la búsqueda de cadenas aproximada (approximate string matching).

El problema consiste en encontrar las subcadenas de un texto $T$ (de longitud $n$) que coinciden con un patrón $P$ (de longitud $m$) permitiendo un máximo de $k$ errores, medidos por la distancia de edición.

La solución estándar mediante programación dinámica (DP), conocida como el algoritmo de Wagner-Fischer, tiene una complejidad de tiempo y espacio de $O(mn)$.

El propósito del algoritmo de Ukkonen es reducir esta complejidad en los casos comunes en los que la distancia de edición resultante ($s$) o el umbral de error permitido ($t$) son pequeños, es decir,

\[ s \ll \max(m, n) \quad \text{o} \quad t \ll \max(m, n) \]

La complejidad de los algoritmos de Ukkonen es:

$O(t \cdot \min(m, n))$ (para verificar un umbral máximo de error $t$), o
$O(s \cdot \min(m, n))$ (para calcular la distancia $s$),

lo cual es significativamente más rápido que $O(mn)$ cuando $s$ o $t$ son pequeños.

Definición

El algoritmo de Ukkonen se basa en optimizar el algoritmo básico de programación dinámica (PD).

Algoritmo Básico (Programación Dinámica)

La solución estándar $O(mn)$ utiliza una matriz de $(m+1) \times (n+1)$, donde cada celda $d_{i,j}$ almacena la distancia de edición entre el prefijo $A[1..i]$ y el prefijo $B[1..j]$.

Para calcular $d_{i,j}$, se toma el mínimo de tres opciones que representan las tres operaciones de edición:

La base es la matriz $d_{i,j}$, donde $d_{i,j}$ representa la distancia de edición mínima entre el prefijo $P[1..i]$ y $T[1..j]$. Se calcula mediante la siguiente recurrencia:

\[ d_{i,j} = \min \begin{cases} d_{i-1,j-1} + \begin{cases} 0, & \text{si } P[i] = T[j] \\ 1, & \text{si } P[i] \neq T[j] \end{cases} \\ d_{i-1,j} + 1, & \text{(eliminación)} \\ d_{i,j-1} + 1, & \text{(inserción)} \end{cases} \]

La observación fundamental de Ukkonen es que los valores en la matriz son monótonamente crecientes a lo largo de cualquier fila, columna o diagonal. Esto implica que si solo nos interesan las coincidencias con un costo $\le t$, no es necesario calcular toda la matriz.

Podemos dejar de calcular cualquier fila o columna tan pronto como el valor mínimo en ella exceda $t$.

Esta optimización da lugar a dos familias principales de algoritmos:

Variante 1: Test de Umbral (Costos Generales)

Esta variante no calcula la distancia exacta $s$, sino que responde a la pregunta de decisión: ¿Es la distancia de edición $s$ menor o igual a un umbral $t$?

El algoritmo solo calcula las celdas $d_{i,j}$ que se encuentran dentro de una banda diagonal alrededor de la diagonal principal.

Fundamento Teórico

Ukkonen demuestra que cualquier ruta de edición con un costo total $s$ debe permanecer dentro de una banda de diagonales.
Si el costo $s$ es pequeño, la banda es estrecha.

Si el algoritmo intenta calcular una celda $d_{i,j}$ fuera de esta banda, su costo garantizado será mayor que $t$, por lo que puede ser ignorada.

Parámetros y Fórmulas

$t$: umbral de distancia de edición que se desea verificar.
$\Delta$: costo mínimo de una operación de inserción o eliminación.
$p$: ancho de la banda diagonal, calculado como:

\[ p = \left\lfloor \frac{1}{2} \left( \frac{t}{\Delta} - |n - m| \right) \right\rfloor \]

Esta fórmula define los límites de la banda.

El algoritmo aplica la recurrencia clásica de la distancia de edición, pero solo para las celdas $(i,j)$ dentro de la banda:

Límites de la Banda

Para el caso $m \le n$, los índices de las celdas que se deben calcular están acotados por:

\[ \max(0, i - p) \le j \le \min(n, i + (n - m) + p) \]

Esto significa que, para cada fila $i$, solo se calculan las columnas $j$ que caen dentro de la banda diagonal definida por $p$. Cualquier celda fuera de estos límites se ignora, ya que su costo garantizado excedería el umbral $t$.

El resultado de esta optimización establece que es posible crear un algoritmo que verifica si la distancia de edición $s \le t$ con:

Tiempo: $O(t \cdot \min(m, n))$
Esto indica que solo necesitamos calcular aproximadamente $t$ celdas por fila (o columna) en la banda, en lugar de toda la matriz, lo que reduce el tiempo de ejecución cuando $t$ es pequeño.
Espacio: $O(\min(t, m, n))$
Solo se requiere almacenar las celdas dentro de la banda, lo que ahorra memoria respecto a almacenar la matriz completa de tamaño $(m+1) \times (n+1)$.

Variante 2: Cómputo Directo (Costo Unitario)

Esta variante calcula directamente la distancia $s$. Funciona únicamente cuando todas las operaciones (inserción, eliminación y sustitución) tienen un costo unitario.

Si todos los costos de edición son 1, el valor de una celda $d_{i,j}$ solo puede ser:

\[ d_{i,j} = \begin{cases} d_{i-1,j-1}, & \text{si hay coincidencia} \\ d_{i-1,j-1} + 1, & \text{si hay edición (inserción, eliminación o sustitución)} \end{cases} \]

Esto implica que los valores a lo largo de una misma diagonal son no decrecientes y aumentan únicamente en pasos de 1.

Debido a esto, no es necesario almacenar todos los valores $d_{i,j}$. El algoritmo conserva solo un valor por cada diagonal $k$ y costo $p$:

\[ f_{k,p} = \text{índice de fila } i_{\text{máx}} \text{ tal que } d_{i,j} = p \text{ y } j - i = k \]

En otras palabras, $f_{k,p}$ representa la posición más lejana alcanzada en la diagonal $k$ con exactamente $p$ errores. Para calcular $f_{k,p}$, el algoritmo toma el máximo entre las tres posibles operaciones anteriores (inserción, eliminación, sustitución) a lo largo de la diagonal.

Sustitución o error en la misma diagonal:

\[ t*{\text{sub}} = f*{k, p-1} + 1 \]

Inserción desde la diagonal $k-1$:

\[ t*{\text{ins}} = f*{k-1, p-1} \]

Eliminación desde la diagonal $k+1$:

\[ t*{\text{del}} = f*{k+1, p-1} + 1 \]

Luego se calcula:

\[ t = \max(t*{\text{sub}}, t*{\text{ins}}, t\_{\text{del}}) \]

El algoritmo “desliza” por la diagonal mientras haya coincidencias (que no añaden costo). Finalmente, se guarda:

\[ f\_{k,p} = t \]

El algoritmo itera para $p = 0, 1, 2, \dots$, calculando los valores $f_{k,p}$ en las diagonales relevantes.

El procedimiento finaliza cuando se cumple:

\[ f\_{n-m, p} = m \]

lo que indica que se ha alcanzado la celda $d_{m,n}$.

Para el caso de costo unitario, la distancia $s$ (y opcionalmente la secuencia de edición) se puede calcular con:

Tiempo: $O(s \cdot \min(m, n))$
Espacio: $O(s \cdot \min(s, m, n))$

Si no se requiere la secuencia de edición, el espacio puede reducirse a $O(\min(s, m, n))$.

Ejemplo de Uso

Bioinformática y Genética Molecular

Una de las aplicaciones más importantes del algoritmo se encuentra en el campo de la genética molecular.

Los biólogos trabajan con secuencias de ADN o con secuencias de proteínas, las cuales pueden tener millones o incluso miles de millones de caracteres (es decir, valores muy grandes de $n$).

Cuando un investigador descubre un nuevo gen (un patrón $P$ de longitud $m$), suele querer buscar secuencias similares dentro de un genoma completo $T$. Debido a la evolución, las secuencias “parientes” casi nunca son idénticas: difieren por pequeñas mutaciones, que corresponden exactamente a las operaciones de distancia de edición:

Sustitución: GATTACA → GCTTACA
Inserción: GATTACA → GACTTACA
Eliminación: GATTACA → GATACA

El objetivo no es encontrar coincidencias exactas, sino todas las subsecuencias en $T$ que tengan, por ejemplo, $k = 5$ mutaciones (errores) o menos.

El algoritmo clásico de distancia de edición (de complejidad $O(mn)$, como el de Wagner–Fischer) resulta computacionalmente muy costoso en este contexto.

Por ejemplo, si el patrón $P$ tiene $m = 100$ caracteres y el genoma $T$ tiene $n = 3.000.000.000$ (genoma humano), el número de operaciones sería:

\[ O(mn) = O(100 \times 3 \cdot 10^9) = O(3 \cdot 10^{11}) \]

En cambio, el algoritmo de Ukkonen, especialmente su Variante 1, que evalúa un umbral $t = k$, reduce la complejidad a:

\[ O(t \cdot \min(m,n)) \]

Por ejemplo, con $t = 5$:

\[ O(5 \times 3 \cdot 10^9) = O(1.5 \cdot 10^{10}) \]

Esto significa que el algoritmo puede ser unas 20 veces más rápido, ya que $m/t = 100/5 = 20$.

Corrección Ortográfica

Cuando un usuario escribe una palabra en un procesador de texto o en un motor de búsqueda, a menudo comete pequeños errores tipográficos.
Por ejemplo, escribe “algoritni” en lugar de “algoritmo”.

El sistema debe sugerir la palabra correcta dentro de un diccionario con cientos de miles o millones de palabras. Una búsqueda exacta de “algoritni” no daría resultados, por lo que se necesita una búsqueda aproximada que permita errores.

El sistema puede usar el algoritmo de Ukkonen (Variante 1) para buscar en el diccionario las palabras que estén a una distancia de edición pequeña respecto a la palabra escrita por el usuario:

Patrón (P): “algoritni”
Texto (T): Diccionario de palabras
Umbral (t): 1 o 2 (para errores comunes de escritura)

Durante la comparación, la banda diagonal del algoritmo se restringe a las posiciones donde el costo no supera el umbral $t$. De esta forma, la mayoría de las comparaciones (por ejemplo, “algoritni” vs. “casa”) se descartan rápidamente, ya que el costo excede el límite muy pronto.

El algoritmo encuentra con facilidad “algoritmo” (distancia de edición = 2, una sustitución y una eliminación) y la sugiere como la corrección más probable.

Implementación

A continuación se muestra una implementación en C++ del algoritmo de Ukkonen para búsqueda aproximada con un umbral de error $k$.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

void ukkonen_algorithm(const std::string& pattern, const std::string& text, int k) {
    int m = pattern.length();
    int n = text.length();
    std::vector<int> col(m + 1);
    for (int i = 0; i <= m; ++i) col[i] = i;
    int lact = std::min(k + 1, m);
    bool found = false;

    for (int pos = 1; pos <= n; ++pos) {
        int Cp = col[0];
        col[0] = 0;
        int Cn;
        int max_row_to_compute = (lact < m) ? (lact + 1) : m;

        for (int i = 1; i <= max_row_to_compute; ++i) {
            int Ci = col[i];
            if (pattern[i - 1] == text[pos - 1])
                Cn = Cp;
            else
                Cn = 1 + std::min({Cp, Ci, col[i - 1]});
            Cp = Ci;
            col[i] = Cn;
        }

        while (lact > 0 && col[lact] > k) lact--;

        if (lact == m && col[m] <= k) {
            found = true;
            int start_pos = pos - m;
            if (start_pos < 0) start_pos = 0;

            std::cout << "Coincidencia aproximada encontrada:" << std::endl;
            std::cout << "   Texto coincidente: \""
                      << text.substr(start_pos, std::min(m, n - start_pos)) << "\"" << std::endl;
            std::cout << "   Posicion en el texto: [" << start_pos
                      << ", " << pos - 1 << "]" << std::endl;
            std::cout << "   Distancia de edicion <= " << k << std::endl;
            std::cout << std::endl;
        }
        else if (lact < m) {
            lact++;
        }
    }

    if (!found) {
        std::cout << "No se encontraron coincidencias con una distancia de edicion <= "
                  << k << "." << std::endl;
    }
}

Texto: Born to Run is the third studio album by the American singer-songwriter Bruce Springsteen, released on August 25, 1975, by Columbia Records
Patron: Born to Rain

=== Busqueda con k = 1 ===
No se encontraron coincidencias con una distancia de edicion <= 1.

=== Busqueda con k = 2 ===
Coincidencia aproximada encontrada:
   Texto coincidente: "Born to Run "
   Posicion en el texto: [0, 10]
   Distancia de edicion <= 2

Explicación de la Función `ukkonen_algorithm()`

La función ukkonen_algorithm() recibe tres parámetros:

pattern: la cadena que se desea buscar (por ejemplo, una palabra o frase).
text: el texto completo donde se realiza la búsqueda.
k: el número máximo de diferencias (errores) permitidas.

El objetivo de la función es encontrar posiciones en el texto donde el patrón aparece con una distancia de edición menor o igual a $k$.

Funcionamiento interno y variables utilizadas

Inicialización de variables:
$m$: longitud del patrón.
$n$: longitud del texto.
col: vector que representa una columna de la matriz de distancias entre el patrón y el texto. Se usa para almacenar los costos acumulados de las operaciones de edición.
$lact$ (“last active row”): indica hasta qué fila del patrón se deben calcular las distancias. Se inicializa como $\min(k + 1, m)$ para limitar el cálculo dentro del margen de error permitido.
found: variable booleana que indica si se ha encontrado una coincidencia aproximada.
Recorrido del texto:
El algoritmo avanza carácter por carácter en el texto ($pos$), comparando el patrón con la subcadena que termina en esa posición.
Cálculo de distancias dentro de la banda diagonal:
Ukkonen optimiza el cálculo limitando la evaluación a una banda diagonal alrededor de la diagonal principal, cuyo ancho depende de $k$.
Esta banda incluye solo las posiciones con una posible distancia válida, y en el código se controla mediante la variable $lact$, que ajusta cuántas filas se procesan según el valor de $k$.
Actualización de la columna de distancias:
Dentro de esa banda acotada, el algoritmo actualiza el vector col:
$Cp$: valor de la diagonal superior izquierda (substitución).
$Ci$: valor de la celda superior (eliminación).
$col[i-1]$: valor de la celda izquierda (inserción).

Si los caracteres del patrón y del texto coinciden, el costo no aumenta; si difieren, se añade 1 al mínimo de esos tres valores:

$$ col[i] = \begin{cases} Cp, & \text{si } pattern[i-1] = text[pos-1] \ 1 + \min(Cp, Ci, col[i-1]), & \text{si difieren} \end{cases} $$

Ajuste dinámico de la banda:
Luego, se reduce $lact$ si los valores calculados superan el umbral $k$.
De esta manera, la banda se “estrecha” automáticamente cuando ya no es posible obtener coincidencias válidas, reduciendo los cálculos innecesarios.
Verificación y reporte de coincidencias:
Si el costo en la última fila ($col[m]$) es menor o igual a $k$, significa que se encontró una coincidencia dentro del umbral permitido.
El algoritmo imprime:
el fragmento del texto que coincide,
la posición donde aparece,
la distancia de edición máxima admitida.
Salida final:
Si no se encuentra ninguna coincidencia válida, el programa lo informa explícitamente.

Ejemplo

Texto (T):
“Born to Run is the third studio album by the American singer-songwriter Bruce Springsteen, released on August 25, 1975, by Columbia Records”
Patrón (P): “Born to Rain”

Búsqueda con $k = 1$
No se encontraron coincidencias. Esto ocurre porque entre “Born to Rain” y “Born to Run” hay dos diferencias (las letras $a \rightarrow u$ y $i \rightarrow n$), por lo que la distancia de edición mínima es 2, superando el límite $k = 1$.

Búsqueda con $k = 2$
Se encuentra una coincidencia aproximada en el inicio del texto: “Born to Run” se reconoce como similar a “Born to Rain” con una distancia de edición de 2.

La salida muestra:

Texto coincidente: “Born to Run”
Posición: [0, 10]
Distancia de edición: ≤ 2

Referencias

Ukkonen, E. (1985). Algorithms for Approximate String Matching. Information and Control, 64, 100–118.
Myers, G. (Año de publicación). Myers bit-vector verification. FU Berlin. Recuperado de: https://www.mi.fu-berlin.de/wiki/pub/ABI/RnaSeqP4/myers-bitvector-verification.pdf