Un programa que compara dos textos no lee ni juzga «qué ha cambiado» como lo haría una persona. Lo que busca es la forma de convertir una lista en la otra con el menor número posible de eliminaciones y adiciones. Este artículo explica cómo calcula diff esa respuesta y por qué el resultado a veces no coincide con lo que esperaríamos.
La unidad de comparación: líneas, palabras, caracteres
diff empieza dividiendo el texto en una lista de tokens. El diff tradicional y git consideran cada línea como un token. Por eso, aunque solo cambie un carácter dentro de una línea, toda la línea aparece como «1 línea eliminada + 1 línea añadida».
Comparar por líneas es rápido y encaja bien con la revisión de código, pero en documentos donde un párrafo largo ocupa una sola línea cuesta ver qué cambió. Por eso muchas herramientas comparan en dos fases:
- Comparan por líneas para encontrar las líneas cambiadas.
- Emparejan las líneas cambiadas y vuelven a comparar su interior por palabras o por caracteres.
Este sitio hace lo mismo. Como unidad dentro de la línea puedes elegir palabras, bloques (separados por espacios) o caracteres.
La subsecuencia común más larga (LCS)
El núcleo matemático de diff es la subsecuencia común más larga (Longest Common Subsequence, LCS). Una subsecuencia se obtiene eligiendo algunos elementos sin alterar su orden. Por ejemplo, la subsecuencia común más larga de ABCABBA y CBABAC tiene longitud 4; CABA y BABA son ejemplos.
Los elementos que forman parte de la LCS son «lo que se conserva»; el resto es «lo eliminado» (solo está a la izquierda) o «lo añadido» (solo está a la derecha). Cuanto más larga es la LCS, menos eliminaciones y adiciones hacen falta. Si las dos listas tienen longitudes N y M y la LCS tiene longitud L, la suma D de eliminaciones y adiciones necesarias es:
D = (N - L) + (M - L)En el ejemplo, N=7, M=6 y L=4, así que D = 3 + 2 = 5. Este D se llama distancia de edición (cuando solo se permiten inserciones y eliminaciones), y la lista de eliminaciones y adiciones se llama script de edición.
El grafo de edición y el algoritmo de Myers
Calcular la LCS de la manera clásica (programación dinámica) exige una tabla de N×M casillas. Comparar dos textos de 10.000 líneas supone 100 millones de casillas: es lento y consume mucha memoria. En 1986, Eugene W. Myers propuso un método más rápido en el artículo «An O(ND) Difference Algorithm and Its Variations», que es la base del algoritmo por defecto de GNU diff y de git.
Myers convierte la comparación en la búsqueda del camino más corto en una cuadrícula:
- Se va desde la esquina superior izquierda (0,0) hasta la inferior derecha (N,M).
- Un paso a la derecha = eliminar un elemento del texto izquierdo; un paso hacia abajo = añadir un elemento del texto derecho. Cada uno cuesta 1.
- Donde los dos elementos coinciden se puede avanzar en diagonal gratis. Un tramo continuo de diagonales se llama snake («serpiente»).
El camino de menor coste es el script de edición más corto. El algoritmo de Myers va ampliando por turnos «el punto más lejano alcanzable con coste 0», «el más lejano con coste 1»… y se detiene al llegar al final. En cada paso basta con recordar la posición más avanzada de cada diagonal, así que el tiempo es aproximadamente proporcional a (N+M)×D. Si los dos textos son casi iguales, D es pequeño y el cálculo es muy rápido; si son completamente distintos, se vuelve lento.
Memoria lineal y middle snake
Para reconstruir el camino hay que guardar un registro en cada paso, y la memoria puede crecer en proporción a D². En el mismo artículo, Myers presentó una variante que avanza a la vez una búsqueda hacia delante desde el inicio y otra hacia atrás desde el final, hasta encontrar el tramo diagonal donde se cruzan (la middle snake). Dividiendo el problema en dos subproblemas más pequeños a partir de ese punto y repitiendo el proceso, la memoria usada es solo proporcional al tamaño de la entrada.
Cuando sale demasiado caro: heurísticas aproximadas
Si las dos entradas tienen decenas de miles de líneas y difieren mucho, D también crece y (N+M)×D puede llegar a miles de millones. Para esos casos, GNU diff incluye una heurística: si la búsqueda supera cierto límite de pasos, corta el problema en la diagonal que más ha avanzado hasta ese momento. El resultado sigue siendo un script de edición correcto, pero no está garantizado que sea el más corto. La opción --minimal de GNU diff o la --minimal de git obligan a buscar el resultado mínimo aunque tarde más.
Lo mínimo no siempre es lo más legible
Puede haber varios caminos con la misma distancia de edición. Por ejemplo, al añadir una función a un código hay llaves de cierre } y líneas en blanco en muchos sitios, y el algoritmo puede emparejar «la } de la función nueva» con «la } de una función existente». El resultado es mínimo, pero a una persona le resulta extraño. Por eso git usa por defecto una heurística que desplaza los límites fijándose en la sangría, y ofrece otros algoritmos como patience o histogram. La comparación detallada está en Comparación de algoritmos diff.
En esta herramienta
El motor de comparación de este sitio implementa en JavaScript la variante de memoria lineal del algoritmo de Myers y, si la entrada es grande, pasa a una división aproximada al estilo de GNU diff. El cálculo se ejecuta en un Web Worker, así que la pantalla no se bloquea con archivos grandes. Una vez obtenido el resultado por líneas, empareja las líneas cambiadas de contenido parecido, las marca como «modificadas» y vuelve a comparar su interior con la unidad elegida (palabras, bloques o caracteres) para resaltarlo.
Introduce dos textos en el comparador de textos y cambia la unidad de comparación dentro de la línea para ver cómo varía el resultado. Para leer el resultado en formato git, consulta Cómo leer un diff unificado.