¿Dónde puedo encontrar una explicación e implementación del algoritmo diff?¿Dónde puedo encontrar el algoritmo diff?
Antes que nada, tengo que reconocer que no estoy seguro de si este es el nombre correcto del algoritmo. Por ejemplo, ¿cómo Stack Overflow marca las diferencias entre dos ediciones de la misma pregunta?
PD: Conozco los lenguajes de programación C y PHP.
Realmente no existe el "algoritmo diff". Existen muchos algoritmos de diferencias diferentes, y de hecho, los algoritmos de diferencias particulares usados se consideran en algunos casos como una ventaja comercial de la herramienta de diferencias en particular.
En general, muchos algoritmos de diferencias se basan en el problema de la subsecuencia común más larga (LCS).
El programa original Unix diff de la década de 1970 fue escrito por Doug McIllroy y utiliza lo que se conoce como el algoritmo Hunt-McIllroy. Casi 40 años después, las extensiones y los derivados de ese algoritmo todavía son muy comunes.
Hace un par de años, Bram Cohen (creador del programa de intercambio de archivos más exitoso y el sistema de control de versiones menos exitoso) creó el Patience Diff algorithm que está diseñado para brindar más resultados legibles que LCS. Originalmente se implementó en el Bazar VCS y también se agregó a Git como una opción.
Sin embargo, a menos que esté interesado en la investigación de algoritmos de diferencias, su mejor opción sería utilizar una biblioteca existente de diff como Davide Libenzi's LibXDiff, que es, por ejemplo, lo que usa Git. No me sorprendería mucho si ya hay una extensión de PHP que lo envuelva. Una buena alternativa es Google's Diff-Match-Patch library, que se usa en Bespin o WhiteRoom, por ejemplo, y está disponible para muchos idiomas. Utiliza el algoritmo Diff de Meyers más algunos procesos previos y posteriores para aceleraciones adicionales.
Un enfoque completamente diferente, si está más interesado en fusionarse que en diferir, se denomina Transformaciones operativas. La idea de OT es que, en lugar de descubrir las diferencias entre dos documentos, intente "aplicar ingeniería inversa" a las operaciones que condujeron a esas diferencias. Esto permite una fusión mucho mejor, porque luego puede "reproducir" esas operaciones. Estos son más útiles para los editores colaborativos en tiempo real como EtherPad, Google Wave o SubEthaEdit.
¿Qué ocurre con wikipedia donde dice que es Hunt-McIlroy algorithm?
Hay OCR'd paper que describe el algoritmo (explicación) y puede inspeccionar source (implementación).
Las preguntas de manera relacionada también la lista (entre otros):
'Best' Diff Algorithm
How do document diff algorithms work?
Diff Algorithm
la que todos parecen ser útiles.
El enlace de papel está muerto. – Matsemann
muchos gracias por su respuesta. Lamentablemente solo tengo un voto y esta vez me encantaría clasificarlo con más –
+1 muy agradable :) – Unreason
+1 para informar sobre la existencia de Transformaciones operativas – EoghanM