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.

[canlot]

http://forum.chip.de/programmieren/tree ... 60512.html *schmunzel*

[Xin]

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.

Ich habe jetzt mal flott in 5 Büchern nach diff geguckt, aber nichts gefunden - jedenfalls nicht unter "diff". Wenn in "Art of Computer Programming" nix dazu drin steht, gibt's diese Algorithmen nicht

Also muss ich mal gucken, was es sonst noch für Suchbare Stichworte dazu gibt.

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.

Dann solltest Du die Bachelorarbeit günstiger legen.

Aber schau mal hier:
http://neil.fraser.name/writing/diff/

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

Hehehe, soll noch Wünsche

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

Ich interessiere mich für das Thema, weil ich auch ein Diff implementieren muss. Ich weiß nicht, ob das schon akut ist, wenn Du Deine Bachelorarbeit schreibst, aber ich biete mich zumindest schonmal an, sie vorab zu lesen und zu kommentieren.
Zum einen bin ich daran interessiert, das heißt, ich würde Deine Beschreibung nacharbeiten, zum anderen bin ich Diplom-Informatiker, als Ghostwriter ein Bachelor-Arbeit brauche ich Dich also nicht mehr

[MrTiger]

Ich danke dir vielmals Xin.

Ich habe jetzt etwas gefunden. Einen Zeilenbasierten diff Algorithmus macht man wohl am besten mit longest common subsequence (dynamic programming). Dazu habe ich auch einige Literatur gefunden, leider aber kein Code-Beispiel in Java. Kennst du da vielleicht gerade was?

Den Baum-basierten Algorithmus macht man wohl mit Levenshtein. Dazu habe ich aber noch keine Literatur gefunden (also auf den Verwendungszweck als diff Algorithmus) und auch noch kein Code. Kannst du da vielleicht weiterhelfen?

Ich interessiere mich für das Thema, weil ich auch ein Diff implementieren muss. Ich weiß nicht, ob das schon akut ist, wenn Du Deine Bachelorarbeit schreibst, aber ich biete mich zumindest schonmal an, sie vorab zu lesen und zu kommentieren.
Zum einen bin ich daran interessiert, das heißt, ich würde Deine Beschreibung nacharbeiten, zum anderen bin ich Diplom-Informatiker, als Ghostwriter ein Bachelor-Arbeit brauche ich Dich also nicht mehr

Vielen Dank für das Angebot. Ich habe ja noch nicht mit der Arbeit begonnen, bin erst im Anfangsstadium.

In wie fern musst du denn einen Diff implementieren (in welchem Zusammenhang)?

[Xin]

Ich habe jetzt etwas gefunden. Einen Zeilenbasierten diff Algorithmus macht man wohl am besten mit longest common subsequence (dynamic programming). Dazu habe ich auch einige Literatur gefunden, leider aber kein Code-Beispiel in Java. Kennst du da vielleicht gerade was?

Bisher nicht.

Meine Algorithmenbücher werfen da nicht viel ab.

Den Baum-basierten Algorithmus macht man wohl mit Levenshtein. Dazu habe ich aber noch keine Literatur gefunden (also auf den Verwendungszweck als diff Algorithmus) und auch noch kein Code. Kannst du da vielleicht weiterhelfen?

Auch hier schweigen sich die Bücher aus. Lediglich 'The Art of Computer Programming' (Bd. 3) erwähnt Levenshtein ohne ihn zu beschreiben.

Ich interessiere mich für das Thema, weil ich auch ein Diff implementieren muss. Ich weiß nicht, ob das schon akut ist, wenn Du Deine Bachelorarbeit schreibst, aber ich biete mich zumindest schonmal an, sie vorab zu lesen und zu kommentieren.
Zum einen bin ich daran interessiert, das heißt, ich würde Deine Beschreibung nacharbeiten, zum anderen bin ich Diplom-Informatiker, als Ghostwriter ein Bachelor-Arbeit brauche ich Dich also nicht mehr

Vielen Dank für das Angebot. Ich habe ja noch nicht mit der Arbeit begonnen, bin erst im Anfangsstadium.

In wie fern musst du denn einen Diff implementieren (in welchem Zusammenhang)?

Ich muss eine Versionsverwaltung abbilden und dafür muss ich die Unterschiede zwischen Texten erkennen können.

[nufan]

Ich habe jetzt etwas gefunden. Einen Zeilenbasierten diff Algorithmus macht man wohl am besten mit longest common subsequence (dynamic programming). Dazu habe ich auch einige Literatur gefunden, leider aber kein Code-Beispiel in Java. Kennst du da vielleicht gerade was?

Einen dynamisierten LCS-Algorithmus kann ich dir schon erklären, aber was machst du dann mit dem Ergebnis?!

[MrTiger]

Ich muss eine Versionsverwaltung abbilden und dafür muss ich die Unterschiede zwischen Texten erkennen können.

Für eine Bachelor- oder Master-Arbeit?

Einen dynamisierten LCS-Algorithmus kann ich dir schon erklären, aber was machst du dann mit dem Ergebnis?!

Zum Zeilenbasierten bzw. LCS-Algorithmus habe ich schon einige Literatur und Beispiele gefunden, das werde ich zuerst einmal durchlesen. Vielleicht habe ich dann noch fragen. Zum Baumbasierten bzw. Levenshtein habe ich aber noch fast nichts gefunden. Das ist dann wohl eher das Problem.

Wie meinst du was ich mit dem Ergebnis mache? Das Ergebnis wird in einem GUI visualisiert. Also zuerst wird wohl ein Array mit den Differenzen zurückgegeben und mit einer seperaten Funktion kann man es dann in einem GUI visualisieren.

[Xin]

Ich muss eine Versionsverwaltung abbilden und dafür muss ich die Unterschiede zwischen Texten erkennen können.

Für eine Bachelor- oder Master-Arbeit?

Für ein Content-Management-System.

Ich bin schon Diplom-Informatiker (FH), ich programmiere für das wahre Leben
Ich spiele zwar mit dem Gedanken mal spaßeshalber einen M. Sc. hinterherzuschieben, aber zum einen fehlt die Zeit und zum anderen Diplom ist ja auch ganz schön. Schon witzig... der eine macht eine Indexbasierte-Suchmaschine als Master-Arbeit, Du den Diff. Da frage ich mich echt, warum ich mir bei meiner Diplomarbeit damals soviel Aufwand gemacht habe.

Vielleicht sollte ich einfach mal meine privaten Quellcodes zur Uni tragen und mir einen Doktor aushändigen lassen ;-D

Einen dynamisierten LCS-Algorithmus kann ich dir schon erklären, aber was machst du dann mit dem Ergebnis?!

Zum Zeilenbasierten bzw. LCS-Algorithmus habe ich schon einige Literatur und Beispiele gefunden, das werde ich zuerst einmal durchlesen. Vielleicht habe ich dann noch fragen. Zum Baumbasierten bzw. Levenshtein habe ich aber noch fast nichts gefunden. Das ist dann wohl eher das Problem.

Ich mache hier keine Recherche, aber zu Levenshtein habe ich auf die Schnelle die Distanz zwischen Wörtern gefunden.

Den nächsten Gedankenschritt drängt sich auf und doch musste ich ihn hier leider hier wieder entfernen, denn den nächsten Gedanken zu fassen, sollte Teil Deiner Leistung zur Bachelorarbeit sein.

Zu Diskutieren wäre jedoch, ob die Ergebnisse von Levenshtein optimal für einen Diff-Algorithmus sind.

Wie meinst du was ich mit dem Ergebnis mache? Das Ergebnis wird in einem GUI visualisiert. Also zuerst wird wohl ein Array mit den Differenzen zurückgegeben und mit einer seperaten Funktion kann man es dann in einem GUI visualisieren.

Wie gesagt, ich stehe vor einem ähnlichen Problem. Inkl. der Visualisierung, ob das in einer GUI oder dem Web passiert, spielt dabei ja keine Rolle. Von daher bin ich am Ergebnis Deiner Arbeit in C++ interessiert, weil es mir Arbeit abnehmen könnte - im Gegenzug liest jemand Deine Bachelor-Arbeit, bevor es der Prof tut.

Dank der kurzen Recherche für diesen Thread sehe ich mich inzwischen aber auch ganz gut gerüstet, den Diff zu implementieren.

Momentan habe ich noch keinen Diff. Ich kann Dir in diesem Sinne anbieten, in Deine Bachelorarbeit einzupflegen, dass der Nutzen Deiner Arbeit schon dadurch gegeben ist, dass Dein Code anschließend produktiv verwendet wird - das spart mir eventuell die Arbeit und Deine Arbeit wird von einer Hausaufgabe zu einem produktiv genutztem Werk. Dafür wäre allerdings das C++ Fähnchen zu schwenken und zwar als Template.
Beim Template kann ich Dir bei Bedarf noch helfen, da Du ja den Algorithmus (be-)schreiben sollst und nicht C++-Templates. Dazu kann ich Dir dann ggfs. für C++ bei Unit-Tests zuarbeiten, denn das ist ja auch nicht Deine Aufgabe, sichert aber Deine Arbeit ab. Sprich das aber ggfs. mit Deinem Prof ab.

[turbo]

Moin,

Den Baum-basierten Algorithmus macht man wohl mit Levenshtein. Dazu habe ich aber noch keine Literatur gefunden (also auf den Verwendungszweck als diff Algorithmus) und auch noch kein Code. Kannst du da vielleicht weiterhelfen?

zu Levenshtein habe ich einige Links:
http://de.wikipedia.org/wiki/Suffixbaum
http://de.wikipedia.org/wiki/Levenshtein-Distanz
http://xlinux.nist.gov/dads/
http://www.delphipraxis.net/58797-proze ... tteln.html
http://www.delphipraxis.net/399584-post.html#472481
http://www.koders.com/delphi/fid54DC48F ... s=download
http://www.h-j-luecking.de/wiki/Einfach ... in_Distanz
http://www.sound-ex.de/
http://levenshtein.de/

[Xin]

@turbo: Wir brauchen eine +1 Funktion im neuen CMS