Diff Algorithmen

[The Gunner]

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.

 

[Rossie]

Was hast Du denn bereits gefunden? Nicht, dass sich jemand die Mühe macht, Links zu posten und Du kennst sie schon alle...

 

[calav3ra_de]

zeilenbasiert? ist das schwer?

 

[Dese]

zu deiner letzten frage:
was willst du denn mit der graphischen darstellung erreichen?also welchen sinn soll sie haben? das jemand damit die überführung machen kann (einfach) oder nur ne kleine veranschaulichung der unterschiede?
für ersteres wäre es (fast) unbrauchbar.

ich kann dir ansonsten keine links zu papern etc. bieten, da ich mich mit der thematik nur oberflächlig mal beschäftigt habe. worauf du aber zu aller erst dein augenmerk lenken solltest ist weniger ein algorithmus der dies erledigt, sondern mit welcher metrik mißt du die differenz.

dies wird ganz besonders bei baumstrukturen wichtig, da es hier ganz gewaltige unterschiedene gibt für was welche metrik sinnvoll ist. und ohne diese zu verstehen macht ein algorithmus, der dann die unterschiede berechnet wenig sinn.

woruaf willst du denn im falle des DOM-Tree wertlegen? dass du einen baum in exakt den anderen überführen kannst oder dass du das dokument, welches durch den einen beschrieben wird in das dokument beschrieben durch den anderen baum? und wann sind zwei dokumente gleich? wenn sie gleich aussehen und funktional sind?

aber ich denke google wird da einiges dazu bieten. schon mal versucht?

Ergänzung (21. September 2012)

kurzer nachtrag: im falle der bäume wird es im allgemeinen bestenfalls gute näherungen für spezialfälle geben, da das isormophie-problem für graphen schon für bäumen np-hart ist

 

[maxwell-cs]

da das isormophie-problem für graphen schon für bäumen np-hart ist

was genau meinst du hier mit isomorphie-problem für graphen? falls du das meinst, was man sonst so unter dem "Graph isomorphism problem" versteht: von dem ist für allgemeine graphen nicht bekannt, ob es NP-hart ist. falls man sich auf bäume beschränkt, ist es in P.

 

[Dese]

du hast recht. hab blödsinn geschrieben. nur ist das allgemeine GI-Problem höchst wahrscheinlich np-hart (hart nicht vollständig). wissen tut man es aber noch nicht.

und ja für bäume ist das problem in P (sogar sehr viel einfacher, glaub nc^1-complete).

woran ich aber eigentlich dachte, war die frage ob für eine gegebene metrik die distanz zweier bäume effizient berrechnet werden kann. das kommt natürlich auf die metrik (und die primitiven operationen) an. ich hab diesbezüglich bissle geschmökert und tatsächlich ist das polynomiell machbar für metriken, die nur das einfügen, löschen und ersetzten von einzelnen knoten als operationen erlauben.
http://grfia.dlsi.ua.es/ml/algorithms/references/editsurvey_bille.pdf

da gibt es noch mehr zum "tree edit problem", welches im übrigen nicht wohldefiniert ist.

ich muss gestehen, ich hatte es mir schwerer vorgestellt. hab mich damit aber einfach kaum jehmals beschäftigt. nur errinnerungen an einer alten vorlesung. das kann sehr trügen wie man sieht.

 

[maxwell-cs]

nur ist das allgemeine GI-Problem höchst wahrscheinlich np-hart (hart nicht vollständig).

wo soll da der unterschied sein? das problem ist doch offensichtlich in NP.

 

[Dese]

wo soll da der unterschied sein? das problem ist doch offensichtlich in NP.

beliebige klasse Y.

ein problem A ist Y-hart, wenn jedes problem B aus Y auf A reduziert werden kann.
ein problem A ist y-vollständig, wenn A in Y ist UND y-hart ist.

np-vollständigkeit impliziert np-hart. aber ein np-hartes problem muss nicht einmal in np liegen, es kann noch schwieriger sein, z.b. in PSPACE liegen. Das allgemeine GI ist vermutlich nicht in NP, nach dem was ich vorhin so gefunden habe.

 

[maxwell-cs]

wie gesagt, GI ist offensichtlich in NP, da sich eine permutation leicht in poly. länge kodieren lässt.

 

[Dese]

wie gesagt, GI ist offensichtlich in NP, da sich eine permutation leicht in poly. länge kodieren lässt.

ich hab nur mal durchgeschmöckert und was ich gelesen hab, da stand die behauptung im raum, dass es vermutlich nciht in np liegt. warum weiß ich nicht.

aber was du schreibst reicht nicht aus, denn du musst mit einer deterministischern turingmaschine in POLYNOMIELLER zeit und POLINOMIELLEN platzbedarf es lösen. dass du für die permutation nur poly platz brauchst ius ja schön, aber alle permutationen gehst du nicht in poly zeit durch

edit: nur zur info:
PSPACE ist die menge aller entscheidungsprobleme die eine deterministische turingmaschine in polynomiellerzeit mit polynomiellen platz entscheiden kann. PSPACE = NPSPACE nach satz von savage.

 

[maxwell-cs]

ok, hier ist die ausführliche variante:

als zertifikat verwenden wir, wie gesagt, eine permutation, die sich in poly. länge (in abh. der länge der kodierungen der beiden graphen) speichern lässt.

der eine graph sei G =(V, E), der andere graph sei H = (V', E').

die permutation definiert eine bijektion phi: V -> V'.
phi ist genau dann ein isomorphismus, wenn

e = {v,w} in E <=> e' = {phi(v), phi(w)} in E'.

das lässt sich in linearzeit überprüfen, indem man einmal über alle kanten in G läuft und überprüft, ob ihr bild unter der durch phi auf VxV induzierten abbildung auch in E' enthalten ist und einmal über alle kanten in H läuft und dasselbe in die andere richtung überprüft.

 

[Dese]

muss ich wirklich jedes detail vorkauen? ich dachte, du hast informatik studiert
...

hab ich. kennst das nicht wenn man manchmal dennoch auf'n schlauch steht wegen ner falschen annahme?

mein fehler war: "that this problem is probaly neither in P nor in NP-complete". in np liegt es, die frage ist nur ob es np-hart ist. https://www.informatik.hu-berlin.de...orithmenII/Publikationen/Papers/comp-gi.ps.gz

aber ja, ne einfache lösung von dir. hät mir mal die mühe geben sollen mal drüber nach zu denken. hab nicht einen moment weiter drüber nachgedacht wegen dem was ich dachte da gelesen zu haben.

edit: ich war versteift auf diesen satz und hab einfach nicht an die beweisprüfung gedacht.

 

[maxwell-cs]

hab ich. kennst das nicht wenn man manchmal dennoch auf'n schlauch steht wegen ner falschen annahme?

klar. ich hab meinen post ja auch schon ne weile editiert

 

[BigNum]

Meine Empfehlungen:

http://en.wikipedia.org/wiki/Diff

http://neil.fraser.name/writing/diff/

http://en.wikipedia.org/wiki/Longest_common_subsequence_problem


HTH

BigNum

 

[The Gunner]

Vielen Dank Leute, ihr seid toll.

Ich habe mich jetzt intensiv in line-based Algorithmen eingelesen und brauche dazu keine Literatur mehr.

Bei den Tree-based Algorithmen habe ich allerdings noch überhaupt nichts gefunden. Da wäre ich über alles froh. Eventuell müsste ich auch was über DOM trees und Abstract Syntax Trees (AST) lesen.


Ich habe noch zwei kleine Fragen (die Fragen vom letzten Mail haben sich erübrigt). Vielleicht könnt ihr mir da weiterhelfen.

1. Ich muss ja einen tree-based Algorithmus implementieren und einen line-based Algorithmus, der auf Wörter und Zeilen angewendet werden kann.

Ein Kollege hat mir nun vorgeschlagen eine Superklasse "Diff" zu machen und dann drei Subklassen "line-diff", "word-diff" und "tree-diff", wobei diese von der Superklasse erben. Ich finde das irgendwie nicht so toll, da die Klassen "line-diff"/"word-diff" und "tree-diff" wohl fast nichts gemeinsam haben. Den diff Algorithmus für Zeilen bzw. Wörter (ist ja genau derselbe) kann ich auch nicht in der Superklasse "Diff" implementieren, da er sonst ja auch in der "tree-diff" Klasse geerbt würde.

Ich würde mir da eher sowas vorstellen:

Superklasse "simple-diff"
Subklassen "line-diff" und "word-diff", die von "simple-diff" erben
Klasse "tree-diff"

Eine Superklasse, die alle diff Varianten (also line-diff, word-diff und tree-diff) umfasst, würde ich nicht machen, da wie gesagt die Schnittmenge wohl eher leer sein wird.

Wie seht ihr das?


2. In der word-based Klasse werde ich eine Funktion zur Verfügung stellen, die einen String Input in Worte unterteilt (welches dann als Input für den Diff Algorithmus genutzt werden kann).

Wie würdet ihr da die Worte trennen? Ich hätte mir da vielleicht nach Leerzeichen vorgestellt, also " ", denn dann wäre es ja auch auf normalen Text anwendbar. Da die Hauptanwendung allerdings bei source code liegt, bin ich mir da nicht sicher, ob eine solche Wort-Unterteilung Sinn macht. Wenn man aber besser unterteilen möchte, müsste man ja schon fast etwas semantisches implementieren, was aber über den Umfang der Arbeit weit hinausgehen würde.

Was hast Du denn bereits gefunden? Nicht, dass sich jemand die Mühe macht, Links zu posten und Du kennst sie schon alle...

Wie gesagt, habe ich bei den tree-based Algorithmen (DOM tree) noch gar nichts.

was willst du denn mit der graphischen darstellung erreichen?also welchen sinn soll sie haben? das jemand damit die überführung machen kann (einfach) oder nur ne kleine veranschaulichung der unterschiede?
für ersteres wäre es (fast) unbrauchbar.

Es soll eine graphische Veranschaulichung der Unterschiede sein.

woruaf willst du denn im falle des DOM-Tree wertlegen? dass du einen baum in exakt den anderen überführen kannst oder dass du das dokument, welches durch den einen beschrieben wird in das dokument beschrieben durch den anderen baum? und wann sind zwei dokumente gleich? wenn sie gleich aussehen und funktional sind?

Wie gesagt, habe ich mich mit DOM-trees, AST und tree-based Algorithmen noch nicht gross beschäftigt, da ich zuerst den line-based Algorithmus mache. Wenn man den Baum in den anderen überführt, dann hätte man ja was ähnliches wie bei line-based Algorithmen, wäre wahrscheinlich am einfachsten. Zwei Dokumente sind gleich, wenn sie genau gleich aussehen. Auf Semantik wird keinen Wert gelegt.

aber ich denke google wird da einiges dazu bieten. schon mal versucht?

Ja natürlich, aber bei tree-based Algorithmen habe ich fast nichts gefunden, wobei man bei line-based Algorithmen sehr viel findet.

http://grfia.dlsi.ua.es/ml/algorithm...rvey_bille.pdf

da gibt es noch mehr zum "tree edit problem", welches im übrigen nicht wohldefiniert ist.

Dese, ich habe das Paper dankend zur Kenntniss genommen.

 

[maxwell-cs]

Ein Kollege hat mir nun vorgeschlagen eine Superklasse "Diff" zu machen und dann drei Subklassen "line-diff", "word-diff" und "tree-diff", wobei diese von der Superklasse erben. Ich finde das irgendwie nicht so toll, da die Klassen "line-diff"/"word-diff" und "tree-diff" wohl fast nichts gemeinsam haben. Den diff Algorithmus für Zeilen bzw. Wörter (ist ja genau derselbe) kann ich auch nicht in der Superklasse "Diff" implementieren, da er sonst ja auch in der "tree-diff" Klasse geerbt würde.

Ich würde mir da eher sowas vorstellen:

Superklasse "simple-diff"
Subklassen "line-diff" und "word-diff", die von "simple-diff" erben
Klasse "tree-diff"

Eine Superklasse, die alle diff Varianten (also line-diff, word-diff und tree-diff) umfasst, würde ich nicht machen, da wie gesagt die Schnittmenge wohl eher leer sein wird.

Wie seht ihr das?

die funktionalität, die die algorithmen nach außen anbieten, sind - soweit ich das sehe - aber sehr ähnlich / gleich. falls das nicht der fall ist, ignoriere den rest, ich hab keine ahnung von line / tree-diffs.
in diesem fall bietet sich ein interface (=eine klasse ohne eigene implementierungen, von denen die drei erben) an, das dann die drei algorithmen implementieren. falls es zwischen word-diff und line-diff viele gemeinsamkeiten gibt, kannst du das ja ausnutzen und die vererbungsstruktur ausweiten.

 

[The Gunner]

Scheint mir logisch, vielen Dank. Falls weitere Probleme auftauchen, werde ich mich melden.

 

[daemon777]

Für die Programmierung der Algorithmen selbst wird dir die Vererbung wohl nicht besonders viele Vorteile einbringen. Dafür wäre der Aufruf von Außerhalb immer gleich, was den Code wiederverwendbar macht.
Außerdem könntest du die graphische Ausgabe in die Superklasse packen. Dann hast du den Kram schonmal nicht in deiner Implementierung der Algorithmen rumfliegen. Das ist natürlich nur dann sinnvoll, wenn die Ausgabe immer gleich visualisiert wird und nur durch das Vorgehen des Algos Unterschiede entstehen.

 

[The Gunner]

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

 

[Dese]

ich hab mir jetzt mal das original nicht angeschaut, aber aus dem was du aufgeschrieben hast würde ich sagen:
1. E[s u i, t v j] ist ein 2D array. erste dimension umfasst s*u*i und zweite t*v*j. Das komma trennt.
2. der speicherverbrauch davon ist lediglich n*log²n * n*log²n. du solltest damit keine probleme haben.

edit: s, u ,t, v durchlaufen den baum nur nach oben (vater von vater). das sind also nur log |T1| bzw. log |T2| schritte.

noch ein edit: das kann man offenbar sogar noch weiter optimieren, denn s beginnt immer mit u und t immer mit v. das halbiert jede der beiden dimensionen für E.