Algoritmo para el sistema de control de fuente?

Question

Necesito escribir un sistema de control de fuente simple y preguntarme qué algoritmo utilizaría para las diferencias de archivos?

No quiero ver el código fuente existente debido a problemas de licencia. Necesito tener una licencia bajo MPL, así que no puedo mirar ninguno de los sistemas existentes como CVS o Mercurial ya que todos tienen licencia GPL.

Solo para dar algunos antecedentes, solo necesito algunas funciones realmente simples: archivos binarios en una carpeta. no hay subcarpetas y cada archivo se comporta como si fuera su propio repositorio. Sin metadatos excepto por algunos permisos.

En general cosas realmente simples, mi única preocupación es cómo almacenar solo las diferencias de un archivo de una revisión a otra sin perder demasiado espacio pero sin ser demasiado ineficiente (Tal vez almacenar una versión completa cada X cambia, un poco al igual que los fotogramas clave en los videos?)

Answer 1

Los algoritmos de subsecuencia más comunes son el principal mecanismo utilizado por las herramientas similares a las diferencias, y se pueden aprovechar mediante un sistema de control de código fuente.

"Reverse Deltas" son un enfoque común para el almacenamiento, ya que principalmente necesita retroceder en el tiempo desde la revisión más reciente.

Answer 2

En realidad estaba pensando en algo similar a esto el otro día ... (raro, ¿eh?)

no tengo una gran respuesta para usted, pero yo he venido a la conclusión de que si yo fuera para escribir una herramienta de diferencia de archivos, que lo haría con un algoritmo (para encontrar diffs) que funciona de alguna manera como funcionan los REGEXes con su codicia.

En cuanto al almacenamiento de archivos DIFF ... Si yo fuera usted, en lugar de almacenar archivos DIFF orientados hacia adelante (es decir, comienza con el archivo original y luego la computadora muestra 150 diffs cuando trabaja con la versión 151), utilice DIFF para su historial pero tiene su último archivo almacenado como una versión completa. Si lo haces de esta manera, cada vez que trabajes con el último archivo (que probablemente sea el 99% del tiempo), obtendrás el mejor rendimiento.

Answer 3

¿Qué tal si miramos el código fuente de Subversion? su licencia bajo licencia Apache 2.0

Answer 4

Aunque fósil es GPL, el algoritmo delta se basa en rsync y describió here

Answer 5

Patience Diff es un buen algoritmo para encontrar los deltas entre dos archivos que son propensos a tener sentido para la gente. Esto a menudo da mejores resultados que el ingenuo algoritmo de "subsecuencia común más larga", pero los resultados son subjetivos.

Dicho esto, muchos sistemas de control de versiones modernos almacenan archivos completos en cada etapa y calculan las diferencias reales más adelante, solo cuando es necesario. Para archivos binarios (que probablemente no son terriblemente comprimibles), es posible que el almacenamiento de deltas inversos sea finalmente más eficiente.

Answer 6

Gene Myers ha escrito un buen documento An O(ND) Difference Algorithm and its Variations. Cuando se trata de comparar secuencias, Myers es el hombre. Probablemente también deberías leer el artículo de Walter Tichy sobre RCS; explica cómo almacenar un conjunto de archivos almacenando la versión más reciente más las diferencias.

Answer 7

La idea de almacenar deltas (hacia adelante o hacia atrás) es clásica con respecto al control de versiones. El problema siempre ha sido, "¿qué delta almacena?"

Muchos sistemas de control de fuente almacenan deltas calculados esencialmente por" diff ", por ejemplo, complemento orientado a línea de las subsecuencias comunes más largas. Pero puede calcular deltas para tipos específicos de documentos de una manera específica a esos documentos , para obtener deltas más pequeños (ya menudo más comprensibles)

Para obtener el código fuente de los lenguajes de programación, se pueden calcular las distancias de Levenshtein sobre las estructuras del programa. Se puede encontrar un conjunto de herramientas para hacer esto. Smart Differencer

Si está almacenando archivos que no son de texto, es posible que pueda aprovechar su estructura para calcular s deltas maller

Por supuesto, si lo que desea es una implementación mínima, entonces simplemente almacenar la imagen completa de cada versión de archivo es fácil. Los discos de Terabyte hacen que esa solución sea viable si no es bonita. (El sistema de archivos PDP10 solía hacer esto implícitamente).