关于从普通文本提取正则表达式的再思考
Mar 9th
rex按：写完上一篇文章之后，一直在考虑如何真正实现从普通文本中归纳正则表达式的实现。走了许多弯路，也学了不少知识。例如，perl黑豹书上复杂的数据结构、匿名散列和数组、refenrence；紫龙书上的状态机的构造，数据结构上图论的知识，都是很有用的。另外还新学了graphviz的用法。以前觉得很神秘，不过一用才发现很直观。本文的插图是使用online版本的graphviz画的。
除了本文的这种实现方法（基于图），我还使用另一种方式实现了，很简单：基于关键词。具体作法是，逐一读取每一行文本，使用\s+等将其split开，形成array；然后再对所有的array进行求交集的操作（使用hash），得到每一行都有的关键词；然后按从左到右的顺序建立这覆的正则式^(.*?)keyword1(.*?)keyword2….keywordN(.*?)$，再分别匹配每一行文本，得到hash的hash表，或者array的array，转置，并列输出，得到^(option1|option2…)keyword1(option..)…$这样的正则式。最后作为验证，再将所最终生成的正则与每一行匹配测试一下。
这样以词为单位做完之后，再逐个字母地分隔开来，递归地处理(option1|option2…)的部分。先是单词级，再是字母级，有利于先在最大程度上找出重复的内容；而且粗化和细化的处理过程，思路是一致的，粒度不同罢了。
新手请自重，高手请赐教，我的思路未必是正确或最优的。
问题
this is a red foxthis is a blue firefoxthis is a piga red fox
标准正则
有两种极端的解法是不可取的：
- ^.*$
- ^(this is a red fox|this is a blue firefox|this is a pig|a red fox)$
第一种失之于太宽泛，第二种失之于太狭隘。太宽泛则泥沙俱下，无论什么文本都能匹配；太狭隘则僵化死板，缺乏灵活性。好的正则表达式源于例文本（从例文本中提取规律），又高于例文本（能匹配同规律的其它文本）。匹配什么，排除什么，都有定则，所谓“君子有所为而有所不为”，指的就是这种情况（貌似跑题了:)）。
思路
既然是一条正则匹配所有的文本，那么这条正则（记为$re）也应该匹配第一行文本。
第一行文本为this is a red fox。那么，从^this is a red fox$应该是$re的一个（真）子集。它的路径为：“^”->this->is->a->red->fox->”$”。全部节点之间，是串联关系，从左到右依次排列即可。
示意图如下(可以点击看全尺寸图，下同)：
同理，第二行文本也应该是$re的子集。不过，由于已经存在了由^->this->is->a的路径，到a时出现支路，a->blue->firefox->$；
将此路径添加到示意图上，得到：
显而易见，这两条并列的支路，始于a，终于$，可以使用|来并列之。
好了，我们总结一下规律：
再往下，this is a pig，同理，只需要在原图基础上添加a->pig->$的支路即可。此时图示如下：
此时，观察可知，一种新的情况出现了。同时存在^->a，和“^”->this->is->a两条路径。想一下初中物理电路图，我们可以将这种情况称为“短路”，即，“^”->this->is->a这个线路的^、a两个节点之间，添加了一条无障碍通道，它能无视this、is的存在，因此，让this->is这条路径成为可选项。再总结一下规律：
如果有A->B->…C->D的路径，且有A->D的路径，则称A->D之间存在短路，此时,B->…->C可以用(B->…->C)?来表示(就是用括号来表示被短路的部分，问号表示短路之)。
这也就是为什么上文要强调是一个节点的缘故。
实现
…
上图其实是一个有向图，只需记录所有的顶点集合，路径集合，再来求各路径之间的关系；最后打印输出，即是所求。
这两个集合在读取文本文件行的时候可以一次性建立。不复杂。关键是关系的确立。
- 从一个顶点A出发的N条支路必定汇合（只是有时是同一个点，有时不在同一点而已。本文给出的例子是最简单的情况，这里可以假设为汇合到同一点）于M点。
- 这N条路中，每一条路径的长短以经过的节点个数来计算。例如上图中，^到a有一条路，上面的路径为2，下面的路径为0。
- 短的支路决定了这N条支路的关系。
- 长度为任意两点之间，最多只可能有一条长度为0的边。
- 如果存在长度为0的边，则其余的同级的支路被短路。
- 长度不为0的N-1条支路之间是并列关系。
- 整个图始于^，终于$。
个人应用之明文字串到正则
Feb 10th
近来工作中需要将某种明文字串转为简单的正则式。手动做当然可以，但是大量重复性的劳动，自然是交给机器处理为好。昨晚写了一款这样的脚本，放在这里。因为是处理我自己的工作的脚本，贴在这里仅作记录和存档之用，可能对别人没什么实际作用。当然，从现有的明文字串到正则式的转换，应该是个不错的题目，有兴趣朋友的可以深究。
值得一提的是，代码中用了$&, (?{}) 这样的perl only的东东，明晰了思路，简化了代码。如果不使用这种特性的话，代码要长5倍。另外，据说从效率上来说，use English之后，使用$MATCH比直接使用$&快5倍。但是对于即输入即执行的命令行程序来说，$&已经足够好。
实际应用一例：
perl hash2re.pl H:aaa-Aaaa-AaaaAaaaaaaAaaaaaaa-AAA0.zip/H:aaa-Aaaa-AaaaAaaaaaaAaaaaaaa-AAA-0/aaa-Aaaa-AaaaAaaaaaaAaaaaaaa-AAA-0/aaa/Aaaaa/aaa-Aaaa-AaaaAaaaaaaAaaaaaaa-AAA-0.exe
RE 1: ^[a-z]{3}-[A-Z][a-z]{3}-[A-Z][a-z]{3}[A-Z][a-z]{6}[A-Z][a-z]{7}-[A-Z]{3}[0-9]\.zip$
Matches: "aaa-Aaaa-AaaaAaaaaaaAaaaaaaa-AAA0.zip"
RE 2: ^[a-z]{3}-[A-Z][a-z]{3}-[A-Z][a-z]{3}[A-Z][a-z]{6}[A-Z][a-z]{7}-[A-Z]{3}-[0-9]$
Matches: "aaa-Aaaa-AaaaAaaaaaaAaaaaaaa-AAA-0"
RE 3: ^[a-z]{3}-[A-Z][a-z]{3}-[A-Z][a-z]{3}[A-Z][a-z]{6}[A-Z][a-z]{7}-[A-Z]{3}-[0-9]$
Matches: "aaa-Aaaa-AaaaAaaaaaaAaaaaaaa-AAA-0"
RE 4: ^[a-z]{3}$
Matches: "aaa"
RE 5: ^[A-Z][a-z]{4}$
Matches: "Aaaaa"
RE 6: ^[a-z]{3}-[A-Z][a-z]{3}-[A-Z][a-z]{3}[A-Z][a-z]{6}[A-Z][a-z]{7}-[A-Z]{3}-[0-9]\.exe$
Matches: "aaa-Aaaa-AaaaAaaaaaaAaaaaaaa-AAA-0.exe"源码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | #!/usr/bin/perl # by rex zhang # Feb 09 2010 in Shanghai # usage: split and regexize hashed filename # my $lines=$ARGV[0]; while($lines =~ m#(C:[^/]+)#) { $c=$1; $lines =~ s/$c//; print "ClearText Filename Ignored:\t\"$c\"\n\n"; } my @array=split(m!\s*(?:\/|H:)+\s*!, $lines); my $counter=0; foreach $line (@array){ next if not $line; my $re=$line; local $len; $re =~ s/(?=[.\[\]()])/\\/g; $re =~ s/\?/./g; $re =~ s/0+(?{ $len=length($&)})/[0-9]\{$len\}/g; $re =~ s/A+(?{ $len=length($&)})/[A-Z]\{$len\}/g; $re =~ s/a+(?{ $len=length($&)})/[a-z]\{$len\}/g; $re =~ s/(.)\1+(?{ $len=length($&)})/$1\{$len\}/g; $re =~ s/\{1\}//g; $re = "\^$re\$"; $counter++; if ($line =~ /$re/) { print "RE $counter:\t$re\n"; print "\tMatches: \"$line\"\n"; } else { print "RE $counter:\t$re\n"; print "\tFailed: \"$line\"\n"; } print "\n"; } |
统计重复文本行的两种方法
Feb 6th
假设样本文件a.txt内容如下：
hello world! hello world! I love regex. hello world! I love regex. hello world!
简单观察可知，hello world!共重复4行；I love regex.重复2行。如何使用正则表达式来写一个程序，统计这些数据呢？因为现实中需要统计的文件，绝非是只凭肉眼就能观察出来。我想到了两种方法，第一种方法，是依赖于正则表达式（否则这篇文章也不会贴在这里）；第二种，hash表做主角，正则表达式作绿叶。
正则表达式的解法
思路是：对于任何一行文本，如果后面若干行[0～EOF）之后，如果存在相同的文本行，则记下该行内容，统计出现次数；然后删除这样的文本行，再进行下一行的统计。输出统计结果。
下面是相应的perl程序，附注释。
#!/usr/bin/perl #usage: ./dup_re.pl <a.txt undef $/; # enable "slurp" mode my $file = <STDIN>; # whole file now here while($file =~ m / #for each line; ^\s* #ignore the whitespaces at both ends; (\S.*?) #get the line content, save to $1; \s*$ #ignore empty lines by using \S .*? #check if there is the same pattern of $1 ^\s*\1\s*$ #after 0 or more lines; /smx) { my $line=$1; my $count= $file =~ s/$line//g; #delete the duplicated lines #save the number to $count; #ignore empty lines print $count,"times:\t",$line,"\n"; }
Hash表解法
这种方法，受益于perl语言本身的强大的hash表功能。思路如下：
- 建立空的hash表；
- 逐行读取文件；
- 以文本内容为key，插入到表中来。如果是首次出现，value为0，否则value++。
- 输出hash表中value>=2的记录。
Perl程序：
#!/usr/bin/perl #usage: ./dup_hash.pl a.txt my %hash=(); while(<>) { if (/^\s*(\S.*?)\s*$/) #ignore whitespaces at both ends; { #ignore empty lines by using \S $hash{$1}++; #save the line to $1, and count the time it appears } } #sort the hash by values; foreach $key (sort { $hash{$b} <=> $hash{$a} } keys %hash) { if ($hash{$key}>=2) #only print the lines that duplicates; { #for all results, just remove the 'if' line printf "%d times:\t%s\n", $hash{$key}, $key; } }
结果
上面的程序分别保存为dup_re.pl，dup_hash.pl。由于程序对于外部文件的读取的方法不同，运行方式也有差别，详见下图：
Update
忽然想到，如果要让这脚本更有效，可以指定忽略大小写，忽略单词间多个空格的情况，使得Hello world!与 hello WORLd! 被视为重复行。测试了一下，正则式没让我失望。
由正则式反推文本:REExtractor
Feb 2nd
发现一款简单有趣的正则表达式应用：REExtractor，作用是输入正则表达式，输出符合正则式描述的文本。作者给的介绍是
Generate all possibilities of Regular Expression，即生成正则表达式的所有可能性。不过，理论上可以做到，执行时却有限制。
一些限制
- 平台是GAE，语言是python，因此用的是python正则。或需代理才能访问使用。
- 支持的元字符或缩写：(), [],{m,n},{n},|,\w,\d。如果需要用到这些字符的字面值，请使用反斜线转义之。其中这里的\w等同于[a-zA-Z0-9]，为62个字符之一，而不是通常意义上的包括下划线在内的[_a-zA_Z0-9]，63字符之一。但是可以用[_\w]来代替，没问题的。
- 不支持的元字符：.(点号),^,$,\b,\D,\W,\1…（后向引用）, (?=…), (?!…), (?<=…), (?<!…)等。
- 如果出现.点号，则直接输出。
- 如果使用^, $, \b, \1, (?=…), (?!…), (?<=…), (?<!…)， 程序无视之。
- 如果使用\D或\b或[^]，则程序会报错。原因是范围太宽。
- 不支持可能性在1000条以上结果的正则表达式。例如，\w{2}，因为它的可能性是62×62。但是你可以使用\w\d，因为它的可能性是62×10。
它能做什么
好吧，虽然限制多多，但是你仍然可以拿它来做一些有趣的应用。下面略举两例。
- 生成一些简单的邮箱地址。试一下这条正则式：[abc]{3}\d@1(26|63).com ，它生成540条邮箱地址。
- 生成一些人名。试一下这条正则式：张[小大勇赞强战海][虎猫龙彪平]。它生成35条人名。是的，它支持中文，并且每个中文字都可以当成一个字符来应用。如果你家要添一个宝宝，可以将一些可能的字排列一下，看看哪些组合比较赏心、顺口，再从中选择一个。
平心而论，上面的这些小应用，当然可以直接编程实现，限制更少，更灵活，更强大。但是有必要每次都开编译器么？尝试一下这款小程序，也挺有趣的。而且，上一节中提及的一些限制，其实也是蛮有道理的。毕竟从正则式反推文本，用不到大多数的零宽断言（不过\1这种反向引用应该挺常用的，却不支持）。当作一个小玩具就好。
skydrive外链mp3方案
Jan 10th
使用合租空间的独立博客，例如本人，有时想在自己的空间上传mp3，又有版权（美国空间要求趋严）、流量（被迅雷爬到后果很严重）的担心。经过比较，觉得skydrive的空间挺不错的，25G空间，可支持外链。唯一不足之处是操作比较复杂，使用普通的方法不容易批量提取mp3的外链。今天下午做出一种简单易行的方法，可以直接抓取skydrive的公开文件夹里的mp3音乐文件绝对地址并生成Google Player播放代码（因此您就不需要再安装播放mp3的wordpress各种插件了）。所写的php源码一并贴出，有兴趣的自行研究。如果是正则表达式方面的讨论，欢迎跟贴；其它问题恕不回复，见谅。
Read the rest of this entry »
抓取页面图片的单行命令
Dec 7th
curl -s $URL |perl -nle "print for m{http://[^\"]+(?:jpg|png|gif)}g;"|sort -u |xargs wget
流程：
- 将包含图片链接的页面（例如http://www.flickr.com/photos/anyaanja/4165312465/sizes/o/ 下载下来，以便析取图片地址。使用的命令是curl -s $URL。这里的地址需要手动替换为你所需要的地址。curl 的-s选项是表明使用silent模式，避免任何输出。
- 使用perl解析刚刚下载的页面，找到以http开头，以jpg、png、gif结尾的图片地址。这里的图片类型任意，只要按照类似的语法可以扩展或缩减。perl的-nle选项表示循环读入输入行，搜索相应匹配行，输出相应部分。详细参见perl one liners。
- perl在这里起解析网页的作用。awk应该也有同样的功效，只是个人感觉awk的正则表达式功能太弱较弱。
- 使用sort -u将生成的url排序。如果有重复项，只保留其一，以免重复下载。
- 使用wget来下载这些图片到当前目录。由于wget 默认无法接收standard input的输入，因此使用xargs作为中转。
2009120更新：
- 使用
curl -s $URL | grep -o "http://.*\?\(png\|jpg\)" |sort -u |xargs wget
or
curl -s $URL | grep -E -o "http://.*?(png|jpg)" |sort -u |xargs wget
能实现同样的作用。其中，-o是表示只显示匹配部分，而不必显示整行文本（默认情况下是显示整行文本）；-E 是扩展模式的正则，在此模式下问号、括号、竖线都可直接使用，不必在前边加反斜杠。
- 使用perl的话，正则表达式部分比较强大，只是命令臃肿；使用grep，灵活小巧，但是有可能无法使用复杂的正则表达式。
使用正则表达式转换手机联系人名单
Jul 5th
今天换了手机，第一件要紧事就是恢复联系人名单。旧手机是HTC c720W，新手机是Nokia 5320XM，其联系人名单格式不一。难道要我一条条输入吗？阿弥陀佛，几百组联系人的信息，手动操作会死人的。
我看了一下以前备份的HTC c720W联系人名单，（说到这里，表扬一下自己：勤于备份真是好习惯，万一某天灾难降临，你还有个指望），发现其格式是这样的：
-
-2147483070
0
SomeBody
1355***9214
***
1899-12-30 00:00:00
1899-12-30 00:00:00
-
...
而诺基亚的通讯录格式是这样的：
"名称","名","中间名","姓","后缀","职务","公司","生日","SIP 地址","一键通","共享视图","用户 ID","备忘","常用手机","常用电话","常用电子邮件","常用传真","常用视频电话","常用网址","常用 VOIP 地址","常用邮政信箱","常用分机","常用街道","常用邮政编码","常用城市","常用省/市/自治区","常用国家/地址","家庭手机","住宅电话","家庭电子邮件","住宅传真","家庭视频电话","家庭网址","家庭 VOIP 地址","家庭邮政信箱","家庭分机","家庭街道","家庭邮政编码","家庭城市","家庭省/市/自治区","家庭国家/地区","公司手机","公司电话","公司电子邮件","公司传真","公司视频电话","公司网址","公司 VOIP 地址","公司邮政信箱","公司分机","公司街道","公司邮政编码","公司城市","公司省/市/自治区","公司国家/地区",""
本想偷懒，去找个xml2csv什么的，不过不太好用。还是请“正则表达式”这个老朋友帮忙吧！
分析xml文件，发现只有
mobiletelephonenumber，businesstelephonenumber，hometelephonenumber，firstname，lastname这5个字段是有用的；对应的csv字段名称是：
“名”,”姓”,”常用手机”,”常用电话”,”公司电话”
其余的字段大可放心删除。
祭出RegexBuddy，写了这样一条正则表达式：
1 2 3 4 5 6 7 8 9 10 | result = re.sub( r"""(?smx)(?#"名","姓","常用手机","常用电话","公司电话") ^\s*<item>.*? <mobiletelephonenumber/?>(?P<mobile>[^\s<]*).*? <businesstelephonenumber/?>(?P<business>[^\s<]*).*? <hometelephonenumber/?>(?P<home>[^\s<]*).*? <firstname/?>(?P<first>[^\s<]*).*? <lastname/?>(?P<lastname>[^\s<]*).*? </item>""", r'"\g<first>","\g<lastname>","\g<mobile>","\g<home>","\g<business>"', subject) |
之所以使用python格式来写正则，是因为它支持命名捕获，看起人直观一些。其实整个替换过程是在RegexBuddy中进行的。
替换后，保存为CSV文件，使用诺基亚自带的软件导入，几百个联系人就又重新归位了。大爽。
附图：
25f30c5f
Comments