| 一种改进的多关键字匹配算法 |
| |
| 引用本文： | 代六玲,王树梅,黄河燕,陈肇雄.一种改进的多关键字匹配算法[J].南京理工大学学报(自然科学版),2005,29(6):735-739. |
| |
| 作者姓名： | 代六玲 王树梅 黄河燕 陈肇雄 |
| |
| 作者单位： | 南京理工大学,计算机科学与技术系,江苏,南京,210094;中国科学院,计算机语言信息工程研究中心,北京,100083,China;南京理工大学,计算机科学与技术系,江苏,南京,210094;中国科学院,计算机语言信息工程研究中心,北京,100083,China |
| |
| 基金项目： | 国家自然科学基金（60272088） |
| |
| 摘 要： | 基于多关键字匹配的Sun Wu算法进行的分析，结合Qs算法的思想，设计了一种改进的多关键字匹配算法：QMS（quick multi-pattern searching）。算法使用散列技术和前缀表减少发生部分匹配时实际进行的关键字比较次数。在计算跳跃距离时，充分考虑当前窗口的紧邻下一个字符带来的信息，进而使用更加精确的跳跃距离计算方法以获得更大的平均跳跃距离，从而获得更高的扫描效率和空间利用率。在真实文本上的对比实验表明，在通常应用环境中，该算法显著的缩短了扫描时间，取得了很好的效果。
|
| 关 键 词： | 多关键字匹配 BM算法 QS算法 Sun Wu算法 |
| 文章编号： | 1005-9830(2005)06-0735-05 |
| 收稿时间： | 2004-04-26 |
| 修稿时间： | 2005-10-15 |
Improved Multi-keyword Matching Algorithm |
| |
| DAI Liu-ling,WANG Shu-mei,HUANG He-yan,CHEN Zhao-xiong.Improved Multi-keyword Matching Algorithm[J].Journal of Nanjing University of Science and Technology(Nature Science),2005,29(6):735-739. |
| |
| Authors: | DAI Liu-ling WANG Shu-mei HUANG He-yan CHEN Zhao-xiong |
| |
| Institution: | 1. Department of Computer Science and Technology, NUST, Nanjing 210094, China; 2. Language Information Engineering,Chinese Academy of Science, Beijing 100083,China |
| |
| Abstract: | An improved algorithm for matching multiple strings is suggested.The new algorithm,named QMS(Quick Multi-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. |
| |
| Keywords: | muhi-keyword matching BM algorithm QS algorithm Sun Wu algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
