tree-based diff Algorithmus (Code-Vergleiche)

[MrTiger]

Hallo

Ich habe mich für einen Bachelor-Arbeit entschieden, in der ich einen line-based und einen tree-based diff algoritmus um zwei Codestücke zu vergleichen. Der Input sind XML-Files, welche ich intern wohl zuerst in Code umwandle. Es geht nicht darum einen Algorithmus zu erfinden, sondern nur einen bestehenden zu implementieren. Die Programmiersprache ist jetzt hier nicht relevant, da es mir zur Zeit nur ums Grundprinzip geht.

Nun muss ich leider bis nächste Woche bereits einen tree-based Algorithmus auswählen, leider habe ich aber praktisch keine Zeit, da ich einige Prüfungen habe.

Könntet ihr mir da vielleicht einen tree-based 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 muss in einer anderen Programmiersprache implementieren).

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

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

[MartinSt]

Die genau Antwort hast du tree-based diff Algorithmus (Code-Vergleiche) - Forum - CHIP Online schon bekommen.

[metux]

Schau doch mal in den git sources nach.

[MrTiger]

Vielen Dank metux.

Meinst du Git? Habe Git Sources noch nie benutzt. Ist da nicht eher so ein Programm, wo man Projekte koordinieren kann?

Ich muss hier wohl noch etwas klar stellen, ich bin da ein bisschen falsch verstanden worden. Es geht mir nicht darum, dass jemand für mich die Arbeit schreibt und ich werde auch selber nach Literatur etc. suchen. Es geht mir nur um Vorschläge für einen Baum-basierten und Zeilenbasierten Algorithmus, ich brauche nur etwas Starthilfe. Ich habe übrigens jetzt auch schon ein Weile gesucht und nicht wirklich etwas brauchbares zu dem Thema gefunden.

Bearbeitet 13. August 2012 von MrTiger

[flashpixx]

X-Diff: An Effective Change Detection Algorithm for XML Documents

Wikipedia Diff

Ansonsten schließe ich mich den Vorrednern an, es ist Deine Arbeit und Du musst selbst eine Lösung erarbeiten. Vor allem, wenn Du schon jetzt zu Beginn Probleme hast, dann würde ich evtl überlegen ob Du nicht das Thema wechseln solltest

Bearbeitet 14. August 2012 von flashpixx

[MrTiger]

Ansonsten schließe ich mich den Vorrednern an, es ist Deine Arbeit und Du musst selbst eine Lösung erarbeiten. Vor allem, wenn Du schon jetzt zu Beginn Probleme hast, dann würde ich evtl überlegen ob Du nicht das Thema wechseln solltest

Ich muss keinen Algorithmus erfinden, sondern nur bestehende implementieren. Und bei einer Arbeit geht es ja auch nicht darum, dass man alles problemlos abarbeiten kann, sondern das man die Probleme gut löst. Das Thema ist das beste, das ich gefunden habe bzw. das Thema, womit ich am wenigsten Probleme haben sollte.

[MrTiger]

Ich habe mich jetzt schon ein wenig eingelesen und die Aufgabenstellung wurde klarer, da ich mit dem Assi gesprochen habe.

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

ich danke vielmals.

Bearbeitet 21. September 2012 von MrTiger

[MrTiger]

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).

http://www.techfak.uni-bielefeld.de/ags/pi/lehre/PatTreesWS11/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.

f(x) is the father of node x, f^2(x) is the father of node f(x) etc.

The following is an algorithm for step (1):

for i = 1,2,...,|T1| do

for j= 1,2,...,|T2| do

for u = i,f(i),f^2(i),...,1 do

for s = u,f(u),f^2(u),...,1 do

for v = j,f(j),f^2(j),...,1 do

for t = v,f(v),f^2(v),...,1 do

if s = u = i and t = v = j then E[s u i, t v j] = r(T1 -> T2[j])

else if s=u=i or t<v=j then E[s u i, t v j] = E[s u i, t f(j) j-1] + r(lambda -> T2[j])

else if s<u=t or t=v=j then E[s u i, t v j] = E[s f(i) i-1, t v j] + r(T1[t] -> lambda)

else E[s u i,t v j] = min(E[s x i,t v j], E[s u i, t y j], E[s u x- 1,t v y-1] + E[x x t, y y j])

(T1[x] is the son of T1 on the path from T1 to T1, and T2[y] is the son of T2[v] on

the path from T2[v] to T2[ j ].)

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.