统计重复文本行的两种方法
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这种反向引用应该挺常用的，却不支持）。当作一个小玩具就好。
正则表达式匹配规则
Jan 30th
原文：How will my regular expression match?
作者：hv
译文：正则表达式的匹配过程
译者：rex
rex译注：在《Programming Perl》第三版第五章，讲了正则匹配的六条规则，深入，透彻，但是不易理解。可以将本文当作是该章的简化版。另外，一定的正则式调试经验也有助于理解正则式的匹配过程。可以参考《Programming Perl》第五章“正则表达式编译器”一节，或阅读这篇文章《Debugging Regular Expressions》。建议阅读例程序时，先默想输出结果，然后再上机测试，最后再看本文的答案。
经常见到关于正则表达式“偏好”的讨论，即，正则表达式引擎“喜欢”更长的、更短的，还是最左端的匹配。
事实非常简单：正则表达式引擎总是返回它所匹配到的第一个结果，如果你理解了正则表达式尝试匹配的顺序，你就再也不会对找到哪一个匹配而困惑了。
下面是一些简单规则（次序无关），阐释正则引擎尝试匹配的顺序。
1．从最左端的字符开始
引擎从目标字串的第一个字符开始，对正则模式进行匹配测试。只有当在第一个字符位置测试完整个正则模式且匹配失败时，引擎才会移动到目标字串的下一个字符，重新开始匹配测试。这样依次测试，直到字串的结束位置。
例子：
1 2 | ($match) = "The longest word" =~ /(\w+)/; print $match; |
其输出结果是“The”（请先自行猜测，再使用鼠标选定，查看结果；下同。），原因是匹配是从字串的最左端开始的。这个单词之后，还有一个更长的单词可以匹配，但是正则引擎却对其视而不见：只要从字串开始处进行匹配且成功，它就返回这个结果，匹配过程就结束了。
Rex:如果正则式是以$结尾的，例如abc$，该正则在试图匹配字串“xyzabc”是否会首先跳到最后一个字符开始比较呢？我的理解是，就常规的正则引擎的正常的匹配过程而言，虽然有$符，但是该$符与普通字符一样，不会特殊处理，整条正则式会在x,y,z处失败3次，然后在a处再开始匹配测试并最终成功。$不会加速匹配过程，只是保证了最终匹配位置。但是不排除具体的正则引擎，会对定位锚点进行优化，从而实现early exit，即只要不符合某一条件，就提前退出，从而减少真正的比较次数，提升效率。看一下abc$ 的perl代码：
Perl引擎对该正则式的分析是：精确匹配普通文本abc；之后是行尾结束符；结束。在匹配时，它直接就“猜”到了匹配结果。
2. 最左边的备选项优先
如果正则模式中含备选项，那么首先测试左边的选项。如果最左侧的备选项成功匹配，那么就继续使用剩余的正则表达式剩余的字串进行匹配测试；只有在最左边的备选项不能匹配时才依次尝试下一个备选项。
例子：
1 2 | ($match) = "Mrs Smith" =~ /(Mr|Mrs)/; print $match; |
其输出结果是“Mr”，因为最左端的正则备选项匹配成功，在本例中也就意味着整个正则表达式匹配成功。此时第二个备选项就被完全无视了。
3. 贪婪模式
对于任何常规的量词（即? * + {1,3}），引擎首先会尝试允许范围内最大数量的重复次数（如果实际文本不足，则尽可能多地重复），然后继续使用剩余的正则表达式剩余的字串进行匹配测试。只有当剩余的正则匹配失败时，引擎才不情愿地“吐出”一次重复的文本，尝试进行后续的匹配，直到匹配成功，或到达允许重复的最小次数。
例子：
1 2 | ($match) = "/foo/bar" =~ m[.*/(.*)]; print $match; |
其输出结果是”bar“。匹配过程是：
.*先匹配完整个字串/foo/bar；此时发现.*之后还需要匹配一个/，此时只好回退字串，.*此时是/foo/ba，然后是/foo/b，/foo/，/foo。此时，后续的正则式得到了/，得以继续匹配并最终成功，返回它认为正确的结果。看图：
Rex: 如果我们想把下面的英文字串
At this point the remaining pattern matches, so this is the match returned提取出最后一个单词和其它部分，应该怎样写正则呢？(.*)(\w+)$吗？这样的话，$2中只有d这个字母。正确的写法包括：
.*\b(\w+)$ # .*先用完整个字符，再一个字符一个字符地回退，直到遇到一个单词边界，然后开始找\w+。
4. 懒惰模式
在量词之后加上问号?（即?? *? +? {1,3}?），就由贪婪模式变为懒惰模式，匹配的过程也随之改变：引擎先尝试允许范围内最少次数的重复，随即使用后续的正则对后续的字串作匹配测试。只有当后续的正则匹配失败时，引擎才懒洋洋地再吃进一次重复，再进行后续匹配测试，直到匹配成功，或到达所允许的匹配次数上限。
例子：
1 2 | ($match) = "foo/bar/baz" =~ m[.*?/(.*)]; print $match; |
显而易见，输出结果是bar/baz。匹配过程中，.*?先匹配空字串”"，然后是”f”，”fo”，”foo”，此时匹配成功，并返回相应结果。
Rex:继续思考上节的问题，另一种将At this point the remaining pattern matches, so this is the match returned中最后一个单词与其余部分分开的正则式还可以是：
.*?\w+$
5. 正则式各部分的匹配次序：从左到右
上面一些例子中的暗含前提是正则模式之间的匹配次序是从左到右。因此在“贪婪模式”例子中有两个.*，基于本条规则，只有当第一个.*的条件满足之后，它才会考虑后续的正则表达式该如何匹配。
6. 嵌套
其实这只是“从左到右”规则的引申。参见下面的例子：
($outer, $inner) = "/foo/bar" =~ m[(/(.+))*]; print $inner;
其输出结果是“foo/bar”。正则引擎先遇到外层的量词，意识到该部分正则要尽可能多地重复，然后开始尝试匹配内层的正则。嵌于内层的量词是贪婪的，因此也会尽可能多地重复，它抓到的字串是foo/bar这部分。此时，外层量词没有机会再重复一次匹配了，但是没有关系——整个正则表达式已经成功匹配，因此返回相应结果。
本文概括了绝大部分常规正则表达式的匹配规则。其余不常见的情况，仍需留心（例如锚点，pos()，以及各种各样的零宽断言）。同时，正则表达式优化器有时会让引擎略过某些步骤，但前提条件是目标匹配结果不变。
Rex注：将何伟平先生译的《Programming Perl》中的正则匹配规则也抄录在这里。只列提纲，需要详细内容的请自行翻书。
- 规则1：引擎试图尽可能地匹配字符串的左边，这样整个正则表达式按照规则2匹配。
引擎从字符串的第一个字符开始，然后从那里开始尝试匹配整个模式。只有引擎在到达字符串的终点之前先到达模式的终点才是整个模式的匹配。如果匹配，引擎马上退出——它不会继续寻找“更好的”匹配，即便模式可能以几种不同的方式匹配也如此。- 规则2：当引擎碰到一个候选集合时（用|符号分隔），不管是在顶层还是在当前“群集”层次中，它都从左向右尝试这些候选项，并且在第一个可以成功完成整个模式匹配的候选项处停止。
- 规则3：如果根据规则4和5（这样整个正则表达式就可以满足了），某个候选项里顺序列出的每个项都匹配，那么这个候选项就是匹配项。
（rex注：列出的每个项，觉得这里说“子项”，层次更清晰。）
- 规则4：如果一个断言不出猎在当前位置匹配，引擎将回溯到规则3并重新以不同的选择试验高强弱顺序的项。
- 规则5：一个量化的原子只有在其本身匹配了其量词许可的次数才算匹配。（原子本身是按照规则6匹配的）。
- 规则6：每个原子都根据它的类型指定的语义来匹配。如果该原子 不匹配（或者它匹配而模式的其余部分不匹配），那么引擎将回溯到规则5,然后尝试该原子 的数量的下一选择。
skydrive外链mp3方案
Jan 10th
使用合租空间的独立博客，例如本人，有时想在自己的空间上传mp3，又有版权（美国空间要求趋严）、流量（被迅雷爬到后果很严重）的担心。经过比较，觉得skydrive的空间挺不错的，25G空间，可支持外链。唯一不足之处是操作比较复杂，使用普通的方法不容易批量提取mp3的外链。今天下午做出一种简单易行的方法，可以直接抓取skydrive的公开文件夹里的mp3音乐文件绝对地址并生成Google Player播放代码（因此您就不需要再安装播放mp3的wordpress各种插件了）。所写的php源码一并贴出，有兴趣的自行研究。如果是正则表达式方面的讨论，欢迎跟贴；其它问题恕不回复，见谅。
Read the rest of this entry »
[译]递归正则表达式
Dec 16th
原文在此。rex译于2009年12月15～17日，翻译过程中使用的是google docs@prism@firefox@ubuntu 9.10，很爽的体验。感谢余晟老师在正则和翻译方面的悉心指导。
平时我们用到的正则表达式，其实没那么“规则”。多数编程语言所支持的扩展的正则表达式，其运算能力比起形式语言理论所定义的“规则”正则表达式要强得多。
rex注：在这里其实可以看到，如果将正则表达式译为正规表达式，一切就都通顺了：
平时我们用到的正规表达式，其实没那么“正规”。多数编程语言所支持的扩展的正规表达式，其运算能力比起正式语言理论所定义的“正规”正规表达式要强得多。regular expression的日文是“正规表现”，在鸟哥书中，好像也将其称为正规表达式。via
例如，经常用到的捕获缓存，就是用来帮助我们临时存储任意正则表达式模式，以便重复使用。 又如，“环视断言”能让正则表达式引擎在做决定之前先偷偷看看环视一下。这些扩展让正则表达式非常强大，足以描述一些“上下文无关语法”。
Perl语言的正则表达式引擎特性异常丰富，其特征之一是懒惰正则子表达式（Lazy regular subexpressions），格式为(??{code})，其中的“code”可以是任意一段perl程序，该子表达式可能匹配时，这段程序就会执行。
我们可以利用这一特征来编写出非常有趣的东西，即将正则表达式自身嵌在它的“code”部分，由此生成递归的正则表达式(a recursive regular expression)！
一直以来，正则表达式无法匹配0n1n这种表达式，也就是由若干个0以及同等数量的1所组成的字符串。如果使用懒惰正则子表达式，这一经典问题就迎刃而解。
下面是匹配0n1n字串的perl正则表达式代码。
$regex = qr/0(??{$regex})?1/;
rex注：紫龙书第四章有云：“文法是比正则表达式表达能力更强的表示方法。每个可以使用正则表达式描述的构造，都可以使用文法来描述，但是反之不成立。换句话说，每个正则语言都是一个上下文无关语言，但是反之不成立。”书中交待的正则，也应该是指的常规正则表达式，而非现代语言中的扩展的正则表达式。一般使用正则表达式来构造小部件，而使用文法来组建语言框架。
此正则表达式匹配一个字符0，之后是正则表达式自身0或1次，之后是字符1。如果正则表达式自身部分不能匹配，那么它只能匹配01；如果自身部分可以匹配，则正则表达式匹配的是00($regex)?11，此时若不能匹配自身则结果是0011，若可以匹配就是000($regex)?111，……依次顺延。
下面是匹配050000150000的Perl程序：
1 2 3 4 5 6 7 8 9 10 11 | #!/usr/bin/perl $str = "0"x50000 . "1"x50000; $regex = qr/0(??{$regex})*1/; if ($str =~ /^$regex$/) { print "yes, it matches"; } else { print "no, it doesn't match"; } |
现在来看题图所示的Yo Dawg正则表达式。你先猜猜它的作用？正确答案是，它匹配(foo(bar())baz)这样完全嵌套的括号表达式（fully parenthesized expression）或((()()())())这样的平衡括号表达式（balanced parentheses）。
1 2 3 4 5 6 7 8 9 | $regex = qr/ \( # (1) match an open paren ( #(1)，此处匹配开括号 ( # followed by #(2)，紧接着是 [^()]+ # (3) one or more non-paren character #(3)，1个或多个非括号字符 | # OR #(4)，或 (??{$regex}) # (5) the regex itself #(5)，正则式自身 )* # (6) repeated zero or more times #(6)，重复0或多次 \) # (7) followed by a close paren ) #(7)，紧接着是闭括号 /x; |
rex注：关于Yo Dawg图片的含义，可以参考这里。基本上是全是“Yo dawg, I herd you like X, so we put a Y in your Y so you can Z while you Z”的结构的配图文字。
构造此正则表达式的思路是这样的。对于完全嵌套的括号表达式，它的开始字符是一个开括号。这是最简单的一步，我们直接写出（上面程序中的(1)）。同理，它的结束字符是闭括号，于是得到(7)。现在该动脑筋了，括号中间是什么呢？对，它可以是既不是开括号又不是闭括号的任意字符（第(3)点），也可以是另一个完全嵌套的表达式（即第(5)点）。所有的这些，既可以只匹配0次（第(3)点），以便构造最小的完全嵌套括号表达式()，也可以匹配多次来匹配较复杂的表达式。
去掉 /x 选项（即，不再使用多行风格的注释模式），可以简记为：
$regex = qr/\(([^()]+|(??{$regex}))*\)/;
但是切勿在正式产品中使用这一特性，它太诡异，不好把握。建议使用较稳定成熟的Text::Balanced 或 Regexp::Common 模块。
rex注：对于(??{code})，perl官方的提示是：此正则表达式仅作测试使用，可能有更新而不作提示。代码执行时产生的副作用，因版本而异，运行结果或有不同，取决于正则引擎的后期优化。
最后提醒大家，在Perl 5.10中已经可以使用递归捕获缓存来替代懒惰代码子表达式了，运行结果相同。
下面是匹配0n1n的递归捕获缓存语法(?N)的实现：
my $rx = qr/(0(?1)*1)/;
(?1)*的含义是“匹配第一组0或多次”，这里的第一组是指整个正则表达式。
请自行动手，重写平衡括号的正则表达式，当作练习。
祝玩得开心！
抓取页面图片的单行命令
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，灵活小巧，但是有可能无法使用复杂的正则表达式。
笔记：如何写出高效率的正则表达式
Nov 30th
如果纯粹是为了挑战自己的正则水平，用来实现一些特效（例如使用正则表达式计算质数、解线性方程），效率不是问题；如果所写的正则表达式只是为了满足一两次、几十次的运行，优化与否区别也不太大。但是，如果所写的正则表达式会百万次、千万次地运行，效率就是很大的问题了。我这里总结了几条提升正则表达式运行效率的经验（工作中学到的，看书学来的，自己的体会），贴在这里。如果您有其它的经验而这里没有提及，欢迎赐教。
为行文方便，先定义两个概念。
- 误匹配：指正则表达式所匹配的内容范围超出了所需要范围，有些文本明明不符合要求，但是被所写的正则式“击中了”。例如，如果使用\d{11}来匹配11位的手机号，\d{11}不单能匹配正确的手机号，它还会匹配98765432100这样的明显不是手机号的字符串。我们把这样的匹配称之为误匹配。
- 漏匹配：指正则表达式所匹配的内容所规定的范围太狭窄，有些文本确实是所需要的，但是所写的正则没有将这种情况囊括在内。例如，使用\d{18}来匹配18位的身份证号码，就会漏掉结尾是字母X的情况。
写出一条正则表达式，既可能只出现误匹配（条件写得极宽松，其范围大于目标文本），也可能只出现漏匹配（只描述了目标文本中多种情况种的一种），还可能既有误匹配又有漏匹配。例如，使用\w+\.com来匹配.com结尾的域名，既会误匹配abc_.com这样的字串（合法的域名中不含下划线，\w包含了下划线这种情况），又会漏掉ab-c.com这样的域名（合法域名中可以含中划线，但是\w不匹配中划线）。
精准的正则表达式意味着既无误匹配且无漏匹配。当然，现实中存在这样的情况：只能看到有限数量的文本，根据这些文本写规则，但是这些规则将会用到海量的文本中。这种情况下，尽可能地（如果不是完全地）消除误匹配以及漏匹配，并提升运行效率，就是我们的目标。本文所提出的经验，主要是针对这种情况。
- 掌握语法细节。正则表达式在各种语言中，其语法大致相同，细节各有千秋。明确所使用语言的正则的语法的细节，是写出正确、高效正则表达式的基础。例如，perl中与\w等效的匹配范围是[a-zA-Z0-9_]；perl正则式不支持肯定逆序环视中使用可变的重复（variable repetition inside lookbehind，例如(?<=.*)abc），但是.Net语法是支持这一特性的；又如，JavaScript连逆序环视（Lookbehind,如(?<=ab)c）都不支持，而perl和python是支持的。《精通正则表达式》第3章《正则表达式的特性和流派概览》明确地列出了各大派系正则的异同，这篇文章也简要地列出了几种常用语言、工具中正则的比较。对于具体使用者而言，至少应该详细了解正在使用的那种工作语言里正则的语法细节。
- 先粗后精，先加后减。使用正则表达式语法对于目标文本进行描述和界定，可以像画素描一样，先大致勾勒出框架，再逐步在局步实现细节。仍举刚才的手机号的例子，先界定\d{11}，总不会错；再细化为1[358]\d{9}，就向前迈了一大步（至于第二位是不是3、5、8，这里无意深究，只举这样一个例子，说明逐步细化的过程）。这样做的目的是先消除漏匹配（刚开始先尽可能多地匹配，做加法），然后再一点一点地消除误匹配（做减法）。这样有先有后，在考虑时才不易出错，从而向“不误不漏”这个目标迈进。
- 留有余地。所能看到的文本sample是有限的，而待匹配检验的文本是海量的，暂时不可见的。对于这样的情况，在写正则表达式时要跳出所能见到的文本的圈子，开拓思路，作出“战略性前瞻”。例如，经常收到这样的垃圾短信：“发*票”、“发#漂”。如果要写规则屏蔽这样烦人的垃圾短信，不但要能写出可以匹配当前文本的正则表达式 发[*#](?:票|漂)，还要能够想到 发.(?:票|漂|飘)之类可能出现的“变种”。这在具体的领域或许会有针对性的规则，不多言。这样做的目的是消除漏匹配，延长正则表达式的生命周期。
- 明确。具体说来，就是谨慎用点号这样的元字符，尽可能不用星号和加号这样的任意量词。只要能确定范围的，例如\w，就不要用点号；只要能够预测重复次数的，就不要用任意量词。例如，写析取twitter消息的脚本，假设一条消息的xml正文部分结构是<span class=”msg”>…</span>且正文中无尖括号，那么<span class=”msg”>[^<]{1,480}</span>这种写法的思路要好于<span class=”msg”>.*</span>，原因有二：一是使用[^<]，它保证了文本的范围不会超出下一个小于号所在的位置；二是明确长度范围，{1,480}，其依据是一条twitter消息大致能的字符长度范围。当然，480这个长度是否正确还可推敲，但是这种思路是值得借鉴的。说得狠一点，“滥用点号、星号和加号是不环保、不负责任的做法”。
- 不要让稻草压死骆驼。每使用一个普通括号()而不是非捕获型括号(?:…)，就会保留一部分内存等着你再次访问。这样的正则表达式、无限次地运行次数，无异于一根根稻草的堆加，终于能将骆驼压死。养成合理使用(?:…)括号的习惯。
- 宁简勿繁。将一条复杂的正则表达式拆分为两条或多条简单的正则表达式，编程难度会降低，运行效率会提升。例如用来消除行首和行尾空白字符的正则表达式s/^\s+|\s+$//g;，其运行效率理论上要低于s/^\s+//g; s/\s+$//g; 。这个例子出自《精通正则表达式》第五章，书中对它的评论是“它几乎总是最快的，而且显然最容易理解”。既快又容易理解，何乐而不为？工作中我们还有其它的理由要将C==(A|B)这样的正则表达式拆为A和B两条表达式分别执行。例如，虽然A和B这两种情况只要有一种能够击中所需要的文本模式就会成功匹配，但是如果只要有一条子表达式（例如A）会产生误匹配，那么不论其它的子表达式（例如B）效率如何之高，范围如何精准，C的总体精准度也会因A而受到影响。
- 巧妙定位。有时候，我们需要匹配的the，是作为单词的the（两边有空格），而不是作为单词一部分的t-h-e的有序排列（例如together中的the）。在适当的时候用上^，$，\b等等定位锚点，能有效提升找到成功匹配、淘汰不成功匹配的效率。
总结完发现，《精通正则表达式》的第5章、第6章已经以更为有条理的方式总结出了常用的优化方法。不过，泛泛地读过的印象是肤浅的，过后即忘的；而真正若有所悟时在书上得到了系统地印证，这种感觉才是真的爽。
效率问题
Oct 22nd
上周发了篇《两条与密码验证相关的正则表达式问题》。今天看了些python的正则表达式，心血来潮，想看看这几种正则哪种效率较高。代码、运行结果见下。这是为什么呢？
#!/usr/bin/python import re import time import fpformat Regex1 = re.compile("^(?=[0-9a-zA-Z@%&]*\d)(?=[0-9a-zA-Z@%&]*[a-zA-Z])(?=[0-9a-zA-Z@%&]*[@%&])[0-9a-zA-Z@%&]{8,}$", re.MULTILINE) Regex2 = re.compile("^(?=.*\d)(?=.*[a-zA-Z])(?=.*[@%&])[0-9a-zA-Z@%&]{8,}$", re.MULTILINE) Regex3 = re.compile("^(?![0-9a-z]{8,16}$|[@%&]{8,16}$)[a-z0-9@%&]{8,16}$", re.IGNORECASE |re.MULTILINE) TimesToDo = 1250; TestString = "" for i in range(800): TestString += "aba134babdedfg@&%\n" StartTime = time.time() for i in range(TimesToDo): Regex1.search(TestString) Seconds = time.time() - StartTime print "R1 takes " + fpformat.fix(Seconds,3) + " seconds" StartTime = time.time() for i in range(TimesToDo): Regex2.search(TestString) Seconds = time.time() - StartTime print "R2 takes " + fpformat.fix(Seconds,3) + " seconds" StartTime = time.time() for i in range(TimesToDo): Regex3.search(TestString) Seconds = time.time() - StartTime print "R3 takes " + fpformat.fix(Seconds,3) + " seconds"
运行结果：
两条与密码验证相关的正则表达式问题
Oct 16th
- 问题1: 密码验证：由且仅由数字、字母（大小写）、特殊符号（@ % &…）组成，三者缺一不可，密码不少于8位。
- 问题2: 十位的数字、字母组合密码，其中包含4位数字和6位字母。
感兴趣的话，建议您在读下文之前，自己思考一下解法，以免被我的思路干扰。
Stage0
对于问题1，它需要满足的条件如下：
- 8位以上；
- 必须包含1位以上的数字；
- 必须包含1位以上的字母；
- 必须包含1位以上的特殊字符。
对于这样的要求，简单使用[0-9a-za-Z@%&]{8,}来匹配的。因此它也匹配像00000000、1111aaaaa这样只含一种或两种字符的字符串。因此，我们要加上更为严格的限制条件，以便匹配更精确。
Stage1
代码:
[0-9a-zA-Z@%&]+\d
字母必须出现一次，则对于每个字符位置来说，它应该是这样的：
代码:
[0-9a-zA-Z@%&]+[a-zA-Z]
特殊字符必须出现一次，则对于每个字符位置来说，它应该是这样的：
代码:
[0-9a-zA-Z@%&]+[@%&]
这三个条件必须同时满足，因此：
代码:
(?=[0-9a-zA-Z@%&]+\d)(?=[0-9a-zA-Z@%&]+[a-zA-Z])(?=[0-9a-zA-Z@%&]+[@%&]).{8,}
为了保证字符整行匹配，需要加上条件^$：
代码:
^(?=[0-9a-zA-Z@%&]+\d)(?=[0-9a-zA-Z@%&]+[a-zA-Z])(?=[0-9a-zA-Z@%&]+[@%&]).{8,}$
它匹配的是，8位(包括)以上字符，由且仅由数字、字母和特殊字符组成。
Stage2
上图中Test部分中彩色部分为正则表达所匹配的字串。但是前三条是符合要求的，却不被匹配。之所以会出现这样的情况，是因为在环视条件中使用了+量词，这会将本来用作辅助验证的字符被消耗掉，原本合格的字串被误认为不合格了。
问题出在+上，因此我们使用*量词，这样就好多了。正则表达式为：
^(?=[0-9a-zA-Z@%&]*\d)(?=[0-9a-zA-Z@%&]*[a-zA-Z])(?=[0-9a-zA-Z@%&]*[@%&]).{8,}$
匹配效果如下所示：
Stage3
但是问题依然存在。测试发现，像这样的字串也是匹配的，但是它显然不是合格的密码字串：
之所以出现这样的问题，是因为stage2代码中
.{8,}$
前边千辛万苦使用[0-9a-zA-Z@%&]所界定的条件，在这里轻轻松松被破坏了。stage2其实只管前8位，只要前8位字符符合要求，它就认为万事大吉了。
认识到这一点，我写个一条长长的正则式：
^(?=[0-9a-zA-Z@%&]*\d)(?=[0-9a-zA-Z@%&]*[a-zA-Z])(?=[0-9a-zA-Z@%&]*[@%&])[0-9a-zA-Z@%&]{8,}$
但是这条正则表达太复杂了。能不能短一些呢？当然可以。从上文可以看出，前边其实不必界定太复杂的条件，只要在最后加上条件判断即可。因此，正则表达式可以改为：
^(?=.*\d)(?=.*[a-zA-Z])(?=.*[@%&])[0-9a-zA-Z@%&]{8,}$
这样一来，我们就得到了这道题迄今为止最简洁的解法。
同理可得，第二道题的解法是：
^(?=.*\d)(?=.*[a-zA-Z])(?=.*[@%&])[0-9a-zA-Z@%&]{8,}$
不多解释。
在思考本题的过程中，感谢创亿无限在stage2的测试，感谢余晟老师在stage3中的指点。余老师现在正写一本正则表达式的傻瓜书，请点击余晟老师的博客来探寻详情。
正则学习杂感：磨刀不误砍柴功
Sep 23rd
反复读紫龙书第三章，以及网文Write Your Own Regular Expression Parser（链接在这篇文章中找），连同该网文附带的源码，终于破关。一点感悟，写在这里。
使用正则表达式搜索字串，比逐位进行strcmp这样的方法要复杂N倍，如果说strcmp是只支持＋－×÷的计算器的话，那么正则表达式就是一台现代化的电脑。正则式不用逐位比较，它有自己的一整套方法。
要想在源字串找某个正则式模式，需要先详尽地分析该正则式，其过程是将该正则式解剖成不可再分的字符（称为状态），然后从任意一个状态开始，通过不同的路径（字符输入）可以到达不同的状态。第一个字符之前，叫做初始状态；最后一个字符之后，叫做接收状态。这种是NFA（不确定的有穷自动机），因为一个状态上有可能存在不止一条的转出状态。
一旦做好了这样的状态集合，就可以进行匹配了。每输入一个字符，从开始状态上就会产生不同的状态集合；依次输入完毕，如果所得到状态集合中包含了一个接受状态，就证明所输入的串是匹配的。但是NFA的效率低下。因为从每个状态上转出的路径不止一条，因此就有回溯。为提升效率，可以将NFA转成等效的DFA，即确定的有穷自动机。
DFA的原理是，对于每个状态集合D和给定的输入字符a，最多只有一条通路可走。与NFA的区别是，对于每个单个的状态f和给定的字符a，就有N条路可走。但是DFA也不是生来就万能的，比方说，它有死状态需要消除，同构的状态需要合并，还存在对于复杂正则表达式的DFA的转换效率低、实现复杂度高的情况，等等。虽如此，NFA转换为DFA还是值得的，有道是磨刀不误砍柴功。
对于正则表达式做好了DFA，就可以进行匹配了。每输入一个字符，自动机就转至下一个状态集合，直至输入结尾。如果所达到的状态集合中包含了接受状态，那么匹配就是成功的。
以上就是NFA、DFA的原理。当然，细节是简化过的。否则的话，上面任何一个步骤都有N多的细节，需要使用各种奇怪的数据结构来存储，复杂的成员函数来操作。
说到这里，想起python, pcre，以及其它一些正则表达式库，都有compile一个选项。先编译再执行，一次编译多次执行，文档一再这样强调。这比一上来就execute效率要高，如果重复执行多次的话。以前总是图方便直接就execute了，现在想想，实现一个正则表达式多不容易呀，对于多次重复的匹配，还是老老实实地compile一次才有礼貌。正则引擎在幕后默默无闻地做了那么多工作，不应该老是麻烦它老人家，呵呵。
正则学习杂感，附几枚链接
Sep 18th
最近在学习编译原理，尤其是正则表达式的实现这一节。从网上搜索到有用的链接，张贴在这里。一个感受是，数学知识是非常有用的，尤其是创造性的编程。如果数学知识足够，完全可以写出更加高效的算法；如果数学知识不够，最多只是重复别人已经写好的算法而已。因此在初步学习时，可以不必另造车轮，老老实实地学习已经很成熟的算法，才是正途。
至于正则表达式的实现，其实也只是先有数学思想，然后将其使用编程语言实现而已。准备步骤是先归纳语法树，自顶至下，逐级细分；而实现步骤是从现有的正则表达式自叶至顶，先将正则式转换为NFA图，再优化，转为DFA，这时才可与目标字串进行比较。
在看紫龙书时，感觉到其中从思路到算法，从伪代码到实际代码之间，其转换需要太多的细节来补充。而这些知识，不单来自于对具体语言语法的掌握，还需要合适的数据支持，才能化繁为简，事半功倍。顺便读了一些C++ STL的内容，觉得这些标准库真是相当有用，在构建正则表达式时这些库正好可以物尽其用。STL的作者善莫大焉。
从理论上说，即使没有STL支持的纯C语言，对于实现正则表达式也是没有任何问题的，只不过是自己捎带着再写一遍自己需要的数据结构而已。别说C，就是宏汇编，也可以实现的。如果感兴趣，可以自行到Aogo的www.aogosoft.com上自行搜索他的实现。归结到一句话：思路有了，语言的实现只是翻译。我等初学者是无力想出更高级的实现的，只是在这种翻译过程中，作为一种深化理解和课后练习罢。言归正传，下面是我要推荐的几则链接。
1. 《正则表达式识别》 http://blog.csdn.net/slavik/archive/2006…40386.aspx
有图有真相。本文的配图还是挺丰富的。思路也清晰。极具指导意义。
可惜没有源码。该博客的其它相关文章，也值得阅读。
2. 正则表达式 TO NFA表格
http://hi.baidu.com/rabbit5455/blog/item…1aac8.html
这篇文章主要是提供了源码，源码中附注释。也不错。
3. 《Write Your Own Regular Expression Parser》 http://www.codeguru.com/cpp/cpp/cpp_mfc/….php/c4093
本文是英文文章，有图示，有源码，很不错。我正在边阅读，边学习，边翻译，一边自行实现。建议直接阅读英文资料，不必等我的翻译。本文的代码只提供了*,|，以及连接操作的实现。不过也对其它操作的实现给出了指导。我已经在源代码基础上添加了问号和加号的支持。
[转]理解正则表达式
Aug 30th
rex注：本文原作者孟岩，原文转自孟岩CSDN博客。本文为《程序员》07年3月号《七种武器》专题所做。rex以前只是知道如何使用正则表达式而已，在读MRE时，读到NFA、DFA其实都是一头雾水，不知所云。现在抓紧时间恶补基础知识，学习了些编译原理，这才有些明白。如今再看从源头讲正则表达式的文章，就心有戚戚了，呵呵。搜到好文章一篇，与大家分享。
在程序员日常工作中，数据处理占据了相当的比重。而在所有的数据之中，文本又占据了相当的比重。文本能够被人理解，具有良好的透明性，利于系统的开发、测试和维护。然而，易于被人理解的文本数据，机器处理起来就不一定都那么容易。文本数据复杂多变，特定性强，甚至是千奇百怪。因此，文本处理程序可谓生存环境恶劣。一般来说，文本处理程序都是特定于应用的，一个项目有一个项目的要求，彼此之间很难抽出共同点，代码很难复用，往往是“一次编码，一次运行，到处补丁”。其程序结构散乱丑陋，谈不上有什么“艺术性”，基本上与“模式”、“架构”什么的无缘。在这里，从容雅致、温文尔雅派不上用场，要想生存就必须以暴制暴。
事实上，几十年的实践证明，除了正则表达式和更高级的parser技术，在这样一场街头斗殴中别无利器。而其中，尤以正则表达式最为常用。所以，对于今天的程序员来说，熟练使用正则表达式着实应该是一种必不可少的基本功。然而现实情况却是，知道的人很多，善于应用的人却很少，而能够洞悉其原理，理智而高效地应用它的人则少之又少。大多数开发者被它的外表吓倒，不敢也不耐烦深入了解其原理。事实上，正则表达式背后的原理并不复杂，只要耐心学习，积极实践，理解正则表达式并不困难。下面列举的一些条款，来自我本人学习和时间经验的不完全总结。由于水平和篇幅所限，只能浮光掠影，不足和谬误之处，希望得到有识之士的指教。
1. 了解正则表达式的历史
正则表达式萌芽于1940年代的神经生理学研究，由著名数学家Stephen Kleene第一个正式描述。具体地说，Kleene归纳了前述的神经生理学研究，在一篇题为《正则集代数》的论文中定义了“正则集”，并在其上定义了一个代数系统，并且引入了一种记号系统来描述正则集，这种记号系统被他称为“正则表达式”。在理论数学的圈子里被研究了几十年之后，1968年，后来发明了UNIX系统的Ken Thompson第一个把正则表达式用于计算机领域，开发了qed和grep两个实用文本处理工具，取得了巨大成功。在此后十几年里，一大批一流计算机科学家和黑客对正则表达式进行了密集的研究和实践。在1980年代早期，UNIX运动的两个中心贝尔实验室和加州大学伯克利分校分别围绕grep工具对正则表达式引擎进行了研究和实现。与之同时，编译器“龙书”的作者Alfred Aho开发了Egrep工具，大大扩展和增强了正则表达式的功能。此后，他又与《C程序设计语言》的作者Brian Kernighan等三人一起发明了流行的awk文本编辑语言。到了1986年，正则表达式迎来了一次飞跃。先是C语言顶级黑客Henry Spencer以源代码形式发布了一个用C语言写成的正则表达式程序库（当时还不叫open source），从而把正则表达式的奥妙带入寻常百姓家，然后是技术怪杰Larry Wall横空出世，发布了Perl语言的第一个版本。自那以后，Perl一直是正则表达式的旗手，可以说，今天正则表达式的标准和地位是由Perl塑造的。Perl 5.x发布以后，正则表达式进入了稳定成熟期，其强大能力已经征服了几乎所有主流语言平台，成为每个专业开发者都必须掌握的基本工具。
2. 掌握一门正则表达式语言
使用正则表达式有两种方法，一种是通过程序库，另一种是通过内置了正则表达式引擎的语言本身。前者的代表是Java、.NET、C/C++、Python，后者的代表则是Perl、Ruby、JavaScript和一些新兴语言，如Groovy等。如果学习正则表达式的目标仅仅是应付日常应用，则通过程序库使用就可以。但只有掌握一门正则表达式语言，才能够将正则表达式变成编程的直觉本能，达到较高的水准。不但如此，正则表达式语言也能够在实践中提供更高的开发和执行效率。因此，有心者应当掌握一门正则表达式语言。
3. 理解DFA和NFA
正则表达式引擎分成两类，一类称为DFA（确定性有穷自动机），另一类称为NFA（非确定性有穷自动机）。两类引擎要顺利工作，都必须有一个正则式和一个文本串，一个捏在手里，一个吃下去。DFA捏着文本串去比较正则式，看到一个子正则式，就把可能的匹配串全标注出来，然后再看正则式的下一个部分，根据新的匹配结果更新标注。而NFA是捏着正则式去比文本，吃掉一个字符，就把它跟正则式比较，匹配就记下来：“某年某月某日在某处匹配上了！”，然后接着往下干。一旦不匹配，就把刚吃的这个字符吐出来，一个个的吐，直到回到上一次匹配的地方。
DFA与NFA机制上的不同带来5个影响：
1. DFA对于文本串里的每一个字符只需扫描一次，比较快，但特性较少；NFA要翻来覆去吃字符、吐字符，速度慢，但是特性丰富，所以反而应用广泛，当今主要的正则表达式引擎，如Perl、Ruby、Python的re模块、Java和.NET的regex库，都是NFA的。
2. 只有NFA才支持lazy和backreference等特性；
3. NFA急于邀功请赏，所以最左子正则式优先匹配成功，因此偶尔会错过最佳匹配结果；DFA则是“最长的左子正则式优先匹配成功”。
4. NFA缺省采用greedy量词（见item 4）；
5. NFA可能会陷入递归调用的陷阱而表现得性能极差。
我这里举一个例子来说明第3个影响。
例如用正则式/perl|perlman/来匹配文本 ‘perlman book’。如果是NFA，则以正则式为导向，手里捏着正则式，眼睛看着文本，一个字符一个字符的吃，吃完 ‘perl’ 以后，跟第一个子正则式/perl/已经匹配上了，于是记录在案，往下再看，吃进一个 ‘m’，这下糟了，跟子式/perl/不匹配了，于是把m吐出来，向上汇报说成功匹配 ‘perl’，不再关心其他，也不尝试后面那个子正则式/perlman/，自然也就看不到那个更好的答案了。
如果是DFA，它是以文本为导向，手里捏着文本，眼睛看着正则式，一口一口的吃。吃到/p/，就在手里的 ‘p’ 上打一个钩，记上一笔，说这个字符已经匹配上了，然后往下吃。当看到 /perl/ 之后，DFA不会停，会尝试再吃一口。这时候，第一个子正则式已经山穷水尽了，没得吃了，于是就甩掉它，去吃第二个子正则式的/m/。这一吃好了，因为又匹配上了，于是接着往下吃。直到把正则式吃完，心满意足往上报告说成功匹配了 ‘perlman’。
由此可知，要让NFA正确工作，应该使用 /perlman|perl/ 模式。
通过以上例子，可以理解为什么NFA是最左子式匹配，而DFA是最长左子式匹配。实际上，如果仔细分析，关于NFA和DFA的不同之处，都可以找出道理。而明白这些道理，对于有效应用正则表达式是非常有意义的。
4. 理解greedy和lazy量词
由于日常遇到的正则表达式引擎全都是NFA，所以缺省都采用greedy量词。Greedy量词的意思不难理解，就是对于/.*/、/\w+/这样的“重复n”次的模式，以贪婪方式进行，尽可能匹配更多字符，直到不得以罢手为止。
举一个例子，以 /<.*>/ 模式匹配 ‘<book> <title> Perl Hacks </title> </book>\t’文本，匹配结果不是 ‘<book>’，而是 ‘<book> <title> Perl Hacks </title> </book>’。原因就在于NFA引擎以贪婪方式执行“重复n次”的命令。让我们来仔细分析一下这个过程。
条款3指出，NFA的模型是以正则式为导向，拿着正则式吃文本。在上面的例子里，当它拿着/.*/这个正则式去吃文本的时候，缺省情况下它就这么一路吃下去，即使碰到 ‘>’字符也不罢手——既然 /./ 是匹配任意字符， ‘>’ 当然也可以匹配！所以就尽管吃下去，直到吃完遇到结尾（包括\t字符）也不觉得有什么不对。这个时候它突然发现，在正则表达式最后还有一个 />/，于是慌了神，知道吃多了，于是就开始一个字符一个字符的往回吐，直到吐出倒数第二个字符 ‘>’，完成了与正则式的匹配，才长舒一口气，向上汇报，匹配字符串从第一个字符 ‘<’ 开始，到倒数第二个字符 ‘>’结束，即’<book> <title> Perl Hacks </title> </book>’。
Greedy量词的行为有时确实是用户所需要的，有时则不是。比如在这个例子里，用户可能实际上想得到的是 ‘book’ 串。怎么办呢？这时候lazy量词就派上用场了。把模式改为/<.*?>/就可以得到 ‘book’。这个加在 ‘*’号后面的 ‘?’ 把greedy量词行为变成lazy量词行为，从而由尽量多吃变为尽量少吃，只要吃到一个 ‘>’立刻停止。
问号在正则表达式里用途最广泛，这里是很重要的一个用途。
5. 理解backtracking
在条款4的基础上解释backtracking就很容易了。当NFA发现自己吃多了，一个一个往回吐，边吐边找匹配，这个过程叫做backtracking。由于存在这个过程，在NFA匹配过程中，特别是在编写不合理的正则式匹配过程中，文本被反复扫描，效率损失是不小的。明白这个道理，对于写出高效的正则表达式很有帮助。
DIY万能通配符
Aug 11th
指定了点号匹配换行符模式，就可以使用点号来匹配包括换行符在内的任意字符了。不过，JavaScript的正则中无法设置点号通配模式，但是我们可以创造一个可以匹配换行符的点号，如下：
(?:.|[\r\n])
除此之外，还可以使用互逆的元字符，来构造这样的万能通配符，例如
[\s\S], [\d\D], [\w\W]
使用普通字符也可以的。因为我们可以将全部字符划分为a和非a，
(?:a|(?!a).)
Comments