详解正则表达式匹配算法原理

太过爱你忘了你带给我的痛 2022-05-08 23:14 243阅读 0赞

注意：关于正则表达式的规则，网上内容已经很多了。所以本文不讲述正则表达式的规则，只讲其背后的算法原理。

# 1. 引入 #

正则表达式，Regular Expression，使用单个字符串来描述、匹配一系列满足某种句法规则的字符串。

在很多文本编辑器里，正则表达式通常被用来检索、替换那些匹配某个模式的文本。

最常见的，比如“.*”，其中“.”表示匹配除“\\n”之外的任何单个字符，“*”表示匹配前面的子表达式零次或多次。

在python中，正则表达式的使用也很简单：

import re
    regexObject = re.compile(r".*abc.*", flags=0) # 匹配含有abc的字符串
    
    s1 = 'asd abc sd abc'
    s2 = 'sdfsabcsdffa'
    s3 = 'fsadf'
    
    match1 = re.search(regexObject, s1) # <_sre.SRE_Match at 0x66473d8>
    match2 = re.search(regexObject, s2) # <_sre.SRE_Match at 0x6647b90>
    match3 = re.search(regexObject, s3) # None

但是，正则表达式的内部原理是怎么样的呢？ 它是按照什么算法来进行字符串匹配？ 这就是本文要解释的内容。

# 2. 状态机 #

# 2.1 有限状态系统 #

下面直接给出几个有限状态系统的实例，从直观上就能理解有限状态系统：

*  例1：指针式钟表，一共有12\*60\*60个状态，每过一秒，钟表就从一种状态转换到另一种状态
 *  例2：围棋共有3\*\*361个状态，每走一步棋，就从一个状态转换到另一个状态
 *  例3：语言的识别

![70][]

# 2.2 有限状态机 #

有限状态机（英语：finite-state machine，缩写：FSM）又称有限状态自动机，简称状态机，是表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型。

有些地方也叫“自动机”，指的都是同一个东西。

FSM的表示，我们常用`状态转移图`。下图就是一个模式字符串的FSM`状态转移图`：

![70 1][]

给定待匹配的字符串”abababaca”，就能通过模式串的FSM进行匹配，这就是正则表达式的匹配思想。

# 3. 正则表达式匹配实例 #

给定正则表达式`a(bb)+a`，其中`+`表示匹配前面的子表达式一次或多次，所以字符串`abba`或`abbbba`都能被这个模式所匹配。

下图是该正则表达式对应的FSM`状态转移图`。

![这里写图片描述][SouthEast]

该FSM中，圈代表不同的状态。读入字符串时，就从一个状态进入另一个状态。FSM有开始和匹配（匹配）两种特殊状态，分别位于头部和尾部。

下面是匹配的过程示例图：

![70 2][]

该状态机结束于最后一个状态，这是一个匹配成功的状态。若状态机结束于非匹配成功状态，那么匹配失败。如果在运行过程中，没有办法到达其他状态，那么状态机提前结束。

# 4. 多路径匹配 #

正则表达式等效于有限状态机，每一个正则表达式都有一个对应的有限状态机。反之，有限状态机也对应一个正则表达式。具体的对应关系可以参见这篇文章（[https://sine-x.com/regexp-1/][https_sine-x.com_regexp-1]）。

下面是多路径的算法匹配过程：

![SouthEast 1][]

匹配时，可能有多条路径，遇到分支时，可以采用试错法，一条走不通，再尝试另一条。但这种做法效率较低。

所以另一种更优的做法，是在分支处同时匹配多条分支，同时保持多个状态，这样避免了很多不必要的尝试。

# 参考 #

本文中的图是直接从下文中截取出来再编辑的，在此感谢原图作者！

*  [https://wenku.baidu.com/view/f8ec4d7814791711cd791768.html][https_wenku.baidu.com_view_f8ec4d7814791711cd791768.html]
 *  [https://sine-x.com/regexp-1/][https_sine-x.com_regexp-1]
 *  [https://www.cnblogs.com/jolin123/p/3443543.html][https_www.cnblogs.com_jolin123_p_3443543.html]

[70]: /images/20220509/ab3295bf912940acae378d6f1d99cc65.png
[70 1]: /images/20220509/781f2584b6ad439ea0edc3bfb52be371.png
[SouthEast]: /images/20220509/c6c7263184ba41e5af3b0899d851be5f.png
[70 2]: /images/20220509/d77d6ae2fd4443d2979d3cba77eed787.png
[https_sine-x.com_regexp-1]: https://sine-x.com/regexp-1/
[SouthEast 1]: /images/20220509/3571c591123845458740d5c9bc41d2c7.png
[https_wenku.baidu.com_view_f8ec4d7814791711cd791768.html]: https://wenku.baidu.com/view/f8ec4d7814791711cd791768.html
[https_www.cnblogs.com_jolin123_p_3443543.html]: https://www.cnblogs.com/jolin123/p/3443543.html