Python下的正则表达式原理和优化笔记

基础规则的介绍

python中的转义符号干扰

        python中，命令行和脚本等，里面都会对转义符号做处理，此时的字符串会和正则表达式的引擎产生冲突。即在python中字符串’n’会被认为是换行符号，这样的话传入到re模块中时便不再是‘n’这字面上的两个符号，而是一个换行符。所以，我们在传入到正则引擎时，必须让引擎单纯的认为是一个”和一个’n’，所以需要分别加上转义符，成为’\n’，针对这个情况，python中使用raw_input方式，在字符串前加上r，使字符串中的转义符不再特殊处理（即python中不处理，统统丢给正则引擎来处理），那么换行符就是r’n’

基本字符

.        #普通模式下，匹配除换行符外的任意字符。（指定DOTALL标记以匹配所有字符）

量词限定符

*        #匹配前面的对象0个或多个。千万不要忽略这里的0的情况。
+        #匹配前面的对象1个或多个。这里面的重点是至少有一个。
?        #匹配前面的对象0个或1个。
{m}      #匹配前面的对象m次
{m,n}    #匹配前面的对象最少m次，最多n次。

锚点符

^        #匹配字符串开头位置，MULTILINE标记下，可以匹配任何n之后的位置
$        #匹配字符串结束位置，MULTILINE标记下，可以匹配任何n之前的位置

正则引擎内部的转义符号

m    m是数字，所谓的反向引用，即引用前面捕获型括号内的匹配的对象。数字是对应的括号顺序。
A    只匹配字符串开头
b    可以理解一个锚点的符号，此符号匹配的是单词的边界（"单词边界符"）。这其中的word定义为连续的字母，数字和下划线。
      准确的来说，b的位置是在w和W的交界处，当然还有字符串开始结束和w之间。
B    和b对应，本身匹配空字符，但是其位置是在非"边界"情况下，比如r'pyB'可以匹配python，但不能匹配'py,','py.' 等等
d    匹配数字
D    匹配非数字
s    未指定UNICODE和LOCALE标记时，等同于[ tnrfv]，注意t之前是一个空格，表示也匹配空格。
S    与s相反
w    未指定UNICODE和LOCALE标记时，等同于[a-zA-Z0-9_]
W    和w相反
Z    只匹配字符串的结尾

<b style="font-weight: bold;">其他的一些python支持的转移符号也都有支持，如前面的't'</b>

括号的相关内容

普通型括号

(...)    普通捕获型括号，可以被number引用。

扩展型括号

(?aiLmsx)
a        re.A
i        re.I    #忽略大小写
L        re.L
m        re.M
s        re.S    #点号匹配包括换行符
x        re.X    #可以多行写表达式

(?:......)      #非捕获型括号，此括号不记录捕获内容，可节省空间
(?P<name>...)   #此捕获型括号可以使用name来调用，而不必依赖数字。调用时使用(?P=name)
(?#...)         #注释型括号，此括号完全被忽略
(?=...)         #lookahead assertion 如果后面是括号中的，则匹配成功
(?!...)         #negative lookahead assertion    如果后面不是括号中的，则匹配成功
(?<=...)        #positive lookbehind assertion    如果前面是括号中的，则匹配成功
(?<!...)        #negative lookbehind assertion    如果前面不是括号中的，则匹配成功
                #以上<span><b>四种类型断言</b></span>，本身均不匹配内容，只是告知正则引擎是否开始匹配或者停止。
                #另外在后两种后项断言中，必须为<b>定长断言</b>。
(?(id/name)yes-pattern|no-pattern)
                #如有由id或者name指定的组存在的话，将会匹配yes-pattern，否则将会匹配no-pattern，通常情况下no-pattern也可以省略。

<b style="font-weight: bold;">匹配优先/忽略优先符号</b>

1，在是进行尝试还是跳过尝试时，匹配优先量词和忽略优先量词会作出相应决定。
2，匹配失败时，回溯需要返回到上一个备用状态，原则是后进先出（LIFO）

回溯典型举例：

1，在相对的应用中，在结果保证正确的情况下，应该优先的去匹配更可能出现的结果。即将可能性大的分支尽可能放在靠前。
2，多选结构的代价。不能滥用多选结构，因为当匹配到多选结构时，缓存会记录下相应数目的备用状态。举例子如：[abcdef]和‘a|b|c|d|e|f’这两个表达式很可能经过稍稍修改都能完成你的某个任务，
但是尽量选择字符型数组，显然后者会在每次比较时建立6个备用状态，会占用一定的内存。

1. 只匹配期望的文本，排除不期望的文本。(善于使用非捕获型括号)
2. 必须易于控制和理解
3. 使用NFA引擎，必须保证效率（如果能够匹配，必须很快地返回匹配结果，如果不能匹配，应该在尽可能短的时间内报告匹配失败。）

（w+)*

import re
re_lx = re.compile(r'(?=(w+))1*d')

效率测试代码

在测试表达式的效率时，可借助以下代码比较所需时间。

import re
import time
re_lx1 = re.compile(r'your_re_1')
re_lx2 = re.compile(r'your_re_2')

starttime = time.time()
repeat_time = 100
for i in range(repeat_time):
    s='test text'*10000
    result = re_lx1.search(s)
time1 = time.time()-starttime
print(time1)

starttime = time.time()
for i in range(repeat_time):
    s='test text'*10000
    result = re_lx2.search(s)
time2 = time.time()-starttime
print(time2)

re_lx1 = re.compile(r'd{5}$')
re_lx2 = re.compile(r'd{5}')

排除型数组的利用

继续上面的例子，我们发现w是包含d的，当使用匹配优先时，前面的w会掠过数字，之所以能匹配成功，或者确定失败，是后面的d迫使前面的量词交还一些字符。
知道这一点，我们应该尽量避免回溯，一个顺其自然的想法就是不让前面的匹配优先量词涉及到d

re_lx1 = re.compile(r'^w+(d{5})')
re_lx2 = re.compile(r'^[^d]+d{5}')    #优于上面的表达式

避免重新编译（循环外创建对象）
使用非捕获型括号（节省捕获时间和回溯时状态的数量）
善用锚点符号
不滥用字符组
提取文本和锚点。将他们从可能的多选分支结构中提取出来，会提取速度。
最可能的匹配表达式放在多选分支前面

1. special部分和normal部分匹配的开头不能重合。一定保证这两部分在任何情况下不能匹配相同的内容，不然在无法出现匹配时遍历所有情况，此时引擎的路径就不能确定。
2. normal部分必须匹配至少一个字符
3. special部分必须是固定长度的

转载自：http://my.oschina.net/o0Kira0o/blog/138516