正则表达式的实现和效率
正则表达式的实现引擎（NFA/DFA)
NFA 是不确定的有限自动机，也就是说在状态的迁移过程中，下一个状态可能有好几种可能，而对于 DFA 确定有限自动机而言，下一个状态只有一种可能。
想起大学时上的一门课，“可计算性理论”，用自动机来证明程序是可以写出来的，我大学有两门典型天书课，这个是一，另一个是 “相对论和量子力学”。
简单来讲，NFA 对应的是正则表达式主导的匹配，而 DFA 对应的是文本主导的匹配。
比如说对于这样的文本和正则表达式，
text ＝ ‘after tonight’
regex ＝ ‘to(nite|nighta|night)’
在 NFA 匹配时候，是根据正则表达式来匹配文本的，从 t 开始匹配 a，失败，继续，直到文本里面的第一个 t，接着比较 o 和 e，失败，正则回退到 t，继续，直到文本里面的第二个 t，然后 o 和 文本里面的 o 也匹配，继续，正则表达式后面有三个可选条件，依次匹配，第一个失败，接着二，三，直到匹配，可以看到回朔发生了两次。
而在 DFA 匹配时候，采用的是用文本来匹配正则表达式的方式，从 a 开始匹配 t，直到第一个 t 跟正则的 t 匹配，但 e 跟 o 匹配失败，回朔，继续，直到文本里面的第二个 t 匹配正则的 t，接着 o o 匹配，n 的时候发现正则里面有三个可选匹配，开始并行匹配，直到文本中的 g 使得第一个可选条件不匹配，继续，直到最后匹配。
可以看到，DFA 匹配过程中文本中的字符每一个只比较了一次，没有回朔的操作，应该是快于 NFA 的，另外，不管正则表达式怎么写，对于 DFA 而言，文本的匹配过程是一致的，都是对文本的字符依次从左到右进行匹配，所以，DFA 在匹配过程中是跟正则表达式无关的，而 NFA 对于不同但效果相同的正则表达式，匹配过程是完全不同的，比如，
to(ni(ght|te)|knight) vs. tonite|toknight|tonight
也正因为 DFA 跟正则表达式无关，也就意味着通过变更正则表达式来提升效率是不可能的，因为不管神马正则表达式，其匹配的过程是一致的。
为什么不用 DFA?
那为什么 DFA 这么快，而大多数工具都采用的是 NFA 的呢，比如 Emacs, vi, grep, awk, sed, python 等。
因为 DFA 不支持很多正则表达式的 feature, 例如，
Group capturing
regex = ‘ab(.+)fg abcdefg’
这个正则表达式里面的 () 代表的是
group，匹配完之后，可以用 \1 来表示该 group
匹配的内容，在这个例子里面，就是 cde，capturing
是在字符串替换等应用中很常用的功能。
Lookaround
text = ‘JeffreyJeff’
regex = ‘(?＝Jeffrey)Jeff JeffreyJeff’
我想匹配文本里面的 Jeffrey 里面的 Jeff, 但不想匹配最后的那个 Jeff,
这个时候，就可以采用 Lookaround 功能，?=
代表的是向后查看，也就是说在匹配到第一个 J 时，先向后看有没有 Jeffrey,
有的话，才开始匹配，没有的话，就跳过。在这个例子里面，第一个 Jeff
完成了匹配，到第二个 Jeff 的时候，因为后面没有
Jeffrey，所以直接跳过，不进行匹配。
Non-greey quantifiers
*, +, {m, n} 等元字符
(metacharacter) 都是贪心版的，比如，
text = ‘<html> <title> Test </title></html>’
如果采用 <.*> 来匹配，因为 *
是贪心的，所以这个正则表达式是匹配了整个文本
<htm...html>，如果采用 *?
这个非贪心元字符，则匹配的是 <html>。
另外还有一些 feature 比如 atomic capturing 等也不支持，在这里就不赘述了。
DFA 之所以可以并行的进行多种可能的匹配，那是因为在匹配前的编译阶段做了工作，它对正则表达式进行了分析，生成了一些 map 关系，在并行匹配过程中才能知道下一个匹配字符是哪个，而这个操作是有 time 和 memory 的消耗的，所以编译阶段，NFA 的效率是高于 DFA 的。
匹配规则
The match that begins earliest wins
text = ’indicates your cat is’
regex = ‘cat’
上面正则表达式匹配的是 indicates 里面的 cat，因为出现的最早。
The standard quantifiers are greey
text = ‘Copyright 2003′
regex = .+([0-9]+)
上面正则表达式的 () 里面匹配的是什么?
是 2003 吗?
不是的，因为 +
是贪心的，所有直接匹配到文本最后，然后发现匹配失败，于是回朔到
3，发现满足 [0-9]+，于是匹配结束，group 匹配的只有 3。
效率
因为 DFA 在匹配过程中是跟正则表达式无关的，所以接下来效率提升方面的讨论只针对 NFA。
我们如何知道一个正则表达式效率低?
匹配失败发生回朔的次数是一个指标，我的 keynote 里面有几个例子来展示对正则表达式进行很简单的改动，就可以大幅减少回朔的次数。
而为什么会发生回朔呢?
因为基本的元字符是贪婪的 (*, +)，因为有选择性的匹配
(|),
于是在匹配过程中每一次这样的选择，都会记录一个回朔点，在匹配失败时，就会回朔到之前一个回朔点，继续匹配，也就是类似于栈的机制，后进先出。
一些提升效率的技巧
对于大部分人来讲，使用正则表达式是想让自己的一些手工劳动变得简单自动高效，所以这里提到的都是类似于 common sense 之类简单的技巧，而如果真的效率很重要，那可能还需要更深入更复杂的方式，在这里就不讨论了。
Alternation is expensive
u|v|w|x|y|z vs. [uvwxyz]
前者每一次匹配失败都要进行回朔，后者一次匹配所有的，如果失败，只发生一次匹配，也就是说，使用前者在全部匹配失败时的回朔次数是后者的六倍。虽然两个方式效果是一样的，能用后者尽量用后者。
Start or end of string/line anchor
如果可以确认行首或者行尾的特征时，尽量使用 ^
$ 元字符，尤其是后面使用 .*
等贪心元字符时。
^T.*
对于这个正则表达式，如果没有
^，那么匹配过程中会对一行中每一个字符进行匹配，看其是否是
T，如果这一行有两万个字符，就回朔两万次，而使用了 ^
之后，只进行一次匹配。
Use non-capturing parentheses (?:)
text = ‘abcdefgh’
regex = ‘ab(.+)e(.+)h
上述正则表达式的两个 () 分别匹配的是 cd 和
fg，但是在很多情况下，使用 ()
只是用来组合元字符，对于其匹配的内容不在乎，那么采用
ab(?:.+)e(?:.+)h，告诉匹配引擎，不需要匹配组，这样可以提升回朔的效率。因为组的匹配会对回朔的效率产生负面影响。
Expose
th(?:is|at) vs. (?:this|that)
显而易见，前者的效率是高于后者的，就跟写程序一样，重复功能可以提出来当作一个函数，在这里，可选择匹配里面重复的内容可以提取到
| 外面，从而减少回朔的次数。
Most likely alternation first
假设我想匹配包含 com net org edu biz 等 url 的后缀，于是我从网上找到所有的可能后缀，然后按字母排序，写出正则表达式如下:
(?:aero|biz|com|...)
但是每一个后缀的域名数量是不一样的，比如 .net .org 的域名很多，但在上面正则表达式的匹配中，因为其很靠后，所以需要匹配失败很多次才能到 .net .org 的匹配，于是按照域名的可能数量来排序
(?:com|edu|org|net|...)
回朔的次数便大大减少了。
Example
假设我需要匹配有效的 IP 地址，例如 10.10.10.10
这样写
[0-9]*\.[0-9]*\.[0-9]*\.[0-9]*
匹配成功，但发现这样的文本 ‘then ...’ 也可以成功。
好，. 前后应该至少有一位数字，并且一行只能有一个 IP
地址，不能出现其他字符，于是改成这样，
^[0-9]+\.[0-9]+\.[0-9]+\.[0-9]+$
OK, 这次 ‘then ...’ 匹配失败了，可是
1234.5678.9101112.131415
匹配成功了，对了，必须至多三位数字的，继续改,
^\d{1,3}\.\d{1,3}\.\d{1,3}\.\d{1,3}$
表的是所有数字，跟 [0-9] 意义一样，成功。可是 900.1.1.1
是个无效 IP 地址，但还是可以匹配的，那我们必须限定数字的取值，有效 IP
地址的每一部分只能是 0-255
的数字，于是我绞尽脑汁，费尽心力折腾出这样一个正则表达式，
^([01]?\d\d?|2[0-4]\d|25[0-5])\.([01]?\d\d?|2[0-4]\d|25[0-5])\.([01]?\d\d?|2[0-4]\d|25[0-5])\.([01]?\d\d?|2[0-4]\d|25[0-5])$
这下圆满了。从后到前看，25[0-5] 代表数字如果开头是 25，那么只能是 250-255；2[0-4]代表如果数字大于 200，那么只能是介于 200 到 249 之间；[01]? 代表所有小于 200 大于 0 的数字。
可是可是，0.0.0.0 也是匹配的，但它是无效 IP 地址。
肿么办?
天无绝人之路，我们还有 Lookaround,
^(?!0+\.0+\.0+\.0+$)([01]?\d\d?|2[0-4]\d|25[0-5])\.([01]?\d\d?|2[0-4]\d|25[0-5])\.([01]?\d\d?|2[0-4]\d|25[0-5])\.([01]?\d\d?|2[0-4]\d|25[0-5])$
(?!0+.0+.0+.0+$) 表示在匹配过程中先往后面看，如果是
0.0.0.0 0.00.0.00 这类 IP
地址，那么直接跳过，不进行后面的一串匹配，也就意味着可以通过 lookaround
功能来剔除匹配中的一些无效匹配。
我们可以说不
为了简单的 IP 地址匹配，我们造出了这么长一个正则表达式，有必要吗?
做任何事情都有一个投入产出比，使用正则表达式，我们是想提高工作效率，减少手工重复劳动，而不是尽量全部使用正则表达式来展示其魔力。
比如对于上面 IP 地址匹配，到这一步
^\d{1,3}\.\d{1,3}\.\d{1,3}\.\d{1,3}$ 是不是就已经够了?
已经限制了 IP 地址的每一部分最多三位数，如果我们在用 Python RE 做这个匹配，那么将每一部分以 group () 的形式返回, 然后在 Python 中比较是不是处于 0-255 之间，是不是来得更快，因为数字比较，任何编程语言都是强项，但正则表达式不是。
-- 记得是四月份的时候在北京 QCon 上看到 Twitter 的 Evan Weaver 在用这个工具，这次试用了一下，是个靠谱的工具 XD
-- Mastering Regular Expression 是本好书，推荐。