[转]正则表达式匹配也可以简单快速(上：原理部分)
发布时间：2015-11-06 栏目：软件算法 评论：0 Comments
正则表达式
正则表达式是一种描述字符串集合的记法。如果一个字符串属于正则表达式描述的集合，那么我们就说正则表达式与这个字符串匹配。
最简单的正则表达式是一个单字符。除了特殊的元字符*+?|,字符都是与它们本身匹配的。为了匹配一个元字符，需要增加一个转义字符”\”,比如\+匹配一个”+”。
两个正则表达式可以通过选择，连接形成一个新的正则表达式。如果e1匹配s，e2匹配t，那么e1|e2就匹配s或者t，e1e2就陪陪st。
元字符*+和?是重复操作符，e1*匹配0个或者更多个字符串e1；e1+匹配一个或者多个；e1?匹配0个或者1个。
操作符优先级，从最弱到最强的绑定顺序，第一个是选择，然后是连接，最后是重复。显式的括号可以被用来改变优先级，就像算术表达式那样。ab|cd等价于(ab)|(cd);ab*等价于a(b*)。
直 到目前为止，前面描述的符号只是传统unix正则表达式符号集的一个子集。这个子集足够描述所有的正则语言。 loosely speaking, a regular language is a set of strings that can be matched in a single pass through the text using on
有一个通用的正则表达式扩展增加了正则表达式的能力，叫做前向引用。一个前向引用比如\1 \2匹配前一个括号里的表达式匹配的字符串。再比如(cat|dog)\1 匹配catcat,dogdog但是并不与catdog,dogcat匹配。实际上含有前向引用的正则表达式已经超出了通常的正则表达式的概念范畴。增加 的前向引用这个功能也带来了很大的花费：最坏情况下，现有已知的最好实现也需要指数级搜索算法，就像perl使用的那个。Perl现在并没有去掉反向引用支持，当然如果正则表达式中不包含前向引用它们实际也可以使用更快的算法，比如上面提到的那个。本文就是介绍这些更快的算法的。
有限自动机
另一种描述字符集的方式是使用有限自动机。有限自动机也被称为状态机，“automaton” 和 “machine”这两个单词意思一致，通常可以相互替换。
作为一个简单的例子，下面这个状态机就可以识别正则表达式a(bb)+a所代表的字符串集合。
有 限自动机，通常用一个环代表一个状态(环里的标号是为了让讨论起来更方便，它们并不是自动机操作的一部分)。当读取字符串的同时，它读一个字符就从一个状 态转换到另一个状态。状态机里有两个特殊状态：开始状态s0和匹配状态s4。开始状态有一个”>”指向它们，匹配状态用一个双环表示。
状 态机一次从输入字符串里读取一个字符，沿着指向状态图中的指针从一个状态转换到另一个状态。比较假设输入字符串是abbbba。当状态机读取第一个字符a 的时候，它处在开始状态s0.然后它沿着指针到达状态s1。之后接着不断读入b到达s2,读入b到达s3，读入b到达s3，最后到达s4。
状态机结束在s4，匹配状态，所以它可以匹配这个字符串。如果状态机结束在一个非匹配状态，那说明它与字符串不匹配。如果在状态机执行过程中的任何一点，针对当前输入字符，没有任何指针了，那麽状态机的执行就可以提前结束了。
现在为止我们看到的都叫做确定性有限自动机(DFA)，因为在任何状态，每个可能的输入字符最多转向一个新状态。我们也可以创建具有多个可能的下一个状态的状态机。比如，下面这个状态机等价于前面那个，但是不是确定性的：
状 态机不是确定性的，因为如果在状态s2读入一个字符b，下一个状态就有多种选择。它可以去状态s1，也可以到达状态s3。因为状态机不能提前看到字符串的剩余部分，也就无法判断哪一个状态是正确决定。在这个情况下，如果能让状态机总是猜的正确的也是很有挑战的。这样的状态机称为非确定性有限自动机 (NFAs或者NDFAs)。如果输入字符串能够通过NFA中的某条路径到达最终的匹配状态，那么就说明字符串与该NFA匹配。
有时如果让NFA包含没有相应输入字符的指针，会很方便，我们称这些指针是未标记的。一个NFA，在任意时刻，不用读入任何输入就可以选择一个未标记的指针到达下一个状态。下面这个NFA等价于前面两个，但是未标记指针使得图形与a(bb)+a的对应关系更明显了：
将正则表达式转换为NFAs
正则表达式与NFAs可以相互进行等价变换：每一个正则表达式都有一个等价的NFA(它们匹配相同的字符集)(现已证明DFAs与NFAs在表达能力上也是 等价的，后面我们也可以看到这点)。有多种方法将正则表达式转换成NFAs。这里描述的方法最初由Thompson在1968年发表在CACM上的。
一个正则表达式的NFAs是逐步由一个子表达式对应的那些NFAs分块构建起来的，不同的操作符具有不同的构建方式。这种NFAs分块没有匹配状态:但是它们倒有一个或者多个悬空指针(未指向任何状态)。整个构建过程将以将这些指针指向一个匹配状态结束。
NFAs对于一个单字符的匹配如下；
对于链接e1e2,需要将e1的终结指针指向e2的状态机的开始状态；
对于选择e1|e2,需要增加一个新的开始状态，这个状态有两个指针指向e1和e2；
对于e?，修改e状态增加一个新状态，并添加一条空指针；
对于e*，使用类似e?相同的改变，但是还要将e的结束指针回指到这个新状态；
对于e+，因为要至少通过e一次，所以做一些改变。如下所示：
数一下上面图中的新状态，可以看到通过这种技术，正则表达式中的每个元字符刚好对应NFA的一个状态(除了括号)。因此最终的NFAs里的状态数目最多等于原始正则表达式串的长度。
观 察上面的图示，我们还可以发现一个特点：每个子片段实际上对外只有开始状态和输出指针是可见的，而上面这些运算，所需要的操作不外乎要么增加一个新的开始 状态，将新片段的输出指针指向另一个片段的开始状态，要么修改原来的输出指针，总之只涉及到输出指针和开始状态的操作。
正如先前描述的NFA例子，很容易消除掉未标记的指针，也很容易一开始就生成不包含未标记指针的NFA。但是引用如果加上这个未标记指针，会让我们的NFA更容易理解和阅读，也能让c代码更简单，所以我们将保留它。
正则表达式搜索算法
现在我们有了一种方法来判断一个正则表达式与一个字符串是否匹配：将正则表达式转换为NFA然后通过字符串输入运行NFA。为了让普通的计算机运行NFA，我们必须找到一种模拟NFA运行的方式。
一种模拟这种完美猜测的方式是首先猜一个选择，如果它不成功则尝试另一个。比如考虑abab|abbb对应的NFA，如果输入abbb,则整个过程如下:
在 step0，NFA首先做一个选择：尝试匹配abab还是abbb?在图中，NFA尝试abab，但是在第3步就失败了。然后NFA尝试另一个选择，到达 step4然后匹配成功。这种回溯策略有一个简单的递归实现但是在成功之前可能会多次读入输入字符串。如果字符串不匹配，在放弃之前状态机就会尝试所有可 能的执行路径。在这个例子里，NFA只尝试了两个路径，但最坏情况下，所有可能的执行路径将会是指数级的，这样会导致极低的运行时间。
一个更有效但是更复杂的方式是通过并行猜测所有的选择来模拟这个猜测的过程。在这种策略里，这个模拟过程允许这个状态机一次处于多个状态。为了处理每个字符，它让所有的状态沿着这个字符对应的指针前进。如下：
状 态机从开始状态以及那些所有从开始状态通过未标注指针可以到达的状态开始。在step1和2，NFA并行地处在两个状态。仅仅在step3减少到一个状 态。多状态策略由于在同一时刻尝试两条可能路径，所有只需要读取输入一次。最坏情况下，NFA每一步可能处在所有的状态，但是这个结果最坏情况下也是与字 符串长度常数级系数关系，所以即使很大的输入字符串也可以在线性时间内处理。与需要回溯的指数级复杂度相比，这已经是一个很大的进步了。这个效率来自于追 踪所有的可达状态集，但是并不是那些可能的路径数目。在一个n节点的NFA里，每一步可能有n个可达状态，但是NFA里可能存在2^n个路径。
所谓的并行执行，不过是一个在NFA状态图中的开始状态开始不断进行广度优先搜索的过程，我们每次记录当前的所有可达状态集合，然后根据下一个输入得到下一个可达状态集合，这样可达状态集合就更新为新计算的这个集合，然后继续进行上面的迭代过程。
留下评论
You must be logged in to post a comment.
