自动生成正则表达式

◆0 前言

自动生成正则表达式这个话题其实国外有相关的研究，这次的使用的方法是我按一个论文的思路做实现的时候想到的。所谓的自动生成其实没有想象的那么高大上，其实就是使用了一些非常简单的思路进行组合。文中提到的方法已经使用python进行了实现，效果就我本身提供的几个二逼的数据来说是不错的，但是我不好评价真实场景下的效果，还有需要注意的就是我文中提供的代码适合生成一些简单的正则表达式。
正则表达式本身的存在是为了匹配具有某个固定模式的文本，既然目标具有固定的模式，那么自动生成就是存在可能性的，先思考一个思路，我们写一个正则表达式的时候我们在思考什么，我们在思考例子，比如我们想去匹配网址，那么我们就会思考不同的例子，比如www.baidu.com www.python.org au.fuck.com,都代表了不同的例子，我们会从其中抽取他们共有的模式编写可以进行匹配的正则表达式语法。
◆1 思考模式

1. 正则表达式

我们需要先去思考正则表达式本身所具有的模式，我们先做一个简单的假设，假设正则表达式本身具有两种模式，一种用于匹配具体的字符串 比如 “baidu”，“google”，“fuck you”，我们称为 FullPatten，另外一种用于匹配模仿的字符串，比如纯数字等等，称为HalfPatten。
2. 共有模式

所谓的共有，就是都拥有的元素。比如 www.baidu.com www.google.com www.hello.com 。我们可以显而易见的看出，三个例子共同存在的元素很多，比如都存在 "www.", ".com" 或者点号和 w,c,o,m....可以看出这我们思考的这几个例子都有一些共同的模式。
3. 丢一起

现在把我们思考出来的模式组合到一起，就是说我们要做的事只是简单的给计算机输入几个栗子，然后让计算机得出共有的模式去生成我们想要的正则表达式。打个比方，我们现在有几个栗子:
example ＝ [www.baidu.com, www.google.com, www.hello.com]然后计算机得出最长的的共有字符串:
union = ['www.', '.com']我们转化成正则表达式的模式后:
regexPatten = [FullPatten, HalfPatten, FullPatten]然后迭代生成正则表达式:
re = "www.w+.com"好了，本次教程就到这里。
开个玩笑，这种二逼的东西就怎么可能浪费我这几天的美剧时间，只要思考几个相反的例子我们就会很容易的得出上面基于规则生成的破逼玩意有多么坑爹。比如如果我们想匹配 “www.au.baidu.com” 比如 我们想匹配 .com 和 .au 结尾的怎么办，或者我们只是想匹配所有的url？下面我们就需要去解决这个问题。
4. 信息熵

当年香农大神提出了信息熵这个概念用于描述事物的不确定性，什么是不确定性，比如1+1=？对于学过加法的你来说它具有不确定性吗？没有，那么他的信息熵就是0。如果问的是 你明天会不会在公司楼下碰见美女，它具有不确定性么？有，很大。。。。。
◆2 数据的多样性

上面的机制的缺点在于没有考虑到数据的多样化，和外面的世界太危险。我们先思考HalfPatten然后将其写成模块，那么现在我们先思考HalfPatten的价值，就是用于匹配模糊的数据，比如 数字 d ，字母w 任意字符 . ，有一个问题，所谓的模糊数据是所有的，还是有固定长度的。比如上面的模糊字符串 google,hello,baidu 我们是匹配长度为 5到6的还是 直接任意字符 ？
我们需要一种简单暴力的方式可以描述数据的不确定性，就是我刚才说的信息熵。比如我们有一些需要模糊匹配的数字长度为 length= [5,6,5,6]，那么它的信息熵就是 (1/2) · log(1/2) – (1/2) · log(1/2) ≈ 0.693 又或者说我们有 5，5，5，5这有的数字长度，那么他的shan就是0. 接下来我们转化成代码。
#!pythonfrom math import logdef shan(x): shan = 0. for i in set(x): shan -= (float(x.count(i))/len(x))*log(float(x.count(i))/len(x)) return shanprint shan([5,6,5,6])print shan([5,5,5,5])out:
0.693147180560.01. HalfPatten

现在我们可以来写HalfPatten模块了。我们可以从下面的代码看出 halfPatten其实也存在 all zone length这三种模式，比如我们检测长度的信息熵为0那么我们只需要单纯的返回 d{长度} 同时我们加入了一个 熵参数shan，只要长度的信息熵超过这个值就说明数据不确定性太大，匹配任意长度就行，低于这个值 我们就只需要匹配某个区间的长度就行。
#!pythonclass HalfPatten: def __init__(self,x): self.x = x self.type = "halfPatten" self.shan = 0. self.regShan= 0. self.x_length = [len(i) for i in x] for i in set(self.x_length): self.shan -= (float(self.x_length.count(i))/len(self.x_length))*log(float(self.x_length.count(i))/len(self.x_length)) for c in set(self.x): self.regShan -= (float(self.x.count(c))/len(self.x))*log(float(self.x.count(c))/len(self.x)) def detection(self,string): s = ''.join(string) if len(s)==0: return "" if s.isalnum(): if s.isdigit(): return "d" return "w" else: return "." def gener(self,patten): if patten=="all": return "%s+"%(self.detection(self.x)) elif patten=="zone": x_len = self.x_length x_len.sort() return "%s{%i,%i}"%(self.detection(self.x),x_len[0],x_len[-1]) else: return "%s{%i}"%(self.detection(self.x),self.x_length[0]) def regex(self,shanRule): if self.detection(self.x)=="": return "" if self.shan>0: if self.shan>shanRule: return self.gener("all") else: return self.gener("zone") else: return self.gener("length")def main(shan=1.): exmple = ['123','123'] exmple2 = ['123','1234'] half = HalfPatten(exmple) half2 = HalfPatten(exmple2) print half.regex(shan) print half2.regex(shan)if __name__ =="__main__": main() main(0.)out:
d{3}d{3,4}d{3}d+我们可以看到我们得出了一个非常不错的结果，那么接下来我们需要来写FullPatten模块。
2. FullPatten

fullPatten其实相对于half来说要简单了许多，我们只需要根据确定性的字符串生成对应的正则表达式就好了。需要注意的是所谓的确定性其实也有不同的模式， 比如 我们想匹配 .com 和 .cn结尾的url而不想要其他的东西。现在写成代码：
#!pythonclass FullPatten: def __init__(self,x): self.x = x self.type = "fullPatten" self.shan = 0. self.regShan = 0. def gener(self,patten): if patten=="all": return "(%s)"%(self.x[0]) else: return "(%s)"%('|'.join(list(set(self.x)))) def regex(self,shanRule): if len(set(self.x))>1: return self.gener("half") else: return self.gener("all")def main(): example = ['.fuck','.fuck'] example1 = ['.com','.cn'] full = FullPatten(example) full1 = FullPatten(example1) print full.regex(example) print full1.regex(example1)if __name__ == "__main__": main()out:
(.fuck)(.com|.cn)接下来我们来把这两个模块组合到一起。
3. 组合

在把这几个玩意丢一起之前我们需要先思考我们要的是什么，我们需要一个模块，能够根据我们提供的确定性的字符串对数据分割成序列的形式。写成代码：
#!pythonclass strspl: def __init__(self,y,shan): self.sentence = [] self.y = y self.shan = shan def re_split(self,string): s = [] for x in self.y: s.append([x[:x.index(string)],string,x[x.index(string)+len(string):]]) half_1 = [] full_1 = [] half_2 = [] for q,w,e in s: half_1.append(q) full_1.append(w) half_2.append(e) self.sentence.append(HalfPatten(half_1)) self.sentence.append(FullPatten(full_1)) self.sentence.append(HalfPatten(half_2)) for l,i in enumerate(self.sentence): if i.shan!=0.: if i.regShan