A Boyer-Moore-style algorithm for regular expression pattern matching
A Boyer-Moore-style algorithm for regular expression pattern matching
复制标题
用于正则表达式模式匹配的 Boyer-Moore 风格算法
DOI：
10.1016/s0167-6423(03)00013-3
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
Richard E. Watson
中科院分区：
文献类型：
--
作者：
Bruce W. Watson;Richard E. Watson
本文提出了用于正则表达式模式匹配的 Boyer-Moore 型算法，回答了 Aho 在 1980 年提出的一个开放问题（字符串中的模式匹配，Academic Press，纽约，1980 年，第 342 页）。新算法处理由正则表达式指定的模式——Boyer–Moore 和 Commentz-Walter 算法的推广。与 Boyer–Moore 和 Commentz-Walter 算法一样，新算法利用了可以预先计算和制表的移位函数。推导了预计算算法，并表明可以根据Commentz-Walter的d1和d2shift函数预计算所需的移位函数。在某些情况下，Boyer-Moore（分别为 Commentz-Walter）算法大大优于 Knuth-Morris-Pratt（分别为 Aho-Corasick）算法（正如 Watson 在埃因霍温理工大学 1995 年 9 月的博士论文中所讨论的，以及：N. Ziviani、R. Baeza-Yates、K. Guimaraes（编辑）， 过程。第三届南美字符串处理研讨会，国际信息学系列，卷。 4，卡尔顿大学出版社，巴西累西腓，1996 年，第 280-294 页）。在测试中，本文提出的算法也经常优于 Aho-Corasick 算法的正则表达式泛化。
This paper presents a Boyer–Moore-type algorithm for regular expression pattern matching, answering an open problem posed by Aho in 1980 (Pattern Matching in Strings, Academic Press, New York, 1980, p. 342). The new algorithm handles patterns specified by regular expressions—a generalization of the Boyer–Moore and Commentz-Walter algorithms. Like the Boyer–Moore and Commentz-Walter algorithms, the new algorithm makes use of shift functions which can be precomputed and tabulated. The precomputation algorithms are derived, and it is shown that the required shift functions can be precomputed from Commentz-Walter's d1and d2shift functions. In certain cases, the Boyer–Moore (respectively Commentz-Walter) algorithm has greatly outperformed the Knuth–Morris–Pratt (respectively Aho–Corasick) algorithm (as discussed by Watson in his Ph.D. Thesis, Eindhoven University of Technology, September 1995, and in: N. Ziviani, R. Baeza-Yates, K. Guimaraes (Eds.), Proc. Third South American Workshop on String Processing, International Informatics Series, vol. 4, Carleton University Press, Recife, Brazil, 1996, pp. 280–294). In testing, the algorithm presented in this paper also frequently outperforms the regular expression generalization of the Aho–Corasick algorithm.