tree-based diff Algorithmus (Code-Vergleiche)

[turbo]

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

steck' das mal dem Admin

[oenone]

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

Zum Einen geht es hier um eine Bachelor-Arbeit (Bachelor < Diplom), zum Anderen ist eine wissenschaftliche Abschlussarbeit zur Erreichung eines akademischen Grads oder Titels mehr als nur Quellcode

Was für ein Thema hatte denn deine DA?

[Xin]

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

Zum Einen geht es hier um eine Bachelor-Arbeit (Bachelor < Diplom),

Bachelor < Diplom gilt in der Wirtschaft, Akademisch gesehen bin ist mein Diplom gleichwertig mit dem Bachelor.

zum Anderen ist eine wissenschaftliche Abschlussarbeit zur Erreichung eines akademischen Grads oder Titels mehr als nur Quellcode

Das ist wohl wahr. Aber eine Bachelorarbeit schreibe ich in zwei Wochen, wenn's sein muss.
Mehr Zeit hatte ich für die Diplomarbeit auch nicht... eigentlich waren es 12 Wochen, aber es kam halt was dazwischen.

Was für ein Thema hatte denn deine DA?

Du kannst Fragen stellen... den Titel weiß ich nicht mehr. ^^

Es ging um Programmiersprachen - worum sonst?

"Verminderung von Quelltext-Redundanzen durch Definition einer nicht spezialisierten, orthogonalen Programmiersprache".
Waren so um die 160 Seiten. Leider fehlte mir die Zeit, um die Arbeit vollständig zu machen, aber ich bekam eh einen Rüffel, dass ich doppelt zuviel geschrieben hätte, wie man lesen wollte. ^^

[MrTiger]

Hallo

Bitte entschuldigt meine verspätete Antwort, aber ich hatte Examen und war dann noch in den Ferien. Jetzt habe ich mit der Arbeit begonnen. Dank euch fiel mir der Einstieg viel leichter, vielen
Dank. Ich habe mich jetzt schon ein wenig eingelesen und die Aufgabenstellung wurde klarer, da ich mit dem Assi gesprochen habe.

Die Programmiersparche ist Eiffel, ich denke nicht, dass ihr euch damit auskennt.

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 (Die Konvertierung zwischen String Objekten und XML Files entfällt). 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 (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.

[Xin]

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.

Ich suchte heute ein Binary Diff. Und nu?

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

Das klingt ein wenig so wie 'Ich wäre froh, wenn mir jemand meine Arbeit schreibt'.

Es geht ja auch ein wenig darum, dass Du Dir die Sachen recherchierst, anschaust, verstehst und bearbeitest.

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

Du darfst auch gerne Links setzen.

Ich kann Dir leider keine weiteren Papers anbieten, da ich bisher nicht danach gesucht habe und in meinem Algorithmenbüchern auch nix gefunden. Und am eigenen Diff bin ich noch nicht.

[turbo]

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

Das klingt ein wenig so wie 'Ich wäre froh, wenn mir jemand meine Arbeit schreibt'.

Es geht ja auch ein wenig darum, dass Du Dir die Sachen recherchierst, anschaust, verstehst und bearbeitest.

auf mich wirkt das genauso

[Xin]

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.

Das klingt ein wenig so wie 'Ich wäre froh, wenn mir jemand meine Arbeit schreibt'.

auf mich wirkt das genauso

Naja, bei Recherche ist es natürlich legitim andere Leute zu fragen, ob sie Quellen kennen. Und Präferenzen zu äußern ist natürlich auch legitim.
Bei der Vielzahl der Quellen ist es natürlich schon interessant, wenn man die Quellen auch vorsortieren darf.

Versuchen kann man es ja mal

[MrTiger]

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.

Der Assistent 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.

Ich suchte heute ein Binary Diff. Und nu?

line-based.

Das klingt ein wenig so wie 'Ich wäre froh, wenn mir jemand meine Arbeit schreibt'.

Es geht ja auch ein wenig darum, dass Du Dir die Sachen recherchierst, anschaust, verstehst und bearbeitest.

Ich möchte ja nicht, dass jemand für mich die Literatur liest oder die Arbeit schreibt. Ich werde schon selber lesen. Recherchiert habe ich auch schon, nur leider finde ich zu den tree-based Algorithmen nichts.

[Xin]

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

Der Assistent 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?

1.) Schreib eine Interface-Klasse.
2.) Kennst Du Templates?

Ich vermute Templates sind Dir noch nicht so geläufig, denn mit deren Denke würdest Du den Levenshtein direkt auf Dein Problem anwenden können. Deswegen mag ich Java nicht... wem die Sprache fehlt, dem fehlt auch das Denken. Lass mich raten, ihr lernt Java? ^^
(Bestätige mir doch mal eben meine Vorurteile )

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.

Ich würde vermutlich meine indexbasierte Suchmaschine ausgraben und die Worte einfach als Index auffassen.
Ich könnte auch meinen 3D-Kern nehmen und die PointCloud nehmen, in der ich alle im 3D-Objekt verwendeten Punkte einem Index zuordne... moment... das die Cloud ist ja ein Template, dass ich für beides benutze, so dass es vollkommen egal ist, ob ich Punkte oder Wörter indizieren möchte...

Für den Fall, dass sich Punkte oder Wörter wiederholen können, habe ich ein Klasse geschrieben, die weniger wie ein Set arbeitet, sondern eher wie ein Array. Schließlich soll aus den Wort-Indizies ja wieder Texte werden und aus den Punkt-Indizes wieder geometrische Figuren.

Ich suchte heute ein Binary Diff. Und nu?

line-based.

byte-based. Was mit einer Template-Superklasse ja gar keinen Unterschied mehr machen würde.

Das klingt ein wenig so wie 'Ich wäre froh, wenn mir jemand meine Arbeit schreibt'.

Es geht ja auch ein wenig darum, dass Du Dir die Sachen recherchierst, anschaust, verstehst und bearbeitest.

Ich möchte ja nicht, dass jemand für mich die Literatur liest oder die Arbeit schreibt. Ich werde schon selber lesen. Recherchiert habe ich auch schon, nur leider finde ich zu den tree-based Algorithmen nichts.

So leid es mir tut, ich habe hier nichts vorliegen. Wenn ich Dir aus dem Kopf raus Hinweise geben könnte, würde ich es tun. In meiner Bibliothek habe ich aber auch nichts passendes gefunden. Also kann ich - wie Du - auch nur im Internet recherchieren.
Ansonsten - wenn ich nach "tree based diff" suche, finde ich vorrangig Deine Postings. Mir scheint, dass "tree based diff" also kein guter Suchbegriff ist. based... Baumbasierte Unterschiede... würdest Du das schreiben? "Unterschiede durch Baumstrukturen aufzeigen" eher, da kommt aber kein basiert drin vor... Ich vermute, wenn Du nach carbon based lifeform suchst, findest Du weniger, als wenn Du einfach nach carbon und lifeform suchst... die Ergebnisse finde ich jedenfalls auf den ersten Blick interessanter... aber ich muss Dir wohl nicht sagen, wie Du google bedienen musst? ^^

Nochmehr ansonsten: Vielleicht schaust Du mal in den Quelltext von diff?

[MrTiger]

1.) Schreib eine Interface-Klasse.
2.) Kennst Du Templates?

Ich vermute Templates sind Dir noch nicht so geläufig, denn mit deren Denke würdest Du den Levenshtein direkt auf Dein Problem anwenden können. Deswegen mag ich Java nicht... wem die Sprache fehlt, dem fehlt auch das Denken. Lass mich raten, ihr lernt Java? ^^
(Bestätige mir doch mal eben meine Vorurteile )

Ich muss in Eiffel implementieren. Dort gibt es keine Interfaces, sondern nur deferred Klassen (was aber ungefähr das gleiche ist). Templates kenne ich nicht. Was ist das?