Diffchecker: comparando secuencias

Seguramente, si has programado alguna vez usando un repositorio, hayas visto cómo al subir código, existe una herramienta llamada diff, capaz de comparar el código antiguo y el nuevo, y detectar los fragmentos que han cambiado, y aquellos que ambos tienen en común.

Ejemplo de diff checking

Este algoritmo parece sencillo hasta que nos paramos a pensar en su funcionamiento un rato. Por ejemplo, si queremos comparar las palabras schwarzenegger y chuarcheneger, obtenemos el siguiente resultado:

1   ANTES:  s c h w a r z . e n e g g e r
2 DESPUES:  . c h u a r c h e n e g . e r
3 CAMBIOS:  - = = / = = / + = = = = - = =

En el cambio hemos eliminado 2 letras, modificado 2 letras y añadido una letra. Este análisis, que no es tan simple de realizar con nuestra inteligencia natural, tampoco tiene una solución algorítmica trivial.

Subsecuencia común más larga (LCS)

Este es el nombre de este problema en algoritmia, donde se formula como: dadas dos secuencias, encontrar la secuencia más larga que ambas tienen en común.

Como las herramientas de diff sólo comparan entre sí dos cadenas, existe una solución mediante un algoritmo divide y vencerás, que va reduciendo el problema a otros problemas más pequeños. Así, se puede definir el problema de la siguiente forma:

1 def LCS(X, Y):
2     if len(X) == 0 or len(Y) == 0:
3         return []
4     if X[-1] == Y[-1]:
5         return LCS(X[:-1], Y[:-1]) + [X[-1]]
6     else:
7         return longest(LCS(X, Y[:-1]), LCS(X[:-1], Y))

Donde longest es una función que sencillamente devuelve la cadena más larga:

1 def longest(X, Y):
2 	return X if len(X) > len(Y) else Y

Teniendo el algoritmo LCS (que podéis probar en Python), es fácil averiguar qué se ha añadido, eliminado, o modificado al comparar dos cadenas. Sin embargo, es un algoritmo muy lento. Basta con que pongamos dos cadenas algo más largas (como arn. schwarzenegger y ar. chuarcheneger) para que el tiempo de ejecución se dispare.

Por eso es necesario el uso de una memoria que almacene los resultados, a fin de no tener que computarlos más de una vez. Haz la prueba:

Esta es la base de este algoritmo, aunque hay que detallar ciertos matices para que funcione correctamente; convertir el algoritmo recursivo en uno iterativo para evitar exceder el límite de recursión, utilizar estructuras de datos que permitan un cálculo más eficiente, o tokenizar las secuencias para considerar que cada elemento puede ser una fila de código o una palabra en lugar de un caracter.

Y para rizar el rizo, aquí tenéis el resultado de una herramienta de diffcheck, comparando nuestro algoritmo antes y después de usar memoria.

Sé el primero en comentar!