自动生成正则表达式

前言

前几天需要做一个匹配目标网址的正则表达式,需求是返回一个array到变量里。这个当然不难咯,我直接写上就保存了。

结果一同学写论文要这玩意儿,说他论文题目是“正则表达式的自动生成”。然后我就开始研究了(因为我本人也比较需要嘛)。

好吧我承认我作死,其实这才是我的实际生活状态。

自动生成正则表达式这个话题其实国外有相关的研究,这次的使用的方法是我按上面那位仁兄的论文思路做实现的时候想到的。

所谓的自动生成其实没有想象的那么高大上,其实就是使用了一些非常简单的思路进行组合。文中提到的方法已经使用 python 进行了实现,效果就我本身提供的几个二逼的数据来说是不错的,但是,我不好评价真实场景下的效果,还有需要注意的就是我文中提供的代码适合生成一些简单的正则表达式。

正则表达式本身的存在是为了匹配具有某个固定模式的文本,既然目标具有固定的模式,那么自动生成就是存在可能性的。

先思考一个思路,我们写一个正则表达式的时候我们在思考什么,我们在思考例子。

比如我们想去匹配网址,那么我们就会思考不同的例子,比如www.baidu.com www.python.org au.fuck.com,都代表了不同的例子,我们会从其中抽取他们共有的模式编写可以进行匹配的正则表达式语法。

Thinking Partten

正则表达式

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

共有模式

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

混合

现在把我们思考出来的模式组合到一起,就是说我们要做的事只是简单的给计算机输入几个栗子,然后让计算机得出共有的模式去生成我们想要的正则表达式。打个比方,我们现在有几个栗子:

example [www.baidu.com, www.google.com, www.hello.com]

然后计算得出最长的的共有字符串:

union = ['www.', '.com']

我们转化成正则表达式的模式后:

regexPatten = [FullPatten, HalfPatten, FullPatten]

然后迭代生成正则表达式:

regex = "www.\w+.com"

好了,本次教程就到这里。

开个玩笑,这种二逼的东西就怎么可能浪费我这几天的美剧时间,只要思考几个相反的例子我们就会很容易的得出上面基于规则生成的破逼玩意有多么坑爹。

比如如果我们想匹配 “www.au.baidu.com” 比如我们想匹配 .com 和 .au 结尾的怎么办,或者我们只是想匹配所有的url?下面我们就需要去解决这个问题。

信息熵

当年香农大神提出了信息熵这个概念用于描述事物的不确定性,什么是不确定性,比如1+1=?

对于学过加法的你来说它具有不确定性吗?没有,那么他的信息熵就是0。

如果问的是:你明天会不会在公司楼下碰见美女,它具有不确定性么?有,而且还很大......

数据的多样性

上面的机制的缺点在于没有考虑到数据的多样化,和外面的世界太危险。我们先思考 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又或者说我们有 5555这有的数字长度,那么他的熵就是0. 接下来我们转化成代码。

输出

0.69314718056
0.0

HalfPatten

现在我们可以来写HalfPatten模块了。

我们可以从下面的代码看出 halfPatten 其实也存在 all zone length 这三种模式,比如我们检测长度的信息熵为0,那么我们只需要单纯的返回 \d{长度} 同时我们加入了一个熵参shan,只要长度的信息熵超过这个值就说明数据不确定性太大,匹配任意长度就行,低于这个值,我们就只需要匹配某个区间的长度就行。

输出

\d{3}
\d{3,4}
\d{3}
\d+

我们可以看到我们得出了一个非常不错的结果,那么接下来我们需要来写 FullPatten 模块。

FullPatten

fullPatten其实相对于half来说要简单了许多,我们只需要根据确定性的字符串生成对应的正则表达式就好了。

需要注意的是所谓的确定性其实也有不同的模式, 比如 我们想匹配 .com 和 .cn结尾的url而不想要其他的东西。现在写成代码:

输出

(.fuck)
(.com|.cn)

接下来我们来把这两个模块组合到一起。

组合

在把这几个玩意丢一起之前我们需要先思考我们要的是什么,我们需要一个模块,能够根据我们提供的确定性的字符串对数据分割成序列的形式。写成代码:

输出

 ['fullPatten', 'fullPatten', 'fullPatten'] (ww|asb|www)(.baidu.)(go|com|fuck)
['halfPatten', 'fullPatten', 'halfPatten'] \w+(.baidu.)\w+

我们可以看到我们在模块中又提供了一个参数,这个参数在于决定,.com 和 .cn 是 full 还是 half

我们可以看到我们对保存着类型序列的 sentence 进行了一次迭代,抽取其中的 regShan 进行判断,regShan 与刚才的长度不同,由数据本身的的差异得出,由于 full 的 regShan 写死了 0. 所以其实是判断half的。目的在于选定一个值来判断 这个类型是否需要改为full类型。

总结一下

现在我们需要把他组成一个成品了,现在我们已经有了各种模块,我们就还需要一个能够自动提取共有模式并且转换的模块。

我们可以从上面的代码看到,算法切割数据的方式是找到第一个匹配的字符串然后进行切割。

那么,比如这样的数据 www.baidu.com www.python.com.ho www.sb.com.as 我们经过切割后会变成 [www., baidu.com] [www., python.com] [www, .sb.com.as] 会被转化成类似 www..{7,8} 类似的玩意,但是我们知道剩下的字符串还存在可以被提取的共有模式就是.com,所以我们设置一个迭代值iter,让机器能够多次提取共有模式,为了让我们能够更好的调整算法的参数,在有多个 halfPatten 的情况下,每次机器只会对其中一个halfPatten进行提取,每次迭代算法会选取其中 regShan最大的进行再提取。

就是说,不确定性更大的数据其中存在共有模式的可能性越高,but 一但其中提取不到共有模式就会自动退出循环。写成代码:

输出

[1.0986122886681096, 0.0, 0.6365141682948128] .{6,7}(.bai).{6}
[1.0986122886681096, 0.0, 0.6365141682948128] .+(.bai).{6}
[0.0, 0.0, 0.6365141682948128] (www.ww|www.www|www.asb)(.bai).{6}
counting 1
[0.0, 0.0, 0.6365141682948128, 0.0, 0.0] (www.ww|www.www|www.asb)(.bai)\w{2}(.com)
counting 1
[0.0, 0.0, 1.0986122886681096, 0.0, 0.6365141682948128] (www.)\w{2,3}(.bai).{6}

我们可以看到,三个参数的不同可以导致生成不同类型的正则表达式。其实到这里差不多就结束了,这里的代码其实在于提供一种思路,里面的逻辑非常简单,关键在于我们可以通过类似信息熵这种可以量化不确定性的方式来生成正则表达式,整个算法思路其实还有很多需要改进的地方。不过还是有另外一点需要讲。

数据最佳化

我们可以看到上面的代码必要时候需要我们自己调整参数,再数据较为简单的情况下,不同参数的生成的正则其实是可以被枚举完的,我们就需要一种可以度量性能的公式。

\begin{equation} f\left( R\right) =\sum _{i=1}^{n}d\left( s_{i},R\left( ti\right) \right)\end{equation}

函数 R 表示正则表达式匹配,t 表示要匹配的文本 R(t) 表示,正则表达式匹配后的值,s 表示要匹配的值,函数 d 表示编辑距离。这样我们就可以度量他的性能,枚举枚举所有的可能性并选取最小值。

唠叨两句

如果有幸你打算把这个方法用在项目中请重写代码,我文中的代码是为了快速实现而写的,其中有很多需要优化的地方,支持的正则符号也不多,主要还是思路本身的可行性。

 

声明: 本文采用 BY-NC-SA 协议进行授权 | Deamwork
转载请注明转自《自动生成正则表达式
本文地址:https://www.deamwork.com/archives/automatically-generate-a-regex.orz6

回复 (8)

  1. Jimmy Zhou China Google Chrome Windows   / 回复

    看不懂的都是好东西 :D

  2. meng Macau Google Chrome Windows   / 回复

    是怎樣 才能 一步一步 學好這些技術的?

  3. meng Macau Google Chrome Windows   / 回复

    怎樣才可以像你一樣 學會這些技術的?

    • Jason Cooper China Mozilla Firefox Windows   / 回复

      @meng
      只要慢慢折腾就可以了吧….还有就是多看看相关的书啥的…..
      你说的无法评论是老毛病了

  4. 太古神王 China Google Chrome Windows   / 回复

    [给力]

发表评论 修改评论取消编辑

允许使用的标签 - 您可以在评论中使用如下的 HTML 标签以及属性。

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <img src="" alt=""> <pre class="" title="" data-url=""> <span class="" title="" data-url="">

 :mrgreen:  :|  :twisted:  :arrow:  8O  :)  :?  8-)  :evil:  :D  :idea:  :oops:  :P  :roll:  ;)  :cry:  :o  :lol:  :x  :(  :!:  :?:

引用通告 (0)

› 尚无引用通告。

欢迎来到Deamwork! o(∩_∩)o
X