Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
WM+: An Optimal Multi-pattern String Matching Algorithm Based on the WM Algorithm
verfasst von : Xunxun Chen, Binxing Fang, Lei Li, Yu Jiang
Erschienen in: Advanced Parallel Processing Technologies
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The WM algorithm, designed by Sun Wu and Udi Manber, is considered the fastest multi-pattern string matching algorithm in practice except when the pattern number is very large or the alphabet size is small[2]. Theoretically, the scanning time of WM is average-optimal (i.e. O(
n
log
σ
(
rm
)/
m
)), but in the worst case, its scanning time can not be evaluated at all. The maximum shift of the original WM algorithm is m-B+1, where
m
is the minimum length of all patterns and B is the
q
-gram size. The tuned WM algorithm (abbreviated as WM+) can reach higher performance by improving the
shift
table building algorithm and combining the AC algorithm with the original WM algorithm. And the scanning time of the WM+ algorithm in the worst case is predictable. Experiments show that the scanning time of the WM+ algorithm is less or not great than that of the WM algorithm for varied size of
m
and number of patterns, especially in the worst case.