Suchalgorithmus gesucht

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

[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 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 ]), 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 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...