¿Puedo usar un algoritmo de diferencias de texto plano para rastrear cambios XML?

Question

Estoy trabajando en Flex/AS3 en (por simplicidad) un editor XML. Necesito proporcionar funcionalidad de deshacer/rehacer.

Por supuesto, una solución es almacenar todo el texto fuente con cada edición. Sin embargo, para conservar la memoria, me gustaría almacenar los diffs en su lugar (estos diffs también se utilizarán para transmitir actualizaciones al servidor para el guardado automático).

---

Mi pregunta es - ¿Puedo usar un algoritmo de diff texto plano para el seguimiento de estos cambios XML?

Mi investigación en Internet indica que I no puede hacerlo. Sin embargo, obviamente me falta algo. diff texto plano proporciona funcionalidad que es supuestamente:

diff(text, text') -> diffs 
patch(text, diffs) -> text' 

XML es simplemente el texto, ¿por qué no puedo simplemente usar diff() y el parche() para transformar el texto de forma fiable?

Por ejemplo: digamos que soy un poeta. Cuando escribo poesía, utilizo muchos signos de puntuación funky ... Ya sabes, como <, /, y>. (Puede ver a dónde voy con esto ...) Si estoy escribiendo mi poesía en una aplicación que usa diffs para proporcionar funcionalidad de deshacer/rehacer, ¿mi poesía se confunde cuando deshago/rehago mis ediciones? ¡Es solo texto! ¿Por qué hace una diferencia en el algoritmo?

Obviamente no consigo algo aquí ... ¡Gracias por explicarme! :)

ACTUALIZACIÓN:

Algunas discusiones que he encontrado en relación con diffing XML con un algoritmo de texto llano:

• http://code.google.com/p/google-diff-match-patch/wiki/Plaintext
• Is there a JS diff library against htmlstring just like google-diff-match-patch on plain text?

---

Además, Yo entiendo y que un patrón de Comando es probablemente una mejor forma de implementar Deshacer/Rehacer. Simplifiqué mi caso de uso por simplicidad, y todavía creo que XML diffing es el mejor enfoque.

Answer 1

yo soy el autor de la/partido de la biblioteca de texto sin formato de diferencias/parche de Google.

La pregunta clave es si sus parches son exactos. En un mundo ideal:

diff(old_text, new_text) -> edits 
    patch(edits, old_text) -> new_text 

Observe que el texto base (old_text) es el mismo en ambas operaciones. En este caso ideal, un parche y un parche simple de texto plano funcionarán perfectamente, independientemente del tipo de contenido. Si este caso se aplica a usted, entonces ha terminado.

El problema está en el parche borroso. Aquí está el ejemplo correspondiente:

diff(old_text, new_text) -> edits 
    patch(edits, old_forked_text) -> new_forked_text 

Observe que el texto base no es el mismo en ambas operaciones. Deben ser similares, pero la operación del parche ahora tiene que usar "juicio" sobre lo que debería hacer. Algunos parches pueden encajar perfectamente como se especifica en la edición, otros pueden necesitar ajustes para su posición, otros pueden necesitar ajustes para un contexto alterado, otros pueden no ajustarse en absoluto y deben descartarse. Si su algoritmo de parchado no tiene conocimiento de la estructura de XML al tomar sus decisiones, es muy posible que termine con XML mal impreso. Aquí hay un ejemplo:

old_text = Jabberwock<SPAN>Hello<SPAN>World</SPAN></SPAN> 
    new_text = Jabberwock<DIV>Hello<SPAN>World</SPAN></DIV> 
    diff(old_text, new_text) -> edits 
    edits = ["SPAN" -> "DIV" @ character 11, 
      "SPAN" -> "DIV" @ character 41] 
    old_forked_text = <SPAN>Hello<SPAN>World</SPAN></SPAN> 
    patch(edits, old_forked_text) -> new_forked_text 
    new_forked_text = <SPAN>Hello<DIV>World</SPAN></DIV> 

Miremos este con cuidado. El original diff devolvió dos ediciones, cambia el SPAN externo a un DIV. Cambio simple Lamentablemente, el texto al que se está aplicando esta edición ha cambiado desde el original. La palabra "Jabberwock" ha sido eliminada. Ahora, el primer cambio de SPAN-> DIV coincide con la segunda etiqueta de SPAN, no la primera. Como el algoritmo de parches no conoce las reglas de XML, da como resultado etiquetas anidadas ilegalmente.

Existen algunos hacks que le permiten garantizar un XML válido cuando se utiliza un parche de texto plano, pero dan como resultado cierta pérdida de flexibilidad (la pregunta original ya tiene un enlace a la página wiki que escribí sobre esto). La solución definitiva para el parcheo de XML es, por supuesto, utilizar un algoritmo de parche y diferenciado compatible con XML. Estos son significativamente más complicados y caros, pero existen. Busque los nombres de Tancred Lindholm y Sebastian Rönnau por el gran trabajo que han realizado en el campo XML (particularmente en lo que respecta a DocEng).

Avísame si hay algo más que pueda agregar.

- Neil Fraser

Answer 2

Creo que puedes usar text diff para xml especialmente en tu caso en que el ser humano escriba el xml línea por línea. No sé qué información obtuviste diciendo que no puedes hacer eso, pero supongo que esa afirmación se basó en el hecho de que los caracteres espaciales (espacio, pestaña, nueva línea ...) son algo diferentes de lo que son en un archivo de texto plano, que podría dar como resultado que dos archivos de texto diferentes sean idénticos desde una perspectiva XML. Pero, de nuevo, para un editor que se dirige a un ser humano, no veo por qué no puede hacerlo.

Answer 3

Uso Beyond Compare todo el tiempo para comparar documentos XML. Entiende XML, hasta cierto punto.

Es posible que deba preprocesar los dos documentos para que la comparación textual haga el mejor trabajo posible. Por ejemplo, en algunos documentos XML, el orden de algunos elementos puede no importar. Sin duda le importará a su herramienta diff! Es posible que deba preprocesar el XML utilizando una Transformación XML que ordena estos elementos en un orden común en ambos archivos, antes de comparar los dos archivos ordenados.

También vas a querer utilizar el mismo sangrado de ambos documentos. Encuentro útil comenzar cada elemento en una nueva línea y usar la misma cantidad de sangría, con espacios, para cada nivel. Si su documento es muy profundo, le conviene usar solo uno o dos espacios por nivel, de modo que la comparación se ajuste a la pantalla. Incluso puede querer usar un atributo por línea (y ordenar los atributos en un orden común).

Answer 4

Si usted es el único "dueño" de los datos entre el deshacer/rehacer puntos entonces por supuesto que puede usar diff texto plano para ellos. Como usted señala, equivale a un conjunto de transformaciones.

En función de las operaciones que ofrece, sin embargo, diff texto plano puede no ser remotamente cerca óptimo para deshacer la grabación/rehacer y puede ser necesario especializarse ciertos casos. Imagínese simplemente grabar un comando ReplaceAll que podría estar a solo unos pocos bytes de sobrecarga más la cadena de búsqueda y reemplazo. Eso podría generar diferencias masivas de texto claro.

En el contexto más amplio, si permite la edición externa de estos documentos, y está pensando más en cómo almacenar deltas en el servidor, está imitando a git u otros sistemas de control de versiones. Tienes que usar algún tipo de algoritmo de diferencias porque simplemente registrar tus comandos obviamente no es la única fuente de transformación. En este punto, está comenzando a mezclar deshacer/rehacer con control de versiones y es posible que desee reflexionar sobre cómo confundir esos conceptos para sus usuarios.

Me gustaría mantener deshacer/rehacer como dentro de una sesión de edición y la prohibición de edición externa, mientras que el archivo está abierto. Eso le permite optimizar su grabación de comandos para casos amplios como dije anteriormente.

Más allá de eso, o bien utilizar el control de versión convencional (considere envolver GIT) o poner en práctica su propia manera de hacer frente a los archivos que se cambian fuera de su editor.