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 ... ee_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: Alles auswählen
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.
Dort gibt es keine Interfaces, sondern nur deferred Klassen (was aber ungefähr das gleiche ist). Templates kenne ich nicht. Was ist das?