摘要
为提高模式匹配算法中子匹配提取过程的时间效率,采用有序二元决策图(ordered binary decision diagram,OBDD)与布尔函数相结合的方法,完成了与PCRE(perl compatible regular expressions)和谷歌的RE2库的对比实验研究。结果表明:基于OBDD的子匹配算法的性能比PCRE和RE2提高了约一到两个数量级。
To improve the time efficiency of sub-matching extraction process in pattern matching algorithm, a method using Ordered Binary Decision Diagram （0BDD） to represent and manipulate Boolean functions is presented. The comparative experiments were conducted, comparing the presented method with Perl Compatible Regular Expressions （PCRE） and Google＇s RE2 library. Experimental results show that the performance of the submatch algorithm based on OBDD is improved about one to two orders of magnitude over PCRE and RE2.
出处
《广西大学学报（自然科学版）》
CAS
北大核心
2017年第5期1760-1766,共7页
Journal of Guangxi University（Natural Science Edition）
基金
国家自然科学基金资助项目(61403109)
黑龙江省自然科学基金资助项目(F2016024)
黑龙江省教育厅科技面上项目(12531121)
关键词
正则表达式
非确定性有限自动机
布尔函数
有序二元决策图
regular expression
nondeterministic finite automaton
boolean function
ordered binary decision diagrams
