Subsecuencia común más larga (LCS)
Cuando comparas dos versiones de un archivo, las líneas que no cambiaron forman una subsecuencia común de ambas. Encontrar la más larga te dice exactamente qué se añadió y qué se eliminó. La misma idea alinea cadenas de ADN y sugiere correcciones ortográficas, y se resuelve con una de las tablas más elegantes de la informática.
El problema
Una subsecuencia de una palabra conserva algunas de sus letras en su orden original: ACE es una subsecuencia de ABCDE, pero EA no. Una subsecuencia común de dos palabras es una subsecuencia de ambas, y el problema consiste en encontrar la más larga. Una palabra de longitud n tiene 2ⁿ subsecuencias, así que probarlas todas es imposible en cuanto hay más de unas pocas letras.
La tabla
Sea len[i][j] la longitud de la subsecuencia común más larga de las primeras i letras de una palabra y las primeras j letras de la otra. Una palabra vacía no comparte nada, así que la primera fila y la primera columna valen 0. Si la letra i es igual a la letra j, len[i][j] = len[i − 1][j − 1] + 1: la coincidencia alarga lo que venía antes. Si no, len[i][j] es el mayor entre len[i − 1][j] y len[i][j − 1]: se descarta una de las dos letras y se conserva el mejor resultado.
Un ejemplo
Compara ABCBDAB con BDCABA. La primera letra de la segunda palabra, B, coincide con la B de la fila 2; la C de la tercera columna coincide con la fila 3, y así sucesivamente, y cada coincidencia suma uno a la celda de arriba a la izquierda. La celda de abajo a la derecha termina en 4. Leyendo de vuelta desde ahí sale BCBA, pero BCAB y BDAB son igual de largas: una subsecuencia común más larga no tiene por qué ser única.
Leer la respuesta de vuelta
Empieza en la celda de abajo a la derecha. Si las letras de su fila y su columna coinciden, esa letra forma parte de la respuesta: anótala y avanza en diagonal hacia arriba a la izquierda. Si no, pasa a la vecina, arriba o a la izquierda, con el valor mayor, porque de ahí sacó la celda su valor. Para en la primera fila o columna. Las letras anotadas, en orden inverso, son la subsecuencia.
Historia y usos
El método de la tabla lo descubrieron de forma independiente varias personas hacia 1970, entre ellas Robert Wagner y Michael Fischer, cuyo artículo de 1974 resolvió el problema, muy relacionado, de la distancia de edición. En 1975 Dan Hirschberg mostró cómo encontrar la subsecuencia con mucha menos memoria, y en 1976 James Hunt y Douglas McIlroy basaron el programa Unix diff en las subsecuencias comunes más largas de líneas. Los biólogos usan la misma idea, con puntuaciones, para alinear secuencias de ADN y de proteínas.
Explóralo
Abre la aplicación y pulsa Paso. Las dos letras que se comparan se iluminan en los encabezados; una coincidencia lee la celda azul de arriba a la izquierda, y una diferencia lee las dos celdas azules de arriba y de la izquierda. Cuando la tabla está llena, el camino naranja sube desde la esquina y las letras de la respuesta aparecen debajo de la tabla.
Preguntas frecuentes
¿Cuánto tiempo y memoria necesita el algoritmo LCS?
Tiempo O(m·n) para palabras de longitudes m y n. La tabla completa también necesita memoria O(m·n) para leer la respuesta de vuelta; en 1975 Dan Hirschberg mostró cómo encontrar la propia subsecuencia con solo O(min(m, n)) de memoria.
¿Cómo usa diff la subsecuencia común más larga?
Trata cada línea de un archivo como un símbolo y encuentra una subsecuencia común más larga de las líneas de los dos archivos. Las líneas de esa subsecuencia no han cambiado; las demás líneas del archivo antiguo se borraron, y las demás líneas del archivo nuevo se añadieron.
¿Y con tres palabras o más?
La tabla tiene una dimensión por palabra, así que tres palabras de longitud n necesitan n³ celdas. Para un número arbitrario de palabras, el problema es NP-difícil.
¿Qué relación hay entre la LCS y la distancia de edición?
Si solo se permiten inserciones y borrados, la distancia de edición de dos palabras es su longitud total menos el doble de la longitud de su subsecuencia común más larga. Si además se permiten sustituciones, se obtiene la distancia de Levenshtein, que se calcula con una tabla muy parecida.
¿Listo para probarlo?
Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.
Prueba la subsecuencia común más larga