一种改进的Wu-Manber多关键字匹配算法

PDF(308 KB)

中文信息学报 ›› 2009, Vol. 23 ›› Issue (1) : 30.

综述

一种改进的Wu-Manber多关键字匹配算法

莫德敏¹,刘耀军²

作者信息 +

An Improvement of Wu-Manber Multiple Patterns Matching Algorithm

MO De-min¹, LIU Yao-jun²

Author information +

History +

摘要

针对Wu-Manber算法在处理公共子后缀模式情况下的不足,该文提出了一种基于非空公共子后缀模式的处理算法。该算法把有非空公共子后缀的模式汇集在一起,进一步减小了next链表的平均长度。在匹配过程中减少了字符比较的次数,从而提高算法的运行效率。该文对搜狗实验室给出的相关文档进行全文检索实验,并和原Wu-Manber算法、孙晓山等提出的改进算法进行比较。实验结果表明,该文提出的改进算法有效地减少了匹配过程中字符比较的次数,从而提高匹配的速度和效率。

Abstract

This paper proposes a modified Wu-Manber algorithm based on theε-free subsuffix for multiple patterns matching . The algorithm reduces the amount of string matching by collecting patterns with common subsuffix. The experiments based on documents provided by Sogou indicate that the suggested algorithm can significantly improve the efficiency of string matching compared with the original Wu-Manber algorithm and its modified version.

导出引用

莫德敏,刘耀军. 一种改进的Wu-Manber多关键字匹配算法. 中文信息学报. 2009, 23(1): 30

MO De-min, LIU Yao-jun. An Improvement of Wu-Manber Multiple Patterns Matching Algorithm. Journal of Chinese Information Processing. 2009, 23(1): 30

参考文献

[1] A.V.Aho and M.J.Corasick. Efficient string matching: an aid to bibliographic search[C]//Communications of the ACM,1975,18(6): 333-340
[2] B.Commentz_Walter. A string matching algorithm fast on average[R]. Proceedings of the 6^thInternational colloquium on Automata,Languages and Programming,number 71 in Leture Notes in Computer Science,Springer_Verlag,1974: 118-132.
[3] S.Wu and V.Manber. A fast algorithm for multi_pattern searching[R].Report TR-94-17,Department of Computer Science.University of Arizona,Tucson,AZ,1994.
[4] Gonzalo Navarro and Mathieu Raffinot. Flexible Pattern Matching in strings.柔性字符串匹配[M].中国科学院计算技术研究所网络信息安全研究组译. 北京: 电子工业出版社 2007.3 ISBN 978-7-121-03858-7.
[5] R.S.Boyer and J.S.Moore. A fast string searching algorithm[C]//Communications of the ACM,1977,20(10): 762-772,.
[6] 张鑫,等.一种改进的Wu-Manber多关键词算法[J].计算机应用,2003,23(7): 29-31.
[7] 孙晓山,等.一种改进的Wu-Manber多模式匹配算法及应用[J].中文信息学报,2006,20(2): 47-52.
[8] 王素琴,邹旭楷.一种优化的并行汉字/字符串匹配算法[J].中文信息学报,1995,9(1): 49-53.
[9] 陈开渠,等.快速中文字符串模糊匹配算法[J].中文信息学报,2004,18(2): 58-65.

PDF(308 KB)

677

Accesses

Citation

Detail

段落导航

摘要
Abstract
关键词
Key words
引用本文
参考文献

Received	Published
2007-11-07	2009-02-16
Issue Date
2009-02-16

选择文件类型/文献管理软件名称

选择包含的内容

摘要

Abstract

关键词

Key words

引用本文

{{custom_sec.title}}

{{custom_sec.title}}

参考文献

{{custom_fnGroup.title_cn}}

脚注