v0.3下载地址:https://download.csdn.net/download/as604049322/14504394 目录 文章目录文档简介作者简介大家好,我是小小明,本人非常擅长解决各类复杂数据处理的逻辑,包括各类结构化与非结构化数据互转。如果你在数据处理上遇到什么困难,欢迎与我交流。 本文档是小小明个人的学习笔记,涵盖了正则表达式的各个方面,包括各种模式、分组、断言。 正则的匹配、查找、替换和切割一节包含各种典型的实际案例,各类使用场景。 正则匹配规则表,方便我们随时查询正则的规则,即使我自己也无法保证把那些规则全部记住,使用时需要随时回来查询。 贪婪模式和非贪婪模式部分顺便简单讲解了正则匹配的基本原理(NFA和DFA,在2.3和3.2两个章节)。 作者的博客地址:https://blog.csdn.net/as604049322 阅读建议本文档本身可能并不适合初学者学习,但非常适合对正则有一定基础了解的朋友系统性学习。 对于初学者建议在B站找两部正则入门教程入门之后再学习本文档。 初学者直接阅读本文档,可以先跳过正则匹配规则表部分,不要纠结,等学完后续部分之后再回来看。 正则匹配规则表主要针对已经掌握正则的朋友,随时回来查询规则。 版权声明转载请申明出处 Python 正则表达式基本概念正则表达式在每种编程语言中都具有相同的概念,整体规则都大致一致,只是部分语言没有实现少部分规则。 正则表达式的本质就是用一些特定字符的组合,组成一个“规则字符串”表达对字符串的一种过滤逻辑,可以很方便的从指定的字符串中提取出我们想要的内容。 python正则表达式的官方文档是:https://docs./zh-cn/3.7/library/re.html 一个优秀的正则测试网站:https:/// 本地正则测试软件(依赖.Net 4.8):https:///tools/regester/index.htm 下面我们看一下正则规则表,可以在以后需要的时候,随时回来查询相应的规则: 正则匹配规则表基本字符规则:
预定义字符集:(可以写在字符集[…]中)
常用字符集:
数量词:
边界匹配器:
逻辑、分组:
非捕获组与环视:
匹配模式和注释:
( 基本字符集匹配测试打开我之前保存的正则:https:///r/GN99Cs/1 可以很清晰的看到数字字符集 假如改成\w: 顺利的匹配所有的数字、字母哈下划线。 你还可以自己测试上述正则匹配规则表中的各类字符集。 贪婪模式、非贪婪模式和独占模式为什么会有贪婪与非贪婪模式呢?我们先来回顾一下正则中表示数量词的规则(前面的正则规则表中有):
{m,n} 可以等价表示
数量词
可以看到
贪婪模式就是尽可能匹配更多的字符,非贪婪模式则是尽可能匹配最少的字符,这两种匹配模式会产生不同的匹配结果。 贪婪模式(Greedy)我们先看一下贪婪匹配下,字符串 123456ab 中使用正则 \d* 的匹配过程: \d* 在匹配开头的数字时,会尝试尽量匹配更多的数字,直到出现第一个字母a 不满足要求为止,匹配完全部数字后每次匹配都得到了空字符串。 非贪婪模式(Lazy)在数量词后面加上英文的问号 (?),正则就变成了 可以看到非贪婪模式下,原本的4项匹配成功变成了9项:
非贪婪模式下匹配到的结果都是单个的数字,就连每个数字左边的空字符串也匹配上了。 贪婪与非贪婪模式对比示例以下代码首先需执行:
示例1 匹配出数字后面的0:
由于\d+采用贪婪匹配,直接把后面的0全部匹配了,0*就只能匹配空字符串了。 加个?就让\d+采用非贪婪匹配,把后面的0匹配出来:
示例2 比如有一批需要提取出用户名的邮件地址:
我们希望提取出其中的用户名: 假如采用默认的贪婪模式,为了匹配开头的<之类的字符,则必须使用非单词字符\W:
但采用非贪婪匹配,开头我们就可以直接使用任意字符
返回的结果都是:
回溯算法不管是贪婪模式,还是非贪婪模式,都需要发生回溯才能完成相应的功能。回溯算法是正则表达式里最重要的一种算法思想,依次考察正则表达式中的每个字符,非通配符时就直接跟文本的字符进行匹配,相同则继续往下处理;不同则回溯。 比如遇到遇到正则表达式的 默认贪婪模式下:
y{1,3}会尽可能长地去匹配,当匹配完 xyy 后,由于 y 要尽可能匹配最长即三个,但字符串中后面是个 z 就会导致匹配不上,这时候正则就会向前回溯,吐出当前字符 z,接着用正则中的 z 去匹配。 非贪婪模式下:
由于 y{1,3}? 代表匹配 1 到 3 个 y,尽可能少地匹配。匹配上一个 y 之后,也就是在匹配上 text 中的 xy 后,正则会使用 z 和 text 中的 xy 后面的 y 比较,发现正则 z 和 y 不匹配,这时正则就会向前回溯,重新查看 y 匹配两个的情况,匹配上正则中的 xyy,然后再用 z 去匹配 text 中的 z,匹配成功。 独占模式(Possessive)在一些场景下,我们不需要回溯,匹配不上返回失败就好了,因此正则中还有另外一种模式,独占模式,它类似贪婪匹配会尽可能多地去匹配,但匹配失败就结束,不会进行回溯,因此在一些场合下性能会更好,具体的方法就是在数量词后面加上加号 独占模式下:
y{1,2}+尽可能多的匹配前两个y,不回溯导致正则z前面的y匹配不上: python的标准库re并不支持独占模式,会报错:
python上要使用独占模式需要安装regex 模块:
再次测试:
独占模式的典型应用: 独占模式性能比较好,可以节约匹配的时间和 CPU 资源,但并不是所有的场景都适用,否则也不会出现python标准库不支持的场景。下面我们看一个适合适用独占模式的场景。 阿里技术微信公众号上的发文。Lazada 卖家中心店铺名检验规则比较复杂,名称中可以出现下面这些组合:
负责开发的小伙伴在开发过程中使用了正则来实现店铺名称校验:
这个正则比较长但很好理解,简化一下主体结构,即:
正则中有的加号 我们只需要将贪婪模式改成独占模式(加号
这个例子中,匹配不上时证明店铺名不合法,不需要进行回溯,因此我们可以使用独占模式,但要并不是所有的场合都可以用独占模式解决,首先要保证正则能满足功能需求。 仔细再看一下 这个正则发现 “组成 1” 和 “组成 2” 部分中,A-Za-z 英文字母在两个集合里面重复出现了,这会导致回溯后的重复判断,去掉重复字符也能大幅度减少正则的计算量。 这个问题将在文末的补充资料中继续详解。 原生字符串简化反斜杠
|
参数 | 描述 |
---|---|
pattern | 匹配的正则表达式 |
string | 被匹配的字符串 |
flags | 标志位,对应于正则规则表中的iLmsux匹配模式 |
而正则替换re.sub的特有参数有repl和count,分别表示被替换的表达式和替换的总次数。
正则切割re.split的特有参数是maxsplit,最大切割次数。
这些将在后面详解。下面首先详解flags标志位:
简写 | 全称 | 含义 |
---|---|---|
A | ASCII | 让 \w , \W , \b , \B , \d , \D , \s 和 \S 只匹配ASCII,而不是Unicode。 |
U | UNICODE | 与 ASCII 模式相反,让 \w , \W , \b , \B , \d , \D , \s 和 \S 匹配Unicode例如 \w 字符集同时会包含英文字符和中文字符 |
I | IGNORECASE | 忽略大小写 |
L | LOCALE | 由当前语言区域决定是ASCII还是UNICODE,以及是否大小写敏感,这个标记只能对8位字节的byte数据有效。 由于语言区域机制很不可靠,这个标记不推荐使用,本文也不作演示。 |
M | MULTILINE | 开启多行模式,当某字符串中有换行符\n 时,让^ 和$ 分别能匹配行的开头和行的结尾,而不是整个字符串的开头和结尾 |
S | DOTALL | DOT表示. ,ALL表示所有,. 默认匹配除了换行符以外的任意字符。而这个标志位让. 匹配包含换行符\n 的任意字符 |
X | VERBOSE | 开启详细模式,可以在正则表达式中加python语法的#注释 |
T | TEMPLATE | 关闭回溯,只使用模板匹配,提高正则的性能 |
DEBUG | 显示编译时的debug信息。 |
在re模块库的源码中:https://github.com/python/cpython/blob/3.7/Lib/re.py
所有的flags标志位都定义在RegexFlag枚举类中:
class RegexFlag(enum.IntFlag):
ASCII = A = sre_compile.SRE_FLAG_ASCII # assume ascii "locale"
IGNORECASE = I = sre_compile.SRE_FLAG_IGNORECASE # ignore case
LOCALE = L = sre_compile.SRE_FLAG_LOCALE # assume current 8-bit locale
UNICODE = U = sre_compile.SRE_FLAG_UNICODE # assume unicode "locale"
MULTILINE = M = sre_compile.SRE_FLAG_MULTILINE # make anchors look for newline
DOTALL = S = sre_compile.SRE_FLAG_DOTALL # make dot match newline
VERBOSE = X = sre_compile.SRE_FLAG_VERBOSE # ignore whitespace and comments
# sre extensions (experimental, don't rely on these)
TEMPLATE = T = sre_compile.SRE_FLAG_TEMPLATE # disable backtracking
DEBUG = sre_compile.SRE_FLAG_DEBUG # dump pattern after compilation
使用方式:例如要忽略大小写就传入re.IGNORECASE 或简写的 re.I,要只匹配英文字符就传入re.ASCII 或简写的 re.A等等。如果需要同时使用多个模式,可以相加,例如我既要只匹配英文字符,还要开启多行模式,可以传入re.A+re.M。
我们可以看一个每个标志位对应的二进制位:
for flag in re.RegexFlag:
print(f"{flag.value:0>9b}", flag, flag.value)
结果:
100000000 RegexFlag.ASCII 256
000000010 RegexFlag.IGNORECASE 2
000000100 RegexFlag.LOCALE 4
000100000 RegexFlag.UNICODE 32
000001000 RegexFlag.MULTILINE 8
000010000 RegexFlag.DOTALL 16
001000000 RegexFlag.VERBOSE 64
000000001 RegexFlag.TEMPLATE 1
010000000 RegexFlag.DEBUG 128
可以看到每个模式数值对应的二进制位只占用1位。所以我们在使用多个模式时使用或
运算符性能更佳,例如re.A|re.M。
下面我们看下各种标示位的示例:
简写与首字母一致。
对于字符串:
s = "Midea美的"
我们只希望匹配其中的英文,就需要使用ASCII模式:
re.search('\w+', s, re.ASCII).group(0)
结果:
'Midea'
注意:
re.ASCII
可简写为re.A
假如不设置ASCII模式,默认模式是UNICODE模式:
re.search('\w+', s).group(0)
结果:
'Midea美的'
简写与首字母一致。
对于下面的字符串,希望能找出所有的Python字符串,可以采用使用忽略大小写模式:
s = "Python1 python2 PYTHON3"
re.findall('python', s, re.I)
由于I模式存在与(?iLmsux)中,还可以直接在正则里面写:
s = "Python1 python2 PYTHON3"
re.findall('(?i)python', s)
结果均为:
['Python', 'python', 'PYTHON']
如果不设置忽略大小写模式:
s = "Python1 python2 PYTHON3"
re.findall('python', s)
结果则为:
['python']
简写与首字母一致。
例如对于下面这段字符串:
s = """数据分析
软件工程
数据分析师
开发工程师
数据分析工程师
数据开发工程师
"""
我们希望取出每行以数据分析开头的文本就可以开启多行模式:
re.findall('^数据分析.*', s, re.M)
也可以直接通过正则本身(iLmsux范围内的字符都支持)开启多行模式:
re.findall('(?m)^数据分析.*', s)
结果均为:
['数据分析', '数据分析师', '数据分析工程师']
当然,如果没有设置多行模式,^和$的作用与\A
和\Z
的作用一致,仅匹配整个字符串的开头和字符串的结尾。
re.findall('^数据分析.*', s)
和
re.findall('\A数据分析.*', s, re.M)
结果均为:
['数据分析']
简写为S,并不是首字母。
例如我们有一段很长的sql脚本,我们希望能找到其中所有的以select(不区分大小写)开头的查询sql语句:
s="""CREATE TABLE GIRL AS
SELECT
SNO,
SNAME,
AGE
FROM
STUDENTS
WHERE SEX = ' 女 ';
SELECT
CNO,
CNAME
FROM
COURSES
WHERE CREDIT = 3 ;
-- 例 查询年龄大于 22 岁的学生情况。
SELECT
*
FROM
STUDENTS
WHERE AGE > 22 ;
-- 例 找出籍贯为河北的男生的姓名和年龄。
SELECT
SNAME,
AGE
FROM
STUDENTS
WHERE BPLACE = ' 河北 '
AND SEX = ' 男 ' ;"""
如果我们不开启DOTALL模式会相对麻烦一点,需要使用[\w\W]
来表示包含换行符的所有字符:
re.findall('^select [\w\W]+?;', s, re.I|re.M)
或:
re.findall('(?im)^select [\w\W]+?;', s)
结果:
['SELECT CNO,CNAME FROM COURSES WHERE CREDIT=3;',
'SELECT \n * \nFROM\n STUDENTS \nWHERE AGE > 22;',
"SELECT \n SNAME,\n AGE \nFROM\n STUDENTS \nWHERE BPLACE = '河北' \n AND SEX = '男';"]
但开启DOTALL模式,就可以直接使用.
来匹配包含换行符的所有字符,即:
re.findall('^select .+?;', s, re.I|re.M|re.S)
或
re.findall('(?ims)^select .+?;', s)
简写为X,并不是首字母。
该模式的作用就是可以在正则中写#号的注释,对于很复杂的正则,或许我们使用注释会更加清晰易懂。
例如我们有段字符串:
s = """中楼层(共9层)|2007年建|1室1厅|24.78平米|北
地下室|2014年建|1室0厅|39.52平米|东
底层(共2层)5室3厅|326.56平米|东南西北"""
我们需要提取出每行数据的 层、楼层数、建筑年份、户型、大小和方向。
如果直接写,或许这个正则阅读起来比较费劲:
re.findall("^([^|(]+)(?:\(共(\d+)层\))?(?:\|(\d{4})年建\|)?(\d室\d厅)\|([\d.]+)平米\|([东南西北]+)", s, re.M)
于是我们可以开启VERBOSE模式加个注释:
pattern = """^([^|(]+?) # 层
(?:\(共(\d+)层\))? # 楼层数
(?:\|(\d{4})年建\|)? # 建筑年份
(\d室\d厅) # 户型
\|
([\d.]+)平米 # 大小
\|
([东南西北]+) #方向
"""
re.findall(pattern, s, re.M|re.X)
也可以直接使用正则字符串本身来开启VERBOSE(简写X)模式:
pattern = """(?mx)^([^|(]+?) # 层
(?:\(共(\d+)层\))? # 楼层数
(?:\|(\d{4})年建\|)? # 建筑年份
(\d室\d厅) # 户型
\|
([\d.]+)平米 # 大小
\|
([东南西北]+) #方向
"""
re.findall(pattern, s)
结果均为:
[('中楼层', '9', '2007', '1室1厅', '24.78', '北'),
('地下室', '', '2014', '1室0厅', '39.52', '东'),
('底层', '2', '', '5室3厅', '326.56', '东南西北')]
再来一个简单的示例:
pattern = r'''(?mx)
^ # 开头
(\d{4}) # 年
[ ] # 空格
(\d{2}) # 月
$ # 结尾
'''
re.findall(pattern, '2020 06\n2020 07')
结果:
[('2020', '06'), ('2020', '07')]
当然,正则本身也支持通过(?#ABC)
增加注释ABC
,例如:
"(\w+)(?#word) \1(?#word repeat again)"
简写与首字母一致。
该模式的作用是关闭回溯,在前面的贪婪模式、非贪婪模式和独占模式一节中,已经讲解过回溯的过程,贪婪模式和非贪婪模式都需要发生回溯才能完成相应的功能。
TEMPLATE表示模板的意思,开启该模式意味着只能使用正则的模板匹配,而不能使用回溯算法,意味着不能再使用任意数量词,包括*、?、+、{m,n}等,哪怕固定数量的{4}也不允许。
例如我们想要获取一个时间字符串的年月日:
s = "1980-02-12"
re_match = re.match(r'(\d{4})-(\d{2})-(\d{2})', s)
re_match.group(1), re_match.group(2), re_match.group(3)
结果:
('1980', '02', '12')
很明显这个时间字符串的每个部分,长度都是确定而且固定的,那我们就完全可以开启TEMPLATE模式,关闭回溯算法。
但直接关闭会报错:
s = "1980-02-12"
re_match = re.match(r'(?t)(\d{4})-(\d{2})-(\d{2})', s)
re_match.group(1), re_match.group(2), re_match.group(3)
error: internal: unsupported template operator MAX_REPEAT
必须这样写:
s = "1980-02-12"
re_match = re.match('(\d\d\d\d)-(\d\d)-(\d\d)', s, re.T)
re_match.group(1), re_match.group(2), re_match.group(3)
或
s = "1980-02-12"
re_match = re.match('(?t)(\d\d\d\d)-(\d\d)-(\d\d)', s)
re_match.group(1), re_match.group(2), re_match.group(3)
这个模式目前连官网文档没有任何说明,开启这个模式能否相对直接执行不会发生回溯的正则是否能提升效率还未知。
这个模式没有简写,对于一般的用户用不上。开启这个模式之后,编译正则表达式时会打印出正则的解释树信息,这些信息并不是任何一种编程语言,而是正则表达式特有的解析树,就类似于hive sql语句编译的解析树一样。通过解析树可以让高级开发人员更清楚了解这个正则执行的性能和效率。
我们随便查看一个正则的编译信息:
re.compile('(\d{2}) ?-12', re.DEBUG)
结果:
SUBPATTERN 1 0 0
MAX_REPEAT 2 2
IN
CATEGORY CATEGORY_DIGIT
MAX_REPEAT 0 1
LITERAL 32
LITERAL 45
LITERAL 49
LITERAL 50
0. INFO 4 0b0 5 6 (to 5)
5: MARK 0
7. REPEAT_ONE 9 2 2 (to 17)
11. IN 4 (to 16)
13. CATEGORY UNI_DIGIT
15. FAILURE
16: SUCCESS
17: MARK 1
19. REPEAT_ONE 6 0 1 (to 26)
23. LITERAL 0x20 (' ')
25. SUCCESS
26: LITERAL 0x2d ('-')
28. LITERAL 0x31 ('1')
30. LITERAL 0x32 ('2')
32. SUCCESS
正则匹配即查找并返回一个匹配项。
re模块完成正则匹配功能的函数有3个:
search: 从字符串任意位置开始匹配,返回第一个匹配成功的对象,匹配失败函数返回None
match: 从字符串开头开始匹配,匹配失败函数返回None
fullmatch: 整个字符串与正则完全匹配
它们的参数均为:
re.xxx(pattern, string, flags=0)
search方法从字符串任意位置开始查找,适配性最强,可以通过加入^
匹配开头达到跟match相同的效果,match也可以通过加入$
匹配结尾达到跟fullmatch相同的效果。
首先测试一下search:
print(re.search('www', 'www.taobao.com'))
print(re.search('com', 'www.taobao.com'))
<re.Match object; span=(0, 3), match='www'>
<re.Match object; span=(11, 14), match='com'>
测试match:
print(re.match('www', 'www.taobao.com'))
print(re.match('com', 'www.taobao.com'))
<re.Match object; span=(0, 3), match='www'>
None
最后测试fullmatch:
print(re.fullmatch('www', 'www.taobao.com'))
print(re.fullmatch('com', 'www.taobao.com'))
print(re.fullmatch('www.taobao.com', 'www.taobao.com'))
None
None
<re.Match object; span=(0, 14), match='www.taobao.com'>
从上述结果中,我们可以清晰的看到search、match和fullmatch三者的区别:
由于’com’在字符串’www.taobao.com’的末尾,所以match函数未匹配到任何结果返回None;而fullmatch函数由于是匹配整个字符串,所以’www’匹配’www.taobao.com’时也返回None。
re.MatchObject
对象同时可以看到,它们均返回了一个re.Match
对象,该对象提供了group(num) 和 groups()方法,group(num) 用于返回对应分组编号的数据,groups()方法用于返回所有分组的数据,而lastindex属性可以获取分组的个数。
示例:
line = "Cats are smarter than dogs"
matchObj = re.match(r'(.*?) are (.*?) ', line, re.I)
if matchObj:
print("总分组数:", matchObj.lastindex)
print("所有分组的数据:",matchObj.groups())
print("整个被匹配的字符串 : ", matchObj.group())
print("第1个分组的数据 : ", matchObj.group(1))
print("第2个分组的数据 : ", matchObj.group(2))
else:
print("No match!!")
结果:
总分组数: 2
所有分组的数据: ('Cats', 'smarter')
整个被匹配的字符串 : Cats are smarter
第1个分组的数据 : Cats
第2个分组的数据 : smarter
re.MatchObject
对象的其他方法:
start() 返回匹配开始的位置
end() 返回匹配结束的位置
span() 返回一个元组包含匹配 (开始,结束) 的位置
目前主要的手机号前三位是:
中国电信号段:133,153, 180,181,189,173, 177,149
中国联通号段:130,131,132,155,156,185,186,145,176,185
中国移动号段:134,135,136,137,138,139,150,151,152,157,158,159,182,183,184,147,178
规律是:
第一位 :1
第二位:3,4,5,7,8
第三位:根据第二位来确定
3 + 【0-9】
4 + 【5,7,9】
5 + 【0-9】!4
7 + 【0-9】! 4和9
8 + 【0-9】
对手机号比较粗略的匹配(11位数字,前2位符合手机号规则):
"1[34578]\d{9}"
较为精确的匹配(11位数字,前3位符合手机号规则):
"1(?:[38]\d|4[579]|5[0-35-9]|7[0-35-8])\d{8}"
测试较为精确匹配:
import re
import random
def random_number(nums):
result = ""
for x in range(nums):
result += str(random.randint(0, 9))
return result
nums = [
133, 153, 180, 181, 189, 173, 177, 149,
130, 131, 132, 155, 156, 185, 186, 145, 176, 185,
134, 135, 136, 137, 138, 139, 150, 151, 152, 157, 158, 159, 182, 183, 184, 147, 178
]
for num in nums:
print(re.fullmatch("1([38]\d|4[579]|5[0-35-9]|7[0-35-8])\d{8}",
f"{num}{random_number(8)}").group(), end=",")
结果:
13320640138,15352178619,18010467102,18124689139,18975065050,17380280568,17798275371,14994833499,13068873816,13151192893,13289047370,15594125464,15648216940,18574982445,18643788553,14516397708,17616874062,18559031583,13443533383,13596265766,13629806068,13745249866,13896644123,13954817486,15076523907,15182868824,15229880699,15794102747,15852468936,15938064514,18297190705,18304331736,18402303981,14751356440,17847872471,
全部成功匹配上。
测试一个错误的电话号码:
pattern = "1([38]\d|4[579]|5[0-35-9]|7[0-35-8])\d{8}"
tel_number = "15452468936"
print(re.fullmatch(pattern, tel_number))
结果:
None
也成功的匹配失败。
邮箱地址的规则是: user@mail.server.name,即名称+@+网站
常见的邮箱地址一般都是@xxx.com,但也还包括一些特殊邮箱地址,能到三级域名甚至四级域名,例如:
@SEED.NET.TW @TOPMARKEPLG.COM.TW @wilnetonline.net @cal3.vsnl.net.in
当然这只是少部分,大部分都是二级域名,但我们不能因此让这些域名匹配不成功。
例如,我们认为下面的邮箱地址都是合法的邮箱地址:
emails = [
'someone@gmail.com',
'bill.gates@microsoft.com',
'mr-bob@example.com',
'someone@SEED.NET.TW',
'chuck.gt@cal3.vsnl.net.in'
]
正则匹配规则可以写为:
r"[a-z.-]+@[[a-zA-Z0-9]+(\.[a-zA-Z]+){1,3}"
测试:
for email in emails:
match_obj = re.match(r"[a-z.-]+@[[a-zA-Z0-9]+(\.[a-zA-Z]+){1,3}", email, re.I)
if match_obj:
print(match_obj.group(0))
结果:
someone@gmail.com
bill.gates@microsoft.com
mr-bob@example.com
someone@SEED.NET.TW
chuck.gt@cal3.vsnl.net.in
再顺便测试一个不是邮箱的字符串:
print(re.match(r"[a-z.-]+@[[a-zA-Z0-9]+(\.[a-zA-Z]+){1,3}", 'bob#example.com', re.I))
未通过校验,打印结果为None。
前面的正则匹配规则表中说过:
\<number>
表示引用编号为\<number>
的分组匹配到的字符串
示例
IT后台有一批用户名和密码的字符串,部门希望找出那些将密码设置的跟用户名一样的用户提醒他们修改密码:
users = [
"user1:password",
"user2:user2",
"user3:password",
"user4:password",
"user5:password",
"user6:user6",
"user7:password",
"user8:user8",
"user9:password",
"user10:user10"
]
这时,在匹配时引用分组就会非常方便:
for user in users:
match_obj = re.match(r"(\w+):\1", user, re.A)
if match_obj:
print(match_obj.group(1))
结果:
user2
user6
user8
user10
可以看到顺利的提取出了,用户名和密码一致的用户。
实现正则查找的函数有:
看完了正则匹配,相信正则查找对于你来说已经很简单。下面直接举几个例子。
示例1
我们需要找出这段文本中所有的数字:
s = ' taobao 123 google 456'
re.findall("\d+", s)
结果:
['123', '456']
使用finditer返回迭代器:
it = re.finditer("\d+", s)
for match_obj in it:
print(match_obj.group(), end=" ")
结果:
123 456
示例2
例如我们希望查找出下面这段英文中所有4个字母的单词:
s = "Clothes are so significant in our daily life that we can't live without them"
re.findall(r"\b[a-z]{4}\b", s, re.I)
结果:
['life', 'that', 'live', 'them']
可以看到很顺利的找到了想要的结果。
\b
表示单词边界,可以回正则规则匹配表查看
也可以使用re.finditer方法返回一个迭代器:
for match_obj in re.finditer(r"\b[a-z]{4}\b", s, re.I):
print(match_obj.group(), end=" ")
结果:
life
that
live
them
注意:re.finditer方法返回的迭代器迭代取出的每一个对象都是
re.Match
对象
示例3
提取出下面文本中所有的单词(被双引号引起来的要作为一个单词,例如the little cat,最终结果无需去重):
we found “the little cat” is in the hat, we like “the little cat”
s = 'we found "the little cat" is in the hat, we like "the little cat"'
print(re.findall('\w+|".*?"', s))
结果:
['we', 'found', '"the little cat"', 'is', 'in', 'the', 'hat', 'we', 'like', '"the little cat"']
示例4
提取出下面网页中head 标签的内容:
<html>
<head>
<title>学习正则表达式</title>
</head>
<body></body>
</html>
参考解法:
s = """<html>
<head>
<title>学习正则表达式</title>
</head>
<body></body>
</html>"""
re.findall("(?si)<head>(.*)<\/head>", s)
结果:
['\n\t\t<title>学习正则表达式</title>\n\t']
实现正则替换的函数有re.sub和re.subn,它们参数均是:
re.sub*(pattern, repl, string, count=0, flags=0)
参数:
pattern : 正则中的模式字符串。
repl : 替换的表达式,也可为一个函数。
string : 要被替换的原始字符串。
count : 模式匹配后替换的最大次数,默认 0 表示替换所有的匹配。
re.subn相对re.sub的区别是会在re.sub返回结果的基础上额外返回替换次数。
有一个电话号码带注释的字符串:
phone = "2004-959-559 # 这是一个电话号码"
如果我们需要删除注释:
num = re.sub(r'#.*$', "", phone)
print("电话号码:", num)
结果:
电话号码: 2004-959-559
删除所有非数字的内容:
num = re.sub(r'\D', "", phone)
print("电话号码:", num)
结果:
电话号码: 2004959559
给金额添加万分符。
有一个金额字符串:
s = """5305256725元
4220元
870元
7866369414527元
144995元
2069993310元
354070715448元
711元
2113046206元"""
需要给万亿、亿、万位置添加逗号,例如7866369414527元
被转换为7,8663,6941,4527元
。
这些位置均为距离元4n个字符的位置,所以可以这样写:
print(re.sub(r"(?<=\d)(?=(?:\d{4})+元)", ",", s, flags=re.M))
结果:
53,0525,6725元
4220元
870元
7,8663,6941,4527元
14,4995元
20,6999,3310元
3540,7071,5448元
711元
21,1304,6206元
(?<=\d)
表示左边必须是一个数字,(?=(?:\d{4})+元)
表示右边必须是紧挨元,而且是4n个数字。
这样在对应的位置替换成,
,便添加了万分符。
\<number>
表示引用编号为\<number>
的分组匹配到的字符串,这个规则不仅可以在匹配表达式中使用,还可以在替换表达式中使用。
需求1:将重叠的字符替换成单个字符(zzzz->z)
例如,将
“我我…我我…我要…要要…要要…学学学…学学…编编编…编程…程.程程…程…程”
转成:
“我要学编程”
思路:
.
去掉。s = "我我...我我...我要..要要...要要...学学学....学学...编编编...编程..程.程程...程...程"
# 去掉所有的字符.
s = s.replace(".", "")
# 连续重复字符转单个字符
s = re.sub(r"(.)\1+", r"\1", s)
s
结果:
'我要学编程'
那么如果使用subn方法有什么特别之处呢?
s = "我我...我我...我要..要要...要要...学学学....学学...编编编...编程..程.程程...程...程"
# 去掉所有的字符.
s = s.replace(".", "")
print("去掉字符.之后:", s)
# 连续重复字符转单个字符
s, count = re.subn(r"(.)\1+", r"\1", s)
print("结果:", s)
print("替换次数:", count)
结果:
去掉字符.之后: 我我我我我要要要要要学学学学学编编编编程程程程程程
结果: 我要学编程
替换次数: 5
可以看到subn方法可以通过元组匹配的方式,额外得到替换的次数,但目前我还没有遇到哪个场景需要得到这个替换次数,但或许哪天你真需要知道替换多少次的时候,使用subn能省不少事。
**需求2:**连续单词去重
有一篇英文文章,里面有一些单词连续出现了多次,我们认为连续出现多次的单词应该是一次,比如:
the little cat cat is in the hat hat hat2, we like it.
其中 cat 和 hat 连接出现多次,要求处理后结果是:
the little cat is in the hat hat2, we like it.
s = "the little cat cat is in the hat hat hat2, we like it."
re.sub(r"(\b\w+)(?:\s+\1\b)+", r"\1", s)
结果:
'the little cat is in the hat hat2, we like it.'
**需求2:**将ip地址进行地址段顺序的排序。
有一个ip字符串:
s = "192.68.1.254 102.49.23.013 10.10.10.10 2.2.2.2 8.109.90.30"
现在需要让它内部的每个ip排序输出。
思路:
s = "192.68.1.254 102.49.23.013 10.10.10.10 2.2.2.2 8.109.90.30"
# 1. 按照每一段需要的最多的0进行补齐,那么每一段就会至少保证有3位。
s = re.sub(r"(\d+)", r"00\1", s)
print("每段开头补2个0后:", s)
# 2. 将每一段只保留3位。这样,所有的ip地址都是每一段3位。
s = re.sub(r"0*(\d{3})", r"\1", s)
print("每段仅保留3个数字:", s)
# 3. 切割排序,并拼接排好序的ip地址字符串
s = " ".join(sorted(s.split()))
print("切割排序并拼接后:", s)
# 4. 去掉结果字符串每个数字开头的0
s = re.sub(r"0*(\d+)", r"\1", s)
print("最终结果:", s)
结果:
每段开头补2个0后: 00192.0068.001.00254 00102.0049.0023.00013 0010.0010.0010.0010 002.002.002.002 008.00109.0090.0030
每段仅保留3个数字: 192.068.001.254 102.049.023.013 010.010.010.010 002.002.002.002 008.109.090.030
切割排序并拼接后: 002.002.002.002 008.109.090.030 010.010.010.010 102.049.023.013 192.068.001.254
最终结果: 2.2.2.2 8.109.90.30 10.10.10.10 102.49.23.13 192.68.1.254
可以看到最终实现了,ip地址的排序。
repl 替换表达式,也可传入一个函数,这个函数的参数必须是一个re.MatchObject
对象(参看前面的正则匹配部分)。
在其他编程语言中,正则表达式的替换功能,往往都是不支持传入函数的,导致要实现一些数值计算性的功能代码会变得比较复杂,而python的正则替换由于支持函数,所以可以很简单的实现一些较为复杂的逻辑。
先从简单的例子开始:
示例1:数值翻倍
假如我们有一个字符串:
s = 'A23G4HFD567'
希望将这个字符串所有连续的数字都翻倍,使用正则替换传入函数会非常方便:
s = 'A23G4HFD567'
print(re.sub('\d+', lambda m: str(int(m.group(0))*2), s))
假如python的正则替换不支持传入函数就会相对比较复杂:
buff = list(s)
for m in re.finditer("\d+", s):
pos = m.span()
buff[pos[0]:pos[1]] = list(str(int(m.group(0))*2))
s = "".join(buff)
s
结果均为:
'A46G8HFD1134'
示例2:数值隔断
有一个字符串:
s='AB837D5D4F7G8H7F8H56D4D7G4D3'
想将这个字符串所有>=6的单个数字替换成9, <6的单个数字替换为0:
s = 'AB837D5D4F7G8H7F8H56D4D7G4D3'
print(re.sub('\d', lambda m:'9' if int(m.group()) >= 6 else '0', s))
结果:
AB909D0D0F9G9H9F9H09D0D9G0D0
示例3:顺序编号
有一段字符串"a,b,c,d,e,f"
,我们希望将每一个出现的字母增加一个递增的编号,比如:
s = "a,b,c,d,e,f"
希望得到结果:'1.a,2.b,3.c,4.d,5.e,6.f'
使用编号迭代器+正则替换会变得非常简单:
s = "a,b,c,d,e,f"
numbers = iter(range(1, 10000))
re.sub("\w", lambda m: f"{next(numbers)}.{m.group()}", s)
结果:
'1.a,2.b,3.c,4.d,5.e,6.f'
我们使用的编号不可能超过1万,所以range函数的最大值传入10000即可,iter获取了range对象的迭代器,从而得到了一个可以不断获取下一个编号的编号迭代器。
顺序编号的比较典型应用场景是模板数据回传,举个比较傻的例子:
比如有一个含有很多sql查询语句的大文本,我们需要将其中所有的sql语句提取出来,执行完毕,再将查询结果写回到sql语句原本所在的位置。
要实现这个功能,首先可以先将所有的sql语句都替换成顺序编号的占位符,我们就以下面这个比较简单的文本为例吧:
s="""
-- 一个查询
SELECT
CNO,
CNAME
FROM
COURSES
WHERE CREDIT = 3;
-- 例 查询年龄大于 22 岁的学生情况。
SELECT
*
FROM
STUDENTS
WHERE AGE > 22 ;
-- 例 找出籍贯为河北的男生的姓名和年龄。
SELECT
SNAME,
AGE
FROM
STUDENTS
WHERE BPLACE = ' 河北 '
AND SEX = ' 男 ' ;"""
只需执行:
numbers = iter(range(10000))
template_text = re.sub("^select .+?;", lambda m: "{%d}" % next(numbers), s, flags=re.I | re.M | re.S)
print(template_text)
结果:
-- 一个查询
{0}
-- 例 查询年龄大于 22 岁的学生情况。
{1}
-- 例 找出籍贯为河北的男生的姓名和年龄。
{2}
实现正则切割的函数是re.split,它的参数是:
re.split(pattern, string, maxsplit=0, flags=0)
这个函数相对前面的函数多了maxsplit,表示最大切割次数。
该函数最常见的应用场景就是字段分割。
例如,我们需要切割出下面这个字符串的每个连续的字符串(含有不确定数量的空格和tab):
s="FRN2004001 100VCP772Z 417BX 417BX181128307CN1012202000 5,004EA2020.03.3045408263L12L12"
可以使用正则进行切割:
fields = re.split("\s+", s)
print(fields)
结果:
['FRN2004001', '100', 'VCP772Z', '417', 'BX', '417', 'BX', '181128307', 'CN10', '1220', '2000', '5,004', 'EA', '2020.03.30', '45408263', 'L12', 'L12']
如果我们希望最后两个L12不被切割,可以设置maxsplit:
print(re.split("\s+", s, maxsplit=15))
结果:
['FRN2004001', '100', 'VCP772Z', '417', 'BX', '417', 'BX', '181128307', 'CN10', '1220', '2000', '5,004', 'EA', '2020.03.30', '45408263', 'L12\tL12']
这样最后一个空白字符\t就没有被切割。
当然对于这个例子,直接使用字符串自带的切割就可以实现,不传参数模式就是用连续的空白字符切割:
s.split()
和
s.split(maxsplit=15)
结果与上面一致。
下面举一个必须用正则切割才能解决的问题:
环视切割,有一个字符串:
s = "北京西北京站北京北北京南站北京东"
我们需要取出其中所有的北京xx,即北京西、北京站、北京北、北京南站 和 北京东。
使用正则切割会非常简单:
s = "北京西北京站北京北北京南站北京东"
re.split("(?<!^)(?=北京)", s)
结果:
['北京西', '北京站', '北京北', '北京南站', '北京东']
在前面的正则匹配规则表中的非捕获组与环视已经说明:
- (?=…) 肯定环视,表示右边是指定内容的位置
- (?<!..) 否定逆序环视,表示左边不是指定内容的位置
(?<!^)
表示切割位置的左边不能是行的开头,(?=北京)
表示切割位置的右边必须是北京
re.compile() 返回 re.Pattern正则表达式编译对象(跟java语言的Pattern类原理一样)。
语法格式为:
re.compile(pattern, flags)
前面的每个正则方法:re.fullmatch、re.findall、re.sub、re.split等方法,执行过程中都会先编译正则表达式(开启DEBUG模式可以看到解析树),如果有些正则表达式会反复被使用,重复的编译会造成较大的资源浪费。于是我们可以通过re.compile方法提前将正则表达式编译好,以后反复使用不会重复编译。
编译一个正则测试一下:
pattern = re.compile('(\d+)')
print(pattern, type(pattern))
结果:
re.compile('(\\d+)') <class 're.Pattern'>
可以看到:
print([m for m in dir(pattern) if not m.startswith("__")])
['findall', 'finditer', 'flags', 'fullmatch', 'groupindex', 'groups', 'match', 'pattern', 'scanner', 'search', 'split', 'sub', 'subn']
具备上述所有方法。
正则匹配:
pattern.search(' taobao 123 google 456')
结果:
<re.Match object; span=(9, 12), match='123'>
正则查找:
pattern.findall(' taobao 123 google 456')
结果:
['123', '456']
正则替换:
pattern.sub("", "2004-959-559 # 这是一个电话号码")
结果:
'-- # 这是一个电话号码'
正则切割:
pattern.split('AB837D5D4F7G8H7F8H56D4D7G4D3')
结果:
['AB', 'D', 'D', 'F', 'G', 'H', 'F', 'H', 'D', 'D', 'G', 'D', '']
来源于python官方文档:https://docs./zh-cn/3.7/library/re.html
本节参考极客时间的课程:《正则表达式入门课》
正则表达式的起源,可以追溯到,早期神经系统如何工作的研究。在 20 世纪 40 年代,有两位神经生理学家(Warren McCulloch 和 Walter Pitts),研究出了一种用数学方式来描述神经网络的方法。
1956 年,一位数学家(Stephen Kleene)发表了一篇标题为《神经网络事件表示法和有穷自动机》的论文。这篇论文描述了一种叫做“正则集合(Regular Sets)”的符号。
随后,大名鼎鼎的 Unix 之父 Ken Thompson 于 1968 年发表了文章《正则表达式搜索算法》,并且将正则引入了自己开发的编辑器 qed,以及之后的编辑器 ed 中,然后又移植到了大名鼎鼎的文本搜索工具 grep 中。自此,正则表达式被广泛应用到 Unix 系统或类 Unix 系统 (如 macOS、Linux) 的各种工具中。
随后,由于正则功能强大,非常实用,越来越多的语言和工具都开始支持正则。不过遗憾的是,由于没有尽早确立标准,导致各种语言和工具中的正则虽然功能大致类似,但仍然有不少细微差别。
于是,诞生于 1986 年的 POSIX 开始进行标准化的尝试。POSIX作为一系列规范,定义了 Unix 操作系统应当支持的功能,其中也包括正则表达式的规范。因此,Unix 系统或类 Unix 系统上的大部分工具,如 grep、sed、awk 等,均遵循该标准。我们把这些遵循 POSIX 正则表达式规范的正则表达式,称为 POSIX 流派的正则表达式。
在 1987 年 12 月,Larry Wall 发布了 Perl 语言第一版,因其功能强大一票走红,所引入的正则表达式功能大放异彩。之后 Perl 语言中的正则表达式不断改进,影响越来越大。于是在此基础上,1997 年又诞生了PCRE——Perl 兼容正则表达式(Perl Compatible Regular Expressions)。
PCRE 是一个兼容 Perl 语言正则表达式的解析引擎,是由 Philip Hazel 开发的,为很多现代语言和工具所普遍使用。除了 Unix 上的工具遵循 POSIX 标准,PCRE 现已成为其他大部分语言和工具隐然遵循的标准。
之后,正则表达式在各种计算机语言或各种应用领域得到了更为广泛的应用和发展。POSIX 流派 与 PCRE 流派 是目前正则表达式流派中的两大最主要的流派。
目前正则表达式主要有两大流派(Flavor):POSIX 流派与 PCRE 流派。
POSIX 规范定义了正则表达式的两种标准:
BRE 标准(Basic Regular Expression 基本正则表达式);
ERE 标准(Extended Regular Expression 扩展正则表达式)。
这两种标准有什么的异同点呢?
早期 BRE 与 ERE 标准的区别主要在于,BRE 标准不支持数量词问号和加号,也不支持多选分支结构管道符。BRE 标准在使用花括号,圆括号时要转义才能表示特殊含义。ERE 标准则在BRE 标准基础上有了一定改进 ,在使用花括号,圆括号时不需要转义了,还支持了问号、加号 和 多选分支。
Linux 发行版大多都集成了 GNU 套件。GNU 在实现 POSIX 标准时,做了一定的扩展:
\+
、\?
表示。\|
表示。BRE 标准和 ERE 标准的详细区别(浅黄色背景是 BRE 和 ERE 不同的地方,三处天蓝色字体是 GNU 扩展):
总之,GNU BRE 和 GNU ERE 它们的功能特性并没有太大区别,区别是在于部分语法层面上,主要是一些字符要不要转义。
POSIX 字符组:
POSIX 流派有自己的字符组,叫 POSIX 字符组。这类似于前面正则匹配规则表中预定义字符集中的 \d 表示数字,\s 表示空白符等,POSIX 中也定义了一系列的字符组。具体的清单和解释如下所示:
除了 POSIX 标准外,还有一个 Perl 分支,也就是大家现在熟知的 PCRE。随着 Perl 语言的发展,Perl 语言中的正则表达式功能越来越强悍,为了把 Perl 语言中正则的功能移植到其他语言中,PCRE 就诞生了。
目前大部分编程语言的正则表达式都是源于 PCRE 标准,前面的python正则表达式也是基于PCRE 标准实现,这个流派显著特征是有\d、\w、\s 这类字符组简记方式。
虽然 PCRE 流派是从 Perl 语言中衍生出来的,但与 Perl 语言中的正则表达式在语法上还是有一些细微差异。
虽然 PCRE 流派是与 Perl 正则表达式相兼容的流派,但这种兼容在各种语言和工具中还存在程度上的差别,这包括了直接兼容与间接兼容两种情况。
而且,即便是直接兼容,也并非完全兼容,还是存在部分不兼容的情况。原因也很简单,Perl 语言中的正则表达式在不断改进和升级之中,其他语言和工具不可能完全做到实时跟进与更新。
直接兼容,PCRE 流派中与 Perl 正则表达式直接兼容的语言或工具。比如 Perl、PHP preg、PCRE 库等,一般称之为 Perl 系。
间接兼容,比如 Java 系(包括 Java、Groovy、Scala 等)、Python 系(包括 Python2 和 Python3)、JavaScript 系(包括原生 JavaScript 和扩展库 XRegExp)、.Net 系(包括 C#、VB.Net 等)等。
在遵循 POSIX 规范的 UNIX/LINUX 系统上,按照 BRE 标准 实现的有 grep、sed 和 vi/vim 等,而按照 ERE 标准 实现的有 egrep、awk 等。
在 UNIX/LINUX 系统里 PCRE 流派与 POSIX 流派的对比:
其实上表中的一些linux工具实现同时兼容多种正则标准,比如 grep 和 sed。如果在使用时加上 -E 选项,就是使用 ERE 标准;加上 -P 选项,就是使用 PCRE 标准。
使用 ERE 标准:
grep -E '[[:digit:]]+' access.log
使用 PCRE 标准:
grep -P '\d+' access.log
在 Linux 系统中可以使用 man 命令查看某个工具所属的流派,例如执行man grep
:
可以看到选项 -G 是指定使用 BRE 标准(默认),-E 是 ERE 标准,-P 是 PCRE 标准。
[root@VM_0_9_centos tmp]# cat a.txt
abcdf
12345
[root@VM_0_9_centos tmp]# grep '\d+' a.txt
[root@VM_0_9_centos tmp]# grep -E '\d+' a.txt
abcdf
[root@VM_0_9_centos tmp]# grep -E '[0-9]+' a.txt
12345
[root@VM_0_9_centos tmp]# grep -P '\d+' a.txt
12345
[root@VM_0_9_centos tmp]# grep -P '[0-9]+' a.txt
12345
在 grep 中直接使用 \d+ 查找不到结果是因为默认的 grep 属于 BRE 流派,而 grep -E
属于 ERE 流派也不支持 \d,\d 相当于字母 d,所以找到了字母那一行。而grep -P
属于 PCRE 标准所以能用python几乎相同的正则规则匹配到数字。
当然grep -E
也可以使用egrep替代,上面的命令可以更换为:
[root@VM_0_9_centos tmp]# egrep '[0-9]+' a.txt
12345
[root@VM_0_9_centos tmp]# egrep '\d+' a.txt
abcdf
下面我们希望分别使用不同的标准(即 BRE、ERE、PCRE )找出下面这段文本中含有 ftp、http 或 https 的行:
[root@VM_0_9_centos tmp]# cat b.txt
https://time.
ftp://ftp.ncbi.nlm.nih.gov
www.baidu.com
www.ncbi.nlm.nih.gov
参考答案:
[root@VM_0_9_centos tmp]# grep 'ftp\|https\?' b.txt
https://time.
ftp://ftp.ncbi.nlm.nih.gov
[root@VM_0_9_centos tmp]# egrep 'ftp|https?' b.txt
https://time.
ftp://ftp.ncbi.nlm.nih.gov
[root@VM_0_9_centos tmp]# grep -P 'ftp|https?' b.txt
https://time.
ftp://ftp.ncbi.nlm.nih.gov
在前面贪婪模式与非贪婪模式一节讲了回溯算法。下面将简单讲解 DFA 和 NFA 引擎的工作方式,即正则匹配过程。
这些原理性的知识,能够帮助我们快速理解为什么有些正则表达式不符合预期,避免一些常见的错误。只有了解正则引擎的工作原理,我们才可以更轻松地写出正确的,性能更好的正则表达式。
在线正则表达式图形化工具Regexper:http://regex./
正则之所以能够处理复杂文本,就是因为采用了有穷状态自动机(finite automaton)。
有穷自动机的具体实现称为正则引擎,主要有 DFA 和 NFA 两种:
而 NFA 又分为传统的 NFA 和 POSIX NFA。
接下来我们来通过一些示例,来看下正则表达式的匹配过程:
在使用正则表达式时,我们经常会“编译”一下,来提升效率,比如:
import re
re.compile(r'a(?:bb)+a')
这个编译的过程,其实就是生成自动机的过程,正则引擎会拿着这个自动机去和字符串进行匹配。生成的自动机可能是这样的:
在状态 s3 时,不需要输入任何字符,状态也有可能转换成 s1。可以理解成 a(bb)+a 在匹配了字符 abb 之后,到底在 s3 状态,还是在 s1 状态,这是不确定的。这种状态机就是非确定性有穷状态自动机(Non-deterministic finite automaton 简称 NFA)。
**NFA 和 DFA 是可以相互转化的,**当我们把上面的状态表示成下面这样,就是一台 DFA 状态机了,因为在 s0-s4 这几个状态,每个状态都需要特定的输入,才能发生状态变化。
下面看看这两种状态机的工作方式的差异:
假设我们使用的字符串和正则如下:
字符串:we search use baidu engine
正则:use (sogou|baidu|bing|google)
NFA 引擎的工作方式是,先看正则,再看文本,而且以正则为主导。正则中的第一个字符是u,NFA 引擎在字符串中查找u,接着匹配其后是否为s ,如果是s则继续,这样一直找到 "use "
。
regex: use (sogou|baidu|bing|google)
^
text: we search use baidu engine
^
再根据正则看文本后面是不是b,发现不是,此时 sogou分支淘汰。
regex: use (sogou|baidu|bing|google)
^
淘汰此分支(sogou)
text: we search use baidu engine
^
我们接着看其它的分支,看文本部分是不是 b,直到 baidu 整个匹配上。当匹配上了 baidu后,整个文本匹配完毕,也不会再看 bing分支和google分支。否则匹配失败会继续尝试匹配 bing分支。
假设这里text文本改一下,把 baidu变成 bing,正则 baidu的a匹配不上时 bing 的 i,会接着使用正则bing来进行匹配,重新从b开始(NFA 引擎会记住这里)。
第二个分支匹配失败:
regex: use (sogou|baidu|bing|google)
^
淘汰此分支(正则a匹配不上文本i)
text: we search use bing engine
^
再次尝试第三个分支:
regex: use (sogou|baidu|bing|google)
^
text: we search use bing engine
^
也就是说, NFA 是以正则为主导,反复测试字符串,这样字符串中同一部分,有可能被反复测试很多次。
而 DFA会先看文本,再看正则表达式,是以文本为主导的。在具体匹配过程中,DFA 会从 we 中的 w 开始依次查找u,定位到 u,这个字符后面是s。所以我们接着看正则部分是否有s,如果正则后面是个s,那就以同样的方式,匹配到后面的"se "。
text: we search use bing engine
^
regex: use (sogou|baidu|bing|google)
^
继续进行匹配,空字符串后面的字符是b ,DFA接着看正则表达式部分,此时 sogou分支和google分支被淘汰,开头是b的分支 baidu和 bing符合要求。
text: we search use bing engine
^
regex: use (sogou|baidu|bing|google)
^ ^ ^ ^
淘汰 符合 符合 淘汰
然后 DFA 依次检查字符串,检测到 bing中的 i 时,只有 bing分支符合,淘汰 baidu,接着看分别文本后面的 ng,和正则比较,匹配成功。
text: we search use bing engine
^
regex: use (sogou|baidu|bing|google)
^ ^
淘汰 符合
可以看到,NFA 是以表达式为主导的,先看正则表达式,再看文本。而 DFA 则是以文本为主导,先看文本,再看正则表达式。
一般来说,DFA 引擎会更快一些,因为整个匹配过程中,字符串只看一遍,不会发生回溯,相同的字符不会被测试两次。也就是说 DFA 引擎执行的时间一般是线性的。DFA 引擎可以确保匹配到可能的最长字符串。但由于 DFA 引擎只包含有限的状态,所以它没有反向引用功能;并且因为它不构造显示扩展也不支持捕获子组。
NFA 以表达式为主导,它的引擎是使用贪心匹配回溯算法实现。NFA 通过构造特定扩展,支持子组和反向引用。但由于 NFA 引擎会发生回溯,即它会对字符串中的同一部分,进行很多次对比。因此,在最坏情况下,它的执行速度可能非常慢。
因为传统的 NFA 引擎“急于”报告匹配结果,找到第一个匹配上的就返回了,所以可能会导致还有更长的匹配未被发现。比如使用正则 pos|posix 在文本 posix 中进行匹配,传统的 NFA 从文本中找到的是 pos,而不是 posix,而 POSIX NFA 找到的是 posix。
POSIX NFA 的应用很少,主要是 Unix/Linux 中的某些工具。POSIX NFA 引擎与传统的 NFA 引擎类似,但不同之处在于,POSIX NFA 在找到可能的最长匹配之前会继续回溯,也就是说它会尽可能找最长的,如果分支一样长,以最左边的为准(“The Longest-Leftmost”)。因此,POSIX NFA 引擎的速度要慢于传统的 NFA 引擎。
我们日常面对的,一般都是传统的 NFA,所以通常都是最左侧的分支优先,在书写正则的时候务必要注意这一点。
下面是 DFA、传统 NFA 以及 POSIX NFA 引擎的特点总结:
回溯是 NFA 引擎才有的,并且只有在正则中出现量词或多选分支结构时,才可能会发生回溯。
比如我们使用正则 a+ab 来匹配 文本 aab 的时候,a+ 是贪婪匹配,会占用掉文本中的两个 a,但正则接着又是 a,文本部分只剩下 b,只能通过回溯,让 a+ 吐出一个 a,再次尝试。
举个极端的例子,使用正则 .*ab
去匹配一个比较长的字符串时, .*
会吃掉整个字符串(不考虑换行),但正则中还有 ab 没匹配到内容只能将 .*
已经匹配的字符串吐出一个字符,再尝试,还不行,再吐出一个,不断尝试:
理解了这个过程,我们就能明白,提取引号中的内容时,需要使用 “[^"]+”或者使用非贪婪的方式 “.+?”,来减少“匹配上的内容不断吐出,再次尝试”的过程。
我们再看一下前面讲解的店铺名匹配示例:
可以看到,一个很短的字符串,NFA 引擎尝试步骤达到了 9021 次,由于是贪婪匹配,第一个分支能匹配上 this is a cat 部分,接着后面的逗号匹配失败,使用第二个分支匹配,再次失败,此时贪婪匹配部分结束。NFA 引擎接着用正则后面的 $ 来进行匹配,但此处不是文本结尾,匹配不上,发生回溯,吐出第一个分支匹配上的 t,使用第二个分支匹配 t 再试,还是匹配不上。
可以使用 中的 Regex Debugger 来调试一下这个过程:
(pdf无法直接看到动图效果。动图地址:
http://image109.360doc.com/DownloadImg/2021/11/3010/235047721_27_20211130104846864.gif)
继续回溯的过程中,第二个分支匹配上的 t 吐出,第一个分支匹配上的 a 也吐出,再用第二个分支匹配 a 再试,如此发生了大量的回溯。
现在尝试优化一下,把第一个分支中的 A-Za-z 去掉,因为后面多选分支结构中重复了,我们再看一下正则尝试匹配的次数:
可以看到只尝试匹配了 57 次就结束了。
所以在多选择分支中,避免出现重复的元素非常重要,我们要尽量减少回溯后的判断。
再看看之前说的独占模式,可以把它可以理解为贪婪模式的一种优化,但它也会发生广义的回溯,只是不会吐出已经匹配上的字符。独占模式匹配到英文逗号那儿,不会吐出已经匹配上的字符,匹配就失败了,所以采用独占模式也能解决性能问题:
注意:独占模式“不吐出已匹配字符”的特性,会使得一些场景不能使用它。另外,只有少数编程语言支持独占模式。
解决这个问题还有其它的方式,比如我们可以尝试移除多选分支选择结构,直接用中括号表示多选一:
会发现性能也是有显著提升(这里只是测试,真正使用的时候,重复的元素都应该去掉,另外这里也不需要保存子组)。
|