[1]代六玲,y,王树梅,等.一种改进的多关键字匹配算法[J].南京理工大学学报(自然科学版),2005,(06):735-739.
 DAI Liu-ling~.Improved Multi-keyword Matching Algorithm[J].Journal of Nanjing University of Science and Technology,2005,(06):735-739.
点击复制

一种改进的多关键字匹配算法
分享到:

《南京理工大学学报》(自然科学版)[ISSN:1005-9830/CN:32-1397/N]

卷:
期数:
2005年06期
页码:
735-739
栏目:
出版日期:
2005-12-30

文章信息/Info

Title:
Improved Multi-keyword Matching Algorithm
作者:
代六玲1 2y 王树梅1 黄河燕2 陈肇雄2
1.南京理工大学计算机科学与技术系, 江苏南京210094; 2. 中国科学院计算机语言信息工程研究中心, 北京100083, China
Author(s):
DAI Liu-ling~
1,2),WANG Shu-mei~1,HUANG He-yan~2,CHEN Zhaoxiong~2
关键词:
多关键字匹配 BM 算法QS 算法 Sun Wu 算法
Keywords:
mult-i keyword matching BM algorithm QS algorithm Sun Wu algorithm
分类号:
TP301.6
摘要:
基于多关键字匹配的Sun Wu算法进行的分析,结合QS算法的思想,设计了一种改进的多关键字匹配算法:QMS(quick multi-pattern searching)。算法使用散列技术和前缀表减少发生部分匹配时实际进行的关键字比较次数。在计算跳跃距离时,充分考虑当前窗口的紧邻下一个字符带来的信息,进而使用更加精确的跳跃距离计算方法以获得更大的平均跳跃距离,从而获得更高的扫描效率和空间利用率。在真实文本上的对比实验表明,在通常应用环境中,该算法显著的缩短了扫描时间,取得了很好的效果。
Abstract:
An improved algorithm for matching multiple strings is suggested. The new algorithm, named QMS (Quick Mult-i pattern Searching) , is based on the analysis of Sun Wu algorithm and the idea of QS algorithm. QMS uses hashing and PREFIX table to decrease the number of comparisons. During the computation of the shift distance, the character closely after the current window is considered. Thus shift distances are computed with more accurate technique, and larger average shift distance is acquired. The scanning efficiency and the space utility are improved in result. Series of tests on an actual corpus show that QMS algorithm is much more efficient than Sun Wu algorithm under usual circumstances.

参考文献/References:

[ 1] Boyer R S, Moore J S. A fast string searching algorithm[ J] . Communications of the ACM, 1977, 20: 762- 772.
[ 2] Sunday DM. A very fast substring search algorithm[ J] . Communications of the ACM, 1990, 33( 8) : 132- 142.
[ 3] Lecroq T. Experimental results on string matching algorithms [ J] . Software- Practice & Exper ience 1995, 25 ( 7) : 727 - 765.
[ 4] Wu S, Manber U. A Fast Algorithm for Mult-i pattern Searching[ R] . Arigona: Computer Science Department, University of Arizona, 1994.
[ 5] David L. The Reuters- 21578 text categorization test collection. http: / /www. research. att. com/- lewis/ reuters 21578. html. 1998- 05- 11.

备注/Memo

备注/Memo:
国家自然科学基金(60272088)
作者简介: 代六玲( 1977- ) , 男, 博士研究生, 主要研究方向: 中文信息处理, 网络内容管理, E-mail: danliu ling@ yahoo.com;
通讯作者: 王树梅, 女, 教授, 主要研究方向: 中文信息处理, 文本分类。
更新日期/Last Update: 2013-03-03