分类：
2008-10-15 16:54:16
如果你花费了数小时和正则表达式做斗争，只是为了让它完成它几秒内就可以完成的匹配，那么这篇文章正是为你量身定做的。Cristian Mocanu指出了在什么地方正则模式匹配会发生延迟，并且解释了为什么。然后，他演示了如何做更多的回缩（backtracking）而不是迷失在其中，如何优化贪婪模式和勉强模式（译者注——这个翻译是在网上查到，总感觉不太合适，原文是reluctant quantifier），以及Possessive quantifiers（译者注——这个有的地方称为抢占量子）、独立分组（independent grouping）和环视（look-around）为什么是你的朋友。
编写正则表达式不仅仅是一种技巧，更是一种艺术 ——Jeffrey Friedl
本文中，我将介绍一些正则表达式中使用默认的java.util.regex包的常见缺点。我将解释为什么回缩（backtracking）既是使用正则表达式进行模式匹配的基础，又是应用程序代码中的常见瓶颈；为什么在使用贪婪模式和勉强模式要学会谨慎，以及它是你正则表达式优化的要素。然后我会介绍优化正则表达的技巧，并讨论通过模式匹配引擎运行新的正则表达式时会发生什么。
基于本文的目的，我假设你已经有使用正则表达式的经验，并且对在代码中优化它们抱有很大的兴趣。本文主题包括简单和自动优化优化技巧，以及如何使用抢占量子（possessive quantifiers）、独立分组（independent grouping）和环视（lookarounds）优化贪婪模式和勉强模式（greedy and reluctant quantifiers）。关于Java中正则表达式的介绍，请参考本文的资源部分。
Java模式匹配引擎和回缩（The Java pattern-matching engine and backtracking）
java.util.regex包使用一种称为非确定性的有限自动机（Nondeterministic Finite Automaton，简称为NFA）的模式匹配引擎。之所以称之为非确定性的，是因为当尝试使用输入的字符串匹配一个正则表达式时，每一个字符会因为正则表达式的不同部分而被多次检查。这也是一种在。NET、PHP、Perl、Python和Ruby被广泛使用的引擎。它将大部分的权利交到了程序员手里，提供了宽范围的量词和其他专有的结构如环视（lookarounds），在后面部分将会讨论。
NFA在本质上使用回缩。通常情况下，并非只有一种方式在给定的字符串上使用正则表达式，因此模式匹配引擎会尝试所有情况，直到它宣布失败。为了更好的理解NFA和回缩（backtracking），考虑下面的例子：正则表达式是“sc（ored|ared|oring）x”，输入字符串是“scared”。
首先引擎会寻找“sc”，由于在输入字符串的起始两个字符，因此会立即找到。然后，它会从输入字符串的第三个字符开始尝试匹配“ored”。没有匹配项，它就回到第三个字符，尝试“ared”。找到匹配，于是它继续向前，尝试匹配“x”。不能找到匹配，它将返回第三个字符，寻找“oring”。仍然没有匹配，于是它就返回到输入字符串的第二个字符，开始寻找另外一个“sc”。一直到达输入字符串的结束，它将宣布失败。
回缩的优化小技巧（Optimization tips for backtracking）
通过上面的例子，你已经看到了NFA如何使用回缩进行模式匹配的，同时你也会发现回缩存在的一个问题。甚至在上面十分简单的例子中，引擎为了将输入字符串匹配到正则表达式不得不回退数次。不难想象，如果回缩使失去控制，将会对你的应用程序的性能发生什么样的影响。优化正则表达式的一个重要部分就是最小化回缩的数量。
Java模式匹配引擎有一些可以自由支配的优化规则，并可以自动应用它们。在本文稍后的部分我将会讨论其中的一些规则。不幸的是，你不能总是依赖引擎来优化你的正则表达式。在上面的例子中，正则表达式的确可以相当快地匹配，但是在多数情况中，对于引擎自动优化来说，表达式过于复杂，而输入字符串也过大。
由于回缩，在现实场景中正则表达式有时候会遇到花费数小时完成匹配的情况。更惨的是，引擎会花费比匹配成功更长的时间声明正则表达式不匹配输入字符串。牢记这个重要的事实。当你想要正则表达式的速度时，使用其不能匹配的字符串进行。其中，特别是使用几乎匹配的字符串，因为它们会消耗最长的时间。
[1]
