Fehlertolerante Suche proggen

Hack Gott · Verfasst: Mo 22.05.06 12:58

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):

markieren

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

jasocul · Verfasst: Mo 22.05.06 13:03

Dann wirst du dich mit der phonetischen Suche beschäftigen müssen.
Beiwikipedia findest du schonmal ein paar Hinweise, wie es funktioniert und wo die Probleme/Grenzen sind.

digi_c · Beiträge: 1905 W98, XP D7 PE, Lazarus, WinAVR

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 · Verfasst: Mo 22.05.06 13:44

Eine Möglichkeit ist SoundEx, was auch mit Delphi-Hausmitteln geht. Eine andere Möglichkeit habe ich hier 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 ;-)

_________________
We are, we were and will not be.

Hack Gott · Verfasst: 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?

markieren

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;

matze · Verfasst: Mo 22.05.06 19:48

Delphi 7 kann aber von Haus aus schon den SoundExBefehl !!!

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

MrSaint · Verfasst: 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: 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

_________________
"people knew how to write small, efficient programs [...], a skill that has subsequently been lost"
Andrew S. Tanenbaum - Modern Operating Systems

alzaimar · Verfasst: 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 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.).

_________________
Na denn, dann. Bis dann, denn.

worm · Beiträge: 135 D6 Prof

Hack Gott hat folgendes geschrieben:

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?

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]??*").

_________________
In the beginning, the universe was created. This has made a lot of people very angry, and is generally considered to have been a bad move.

wolkenjäger · Hält's aus hier Beiträge: 5 WIN 2000, WIN XP Delphi 5

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:
www.delphi-fundgrube.de/files/levensh.txt

Ciao

digi_c · Beiträge: 1905 W98, XP D7 PE, Lazarus, WinAVR

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 · Verfasst: 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.

_________________
We are, we were and will not be.

galagher · Verfasst: Di 23.05.06 20:17

Hallo!
Sieh dir das einmal an, vielleicht kannst du das brauchen:
groups.google.at/gro...=de#f03a1e596e94d2f2

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

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme