Bitap: Mein liebster String-Matching-Algorithmus
Bitap: My favorite string matching algorithm
Bitap, auch Shift-and genannt, ist ein eleganter Algorithmus zum Finden eines Musters in einem Text. Er funktioniert am besten bei kurzen Mustern, die in ein Maschinenwort passen, und nutzt Bitoperationen, um eine Menge aktiver Zustände zu verwalten. Der Autor leitet ihn schrittweise vom naiven Ansatz über eine Streaming-Variante her und zeigt, wie er durch Bitmanipulation schnell und einfach wird.
Obwohl ich auch Boyer-Moore und KMP im Detail studiert habe, dauert es ziemlich lange, sie von Grund auf herzuleiten, während Bitap sehr leicht abzuleiten ist, da er für mich nur der naive Algorithmus in anderem Gewand ist.