Suchalgorithmus gesucht

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