bin grad unterwegs, deshalb nur ein kurzer Blick nach devshare und eine kurze Antwort:

1. Die Versionskontrolle ist nochmal ein anderer Schuh. Wahrscheinlich wird es so laufen, dass es nur eine Linie an Veränderungen geben wird und dass (bestimmte) registrierte Benutzer einen Artikel eine bestimmte Zeit auschecken können, währen der dieser dann nicht bearbeitet werden kann. Andere Benutzer erhalten dann, falls sie z.B. V.5 editieren, zwischenzeiltlch jemand jedoch das gleiche getan hat und V.6 bereits existiert einen Hinweis usw. - wie auch immer, daru geht es hier nicht. Gegeben sind zwei Texte, einer aus dem anderen entstanden, womöglich auch beide grundverschieden...

2. Die Darstellung der Änderungen liegt nicht innert eines HTML-Formulars und ist auch erstmal kein Thema.

3. Hinzugefügte und entfernte Buchstaben und Passagen lassen sich natürlich leicht darstellen, verschobene schon schwieriger. Da kommt es darauf an herauszufinden, was mehr taugt. Im Prinzip ist es im obigen Beispiel egal, ob die Wörter als korrigiert oder die Sätze als vertauscht markiert werden. Wichtig ist einfach, dass man gut erfassen kann, was sich geändert hat und hier mach ich auch Schluß... bis nächste Woche...

Basti

wie soll der Ablauf sein und was genau ist gewünscht?

Ich hatte gedacht:

1.) Gegeben ist ein Ausgangstext X

2.) X wird gelesen (von wem ?) und gegebenenfalls geändert (von wem ?)

3.) Nun haben wir Version X_1 (wenn nur eine Person Änderungen vornehmen darf),
bzw. verschiedene Versionen von X_1 (wenn mehrere Personen Änderungen vornehmen dürfen).

Wie ich's verstanden hatte, soll nun diese Version X_1 insofern aufbereitet werden,
daß die am Prozess Beteiligten möglichst auf den ersten Blick erkennen können, welche
Änderungen stattgehabt haben.

4.) Schritte 2.) und 3.) wiederholen sich, bis wer(?) mit dem Ergebnis zufrieden ist.

Wobei hier wichtig wäre, den Arbeitsablauf zu synchronisieren, sodaß nicht jemand
anfängt, Version X_1n zu ändern, während schon längst Version X_3 aktuell ist, aber
das wär sozusagen andre Baustelle.

Aber zunächst: Ist das so richtig? Dein Interesse ist wesentlich die sinnvolle
Darstellung der Änderungen in Punkt 3.) ?

------------------------------------------

Sodann - nimm einfach mal das alte Beispiel des durcheinandergeratenen Kochrezepts:

X ->

Rezept:

Braten Sie das Hühnchen

Schlachten und rupfen Sie das Hühnchen

Fangen Sie das Hühnchen

X1 ->

Rezept:

Fangen Sie das Hühnchen

Schlachten und rupfen Sie das Hühnchen

Braten Sie das Hühnchen

------------------------------------------

Problem:

Wenn man, wie vorgeschlagen, nach den längsten zusammenhängenden Blöcken sucht,
und sich dann die Änderungen ausgeben läßt, erhält man folgerichtig die
beiden äusseren Zeilen, während die mittlere gleichbleibt.

Tatsächlich geändert haben sich aber nur die Worte 'Fangen' und 'Braten'.

Das würde für dieses Beispiel bedeuten, daß dem (wie aufgebauten) Html-Formular
eine Information über die gewünschte Darstellung der Änderung mitgegeben werden
müsste (vor allem dann, wenn auch nach etwaigen kleineren Tippfehlern gesucht
werden soll).

Nach wie vor grübelnd

matho

danke für die Ausführung.

Ja, die Änderungen zu verfolgen würde die Sache (Zuordnung) vielleicht vereinfachen, die Daten werden jedoch per HTML-Formular eingegeben...

Ansonsten können wir ja vielleicht mal andersherum drangehen:
Wie wäre denn eine geeignete Darstellung der Veränderungen? Ausgangsbasis ist dabei ein Artikel zur Online-Präsentation, alo Überschrift, ev. Teasertext, und dann (in Relation zu Printmedien-Texten) viele kurze Absätze, zum Teil mit unterüberschriften, dazu Listen, Tabellen und Bilder und Lins natürlich.

Basti

ja, da sind wir uns einig, die Wahl der Programmiersprache ist zunächst nebensächlich, das
hattest Du ja selbst schon gesagt, und ich hab Dir eigentlich bloß zugestimmt.
Ich hatte das nun in python gemacht, weil ich annahm, daß auch jemand, der damit gar nicht
umgeht, das erstmal ohne grosse Worte verstehn kann.
Das script sucht nach möglichst langen Übereinstimmungen der beiden strings, und das tut es
auf etwas 'unsaubere' Art: es benutzt dazu einfach Ausnahmen:

Die Zeilen in der inneren while-Schleife:

             try:
                 i = index(s2, s1[a:o])
                 ve = [i, a, len(s1[a:o]), s1[a:o]]
             except:
                 s = s1[a:o-1]
 

heißen schlicht nichts anderes als:
Versuche, in string s2 bei wachsendem o fündig zu werden - wenn das nicht mehr
klappt (except), nimm den letzen gültigen Treffer - s = s1[a:o-1]

ve ist quasi eine Rückversicherung, falls nämlich beide strings von einer
beliebigen stelle bis zum Ende gleich sind, wird ja keine exception ausgelöst,
obwohl etwas gefunden wurde - deshalb meinte ich: 'unsauber'....

Also schon in etwa Dein Vorschlag, erst mal nach den grösseren Einheiten zu
schauen, mit dem Unterschied, daß ich Einheit als tatsächlich identisch
angenommen habe.

Aber das ist zunächst nicht wichtig, ich wollte lediglich aufzeigen,
wie man sich so einem Problem im ersten Schritt nähern könnte.

Im Zuge dieser Annäherung bin ich dann auf ein paar Sachen gekommen, bei denen ich,
wie gesagt, momentan nicht so recht wüsste, wie man damit umzugehen hat.

Da wären zB. doppelte Vorkommen eines substrings in beiden strings, bei denen sich
während einer Änderung beide Positionen gleichzeitig geändert haben.
So ein Fall könnte zB. relativ leicht eintreten bei einer Besprechung eines
Zitats, das halt des öfteren in verschiednen Kontexten wiederholt wird.

Desweiteren könnte ich nicht behaupten, einen irgendwie sinnvollen Begriff einer
möglichen Klassifizierung von Stringunterschieden zu haben. Ich empfinde das Thema
als schon ziemlich kompliziert.

Ich war zwischenzeitlich auf die Idee verfallen, texte und deren Änderungen in
einer spezifischen Umgebung stattfinden zu lassen, wo beispielsweise die
Möglichkeit bestünde, sämtliche Editorereignisse aufzuzeichnen, um sodann
die jeweiligen Änderungen mit einer Kennmarke zu versehen - so in dem Stil:
dieser substring wurde durch ein 'cut' entfernt, durch dieses und jenes 'paste'
geändert, und dann durch ein weiteres 'paste' wieder eingefügt, wobei gleichzeitig
ein andrer substring (teilweise) überschrieben wurde... uswusfetcpp.....
Aber das ist natürlich käse. Zum einen wär das schon ziemlich hirnverschwurbelnd,
zum andern hätte man dann zwar ein hübsche Sammlung der stattgehabten Änderungen,
aber die wären zum Zweck der Darstellung größtenteils überflüssig (wenn nicht gar
hinderlich), weil man ja tatsächlich "nur" die Änderungen von Anfangszustand zum
relativen Endzustand haben möchte. Und damit wär man wieder so klug wie zuvor,
soll heißen - in meinem Fall - eher weniger.

Natürlich gibt's ne ganze Menge intressanter Sachen im Umfeld dieses Problems -
Wenn du mal unterm Stichwort 'relevanz' ein bißchen rumsuchst, wirst Du sehr spannende
und schlaue Sachen entdecken (wenn's Dich intressiert, kann ich Dir auch ein paar links
posten). Allerdings ist mir nichts bekannt, das mich jetzt bei diesem konkreten
Problem entscheidend weiterbringen täte.

Im Falle der einfachen Einfügung (Bsp. G_1N) hat man ja das gewünschte Ergebnis
recht leicht, aber das ja eben ein sehr spezieller Fall.
Was mir fehlt, ist, ich beginnne mich zu wiederholen, eine einigermaßen
schlüssige Vorstellung der Klassifizierung der möglichen Unterschiede.

gruß

matho

@st2: Python, nicht Perl...

@matho:
Ich hab mir dein Posting jetzt länger nicht angeschaut, weil ich nicht an deinen Code wollte. Jetzt hab ich ihn mir doch mal genauer angesehen und es gibt für mich einfach zu viele Stellen, wo ich mir zusammenreimen müsste, was da genau passiert, etwas, das du dir vielleicht unschwer vorstellen kannst, weil du mit der Semantik ja vertraut bist.

Aber du schreibst selbst, dass die Programmiertechnik (womit du, wenn ich dich richtig verstehe eben das Umsetzen in eine bestimmte Programmiersprache meinst) hier erstmal nebensächlich ist und insofern bitte ich dich, einfach mit Worten zu beschreiben, was dein Vorgehen ist.

Natürlich spielt die Sprache aber dennoch eine Rolle, da sie die Werkzeuge zur Verfügung stellt und da lohnt es natürlich zu schauen: Was gibt es schon, was muss ich selber machen.

Basti

ich denke, es geht weniger um ein programmiertechnisches Problem,
als vielmehr um ein logisches (zumindest soweit ich's momentan begreife).
Zunächst einmal könnte man ja sagen: suche alle substrings, die in
beiden strings identisch sind.
Wenn die Identitaeten gefunden sind, vergleiche die jeweils wieder mit
den beiden Eingabestrings, und pinsel alles, das nicht übereinstimmt, bunt an -
im ersten string lila, im zwoten tschidscheringrün.
Das kann man mit ein paar Schleifen machen, mit Rekursionen, unter
Zuhilfenahme von Stringfunktionen oder regexes, oder von allem etwas,
ad libitum.
Nun gibt es aber diverse Arten denkbarer Unterschiede <=> Gleichheiten.
In Deinem Beispiel geht es um Einfügungen. Möglich sind aber auch zB.
Verdopplungen (oder auch mehrfache Wiederholungen) oder, wie bereits
erwähnt, Umstellungen, oder Kombinationen aus allem.
Während der Fall der einfachen Einfügung relativ leicht zu behandeln ist,
(im folgenden der Vergleich von a und b), ist der Vergleich
von c und d schon etwas unklarer. Ich habe da den substring Ubbu_ubbu,
gemeinerweise in beiden zu vergleichenden strings doppelt vorkommend.
Was ist nun unter 'Unterschied' zu verstehn? Das hängt, soweit ich das
sehn kann, davon ab, was man unter 'Unterschied' verstehn möchte bzw. in
Abhängigkeit der jeweiligen Aufgabenstellung verstehen muß/soll.

Ich habe das folgende Beispiel in python gemacht, einfach deshalb,
weil mir a) php nicht so geläufig ist, und b) python-scripts beinah wie
pseudo-code gelesen werden können (wenn man sich python nicht runterladen
möchte und einfach ausprobieren). Ich denke, Du wirst damit keine
Verständnisschwierigkeiten haben:

# coding: utf-8
 from string import *
 
 a = """
     Aber das währe doch nicht nötig gewesen.
     Es ist nämlich so, daß hier alles automatisch erledigt wird,
     aber das wissen Sie ja.
     """
 
 b = """   
     'Aber das wäre doch nicht nötig gewesen', antwortete er.
     'Es ist nämlich so, dass hier alles automatisch erledigt wird,
     aber das wissen Sie ja.'
 """
 
 ####################################
 
 c = """hjmmn,,.,....oo
     Aber das währe doch nicht nötig gewesen.
     Ubbu_ubbu
     Es ist nämlich so, SSSSSSSSSSSSdaß hier alles automatisch erledigt wird,
     aber das wissen Sie ja.Ubbu_ubbu
     nmoziooppp
     """
 
 d = """ qweeeeee  
     'XXXXXXnötig gewesen', antwortete er. nqwnenrtnnn65656Ubbu_ubbu5656
     'Es ist nämlich so, dass hier alles automatisch erledigt wird,
      aber das wissen Sie ja.'Aber hmurgknurgldas wäre doch nicht 
      8iiljk..%%%%%%%%%%Ubbu_ubbu%%%%%%%%%
 """
 
 ###################################################################
 
 def V(s1, s2, d = 0):   # d soll 0 oder -1 sein
     v, ve, a = [[0, 0, 0, '']], [0, 0, 0, ''], 0  
     if len(strip(s1)) <= len(strip(s2)): s1, s2 = map(strip, (s1, s2))
     else: s1, s2 = map(strip, (s2, s1))
     while a < len(s1):
         o, iq = a + 1, 0
         while o < len(s1):
             try:
                 i = index(s2, s1[a:o])
                 ve = [i, a, len(s1[a:o]), s1[a:o]]
             except:
                 s = s1[a:o-1]
                 for j in v:
                     if find(j[3], s) > d: iq = 1
                 if len(s) and not iq: v.append([i, a, len(s), s])                    
                 else: iq = 0
                 break
             o += 1
         a += 1
         if v[-1][0] < ve[0] and find(v[-1][3], ve[3]) < 0: v.append(ve)   
     return v[1:]
 
 def N(n):
     for i in range(len(n)):  #eine moegliche normalisierung, wenn keine         
         try:                 #vertauschungen vorliegen
             if n[i][0] > n[i+1][0]: n.remove(n[i])  
         except: pass 
     return n[n.index(min(n)):n.index(max(n))+1]
 
 print 'n___________________________G1_______________________________n'
 
 G1 = V(a, b)
 for i in G1: print i
 print 'n___________________________G1_N_____________________________n'
 
 G1_N = N(V(a, b))
 for i in G1_N: print i
 print 'n___________________________G2_______________________________n'
 
 G2 = V(c, d)
 G2.sort() # eine moeglichkeit, sich nen ueberblick zu verschaffen
 for i in G2: print i
 print 'n______________________aus die maus__________________________n'
 
 

Das erzeugt die Ausgabe:

 
 ___________________________G1_______________________________
 
 [1, 0, 11, 'Aber das wxe4']
 [18, 11, 1, 'h']
 [12, 12, 27, 're doch nicht nxf6tig gewesen']
 [55, 39, 6, '.n    ']
 [62, 45, 21, 'Es ist nxe4mlich so, da']
 [85, 67, 65, ' hier alles automatisch erledigt wird,n    aber das wissen Sie ja']
 
 ___________________________G1_N_____________________________
 
 [1, 0, 11, 'Aber das wxe4']
 [12, 12, 27, 're doch nicht nxf6tig gewesen']
 [55, 39, 6, '.n    ']
 [62, 45, 21, 'Es ist nxe4mlich so, da']
 [85, 67, 65, ' hier alles automatisch erledigt wird,n    aber das wissen Sie ja']
 
 ___________________________G2_______________________________
 
 [10, 15, 5, 'n    ']
 [10, 60, 5, 'n    ']
 [10, 74, 5, 'n    ']
 [22, 4, 1, 'n']
 [22, 46, 13, 'nxf6tig gewesen']
 [36, 5, 1, ',']
 [36, 6, 1, ',']
 [36, 8, 1, ',']
 [42, 13, 1, 'o']
 [42, 14, 1, 'o']
 [51, 7, 1, '.']
 [51, 12, 1, '.']
 [51, 59, 1, '.']
 [69, 65, 9, 'Ubbu_ubbu']
 [69, 179, 9, 'Ubbu_ubbu']
 [88, 79, 19, 'Es ist nxe4mlich so, ']
 [93, 44, 3, 't n']
 [97, 2, 1, 'm']
 [97, 3, 1, 'm']
 [97, 194, 1, 'm']
 [101, 0, 1, 'h']
 [101, 31, 1, 'h']
 [111, 113, 43, ' hier alles automatisch erledigt wird,n    ']
 [151, 152, 27, '    aber das wissen Sie ja.']
 [156, 21, 9, 'ber das w']
 [170, 97, 2, ' S']
 [175, 1, 1, 'j']
 [179, 20, 5, 'Aber ']
 [195, 25, 6, 'das wxe4']
 [201, 32, 14, 're doch nicht ']
 [227, 9, 2, '..']
 [227, 10, 2, '..']
 [227, 11, 2, '..']
 
 ______________________aus die maus__________________________
 
 
 

Aufgelistet werden die beiden offsets, die Länge des gemeinsamen substrings,
und eben jenner.
Wie Du in Liste G2 unter zB. den Einträgen Ubbu_ubbu sehn kannst, habe ich
jetzt nur nach dem niedrigsten index im zwoten string suchen lassen,
eben aus oben erwähntem Grund: wenn man auch nach andern indices sucht,
welche Änderung im zwoten string wäre welcher Stelle im ersten string
zuzuordnen? Und daraus ergibt sich die Frage: Wenn verschiedene Änderungen
vorliegen, welche ist bezüglich des Originals einerseits und im Vergleich
zueinander andrerseits als Änderung aufzufassen, und welche 'Änderung' ist
gar keine, sondern eigentlich 'gleichgeblieben'.
Vermutlich sollte man einen 'willkürlich' festzusetzenden Bezugspunkt wählen,
an dem dann die anderen Punkte nach Bedarf gemessen werden.

Naja, vielleicht bringt's Dich ja auf ein paar klügere Gedanken als mich.

gruß

matho

Wenn die Ähnlichkeits-Routine gut ist, dann kann man hier schon die beiden letzteren Absatz-Klassen (gelöschte und hinzugefügte) entsprechend verbuchen, aber das dürfte garnicht so einfach sein...

Die zusammengehörigen, also ähnlichen, aber dennoch unterschiedlichen Absätze knöpft man sich dann nach dem gleichen Muster satzweise vor usw.

Basti

der Sinn ist es, wie bei einem Wiki Änderungen an Textdokumenten verfolgen zu können. Schau mal z.B. hier:

http://alt.thetinfoilhat.com/tiki-pageh … mp;diff=20

Dort wird eine Version x einer Page mit der aktuellen Version verglichen bzw. eben nur gegenübergestellt.

Hier wäre es ja zum Bep. schön, wenn die einzelnen Abschnitte parallel dargestellt werden würden. Dann sehe ich im Block "News" die zeile "The demo site is here help you.", wobei in der aktuellen Version das fehlende "to" ergänzt wurde. Nun wär's ja nett, wenn dieses einfach grau hinterlegt wäre, damit der verantwortliche Redakteur nicht lange suchen muss, was denn nun verändert wurde.

Hier:

http://alt.thetinfoilhat.com/tiki-pageh … p;diff2=20

ist sowas ja ansatzweise verwirklicht, wobei es ja eben nett wäre, die beiden Ansichten in eine zu bringen.

Und nun zu deinem Ansatz:
Ich seh da eben einige Schwierigkeiten.
Nehemen wir mal an, wir bearbeiten so und zwar Buchstabenweise meine beiden Beispieltexte oben:

Text A:
"Das währe aber nicht nötig gewesen. Es ist nämlich so, dass hier alles automatisch erledigt wird aber das wissen Sie ja"

Text B:
"Aber das wäre doch nicht nötig gewesen", antwortete er. "Es ist nämlich so, dass hier alles automatisch erledigt wird, aber das wissen Sie ja."

"D" und "A" sind unterschiedlich. Weder kann in Text A ein "A" gefunden wurden, noch konnte in Text B ein "D" gefunden werden.

Folglich wurde das "A" hinzugefügt und das "D" entfernt.

Wie weiter? Schauen wir mal, ob noch mehr außer dem "D" entfernt wurde:

Suche "a" in Text B usw. Das geht ganz gut bis zu dem falschen "h" in "währe", denn dieses wird nun in dem "nicht" von Text B gefunden. das folgende "r" findet er dann in "antwortete" und schon haben wir den Faden verloren.

Das ganze mit Wörtern:
"Das" != "Aber", "währe" fehlt, "aber" fehlt, "nicht", "nötig" und "gewesen" findet er dann exakt und den Rest auch. Jetzt könnte man ja quasi die gefundenen Übereinstimmungen mal "weglegen" und nur noch den Rest untersuchen:

"Das währe aber"

und:

"Aber das wäre doch", "antwortete er" und "aber das wissen Sie ja"

Klar: Keine Wortübereinstimmungen: Ersteres wurde gelöscht, die 3 Teile in Text B eingefügt.

...Schonmal nicht schlecht, wobei hier z.B. die Satzzeichen ignoriert wurden und eigentlich ist das so übersichtlicher, als wenn z.B. das "D" von "Das" und das "h" von "währe" hervorgehoben würden.

..mal sehen..

Basti

Ich könnte mir das nach einem solchen Schema vorstellen:

Immer einen Buchstaben (wenn es Buchstaben-genau sein soll, ansonsten z. B. auch immer ein Wort) vergleichen. Wenn es gleich ist, ist natürlich alles ok. Wenn es einen Unterschied gibt, müsste man es einfach markieren.

Bei einem Unterschied muss dann (wahrscheinlich bei beiden Texten) solange gesucht werden, bis die Fortsetzung der Zeichenkette des einen im anderen Text wieder auftaucht. Damit bekommt man heraus, ob etwas hinzugefügt wurde.

Wenn etwas weggenommen wurde, bekommt man es durch den Gegenvergleich heraus. <-- doof ausgedrückt. Nochmal: Wenn in Text 1 etwas weggenommen wurde und das neue "Text 2" heißt, ist das so, als ob in "Text 2" etwas dazugekommen ist und das neue "Text 1" heißt. Das meine ich mit andersherum.

Vielleicht hilft das schon? Ich sehe zwar nicht so ganz den Sinn, aber das macht ja nichts <img src="/forum/images/graemlins/smile.gif" alt="" />

Mamphil

Gegeben sind also zwei Texte und die Info: Text B ist aus Text A entstanden.

Ich hab so keinen rechten Ansatz...

Kein Problem wäre wohl folgendes:
- gleiche Wortketten identifizieren;
- kleine Änderungen innerhalb einer Wortkette identifizieren (Rechtschreibfehler) - wobei das schon wieder einige Probleme aufwirft;
- herausgenommene Wörter "finden";
- ...?

Basti

hat jemand von euch Lust auf folgendes kleines Projekt:

Es geht darum, eine Funktion zu erstellen, die zwei Versionen eines Textes vergleicht und die Änderungen ausspuckt.

Das ganze soll dann in PHP programmiert werden und so ausgegeben werden, dass die beiden Texte auf einer HTML-Seite in je einer (Tabellen-)Spalte nebeneinander stehen und links in der alten Version alle gelöschten Teile farbig hinterlegt sind und rechts entsprechend die hinzugefügten Teile hinterlegt sind. Vielleicht könnte man dann noch bei jedem Absatz eine neue Tabellenzeile einfügen, so, dass die Texte weitgehend parallel dargestellt werden.

Mal ein beipiel:

TextAlt:
"Das währe aber nicht nötig gewesen. Es ist nämlich so, dass hier alles automatisch erledigt wird aber das wissen Sie ja"

TextNeu
"Aber das wäre doch nicht nötig gewesen", antwortete er. "Es ist nämlich so, dass hier alles automatisch erledigt wird, aber das wissen Sie ja."

Ein wünschenswertes Erbenis wäre dann als Anzeige des alten Textes:
"Das währe aber nicht nötig gewesen. Es ist nämlich so, dass hier alles automatisch erledigt wird aber das wissen Sie ja"

Und der als neuer Text käme:
"Aber das wäre doch nicht nötig gewesen", antwortete er. "Es ist nämlich so, dass hier alles automatisch erledigt wird, aber das wissen Sie ja."

..oder vielleicht gibt es noch tauglichere Darstellungsformen, um Veränderung gut erfassen zu können.

Basti