au3 正则参考 -71-回溯控制
<!DOCTYPE html>
回溯的控制
通过回溯可以创建强大, 灵活的正则表达式. 回溯在提供这些优点的同时, 可能也会使性能差得无法接受. 因此要防止过度回溯.
误用回溯或依赖过多回溯通常会显著降低正则表达式的性能. 在最糟糕的情况下, 输入字符串中每增加一个字符, 执行时间会加倍. 实际上, 如果过多使用回溯, 则在输入与正则表达式模式近似匹配时很容易创建无限循环的编程等效形式; 正则表达式引擎可能需要几小时甚至几天来处理相对短的输入字符串.
尽管回溯不是匹配所必需的, 但应用程序会因使用回溯而对性能产生负面影响. 例如正则表达式 \b\p{Lu}\w\b 将匹配以大写字符开头的所有单词, 如下表所示:
| 模式 | 说明 |
|---|---|
| \b | 在单词边界处开始匹配. |
| p{Lu} | 匹配大写字符. |
| \w | 匹配零个或多个单词字符. |
| \b | 在单词边界处结束匹配. |
由于单词边界与单词字符不同, 也不是单词字符的子集, 因此正则表达式引擎在匹配单词字符时将跨越单词边界. 这意味着对于正则表达式而言, 回溯对任何匹配的总体成功不会有任何贡献 -- 由于正则表达式引擎被强制保存每个单词字符的成功匹配的状态, 因此它只会降低性能.
回溯控制支持以下三个正则表达式语言元素, 这些元素限制或禁止回溯, 并支持对性能没有负面影响或负面影响很小的复杂正则表达式:
非回溯子表达式, 回顾断言, 预测先行断言.
非回溯子表达式
如果你确定不需要回溯, 则可使用 (?>子表达式) 语言元素禁止在子表达式中使用回溯. 它可用于预防与匹配失败关联的性能问题.
上面描述的表达式 \b\p{Lu}\w\b 依赖于回溯, 将其修改为 \b\p{Lu}(?>\w)\b 则会禁用回溯.
用这 2 个表达式分别匹配字符串 This this word Sentence name Capital , 这两个正则表达式产生的结果相同.
下面的示例演示使用嵌套限定符时禁止回溯如何改进性能. 它测量正则表达式引擎确定输入字符串与两个正则表达式不匹配( 即两个表达式都没有匹配项 )所需要的时间.
第一个正则表达式使用回溯尝试匹配一个字符串, 在该字符串中, 一个或多个十六进制数出现一次或多次, 然后依次为冒号, 一个或多个十六进制数, 两个冒号.
第二个正则表达式与第一个相同, 不同之处是它禁用了回溯. 测试可见禁用回溯对性能的改进非常显著.
字符串: b51:4:1DB:9EE1:5:27d60:f44:D4:cd:E:5:0A5:4a:D24:41Ad:
回溯子表达式 : (([0-9a-fA-F]{1,4}:)([0-9a-fA-F]{1,4}))(::)
非回溯子表达式 : ((?>[0-9a-fA-F]{1,4}:)(?>[0-9a-fA-F]{1,4}))(::)
分别使用这 2 个表达式测试, 回溯子表达式耗时高达 250 毫秒以上, 而非回溯子表达式耗时仅 0.1 毫秒左右.
回顾断言
包括两个语言元素 (?<=断言模式) 和 (?<!断言模式), 它们与输入字符串中的前面一个或多个字符匹配. 这两个语言元素都是零宽度断言; 它们通过断言模式而不是前移或回溯来确定当前字符之前紧挨着的一个或多个字符是否匹配.
(?<= 断言模式) 是正回顾断言; 当前位置之前的一个或多个字符必须与 断言模式 匹配.
(?<! 断言模式) 是负回顾断言; 当前位置之前的一个或多个字符不得与断言模式匹配.
当断言模式为前一个子表达式的子集时, 正回顾断言和负回顾断言都最为有用.
在许多情况下正则表达式模式与输入文本匹配时, 回溯很重要. 但过度回溯会严重降低性能, 并且会产生应用程序已停止响应的感觉. 特别需要指出的是, 当嵌套限定符并且与外部子表达式匹配的文本为与内部子表达式匹配的文本的子集时, 尤其会出现这种情况.
例如正则表达式模式 0-9A-Z\$ 用于匹配至少包括一个字母数字字符的部件号. 任何附加字符可以包含字母数字字符, 连字符, 下划线或句号, 但最后一个字符必须为字母数字. 美元符号用于终止部件号. 在某些情况下, 由于限定符嵌套并且子表达式 [0-9A-Z] 是子表达式 [-.\w] 的子集, 因此此正则表达式模式会表现出极差的性能.
此时可通过移除嵌套限定符并将外部子表达式替换为零宽度预测先行和回顾断言来优化正则表达式性能. 预测先行和回顾断言是定位点; 它们不在输入字符串中移动指针, 而是通过预测先行或回顾来检查是否满足指定条件. 例如可将部件号正则表达式重写为 [0-9A-Z][-.\w](?<=[0-9A-Z])\$. 此正则表达式模式的定义如下表所示:
| 表达式 | 说明 |
|---|---|
| [0-9A-Z] | 匹配一个字母或数字字符. 部件号至少要包含一个此类字符. |
| [-.\w] | 匹配零个或多个任意单词字符, 或连字符, 或句号. |
| \$ | 转义 $ 字符匹配美元符号. |
| (?<=[0-9A-Z]) | 正回顾断言. 查看美元符号结束的前面是否为一个字母或数字. |
此表达式与字符串 A1C$, A4, A4$, A1603D$, A1603D# 匹配时, 将匹配红标部分, 其它 2 个不匹配.
下面示例使用 2 个等效正则表达式模式. 第一个模式由于过多使用回溯, 性能极差. 第二个模式通过将嵌套的限定符替换为正回顾断言来修改第一个正则表达式.
字符串: aaaaaaaaaaaaaaaaaaaa ; 20 个 a
表达式1 : (?i)^0-9A-Z
匹配结果(标志 1) : [0]aaaaaaaaaaaaaaaaaaa ; 返回 19 个 a
表达式1分析:
| 模式 | 子模式 | 说明 |
|---|---|---|
| (?i) | 启动不区分大小写匹配. | |
| ^ | 从字符串开头开始匹配. | |
| [0-9A-Z] | 匹配一个字母或数字字符. | |
| ([-.\w][0-9A-Z]) | 匹配以下 0 个或多个下列子模式的组合. 这是第一个捕获组. | |
| [-.\w] | 匹配 0 个或多个 连字符, 或句号, 或字母字符 . | |
| [0-9A-Z] | 匹配一个字母或数字字符. |
表达式2 : (?i)[0-9A-Z][-.\w](?<=[0-9A-Z])
匹配结果(标志 1) : [0]aaaaaaaaaaaaaaaaaaaa ; 返回 20 个 a
表达式2分析
| 模式 | 说明 |
|---|---|
| (?i) | 启动不区分大小写匹配. |
| ^ | 从字符串开头开始匹配 |
| [0-9A-Z] | 匹配一个字母或数字字符. |
| [-.\w] | 匹配 0 个或多个连字符, 或句号, 或字母字符. |
| (?<=[0-9A-Z]) | 回顾最后一个匹配的字符, 如果该字符是字母数字字符, 则继续匹配. 请注意, 字母数字字符是由句号, 连字符和所有单词字符构成的集合的子集. |
预测先行断言
包括两个语言元素 (?=断言模式) 和 (?!断言模式), 它们与输入字符串中的后面一个或多个字符匹配. 这两个语言元素都是零宽度断言; 它们通过断言模式而不是前移或回溯来确定当前字符之后紧挨着的一个或多个字符是否匹配.
(?=断言模式) 是正预测先行断言; 当前位置之后的一个或多个字符必须与断言模式匹配.
(?!断言模式)是负预测先行断言; 当前位置之后的一个或多个字符不得与断言模式匹配.
当断言模式为下一个断言模式的子集时, 正预测先行断言和负预测先行断言都最为有用.
下面示例使用两个可验证完全限定类型名称的等效正则表达式模式. 第一个模式由于过多使用回溯, 性能极差. 第二个模式通过将嵌套的限定符替换为正预测先行断言来修改第一个正则表达式.
字符串 : aaaaaaaaaaaaaaaaaaaa ; 22 个字符 a
表达式1 : (?i)^(([A-Z]\w)+.)[A-Z]\w$
测试标志 3 匹配失败, 耗时 205ms
表达式分析:
| 模式 | 子模式 | 说明 |
|---|---|---|
| (?i) | 启动不区分大小写匹配. | |
| ^ | 从字符串开头开始匹配. | |
| (([A-Z]\w)+.) | 对后跟零个或多个单词字符, 句点的字母字符 (A-Z) 匹配一次或多次 | |
| ([A-Z]\w) | 匹配任意一个 A-Z 字母后跟的单词字符的 0 次或多次. | |
| +. | 匹配上模式捕获值的 1 次或多次, 再后跟一个句号. | |
| ) | 匹配上模式捕获值的 0 次或多次 | |
| [A-Z]\w | 匹配任意一个 A-Z 字母后跟的单词字符的 0 次或多次. | |
| $ | 在输入字符串末尾结束匹配 |
表达式2 : (?i)^((?=[A-Z])\w+.)[A-Z]\w$ 使用正预测先行断言
测试标志 3 匹配失败, 耗时 0.062ms
表达式2分析:
| 模式 | 子模式 | 说明 |
|---|---|---|
| (?i) | 启动不区分大小写模式. | |
| ^ | 从字符串开头开始匹配 | |
| ((?=[A-Z])\w+.) | 匹配对象分述如下: | |
| (?=[A-Z]) | 正预测先行断言. 匹配任意一个 A-Z 范围内的字母. | |
| \w+. | 匹配 1 或多个单词字符, 并后跟一个句点. | |
| ) | 匹配上模式捕获值的 0 次或多次. | |
| [A-Z]\w* | 0 次或多次匹配任意一个 A-Z 范围内字母 | |
| $ | 在输入字符串末尾结束匹配 |
- 运行时间: 20048 天
- 日志总数: 365 篇
- 评论数量: 549 条
- 微语数量: 6 条
- 附件总量: 388 件
-
逝出的青春
-
打赏"绿色风"
扫码关注本站公众号 可搜本站内容
-
Autoit V3 脚本交流群
-
常驻群1:905774875
常驻群2:40672266
-
链接
-
分类
发表评论
木有头像就木JJ啦！还木有头像吗？点这里申请属于你的个性Gravatar头像吧！