Algoritmos de diff de texto: Myers, Patience e Histograma

Qué significa “diff” en realidad

Un diff es una lista de cambios de una versión de un archivo a otra. Le das viejo y nuevo, te da la lista más corta de ediciones que convierte uno en el otro.

El algoritmo importa porque hay muchas listas válidas de ediciones, y la que un humano encuentra legible no siempre es la que un ordenador encuentra más corta. Git, GitHub, tu IDE, tu herramienta de code review, todos ejecutan un algoritmo de diff cada vez que cambias un archivo. La elección del algoritmo da forma a cómo se ve la revisión.

Myers: el default que usa Git

El algoritmo Myers ha sido el default en Git, en diff de cualquier Unix, y en la mayoría de herramientas de code review desde 1986. Encuentra la lista más corta de ediciones tratando el archivo como una secuencia de líneas y caminando una rejilla que compara cada línea vieja con cada línea nueva.

Myers es rápido en archivos típicos (menos de 10.000 líneas). Produce diffs correctos y óptimos en el sentido de “menos cambios contados por línea”.

El truco: óptimo por conteo de líneas no siempre es legible. Myers puede emparejar líneas pequeñas idénticas (como líneas en blanco o }) entre funciones muy distintas, haciendo que el diff parezca que moviste código que en realidad reescribiste en su sitio. El famoso “bloque equivocado de llaves de cierre”.

Cuando quieras inspeccionar un diff a mano sin una herramienta, pega las dos versiones en el comparador de textos de AldeaCode. Corre el diff en tu navegador y enseña el resultado lado a lado, sin subida.

Patience diff: el primo legible

Patience diff lo diseñó Bram Cohen (el autor de BitTorrent) específicamente para arreglar el problema de la “llave equivocada” de Myers.

El algoritmo solo empareja primero las líneas que aparecen exactamente una vez en ambos archivos, y luego diff recursivamente los trozos entre esas coincidencias. El efecto es que las líneas que claramente son el mismo contexto (nombres de función, comentarios únicos, cadenas distintas) anclan el diff, y el emparejamiento de líneas genéricas a su alrededor queda restringido.

Patience produce diffs que se parecen más a lo que dibujaría un humano. El precio es un runtime ligeramente más lento y diffs ligeramente más grandes en casos patológicos.

Git soporta patience diff con git diff --patience o poniendo diff.algorithm = patience en la config. Muchos equipos lo activan globalmente y no vuelven atrás.

Histograma: el default moderno

El histograma es un refinamiento de patience que elige las líneas raras como anclas de forma más agresiva. Es el default en JGit (Eclipse) y una opción en Git a través de --histogram o diff.algorithm = histogram.

Para la mayoría de código, histograma y patience producen resultados similares. Para algunos archivos patológicos (cambios grandes con muchas líneas pequeñas repetidas), histograma produce diffs notablemente mejores.

Recomendación moderna: activa histograma en tu config global de Git. El runtime es un par de por ciento más lento que Myers en archivos típicos, el resultado es más legible, y casi nunca hace que las cosas vayan peor.

Hunt-Szymanski: el ancestro

Hunt-Szymanski es de 1977, diez años antes que Myers. Es el algoritmo que movía el diff original de Unix en los 70. La mayoría de sistemas modernos lo abandonaron porque no maneja el peor caso con la elegancia de Myers.

Vale la pena conocerlo porque la documentación vieja todavía lo cita, y porque algunas herramientas especializadas (alineamiento de genoma, detección de plagio) siguen usando derivados.

Los modos de fallo reales

Algunos casos donde cualquier algoritmo de diff produce algo confuso:

Cambios solo de espacios. Un reformato (tabs a espacios, finales de línea, espacios al final) hace que cada línea aparezca “cambiada” aunque el significado no. El arreglo es git diff -w para ignorar espacios, o ejecutar un formatter y commitear el formato aparte de la lógica.

Bloques renombrados. Si cortas una función de un sitio y la pegas idéntica en otro, el diff por líneas ve un borrado en un sitio y un insert en otro. git diff -M detecta renombrados a nivel de archivo pero no de bloques dentro de un archivo.

Líneas reordenadas. Intercambiar dos líneas adyacentes son dos cambios (borrar, insertar) en diff por líneas. Diff por palabras o por caracteres lo maneja mejor, pero a un coste mucho más alto.

Archivos de una sola línea larga. JavaScript minificado o config comprimida hacen que el archivo entero parezca una línea grande. Los algoritmos de diff sufren. El arreglo pragmático es formatear el archivo antes de diffearlo.

Eligiendo el algoritmo

Para el 99 por ciento del código en 2026:

• Pon diff.algorithm = histogram en tu config de Git y olvídate.
• Usa -w cuando tengas ruido de espacios.
• Usa -M cuando sospeches renombrados.

Para casos especializados:

• Patience cuando histograma no esté disponible (algunas versiones viejas de Git).
• Diff a nivel de palabra para prosa, posts de blog, documentación.
• Diff a nivel de carácter para cadenas muy cortas donde cada carácter cuenta.

Cuando quieras inspeccionar un diff fuera de Git, el comparador de textos, el formateador JSON para canonicalizar ambos lados, y el buscar y reemplazar para normalizar, todos corren en tu navegador. El algoritmo de diff es una de esas piezas de tu tooling que silenciosamente da forma a cómo experimentas cada code review. Elegir un default sensato una vez te ahorra una pequeña dosis de confusión cada día.