觅迹寻踪之正则表达式

原创腾讯CDC 腾讯CDC体验设计 4月28日

灵魂拷问

成功骗你点进来，准备好学习新知识了吗？

“应该是没有”

不知道你有没有听过，正则匹配。它的使用场景是什么？

“在多个文本中，找到【我最帅】”

这篇是原理篇，可能有点晦涩。

背景

把正则表达式理解为一门编程语言，那它可能会有解析引擎和执行引擎。

希望通过介绍正则表达式的执行引擎，了解其实现原理，能帮助大家写出更优雅的正则表达式。

执行引擎

正则表达式的执行引擎主要分为两个大类：

DFA (Deterministic finite automaton) 确定型有穷自动机
NFA (Non-deterministic finite automaton) 非确定型有穷自动机

其中：
1. NFA 中可以再进行细分，分为 POSIX NFA 和 Traditional NFA
2. 还有些程序支持 DFA 和 NFA 混合体整理为表格如下：

> 章节原因，FA,DFA,NFA 之间的关系，留待下一次叙述

DFA 执行引擎

由上可以得出，DFA 的特点：

1.先看文本，再看正则，以文本主导

2.编译完表达式后，还需要遍历出表达式中所有的可能

3.匹配过程，字符串只看一次

NFA 执行引擎

> 文中的 NFA ，指的都是 Traditional NFA

由上可以得出，NFA 的特点：

1.先看正则，再看文本，以正则主导

2.编译完表达式即完成

3.匹配过程中，可能会发生回退，字符串同一部分会比较多次（通常将回退称为回溯）

敲重点

如何区分

如何区分 Traditional NFA, POSIX NFA, DFA, DFA/NFA

看是否支持忽略优先量词。如果支持，基本就能确定是 Traditional NFA

正则表达式 nfa|nfa.not，文本 nfa.not

如果只匹配到 nfa ，基本就能确定是 Traditional NFA

看是否支持捕获型括号或者回溯。如果支持，基本能确定是 POSIX NFA

正则表达式 X(.+)+X，文本 XxX==============

如果出现灾难性回溯，基本能确定是 POSIX NFA

但是可能存在 DFA 和 NFA 两种引擎的混合的工具

细品 NFA 回溯

上文提到，NFA 具有回溯的能力，该能力是一把双刃剑因为回溯会增加匹配的步骤，步骤过量会导致 CPU 使用率飙升

因此了解回溯出现的场景十分有必要

常见场景

贪婪模式

1.贪婪，每次都尽可能多标绿匹配的内容。

2.回溯。当正则需要匹配下一个文本内容时候，发现不匹配，文本只能回退一步。

惰性模式

1.懒惰，每次尽可能少标绿匹配的内容。

2.回溯。当正则需要匹配下一个文本内容时候，发现不匹配，文本只能回退一步。

分组模式

1.分组，按照分支的顺序逐个匹配。

2.回溯。当正则需要匹配下一个文本内容时候，发现不匹配，文本只能回退一步。

> 关于什么是贪婪模式，懒惰模式，独占模式，分组模式不在这里展开详细叙述，留待下一次讲解

实（踩）战（坑）例子

检验商店名字地址是否合法

检验商店名字地址是否合法，规则：
1.英文字母大小写 2.数字 3. 越南文 4.一些特殊字符，如 &，-，_ 等使用以下正则作示例：^([A-Za-z0-9._()&'\- ]|[aAàÀảẢãÃáÁạẠăĂằẰẳẲẵẴắẮặẶâÂầẦẩẨẫẪấẤậẬbBcCdDđĐeEèÈẻẺẽẼéÉẹẸêÊềỀểỂễỄếẾệỆfFgGhHiIìÌỉỈĩĨíÍịỊjJkKlLmMnNoOòÒỏỎõÕóÓọỌôÔồỒổỔỗỖốỐộỘơƠờỜởỞỡỠớỚợỢpPqQrRsStTuUùÙủỦũŨúÚụỤưƯừỪửỬữỮứỨựỰvVwWxXyYỳỲỷỶỹỸýÝỵỴzZ])+$

我们使用正则验证工具(regex101)进行调试

1.文本：this is good

2.文本：this is good，

发现输入 this is good， 竟然要多达 17599 步才完成匹配

3.抽丝剥茧上述的正则表达式看上去写得很复杂，实际可以简化一下：^([符合要求的组成1]|[符合要求的组成2])+$能发现正则表达式中有 + 出现，意味着有贪婪匹配，可能会有大量回溯利用 regex101 工具中的调试功能，发现当到 30+ 步数，就开始进行回溯

我们尝试将贪婪模式改成独占模式，即修改为：

^([A-Za-z0-9._()&'\- ]|[aAàÀảẢãÃáÁạẠăĂằẰẳẲẵẴắẮặẶâÂầẦẩẨẫẪấẤậẬbBcCdDđĐeEèÈẻẺẽẼéÉẹẸêÊềỀểỂễỄếẾệỆfFgGhHiIìÌỉỈĩĨíÍịỊjJkKlLmMnNoOòÒỏỎõÕóÓọỌôÔồỒổỔỗỖốỐộỘơƠờỜởỞỡỠớỚợỢpPqQrRsStTuUùÙủỦũŨúÚụỤưƯừỪửỬữỮứỨựỰvVwWxXyYỳỲỷỶỹỸýÝỵỴzZ])++$

改为独占模式后，匹配步数锐减到 29 步

> 使用独占模式，需要注意两点：1. 是否满足业务需求；2. 使用的编程语言是否支持

正则表达千万条，还有其他优化的方案在原有 ^([A-Za-z0-9._()&'\- ]|[aAàÀảẢãÃáÁạẠăĂằẰẳẲẵẴắẮặẶâÂầẦẩẨẫẪấẤậẬbBcCdDđĐeEèÈẻẺẽẼéÉẹẸêÊềỀểỂễỄếẾệỆfFgGhHiIìÌỉỈĩĨíÍịỊjJkKlLmMnNoOòÒỏỎõÕóÓọỌôÔồỒổỔỗỖốỐộỘơƠờỜởỞỡỠớỚợỢpPqQrRsStTuUùÙủỦũŨúÚụỤưƯừỪửỬữỮứỨựỰvVwWxXyYỳỲỷỶỹỸýÝỵỴzZ])+$ 基础上优化

移除重复的字母（不要在多选择分支中，出现重复的元素）

^([0-9._()&'\- ]|[aAàÀảẢãÃáÁạẠăĂằẰẳẲẵẴắẮặẶâÂầẦẩẨẫẪấẤậẬbBcCdDđĐeEèÈẻẺẽẼéÉẹẸêÊềỀểỂễỄếẾệỆfFgGhHiIìÌỉỈĩĨíÍịỊjJkKlLmMnNoOòÒỏỎõÕóÓọỌôÔồỒổỔỗỖốỐộỘơƠờỜởỞỡỠớỚợỢpPqQrRsStTuUùÙủỦũŨúÚụỤưƯừỪửỬữỮứỨựỰvVwWxXyYỳỲỷỶỹỸýÝỵỴzZ])+$

移除多选分支选择结构（直接用中括号表示多选一）

^([A-Za-z0-9._()&'\- aAàÀảẢãÃáÁạẠăĂằẰẳẲẵẴắẮặẶâÂầẦẩẨẫẪấẤậẬbBcCdDđĐeEèÈẻẺẽẼéÉẹẸêÊềỀểỂễỄếẾệỆfFgGhHiIìÌỉỈĩĨíÍịỊjJkKlLmMnNoOòÒỏỎõÕóÓọỌôÔồỒổỔỗỖốỐộỘơƠờỜởỞỡỠớỚợỢpPqQrRsStTuUùÙủỦũŨúÚụỤưƯừỪửỬữỮứỨựỰvVwWxXyYỳỲỷỶỹỸýÝỵỴzZ])+$

检验 URL 地址是否合法

检验 URL 地址是否合法，规则如下：

1.校验协议 2. 校验域名 3. 校验参数使用以下正则作示例：
^([hH][tT]{2}[pP]:\/\/|[hH][tT]{2}[pP][sS]:\/\/)(([A-Za-z0-9-~]+).)+([A-Za-z0-9-~\\\/])+$1.文本：http://www.fapiao.com/index.html

2.文本：

http://www.fapiao.com/dzfp-web/pdf/download?request=6e7JGm38jfjghVrv4ILd-kEn64HcUX4qL4a4qJ4-CHLmqVnenXC692m74H5oxkjgdsYazxcUmfcOH2fAfY1Vw__%5EDadIfJgiEf