一种面向PDF文本内容审查的高效多模式匹配算法  

Efficient multi-pattern matching algorithm for PDF content search

作　　者：刘邦国 陈庆春[1] 类先富 Liu Bangguo;Chen Qingchun;Lei Xianfu(School of Information Science&Technology,Southwest Jiaotong University,Chengdu 611756,China)

机构地区：[1]西南交通大学信息科学与技术学院,成都611756

出　　处：《计算机应用研究》2020年第6期1755-1759,共5页Application Research of Computers

基　　金：国家自然科学基金资助项目(61771406)。

摘　　要：针对Wu-Manber多模式匹配算法所存在的匹配效率低、跳转距离较小的问题,结合PDF文本内容的编码规则,提出了一种适用于中文PDF文本内容审查的Wu-Manber改进算法。该算法使用布隆过滤器提取模式串关键信息,同时结合双重哈希和PDF文本编码规则,减少了无谓的匹配次数,加大了跳转幅度,从而提升了PDF文本的匹配性能。实验结果表明,这种改进算法在PDF文本审查中的匹配速率有较大提升,尤其当最短模式串较长且模式串规模较大时速度可以提升一倍以上。To solve the deficiency of Wu-Manber multi-pattern matching algorithm in terms of the achieved matching efficiency and jump distance,this paper proposed an improved Wu-Manber algorithm for Chinese PDF document content review on the basis of the coding formats of PDF document content. By employing the Bloom filter to extract the crucial information of the pattern string,and exploiting the double hash and PDF document encoding rules,the proposed improved algorithm was able to reduce the number of unnecessary matches and increase the jump distance,which results in improving the matching efficiency for the content retrieval of PDF document. The practical experimental results confirm the improved matching efficiency for PDF document,especially when the shortest mode string is long and the mode string size is large,the matching efficiency can be even doubled.

关 键 词：多模式匹配 WU-MANBER算法 PDF文本编码 布隆过滤器 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]