全面考察回溯

04-13Ctrl+D 收藏本站

关灯小中大繁直达底部

A Global View of Backtracking

从局部来看，回溯就是倒退至未尝试的分支。这很容易理解，但是回溯对整个匹配影响并不容易理解。在本节，我们会详细考察回溯在匹配成功和不成功时的各种细节，尝试从中发掘出一些东西。

先来仔细看看前一章的几个例子，在165页，我们把「＂.＊＂」应用到下面的文本：

The name ＂McDonald\'s＂ is said ＂makudonarudo＂ in Japanese

匹配过程如图6-3所示。

正则表达式会从字符串的起始位置开始依次尝试每个字符，但是因为开头的引号无法匹配，此后的字符也不能匹配，直到尝试进行到标记位置 A。接着尝试表达式的其他部分，但是传动装置（☞148）知道如果这种尝试不成功，整个表达式可以从下一个位置开始尝试。

然后「.＊」匹配直到字符串末尾，此时点号无法匹配，所以星号停止迭代。因为「.＊」匹配成功可以不需要任何字符，所以在此过程中引擎记录了46个状态供回溯。现在「.＊」停止了，引擎从最后保存的状态开始回溯，在处开始尝试。

也就是说，我们在字符串的末尾尝试匹配表示结束的双引号。不过，在这里双引号同样无法匹配，所以尝试仍然失败。然后引擎继续回溯、尝试，结果同样是无法匹配。

图6-3：「＂.＊＂」的成功匹配过程

引擎倒过来尝试（最后保存的状态排在最先）从A到B保存的状态，首先是从B到C。在进行了多次尝试之后到达这个状态：正则表达式中的对应字符串中的·in·Japa…，也就是C所标注的位置。此时匹配成功，于是我们在D位置得到全局匹配。

这就是传统型NFA的匹配过程，剩下的未使用状态将被抛弃，报告匹配成功。

More Work for a POSIX NFA

我们已经介绍过，POSIX NFA的匹配是“到目前为止最长的匹配”，但是仍然需要尝试所有保存的状态，确认是否存在更长的匹配。我们知道，对本例来说，第一次找到的匹配就是最长的，但正则引擎需要确认这一点。

所以，在保存的所有状态中，除了两个能够匹配双引号的可能之外，其他都会在尝试后立即被放弃。所以，尝试过程D-E-F和F-G-H类似B-C-D，只是F和H会被放弃，因为它们匹配的文本比D的要短。

在I位置能进行的回溯是“启动驱动过程，进行下一轮尝试（bump-along and retry）”。不过，因为从A位置开始的尝试能够找到匹配（实际上是三个），POSIX NFA引擎最终停下来，报告在D位置的匹配。

Work Required During a Non-Match

我们还需要分析无法匹配时的情况。我们知道「＂.＊＂！」无法匹配范例文本，但是它在匹配过程中仍然会进行许多工作。我们将会看到，工作量增大了许多。

图6-4说明了这些。A-I序列类似图6-3。区别在于，在位置D无法匹配（因为结尾的问号）。另一点区别在于，图6-4中的整个尝试序列是传统型NFA和POSIX NFA都必须经历的：如果无法匹配，传统型NFA必须进行的尝试与POSIX NFA一样多。

图6-4：「＂.＊＂！」匹配失败的经过

因为从开始的A到结束的I的所有尝试都不存在匹配，传动装置必须启动驱动过程开始新一轮尝试。从J、Q、V开始的尝试看来有可能匹配成功，但结果都与从A开始的尝试一样。最终到Y，不存在继续尝试的途径，所以整个尝试宣告失败。如图6-4所示，得到这个结果花费了许多工夫。

Being More Specific

我们把点号换成「[^＂]」来做个比较。前一章已经讨论过，这样的结果更容易理解，因为它能匹配的字符更少，而且这样一来，正则表达式的效率也提高了。如果使用「＂[^＂]＊＂！」，「[^＂]＊」匹配的内容就不能包括双引号，减少了匹配和回溯。

图6-5说明了尝试失败的过程（请对比图6-4）。从图中可以看到，回溯的次数大大减少了。如果这个结果满足我们的需要，减少的回溯就是有益的伴随效应（side effect）。

图6-5：「＂[^＂]＊＂！」无法匹配

Alternation Can Be Expensive

多选结构或许是回溯的主要原因。举个简单的例子，用makudonarudo来比较「u|v|w|x|y|z」和「[uvwxyz]」的匹配。字符组一般只是进行简单测试（注3），所以「[uvwxyz]」只需要进行34次尝试就能匹配。

如果使用「u|v|w|x|y|z」，则需要在每个位置进行6次回溯，在得到同样结果之前总共有204次回溯。当然，并不是每个多选结构都可以替换为字符组，即使可以，也不见得会这么简单。不过，在某些情况下，我们将要学习的技巧能够大大减少与匹配所须的多选结构相关的回溯。

理解回溯可能是学习NFA效率中最重要的问题，但所有的问题不只于此。正则引擎的优化措施能够大大提升效率。在本章后面，我们将详细考察正则引擎要做的工作和优化手段。