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.