Autor Beitrag
Gausi
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8548
Erhaltene Danke: 477

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: Di 19.07.05 15:31 
Normalerweise sucht man ja so als Delphi-Programmierer mit dem schönen Befehl pos o.Ä. nach Substrings in größeren Strings. Ist ja alles schön und gut.
Ich möchte jetzt aber eine gewisse Fehlertoleranz zulassen. GROß/kleinschreibung ignoriere ich schon, bevor ich groß rumerzähle, ein paar Beispiele:

Suchbegriff: REM
gewünschte Ergebnisse (z.B.): REM, R E M, R.E.M.
oder:
Herbert Grönemeyer -> Herbert Grönemeier, Herbert Groenemeyer,
Seeed -> Seed
Die Ärzte -> Die Aerzte, Ärzte, Aerzte
Die Toten Hosen -> Die Roten Rosen (!), Hosen, Toten Hosen
Und weiter gehts mit AC/DC, A-Ha, A-Teens, BroSis, B3, Guns 'N Roses, H-Blockx,...

Ich möchte also nicht nur, dass eine exakte Übereinstimmung gefunden wird, sondern auch, dass "ähnliche" Strings gefunden werden - was auch immer ähnlich genau bedeutet.

Vieles würde man mit viel Gewalt hinkriegen (alle Leer/Sonderzeichen per Stringreplace durch '' ersetzen), aber für elegant oder effizient halte ich das nicht. Und kleine Rechtschreibfehler (Alanis Mor(r)is(s)et(t)e, Grönemei(?)er, Mittermai(?)er, H-Blocks(?), Se(e)ed) bekommt man damit auch nicht weg.

Jemand ne Idee?

_________________
We are, we were and will not be.
jasocul
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 6393
Erhaltene Danke: 147

Windows 7 + Windows 10
Sydney Prof + CE
BeitragVerfasst: Di 19.07.05 15:40 
Hi Gausi,
in Datenbanke gibt es doch phonetische Suchfunktionen. Das geht doch ganz grob in die Richtung. Geh doch mal auf die Suche, ob es dazu entsprechende Algos gibt.
retnyg
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2754

SNES, GB, GBA, CPC, A500, 486/66, P4/3.0HT: NintendOS, AmigaOS, DoS
Delphi 5, Delphi 7
BeitragVerfasst: Di 19.07.05 15:55 
nur ne idee : lies jedes wort als ganzes und mach jeweils einen vergleich. wenn z.b. 80% der zeichen ['a'..'z'] übereinstimmen, ist es ein treffer, sonst nicht. punkte und sonderzeichen sollten also ausgefiltert werden

_________________
es gibt leute, die sind genetisch nicht zum programmieren geschaffen.
in der regel haben diese leute die regel...
Gausi Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8548
Erhaltene Danke: 477

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: Di 19.07.05 16:10 
@Jasocul: Punkt1: Scheint sehr kompliziert zu sein, da die Strings wohl in einzelne Laute zerlegt werden müssen. Da ich aufgrund der Anwendung auch mit mehreren Sprachen und vielen Sonderfällen zu tun habe, kaum durchführbar - fürchte ich. Oder zumindest unangemessener Aufwand.

@retnyg:
ausblenden Quelltext
1:
2:
3:
A e r z t e
| | | | | |
Ä r z t e
Da sind genau Null Zeichen gleich, der Rest total unterschiedlich. Oder wie meintest du das? Gut bei
ausblenden Quelltext
1:
2:
A C(-)D C
A C...D C
würds funktionieren...

Über phonetische Suche bin ich aber auf das und das gestoßen. Könnte interessant sein...

_________________
We are, we were and will not be.
ManuelGS
ontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic starofftopic star
Beiträge: 173

Win XP HE, Suse Linux
D6, D7, D2005 Personal
BeitragVerfasst: Di 19.07.05 16:17 
Deinen Suchstring aufsplitten!
Z.B. alá Dos nach "Gr*nem*er" suchen lassen, d.h.:
1. nach "gr" (kleinGROSS hast du ja schon...)
2. von da aus nach "nem"
3. und schließlich nach "er"

String zusammensetzen (von "gr" bis "er"). Der gefundene String darf nicht größer als length(Gr*nem*er)+x sein. x ist deine "Fehlertoleranz" in Zeichenanzahl.

Wie du auf die * kommst...nach "ae", "ä", "th", "q" etc. suchen und mit "*" ersetzen oder gleich in einem Array speichern. (Erst nach den größeren Strings suchen ("th" vor "t").

Wäre jetzt mal mein Ansatz...
Wenn eine Band allerdings "Skrhtäßth" heißt, taugt das ganze allerdings nichts...

_________________
"Leben ist gänzlich Bühne und Spiel; so lerne denn spielen
und entsage dem Ernst - oder erdulde das Leid." - Palladas von Alexandria
jasocul
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 6393
Erhaltene Danke: 147

Windows 7 + Windows 10
Sydney Prof + CE
BeitragVerfasst: Di 19.07.05 16:25 
Das mit den Datenbanken (SoundEx) sollte auch nur ein Gedankenansatz sein.
Ich glaube, da gibt es ein paar Standard-Ansätze iirc:

Alle Umlaute in normale Vokale wandeln. (Ä -> A)
Vokalfolgen auf den führenden Vokal reduzieren. (ae -> a)
Doppelkonsonanten auf einen reduzieren, (sch -> s, th -> t, ck -> k, ch -> k, ...)
Lautverschiebungen anpassen (Dehnungslaute u.ä.)
Berücksichtigung der üblichen Tippfehler (da wird es dann aber wohl richtig heftig)

Da wirst du dann wohl ein paar Umwandlungstabellen pflegen müssen. :roll:

Einige Dinge dürften sprachenspezifisch sein.
Gausi Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8548
Erhaltene Danke: 477

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: Di 19.07.05 16:47 
user profile iconjasocul hat folgendes geschrieben:
Berücksichtigung der üblichen Tippfehler (da wird es dann aber wohl richtig heftig)
Deswegen hab ich ja den Thread aufgemacht :lol:

user profile iconjasocul hat folgendes geschrieben:
Da wirst du dann wohl ein paar Umwandlungstabellen pflegen müssen.
Und genau das möchte ich nach Möglichkeit auch vermeiden. Ich bin kein Phonetik-Experte, und das ist mir - sorry - so ohne weiteres zu schwammig. Und Bücher über Phonetik werde ich deswegen nicht durchackern.

@ManuelGS: Ist natürlich ne Idee, die mir im Wesentlichen auch schon gekommen ist, aber das halte das irgendwie für Frickelei :nixweiss:

_________________
We are, we were and will not be.
jasocul
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 6393
Erhaltene Danke: 147

Windows 7 + Windows 10
Sydney Prof + CE
BeitragVerfasst: Di 19.07.05 16:56 
Vielleicht geht folgender Ansatz:
Erstmal alle Konsonanten durch 'X' ersetzen und alle Vokale durch 'A'.
Danach alle Doppelvokale und Doppelkonsonanten auf "1" reduzieren.
Daraus die 1. Ergebnisliste erstellen.
Damit hättest du den gröbsten Filter erstellt.
Daraus eine Verfeinerung bilden (also die Genauigkeit der Suche wieder erhöhen).
Dieses solange durchführen, bis ein exakter Treffer vorliegt (sollte man vielleicht am Anfang schon prüfen) oder die Ergebnismenge leer ist.

Die Regeln für die Verfeinerung müsste man dann allerdings noch definieren. Da habe ich heute aber keine Zeit mehr für.
retnyg
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2754

SNES, GB, GBA, CPC, A500, 486/66, P4/3.0HT: NintendOS, AmigaOS, DoS
Delphi 5, Delphi 7
BeitragVerfasst: Di 19.07.05 17:16 
user profile iconGausi hat folgendes geschrieben:

@retnyg:
ausblenden Quelltext
1:
2:
3:
A e r z t e
| | | | | |
Ä r z t e
Da sind genau Null Zeichen gleich, der Rest total unterschiedlich. Oder wie meintest du das?

die buchstaben erzt sind in beiden vorhanden (das sind 80% übereinstimmung).
dazu ist noch ihre reihenfolge gleich.
ausserdem sollte deine software von haus aus intern nur mit ae statt ä arbeiten.

_________________
es gibt leute, die sind genetisch nicht zum programmieren geschaffen.
in der regel haben diese leute die regel...
Gausi Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8548
Erhaltene Danke: 477

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: Di 19.07.05 17:34 
user profile iconretnyg hat folgendes geschrieben:

die buchstaben erzt sind in beiden vorhanden (das sind 80% übereinstimmung).
dazu ist noch ihre reihenfolge gleich.
Glaub ich gerne, seh ich ja auch auf einem Blick, aber wie macht man das im Programm?

user profile iconretnyg hat folgendes geschrieben:
ausserdem sollte deine software von haus aus intern nur mit ae statt ä arbeiten.
Ja, und was mach ich dann mit
ausblenden Quelltext
1:
2:
3:
M o r r i s s e t t e
| | | X X X X X X
M o r i s e t t e
...? da kommt dann wieder: alle doppelten Buchstaben durch einen ersetzen...:? Ist sicherlich eine ganz nette Idee, aber irgendwie sagt die mir noch nicht ganz zu...das ist halt wieder auf eine bestimmte Art von Fehler zugeschnitten. Und wenn ich das alles hintereinander überprüfe, dann rechne ich ne halbe Sekunde an einem Vergleich rum - und das is zuviel. Ich würde ja erst den String bearbeiten müssen, bevor ich mit dem eigentlichen Vergleich anfange. Besser wäre es doch, wenn ich anfange, zu vergleichen, und recht schnell feststelle, dass weiteres Arbeiten nix bringt...

Jasocul hat übrigens per ICQ den Vorschlag geäußert, dass ich daraus eine Art Wettbewerb starte: Wer schreibt den besten intelligenten Suchalgorithmus?

_________________
We are, we were and will not be.
Spaceguide
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 552


(D3/D7/D8) Prof.
BeitragVerfasst: Di 19.07.05 18:37 
Guck dir mal den Algorithmus für den minimalen Editierabstand an. Damit kannst du die Ähnlichkeit zweier Zeichenketten berechnen.
retnyg
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2754

SNES, GB, GBA, CPC, A500, 486/66, P4/3.0HT: NintendOS, AmigaOS, DoS
Delphi 5, Delphi 7
BeitragVerfasst: Di 19.07.05 19:08 
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:
function intCompare(s1, s2: string) :boolean;
// compares wors on a similar content
// (c) retnyg

  function reformat (s:string):string;
  var l,i : integer;
  begin
     l:=length(s);
     result := '';
     for i := 1 to l do
       case upcase(s[i]) of
         'A'..'Z': result := result + upcase(s[i]);
         'Ä','ä': result := result + 'AE';
         'Ö','ö': result := result + 'OE';
         'Ü','ü': result := result + 'UE';
       end;
  end;

type ad = array [0..26of dword;
var
//    count1, count2: ad;
//    pcount: ^ad;
    usedletters1: string;
    usedletters2: string;
    plen : pinteger;
    i,l,l2:integer;
    p, p2: pstring;

begin
  result := false;

  if (length(s1) = 0or (length(s2) = 0then exit;

  s1:=reformat(s1);
  s2:=reformat(s2);

  l := length(s1);
  l2 := length(s2);

//  if (l * 100) div (length(s2) * 100)
  plen := @l;
  p := @s1;
  p2 := @usedletters1;
//  pcount:= @count1;
//  zeromemory(pcount,sizeof(ad));

  setlength(p2^,0);

  for i := 1 to plen^ do begin
     if pos(p^[i],p2^) = 0 then
      p2^ := p2^ + p^[i];
//     inc(count1[ord(p^[i])-65]);
  end;

  plen := @l2;
  p := @s2;
  p2 := @usedletters2;
//  pcount:= @count2;
//  zeromemory(pcount,sizeof(ad));

  setlength(p2^,0);

  for i := 1 to plen^ do begin
     if pos(p^[i],p2^) = 0 then p2^ := p2^ + p^[i];
//     inc(count1[ord(p^[i])-65]);
  end;

  if usedletters1 = usedletters2  then begin result := true; exit; end;

end;


ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
procedure TForm1.Button3Click(Sender: TObject);
begin
  if intCompare('Morrisette''moriset'then showmessage('same word');
  if intCompare('ärzte''Aerzte'then showmessage('same word');
end;

_________________
es gibt leute, die sind genetisch nicht zum programmieren geschaffen.
in der regel haben diese leute die regel...


Zuletzt bearbeitet von retnyg am Di 19.07.05 19:42, insgesamt 1-mal bearbeitet
GTA-Place
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
EE-Regisseur
Beiträge: 5248
Erhaltene Danke: 2

WIN XP, IE 7, FF 2.0
Delphi 7, Lazarus
BeitragVerfasst: Di 19.07.05 19:32 
Hey, coole Funktion! Sogar "mmoorriisseettee" wird erkannt.

_________________
"Wer Ego-Shooter Killerspiele nennt, muss konsequenterweise jeden Horrorstreifen als Killerfilm bezeichnen." (Zeit.de)
retnyg
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2754

SNES, GB, GBA, CPC, A500, 486/66, P4/3.0HT: NintendOS, AmigaOS, DoS
Delphi 5, Delphi 7
BeitragVerfasst: Di 19.07.05 20:22 
user profile iconSpaceguide hat folgendes geschrieben:
Guck dir mal den Algorithmus für den minimalen Editierabstand an. Damit kannst du die Ähnlichkeit zweier Zeichenketten berechnen.
wo gibts den ?

_________________
es gibt leute, die sind genetisch nicht zum programmieren geschaffen.
in der regel haben diese leute die regel...
Gausi Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8548
Erhaltene Danke: 477

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: Di 19.07.05 20:37 
Einer der wiki-Links von mir weiter oben zeigt den, wenn auch nicht direkt unter dem Namen. Den bearbeite ich gerade, und passe den ggf. weiter an...

_________________
We are, we were and will not be.
retnyg
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2754

SNES, GB, GBA, CPC, A500, 486/66, P4/3.0HT: NintendOS, AmigaOS, DoS
Delphi 5, Delphi 7
BeitragVerfasst: Di 19.07.05 20:42 
ist dir mein code nicht gut genug :mrgreen:
kannst du mir mal den genauen link posten pls ?

_________________
es gibt leute, die sind genetisch nicht zum programmieren geschaffen.
in der regel haben diese leute die regel...
Gausi Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8548
Erhaltene Danke: 477

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: Di 19.07.05 21:02 
im wesentlichen das hier.

zu deinem Code: erste Versuche haben Fehler und Fehlverhalten ergeben. Mit Leerzeichen kommt der z.B. nicht wirklich klar. Und richtig verstanden hab ich den auf Anhieb auch nicht. Zuviel mit Zeigern drin ;-) Und dann kam dieser Editier-Algo dazwischen...Wenn das ne Sackgasse wird, komme ich aber auf dich zurück!

_________________
We are, we were and will not be.
matze
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 4613
Erhaltene Danke: 24

XP home, prof
Delphi 2009 Prof,
BeitragVerfasst: Mi 20.07.05 09:06 
soweit ich das mitbekommen habe, suchst du quasi den SoundEx Algorithmus. den kann delphi (zumindest ab version 7) aber schon selber.

_________________
In the beginning was the word.
And the word was content-type: text/plain.
Gausi Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8548
Erhaltene Danke: 477

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: Mi 20.07.05 10:17 
Aarrrggghhh.. :motz: :autsch:

Da probiert man ellenlang rum, und dann gibts da ne fertige Funktion? Tatsächlich liefert das Teil ganz vernünftige Ergebnisse. Zu REM findet er z.B. Rem, R.E.M., das Album 'Reim' von Matthias Reim und Titel wie 'Rain'... ein bissel Feinjustierung tut da wohl noch gut.

Trotzdem hat mich jetzt der Eifer gepackt, und ich versuch das nochmal mit der Editierdistanz. Ganz zufrieden bin ich mit SoundEx noch nicht...ich bekomm das mit der Länge der Strings nicht richtig hin...bei Suche nach "Hosen" spuckt er nix aus - der stört sich wohl an dem "die Toten", was häufig davor steht. Und um das mit pos zu verbinden, muss ich die phonetische Repräsentation passend kürzen, aber da hab ich noch nix zu gefunden :?

_________________
We are, we were and will not be.
matze
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 4613
Erhaltene Danke: 24

XP home, prof
Delphi 2009 Prof,
BeitragVerfasst: Mi 20.07.05 10:26 
user profile iconGausi hat folgendes geschrieben:
Aarrrggghhh.. :motz: :autsch:
Da probiert man ellenlang rum, und dann gibts da ne fertige Funktion?

Sorry. Ich wollte dir nicht den Spaß vermiesen :wink:

Du könntest aber ja den titel anhand der Leerzeichen in einezelne Wörter aufsplitten und dann diese einzel wörte "Soundexen".

_________________
In the beginning was the word.
And the word was content-type: text/plain.