algorithm diff

algorithm - ¿Hay algún algoritmo similar a un diff que maneje un bloque móvil de líneas?



(7)

Aquí hay un boceto de algo que puede funcionar. Ignore las insertaciones / eliminaciones de diferencias por el momento en aras de la claridad.

Esto parece consistir en descubrir el mejor bloqueo, similar a la compresión de texto. Queremos encontrar la subcadena común de dos archivos. Una opción es crear un árbol de sufijo generalizado e iterativamente tomar la subcadena común máxima, eliminarla y repetir hasta que no haya una subcadena de un tamaño $ s $. Esto se puede hacer con un árbol de sufijos en O (N ^ 2) hora ( https://en.wikipedia.org/wiki/Longest_common_substring_problem#Suffix_tree ). El tomar con valentía el máximo parece ser óptimo (como una función de los caracteres comprimidos) ya que tomar una secuencia de caracteres de otra subcadena significa agregar el mismo número de caracteres en otro lugar.

Cada subcadena sería reemplazada por un símbolo para ese bloque y se mostraría una vez como una especie de ''diccionario''.

$ diff a.txt b.txt 1,3d0 < $ 6a4,6 > $ $ = 1,2,3

Ahora tenemos que reintroducir el comportamiento de tipo diff. La respuesta simple (posiblemente no óptima) es simplemente ejecutar primero el algoritmo diff, omitir todo el texto que no se generará en el original diff y ejecutar el algoritmo anterior.

El programa diff , en sus diversas encarnaciones, es razonablemente bueno para calcular la diferencia entre dos archivos de texto y expresarlo de forma más compacta que mostrando ambos archivos en su totalidad. Muestra la diferencia como una secuencia de fragmentos insertados y eliminados de líneas (o líneas modificadas en algunos casos, pero eso es equivalente a una eliminación seguida de una inserción). Los sistemas de control de fuente y patch utilizan el mismo o muy similar programa o algoritmo para minimizar el almacenamiento requerido para representar las diferencias entre dos versiones del mismo archivo. El algoritmo se discute here y here .

Pero se cae cuando se mueven bloques de texto dentro del archivo.

Supongamos que tiene los siguientes dos archivos, a.txt y b.txt (imagine que ambos tienen cientos de líneas de longitud en lugar de solo 6):

a.txt b.txt ----- ----- 1 4 2 5 3 6 4 1 5 2 6 3

diff a.txt b.txt muestra esto:

$ diff a.txt b.txt 1,3d0 < 1 < 2 < 3 6a4,6 > 1 > 2 > 3

El cambio de a.txt a b.txt se puede expresar como "Tome las primeras tres líneas y a.txt al final", pero diff muestra el contenido completo del fragmento movido de líneas dos veces, perdiendo la oportunidad de describir este gran cambio muy corto.

Tenga en cuenta que diff -e muestra el bloque de texto solo una vez, pero eso se debe a que no muestra el contenido de las líneas eliminadas.

¿Hay una variante del algoritmo diff que (a) conserva la capacidad de diff para representar inserciones y eliminaciones, y (b) representa bloques de texto movidos de manera eficiente sin tener que mostrar todos sus contenidos?

Como solicitó un algoritmo y no una aplicación, eche un vistazo a "El problema de corrección String-to-String con movimientos de bloque" de Walter Tichy. Hay otros, pero ese es el original, por lo que puede buscar documentos que lo citen para encontrar más.

El documento cita el artículo de Paul Heckel "Una técnica para aislar las diferencias entre los archivos" (mencionado en esta respuesta a esta pregunta) y menciona esto sobre su algoritmo:

Heckel [3] señaló problemas similares con las técnicas LCS y propuso un algoritmo de cal lineal para detectar movimientos de bloque. El algoritmo funciona adecuadamente si hay pocos símbolos duplicados en las cadenas. Sin embargo, el algoritmo da resultados pobres de lo contrario. Por ejemplo, dadas las dos cadenas aabb y bbaa , el algoritmo de Heckel no puede descubrir ninguna subcadena común.

El siguiente método es capaz de detectar movimientos de bloque:

Paul Heckel: una técnica para aislar las diferencias entre archivos
Comunicaciones del ACM 21 (4): 264 (1978)
http://doi.acm.org/10.1145/359460.359467 (acceso restringido)
Mirror: http://documents.scribd.com/docs/10ro9oowpo1h81pgh1as.pdf (acceso abierto)

wikEd diff es una biblioteca gratuita de JavaScript que implementa este algoritmo y lo mejora. También incluye el código para compilar una salida de texto con inserciones, eliminaciones, bloques movidos y posiciones de bloques originales insertadas en la nueva versión de texto. Consulte la página del proyecto o el código extensamente comentado para obtener más información. Para las pruebas, también puede usar la demostración en línea .

Git 2.16 (Q1 2018) introducirá otra posibilidad, ignorando algunas líneas movidas especificadas.

" git diff " aprendió una variante del algoritmo " --patience ", a la cual el usuario puede especificar qué línea ''única'' usar como puntos de anclaje.

Ver commit 2477ab2 (27 Nov 2017) por Jonathan Tan ( jhowtan ) .
(Fusionada por Junio ​​C Hamano - gitster - in commit d7c6c23 , 19 de diciembre de 2017)

diff : línea (s) de anclaje de soporte

Enseñe a diff un nuevo algoritmo, uno que intenta evitar que las líneas especificadas por el usuario aparezcan como una eliminación o adición en el resultado final.
El usuario final puede usar esto especificando " --anchored=<text> " una o más veces al usar comandos de Git como " diff " y " show ".

La documentación para git diff ahora dice:

--anchored=<text>:

Genera un diff usando el algoritmo "diff anclado".

Esta opción se puede especificar más de una vez.

Si existe una línea tanto en el origen como en el destino, existe solo una vez y comienza con este texto, este algoritmo intenta evitar que aparezca como una eliminación o adición en la salida.
Utiliza el algoritmo "paciencia diff" internamente.

Vea las pruebas para algunos ejemplos :

pre post a c b a c b

normalmente, c se mueve para producir la diferencia más pequeña.
Pero:

git diff --no-index --anchored=c pre post

Diff sería a .

Nuestras herramientas Smart Differencer hacen exactamente esto cuando se calculan las diferencias entre los textos fuente de dos programas en el mismo lenguaje de programación. Las diferencias se informan en términos de estructuras de programa (identificadores, expresiones, instrucciones, bloques) precisas para el número de línea / columna, y en términos de operaciones de edición plausibles (borrar, insertar, mover, copiar [arriba y más allá de la solicitud de OP de mera "copia"] ], rename-identifier-in-block).

Los SmartDifferencers requieren un artefacto estructurado (por ejemplo, un lenguaje de programación), por lo que no puede hacer esto para texto arbitrario. (Podríamos definir la estructura como "solo líneas de texto", pero no creemos que sea particularmente valiosa en comparación con la diferencia estándar).

Para esta situación en mi codificación de la vida real, cuando realmente muevo todo un bloque de código a otra posición en la fuente, porque tiene más sentido ya sea lógicamente o por legibilidad, lo que hago es esto:

  • limpiar todos los diffs existentes y comprometerlos
    • para que el archivo solo requiera el movimiento que estamos buscando
  • eliminar todo el bloque de código de la fuente
    • guarda el archivo
    • y escenifica ese cambio
  • agregue el código en la nueva posición
    • guarda el archivo
    • y escenifica ese cambio
  • cometer los dos parches escalonados como uno comprometerse con un mensaje razonable

SemanticMerge , la herramienta "semántica scm" mencionada en este comentario para una de las otras respuestas, incluye una "diferencia semántica" que maneja mover un bloque de líneas (para lenguajes de programación compatibles). No he encontrado ningún detalle sobre el algoritmo pero es posible que el algoritmo diff en sí mismo no sea particularmente interesante ya que depende del resultado de un análisis separado de los archivos de código fuente del lenguaje de programación. Aquí está la documentación de SemanticMerge sobre la implementación de un analizador de lenguaje (externo), que puede arrojar algo de luz sobre cómo funcionan sus diferencias:

Lo probé hace un momento y su diferencia es fantástica . Es significativamente mejor que la que produje utilizando la demostración del algoritmo mencionado en esta respuesta (y esa diferencia en sí misma fue mucho mejor que la que fue producida por el algoritmo de diferencia predeterminada de Git) y sospecho que es mejor que una que pueda ser producida por el algoritmo mencionado en esta respuesta .