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

作     者：沈洲 王永成 刘功申 

作者机构：上海交通大学电子信息学院上海200030 

基　　金：国家 8 6 3计划 (编号 :86 3- 30 6 - ZD0 3- 0 4 - 1)资助项目 

出 版 物：《数据采集与处理》 (Journal of Data Acquisition and Processing)

年 卷 期：2001年第16卷第4期

页      码：459-465页

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

主 题 词：有限状态自动机 字符串 模式匹配 计算机 有序跳跃模式 

学科分类：1305[艺术学-设计学类] 0810[工学-土木类] 13[艺术学] 08[工学] 081104[081104] 0804[工学-材料学] 0835[0835] 081101[081101] 0811[工学-水利类] 0812[工学-测绘类] 

核心收录：

D　O　I：10.3969/j.issn.1004-9037.2001.04.013

馆 藏 号：203618871...