效率问题

Oct 22nd

Posted by rex in 杂项

3 comments

上周发了篇《两条与密码验证相关的正则表达式问题》。今天看了些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"

运行结果：
我爱正则表达式|效率问题

concise perl re table

Oct 21st

Posted by rex in 杂项

No comments

GDOC链接在这里。

正则学习杂感：磨刀不误砍柴功

Sep 23rd

Posted by rex in 杂项

2 comments

反复读紫龙书第三章，以及网文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

Posted by rex in 杂项

No comments

最近在学习编译原理，尤其是正则表达式的实现这一节。从网上搜索到有用的链接，张贴在这里。一个感受是，数学知识是非常有用的，尤其是创造性的编程。如果数学知识足够，完全可以写出更加高效的算法；如果数学知识不够，最多只是重复别人已经写好的算法而已。因此在初步学习时，可以不必另造车轮，老老实实地学习已经很成熟的算法，才是正途。

至于正则表达式的实现，其实也只是先有数学思想，然后将其使用编程语言实现而已。准备步骤是先归纳语法树，自顶至下，逐级细分；而实现步骤是从现有的正则表达式自叶至顶，先将正则式转换为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

本文是英文文章，有图示，有源码，很不错。我正在边阅读，边学习，边翻译，一边自行实现。建议直接阅读英文资料，不必等我的翻译。本文的代码只提供了*,|，以及连接操作的实现。不过也对其它操作的实现给出了指导。我已经在源代码基础上添加了问号和加号的支持。

, , ,

DIY万能通配符

Aug 11th

Posted by rex in 杂项

No comments

指定了点号匹配换行符模式，就可以使用点号来匹配包括换行符在内的任意字符了。不过，JavaScript的正则中无法设置点号通配模式，但是我们可以创造一个可以匹配换行符的点号，如下：

(?:.|[\r\n])

除此之外，还可以使用互逆的元字符，来构造这样的万能通配符，例如

[\s\S], [\d\D], [\w\W]

使用普通字符也可以的。因为我们可以将全部字符划分为a和非a，

(?:a|(?!a).)

正则杂谈：从“评论已关闭”到正则表达式之眼

May 27th

Posted by rex in 杂项

1 comment

近来沸沸扬扬地一条饭否消息是评论已关闭，这个关键词真的选的很好，它一下子把所有的一类敏感问题都串起来了，找到了该类问题的共同特征。至于为什么关闭评论，关闭的标准是什么，这里都不做探讨，只是从正则角度谈论一下技术而已。

所谓正则表达式，其实是一种抽象，是从现有的文本中找到规律，然后用正则的语言描述出来。例如，上次有人问，以http开头的，以空格结尾的正则式如何写？这个问题不难，我们只要符合这两个要求即可，即^(http\S+)\s。至于http后面的冒号、双斜杠，都不必劳神去匹配。这样写出来的正则表达式简洁明快，清晰易读。当然，从效率出发，越精确的正则式越有利于尽早失败，有利于提升效率。权衡写的效率与执行的效率，其过程也是很不错的。

数字转美元程序

Feb 15th

Posted by rex in 杂项

No comments

本程序将数字转换为英文的美元数，如： 输入

./num2eng.pl 1,100,834.10

则输出：

Total: Say US Dollars One Million One Hundred Thundsand Eight Hundred and Thirty-Four and Ten Cents Only.

注意事项：

  1. 整数部分可以使用半角的逗号、空格、单引号、下划线、中划线分隔。
  2. 分隔符的位置可以任意（每3位可，每4位也可），可以任意组合（可以混合使用上述的分隔符）。
  3. 如果使用单引号，请注意在最外边加上双引号以免转义。

完整程序：
Read the rest of this entry »

,

使用饭否新版API编写批量抓取饭否消息的程序

Jan 6th

Posted by rex in 杂项

3 comments

我在断断续续地写一款抓饭程序。预想的功能包括：下载、更新饭否消息，搜索，统计。

近日饭否官方释出搜索功能，可以使用关键字搜索自己曾经发布的消息。作离线版的饭否消息管理工具，似乎没有必要。不过，有的网友习惯将饭否消息列到blog上，因此，我的程序还是有用的。

我原来写的程序，时间都消耗在饭否消息的下载、解析上。好在饭否新版API提供了任意页码的饭否消息，大大简化了抓取难度，因此编写一款饭否消息管理工具不再是一件难事。以python语言为例，我把自己的思路写出来，供各位有类似兴趣的朋友参考。

Read the rest of this entry »

, , , ,

饭否私信格式分析

May 31st

Posted by rex in 杂项

1 comment

URL

饭否私信分为两种，一种是我收到的私信，一种是我发出的私信。

  • 我收到的私信：http://fanfou.com/privatemsg/p.(1-N)
  • 我发出的私信：http://fanfou.com/privatemsg/sent/p.(1-N)

上面的地址中不含饭否ID；需要cookie验证。

结束标志

通过cookie验证后，可以使用数字获得对应页码的私信内容。什么时候是结束呢？假如您的收件箱有1000条私信，每页显示20条，那么当你您输入http://fanfou.com/privatemsg/p.51时，就得不到任何有效的内容了。作为程序，它是寻找如下标志：

<ol class="wa">\s*</ol>

好友列表

在页面代码中，每页都有一个“向XXX发送私信”的combox列表，条目以昵称+ID组成。如果你的好友很多的话（500+），每条好友（昵称+ID）需要20字节（估算）的话，20*500=10K，大约需要多抓取10K的字节量。

收件箱饭否私信的结构

收到的私信分为两种，一种是有回复信息的（回复原文:…），一种是没有回复的。先从简单的入手，看没有回复的。
所有的私信都在<ol class=”wa”>…</ol>之内，以<li></li>分隔

例如下面这一条，就是一则很规范的私信（与发件人相关的信息都使以正则式表示）：

<li>
	<a href="/[^"]+" title="[^"]+" class="avatar"><img src="[^"]+" alt="[^"]+" /></a>
	来自<a href="[^"]+">[^"]+</a>：
	<span class="content">没法比较啊,你得说个具体的值,比如100条以下的算少,1000条以上的算多……</span>
	<span class="stamp time" title="2008-05-30 17:25">约 15 小时前</span>
	<span class="op">
		<a href="/privatemsg.reply/583520">回复</a>
		<a href="/privatemsg.del/583520" class="post_act">删除</a></span>
</li>

其中，需要记录的信息有：

  • 发件人名字；
  • 发件人ID；
  • 私信内容；
  • 时间；
  • 私信ID；（便于作删除、回复处理）。

根据以上需求，将上面的私信代码作处理：

<li>
	<a href="/([^"]+)" title="([^"]+)" class="avatar"><img src="[^"]+" alt="[^"]+" /></a>
	来自<a href="[^"]+">[^"]+</a>：
	<span class="content">([^<]+)</span>
	<span class="stamp time" title="([^"]+)">[^<]+</span>
	<span class="op">
		<a href="/privatemsg.reply/(\d+)">回复</a>
		<a href="/privatemsg.del/\d+" class="post_act">删除</a>
	</span>
</li>

从而得到：

$1=fanfou ID;
$2=fanfou name;
$3=private msg;
$4=msg time;
$5=msg ID;

再看一下包含“回复原文”的私信的结构(部分内容已作正则处理)：

<li>
	<a href="/([^"]+)" title="([^"]+)" class="avatar"><img src="[^"]+" alt="[^"]+" /></a>
	来自<a href="[^"]+">[^"]+</a>：
	<span class="content">([^<]+)</span>
	<span class="stamp time" title="([^"]+)">[^<]+</span>
	<span class="op">
		<a href="/privatemsg.reply/(\d+)">回复</a>
		<a href="/privatemsg.del/\d+" class="post_act">删除</a>
	</span>
	<p class="pm-parent">回复原文: 有兴趣就有动力</p>
</li>

与前者相比，只是多了<p class=”pm-parent”>.*?</p>这一段。这是不足为虑的。只要整体加上?这个强有力的正则符号，就能与上面的代码片段归纳到一起。两者结合合的代码如下：

<li>
	<a href="/([^"]+)" title="([^"]+)" class="avatar"><img src="[^"]+" alt="[^"]+" /></a>
	来自<a href="[^"]+">[^"]+</a>：
	<span class="content">([^<]+)</span>
	<span class="stamp time" title="([^"]+)">[^<]+</span>
	<span class="op">
		<a href="/privatemsg.reply/(\d+)">回复</a>
		<a href="/privatemsg.del/\d+" class="post_act">删除</a></span>
	(?:<p class="pm-parent">([^<]+)</p>)?
</li>

得到的变量为：

$1=fanfou ID;
$2=fanfou name;
$3=private msg;
$4=msg time;
$5=msg ID;
$6=parent msg;#回复原文。

发件箱饭否私信的结构

抄代码：

<li>
	<a href="/([^"]+)" title="([^"]+)" class="avatar"><img src="[^"]+" alt="[^"]+" /></a>
	发给<a href="[^"]+">[^"]+</a>：
	<span class="content">海内的像片是真的。</span>
	<span class="stamp time" title="2008-05-28 20:24">2008-05-28 20:24</span>
	<span class="op"><a href="/privatemsg.del/576827" class="post_act">删除</a></span>
</li>

这与“我收到的私信”的结构完全一致，只是将原来的“来自”改为“发给”而已。

不出意外，带有“回复原文”的“我收到的私信”的结构是这样的：

<li>
	<a href="/([^"]+)" title="([^"]+)" class="avatar"><img src="[^"]+" alt="[^"]+" /></a>
	发给<a href="[^"]+">[^"]+</a>：
	<span class="content">在自述部分显示的那个网上。</span>
	<span class="stamp time" title="2008-05-29 17:00">2008-05-29 17:00</span>
	<span class="op"><a href="/privatemsg.del/579918" class="post_act">删除</a></span>
	<p class="pm-parent">回复原文: 我也要试一试。</p>
</li>

我们从饭否私信代码上得到的信息就这些。遗憾的是，饭否私信中，关于“回复原文”是以明文内容形式出现，而不是以原私信ID的形式出现。后期处理时通过搜索功能解决此问题并非不能，只是如果饭否官方能够再将此功能完善的话，会省整理者不少力气。

饭否的私信源码分析完毕。至于如何读写cookie，如何写代码，如何以数据库的形式来管理下载的数据，是第二阶段的事情了。待我一一实现。

, ,

精通正则表达式中文第三版到手

May 16th

Posted by rex in 杂项

No comments

今天收到从淘宝上买来的《精通正则表达式》：第3版（中文版），感觉很爽。加上之前购买的精通正则表达式：第2版（影印版），手头就有两本正则书了。之前那边英文版可是“韦编三绝”，被我读得破破烂烂的了。
,

Hello regex world!

Apr 22nd

Posted by rex in 杂项

7 comments

2008年4月24日，一个普普通通的日子，iregex.org我爱正则式博客低调开张了。使用的平台是wordpress，面向的受众是对正则式有好感或即将有好感的网友。如果您了解并喜欢正则表达式。如果您不了解、不喜欢正则表达式。

什么是正则表达式？如果您在dos中使用过*和?这两个通配符，那你就理解一半了。正则表达式是一整套通配符。它可以像天书（貌似一堆无意义字符的组合），但也可以简洁高雅。它的作用是高效地搜索和替换字符串。与庞大的操作系统相比，它只是一个小零件。但是，这一零件的作用越来越为人所熟知，越来越不可或缺。

本站关注正则表达式。内容包括原创、转载、翻译与正则表达式有关的教程和应用文章。饭友ppip在自述中说，“因此我将坚持多原创、少转载、少翻译的原则，宁可显出自己的愚钝，也绝不借助于他人的头脑表达。”笔者欣赏这种注重提高自身修养的思想境界。但是本站的宗旨在于分享和交流，同时本人技术并非精尖，所以自矜的仅是对正则式的热爱和对技术的痴迷，因此本站会在坚持原创的同时，不排斥转载和翻译本主题的优秀文章，与各位regexers共享。本人也立志从一名regexer成长为regexist，并最终成为regex guru。

除了正则式，本站还会刊登与搜索引擎有关的文章。Google和百度改变了我们的学习、工作和生活。我们从一个信息贫乏时代跨入了信息泛滥时代。如何精准定位所需的信息，想必也是每位网友所关心的。

为了让更多的人了解、应用正则式这一好用的工具，本站还准备开设一个小型论坛（不日开放）已经列架设一个正则表达式论坛，专门用来为新手答疑解惑。首先应该声明的是，本人对于正则式只是叶公好龙，愿意组建平台并抛砖引玉，对于新手的问题知无不言言无不尽；更高深的问题，还望诸多大牛现身赐教；在讨论中相互促进，在解惑中得到提高。

本站的域名为iRegEx.org，i可以理解为I，自己，也可以理解为中文的同音字“爱”。RegEx当然是正则式的意思了。.org是非赢利性组织域名，而非.com。旨在聚拢尽可能多的同道中人，而不是攫取尽可能多的利润。当然，如果本站将来做得足够好，流量足够大，亦不排除出售广告位来达到维持平衡的可能性。我正则，爱正则，我爱正则！

做一个与正则式有关的网站，是本人的一个愿望。现在，这是得偿夙愿的开始。我想以一副长联作为本篇开场白的结语。该长联是本人在饭否上写的“自述”:

◆匹配文本，管它字母数字一次多次懒惰贪婪行首行尾，火眼金睛疏不漏
◆替换字串，任尔局部全局单行多行前瞻回顾大写小写，偷梁换柱度陈仓

希望各位网友多支持“我爱正则式”，多订阅，多评论。谢谢大家。

Page 1 of 11