Diff Algorithmen

M

MrTiger

Grünschnabel
Hallo

Ich würde gerne einen zeilenbasierten und Baumbasierten Diff Algorithmus schreiben. Für den Baumbasierten Diff Algorithmus sollten zwei XML files als Input dienen, wobei dann der DOM-tree erzeugt wird und darauf der Algorithmus anwendet wird (wie hängt der DOM-tree mit dem AST zusammen?).

Kann vielleicht jemand gute Papers bzw. Code insbesondere zu baumbasierten Diff Algorithmen (basierend auf dem DOM-tree) empfehlen? Über Papers bzw. Code zu zeilenbasierten Algorithmen wäre ich auch fro (wobei baumbasierte Algorithmen wichtiger sind).


-------------------------
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.
 
Ich danke euch. Es geht nicht direkt um das Diffen von XML Dokumenten. Die XML Dokumente werden in einen DOM tree geparsed (habe dafür eine library). Der tree diff Algorithmus soll dann auf den DOM Tree angendet werden.

Hat da vielleicht gerade jemand Literatur oder Tipps? Ist schwer da etwas zu finden.
 
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.

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[i] -> 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[u] on the path from T1[u] to T1[i], 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.
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück