Entwickler-Ecke :: Thema anzeigen - Fehlertolerante Suche proggen

Hack Gott - Mo 22.05.06 12:58
Titel: Fehlertolerante Suche proggen

Hi, ich will eine fehlertolerante Suche (also Filter) programmieren. Z.B. das wenn ich täst eingebe, trotzdem noch einträge wie test kommen. außerdem will ich nicht mehr das wenn ich test eingebe, dass wenn der eintrag 'neuer test' heißt, dieser dann rausgefiltert wird.

Bis jetzt habe ich das immer so gemacht (das ist aber leider absolut nicht fehler tolerant):

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:

procedure TForm1.Edit1Change(Sender: TObject);
var
  i,j : integer;
  s : string;
begin
  listBox2.Clear;
  if edit1.Text = '' then begin
  ListBox2.Items := Listbox1.Items;
  Exit;
  end;
  for i := 0 to ListBox1.Count - 1 do
    begin
     s:= '';
     for j:= 1 to Length(Edit1.Text) do
      S:= s+Listbox1.Items[i][j];
      if LowerCase(s) = LowerCase(edit1.Text) then Listbox2.Items.Add(Listbox1.Items[i]);
  end;
end;

Moderiert von Gausi: Topic aus Delphi Language (Object-Pascal) / CLX verschoben am Di 23.05.2006 um 15:27

digi_c - Mo 22.05.06 13:09

Das wird schwer, insbesondere wenn man das performant hinkriegen will :roll:

Das erste wäre eine phonetische Suche.
Es gibt in SQL eine Funktin namens Soundexund diese gibt es auch für Strings unter Delphi.

Kontextsuche
Nun bei der Fehlertolleranz Marke test->neuer test könnte man mit SQL Likemachen oder aber die Filter Eigenschaft von ADO nutzen. Für nicht DB Anwendungen hätten wir als unscharfe Suche noch MatchesMask für sowas ähnliches und für regulären Ausdrücken.

Hoffe das bringt dich erstmal weiter...

Gausi - Mo 22.05.06 13:44

Eine Möglichkeit ist SoundEx, was auch mit Delphi-Hausmitteln geht. Eine andere Möglichkeit habe ich hier [http://www.delphi-forum.de/viewtopic.php?p=274443#274443] gepostet, die rein auf der Buchstabenabfolge basiert.
Zur Performance: Laufzeit ist in O(n*m), wobei n die Länge des Musters, m die Länge des zu durchsuchenden Textes ist. Ist nicht besonders gut, aber auch nicht furchtbar langsam ;-)

Hack Gott - Mo 22.05.06 15:35

Danke für die vielen Antworten!
Also, ich hab mich jetzt entschieden, da es doch alles sehr kompliziert ist, einfach nur die Funktion MatchesMask zu verwenden. Jetzt habe ich aber folgendes Problem: die Begriffe kommen nur, wenn ich genau den selben text eingebe und das wenn ich test eingebe, dass dann neu test kommt, klappt schon mal gar nicht. Was mache ich falsch?

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:

var u : integer;
begin
 for u := 1 to listbox1.Items.Count do begin
  if MatchesMask(listbox1.Items.Strings[u-1], edit1.Text) = true then
    begin
    listbox2.Items.Add(listbox1.Items.Strings[u-1]);
    end;
  end;
end;

MrSaint - Mo 22.05.06 21:42

Ich habe für die Uni mit einem Team auch schonmal sowas implementiert. Wir haben uns damals für den Levenshtein Algorithmus entschieden: http://de.wikipedia.org/wiki/Levenshtein Hat wunderbar funktioniert... Ich weiß nicht mehr waum, aber wir hatten für uns SoundEx aus irgendeinem Grund ausgeschlossen.. Levenshtein funktioniert so, dass er schaut, wieviele "Schritte" man bräuchte um den einen String dem anderen anzugleichen.

MrSaint

alzaimar - Mo 22.05.06 22:24

SoundEx ist, soweit ich das beurteilen kann, für die deutsche Sprache nur bedingt geeignet.

Eine möglichkeit (neben Levenshtein), ist die phonetische Kodierung [http://www.nist.gov/dads/HTML/phoneticCoding.html] die als erstes in der Telefonauskunft New Yorks zum Einsatz kam. Natürlich ist das sprachabhängig, aber wenn man mit ein wenig Schmalz an die (deutsche) Sache rangeht, kann es was werden.

Worum gehts? Es geht darum, Wörter, die ähnlich klingen müssten, einfach auf identische Schlüssel abzubilden.

Beispiel: Test, Täst, Däst, Dest, Desd, Tesd etc. klingen doch nun ähnlich. Wenn man also ähnlich klingende Phoneme durch einheitliche erstetzt, wird aus den eben genannten Wörtern z.B. ein 'DESD', und somit findet man alle ähnlich klingenden Wörter. Ähnliches gilt für 'P' und 'B', 'PH' und 'F' etc. Ganz so trivial ist das nicht, man muss schon sich schon ein wenig mit der deutschen Sprache auskennen (Ausnahmen, wann wird was lang/kurz gesprochen etc.).

worm - Di 23.05.06 00:01

Hack Gott hat folgendes geschrieben:

Die Maske, die Du angegeben hast, passt nur auf exakt den selben Text. Die von MatchesMask verwendete TMask erwartet eine Syntax ähnlich der von DOS/Windows bei der Suche nach Dateinamen - ? steht für ein beliebiges Zeichen, * für eine beliebige Zahl beliebiger Zeichen.
Mit MatchesMask(listbox1.Items.Strings[u-1], '*'+edit1.Text+'*' sollte es also gehen. Je nach Anwendungszweck könntest Du auch dem Nutzer überlassen, die Maske so einzugeben, wie er sie möchte, dann kann er alle Möglichkeiten nutzen (und z.B. nur nach Strings mit A, B oder C am Anfang und mindestens 2 weiteren Zeichen suchen: "[A-C]??*").

wolkenjäger - Di 23.05.06 00:37

Ich denke "Levensthein" ist der "tolleranteste" Ansatz zur Suche. Zerlege den zu durchsuchenden String schrittweise in SubStrings der Länge des gesuchten Strings. Vergleiche die SubStrings mittels Levensthein und merke Dir dabei den kleinsten aufgetretenen Wert als Vergleichsergebnis. Falls der SuchString länger als der zu durchsuchende String ist - einfach die Strings gegeneinander austauschen.

einfach mal ansehen:
http://www.delphi-fundgrube.de/files/levensh.txt

Ciao

digi_c - Di 23.05.06 08:38

Wo wir gerade bei suchen sind vielleicht mal eine andere Frage:

Weiß einer wie die Suchen in Boards,Suchmaschienen... implementiert werden?

Ich meine wenn ich den Suchstring einfach in ein Like *Suchstring* übergebe würde ja bei "Schloss Hund" weder "Schlosshund" noch nur "Schloss" oder "Hund" gefunden. Werden die vorher einfach nur per PHP,... zerlegt bzw. die typischen AND,OR,NOT,+,- Befehle herausgesucht?

Gausi - Di 23.05.06 08:52

Nur so als Hinweis noch zwischendurch: Was ich oben verlinkt habe ist eine Variante von Levenstein, die auch Teilwörter findet. D.h. ein Einfügen von Buchstaben am Anfang oder Ende des zu suchenden Wortes benötigt keine Kosten, die Distanz zwischen "Die Toten Hosen" und "Rosen" ist bei der Variante von mir 1.
Und es können einzelne Zeichen ignoriert werden, Z.B. ist die Distanz von "R.E.M." und "R E M" Null.

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!