Zitat von
Gausi:
Zitat von
stoxx:
Ein Bayer Moore Algorithmus hat ja immer noch die Laufzeit O(m/n).
Also erstens heißt das Boyer-Moore, und zweitens hat das Ding im Mittel ne Laufzeit von O(log(n)/n * m) (log zur Basis der Alphabetgröße, aber das ist ja egal). Im Worst-Case ist die Laufzeit O(m*n) bzw. O(m), je nachdem welche Boyer-Moore-Variante man nun genau nimmt (Wikipedia nicht fragen, da steht teilweise Stuss.) O(1), wenn m=n ist, ist auch Quatsch - wenn das Muster gleich dem Text ist, muss man das ja überprüfen, man hat also m Schritte im Worst-Case, einen im Best-Case, also O(m) im Mittel.
Ich habe nicht den ganzen Thread gelesen, aber der Algorithmus ganz oben sieht sehr nach Quicksearch (von Sunday) aus, eine Variante von Boyer-Moore-Horspool. Diese beiden Algorithmen sind in vielen Anwendungsgebieten die schnellsten bekannten Algorithmen (ja, schneller als der Standard-Boyer-Moore!). Zumindest für den Fall, dass man den zu durchsuchenden Text nicht aufbereitet, sondern nur das Suchmuster, aber das ist ja ne ganz andere Herangehensweise.
Für kleine Alphabete (z.B. für eine Suche in DNS-Sequenzen) eignen sich dann allerdings andere Algorithmen besser. Da wären die Faktor-basierten Algorithmen (die auch mit Suffix-Trees arbeiten) besser, oder die sogenannten Faktor-Orakel, die so um 2001 das "erfunden" wurden.
Ansonsten ist der Algorithmus im ersten Beitrag sehr zu empfehlen, und eine Optimierung halte ich im Gegnsatz zu meinem Vorredner für durchaus sinnvoll.
hehe .. danke, Du hast Recht mit der Laufzeit O(1) ... war zu kurz nachgedacht.
In der realen Anwendung hats mir halt nix gebracht,.... Wenn es mich sehr viel Zeit kostet,die Daten irgendwo herzubekommen, wie sie dann zu durchsuchen .. (mit dem einfachsten suchalgorithmus beim linearen durchgehen mit einer simplen Pascal Schleife ... hmmm .. dann kann ich höchstens den Faktor 2 sparen. Weil die Daten muss ich ja noch irgendwo beschaffen.
Wenn ich dann noch einmal zuviel kopiere, dann wird noch langsamer ( guck Dir mal die Explode Implementierung an)
und da kann der Algorithmus gar nix mehr machen. Da dauerts einfach drei oder viermal so lange. Nur weil man ihn schlecht umgesetzt hat.
Naja ... waren nur die praktischen Erfahrungen.
Die Theorie eines Algorithmus muss nicht unbedingt in der Praxis zutreffen. Suffix Arrays sind per Definition laut mathematik langsamer als Suffix-Trees. Dennoch gibt es C-implementationen die genauso schnell sind, wie ein Tree ..
So ist das eben
