Posso usare un algoritmo diff in chiaro per il tracciamento delle modifiche XML?

Question

Sto lavorando in Flex/AS3 su (per semplicità) un editor XML. Devo fornire funzionalità di annullamento/ripristino.

Ovviamente, una soluzione consiste nel memorizzare l'intero testo di origine con ogni modifica. Tuttavia, per risparmiare memoria, vorrei invece memorizzare i diff (questi diff saranno anche usati per trasmettere aggiornamenti al server per il salvataggio automatico).

---

La mia domanda è - posso usare un algoritmo diff testo in chiaro per il monitoraggio di questi cambiamenti XML?

La mia ricerca su Internet indica che I non può fare così. Tuttavia, mi manca ovviamente qualcosa. diff Plaintext fornisce funzionalità che è presumibilmente:

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

XML è semplicemente il testo, quindi perché non posso semplicemente usare diff() e la patch() per trasformare il testo in modo affidabile?

Ad esempio: Diciamo che sono un poeta. Quando scrivo poesie, uso molta punteggiatura funky ... Sai, come <, /, e>. (Potresti vedere dove sto andando con questo ...) Se sto scrivendo la mia poesia in un'applicazione che utilizza diffs per fornire funzionalità di annullamento/ripetizione, la mia poesia diventa confusa quando annullo/ripristino le mie modifiche? È solo testo! Perché fa la differenza nell'algoritmo?

Ovviamente non capisco qualcosa qui ... Grazie per aver spiegato! :)

UPDATE:

Alcune discussioni che ho incontrato per quanto riguarda diffing XML con un algoritmo di testo in chiaro:

• 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?

---

Inoltre, Io capisco e che un pattern Command è probabilmente un modo migliore per implementare Undo/Redo. Ho semplificato il mio caso d'uso per semplicità, e continuo a pensare che la diffusione di XML sia l'approccio migliore.

Answer 1

Sono l'autore del/partita libreria di testo semplice diff/patch da parte di Google.

La domanda chiave è se le patch sono esatte. In un mondo ideale:

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

Si noti che il testo di base (old_text) è lo stesso in entrambe le operazioni. In questo caso ideale, un semplice testo e patch in chiaro funzionerà perfettamente, indipendentemente dal tipo di contenuto. Se questo caso si applica a te, allora hai finito.

Il problema risiede con la patch sfocata. Ecco l'esempio corrispondente:

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

Si noti che il testo di base non è lo stesso in entrambe le operazioni. Dovrebbero essere simili, ma l'operazione di patch ora deve usare il "giudizio" su cosa dovrebbe fare. Alcune patch possono adattarsi perfettamente come specificato nella modifica, altre potrebbero dover essere ottimizzate per la posizione, altre potrebbero dover essere ottimizzate per il contesto alterato, altre potrebbero non adattarsi affatto e dovrebbero essere eliminate. Se il tuo algoritmo di patching non è a conoscenza della struttura di XML quando prendi le sue decisioni, potresti finire con l'XML malfromed. Ecco un esempio:

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> 

Diamo un'occhiata a questo attentamente. Il differenziale originale ha restituito due modifiche, modifica lo SPAN più esterno in un DIV. Cambio semplice Sfortunatamente il testo a cui questa modifica viene applicata è stato modificato rispetto all'originale. La parola "Jabberwock" è stata rimossa. Ora la prima modifica SPAN-> DIV corrisponde al secondo tag SPAN, non al primo. Poiché l'algoritmo di patch non è a conoscenza delle regole di XML, risulta in tag nidificati illegalmente.

Esistono alcuni hack che consentono di garantire un XML valido quando si utilizza una patch di testo normale, ma comportano una perdita di flessibilità (la domanda originale ha già un collegamento alla pagina wiki che ho scritto a riguardo). La soluzione definitiva per il patching di XML è ovviamente quella di utilizzare un algoritmo diff e patch XML-aware. Questi sono significativamente più complicati e costosi, ma esistono. Google i nomi Tancred Lindholm e Sebastian Rönnau per il grande lavoro che hanno fatto nel campo XML (in particolare per quanto riguarda DocEng).

Fatemi sapere se c'è qualcos'altro che posso aggiungere.

- Neil Fraser

Answer 2

Penso che si possa usare text diff per xml specialmente nel tuo caso in cui l'essere umano scriverà l'xml riga per riga. Non so quali informazioni hai detto che non puoi farlo, ma suppongo che questa affermazione fosse basata sul fatto che i caratteri spaziali (spazio, tab, newline ...) sono in qualche modo diversi da essere in un semplice file di testo, che potrebbe causare due file di testo diversi sono identici da una prospettiva XML. Ma ancora, per un editore che si rivolge all'essere umano, non vedo perché non puoi.

Answer 3

Io uso Beyond Compare tutto il tempo per confrontare documenti XML. Comprende l'XML, in una certa misura.

Potrebbe essere necessario pre-elaborare i due documenti in modo che il confronto testuale faccia il miglior lavoro possibile. Ad esempio, in alcuni documenti XML, l'ordine di alcuni elementi potrebbe non avere importanza. Sarà sicuramente importante per il tuo strumento diff! Potrebbe essere necessario pre-elaborare l'XML utilizzando una Trasformazione XML che ordina questi elementi in un ordine comune in entrambi i file, prima di confrontare i due file ordinati.

si sta anche andando a voler usare lo stesso rientro per entrambi i documenti. Trovo utile iniziare ogni elemento su una nuova riga e usare la stessa quantità di indentazione, con spazi, per ogni livello. Se il tuo documento diventa molto profondo, dovresti utilizzare solo uno o due spazi per livello, in modo che il confronto si adatti allo schermo. Potresti anche voler utilizzare un attributo per riga (e ordinare gli attributi in un ordine comune).

Answer 4

Se sei l'unico "proprietario" dei dati tra i tuoi punti di annullamento/ripetizione, ovviamente puoi usare il testo in chiaro diff per loro. Come fai notare, equivale a un insieme di trasformazioni.

A seconda delle operazioni fornite, tuttavia, il diff in testo normale potrebbe non essere remoto in modo ottimale per la registrazione di annullamento/ripristino e potrebbe essere necessario specializzare determinati casi. Immagina solo di registrare un comando ReplaceAll che potrebbe essere solo pochi byte overhead più la stringa search and replace. Questo potrebbe generare enormi differenze in testo in chiaro.

Nel contesto generale, se si consente la modifica esterna di questi documenti e si sta pensando a come memorizzare i delta sul server, si sta imitando git o altri sistemi di controllo della versione. Devi usare un qualche tipo di algoritmo diff perché solo la registrazione dei tuoi comandi non è ovviamente l'unica fonte di trasformazione. A questo punto stai iniziando a mixare undo/redo con il controllo della versione e potresti voler pensare a confondere questi concetti per i tuoi utenti.

Manterrei annullare/ripristinare come all'interno di una sessione di modifica e vietare la modifica esterna mentre il file è aperto. Ciò consente di ottimizzare la registrazione dei comandi per casi ampi come ho detto sopra.

Oltre a ciò, è possibile utilizzare il controllo di versione convenzionale (si consideri il wrapping git) o ​​implementare il proprio modo di gestire i file modificati al di fuori del proprio editor.