基于有限自动机的模式匹配算法及其应用研究new

《基于有限自动机的模式匹配算法及其应用研究new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第19卷第12期系统仿真学报©Vol.19No.122007年6月JournalofSystemSimulationJun.,2007基于有限自动机的模式匹配算法及其应用研究李钢，吴燎原，张仁斌，张佑生(合肥工业大学计算机与信息学院,安徽合肥230009)摘要：针对质量统计过程控制(SPC)中的异常模式快速匹配问题，提出了基于确定有限自动机(DFA)的模式匹配算法，给出了能利用DFA进行匹配的基于多维输入数据的模式串定义。在分析常规质量控制图中的八种异常模式的基础上，给出了基于DFA的模式串匹配算法。该算法在企业计算机辅助质量控制系统(CAQCS)中得到了成功的

2、应用,表明它适于解决SPC中的异常模式的匹配问题,且有简单、快速和准确的特点。关键词：异常模式匹配；确定有限自动机；多维；常规控制图中图分类号：TP391.9文献标识码：A文章编号：1004-731X(2007)12-2772-04ResearchonAlgorithmofFinite-automaton-basedPatternMatchingandItsApplicationsLIGang,WULiao-yuan,ZHANGRen-bin,ZHANGYou-sheng(CollegeofComputerandInformation,HefeiUniversi

3、tyofTechnology,Hefei230009,China)Abstract:Analgorithmofpatternmatchingwasproposedbasedondeterminatefiniteautomaton(DFA)fortheproblemofquickabnormalpatternsmatchinginqualitystatisticalprocesscontrol(SPC).Thepatternstringsbasedonmulti-dimensionalinputdataweredefinedwhichcanbematchedbyD

4、FA.AfteranalyzingtheeightabnormalpatternsinShewhartControlCharts,thematchingalgorithmbasedonDFAforpatternstringsofthemweregiven.Thealgorithmwassuccessfullyappliedtoacomputerassistantqualitycontrolsystem(CAQCS),whichshowsthatthealgorithmissuitabletosolvetheproblemsofabnormalpatternsma

5、tchinginSPCandhasthedesirablecharacteristicsofsimplicity,highspeedandnicety.Keywords:abnormalpatternsmatching;DFA;multi-dimension;ShewhartControlCharts1技术，如何确定研究对象的统计分布函数是个应用中的难引言点，面向统计分布自由(Distribution-Free)的分类器还只是研生产过程中实施的质量统计过程控制（Statistical究初始阶段。在实际应用中，需要综合应用多项技术，取长processcontrol

6、,SPC），存在控制图异常模式[13]的快速匹配问[6]补短，才能取得好的应用效果。题。如何快速自动匹配异常模式，找出影响生产质量的原因，统计过程质量控制是建立在统计学分布规律已知或近似对过程进行智能诊断是多年来统计过程质量控制领域的一已知的基础上，对过程模型进行监测和诊断的技术，通过统计个研究热点。学的分析，结合其它诊断技术，可以得到满足一定质量控制精基于过程认知的错误检测技术在SPC领域中有着广泛度的异常模式(异常趋势)模型。通过对异常模型的分析，可以的研究与应用，主要分为定性与定量二类技术，前者主要包得到形式化的异常模式串，从而可以利用模式串匹配的技术[1

7、]括专家系统与定性趋势分析(Qualitativetrendanalysis，对过程异常模式进行快速与准确地匹配，来发现过程异常。[2][3]QTA)，后者主要包括神经网络、PCA/PLS（Principal有限自动机是解决模式串匹配问题的一个十分有效的[4]componentanalysis/partialleastsquares）与统计学模式分类方法，在编译系统设计、信息检索、网络监测、协议分析等[5]器。这些技术都是在基于过程历史数据的基础上，进行过众多领域有着广泛而深入的应用。模式串匹配分为单模式串程的特征提取与模式匹配，有着各自的优缺点。专家系统易匹配

8、和多模式串匹配，单模式串