Algoritmo de la Subsequencia Común Más Larga (LCS) en Python

Enfoques Algorítmicos

def lcs_recursive(X, Y, i, j):
    if i == 0 or j == 0:
        return ""
    if X[i-1] == Y[j-1]:
        return lcs_recursive(X, Y, i-1, j-1) + X[i-1]
    else:
        a = lcs_recursive(X, Y, i-1, j)
        b = lcs_recursive(X, Y, i, j-1)
        return a if len(a) > len(b) else b

def lcs_dp(X, Y):
    m, n = len(X), len(Y)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i-1] == Y[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    # Reconstruir la LCS
    i, j = m, n
    lcs = []
    while i > 0 and j > 0:
        if X[i-1] == Y[j-1]:
            lcs.append(X[i-1])
            i -= 1; j -= 1
        elif dp[i-1][j] >= dp[i][j-1]:
            i -= 1
        else:
            j -= 1
    return ''.join(reversed(lcs))

Optimización de Espacio

Para secuencias muy largas (p.ej., m,n > 10⁶) la tabla completa puede ser prohibitiva. Observando que cada fila depende solo de la fila anterior, podemos reducir el uso de memoria a O(min(m,n)):

def lcs_space_optimized(X, Y):
    if len(Y) > len(X):
        X, Y = Y, X  # aseguramos que X es la más larga
    previous = [0] * (len(Y) + 1)
    for i in range(1, len(X) + 1):
        current = [0]
        for j in range(1, len(Y) + 1):
            if X[i-1] == Y[j-1]:
                current.append(previous[j-1] + 1)
            else:
                current.append(max(previous[j], current[-1]))
        previous = current
    # Reconstruir la LCS requiere una pasada extra o almacenar índices; aquí devolvemos solo la longitud
    return previous[-1]

Este enfoque es ideal para servicios de micro‑servicios o contenedores con memoria limitada.

Comparativa con Algoritmos Relacionados

Pruebas Unitarias y Buenas Prácticas

import unittest
class TestLCS(unittest.TestCase):
    def test_basic(self):
        self.assertEqual(lcs_dp('AGGTAB', 'GXTXAYB'), 'GTAB')
        self.assertEqual(lcs_dp('', 'ABC'), '')
        self.assertEqual(lcs_dp('ABC', ''), '')
        self.assertEqual(lcs_dp('ABC', 'ABC'), 'ABC')
    def test_space_optimized(self):
        self.assertEqual(lcs_space_optimized('AGGTAB', 'GXTXAYB'), 4)
        self.assertEqual(lcs_space_optimized('ABCDEF', 'FBDAMN'), 2)  # "BD"
if __name__ == '__main__':
    unittest.main()

Ejecuta python -m unittest nombre_del_archivo.py para validar. Mantén los tests en un directorio tests/ y usa CI/CD para asegurar que futuros cambios no rompan la lógica.

Consideraciones de Rendimiento y Escalabilidad

• Paralelismo: La tabla DP es inherentemente secuencial, pero se pueden paralelizar las diagonalas usando numpy o numba para GPUs.
• Streaming: En flujos de datos (p. ej., logs en tiempo real) se puede aplicar la variante online LCS que mantiene sólo la última fila y actualiza incrementalmente.
• Contenedores: Cuando despliegas en Docker/Podman, define --memory y --cpus adecuados; la versión optimizada ocupa ~2·min(m,n)·4bytes de RAM.
• Cache: Usa functools.lru_cache en la versión recursiva para evitar recalcular sub‑problemas cuando el dominio es pequeño.

Resolución de Problemas Comunes (Troubleshooting)

1. Resultado vacío inesperado: Verifica que los caracteres coinciden exactamente (mayúsculas/minúsculas). Usa .lower() si la comparación debe ser case‑insensitive.
2. Exceso de memoria: Cambia a la versión lcs_space_optimized o implementa la variante de Hirschberg que reduce la memoria a O(min(m,n)) y permite reconstruir la cadena.
3. Desbordamiento de tiempo en grandes textos: Considera usar algoritmos de alineamiento aproximado (p. ej., Smith‑Waterman) o limitar la longitud máxima con recortes heurísticos.
4. Incompatibilidad de tipos: Asegúrate de pasar str o listas de caracteres; si trabajas con bytes, decodifica primero.

Conclusión

El algoritmo de la Subsequencia Común Más Larga es una pieza fundamental en la comparación de secuencias y tiene aplicaciones que van desde la bioinformática hasta el control de versiones. Con Python puedes implementarlo de forma clara y, según tus restricciones de memoria y tiempo, elegir entre la versión recursiva, la tabla completa o la variante optimizada. Incorporar pruebas automatizadas, monitorizar el uso de recursos y aplicar buenas prácticas de contenedorización garantizan una solución robusta y escalable.