有穷自动机在字符串匹配中的应用

计算机研究与发展DOI:10.7544/issn1000-1239.2014.20121044JournalofComputerResearchandDevelopment51(1):1-16,2014收稿日期：2015-06-20基金项目：如有国家或省部级基金资助，请写上正确基金项目名称和编号有穷自动机在字符串匹配中的应用侯丹11北京林业大学信息学院，北京100083([e-mail])TheApplicationofDeterministicFiniteAutomatainStringMatchingHouDan11(SchoolofInformationScience&Technology,BeijingForestryUniversity,Beijing100083)AbstractThestringmatchisoneofthemainresearchissuesinthefieldofcomputerscience.Itsefficiencyhasinfluenceonanumberofareas.Forinstance,onlineinformationsearch.Sothat,itisnecessarytodevelopaalgorithmwithhightimecomplexityandhighspacecomplexity.Alsothealgorithmissimpleandpractical.Basedontheideaofautomaticmachines,Thearticlewilldescribetheapplicationofdeterminantfiniteautomaticinstringmatching.Thetechnologyisimplementedwithstructuresoftreeandgraphdata.Itcansolvethisprobleminsomeextent.Also,itcanavoidredundantspace.KeywordsDFA;compiler;tree;stringmatching摘要字符串匹配是计算机科学领域内热门的课题，其效率影响着搜索等多个领域，很有必要研发一款时间、空间复杂度高，有简单实用的算法。基于自动机的思想，将确定有穷自动机应用于字符串匹配上，用树和图的数据结构进行实现，能一定程度上解决这个问题。而且还避免比较中的冗余的提高空间。关键词确定的有穷自动机；编译原理；树；字符串匹配中图法分类号TP391字符串匹配是计算机科学中最古老、研究最广泛的问题之一。一个字符串是一个定义在有限字母表∑上的字符序列。例如，ATCTAGAGA是字母表∑={A,C,G,T}上的一个字符串。字符串匹配问题就是在一个大的字符串T中搜索某个字符串P（子字符串）的所有出现位置。其中，T称为文本，P称为模式，T和P都定义在同一个字母表∑上。它的应用包括生物信息学、信息检索、拼写检查、语言翻译、数据压缩、网络入侵检测。例如在生物信息学中，启动子有助于研究者从数以亿计的ACGT序列中快速定位内含子的起始位置，这些启动子中较常见的有TATA序列。它常常出现在CAATCT序列之后。它们之间并不是连续出现，而是间隔了30-50个通配符。又比如在信息检索中，一个挑战性的任务是，搜索出由用户自定义的模式对应在文本中的匹配位置，这种模式很可能带有通配符。在上述应用背景下，一种更加灵活的带有通配符的模式串应运而生。1.字符串匹配相关研究介绍串匹配算法虽然发展了几十年，然而非常实用的算法是今年才发现。串匹配问题的研究存在理论研究和实际应用的脱节。在字符串匹配这个领域，潜心研计算机研究与发展DOI:10.7544/issn1000-1239.2014.20121044JournalofComputerResearchandDevelopment51(1):1-16,2014究算法的人开发出一些看起来很“美妙”的算法和技术，都是具有很好的时间和空间复杂度。而开发人员只追求实际应用中尽可能快的算法。两者之间从不注意对方在干什么。将理论研究和实际应用结合的算法(如BNDM算法)只是近年才出现。在实际应用中常常很难找到适合需求的算法——这样的算法实际上是存在的，但是只有资深专家才比较了解。考虑如下情况，一位软件开发人员，或者一位计算生物学家，或者一位研究人员，又或者一位学生，对字符串匹配领域并没有深入了解，可是现在需要处理一个文本搜索问题。那些汗牛充栋的书籍使得阅读者淹没在各种匹配算法的海洋中，却没有足够的知识选择最适用的算法。最后，常常导致这样的局面：选择一种最简单的算法加以实现。这往往导致很差的性能，从而影响整个开发系统的质量。更糟糕的是，选择了一个理论上看起来很漂亮的算法，并且花费了大量精力去实现。结果，却发现实际效果和一个简单算法差不多，甚至还不如简单算法。因此，应该选用一种“实用”算法，即在实际应用中性能较好，并且一个普通程序员能在几小时内完成算法的实现代码。另外，在字符串匹配研究领域中，一个人所共知的事实是“算法的思想越简单，实际应用的效果越好”。找到合适的低成本，高效率的字符串匹配算法也不容易。在Fischer和Paterson于1974年将通配符*引入模式匹配问题之后，如何将通配符与传统的模式匹配有效结合是研究的重点。带有通配符的串匹配进入了人们的视野。比较常用的是KMP算法。KMP算法是通过分析模式串，预先计算每个位置发生不匹配的时候，所需GOTO的下一个比较位置，整理出来一个next数组，然后在上面的算法中使用。传统的串匹配算法和技术还有许多，可以概括为前缀搜索、后缀搜索、子串搜索。代表算法有KMP，Shift-And，Shift-Or，BM，Horspool，BNDM，BOM等。所用到的技术包括滑动窗口、位并行、自动机、后缀树等。2.确定有穷自动机相关知识的介绍有穷自动机，或有穷状态的机器，是描述（或“机器”）特定类型算法的数学方法。特别地，有穷自动机可用作描述在输入串中识别模式的过程，因此也能用作构造扫描程序。DFA（英文全称：DeterministicFiniteAutomaton）是专指确定型的有穷自动机，在其输入确定的情况下，相对应的输出是确定的。一个确定的有穷自动机M是一个五元组[1]：M=（K，Σ，f，S，Z）其中1.K：有穷非空的状态集合；2.Σ：有穷非空的输入符号字母表；3.f：转换函数，是在K×Σ→K上的映像，即，如f(ki,a)=kj,(ki∈K,kj∈K)就意味着，当前状态为ki，输入符为a时，将转换为下一个状态kj，我们把kj称作ki的一个后继状态；4.S∈K是唯一的一个初态；5.ZK是非空的终态集合。用DFA的思想描述程序中的一些状态，具有形象、严密、清晰地优点。DFA可以用状态转换图、状态矩阵等方式表示，并且有严格的逻辑语言的限制。在应用于字符串匹配中，能够清晰地分出不同的匹配状态，能减少很多不必要的浪费。3.用有穷自动机构造图、树结构进行字符串匹配3.1单模式串匹配的情况DFA可以看成是一个图的数据结构，可以按照图的思想构造出节点和边。在这里，我们把DFA的每个状态当成是图结构中的每个节点，把DFA中输入对应的状态跳转当成是图结构中的边。由于DFA存在着状态的确定性，此图具有以下特点：1.每条边都会指向确定的一个节点。2.不会存在同一个节点同样的输入对应两个或两个以上的边。3.允许一条边的起点和终点是一个节点的情况。4.允许没有输出的节点，此节点即为终结节点。5.允许节点没有对应的数值6.只允许出现一个没有输入的节点，该节点是起始节点。7.每个节点可以有多个输入，也可以有多个输出。按照如下方式构造自动机：1.初始节点对应子字符串的start2.把模式串每个字符当做一个输入，依次排出各个输入字符，每输入一个字符跳到下一个状态。3.以此类推，直至跳转到最后一个状态，最后一个状态为终结状态。如图所示，本图给出了一个终结状态为“nano”计算机研究与发展DOI:10.7544/issn1000-1239.2014.20121044JournalofComputerResearchandDevelopment51(1):1-16,2014的自动机[2]。emptynnanannanoananstartothernaotherotherotheranyn图1终结状态为“nano”的自动机此自动机构造好之后，母串的字符串，可以通过此自动机“跑”一遍，如果依次输入各字符，在自动机上走一遍，依次经过各状态最终跳转至终结状态，则该模式串与母串字符串匹配成功，母串包含相应的模式串，否则，匹配失败。3.2多模式串匹配的情况图结构进行设计，结构较为简单，随意，实现方便。针对多模式串匹配的特点，我们可以采用树的数据结构。同样的，在这里，我们把DFA的每个状态当做是树结构中的每个节点，把DFA中输入对应的状态跳转当做是树结构中的边[3]。树形结构的构造特点，做一些改进：1.每条边都会指向确定的一个节点。2.不会存在同一个节点同样的输入对应两个或两个以上的边。3.允许一条边的起点和终点是一个节点的情况。4.允许没有输出的节点，此节点即为终结节点。5.只允许出现一个没有输入的节点，该节点是根节点。6.只允许根节点没有相应的数值。7.每个节点可以有只能有一个输入，但可以有多个输出。按照如下方式构造自动机：1.初始节点对应子字符串的start。2.先按照3.1中的方法构造第一个模式串，第一个模式串的输入接在start之下。3.把模式串每个字符当做一个输入，依次排出各个输入字符，每输入一个字符跳到下一个状态。直至跳转到最后一个状态，最后一个状态为终结状态。4.判断是否有下一个模式串，如果有，按照5的方法再构造下一个模式串。5.把本模式串当做输入，从start开始，依次读入各个字符，当遇到模式串中的字符在树中没有输入与之对应时，从此节点新建一个分支，继续3的步骤，创建下面的树枝。6.直至创建完所有的模式串。如图2所示，举两个例子[4]，构造两个多模式串的树状结构。4个模式串babaabaaabaaabbroot模式串abcdabcabeaebcbebceecbaebdcee母串：kbaabce图2两个多模式串的树状结构的例子此自动机构造好之后，仍然是将母串在自动机上走一遍，至终结状态，则匹配成功，该终止节点的字符串即包含在母串中，否则，匹配失败。通过观察发现，此树状结构有很多不错的性质，树中的每一个节点都对应着某个模式串的前缀，母串的串每走到一个节点，就意味着和这个节点多对应的前缀相同。4.复杂度分析由于树形结构的应用是比较广泛的，在这里只讨论树形结构构造的算法复杂度。通过复杂度的计算，可以看出将n个模式串插入到一棵这样的树中的时间复杂度为O(∑length(i))，length(i)表示第i个模式串的长度。创建这树的效率还是很高的[6]。而母串在树形结构上遍历的效率就更高了，最好情况是每个模式串第一个就出现匹配错误复杂度是O(n)，最坏情况也是O(log(n))[5]。由此可见，此技术运用在字符串匹配上还是很可行的。5.技术上的拓展以上实现过程与其他算法相比，还存在一些问题。如，对比较过程中冗余的处理。在此，可以对其进行一定的拓展。采用构造NEXT数组和前缀指针的方法。借鉴KMP计算机研究与发展DOI:10.7544/issn1000-1239.2014.20121044JournalofComputerResearchandDevelopment51(1):1-16,2014算法的优点------避免了指针回溯，仿照KMP算法，建立NEXT数组，对树上的每一个加点建立一个前缀指针，从根节点延边到某节点的过程中，我们可以得到一个字符串w，该节点的前缀指针即为，指向树中出现过w的最长后缀。在遍历的过程中，如果该节点向下走，没有输入与之对应，则访问其前缀指针指向的节点进行判断，若还没有，则递归的上溯到他的前缀节点，以此类推。如果遍历过程中遇到了