1. Zuhause
  2. Frage und Antwort
  3. Wie funktionieren Document Diff Algorithmen?

Wie funktionieren Document Diff Algorithmen?

2009-10-02 7 views

Antwort

3

Die meisten optimize Lösung von LCS ist O(ND) Myer 's algorithm, und hier ist ein algorithmischer Ansatz, Ich habe verwendet, um diff Office 2007 Dokumente zu implementieren. Link to algorithm paper

Quelle

2009-10-03 17:34:39 SunnyShah

+4

Papierverbindung funktioniert nicht .. –

+2

Dies funktioniert für mich: http://www.xmailserver.org/diff2.pdf – Zamicol

15

Ein Diff ist im Wesentlichen nur a solution zu longest common sub-sequence problem.

Die optimale Lösung erfordert Kenntnisse von dynamic programming, so ist es ein ziemlich komplexes Problem zu lösen.

Es kann jedoch auch getan werden, indem Sie einen Suffix-Baum erstellen. Beide Algorithmen sind umrissen here.

Quelle

2009-10-02 15:24:13

+1

Das ist im Allgemeinen, wenn Sie davon ausgehen, dass Ihr Dokument ein Strom von Zeichen oder Bytes ist.Hier geht es jedoch um ein Word-Dokument. Bevor Sie einen solchen Algorithmus implementieren, müssen Sie sich eine Frage stellen: "Hello World" in Blau 8pt Verdana gleich "Hello World" in Rot 10pt Arial, etc. – quosoo

+1

Ja, offensichtlich benötigen die grundlegenden Algorithmen zusätzliche Logik, um solche zu parsen Unterschiede, aber der Kern des Algorithmus wird immer noch der gleiche sein. –

2

Wie Ben S anmerkte, kann das Differenzierungsproblem allgemein gelöst werden, indem das längste gemeinsame Subsequenzproblem gelöst wird. Insbesondere ist Hunt-McIlroy algorithm einer der klassischen Algorithmen, die auf das Problem angewendet wurden (z. B. bei der Implementierung von Unix 'diff).

Quelle

2009-10-02 15:28:29

28

Nun, im Allgemeinen wird diff 'in der Regel durch die Longest common subsequence problem gelöst. Siehe auch die "Algorithm" Abschnitt der Wikipedia-Artikel über Diff.

Der Betrieb von diff auf basiert die längste gemeinsame Teilfolge Problemlösung

In diesem Problem, Sie haben zwei Sequenzen von Elementen :

a b c d f g h j q z 

    a b c d e f g i j k r x y z

und Sie möchten die längste Reihenfolge der Elemente finden, die in bot vorliegt h Originalsequenzen in der gleichen Reihenfolge. Das heißt, Sie möchten eine neue Sequenz finden, die von der ersten Sequenz durch Löschen einiger Elemente und aus der zweiten Sequenz von Löschen anderer Elemente erhalten werden kann. Sie wollen auch diese Sequenz so lang wie möglich sein. In diesem Fall ist es

a b c d f g j z

Von der längsten gemeinsamen Teilfolge es ist nur ein kleiner Schritt diff-ähnliche Ausgabe zu erhalten:

e h i q k r x y 
    + - + - + + + +

Das heißt, das alles funktioniert gut mit textbasierten Unterlagen. Da Word-Dokumente effektiv in einem binären Format vorliegen und viele Formatierungsinformationen und Daten enthalten, ist dies sehr viel komplexer. Im Idealfall könnte man Wort selbst schaut in der Automatisierung, da es die Fähigkeit, „diff“ zwischen Dokumenten hat, wie hier beschrieben:

Microsoft Word Tip: How to compare two documents for differences

Quelle

2009-10-02 15:30:03 CraigTP

+0

Es gibt zwei Zwecke, um eine Diff-Algorithmus-Implementierung zu haben: Um nur die Unterschiede zwischen den Versionen zu speichern oder um die Unterschiede zwischen den Versionen anzuzeigen. Diese sind sehr unterschiedlich (kein Wortspiel beabsichtigt). LCS ist normalerweise nur zum Anzeigen der Unterschiede geeignet, aber für eine optimale Speicherung werden fortschrittlichere Algorithmen benötigt. Wenn Sie beispielsweise einen großen Teil eines Abschnitts des Dokuments ausschneiden und in einen anderen Abschnitt einfügen, wird dies von einem guten Speicheralgorithmus erkannt und nicht als "hey, viele neue Daten wurden gerade hier angezeigt" gespeichert. –

+2

@Lasse - Einverstanden. Da der ursprüngliche Fragesteller über Word-Dokumente sprach, nahm ich an, dass sie sich mehr für die "visuelle" Seite des Diffing interessieren würden als für die Storage-Seite. Sie haben jedoch Recht, dass Sie für die Speicherseite in Delta Encoding/Compression (http://en.wikipedia.org/wiki/Delta_encoding) usw. suchen. – CraigTP

Verwandte Themen

 Verwandte Themen