--------------------------虽然在java perl php python ruby里它很慢
Author:Russ Cox Email:rsc January 2007
导引
这篇文章介绍了正则表达式匹配的两种方法。一种被广泛应用在很多语言的标准解释器里，比如perl。另一
个仅仅在一些地方使用，主要是大部分的awk和grep实现里使用。这两个方法在性能上具有很大的区别。
我们使用上标来代表字符重复，比如 a?^3a^3 代表 a?a?a?aaa。上面两个图是使用上面两种方法来匹配模
式串a?^na^n 和字符串a^n。
可以注意到perl需要超过60秒时间来匹配一个29字符的字符串。另一种方法，标注了Thompson NFA的那个，只需要20 ms就可以完成匹配。这个不是一个打印错误，事实就是如此。perl的图时间是以秒为单位，而Thompson NFA的则是以ms为单位：可以看出Thompson NFA实现的速度是perl实现的成百上千倍。图的发展趋势可以看出：Thompson NFA 处理一个100个字符的字符串200ms内就可以完成，但是perl则需要1o^15年。(perl仅仅是使用这种算法的一个最流行的一个语言；上面的图也可能是python,php,ruby或者其他语言。文章后面还会有更细节化的图提供了其他实现的相关数据)
很难相信上面的图形，或许你使用过perl，但是可能从没有碰到正则表达式匹配会匹配的如此之慢。实际上大多数时间，perl的正则表达式匹配是足够快速的。正如图形所展示的，尽管很可能写出上面那样的病态正则表达式会让perl的匹配非常慢。与此不同的是，对于Thompson NFA实现来说，并不存在这样的病态正则表达式。这就引出了另外一个问题，"为什么perl不使用Thompson NFA方法呢"，它可以，它也应该，这也是我们这篇文章剩余内容要说明的。
从历史上来看，正则表达式是计算机科学领域里关于理论如何帮助产生好程序的一个出色的例子。最初它们只是被看做一种简单的计算模型进行理论性的研究，但是Ken Thompson通过他实现的文本编辑器QED把它们介绍给程序员。 Dennis Ritchie 后来又将它移植到GE-TSS系统上的QED。Thompson and Ritchie创建了UNIX，他们又把正则表达式引入了UNIX。直到1970s，正则表达式逐步成为unix领域的关键特点，广泛应用在各种工具里，比如ed,sed,grep,egrep,awk和lex中。
今天，正则表达式已经成为忽略好的理论将导致坏程序的一个良好例证。今天的那些流行工具所使用的正则表达式实现很明显速度低于30年前的那些Unix工具使用的正则表达式匹配引擎。
这篇文章将会回顾那些好的理论：正则表达式，自动机，由Ken Thompson在19世纪60年代中期发明的正则表达式搜索算法。还会将这些理论实现出来，描述了Thompson的一个简单实现。该实现，少于400行c代码，上面图中我们与perl对比的那个程序就是使用的这个实现。它要比perl,python,pcre这些软件使用的实现性能表现得要好。这篇文章主要讨论在现实实现中，理论是如何转化为实际应用的。
正则表达式
正则表达式是一种描述字符串集合的记法。如果一个字符串属于正则表达式描述的集合，那么我们就说正则表达式与这个字符串匹配。
最简单的正则表达式是一个单字符。除了特殊的元字符*+?|,字符都是与它们本身匹配的。为了匹配一个元字符，需要增加一个转义字符"\",比如\+匹配一个"+"。
两个正则表达式可以通过选择，连接形成一个新的正则表达式。如果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 only a fixed amount of memory.新的正则表达式语言(尤其是perl和那些使用perl的)已经添加了很多新的操作符和转义序列。这些新添加的特点，使得正则表达式语言更加准确，虽然显得更复杂，但并没有显得更强大：这些新的正则表达式通常都可以在旧的那里找到更长的等价表示方法。
有一个通用的正则表达式扩展增加了正则表达式的能力，叫做前向引用。一个前向引用比如\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状态图中的开始状态开始不断进行广度优先搜索的过程，我们每次记录当前的所有可达状态集合，然后根据下一个输入得到下一个可达状态集合，这样可达状态集合就更新为新计算的这个集合，然后继续进行上面的迭代过程。
评论