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

摘要：

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

关键词：匹配、近似模式匹配、组合分析、有限状态自动机

所属期刊栏目：16

分类号：TP311(计算技术、计算机技术)

资助基金：国家高技术研究发展计划863计划863-306-ZD03-04-1

在线出版日期：2004-01-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：459-465