Comparison of stringmatching algorithms: an aid to information content security
A-Ning Du, Binxing Fang, Xiaochun Yun, Mingzeng Hu, Xiu-Rong Zheng · 2004
We analyzed the core ideas of three basic string matching algorithms (KMP, BM, DFA), described the principles of five advanced online multi-pattern matching algorithms (AC, RAC, AQR, SBOM, Mgrep) and compared the matching efficiencies of the five algorithms by searching speed, preprocessing time and memory used on three web information string sets (Chinese phases, URL strings, Email address strings), especially focusing on the infection of pattern set size and min pattern length on the efficiency. From the comparison, we find that stringmatching on Chinese text and URL strings, AQR algorithm is rather efficient; while on Email address matching, SBOM does better. The skipping matching algorithms (such as Mgrep) are much more efficient for small pattern sets. So a combined algorithm of efficient matching algorithms seems to improve the performance and efficiency of information content security systems.