Entwickler-Ecke

Delphi Language (Object-Pascal) / CLX - Ähnlichkeit zweier Strings ermitteln + sinnvoll antworten


galagher - Do 07.08.08 00:44
Titel: Ähnlichkeit zweier Strings ermitteln + sinnvoll antworten
Hallo!

Ich habe eine Liste, zB. wie diese hier. Man soll eine Frage eingeben und das Programm soll aus dieser Frage die richtige (sinnvollste) Antwort geben. So ist zB. auf die Frage "wann wurde Karl Wilhelm Reinmuth geboren?" klar, dass die letzte Antwort am Besten passt:

Delphi-Quelltext
1:
2:
3:
Karl Wilhelm Reinmuth am Observatorium auf dem Königstuhl bei Heidelberg tätig
Karl Wilhelm Reinmuth war ein deutscher Astronom
Karl Wilhelm Reinmuth wurde am 4. April 1892 geboren und starb am 6. Mai 1979

Also habe ich mir gedacht, ich stelle den Items eine Zahl voran, die eine "Ähnlichkeitsfunktion" ermittelt, sortiere die Liste und gebe die Zeile mit der höchsten Zahl aus. Dachte ich. Funktioniert auch rein technisch, aber nicht im Sinne einer korrekten Antwort! So ergibt:

Delphi-Quelltext
1:
2:
3:
4:
000 Merope ist ein Asteroid des Hauptgürtels, der am 16. September 1925 vom deutschen Astronom Karl Wilhelm Reinmuth in Heidelberg entdeckt wurde
005 Karl Wilhelm Reinmuth war ein deutscher Astronom
020 Karl Wilhelm Reinmuth war am Observatorium auf dem Königstuhl bei Heidelberg tätig
024 Karl Wilhelm Reinmuth wurde am 4. April 1892 geboren und starb am 6. Mai 1979

... ist ok.

Aber "wo ist Karl Marx begraben?":

Delphi-Quelltext
1:
2:
000 Karl Marx ist in London begraben
022 Karl Marx stammt aus Trier

... ist leider absolut nicht richtig. Wieso funktioniert es das eine Mal, das andere Mal nicht?

Dazu muss ich sagen, dass diese Listen unterschiedlich viele Zeilen enthalten können und bei der Auswertung der Frage Gross-/Kleinschreibung berücksichtigt wird, Satzteichen sind irrelevant.

Hier noch die (mit Google gefundene) Funktion Similar, die auf Ähnlichkeiten prüft:

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
function Similar(Str1, Str2: String): Integer;
VAR treffer, p1, p2, l1, l2, pt, diff: INTEGER;
     hstr: STRING;
    test: ARRAY [1..255] OF BOOLEAN;
BEGIN
 {Hinzugefügt: Bei nur 1 Wort das 1. Zeichen des Strings als 2. Wort verwenden}
 if Pos(' ', Str1) = 0 then Str1 := Str1+' '+Str1[1];
 if Pos(' ', Str2) = 0 then Str2 := Str2+' '+Str2[1];

 IF Length(Str1) < Length(Str2) THEN BEGIN
  hstr:= Str2;  Str2:= Str1;  Str1:= hstr;
 END;
 l1:= Length (Str1);
 l2:= Length (Str2);
 p1:= 1;  p2:= 1;  treffer:= 0;
 diff:= Max (l1, l2) DIV 3 + ABS (l1 - l2);
 FOR pt:= 1 TO l1 DO  test[pt]:= FALSE;
 REPEAT
  IF NOT (test[p1]) THEN BEGIN
   IF (Str1[p1] = Str2[p2]) AND (ABS(p1-p2) <= diff) THEN BEGIN
    test[p1]:= TRUE;
    treffer:= Succ(treffer);
    p1:= Succ(p1);
    p2:= Succ(p2);
    IF p1 > l1 THEN p1:= 1;
   END ELSE BEGIN
    test[p1]:= FALSE;
    p1:= Succ(p1);
    IF p1 > Length(Str1) THEN BEGIN
     WHILE (p1 > 1) AND NOT(test[p1]) DO  p1:= Pred(p1);
     p2:= Succ(p2)
    END;
   END;
  END ELSE BEGIN
   p1:= Succ(p1);
   IF p1 > Length(Str1) THEN BEGIN
    REPEAT
     p1:= Pred(p1);
    UNTIL (p1 = 1) OR test[p1];
    p2:= Succ(p2)
   END;
  END;
 UNTIL p2 > Length(Str2);
 Result := 100 * treffer DIV l1;
end;

Kurz gefragt: Wie macht man sowas richtig?


mkinzler - Do 07.08.08 07:37

Es gibt Methoden Ähnlichkeiten zwischen Strings zu ermitteln. Such mal nach Soundex oder Levenshtein


Gausi - Do 07.08.08 08:17

Ich hab da mal was vorbereitet... *klick* [http://www.delphi-forum.de/topic_ApproxStrUtils_83298.html]. Aber ich bin mir nicht sicher, ob eine rein syntaktische Untersuchung der Strings bei so etwas sinnvoll ist. :nixweiss:


galagher - Do 07.08.08 11:26

Erstmal danke für das Interesse!

Ich habe mir eine "Sonstige-Worte-Liste" geschrieben, in der zB. der/die/das/wo/wann usw. vorkommt. Diese Worte filtere ich aus der Eingabe heraus, dann vergleiche ich das 1. Wort der Eingabe+die aktuelle Zeile+das_letzte Wort der Eingabe mit der Eingabe - und erreiche so die bisher besten Ergebnisse. Keine Ahnung, warum das so ist!

Die Antworten sind alle ähnlich aufgebaut: Alle enthalten mindestens ein Substantiv und alle geben in mehr oder weniger knappen Worten sowas wie Allgemeinwissen wieder. Je mehr Substantive, desto besser die Ergebnisse.

user profile iconGausi hat folgendes geschrieben:
Aber ich bin mir nicht sicher, ob eine rein syntaktische Untersuchung der Strings bei so etwas sinnvoll ist. :nixweiss:

Klar wäre es besser, die Bedeutung der einzelnen Worte, womöglich in ihrem Kontext, zu ermitteln und auf dieser Basis zu prüfen. Aber das wäre ja wie ein Verstehen des Satzes und damit eine echte KI.
Wenn du sowas drauf hast, ich könnt's zufälllig grad gut gebrauchen! :mrgreen:
Aber im Ernst: Das übersteigt meine Kenntnisse! Und selbst wenn: Wie lange würde es dann dauern, bis das Programm einen Satz ermittelt hat?