一种有效的字符串有序跳跃模式近似匹配算法

• 作者: 刘功申 沈洲 王永成
• 来源期刊: 数据采集与处理
• 学科: 工学
• 关键词: 匹配 近似模式匹配 组合分析 有限状态自动机
• 年，卷（期）: 2001,（4）
• 所属期刊栏目: 研究简报
• 页码范围: 459-465
• 页数: 7页
• 分类号: TP311
• 字数: 6540字
• 语种: 中文
• DOI: 10.3969/j.issn.1004-9037.2001.04.013

摘要

字符串的模式匹配问题是计算机科学的基本问题之一,而近似模式匹配更是近期的研究热点.本文分析了文本分析领域中出现的一种特殊的近似模式匹配问题,即字符串有序跳跃模式近似匹配问题,提出了一种基于有限自动机的组件组合分析算法.算法的特点在于将组件匹配过程与组配过程进行分离,这样既降低了问题的复杂度,又可以实现按策略组配的灵活性.组件匹配过程中利用有限自动机对跳跃模式的组件进行匹配查找;组件的组配过程中先对查找到的组件进行组合分析,然后再对各种组合进行初步筛选和基于策略的优选.初步筛选工作是依据顺序性、唯一性和最大数三条原则进行;而优选工作是根据四个设计的评价参数选择其中最佳组合.实验结果表明,该算法的确能解决字符串有序跳跃模式匹配问题,完全可以适用于句型匹配与主题词跳词匹配.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘功申	上海交通大学电子信息学院	97	848	14.0	25.0
2	王永成	上海交通大学电子信息学院	94	2540	28.0	48.0
3	沈洲	上海交通大学电子信息学院	9	240	7.0	9.0