¿Cómo detectan las aplicaciones como DiffMerge las diferencias en los archivos de texto, y cómo determinan cuándo una línea es nueva, y no solo en una línea diferente a la del archivo que se verifica?¿Cómo funcionan las aplicaciones de diferenciación de texto?
¿Es esto algo bastante fácil de implementar? ¿Ya hay bibliotecas para hacer esto?
Aquí está the paper que sirvió de base para la herramienta de línea de comandos de UNIX diff.
En realidad es bastante simple; Los programas DIFF, la mayoría de las veces, se basan en el Longest Common Sequence, que se puede resolver utilizando un algoritmo de gráfico.
This web page ofrece implementaciones de ejemplo en C#.
Esa es una pregunta compleja. Realizar una diferencia significa encontrar la distancia de edición mínima entre los dos archivos. Es decir, la cantidad mínima de cambios que debe realizar para transformar un archivo en el otro. Esto es equivalente a encontrar la subsecuencia común más larga de líneas entre los dos archivos, y esta es la base de los diversos programas de diferencias. El problema de subsecuencia común más largo es bien conocido, y debería ser capaz de encontrar la solución de programación dinámica en google.
El problema con el enfoque de programación dinámica es que es O (n^2). Por lo tanto, es muy lento en archivos grandes e inutilizable para cadenas binarias grandes. La parte más difícil al escribir un programa de diferencias es optimizar el algoritmo para su dominio problemático, de modo que obtenga un rendimiento razonable (y resultados razonables). El documento "Un algoritmo para la comparación de archivos diferenciales" de Hunt y McIlroy ofrece una buena descripción de una versión temprana de la utilidad de diferencias de Unix.
Hay bibliotecas. Aquí hay uno: http://code.google.com/p/google-diff-match-patch/
StackOverflow utiliza Beyond Compare para su diferencia. Creo que funciona llamando a Beyond Compare desde la línea de comandos.
Los archivos que voy a diferenciar son muy pequeños, de 10 a 50 líneas, por lo que la velocidad del algoritmo no es un problema. – scottm
Y Kristo ya mencionó un documento que lo reduce a O (ND). – beef2k