Suchalgorithmus gesucht

[alzaimar]

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 )