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

第 19 卷第 12 期 系系 统统 仿仿 真真 学学 报报 Vol.19 No.12 2007年6月 Journal of System Simulation Jun.,2007 2772基于有限自动机的模式匹配算法及其应用研究基于有限自动机的模式匹配算法及其应用研究 李 钢，吴燎原，张仁斌，张佑生(合肥工业大学计算机与信息学院,安徽 合肥 230009)摘摘 要：要：针对质量统计过程控制(SPC)中的异常模式快速匹配问题，提出了基于确定有限自动机基于确定有限自动机(DFA)的模式匹配算法的模式匹配算法，给出了能利用 DFA 进行匹配的基于多维输入数据的模式串定义基于多维输入数据的模式串定义。在分析常规质量控制图中的八种异常模式的基础上，给出了基于基于 DFA 的模式串匹配算法的模式串匹配算法。该算法在企业计算机辅助质量控制系统(CAQCS)中得到了成功的应用,表明它适于解决 SPC 中的异常模式的匹配问题,且有简单、快速和准确的特点。关键词关键词：异常模式匹配；确定有限自动机；多维；常规控制图 中图分类号中图分类号：TP391.9 文献标识码文献标识码：A 文章编号：文章编号：1004-731X(2007)12-2772-04 Research on Algorithm of Finite-automaton-based Pattern Matching and Its Applications LI Gang,WU Liao-yuan,ZHANG Ren-bin,ZHANG You-sheng(College of Computer and Information,Hefei University of Technology,Hefei 230009,China)Abstract: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.Key words:abnormal patterns matching;DFA;multi-dimension;Shewhart Control Charts 引引 言言1 生产过程中实施的质量统计过程控制（Statistical process control,SPC），存在控制图异常模式13的快速匹配问题。如何快速自动匹配异常模式，找出影响生产质量的原因，对过程进行智能诊断是多年来统计过程质量控制领域的一个研究热点。基于过程认知的错误检测技术在 SPC 领域中有着广泛的研究与应用，主要分为定性与定量二类技术，前者主要包括专家系统1与定性趋势分析(Qualitative trend analysis，QTA)2，后者主要包括神经网络3、PCA/PLS（Principal component analysis/partial least squares）4与统计学模式分类器5。这些技术都是在基于过程历史数据的基础上，进行过程的特征提取与模式匹配，有着各自的优缺点。专家系统易于构造，但存在着领域局限性；QTA 建立在严格的数学模型基础上，存在着过程趋势特征提取的难度大、计算复杂等问题；神经网络技术尽管有其自身的优势，但实际应用中存在获取大量样本困难、训练时间较长和准确性不高等问题；PCA/PLS 技术，作为多元的统计学分析技术不需要明确的过程模型，有其优越之处，但在实际中不能有效隔离错误；统计学分类器是建立在统计分布函数已知的基础上的分类 收稿日期：收稿日期：2006-05-19 修回日期：修回日期：2006-06-28 作者简介：李钢作者简介：李钢(1956-),男,山西河津人,研究员,研究方向为计算机控制与人工智能应用、工业控制与信息集成等。技术，如何确定研究对象的统计分布函数是个应用中的难点，面向统计分布自由(Distribution-Free)的分类器还只是研究初始阶段。在实际应用中，需要综合应用多项技术，取长补短，才能取得好的应用效果6。统计过程质量控制是建立在统计学分布规律已知或近似已知的基础上，对过程模型进行监测和诊断的技术，通过统计学的分析，结合其它诊断技术，可以得到满足一定质量控制精度的异常模式(异常趋势)模型。通过对异常模型的分析，可以得到形式化的异常模式串，从而可以利用模式串匹配的技术对过程异常模式进行快速与准确地匹配，来发现过程异常。有限自动机是解决模式串匹配问题的一个十分有效的方法，在编译系统设计、信息检索、网络监测、协议分析等众多领域有着广泛而深入的应用。模式串匹配分为单模式串匹配和多模式串匹配，单模式串匹配算法有 KMP7、BM8、RK9等，多模式匹配算法包括基于确定有限状态机的算法AC10、CW 11等。这些经典算法时间复杂度都是线性或亚线性的，在实际应用中有很多优化的版本。现有的经典匹配算法中输入串都是一维的，要匹配的模式串都是建立在一维输入数据的组合上。然而，实际应用中存在多维输入数据，需要对建立在多维输入数据组合上的模式串进行匹配。为了解决这种复杂的模式串匹配问题，本文从基于多维输入数据的模式串定义出发，提出基于确定有限自动机的模式匹配算法，实现了常规控制图异常模式的快速匹配，在生产实际中取得很好效果。第 19 卷第 12 期 Vol.19 No.12 2007年6月 李 钢,等：基于有限自动机的模式匹配算法及其应用研究 Jun.,2007 27731 基于多维输入数据的模式串定义与基于基于多维输入数据的模式串定义与基于DFA 的匹配的匹配 设12SSSq=?是多维的输入数据集合(,12SSSq?是不同维上的输入数据集合，q 是维数)；,12XXXt?是输入数据集合的分类（即子集），可以理解为组成模式的“字 符”，且0,1tXtXPXtiii=,=，即Xi为的幂集中 的一个元素，且中的任一元素都能映射到,12XXXt?中的至少一个。下面给出基于这种数据的模式串描述性定义。定义：模式串 M 是对一类模式的形式化表示，也就是用有限个“字符”定义一类模式，即12()|pMHHH+?。其中,012121pHHHXXXHpjptj=?且，p 为组 成模式M的“字符”个数，H1,H2,Hp是组成模式串的“字符”。上述定义中的“字符”是进行模式匹配时输入数据中的子集。根据正规表达式与正规集定义12，组成的正闭包 是正规集，因此，模式串 M 可以表示为正规表达式，而正规表达式与有穷自动机是等价的。根据上述模式串定义，对于任何输入的数据，映射到模 式串中的“字符”()|12H HHp?时，由于,01pHpjj=，即 模式串中不存在空字符匹配，所以在进行模式匹配时没有二意性，可以直接用 DFA 实现此类模式串的匹配。当进行多模式串的匹配时，根据上述推断，若组成模式串的“字符”存在互斥关系，则匹配各自模式串的 DFA 可以合并成一个 DFA。这样可以减少实际应用中的 DFA 数量，有利于更快速的多模式串匹配。2 常规质量控制图异常模式的匹配常规质量控制图异常模式的匹配 2.1 常规控制图的异常模式常规控制图的异常模式 常规质量控制图就是根据从控制过程中以近似等间隔抽取数据组成的抽样子组特性值与子组序号相对应获得的图形，它包括一条中心线(CL)，作为所有点特性的基准值，还包含由统计方法确定的两条控制限，位于中心线的各一侧，分别为上控限（UCL）和下控限（LCL）。上、下控制限分别位于中心线的上、下 3距离处。为了便于应用这八种模式，将控制图分为6个区，分布在中心线的两侧，关于中心线对称，其标号分别为+A，+B，+C，-C，-B，-A，每个区的宽度为，如图 1 所示。根据文献13变差的可查明原因的八种异常模式分别定义如下：模式 1：一个点落在 A 区以外；模式 2：连续 9 点落在中心线同一侧；模式 3：连续 6 点递增或递减；模式 4：连续 14 点中相邻点交替上下；模式5：连续3 点中有2 点落在中心线同一侧的B 区以外；模式6：连续5 点中有4 点落在中心线同一侧的C 区以外；模式 7：连续 15 点落在中心线两侧的 C 区内；模式 8：连续 8 点落在中心线两侧且无一在 C 区内。2.2 匹配异常模式的数学建模匹配异常模式的数学建模 2.2.1 输入数据集定义输入数据集定义 由抽样点的数据落在控制图中的位置与数据之间的关系，定义输入数据集合1231,SSSSSU SD=，,2SABC D=，3,SBG SM=，各维数据的意义为:(SU：上侧，SD：下侧；A：点落在 A 区，B：点落在 B 区，C：点落在 C 区，D：点落在A、B、C 区之外；BG：当前点与上点连线上升，SM：当前点与上点连线下降)。设输入的第一个点的S3维的值为BG。2.2.2 模式串定义模式串定义 设 X1,X2,X12 是信号集合的分类，现定义组成模式串的“字符”如表 1 所示，前述八种异常模式的模式串定义如表 2 所示。表表 1 组成模式串的组成模式串的“字符字符”定义定义 X1=SU,SDDBG,SM X7=SDA,DBG,SM X2=SUA,B,C,DBG,SM X8=SU,SDB,CBG,SM X3=SDA,B,C,DBG,SM X9=SU A,B,DBG,SM X4=SU,SDA,B,C,DBG X10=SD A,B,DBG,SM X5=SU,SDA,B,C,DSM X11=SU,SDCBG,SM X6=SUA,DBG,SM X12=SU,SDA,B,DBG,SM表表 2 控制图八种异常模式的模式串定义控制图八种异常模式的模式串定义 异常模式模式串定义 模式1 M1H11,H11=X1 模式2 M2H219|H229,H21=X2,H22=X3 模式3 M3H315|H325,H31=X4,H32=X5 模式4 M4H41(H42H41)6|(H42H41)6H42,H41=X4,H42=X5 模式5 M5H512|H522|H51H53H51|H51H52H51|H52H53H52|H52H51H52,H51=X6,H52=X7,H53=X8 模式6 M6H614|H624|H61H63H613|H612H63H612|H613H63 H61|H62H63H623|H622H63H622|H623H63H62,H61=X9,H62=X10,H63=X11 模式7 M7H7114,H71=X11 模式8 M8H818,H81=X12 2.2.3 输入数据集合到组成模式串的“字符”的映射关系输入数据集合到组成模式串的“字符”的映射关系 根据上述定义，输入数据集合到组成模式串的“字符”的映射关系如表 3 所示。表中 F0,F1,F2,F3,F4,F5 为标志位，其值由经过处理的输入数据根据映射关系映射产生。2.3 匹配异常模式的匹配异常模式的 DFA 为了描述的方便，给出如下两个约定：约定 1：所有 DFA 中某个状态下对输入的“字符”不能匹配时，都转换到 0 状态；约定2：模式 3、模式 4 的匹配都从第二个输入数据开始。UCLCLLCL+A-A-B-C+C+B图1 常规控制图分区 第19卷第12期 Vol.19 No.12 2007年6月 系 统 仿 真 学 报 Jun.,2007 2774表表 3 输入数据集合到组成模式串的“字符”的映射关系输入数据集合到组成模式串的“字符”的映射关系 序号 输入数据 F0 F1 F2 F3 F4 F5 1 SU,A,BG X2 X4 X6 X9 X12 2 SU,A,SM X2 X5 X6 X9 X12 3 SU,B,BG X2 X4 X8 X9 X12 4 SU,B,SM X2 X5 X8 X9 X12 5 SU,C,BG X2 X4 X8 X11 6 SU,C,SM X2 X5 X8 X11 7 SU,D,BG X1 X2 X4 X6 X9 X12 8 SU,D,SM X1 X2 X5 X6 X9 X12 9 SD,A,BG X3 X4 X7 X10 X12 10 SD,A,SM X3 X5 X7 X10 X12 11 SD,B,BG X3 X4 X8 X10 X12 12 SD,B,SM X3 X5 X8 X10 X12 13 SD,C,BG X3 X4 X8 X11 14 SD,C,SM X3 X5 X8 X11 15 SD,D,BG X1 X3 X4 X7 X10 X12 16 SD,D,SM X1 X3 X5 X7 X10 X12 现举例说明，控制图异常模式 6 的 DFA，如图 2 所示(其它模式的 DFA 可根据各自的模式串定义构造)。上述确定有限自动机的状态图，完整表述了对于每个输入“字符”的模式 6 的匹配过程。例如图 2 中的第一部分，0135M6246H61H61H61H62H62H62H61H62H63173410902H62H63H61H62H63H61H63H62284391001H61H63H62H61H63H62H63H6131154101302H62H63H61H62H63H61H63H624126591401H61H63H62H61H63H62H63H61515M64101302H62H63H61H62H63H61H63H62616M6391401H61H63H62H61H63H62H63H61 图2 常规控制图异常模式6的DFA 表述了连续四个点落在上侧 C 区以外或连续四个点落在下侧 C 区以外的模式匹配过程。再如，如果输入的数据映射到“字符”的序列为 H63H61H62H63H62H62H62，则状态转换序列为 0171046M6。2.4 异常模式的匹配算法异常模式的匹配算法 基于 DFA 的控制图异常模式匹配算法的步骤如下：Step1：根据统计学知识与特征提取技术，构造异常模式，定义异常模式串；Step2：构造匹配异常模式串的 DFA；Step3：离散化当前检测到的样本数据，并映射为一个或多个组成异常模式串的“字 符”，即置表 3 中的标志位；Step4：根据当前的“字符”，顺序利用各个 DFA 来匹配相应的异常模式，如果出现一个异常模式，指示生产过程异常，否则转 Step2。下面结合简单实例来说明算法过程。例如，设控制图参数为：CL=50.000，UCL=50.150，LCL=49.850，=0.050。离散化生产过程检测到的样本数据并得到其到“字符”的映射，如表 4 所示。各个 DFA 所处状态如表 5 所示(DFA7、DFA8 合并为DFA9)。因此，可以判断上述样本数据序中存在异常模式 6，即连续 5 点中有 4 点落在中心线同一侧的 C 区以外。表表 4 生产过程检测到的样本数据及其到生产过程检测到的样本数据及其到“字符字符”的映射的映射 检测数据标志位50.00150.05349.997 50.056 50.05150.102离散数据SU,C,BGSU,B,BGSD,C,SMSU,B,BGSU,B,SMSU,A,BGF0 H12 H12 H12 H12 H12 H12 F1 H21 H21 H22 H21 H21 H21 F2 H31 H31 H32 H31 H32 H31 F3 H53 H53 H53 H53 H53 H51 F4 H63 H61 H63 H61 H61 H61 F5 H71 H81 H71 H81 H81 H81 表表 5 各各 DFA 所处状态所处状态 检测数据 状态 50.00150.053 49.997 50.056 50.051 50.102DFA1 0 0 0 0 0 0 DFA2 1 3 2 1 3 5 DFA3 1 3 2 1 2 1 DFA4 1 3 2 1 2 1 DFA5 0 0 0 0 0 1 DFA6 0 1 9 3 5 M6DFA9 1 0 1 0 2 4 2.5 异常模式匹配算法在实际系统中的应用异常模式匹配算法在实际系统中的应用 上述算法在我们开发的“汽车关键零部件计算机辅助质量控制系统”项目得到成功的应用，并在江淮汽车公司零部件生产线上取得很好的实用效果。实际系统中存在的异常模式主要有：连续上升、连续下降、越界、周期变化、向上趋势和向下趋势等。所有异常模式的出现都预示着生产过程出现了异常变化，导致不合格品出现的几率增加。具体在实际应用中，连续上升、连续下降异常模式的出现，表明生产设备如刀具、齿轮和转动轴等出现磨损老化，预示零件的加工误差在累计，可第19卷第12期 Vol.19 No.12 2007年6月 李 钢,等：基于有限自动机的模式匹配算法及其应用研究 Jun.,2007 2775能导致不合格品的出现；越界异常模式的出现，表明生产设备异常，可直接导致不合格品的出现；周期变化异常模式表明设备性能或加工工艺在时序上出现异常波动，可能导致大量不合格品的出现；向上趋势或向下趋势异常模式的出现，表明过程能力的衰退，要及时对生产过程进行修正。在实施 SPC 的在线检测系统中，采样频率对判异结果有较大影响。频率过高，系统过于敏感，导致不必要的调整加工工艺；频率过低，可能出现漏报等现象。这些，都涉及到常规控制图的第 I 类错误、第 II 类错误的问题。为了尽量避免这两类错误的发生，在试生产阶段或工艺调整阶段，采样频率应当高点；工序能力趋于稳定时，采样频率应当低点。在线监控时，采样频率受数据处理时间的限制，数据处理时间越短采样频率可选范围越大。上述异常模式匹配算法针对当前采样数据进行异常模式匹配时间复杂度显然为(n 为要匹配的异常模式个数)，在低性能的处理器上也能在 ms级完成匹配。由于模式的确定性和有限性，判异动作具有很高的时效性，因此在实际应用中可很好地满足实时性要求。在分析控制图中的异常模式时，可以在控制图显示区域单击鼠标右键，在快捷菜单中点击“匹配判异模式，智能判断”选项，即可调用控制图类中的模式匹配类的对象方法进行在线的判异，并标出异常点，如图 3 所示。5 10 15 20 25 30 子样号 标准差 0.0180.0140.0100.0060.002 图3 模式匹配算法的应用 3 结论结论 本文根据实际应用的需要，提出针对多维输入数据进行多模式匹配的数学建模思想，针对复杂多模式匹配，给出用DFA 匹配的数学准则，并针对 SPC 体系中的控制图八种异常模式匹配问题，给出性能优化算法，在质量控制系统中得到很好的应用。实践证明，这种匹配算法的计算复杂度低，快速准确，完全能满足实际需要。参考文献参考文献:1 Leung D,Romagnoli J.Dynamic probabilistic model based expert system for fault diagnosis J.Computers and Chemical Engineering(S0098-1354).2000,24(11):2473-2492.2 Rengaswamy R,Hagglund T,Venkatasubramanian V.A.qualitative shape analysis formalism for monitoring control loop performance J.Engineering Applications of Artificial Intelligence(S0952-1976).2001,14(1):23-33.3 Wani M A,Pham D T.Efficient control chart pattern recognition through synergistic and distributed artificial neural networks J.Proceedings of the Institution of Mechanical Engineers(S1464-4207).1999,213:157-169.4 Li W,Yue H,Valle-Cervantes S,Qin S.Recursive PCA for adaptive process monitoring J.Journal of Process Control(S0959-1524).2000,10(5):471-486.5 Johnston L P M,Kramer M A.Probability density estimation using elliptical basis functions J.American Institute of Chemical Engineers Journal(S0001-1541).1994,40(10):1639-1649.6 Venkatasubramanian V,Raghunathan Rengaswamy,Surya N Kavuri et.al.A review of process fault detection and diagnosis.Part III:Process history based methods J.Computers and Chemical Engineering(S0098-1354).2003,27(3):327-346.7 Knuth D E,Morris J H,Pratt V R.Fast pattern matching in strings J.SIAM J Comput(S0097-5397).1977,6(2):323-350.8 Boyer R S,Moore J S.A fast string searching algorithm J.Communications of the ACM(S0001-0782).1977,20(10):762-772.9 Karp R M,Rabin M O.Efficient randomized pattern-matching algorithms J.IBM Journal Res Dev(S0018-8646).1987,31(2):249-260.10 Aho A V,Corasick M J.Efficient String Matching:An Aid to Bibliographic Search J.Communications of the ACM(S0001-0782).1975,18(6):333-340.11 Commentz-Walter Beate.A string matching algorithm fast on the averageC/Proceedings of the 6th Colloquium on Automata,Languages and ProgrammingSpringer-Verlag,London,UK,1979:118-132.12 史杏荣,万炳奎.编译程序设计原理与构造技术M.合肥:中国科学技术大学出版社,1998:38-66.13 GB/T4091-2001.常规控制图 S.中国标准出版社.(上接第 2771 页)4 结论结论 本文展示了一个用 Simulink 环境实现的船舶自动避碰系统模型，并提出了工作于这个模型框架下的经验避碰方法，仿真结果表明系统实现了自动避碰决策并具有一定的智能程度。尽管只是初步实现单船避碰，但是新仿真环境已经显露出一些值得注意的特点，比如其快速建模能力，可以容易地为模型引进一些新的避碰方法，Stateflow 澄清复杂系统和处理复杂逻辑问题的能力，可以用以应付变化多端的会遇局面。这些特点对于目前还需更多突破和交流的避碰自动化研究领域，将是很有帮助意义的。参考文献：参考文献：1 鹤田三郎.船舶航行专家系统的基础研究C/日本航海学会,1987,77:43-46.2 Coenen F P,Sneaton G P,Bole A G.Knowledge-based collision avoidance J.The Journal of Navigation,1989,42(1):107-116.3 赵劲松,王逢辰.船舶避碰学原理M.大连:大连海事出版社,1999.4 Fossen T I.Guidance and Control of Ocean Vehicles M.New York:Wiley,1994.5 姚杰.未来的船舶避碰自动化系统 C/航海技术现状与发展趋势论文集.中国航海学会,2001:3-5.6 Lluch D.Building Multi-UAV simulation Methods C/AIAA MST Conference and Exhibit 5-8 August 2002,Monterey,California,AIAA-2002 4495.7 The MATHWORKS,INC.Stateflow for use with Simulink Users Guide,2003.DB/OL