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

Research on Algorithm of Finite-automaton-based Pattern Matching and Its Applications

作　　者：李钢[1] 吴燎原[1] 张仁斌[1] 张佑生[1] 

机构地区：[1]合肥工业大学计算机与信息学院,安徽合肥230009

出　　处：《系统仿真学报》2007年第12期2772-2775,共4页Journal of System Simulation

摘　　要：针对质量统计过程控制(SPC)中的异常模式快速匹配问题,提出了基于确定有限自动机(DFA)的模式匹配算法,给出了能利用DFA进行匹配的基于多维输入数据的模式串定义。在分析常规质量控制图中的八种异常模式的基础上,给出了基于DFA的模式串匹配算法。该算法在企业计算机辅助质量控制系统(CAQCS)中得到了成功的应用,表明它适于解决SPC中的异常模式的匹配问题,且有简单、快速和准确的特点。An algorithm of pattern matching was proposed based on determinate finite automaton （DFA ） for the problem of quick abnormal patterns matching in quality statistical process control （SPC）, The pattern strings based on multi- dimensional input data were defined which can be matched by DFA. After analyzing the eight abnormal patterns in Shewhart Control Charts, the matching algorithm based on DFA for pattern strings of them were given. The algorithm was successfully applied to a computer assistant quality control system （CAQCS）, which shows that the algorithm is suitable to solve the problems of abnormal patterns matching in SPC and has the desirable characteristics of simplicity, high speed and nicety.

关 键 词：异常模式匹配 确定有限自动机 多维 常规控制图 

分 类 号：TP391.9[自动化与计算机技术—计算机应用技术]