Las diferencias son parte del problema de subsecuencia común más largo (http://en.wikipedia.org/wiki/Lon…). Este es un problema difícil de NP que básicamente trata de encontrar secuencias continuas en datos arbitrarios, es decir, muchos archivos fuente / secuencia de disparos de ADN.
Sin embargo, diffs solo opera en 2 secuencias, lo que reduce la complejidad de la búsqueda a O (m * n), siendo m / n la longitud de los archivos (gracias a Peter Scott).
Estoy bastante seguro de que vimdiff usa la herramienta de diferencias estándar (http://en.wikipedia.org/wiki/Dif…) para atacar este problema:
- ¿Cuál es un ejemplo de un bucle infinito?
- ¿Qué debo aprender a continuación para mejorar mi última capa?
- ¿Cuáles son los algoritmos criptográficos básicos que un programador debe saber?
- ¿Algún consejo para estudiar la complejidad del espacio para programar entrevistas? ¿Cuáles son algunos buenos recursos para aprender sobre la complejidad del espacio?
- ¿Qué algoritmos de máquina requieren escala / normalización de datos?
Esto solo funciona cuando un comando estándar “diff” está disponible. Ver ‘diffexpr’.
Fuente: http://vimdoc.sourceforge.net/ht…
En sistemas basados en Unix, Vim debería funcionar sin problemas porque debería haber un programa de diferencias “estándar” disponible
Fuente: http://vim.wikia.com/wiki/Runnin…
Diff utiliza principalmente el algoritmo descrito en el documento, Algoritmo de diferencia An O (ND) y sus variaciones (http://www.xmailserver.org/diff2…), que se encuentra en http://stackoverflow.com/questio….
Se incluyen otras referencias en el código fuente que se encuentra aquí http://ftp.gnu.org/gnu/diffutils/:
El algoritmo básico se describe en “Un algoritmo de diferencia O (ND) y sus variaciones”, Eugene W. Myers, ‘Algorithmica’ Vol. 1 No. 2, 1986, págs. 251-266; y en “Un programa de comparación de archivos”, Webb Miller y Eugene W. Myers, “Software – Practice and Experience” vol. 15 No. 11, 1985, págs. 1025-1040. El algoritmo se descubrió independientemente como se describe en “Algoritmos para la coincidencia aproximada de cadenas”, E. Ukkonen, “Información y control” vol. 64, 1985, págs. 100-118.
El código para varios idiomas se puede encontrar en http://code.google.com/p/google-…
Más discusión aquí: http://c2.com/cgi/wiki?DiffAlgor…
