Kann ich einen Klar diff-Algorithmus für die Verfolgung von XML-Änderungen verwenden?

https://stackoverflow.com/questions/2430083

19-09-2019
|

Frage

Ich arbeite in Flex / AS3 auf (der Einfachheit halber) ein XML-Editor. Ich muss liefern Undo / Redo-Funktionalität.

Natürlich ist eine Lösung, die die gesamte Quelltext mit jeder Bearbeitung zu speichern. Ich würde jedoch zu sparen Speicher, wie die Differentiale speichern statt.

(diese Differentiale werden auch auf den Server für die Auto-Speicher zu übertragen Updates verwendet werden)

Meine Frage ist - kann ich einen Klar diff-Algorithmus für die Verfolgung dieser XML-Änderungen verwenden

Meine Forschung im Internet zeigt, dass ich nicht tun. Allerdings fehlt mir natürlich etwas. Klartext diff bietet Funktionalität, ist vorgeblich:

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

XML ist einfach Text, also warum kann ich nicht nur diff () und Patch () den Text zuverlässig zu transformieren?

Zum Beispiel: Nehmen wir an, ich bin ein Dichter. Wenn ich Gedichte schreiben, verwende ich viel von funky Zeichensetzung ... Sie wissen, wie <, /, und>. (Sie können sehen, wo ich mit diesem gehe ...) Wenn ich meine Gedichte in einer Anwendung Ich schreibe, dass Verwendungen diffs zur Verfügung zu stellen Undo / Redo-Funktionalität, ist meine Poesie werden verstümmelt, wenn ich Undo / Redo meiner Änderungen? Es ist nur Text! Warum macht es einen Unterschied zu dem Algorithmus?

Ich verstehe natürlich nicht etwas hier ... Vielen Dank für die Erklärung! :)

UPDATE:

Einige Diskussion Ich habe festgestellt in Bezug auf die Differenzen zwischen XML mit einem Klar Algorithmus:

Auch verstehe ich, dass ein Befehlsmuster ist wahrscheinlich ein besserer Weg, Undo / Redo zu implementieren. Ich habe meine Anwendungsfall aus Gründen der Einfachheit vereinfacht, und ich glaube immer noch, dass XML diffing ist der beste Ansatz.

Lösung

Ich bin der Autor der Klartext-Diff / Spiels / Patch-Bibliothek von Google.

Die entscheidende Frage ist, ob die Patches genau sind. In einer idealen Welt:

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

Beachten Sie, dass der Basistext (Alter_Text) das gleiche in beiden Operationen ist. In diesem Idealfall dann ein einfacher Klartext-Diff und Patch werden perfekt funktionieren, unabhängig von der Art des Inhalts. Wenn dieser Fall auf Sie zutrifft, dann sind Sie fertig.

Die Frage liegt mit Fuzzy-Patching. Hier ist das entsprechende Beispiel:

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

Beachten Sie, dass der Basistext in beiden Operationen nicht das gleiche ist. Sie sollten ähnlich sein, aber der Patch-Betrieb hat jetzt die Verwendung von „Urteil“ über das, was sie tun sollten. Einige Patches können perfekt passen, wie in der Bearbeitung angegeben, andere müssen für die Position gezwickt werden, andere müssen für veränderten Kontext gezwickt werden, andere überhaupt nicht passen können und sollten fallen gelassen werden. Wenn Ihr Patching-Algorithmus keine Kenntnis von der Struktur von XML ist, wenn seine Entscheidungen, können Sie sehr gut mit malfromed XML enden. Hier ist ein Beispiel:

  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>

Schauen wir uns diese sorgfältig. Die ursprüngliche diff zurück zwei Bearbeitungen, zu einem DIV der äußersten SPAN ändern. Einfacher Wechsel. Leider ist der Text Bearbeiten angewendet wird, um von dem Original verändert. Das Wort „Jabberwock“ wurde entfernt. Nun ist die erste spa-> DIV Änderung übereinstimmt mit dem zweiten SPAN-Tag auf, nicht die erste. Da der Patch-Algorithmus keine Kenntnis von den Regeln von XML ist, ergibt sich illegal verschachtelte Tags.

Es gibt einige Hacks, die Ihnen erlauben gültige XML zu garantieren, wenn ein Klartext-Patch verwenden, aber sie führen zu einem gewissen Verlust an Flexibilität (die ursprüngliche Frage hat bereits einen Link zu der Wiki-Seite ich darüber geschrieben). Die ultimative Lösung für XML-Patching ist natürlich ein XML-fähiges Diff und Patch-Algorithmus zu verwenden. Dies sind deutlich mehr kompliziert und teuer, aber sie existieren. Google die Namen Tancred Lindholm und Sebastian Rönnau für die großartige Arbeit, dass sie im XML-Bereich getan haben (insbesondere im Hinblick auf DocEng).

Lassen Sie mich wissen, ob es noch etwas, das ich hinzufügen kann.

- Neil Fraser

Andere Tipps

Ich benutze Beyond Compare die ganze Zeit von XML-Dokumente zu vergleichen. Es versteht XML, bis zu einem gewissen Grad.

Möglicherweise müssen Sie die beiden Dokumente, um für Textvergleich vorverarbeiten den besten Job möglich zu tun. Zum Beispiel in einigen XML-Dokumenten kann die Reihenfolge einiger Elemente keine Rolle. Es wird sicherlich zu Ihrem Diff-Tool von Bedeutung! Möglicherweise müssen Sie die XML vorverarbeitet, die Sortierungen diese Elemente in einem gemeinsamen, um eine XML-Transformation in beiden Dateien verwenden, bevor die beiden Dateien sortiert verglichen wird.

Sie gehen zu wollen, auch die gleiche Vertiefung für beiden Dokumente verwenden. Ich finde es nützlich, jedes Element auf eine neue Zeile zu beginnen und die gleiche Menge an Einbuchtung zu verwenden, mit Leerzeichen, für jede Ebene. Wenn Ihr Dokument sehr tief wird, würden Sie wollen, nur ein oder zwei Räume pro Ebene verwenden, so dass die Anfälle auf dem Bildschirm vergleichen. Vielleicht möchten Sie auch pro Zeile ein Attribut verwenden (und die Attribute in eine gemeinsame Reihenfolge zu sortieren).

Wenn Sie der einzige „Eigentümer“ der Daten zwischen Ihrem Undo / Redo-Punkte dann natürlich sind, können Sie Klartext diff für sie verwenden. Wie Sie weisen darauf hin, beträgt er eine Reihe von Transformationen.

Je nach den Operationen, die Sie zur Verfügung stellen, jedoch Klartext diff kann nicht aus der Ferne in der Nähe optimal für die Aufnahme Undo / Redo und Sie können bestimmte Fälle spezialisieren müssen. Man stelle sich eine ReplaceAll Befehl Aufzeichnung, die nur ein paar Bytes Overhead sein könnte und das Suchen und Ersetzen-String. Das könnte massiven Klartext diffs erzeugen.

Im breiteren Kontext, wenn Sie erlauben, externe Bearbeitung dieser Dokumente, und Sie denken mehr darüber, wie Deltas speichern auf dem Server, Sie imitiert git oder andere Versionskontrollsysteme. Sie haben eine Art von Diff-Algorithmus zu verwenden, da nur die Befehle der Aufnahme ist natürlich nicht die einzige Quelle der Transformation. An diesem Punkt fängst du Undo / Redo mit Versionskontrolle zu mischen und Sie können über verwirrend diese Konzepte für die Benutzer denken, hart wollen.

Ich würde halten Undo / Redo, wie innerhalb einer Bearbeitungssitzung und verbieten die externe Bearbeitung, während die Datei geöffnet ist. Das ermöglicht es Ihnen, Ihre Befehlsaufzeichnung für breite Fälle zu optimieren, wie ich oben gesagt.

Darüber hinaus, entweder verwenden konventionelle Versionskontrolle (man denke Verpackung git) oder implementieren Sie Ihre eigene Art und Weise mit den Dateien der Bewältigung außerhalb Ihres Editor geändert werden.

Ich glaube, Sie Text diff für xml vor allem in Ihrem Fall verwenden können, wo Mensch wird die XML-Zeile für Zeile schreiben. Ich weiß nicht, welche Informationen Sie bekamen sagen Sie das nicht tun, aber ich denke, diese Aussage auf der Tatsache beruhte, dass Leerzeichen (Leerzeichen, Tabulator, neue Zeile ...) etwas anders ist, dass sie in einer Textdatei sind, die führen könnte in zwei verschiedenen Textdateien sind identisch aus einer XML-Perspektive. Aber auch hier für einen Editor Mensch Targeting, ich sehe nicht, warum Sie nicht können.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow