Boyer Moore Algorithmus

[Ginko]

Hi und Danke für die Antworten.
Im Anhang ist ein Projekt welches eine Testdatei erstellen kann (Zeilenlänge nach Wahl) und die Zeit mit dem QueryPerformanceCounter misst.
Zum testen habe ich den Code von Furtbichler genommen, allerdings musste ich ihn noch etwas anpassen, damit das mit dem Offset klappt.
Gezählt wird jetzt jedenfalls absolut korrekt. Aber BMH ist bis zu 5 mal langsamer. Habe ich wahrscheinlich ne Bremse eingebaut...

@Horst_ dein Test hat bei mir keine richtigen Werte geliefert. (Vielleicht habe ich aber auch was vergessen...)

[Gausi]

Boyer-Moore (oder andere Verfahren jenseits des naiven) sind deshalb so schnell, weil sie vor der eigentlichen Suche eine Vorbereitungsphase haben. Bei Boyer-Moore läuft diese Vorbereitungsphase auf Grundlage des Suchstrings und heißt hier PreProcess_BMH_BC.

Dein Code durchläuft nach jedem Fund diese Vorbereitungsphase erneut - und bremst dadurch das Verfahren extrem aus. Inbesondere dann, wenn du viele Fundstellen hast. Wenn du alle Fundstellen haben willst, dann musst du den Code anpassen, und anstelle des "Result := ...; Exit;" eine Liste mit allen Fundstellen aufbauen.

Auto Vergleiche sind ja immer schön: Du hast dein Auto schön auf Vordermann gebracht (frisches Öl, neue Reifen, Spolier) um schneller ans Ziel zu kommen. Und dann steigst du an jeder Ampel aus und machst den Öl- und Reifenwechsel erneut.

[Ginko]

Zitat von Gausi:

Dein Code durchläuft nach jedem Fund diese Vorbereitungsphase erneut - und bremst dadurch das Verfahren extrem aus. Inbesondere dann, wenn du viele Fundstellen hast. Wenn du alle Fundstellen haben willst, dann musst du den Code anpassen, und anstelle des "Result := ...; Exit;" eine Liste mit allen Fundstellen aufbauen.

Danke für den Hinweis das werde ich mal versuchen, hört sich plausibel an.

[Ginko]

So jetzt läufts, ab 2 oder 3 Zeichen wird der BMH deutlich schneller.

[Edit] Ab einer gewissen Länge des Suchwortes wird die Standard Funktion bei mir aber wieder schneller, ist das normal ?

Hier nochmal der der Angepasste Code mit Test:

[BUG]

Zitat von Gausi:

Boyer-Moore (oder andere Verfahren jenseits des naiven) sind deshalb so schnell, weil sie vor der eigentlichen Suche eine Vorbereitungsphase haben. Bei Boyer-Moore läuft diese Vorbereitungsphase auf Grundlage des Suchstrings und heißt hier PreProcess_BMH_BC.

Imho wäre es schön, die Suche in ein Objekt zu verpacken. Damit könnte man den Status der Suche (uninitialisiert, initialisiert, nach letztem Fund, usw.) gut verwalten.

[Horst_]

Hallo,

ich habe weiter oben die Vorbereitungsphase in einen Record ausgelagert, weil mir das sehr unsinnig erschien, das ständig neu zu erstellen.
Ich habe Ginko Version 4 mal etwas umgestellt.
Wobei Count seiner Version entspricht, Count_II meiner vorherigen, bei der der vorbereitete Record für das Suchwort BMH mit Offset wiederholt aufruft, falls man eine Liste aufbauen oder etwas sofort verarbeiten will.
Erstaunlicherweise ist Version Count_II wesentlich langsamer.
50 mal in 100000 Zeilen nach Taxi suchen.

Code:

BMH Count II:  100000 in 424ms
BMH Count:     100000 in 353ms
Std Pos Count: 100000 in 343ms

Wieso da 20% verloren gehen, wobei der große Unterschied nur in einem Aufruf pro Fund und Bestimmung der Länge des Suchtextes besteht, alles Kleckerkram für 5 Mio Aufrufe. 58 CPU-Takte mehr.
PosEX ist aber hier, bei solch speziellen Wörtern ( alle sehr unterschiedlich, um möglichst kompakt alle Buchstaben des Alphabetes unterzubringen ), sehr schnell.
Suche nach " im" also mit Leerzeichen vorne
BMH Count II: 100000 in 573ms
BMH Count: 100000 in 450ms
Std Pos Count: 100000 in 1012ms

Falls es aber, wie im ersten Posting angedeutet, um das Durchsuchen von Dateien geht ist eher die Festplatte die herausforderung.

Gruß Horst

[Furtbichler]

Ich verstehe nicht, wieso Du nicht einfach den BM-Suchalgorithmus in einen Count-Algorithmus umwandelst. Nimm das 'fehlende exit' heraus und ersetze das durch ein 'inc(Result)', wobei 'Result' mit 0 initialisiert wird. Dann kannst Du dir diese Schleife auch sparen, wo der SearchBM immer aufgerufen wird.

Und dann kannst Du dir dein Auslagern des Preprocess sparen. Praktikabel ist es i.A. eh nicht, denn wer sucht schon immer nach dem gleichen Text. Und die paar Nanosekunden sind auch egal. Meistens jedenfalls.

[Horst_]

Hallo,

Hallo,

Zitat von BUG:

Zitat von Gausi:

Boyer-Moore (oder andere Verfahren jenseits des naiven) sind deshalb so schnell, weil sie vor der eigentlichen Suche eine Vorbereitungsphase haben. Bei Boyer-Moore läuft diese Vorbereitungsphase auf Grundlage des Suchstrings und heißt hier PreProcess_BMH_BC.

Imho wäre es schön, die Suche in ein Objekt zu verpacken. Damit könnte man den Status der Suche (uninitialisiert, initialisiert, nach letztem Fund, usw.) gut verwalten.

Zitat von Horst_:

ich habe weiter oben die Vorbereitungsphase in einen Record ausgelagert, weil mir das sehr unsinnig erschien, das ständig neu zu erstellen...
Wobei Count seiner Version entspricht, Count_II meiner vorherigen, bei der der vorbereitete Record für das Suchwort BMH mit Offset wiederholt aufruft, falls man eine Liste aufbauen oder etwas sofort verarbeiten will

Also Count, welches nur einmal aufgerufen wird, existiert immer noch und ist ja auch schneller.
Ich habe auch schon mal vor x Jahren einen Ansatz gehabt, viele Dateien nach vielen Wörtern zu durchsuchen.Dabei wurden, wie im ersten Ansatz von Ginko, Blöcke von 4 Kb eingelesen mit Platz für das längste Wort davor, damit Blockread immer auf die selbe Stelle in selber Größe erfolgte.Lange Rede, keinen Sinn. Dort brauchte man eine Struktur, die den Suchstring und dessen letzte Position speicherte.

Gruß Horst

[CCRDude]

Zitat von Horst_:

viele Dateien nach vielen Wörtern zu durchsuchen.

Da ist der BM/BMH aber der falsche Ansatz, da eignet sich etwa der AC deutlich besser, da er dank eines Suchbaumes mit einem Durchgang und höchstens einem Vergleich pro Zeichen auskommt (den Baum zu bauen ist natürlich ggfls. teurer als die einfache/doppelte Skipliste des BM/BMH).