Autor |
Beitrag |
Gausi
      
Beiträge: 8548
Erhaltene Danke: 477
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: 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
      
Beiträge: 6393
Erhaltene Danke: 147
Windows 7 + Windows 10
Sydney Prof + CE
|
Verfasst: 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
      
Beiträge: 2754
SNES, GB, GBA, CPC, A500, 486/66, P4/3.0HT: NintendOS, AmigaOS, DoS
Delphi 5, Delphi 7
|
Verfasst: 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 
      
Beiträge: 8548
Erhaltene Danke: 477
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: 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:
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 Quelltext 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
      
Beiträge: 173
Win XP HE, Suse Linux
D6, D7, D2005 Personal
|
Verfasst: 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
      
Beiträge: 6393
Erhaltene Danke: 147
Windows 7 + Windows 10
Sydney Prof + CE
|
Verfasst: 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.
Einige Dinge dürften sprachenspezifisch sein.
|
|
Gausi 
      
Beiträge: 8548
Erhaltene Danke: 477
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: Di 19.07.05 16:47
jasocul hat folgendes geschrieben: | Berücksichtigung der üblichen Tippfehler (da wird es dann aber wohl richtig heftig) |
Deswegen hab ich ja den Thread aufgemacht
jasocul 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 
_________________ We are, we were and will not be.
|
|
jasocul
      
Beiträge: 6393
Erhaltene Danke: 147
Windows 7 + Windows 10
Sydney Prof + CE
|
Verfasst: 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
      
Beiträge: 2754
SNES, GB, GBA, CPC, A500, 486/66, P4/3.0HT: NintendOS, AmigaOS, DoS
Delphi 5, Delphi 7
|
Verfasst: Di 19.07.05 17:16
Gausi hat folgendes geschrieben: |
@retnyg:
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 
      
Beiträge: 8548
Erhaltene Danke: 477
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: Di 19.07.05 17:34
retnyg 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?
retnyg hat folgendes geschrieben: | ausserdem sollte deine software von haus aus intern nur mit ae statt ä arbeiten. |
Ja, und was mach ich dann mit
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
      
Beiträge: 552
(D3/D7/D8) Prof.
|
Verfasst: 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
      
Beiträge: 2754
SNES, GB, GBA, CPC, A500, 486/66, P4/3.0HT: NintendOS, AmigaOS, DoS
Delphi 5, Delphi 7
|
Verfasst: Di 19.07.05 19:08
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;
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..26] of dword; var usedletters1: string; usedletters2: string; plen : pinteger; i,l,l2:integer; p, p2: pstring;
begin result := false;
if (length(s1) = 0) or (length(s2) = 0) then exit;
s1:=reformat(s1); s2:=reformat(s2);
l := length(s1); l2 := length(s2);
plen := @l; p := @s1; p2 := @usedletters1;
setlength(p2^,0);
for i := 1 to plen^ do begin if pos(p^[i],p2^) = 0 then p2^ := p2^ + p^[i]; end;
plen := @l2; p := @s2; p2 := @usedletters2;
setlength(p2^,0);
for i := 1 to plen^ do begin if pos(p^[i],p2^) = 0 then p2^ := p2^ + p^[i]; end;
if usedletters1 = usedletters2 then begin result := true; exit; end;
end; |
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
      

Beiträge: 5248
Erhaltene Danke: 2
WIN XP, IE 7, FF 2.0
Delphi 7, Lazarus
|
Verfasst: 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
      
Beiträge: 2754
SNES, GB, GBA, CPC, A500, 486/66, P4/3.0HT: NintendOS, AmigaOS, DoS
Delphi 5, Delphi 7
|
Verfasst: Di 19.07.05 20:22
Spaceguide 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 
      
Beiträge: 8548
Erhaltene Danke: 477
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: 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
      
Beiträge: 2754
SNES, GB, GBA, CPC, A500, 486/66, P4/3.0HT: NintendOS, AmigaOS, DoS
Delphi 5, Delphi 7
|
Verfasst: Di 19.07.05 20:42
ist dir mein code nicht gut genug
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 
      
Beiträge: 8548
Erhaltene Danke: 477
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: 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
      
Beiträge: 4613
Erhaltene Danke: 24
XP home, prof
Delphi 2009 Prof,
|
Verfasst: 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 
      
Beiträge: 8548
Erhaltene Danke: 477
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: Mi 20.07.05 10:17
Aarrrggghhh..
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
      
Beiträge: 4613
Erhaltene Danke: 24
XP home, prof
Delphi 2009 Prof,
|
Verfasst: Mi 20.07.05 10:26
_________________ In the beginning was the word.
And the word was content-type: text/plain.
|
|
|