Programación dinámica: LCS y distancia de edición

De qué trata este capítulo

¿Qué tan diferentes son dos strings? ¿Qué tan parecidos son dos archivos? Esas preguntas — las que están detrás de los correctores ortográficos, diff, el autocorrector, la búsqueda difusa y el alineamiento de ADN — se responden con programación dinámica sobre dos secuencias a la vez. La distancia de edición (distancia de Levenshtein) cuenta el mínimo de ediciones de un solo carácter — insertar, borrar, sustituir — para convertir un string en otro; kitten se vuelve sitting en tres ediciones. La subsecuencia común más larga (LCS) encuentra la racha más larga de caracteres (en orden, con huecos permitidos) que ambos strings comparten; así es como diff alinea dos versiones de un archivo. Las dos son DP sobre una tabla de dos dimensiones indexada por cuánto llevas consumido de cada string, donde cada celda compara un carácter de cada lado y combina las respuestas de sus vecinas. A diferencia de la tabla pseudo-polinomial de la mochila, esta sí es genuinamente polinomial — O(m·n) — y la recursión ingenua que reemplaza es exponencial. Este capítulo construye ambas, llena en pantalla la clásica cuadrícula de Levenshtein y muestra el factor de 250 que la DP se ahorra.

Un poco de historia

Los dos algoritmos vienen de campos distintos que terminaron convergiendo en la misma DP. Vladimir Levenshtein definió la distancia de edición en 1965 en el contexto de los códigos correctores de errores — midiendo cuántos errores de carácter podía aguantar una palabra transmitida. De forma independiente, los biólogos necesitaban alinear secuencias de ADN y proteínas para medir similitud evolutiva, y Saul Needleman y Christian Wunsch publicaron esencialmente el mismo programa dinámico en 1970 para alineamiento global de secuencias, seguido en 1981 por la variante de alineamiento local de Temple Smith y Michael Waterman — ambos pilares de la bioinformática, y ambos distancia de edición con puntajes específicos del dominio. La subsecuencia común más larga se volvió la base de la comparación de archivos: la utilería diff de Unix (1976, Doug McIlroy y compañía) y todos los sistemas de control de versiones desde entonces calculan un LCS de las líneas de dos archivos para mostrar qué cambió. Que tres campos — teoría de códigos, biología computacional y programación de sistemas — hayan llegado a la misma tabla bidimensional dice mucho de lo fundamental que es la pregunta "¿qué tan parecidas son estas dos secuencias?", y de lo bien que se presta a la programación dinámica.

La intuición

Piensa en convertir A en B un carácter a la vez, trabajando desde el final. Mira el último carácter de cada uno. Si son iguales, no cuestan nada — los alineas y recurres sobre el resto. Si son distintos, tienes tres movimientos y te quedas con el más barato: borrar el último carácter de A (y recurrir sobre el resto de A contra todo B), insertar el último carácter de B (recurrir sobre todo A contra el resto de B), o sustituir el último de A por el de B (recurrir sobre el resto de ambos). Cada movimiento cuesta una edición. Esa recurrencia es correcta pero exponencial, porque los mismos subproblemas — "distancia entre este prefijo de A y aquel prefijo de B" — se repiten entre las ramas, exactamente la situación de subproblemas traslapados de los dos capítulos anteriores.

La programación dinámica acomoda esos subproblemas en una cuadrícula. Sea dp[i][j] la distancia de edición entre los primeros i caracteres de A y los primeros j de B. La primera fila y la primera columna son fáciles: convertir el string vacío en un prefijo de j caracteres toma j inserciones, así que dp[0][j] = j, y por simetría dp[i][0] = i. Cualquier otra celda es el mínimo de tres vecinas: dp[i-1][j] + 1 (borrar, viniendo de arriba), dp[i][j-1] + 1 (insertar, desde la izquierda) y dp[i-1][j-1] + costo (coincidencia o sustitución, desde la diagonal, donde el costo es 0 si los caracteres son iguales y 1 si no). Llenas la cuadrícula fila por fila y la celda de la esquina inferior derecha es la respuesta. La subsecuencia común más larga es la misma cuadrícula con otra regla: cuando los caracteres coinciden, dp[i][j] = dp[i-1][j-1] + 1 (extiendes la diagonal); cuando no, dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (descartas un carácter del lado que más convenga). En ambos casos, la cuadrícula calcula cada uno de los m·n subproblemas exactamente una vez, y rastrear las decisiones hacia atrás desde la esquina recupera el script de edición real o la subsecuencia real.

Complejidad: cómo escala

La DP es O(m·n) en tiempo y espacio — una pasada sobre la cuadrícula de m×n, O(1) por celda. (El espacio puede bajar a O(min(m,n)) con el truco del arreglo rodante, guardando solo la fila actual y la anterior, si no necesitas reconstruir el alineamiento.) La recursión ingenua, en cambio, es exponencial — más o menos O(3^min(m,n)), ramificándose en tres cada vez que hay una diferencia y resolviendo una y otra vez los mismos subproblemas. El enfrentamiento cuenta el trabajo directo: llamadas recursivas ingenuas contra celdas de la cuadrícula de la DP, conforme crecen los strings:

En escala logarítmica la línea de la versión ingenua sube en picada — exponencial — mientras que la de la DP casi no se mueve, creciendo como el producto de las longitudes. Con longitud 12 (y un alfabeto de dos letras, que maximiza la ramificación), la recursión ingenua hizo unas 42,000 llamadas; la DP llena 169 celdas — 250 veces menos trabajo, y la brecha explota conforme crece la longitud (con longitud 20 la versión ingenua haría cientos de millones de llamadas; la DP llena 441 celdas). Esta es otra vez la jugada característica de la programación dinámica: un algoritmo exponencial vuelto polinomial nada más por calcular cada subproblema una sola vez. La diferencia entre "comparar dos strings de 12 caracteres al instante" y "quedarse colgado con dos strings de 30 caracteres" es justo la memoria que da la cuadrícula.

En qué es buena y en qué no

La DP sobre secuencias es la herramienta correcta cada vez que necesitas comparar, alinear o medir la similitud de dos secuencias ordenadas. Los correctores ortográficos y el autocorrector rankean correcciones candidatas por distancia de edición contra la palabra mal escrita. La búsqueda difusa y el enlace de registros emparejan strings aproximadamente iguales. diff, git y cualquier herramienta de merge calculan el LCS de las líneas para mostrar y reconciliar cambios. La bioinformática alinea secuencias de ADN, ARN y proteínas con variantes ponderadas (Needleman-Wunsch para alineamiento global, Smith-Waterman para local) para encontrar relaciones evolutivas y regiones funcionales. La detección de plagio, la post-corrección de OCR, la evaluación de reconocimiento de voz y el diffing de versiones de cualquier dato estructurado también la usan. Además generaliza limpiamente — costos de edición distintos, penalizaciones de hueco afines y alineamiento múltiple son todos elaboraciones de la misma cuadrícula.

Donde sufre es en la escala. O(m·n) está bien para palabras y secuencias cortas, pero sale caro con secuencias muy largas — dos genomas de un millón de caracteres dan una cuadrícula de 10¹² celdas, inviable de forma directa, y por eso la bioinformática usa DP en banda (calcular solo las celdas cercanas a la diagonal), heurísticas de semilla y extensión (BLAST) o divide y vencerás en espacio lineal (el algoritmo de Hirschberg, que calcula el alineamiento en tiempo O(m·n) pero espacio O(min)). Para comparación masiva o aproximada, los índices especializados y el hashing (como MinHash y el locality-sensitive hashing que se usa en detección de casi duplicados) reemplazan a la DP exacta. Y la versión básica compara dos secuencias; alinear muchas a la vez (alineamiento múltiple de secuencias) es NP-duro y necesita heurísticas. La DP sobre secuencias es exacta y clara para pares de longitud moderada, y es el punto de partida — no la última palabra — para trabajo a escala de genomas.

Los datos, o las entradas

El enfrentamiento cuenta las llamadas recursivas ingenuas contra el número de celdas de la cuadrícula de la DP para la distancia de edición, sobre strings aleatorios de dos letras (que maximizan la ramificación) de longitud creciente — exponencial contra polinomial. La corrección se verifica a fondo: sobre 1500 pares de strings aleatorios, la distancia de edición de la DP debe ser igual a la de la recursión ingenua, el script de edición reconstruido debe transformar realmente A en B (y tener exactamente distance operaciones que no sean coincidencias), y la longitud del LCS junto con la subsecuencia devuelta deben coincidir con un LCS por fuerza bruta y ser una subsecuencia común genuina de ambos. La animación llena la cuadrícula de distancia de edición para el ejemplo de libro de texto kitten → sitting, una fila a la vez, y luego traza el camino del alineamiento.

Constrúyelo, una función a la vez

Distancia de edición — la DP de tres movimientos con reconstrucción del script de edición:

def edit_distance(a, b):
    """Levenshtein distance: fewest insert/delete/substitute edits to turn `a` into `b`. dp[i][j] is
    the distance between the first i characters of a and the first j of b. Deleting a char costs
    dp[i-1][j]+1, inserting costs dp[i][j-1]+1, and matching/substituting costs dp[i-1][j-1] plus 0
    if the characters are equal else 1. Fill the grid and dp[m][n] is the answer. O(m·n). Returns
    (distance, operations) where operations is the reconstructed edit script."""
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i                             # delete all of a's first i chars
    for j in range(n + 1):
        dp[0][j] = j                             # insert all of b's first j chars
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            cost = 0 if a[i - 1] == b[j - 1] else 1
            dp[i][j] = min(dp[i - 1][j] + 1,      # delete a[i-1]
                           dp[i][j - 1] + 1,      # insert b[j-1]
                           dp[i - 1][j - 1] + cost)   # match (cost 0) or substitute (cost 1)
    # backtrace the choices to recover the actual edit script
    ops, i, j = [], m, n
    while i > 0 or j > 0:
        if i > 0 and j > 0 and dp[i][j] == dp[i - 1][j - 1] + (a[i - 1] != b[j - 1]):
            ops.append(("match" if a[i - 1] == b[j - 1] else "sub", a[i - 1], b[j - 1]))
            i, j = i - 1, j - 1
        elif i > 0 and dp[i][j] == dp[i - 1][j] + 1:
            ops.append(("del", a[i - 1], None))
            i -= 1
        else:
            ops.append(("ins", None, b[j - 1]))
            j -= 1
    return dp[m][n], ops[::-1]

Subsecuencia común más larga — la misma cuadrícula, con la regla de que la coincidencia extiende la diagonal:

def lcs(a, b):
    """Longest common subsequence: the longest string that is a subsequence of both `a` and `b`
    (characters in order, gaps allowed). dp[i][j] is the LCS length of the first i chars of a and
    first j of b: if the characters match, extend the diagonal (dp[i-1][j-1]+1); otherwise take the
    better of dropping a's char (dp[i-1][j]) or b's char (dp[i][j-1]). O(m·n). Returns (length,
    subsequence). This is the engine behind diff."""
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    # walk back to build the subsequence itself
    out, i, j = [], m, n
    while i > 0 and j > 0:
        if a[i - 1] == b[j - 1]:
            out.append(a[i - 1])
            i, j = i - 1, j - 1
        elif dp[i - 1][j] >= dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return dp[m][n], "".join(reversed(out))

Míralo funcionar

Aquí está la cuadrícula de distancia de edición para kitten → sitting, llenada una fila a la vez. La fila de arriba y la columna de la izquierda son los casos base — convertir el string vacío en un prefijo toma esa cantidad de inserciones o borrados, así que van contando 0, 1, 2, 3… Cada celda interior toma el mínimo de tres vecinas: la de arriba más uno (borrar), la de la izquierda más uno (insertar) y la diagonal más cero-si-los-caracteres-coinciden-o-uno-si-no. Las celdas en verde azulado marcan dónde los dos caracteres son iguales — los movimientos diagonales "gratis". Observa cómo los números se propagan hacia abajo y hacia la derecha, cada celda a una edición de distancia de una vecina más barata, hasta que la esquina inferior derecha marca 3. El camino naranja traza el alineamiento hacia atrás: sustituir k→s, conservar itt gratis, sustituir e→i, conservar n, insertar g — tres ediciones, y puedes leer la transformación exacta sobre la diagonal:

El código completo

La pestaña desde cero es la distancia de edición (con el script de edición reconstruido) y LCS (con la subsecuencia reconstruida); la pestaña de librería es la recursión exponencial ingenua que se usa para verificar y para contrastar, con una nota sobre el difflib de Python para diffs y similitud de verdad. Cambia entre ellas — la recursión ingenua es más corta y obviamente correcta, y es exponencial; la DP es la misma recurrencia con la cuadrícula como memoria.

"""Edit distance and longest common subsequence — dynamic programming on two sequences at once,
and two of the most useful algorithms in computing. Edit distance (Levenshtein distance) counts the
fewest single-character edits — insert, delete, or substitute — to turn one string into another; it's
what spell-checkers, autocorrect, fuzzy search, and DNA alignment run on. Longest common subsequence
finds the longest sequence of characters appearing in both strings in order (not necessarily
contiguous); it's what `diff` and version control use to line up files.

Both are DP over a two-dimensional state: a table indexed by (how much of string A, how much of
string B) we've consumed. Each cell compares one character of each string and combines the answers
of neighboring cells — diagonal (both consumed), up (one consumed), left (the other). Unlike
knapsack's pseudo-polynomial table, this one is genuinely polynomial: O(m·n) in the two lengths.
The naive recursion, exploring every alignment, is exponential — the same overlapping-subproblems
blowup dynamic programming exists to prevent.
"""


# region: edit_distance
def edit_distance(a, b):
    """Levenshtein distance: fewest insert/delete/substitute edits to turn `a` into `b`. dp[i][j] is
    the distance between the first i characters of a and the first j of b. Deleting a char costs
    dp[i-1][j]+1, inserting costs dp[i][j-1]+1, and matching/substituting costs dp[i-1][j-1] plus 0
    if the characters are equal else 1. Fill the grid and dp[m][n] is the answer. O(m·n). Returns
    (distance, operations) where operations is the reconstructed edit script."""
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i                             # delete all of a's first i chars
    for j in range(n + 1):
        dp[0][j] = j                             # insert all of b's first j chars
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            cost = 0 if a[i - 1] == b[j - 1] else 1
            dp[i][j] = min(dp[i - 1][j] + 1,      # delete a[i-1]
                           dp[i][j - 1] + 1,      # insert b[j-1]
                           dp[i - 1][j - 1] + cost)   # match (cost 0) or substitute (cost 1)
    # backtrace the choices to recover the actual edit script
    ops, i, j = [], m, n
    while i > 0 or j > 0:
        if i > 0 and j > 0 and dp[i][j] == dp[i - 1][j - 1] + (a[i - 1] != b[j - 1]):
            ops.append(("match" if a[i - 1] == b[j - 1] else "sub", a[i - 1], b[j - 1]))
            i, j = i - 1, j - 1
        elif i > 0 and dp[i][j] == dp[i - 1][j] + 1:
            ops.append(("del", a[i - 1], None))
            i -= 1
        else:
            ops.append(("ins", None, b[j - 1]))
            j -= 1
    return dp[m][n], ops[::-1]
# endregion


# region: lcs
def lcs(a, b):
    """Longest common subsequence: the longest string that is a subsequence of both `a` and `b`
    (characters in order, gaps allowed). dp[i][j] is the LCS length of the first i chars of a and
    first j of b: if the characters match, extend the diagonal (dp[i-1][j-1]+1); otherwise take the
    better of dropping a's char (dp[i-1][j]) or b's char (dp[i][j-1]). O(m·n). Returns (length,
    subsequence). This is the engine behind diff."""
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    # walk back to build the subsequence itself
    out, i, j = [], m, n
    while i > 0 and j > 0:
        if a[i - 1] == b[j - 1]:
            out.append(a[i - 1])
            i, j = i - 1, j - 1
        elif dp[i - 1][j] >= dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return dp[m][n], "".join(reversed(out))
# endregion


# region: edit_table
def edit_table(a, b):
    """The full edit-distance table plus, for each cell, which neighbor it came from — used to
    animate the fill and highlight the diagonal alignment path. Move codes: 'diag' (match/sub),
    'up' (delete), 'left' (insert)."""
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            cost = 0 if a[i - 1] == b[j - 1] else 1
            dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + cost)
    return dp
# endregion

"""The contrast and the library reference. Two things:

- `naive_edit` is the exponential recursion — the same recurrence as the DP but with no memory, so
  it re-solves overlapping subproblems and blows up. It's the correctness cross-check on small
  strings and the 'why DP' contrast in the face-off.
- Python's `difflib` is the standard-library tool that USES these ideas: SequenceMatcher computes
  matching blocks (closely related to LCS) for diffs and similarity ratios. It's what powers
  `difflib.unified_diff`, `get_close_matches`, and the '?' hints in doctest failures.

    import difflib
    difflib.SequenceMatcher(None, a, b).ratio()          # a similarity score in [0,1]
    list(difflib.unified_diff(lines_a, lines_b))         # a line-by-line diff

difflib's algorithm isn't textbook LCS (it favors longer contiguous matches), so it's used here for
illustration, not as an exact LCS oracle — that's what the brute-force check in the trace generator is.
"""


# region: naive
def naive_edit(a, b, calls=None):
    """The direct recursion for edit distance: compare the last characters, and if they differ, try
    all three edits and take the best. No memoization → the same (i, j) subproblems are recomputed
    exponentially many times. `calls` counts invocations to expose the blowup."""
    if calls is not None:
        calls[0] += 1
    if not a:
        return len(b)
    if not b:
        return len(a)
    if a[-1] == b[-1]:
        return naive_edit(a[:-1], b[:-1], calls)
    return 1 + min(
        naive_edit(a[:-1], b, calls),            # delete
        naive_edit(a, b[:-1], calls),            # insert
        naive_edit(a[:-1], b[:-1], calls),       # substitute
    )
# endregion

Desde cero vs librería

La distancia de edición y LCS cristalizan el patrón de DP en dos dimensiones, y la cuadrícula de la animación es el modelo mental que vale la pena conservar: los problemas de alineamiento de secuencias son caminos a través de una cuadrícula, donde estás eligiendo la ruta más barata de esquina a esquina, y los movimientos (diagonal, abajo, derecha) son las ediciones. Esa imagen generaliza a cada variante — ediciones ponderadas, penalizaciones de hueco, alineamiento local — como costos distintos sobre la misma cuadrícula, y por eso un solo diagrama le sirve igual a la teoría de códigos, a la biología y a la comparación de archivos. El capítulo también cierra el arco de programación dinámica: los fundamentos mostraron la tabla unidimensional (cambio de monedas), la mochila mostró una tabla bidimensional con la trampa pseudo-polinomial, y este muestra una tabla bidimensional genuinamente polinomial sobre dos secuencias. En producción usarías difflib para diffs, una librería de corrección ortográfica para las correcciones, o BLAST para genomas; construir la cuadrícula tú mismo es lo que hace legibles la salida de diff, las sugerencias del autocorrector y un alineamiento de secuencias como el mismo cálculo de camino-más-barato-por-una-cuadrícula.

Dónde te la vas a encontrar

La DP sobre secuencias corre todo el tiempo, muchas veces sin que la veas. Todo corrector ortográfico y todo autocorrector rankea sugerencias por distancia de edición. git, diff y las herramientas de code review calculan el LCS de las líneas para mostrar qué cambió y para hacer merge de ramas. Los buscadores y las bases de datos hacen emparejamiento difuso y tolerancia a errores de dedo con distancia de edición. La bioinformática alinea ADN y proteínas con distancia de edición ponderada (Needleman-Wunsch, Smith-Waterman) como cimiento de la genómica — BLAST, la herramienta más usada en biología, es alineamiento de secuencias con semillas. Los sistemas de OCR y de reconocimiento de voz evalúan sus salidas contra referencias con ella (la tasa de error por palabra es distancia de edición). El enlace de registros y la deduplicación de datos emparejan entradas casi idénticas. Los detectores de plagio y la detección de páginas web casi duplicadas usan medidas tipo LCS. Y la comparación estilo diff de cualquier dato estructurado — configuración, ASTs, documentos — se reduce a estas cuadrículas. Donde sea que se pregunte "¿qué tan parecidas son estas dos secuencias?", esta DP es la que responde.

Conclusiones

La distancia de edición y la subsecuencia común más larga comparan dos secuencias con una cuadrícula DP bidimensional dp[i][j] sobre prefijos de cada string, donde cada celda combina tres vecinas — diagonal (coincidencia/sustitución), arriba (borrar), izquierda (insertar) — en O(1), para un total de O(m·n), y rastrear hacia atrás recupera el alineamiento en sí. Son la misma cuadrícula con el movimiento de sustitución prendido (distancia de edición) o apagado (LCS, ligado a la distancia de edición por m + n − 2·LCS). La DP vuelve polinomial la recursión exponencial ingenua del alineamiento — 250× menos trabajo con longitud 12 — y es el motor detrás de la corrección ortográfica, diff y el alineamiento de ADN. Los problemas de secuencias son caminos-más-baratos por una cuadrícula.

Con esto cierra la trilogía central de programación dinámica. El siguiente capítulo se va a otro paradigma, el de los problemas donde tienes que buscar entre posibilidades en vez de llenar una tabla: backtracking. N-Reinas, Sudoku y la generación de todos los subconjuntos y permutaciones se resuelven construyendo un candidato poco a poco y abandonándolo — "podando" — en cuanto deja de poder llevar a una solución, una exploración disciplinada y en profundidad del espacio de decisiones que recupera la fuerza bruta exponencial solo donde el problema de verdad lo exige.