Diffchecker: comparando secuencias

Si alguna vez has programado alguna vez usando un repositorio, habrás usado una herramienta de diff para comparar el código antiguo y el nuevo, y detectar qué fragmentos han cambiado y qué fragmentos son comunes a ambos.

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:

  ANTES:  s c h w a r z . e n e g g e r
DESPUES:  . c h u a r c h e n e g . e r
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)

En algoritmia, este problema se conoce como LCS. El objetivo de LCS es, dadas dos secuencias, encontrar la subsecuencia 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:

def LCS(X, Y):
    if len(X) == 0 or len(Y) == 0:
        return []
    if X[-1] == Y[-1]:
        return LCS(X[:-1], Y[:-1]) + [X[-1]]
    else:
        return longest(LCS(X, Y[:-1]), LCS(X[:-1], Y))

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

def longest(X, Y):
 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.

Sé el primero en comentar

Recibir un mail

🍪 ¿Cookies?

Esta web usa cookies para identificar qué contenido es interesante y escribir más contenido similar. Puedes obtener más información aquí.