au3 正则参考 -70-回溯

3月302016

作者：绿色风发布：2016-3-30 11:27 Wednesday 分类：工具●教程阅读：12258次评论：0条

<!DOCTYPE html> RegExp

正则表达式中的回溯

正则表达式前进到子表达式的下一个语言元素并且匹配不成功时, 正则表达式引擎可放弃其成功匹配的一部分, 并返回以前保存的正则表达式与输入字符串匹配有关的状态. 返回到以前保存状态以查找匹配的这一过程称为回溯.

通常正则表达式引擎使用线性进度在输入字符串中移动. 当正则表达式模式包含可选限定符或可选构造时, 会发生回溯, 并且正则表达式引擎会返回以前保存的状态, 并继续搜索匹配项, 以便成功完成整个模式的匹配.

回溯是正则表达式强大功能的中心; 它使得表达式强大, 灵活, 可以匹配非常复杂的模式. 同时, 这种强大功能需要付出一定代价.

通常, 回溯是影响正则表达式引擎性能的单个最重要的因素. 幸运的是正则表达式编写者可以控制正则表达式引擎的行为及其回溯的使用方式. 本主题说明回溯的工作方式. 回溯的控制见这里.

不使用回溯的线性比较

如果正则表达式模式没有可选限定符或可选构造, 正则表达式引擎将以线性时间执行. 正则表达式引擎将模式中的第一个语言元素与输入字符串中的文本匹配后, 它尝试将模式中的下一个语言元素与输入字符串中的下一个字符或字符组合匹配. 此操作将继续, 直至匹配成功或失败. 在任何一种情况下, 在同一时间, 正则表达式引擎都比输入字符串中提前一个字符.

下面示例进行这方面的演示. 正则表达式 e{2}\w\b 查找字母 "e" 后跟任意单词字符再后跟单词边界的两个匹配项.

字符串: needing a reed

表达式: e{2}\w\b

匹配结果(标志 1, 或 2, 或 3): [0]eed

表达式分析:

模式	说明
e{2}	匹配 2 个字符 e .
\w	字符组 [0-9a-zA-Z] 的简记形式. 匹配任何一个数字, 或一个任意字母, 或一个下划线 ""
\b	在单词边界处结束匹配.

尽管此正则表达式包括限定符 {2}, 但它仍以线性方式进行计算. 由于 {2} 不是可选的限定符, 它指定确切数字, 而不是前一个子表达式必须匹配的可变次数. 因此该正则表达式引擎不回溯.

使用可选限定符或可选构造的回溯

当正则表达式模式包含可选限定符或可选构造时, 输入字符串的计算将不再为线性. 模式匹配由正则表达式中的语言元素驱动, 而不是由输入字符串中要匹配的字符驱动. 因此, 正则表达式引擎将尝试完全匹配可选或可替换的子表达式.

例如正则表达式模式 .(es), 它匹配字符 es 以及它前面的所有字符. 如果输入字符串为 Essential services are provided by regular expressions. 模式将匹配 expressions 之前且包括 es 在内的整个字符串.

字符串: Essential services are provided by regular expressions.

表达式: .(es)

匹配结果(标志 2):
[0]Essential services are provided by regular expres ; 从位置 0 开始的匹配结果
[1]es ; 从位置 47 开始的匹配结果.

正则表达式引擎按如下所示使用回溯:

1. 将 . (它对应于出现零次, 一次或多次的任意字符)与整个输入字符串匹配.

    2. 尝试在正则表达式模式中匹配 e . 但输入字符串没有剩余的可用字符来匹配.

    3. 回溯到上一次成功的匹配 "Essential services are provided by regular expressions" , 并尝试将 e 与句尾的句号匹配. 匹配失败.

    4. 继续回溯到上一个成功匹配, 一次一个字符, 直至临时匹配的子字符串为 "Essential services are provided by regular expr" . 然后, 它将模式中的 e 与 expressions 中的第二个 e 进行比较, 并找到匹配.

    5. 将模式中的 s 与匹配的 e 字符之后的 s (“expressions"中的第一个 s )进行比较. 匹配成功.

当您使用回溯将正则表达式模式与输入字符串(长度为 55 个字符)匹配时, 需要执行 67 次比较操作. 有趣的是, 如果正则表达式模式包括惰性限定符 .?(es), 则匹配正则表达式将需要进行更多次比较. 在此情况下, 不必从字符串末尾回溯到 expressions 中的 r , 正则表达式引擎必须一直回溯到字符串开头来匹配 Es , 将需要进行 113 次比较. 通常, 如果正则表达式模式包括单个可选构造或单个可选限定符, 则匹配模式所需要的比较操作数大于输入字符串中字符数的两倍.

使用嵌套可选限定符的回溯

如果模式中包括大量可选构造, 嵌套的可选构造(或最常见的是嵌套的可选限定符), 则匹配正则表达式模式所需要的比较操作数会成指数增加.

例如正则表达式模式 (a+)+ 用于匹配包含一个或多个 a 字符的完整字符串. 该示例提供了两个长度相同的输入字符串, 但只有第一个字符串与模式匹配.

字符串: aaaaaa, aaaaa!

表达式: (a+)+

匹配结果(标志 1): [0]aaaaaa

正如示例输出所示, 正则表达式引擎查找输入字符串与模式不匹配所需的时间大约为标识匹配字符串所需时间的两倍. 这是因为, 不成功的匹配始终表示最糟糕的情况. 正则表达式引擎必须使正则表达式遵循通过数据的所有可能路径, 然后才能得出匹配不成功的结论, 嵌套的括号会创建数据的许多其他路径. 正则表达式引擎通过执行以下操作来确定第二个字符串与模式不匹配：

1. 检查字符串开头, 然后将字符串中的前五个字符与模式 a+ 匹配. 然后确定字符串中没有其他成组的 a 字符. 最后, 它测试是否位于字符串结尾. 由于还有一个附加字符保留在字符串中, 所以匹配失败. 这一失败的匹配需要进行 9 次比较. 正则表达式引擎也从其 a(我们将其称为匹配 1), aa(匹配 2), aaa(匹配 3)和 aaaa(匹配 4)的匹配中保存状态信息.

2. 返回到以前保存的匹配 4. 它确定没有一个附加的 a 字符可分配给其他捕获组. 最后, 它测试是否位于字符串结尾. 由于还有一个附加字符保留在字符串中, 所以匹配失败. 该失败的匹配需要进行 4 次比较. 到目前为止, 总共执行了 13 次比较.

3. 返回到以前保存的匹配 3. 它确定有两个附加的 a 字符可分配给其他捕获组. 但是, 字符串末尾测试失败. 然后, 它返回匹配 3 , 并尝试在两个附加的捕获组中匹配两个附加的 a 字符. 字符串末尾测试仍失败. 这些失败的匹配需要进行 12 次比较. 到目前为止, 总共执行了 25 次比较.

输入字符串与正则表达式的比较将以此方式继续, 直到正则表达式引擎已尝试所有可能的匹配组合然后得出无匹配的结论. 因为存在嵌套的限定符, 所以此比较为 2 的 n 次方或指数操作, 其中 n 是输入字符串中的字符数. 这意味着在最糟糕的情况下, 包含 30 个字符的输入字符串大约需要进行 1,073,741,824 次比较, 包含 40 个字符的输入字符串大约需要进行 1,099,511,627,776 次比较. 如果使用上述长度甚至更长的字符串, 则正则表达式方法在处理与正则表达式模式不匹配的输入时, 会需要超长的时间来完成.

本文固定链接: http://jianyiit.com/post-222.html