Suchalgorithmus gesucht

[Daniel]

Moin z'ammen,

ich suche eine Suche ...

Es geht darum, dass ich einen Haufen an einzelnen, relativ kurzen (i.d.R. weniger als 40 Zeichen), Strings habe, die ich durchsuchen möchte. Wichtig an der Sache ist, dass ich auch nach beliebigen Teilstrings suchen muss - mein erster Ansatz mit Binärbäumen z.B. hat mir hier wenig geholfen.

Aktuell bin ich bei knapp 30.00 Einträgen und komme noch mit eiener FOR-Schleife und der Pos-Funktion aus dem FastCode-Project zurecht. Es ist aber absehbar, dass dieser Ansatz auf Dauer nur bedingt tauglich sein wird.


Hat einer von Euch mal ein Stichwort, nach welchen Verfahren ich da suchen könnte?

[Bernhard Geyer]

(Java) Lucene + JNI (Java Native Interface).

[OregonGhost]

Wäre da nicht ein Directed Acyclic Word Graph (DAWG) etwas? Das hat Hagen neulich irgendwo gepostet. Ich bin nicht sicher, ob das wirklich genau dein Problem löst, aber einen Blick wäre es vielleicht wert.

[Phoenix]

Ggf. eine Hashtable.

Beim Eingeben eines Strings zerlegst Du diesen in alle möglichen Teilstrings.
Gibt es diesen Teilstring schon in der Hashtable, dann fügst Du dort eine Referenz auf den neuen String hinzu.
Gibt es diesen Teilstring noch nicht, berechnest Du darüber den Hash und fügst ihn mit der Referenz auf den neuen String in die Table ein.

Bei einer Suche berechnest Du über die Eingabe den Hash, und suchst in der Hashtable nach diesem Eintrag (Eine einzige For-Schleife über die Table).

Hast Du genau diesen Hash in der Tabelle gefunden sind alle mit diesem Eintrag referenzierten Strings das Suchergebnis, existiert der Hash nicht in der Tabelle hast Du auch keine Strings in der Datenquelle, die zu dieser Suche passen.

Das ist natürlich beim Einfügen eines neuen Datensatzes ein etwas höherer Aufwand, dafür ist die Suche schnell (nur Vergleich auf Gleichheit).

Zur Optimierung kann man dann die Hashtable in einen binären Baum packen, damit man nicht durch die gesamte Tabelle laufen muss sondern hier gezielt einen Hashwert herausfischen kann.

[Daniel]

Danke erstmal für Eure Hinweise. :-)

Die DAWG werde ich zu einem späteren Zeitpunkt mal versuchen - rein aus Interesse.

[HERMES]

Du kannst die einzelnen Strings mit Boyer Moore oder KMP durchsuchen, das sind recht effiziente Matching Algorithmen.

[mschaefer]

Moin, moin,
ich hätte mal zwei Links auf die DP: Teil)String in anderem String suchen/zählen
und wenn man das noch kombiniert mit einer Directory-List (im Beispiel)
Vergleich von Suchverfahren mit Beispielen , dann sollte da was auf der Überholspur herauskommen.

Grüße in den Norden // Martin

[stahli]

Hallo Daniel,

interessieren Dich nur EXISTIERENDE TEXTTEILE ohne insgesamt ähnliche Einträge zu Deinen Suchwörtern (incl. evtl. Schreibfehler oder Abkürzungen)?

Stahli

[Gausi]

Wenn, dann aber bitte Boyer-Moore. KMP ist in aller Regel nicht schneller als der naive Ansatz.

Was spricht denn gegen das normale Pos? Wieviele Strings werden das denn am Ende sein? Ich habe ein ähnliches Problem in einem anderen Programm, und da arbeite ich mit ca. 50.000 Objekten mit je 5 Strings (4 davon mit ähnlicher Länge, der fünfte kann auch was länger sein), und ein Durchsuchen dieser 250.000 Strings nach einem Suchbegriff dauert nur ein oder zwei Sekunden, vielleicht auch mal drei.

[Daniel]

@Stahli: Ja, es geht nur um existierende Textteile. Ähnlichkeit wäre knuffig, würde aber den Rahmen des Projektes sprengen.

@Gausi: Noch spricht nichts gegen den Einsatz der Pos-Funktion. Aktuell realisiere ich damit eine Filterung der Daten in (gefühlter) Realzeit. Sprich: Sobald der Anwender mit dem Tippen fertig ist, sieht er eine Liste, die seiner Auswahl entspricht. Ich werde vermutlich heute Abend mal eine signifikant größere Datenmenge haben. Die daraus resultierenden Suchzeiten werden bestimmen, wieviel Aufwand ich in die Optimierung der Suche stecken muss.

[stahli]

Hallo Daniel,

wenn Du´s "knuffig" findest, kannst Du es ja mal testen. Anbei eine komplette Pas, dann hält sich der Aufwand damit für Dich in Grenzen...

Ich wäre der glücklichste Mann der Welt (na ja, an der Formulierung muss ich noch arbeiten ;-) ) wenn ich Dir hier auch mal helfen könnte...

Du brauchst nur die zwei Strings übergeben, sowie ggf. einen minimalen Ähnlichkeitswert...
-> GetStahliSuche(Suchbegriffe,Suchtext:String;AbAehn lichkeit:Integer=75)

Sehr schnell wird es nicht gehen (ist auch noch nicht wirklich optimiert), aber mit dem Ergebnis war ich bisher immer ganz zufrieden. Man kann natürlich die Ergebnisse auch gleich nach Ähnlichkeiten sortieren lassen.

Hoffentlich bringt Dir das was... Würde mich freuen.

Stahli

[alzaimar]

Zitat:

Zitat von Daniel

Hat einer von Euch mal ein Stichwort, nach welchen Verfahren ich da suchen könnte?

Dictionary Of Algorithms and Data Structures Algorithmen allgemein
Charras & Lecroq, Université de Rouen Stringmatching.

Du hast also 30000 kleine Strings und suchst in denen nach Teilstrings? Versuchs mal mit einer Klasse, die ich für eine schnelle inkrementelle Adressensuche geschrieben habe. Ich habe 100000 Adressen, in denen ich nach Namen/Strassen oder Teilen davon suchen muss. Das geht so schnell, das ich damit eine inkrementelle (While you type) darstellung der Ergebnisse hinbekomme (Suchzeit < 50ms). Ich breche allerdings nach 500 gefundenen Adressen ab... Je länger die Strings und je länger der Suchstring, desto schneller ist die Gurke.

Ich habe den Quicksearch-Algorithmus verwendet, einen vereinfachten Boyer-Moore. BM ist -in Delphi implementiert- nicht schnell genug (zuviel overhead), und da ich kein ASM verwende (zu blöd), hab ich eben den QS mit einer Optimierung von Raita implementiert.

Der DAWG von Hagen ist zwar viel schneller, verbrät aber so viel Speicher, das mein 2GB-Teil aufgegeben hat.

So in etwa sollte es funktionieren.

Delphi-Quellcode:

Var
  MyData : TcsPosList;
  iLine, iPos : Cardinal;

Begin
// Daten initialisieren
  MyData := TcsPosList.Create('\'); // Irgendein delimiter, der in deinen Strings nicht vorkommt.
  For i:=0 to 29999 do MyData.Add(DanielsKurzeStrings[i]); // Deine Zeilen in die Struktur einfügen
  MyData.Finalize; // Einfügen abschließen.
//
//
// Suche initialsieren (pro Pattern 1x)
  MyData.Pattern := 'FooBar'; // Suche nach "Foobar";

// Alles durchsuchen
  iLine := 0;
  iPos := 0;
  MyData.First;
  While MyData.FindNext(iLine, iPos, psContains) Do Begin // Oder '...psBeginsWith'
    ListBox1.Lines.Add (MyData.Lines[iLine]);
  End;
...
... 
  MyData.Free;
End;

Probier mal, ob Du damit klar kommst (der Code ist selbstverständlich völlig unkommentiert :oops: )

[Daniel]

Wunderbar, danke. :-) Dann kann ich heute am späteren Abend mal Tests durchführen.

Das Ganze soll eine IDE-Erweiterung für Delphi 2007 werden - wenn alles klappt, kann ich den Code also quasi wieder zurückgeben. ;-)

[Gausi]

Zitat:

Zitat von alzaimar

Ich habe den Quicksearch-Algorithmus verwendet, einen vereinfachten Boyer-Moore. BM ist -in Delphi implementiert- nicht schnell genug (zuviel overhead), und da ich kein ASM verwende (zu blöd), hab ich eben den QS mit einer Optimierung von Raita implementiert.

Zu "BM ist zu langsam" hätte ich mal ne Frage. Klar, die Preprocessing-Phase ist bei BM etwas aufwendig und frickelig (zumindest der Good-Suffix-Part [in der Original-Literatur ist der Teil sogar falsch :stupid:]), aber könnte man das in diesem Fall nicht so anpassen, dass das Preprocessing einmalig durchgeführt wird, und diese Tabellen für alle Suchen in den kleinen Strings benutzt werden? Das würde den Overhead doch deutlich senken, oder?

Oder gibts da nochwas, was ich übersehen habe?

[stahli]

Hallo Daniel,

wenn die Suche in der IDE verwendet werden soll taugt meine Funktion vielleicht doch nicht ganz so gut :-(

Ich habe sie mal geschrieben, um komplette Kundenadressen zu vergleichen und doppelte Einträge zu finden. Das Problem: Es gab für ein und den selben Kunden mehrere verschiedene Schreibweisen unter unterschiedlichen Kundennummern. (In meinem Projekt wurden dann auch noch die Teile VOR und HINTER einem evtl. "c/o" gegenseitig verglichen.)

In der IDE weiß man ja meistens schon, was man genau sucht ;-)

Auf jeden Fall sind in der aktuellen Version der Funktion hohe Ähnlichkeiten nur zu erwarten, wenn beide Texte in etwa die gleichen Daten beinhalten UND NICHT in beiden Texten weitere verschiedene Zusätze enthalten sind:

André Stahl -> AndreasStahl -> ähnlich
André Stahl -> StahlAndreGbR -> ähnlich
André Stahl, Halle -> AndreasStahl fährt Opel Corsa -> nicht ähnlich

Im dritten Beispiel wird zwar zuerst eine gute Übereinstimmung gefunden, dann aber abgewertet, da ein großer Rest ohne Übereinstimmung übrig bleibt.

Ggf. könnte mann diese "Abwertung" reduzieren oder abstellen. Dann hätte man eine unscharfe Suche nach Teilwörten in einem längeren Text ... ?!

Anbei mal eine kleine Exe zum Testen der aktuellen Funktion.
Mit der TrackBar lässt sich der Schwellenwert für "ähnlich/nicht ähnlich" einstellen.

Stahli

[mschaefer]

Moin, moin,

Du konntest den ersten Buchstaben eine höhere Wertigkeit(Punkte?) geben als den letzten.

Grüße // Martin

[alzaimar]

Zitat:

Zitat von Gausi

Zu "BM ist zu langsam" hätte ich mal ne Frage. ...

Das hat nichts mit dem Erstellen der Suffixtabellen zu tun, sondern mit dem Suchalgorithmus selbst. Dieser Overhead (Entscheidungen, wie und ob gesprungen wird etc.) sind für die relativ kurzen Strings (1-10 Zeichen) einfach zu viel. Stringmatching wird ja z.B. in der Genanalyse verwendet, wo man in einem String von 1000000den von GACT-Sequenzen eine bestimmte, vielleicht 100000 Zeichen lange zweite Sequenz suchen will.

In der FastString-Unit von DroopyEyes ist zwar ein BM-Search implementiert, nur scheint der im Endeffekt ein QS zu sein.

Grundsätzlich ist es aber schon so, das man die Erstellung der Sprungtabellen VOR dem Durchsuchen des Strings einmalig durchführt, da sie relativ zeitaufwändig sind.

[stahli]

@Martin:

Kann man machen, das hat aber den Nachteil, dass die Wörter in beiden Zeichenketten in der gleichen Reihenfolge enthalten sein müssen...
Das ist in vielen Fällen sicher eher störend...

Stahli

[mschaefer]

Hm ja leuchtet ein! Das ist wahrscheinlich nicht zu erwarten...