众里寻她千百度--正则表达式
|
原文地址 先来看一个让人震撼的小故事，故事来自知乎问题PC用户的哪些行为让你当时就震惊了？
不知道是否确有此事，不过看起来好吓人的样子。仔细想想，大多数人都是用以往的经验来分析遇见的新问题的。就上面的大妈而言，在接触计算机之前的几十年里，她面对的都是纸质的客户资料，此时，要查找某一客户资料，只能一行一行看下去了。 现在，虽然有了计算机，但是只是简单的把它看做一个比较大的纸质资料库罢了，并没有认识到计算机的强大之处。这里的强大主要就是说计算机在处理电子文档时的强大的搜索功能了。 当然，对于大部分年轻人来说，计算机中的搜索功能是再熟悉不过了。我们可以在word、excel、网页中搜索特定内容，可以在整个计算机文件系统中搜索文件名，甚至搜索文件中的内容（Win下的everthing，Mac下的Spotlight）。 这些搜索主要用到了两种技术：
这里我们先介绍一下正则表达式。 正则表达式介绍简单来说，正则表达式就是用来 正则表达的理念是由数学家Stephen Kleene在1950年首次提出来的，开始时主要用于UNIX下文本编辑器ed和过滤器grep中。1968年开始广泛应用于文本编辑器中的模式匹配和编译器中的词法分析。1980年，一些复杂的正则表达语句开始出现在Perl中，使用了由Henry Spencer实现的正则表达解析器。而Henry Spencer后来写了更高效的正则解析器Tcl，Tcl混合使用了NFA（非确定有限自动机）/DFA（确定有限自动机）来实现正则表达语法。 正则表达式有以下优点：
正则表达式的语法十分简单，虽然各种编程语言在正则表达式的语法上有细节上的区别，不过主要部分如下：
回到我们前面的例子中，我们用正则表达式[ab]*abb来匹配由a、b组成的，以abb结尾的字符串。这里[ab]*abb即可以这样解读： 下面用python在"aababbaxz abcabb abbbbabb"中搜索 import re
content = "aababbaxz abcabb abbbbabb"
pattern = re.compile("[a|b]*abb")
print pattern.findall(content)
# outputs: ['aababb','abb','abbbbabb']
其实，正则表达式不只用于文本搜索和模糊匹配，还可以用于以下场景：
正则表达式实现原理正则表达式便于我们理解使用，但是如何让计算机识别用正则表达式描述的语言呢？仍然以前面的
图中一共有4个状态S0,S1,S2,S3，在每个状态基础上输入字符a或者b就会进入下一个状态。如果经过一系列输入，最终如果能达到状态S3，则输入内容一定满足正则表达式[a|b]*abb。 为了更清晰表述问题，将上图转换为状态转换表，第一列为当前状态，第二列为输入a后当前状态的跳转，第三列为输入b后当前状态的跳转。其中S0为
其实上图就是一个DFA实例（确定有限自动机），下面给出DFA较为严格的定义。一个确定的有穷自动机(DFA) M 是一个五元组：M = (K,∑,f,S,Z)，其中：
DFA的确定性表现在转换函数f:K×∑→K是一个单值函数，也就是说对任何状态ki∈K和输入符号a∈∑，f(k,a)唯一地确定了下一个状态，因此DFA很容易用程序来模拟。 下面用字典实现[a|b]*abb的确定有限自动机，然后判断输入字符串是否满足正则表达式。 DFA_func = {0: {"a": 1,"b": 0},1: {"a": 1,"b": 2},2: {"a": 1,"b": 3},3: {"a": 1,"b": 0}
}
input_symbol = ["a","b"]
current_state = 0
accept_state = 3
strings = ["ababaaabb","ababcaabb","abbab"]
for string in strings:
for char in string:
if char not in input_symbol:
break
else:
current_state = DFA_func[current_state][char]
if current_state == 3:
print string,"---> Match!"
else:
print string,"--->No match!"
current_state = 0
"""outputs:
ababaaabb ---> Match!
ababcaabb --->No match!
abbab --->No match!
"""
上面的例子可以看出DFA识别语言简单直接，便于用程序实现，但是DFA较难从正则表达式直接转换。如果我们能找到一种表达方式，用以连接正则表达式和DFA，那么就可以让计算机识别正则表达式了。事实上，确实有这么一种表达方式，可以作为正则表达式和DFA的桥梁，而且很类似DFA，那就是非确定有限自动机(NFA)。 还是上面的例子，如果用NFA表示流程图，就如下图所示：
看上去很直观，很有
NFA的定义与DFA区别不大，M = (K,Z)，其中：
数学上已经证明：
这里不做过多陈述，想了解详情可以参考《编译原理》一书。至此，计算机识别正则表达式的过程可以简化为： 正则表达式应用实例前面已经使用python的re模块，简单展示了正则表达式[ab]*abb的匹配过程。下面将结合几个常用的正则表达式例子，展示正则表达式的强大之处。 开始之前，先来看下python中正则表达的一些规定。
python中常用到的正则表达式函数主要有
re.search和re.match均可指定开始搜索和结束搜索的位置，即re.search(string[,pos[,endpos]])和re.match(string[,endpos]])，此时从pos搜索到endpos。需要注意的是，match总是从起始位置匹配，而search则从起始位置扫描直到遇到匹配。
match = re.search(pattern,string)
if match:
process(match)
re.MatchObject对象主要有以下方法：group([group1,...])和groups([default])。group返回一个或多个分组，groups返回包含所有分组的元组。 例子1：匹配Hello，当且仅当后面没有紧跟着World。 strings = ["HelloWorld!","Hello World!"]
import re
pattern = re.compile(r"Hello(?!World).*")
for string in strings:
result = pattern.search(string)
if result:
print string,"> ",result.group()
else:
print string,"Not match"
'''
outputs:
HelloWorld! > Not match
Hello World! > Hello World!
'''
例子2：匹配邮箱地址。目前没有可以完美表达邮箱地址的正则表达式，可以看stackflow上问题Using a regular expression to validate an email address 。这里我们用 content = """
alice@google.com
alice-bob@gmail.._com gmail
alice.bob@apple.com apple
alice.bob@gmailcom invalid gmail
"""
import re
address = re.compile(r'[w.-]+@[w-]+.[w.-]+')
print address.findall(content)
'''
outpus:
['alice@google.com','alice-bob@gmail.._com','alice.bob@apple.com']
'''
例子3：给函数添加装饰器。 original = """
def runaway():
print "running away..."
"""
import re
pattern = re.compile(r"def (w+():)")
wrapped = pattern.sub(r"@get_carndef 1",original)
print original,"--->",wrapped,"----"
"""outputs
def runaway():
print "running away..."
--->
@get_car
def runaway():
print "running away..."
----
"""
看起来正则表达式似乎无所不能，但是并不是所有的场合都适合用正则表达式，许多情况下我们可以找到替代的工具。比如我们想解析一个html网页，这时候应该使用使用 HTML 解析器，stackflow上有一个答案告诉你此时为什么不要使用正则表达式。python有很多html解析器，比如：
参考 （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
||||||||||||||||||||||||||||||||