《计算机应用研究》|Application Research of Computers

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

Efficient multi-pattern matching algorithm for PDF content search

免费全文下载 (已被下载 次)  
获取PDF全文
作者 刘邦国,陈庆春,类先富
机构 西南交通大学 信息科学与技术学院,成都 611756
统计 摘要被查看 次,已被下载
文章编号 1001-3695(2020)06-030-1755-05
DOI 10.19734/j.issn.1001-3695.2018.11.0868
摘要 针对Wu-Manber多模式匹配算法所存在的匹配效率低、跳转距离较小的问题,结合PDF文本内容的编码规则,提出了一种适用于中文PDF文本内容审查的Wu-Manber改进算法。该算法使用布隆过滤器提取模式串关键信息,同时结合双重哈希和PDF文本编码规则,减少了无谓的匹配次数,加大了跳转幅度,从而提升了PDF文本的匹配性能。实验结果表明,这种改进算法在PDF文本审查中的匹配速率有较大提升,尤其当最短模式串较长且模式串规模较大时速度可以提升一倍以上。
关键词 多模式匹配; Wu-Manber算法; PDF文本编码; 布隆过滤器
基金项目 国家自然科学基金资助项目(61771406)
本文URL http://www.arocmag.com/article/01-2020-06-030.html
英文标题 Efficient multi-pattern matching algorithm for PDF content search
作者英文名 Liu Bangguo, Chen Qingchun, Lei Xianfu
机构英文名 School of Information Science & Technology,Southwest Jiaotong University,Chengdu 611756,China
英文摘要 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.
英文关键词 multi-pattern matching; Wu-Manber algorithm; PDF text encoding; Bloom filter
参考文献 查看稿件参考文献
 
收稿日期 2018/11/16
修回日期 2019/1/10
页码 1755-1759
中图分类号 TP301.6
文献标志码 A