Speeding up pattern matching by optimal partial string extraction

摘要: String matching plays a key role in web content monitoring systems. Suffix algorithms have good time efficiency, and thus are widely used. These require that all patterns set the same length. When cannot satisfy this requirement, leftmost characters, m being length of shortest pattern, extracted to construct data structure. We call such -character strings partial strings. However, simple extraction from left does not address impact string locations on search speed. propose novel method extract each pattern which maximizes More specifically, with we can compute corresponding searching cost by theoretical derivation, choose location yields an approximately minimal time. evaluate our two rule sets: Snort ClamAV. Experiments show most cases, achieves fastest speed possible extraction, is about 5%–20% faster than alternative methods.