Hallo

Ich möchte gerne einen Baum-basierten und Zeilenbasierten diff Algorithmus schreiben um zwei Codestücke zu vergleichen (Input kann entweder ein Classfile oder ein XML File sein). Welche Programmiersprache ich verwende, spielt jetzt gerade keine Rolle, da es mir zuerst nur ums Prinzip geht. Könntet ihr mir da vielleicht einen Baum-basierten diff Algorithmus empfehlen? Er sollte nicht zu kompliziert sein, gut dokumentiert (Literatur) und v.a. sollte bereits eine Implementation z.B. in Java vorhanden sein (Ich werde in einer anderen Sprache implementieren).

Wäre nett, wenn da jemand weiterhelfen könnte.

PS: Falls jemand auch gleich noch einen guten zeilenbasierten diff Algorithmus empfehlen könnte, wäre ich auch froh.

Ich habe mich jetzt schon ein wenig eingelesen und die Aufgabenstellung wurde klarer.

Als Input für den line-based Algorithmus sollen XML files und String Objekte möglich sein, d.h. der Algorithmus kann eigentlich auf jedes Dokument angewendet werden.

Der tree-based Algorithmus akzeptiert nur XML files als Input. Es soll zuerst ein DOM tree erstellt werden (in wie fern hängt der mit dem AST zusammen?), wobei Der Algorithmus dann auf diesen DOM tree anwendet werden soll.

Ich wäre froh, wenn ihr mir vielleicht Literatur (insbesondere Papers) zu tree-based Algorithmen (auf der Basis von der DOM Struktur) empfehlen könnt. Die Papers sollten nicht zu umfangreich sein und nicht zu kompliziert, wenn sie gerade noch Code Beispiele enthalten würden, wäre das natürlich toll. Falls jemand noch Literatur über DOM bzw. AST hätte, würde ich das auch dankend annehmen (wobei natürlich Literatur über tree-based Algorithmen Priorität haben).

Beim line-based Algorithmus habe ich schon einige Papers gefunden, falls jemand aber noch zusätzliche empfehlen könnte (z.B. über Levensthein, Diff von Unix etc.), wäre das nicht schlecht (aber wie gesagt tree-based hat Priorität, da ich da noch praktisch keine Papers gefunden habe).



-------------------------
By the way, Eine kleine kurze Frage habe ich noch. Vielleicht könnt ihr mir da helfen.

Nehmen wir an, dass wir zwei Dokumente A und B hätten, wobei A = abbba und B = abbab

Mit dem line-based Algorithmus, den ich implementieren könnte, würde man ein edit script bekommen mit dem man vom ersten Dokument (A) aufs zweite Dokument (B) kommt. D.h. es würde beschrieben werden, welche Elemente in A gelöscht und welche eingefügt werden müssten.

Also z.B. für das obige Beispiel würden wir das 4. Element von A löschen und das 3. b aus B nach der 5. Stelle von A einfügen. Somit würden wir aus A B bekommen.

Wenn ich nun die Differenzen graphisch darstelle, wäre es dann ok, wenn ich im Dokument A einfach alle Elemente, die gelöscht wurden markiere (also das 4. Element von A) und in Dokument B einfach alle Elemente markiere, die in A eingefügt wurden (also das 3. Element von B) ?

ich danke vielmals.

So ich habe mich jetzt in die tree-based diff algorithmen eingelesen und möchte nun den Algorithmus aus dem Paper 'The Tree-to-Tree Correction Problem' von Tai implementieren.

S. 431 (bzw. S 10 im PDF) step (1), step(2) und step(3).
techfak.uni-bielefeld.de/ags/p…WS11/tree-to-tree_tai.pdf

Leider ist der nicht so ganz einfach und ich habe ziemliche Probleme. Es sind zwei Bäume vorhanden, welche in Preorder nummeriert sind (wie im Algorithmus gefordert).

Zur Zeit hänge ich gerade im Step(1) des Algorithmus fest. Und zwar geht es da um folgenden Code.



Wichtig ist hier noch, dass s <= u < i und t <= v < j. Es gilt preorder Nummerierung. T1 und T2 sind die zwei Bäume die "gedifft" werden sollen. |T1| und |T2| ist die Anzahl der Knoten in den Bäumen. r(...) bedeutet eine edit operaton, also das löschen, hinzufügen oder verändern eines Knotens.

Der Pesudocode ist ja nun ziemlich abstrakt und nicht so leicht zu implementieren. Ich möchte zudem nicht nur die edit distance, wie im Algorithmus berechnet wird, sondern auch gleich noch das edit script dazu.

Hat da vielleicht jemand einen Tipp wie ich den Algorithmus am besten umsetzen könnte? Wie gesagt, die Baumstruktur ist schon vorhanden.

Insbesondere habe ich ein Problem mit Datenstruktur für E[s u i, t v j].
E[s u i, t v j] muss man doch fast als 6D Array speichern oder wie würdet ihr das machen? Das Array wäre dann leider ziemlich gross, also |T1| x |T1| x |T1| x |T2| x |T2| x |T2|. Für grössere Bäume ist die Laufzeit sehr schlecht.

Die einfachste Möglichkeit wäre natürlich das Mapping auf ein 1D Array zu machen, das wäre auch sehr schnell, aber da habe ich dann das Problem dass es out of memory läuft.