Autor Beitrag
galagher
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 2510
Erhaltene Danke: 44

Windows 10 Home
Delphi 10.1 Starter, Lazarus 2.0.6
BeitragVerfasst: Do 11.07.13 20:39 
Hallo!

Ich suche nach einer Möglichkeit, einen (Teil-)String in einem anderen String zu finden, wobei ich vorher aber nicht genau weiss, wonach ich eigentlich suche. So kann es beispielsweise 'was ist Mensch ärgere dich nicht' und 'Mensch ärgere dich nicht ist ein Brettspiel, das mit einem Würfel gespielt wird' sein, der ähnliche (hier konkret der identische) Teilstring wäre also 'Mensch ärgere dich nicht', daher: Treffer.

Ich kann dabei aber weder Pos noch irgendeine StringCompare-Funktion (zB. Levenshtein www.delphipraxis.net...nshtein-distanz.html) benutzen, da ich nie weiss, wie hoch die Übereinstimmung als Integer sein wird.

Die beiden Strings können auch unterschiedlich lang sein und bis auf einige wenige gleiche oder sehr ähnliche Wörter auch solche enthalten, die nur jeweils in dem einem String vokommen, im anderen jedoch nicht. Es geht im Prinzip darum, gewisse Wörter zu finden, die aber in den beiden Strings nicht unbedingt in der gleichen Reihenfolge vorkommen müssen.
So könnte der Stringvergleich auch lauten: 'was ist ein Brettspiel' - 'Mensch ärgere dich nicht ist ein Brettspiel, das mit einem Würfel gespielt wird'.

Auch sollen dabei ähnliche Wörter erkannt werden, zB. 'Brettspiel' - 'Brettpiele'

Also eine "(Teil-)String in String - (Teil-)String in (Teil-)String - String in String - String in (Teil-)String"-Suche. So in etwa...

Ich habe keinen Ansatz, wie ich das realisieren soll und bin daher für Konzepte dankbar!

lg
galagher

Moderiert von user profile iconMartok: Beiträge zusammengefasst

//Edit: habe da doch etwas gefunden: www.delphipraxis.net...stringvergleich.html
Wie soll ich aber wissen, ab welchem Prozentsatz "Bingo" ist? Kann ja wie gesagt völlig unterschiedlich sein.


Moderiert von user profile iconGausi: Topic aus Delphi Language (Object-Pascal) / CLX verschoben am Fr 12.07.2013 um 09:38

_________________
gedunstig war's - und fahle wornen zerschellten karsig im gestrock. oh graus, es gloomt der jabberwock - und die graisligen gulpen nurmen!
Tranx
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 648
Erhaltene Danke: 85

WIN 2000, WIN XP
D5 Prof
BeitragVerfasst: Do 11.07.13 22:09 
Als Ansatz würde ich einen mehrschichtigen Vergleich wählen.

1. Ebene: kompletter Text: Wenn dieser im zu vergleichenden String vorhanden ist -> 1000
2. Ebene: Einzelne Worte des Vergleichsstrings, wenn im zu vergleichenden String vorhanden, dann jeweils + 10
Sind alle Worte vorhanden, dann +100 zusätzlich
Sind die Reihenfolgen im zu vergleichenden String ebenfalls aufsteigend: + 100

Die erste Ebene kann mit Pos erledigt werden, die zweite Ebene mit einer Abfolge von Pos-Befehlen in einer Schleife. Als Ergebnis wäre dann eine Integer-Zahl auszugeben, welche durch ihre Größe den Grad der Übereinstimmung signalisiert.

Du müsstest dann Deinen Vergleichsstring vorher in einzelne Worte (Am Besten in eine Variable vom Typ TString) überführen. Als Worttrenner die üblichen Trenner (" ", ",", ";", ":", """, ".","!","?") wählen.

_________________
Toleranz ist eine Grundvoraussetzung für das Leben.
IhopeonlyReader
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 600
Erhaltene Danke: 23


Delphi 7 PE
BeitragVerfasst: Do 11.07.13 23:13 
Den zu suchenden String in "Wörter" aufteilen und diese einzeln suchen (evt Satzweise).. pro Übereinstimmung +1 (bei mehrfachen vorkommen auch nur +1) am ende durch die anzahl der wöter. -> prozentuale wiederfindung

_________________
Sucht "neueres" Delphi :D
Wer nicht brauch was er hat, brauch auch nicht was er nicht hat!
Mr_Emre_D
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 114
Erhaltene Danke: 14



BeitragVerfasst: Fr 12.07.13 07:56 
Mein erster Gedanke war, dass man den kürzeren String mit dem längeren xort und schaut, wie viele benachbarte Nullen sich bilden.
Man verschiebt den kürzeren String bis man am Ende angelangt ist und merkt sich bis dahin die maximale 0-Folge.

Beispiel:
X: "ABC"
Y: "AB"

Y (kürzer) gexort mit X würde ergeben 00"C" (max Nullfolge atm = 2)
(verschoben:
"ABC"
"AB" (xor)
= "ABC")

Edit: Mit diesem Ansatz findest du die "interessanten" Stellen. Die müsste man eig. noch genauer analysieren.

Edit2: Stimmt, ist nutzlos, wenn die Reihenfolge egal sein soll..


Zuletzt bearbeitet von Mr_Emre_D am Fr 12.07.13 09:01, insgesamt 1-mal bearbeitet
Tranx
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 648
Erhaltene Danke: 85

WIN 2000, WIN XP
D5 Prof
BeitragVerfasst: Fr 12.07.13 08:18 
user profile iconMr_Emre_D hat folgendes geschrieben Zum zitierten Posting springen:
Mein erster Gedanke war, dass man den kürzeren String mit dem längeren xort und schaut, wie viele benachbarte Nullen sich bilden.
Man verschiebt den kürzeren String bis man am Ende angelangt ist und merkt sich bis dahin die maximale 0-Folge.

Beispiel:
X: "ABC"
Y: "AB"

Y (kürzer) gexort mit X würde ergeben 00"C" (max Nullfolge atm = 2)
(verschoben:
"ABC"
"AB" (xor)
= "ABC")

Edit: Mit diesem Ansatz findest du die "interessanten" Stellen. Die müsste man eig. noch genauer analysieren.


Das mag vielleicht funktionieren, aber eigentlich funktioniert der Operator XOR nur mit Integer-Variablen, nicht mit Strings. Das hieße, Du müsstest die einzelnen Strings in einzelne Zeichen aufteilen und diese dann vergleichen. Allerdigns ist da noch Groß- und Kleinschreibung. Allerdings macht Pos ja schon das, was Du beschreibst, denn es gibt das erste Vorkommen vom zu suchenden String im Suchstring an. Ist der zu suchende String nicht im Suchstring, gibt die Funktion 0 aus. Und Du kannst, wenn Du willst, sowohl Groß-Kleinschreibung beachten, oder auch nicht:


ausblenden Delphi-Quelltext
1:
2:
3:
4:
    TextVar := 'Ein etwas längerer Text, der zu durchsuchen ist.');
    SuchText := 'Der';
    x := Pos(Suchtext, TextVar); // = 0, weil "Der" nicht vorhanden ist.
    x := Pos(Uppercase(Suchtext),Uppercase(TextVar)); // >0, weil ohne Groß-/Kleinschreibung getestet wird.

_________________
Toleranz ist eine Grundvoraussetzung für das Leben.
jasocul
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 6386
Erhaltene Danke: 146

Windows 7 + Windows 10
Sydney Prof + CE
BeitragVerfasst: Fr 12.07.13 08:27 
user profile icongalagher hat folgendes geschrieben Zum zitierten Posting springen:

Auch sollen dabei ähnliche Wörter erkannt werden, zB. 'Brettspiel' - 'Brettpiele'

Dafür musst du erstmal definieren, was "ähnlich" bedeutet.
In deinem Beispiel ist das schon nicht mehr simpel. Brettspiel ist z.B. über Pos nich in Brettpiele enthalten, weil im zweiten Wort das "s" fehlt. Selbst ein Klangvergleich der Wörter würde hier wohl keinen Treffer geben, da das "s" meines Wissens wichtig wäre.
Tippfehler, wie in deinem Beispiel, sind mMn nur schwer zu analysieren.

Sollte es hier aber ein Tippfehler von dir sein, kannst du natürlich jedes Wort des einen Satzes gegen jedes Wort des anderen Satzes prüfen und umgekehrt. Wobei der Plural damit nicht komplett abgebildet werden kann (Fall -> Fälle, etc). Dabei kann man natürlich auch in eine "Falle" tappen. :lol:

Was dir vielleicht helfen kann ist SoundEx.
jaenicke
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 19272
Erhaltene Danke: 1740

W11 x64 (Chrome, Edge)
Delphi 11 Pro, Oxygene, C# (VS 2022), JS/HTML, Java (NB), PHP, Lazarus
BeitragVerfasst: Fr 12.07.13 08:46 
user profile iconjasocul hat folgendes geschrieben Zum zitierten Posting springen:
Tippfehler, wie in deinem Beispiel, sind mMn nur schwer zu analysieren.
Sind sie weniger solange man sich nicht komplett vertippt, ich habe das schon für eine Skriptsprache implementiert. Der Interpreter schlägt als Ausgabe vor was gemeint gewesen sein könnte, wenn man sich vertippt. Eine Möglichkeit dafür ist die schon genannte Levenshtein Distanz.

In diesem Fall wird die Analyse auf mehreren Ebenen stattfinden müssen. Eine relativ einfache Möglichkeit wäre eine Liste der Vorkommen der einzelnen Worte zu erstellen und dann auf alle Fundstellen und den der Länge des Suchtextes entsprechenden Teil des Textes an der Stelle die Levenshtein Distanz zu berechnen.

Auf die Weise sollten brauchbare Ergebnisse herauskommen. Ist im Suchtext nur ein Wort drin, würde ich alle Wörter mit der Levenshtein Distanz abgleichen.
Mr_Emre_D
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 114
Erhaltene Danke: 14



BeitragVerfasst: Fr 12.07.13 09:26 
Also mein Ansatz zuvor ist doch nicht ganz falsch - er ist jedoch nicht die optimalste Lösung (Laufzeitverhalten!)!

ausblenden volle Höhe 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:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
type
  TPointArray = Array of TPoint;

function demo(const A: Stringconst B: String): TPointArray;
var
  pShorterStr : PString;
  pLongerStr  : PString;
  i, j        : Integer;
  zeroBuf     : Array of Integer;

  function getMaxAdjacentZeroes(): Integer;
  var
    i, idx: Integer;
  begin
    Result := 0;
    idx := 0;
    for i := 0 to High(zeroBuf) do
      if (zeroBuf[i] <> 0then
      begin
        if idx <> -1 then
        begin
          if (i - idx) > Result then
            Result := i - idx;
          idx := -1;
        end;
      end else
        if idx = -1 then
          idx := i;
      if (idx <> -1and (i - idx > Result) then
        Result := i - idx;
  end;

  procedure add(const x, y: Integer);
  begin
    SetLength(Result, Length(Result) + 1);
    Result[High(Result)] := Point(x, y);
  end;

begin
  if Length(A) <= Length(B) then
  begin
    pShorterStr := @A;
    pLongerStr  := @B;
  end else
  begin
    pShorterStr := @A;
    pLongerStr  := @B;
  end;
  SetLength(zeroBuf, Length(pShorterStr^));
  for i := -Length(pShorterStr^) to Length(pLongerStr^) do
  begin
    for j := 1 to Length(pShorterStr^) do
      if i+j < 0 then
        zeroBuf[j-1] := -1
      else
        zeroBuf[j-1] := Ord(pShorterStr^[j]) xor Ord(pLongerStr^[i+j]);
    j := getMaxAdjacentZeroes();
    if (j > 0then
      add(i, j);
  end;
end;

var
  pa: TPointArray;
  i: Integer;

begin
  pa := demo(
    'was ist ein Brettspiel',
    'Mensch ärgere dich nicht ist ein Brettspiel, das mit einem Würfel gespielt wird');
  for i := 0 to High(pa) do
    writeln(pa[i].X, ' - ', pa[i].Y);
  readln;
end.


Die "demo" Funktion liefert mir ein Array mit Indizes und max. Übereinstimmung als Tupel:
ausblenden volle Höhe 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:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
-19 - 1
-14 - 1
-13 - 1
-10 - 1
-8 - 1
-7 - 1
-5 - 1
-4 - 1
-2 - 2
-1 - 1
1 - 1
2 - 1
3 - 1
4 - 1
6 - 1
7 - 1
8 - 1
9 - 1
10 - 1
11 - 1
12 - 1
13 - 1
15 - 1
16 - 1
17 - 2
20 - 1
21 - 19
22 - 1
24 - 1
25 - 1
26 - 1
27 - 1
29 - 1
30 - 1
31 - 1
33 - 1
35 - 1
36 - 1
37 - 1
39 - 1
41 - 1
42 - 1
43 - 2
45 - 5
46 - 1
47 - 1
48 - 1
49 - 1
50 - 1
51 - 5
53 - 1
54 - 1
55 - 1
57 - 1
58 - 1
59 - 1
61 - 1
62 - 1
63 - 1
64 - 1
66 - 1
67 - 2
71 - 1
72 - 1
74 - 1
75 - 1
76 - 1
77 - 1
78 - 1


Nehmen wir folgende Werte heraus: (-2, 2), (21, 19), (45, 5)
Beispiel: (21, 19)
Wenn wir den kürzeren String 'was ist ein Brettspiel' um 21 nach rechts verschieben
und unterhalb vom größeren String positionieren, finden wir 19 idente aufeinanderfolgende Zeichen =
ausblenden Quelltext
1:
2:
Mensch ärgere dich nicht ist ein Brettspiel, das *snip
                     was ist ein Brettspiel


Dh. man müsste jetzt nur noch mehr schauen, welche Worte in diesem Range entweder im längeren oder im kürzeren String vollkommen abgedeckt werden! Worte grenzen sich mit Leerzeichen und Satzzeichen (!.?;,:='") ab.
Dieser Test ist dann aber einfacher zu implementieren!

"was" zb wird nicht ganz abgedeckt, "ist" "ein" "Brettspiel" werden jedoch schon abgedeckt!
Gausi
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8535
Erhaltene Danke: 473

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: Fr 12.07.13 09:38 
Wenn ich dich richtig verstanden habe, dann ist der exakte Fall das "Longest Common Substring"-Problem. Wikipedia gibt da einen kleinen Einstieg.
Ob und wie man das auf "Longest Common Fuzzy Substring" erweitern kann, weiß ich nicht. Aber vielleicht hilft der Link ja beim Einlesen. :D

Edit: Link vergessen: en.wikipedia.org/wik...on_substring_problem

_________________
We are, we were and will not be.
galagher Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 2510
Erhaltene Danke: 44

Windows 10 Home
Delphi 10.1 Starter, Lazarus 2.0.6
BeitragVerfasst: Fr 12.07.13 16:50 
user profile iconjasocul hat folgendes geschrieben Zum zitierten Posting springen:
Tippfehler, wie in deinem Beispiel, sind mMn nur schwer zu analysieren.
Ja, das ist tatsächlich ein Tippfehler!

Das Ganze ist ein Chat-Programm, das die Benutzereingabe analysiert und möglichst passend antwortet. Klappt soweit ganz gut, ich möchte in die "Wissens-Datenliste" jedoch keine Sätze aufnehmen, die "ich", "dir", "mich", "dich" usw. enthalten. Solche Worte sind i.d.R. keine Bestandteile von Aussagen, die Fakten beschreiben. Im Satz "Mensch ärgere dich nicht ist ein [...]" kommt nun aber "dich" vor; das Spiel heisst nun einmal so. Dennoch ist es eine Aussage. Also ist es eine Ausname.

Danke für eure Lösungsansätze, für's Erste tut's der Levenshtein-Code, aber er ist eben nicht massgeschneidert für diese Aufgabe, also eventuell werde ich die eine oder andere Möglichkeit, die ihr mir hier vorgestellt habt, noch anwenden (wenn ich sie verstanden habe), oder ich bastle mir was Eigenes, das ist am Besten, weil ich es dann selbst erarbeitet und jedenfalls verstanden habe.
Mir schwebt so etwas wie eine Wortfolge-Prüfung vor: Zwei oder mehr Worte, die in beiden Strings direkt aufeinander folgen, sind dann ein Plus, ihr wisst, was ich meine.

-

Danke, user profile iconMartok, für's zusammenfassen, da habe ich mich verklickt!

_________________
gedunstig war's - und fahle wornen zerschellten karsig im gestrock. oh graus, es gloomt der jabberwock - und die graisligen gulpen nurmen!