Oracle提供了一个非常好用的关键字rownum，可以限制结果集的大小。
MySQL也提供了相同的功能，写法略有差别。

Usage:
Select clause
[LIMIT [offset,] rows]

In Oracle
select * from table1 where rownum <= 2;

In MySQL
select * from table1 limit 0,2;
or
select * from table1 limit 2;

看翻译的文章，时常会感觉很别扭，没有原文，随便举两个典型：

“他是如此的生气，以至于说不出话来”
这不是中文！
“他气得说不出话来”
“他的火气太大，连话都说不出来”。

“直升机的偶然闯入，使这张照片成了一幅大师级的佳作”
不好，不喜欢。
“直升机的偶然闯入，造就了一幅大师级的佳作”
“偶然闯入的直升机，成就了这幅大师级的佳作”

语言是很复杂也很精妙的东西，需要译者用心去体会，去捉摸。
一般认为，不同的语言中，不存在完全相等的词汇和概念；既然如此，照着模式硬译，多少有偷懒的嫌疑。

在软件开发中，时常会遇到这样的情景：客户或程序需要数据库的多个实例（Instance）。有时，这些实例需要安放在同一位置，以增强负载能力和可靠性；有时各个实例需要分布在不同的地点，提供大范围的服务。无论是那种情形，都需要由多个实例提供相同的数据，DBMS解决这种问题的方案有很多，Replication技术其中之一。

Master & Slave

不同的DBMS对replication的定义不尽相同，但所有的定义都将replication分为两方：一方提供数据，叫做Primary database；另一方接收数据，叫做replicator。在MySQL中，前者称为Master，后者称为Slave。

Sychronized & ASynchronized

按照机制的不同，replication可分为两类，一类为同步复制（synchronized replication），另一类为异步复制（asynchronized replication）。
在同步复制中，客户端事务（Transaction）的提交（commit）是对所有服务器进行的，也就是“双重提交”（dual commit）或者“双阶段提交”（dual phrase commit），只有对所有服务器的commit操作都正确完成后，事务才算结束。

同步复制

在非同步复制中，客户端事务的提交只对primary database进行，事务结束后，由单独的进程负责将修改复制到所有replicator。

非同步复制

One-Way & Merge

按照策略的不同，replication可以分为One-Way replication和Merge replication。在One-Way replication的情况下，Primary database是固定的，所有的数据操作都在Primary database上进行，再单向复制到其他所有replicator；在Merge replication情况下，Primary database不是固定的，对任意一个实例的操作，都可以“扩散”到其他所有实例。

Replication的理由

Replication可以提高性能，将负载分布到数据库的多个实例上；
Replication可以提供地理分散性，为不同地域的用户访问提供更好的体验；
Replication也可以提供冗余和备份的能力。

MySQL的Replication

作为开源数据库的MySQL，也提供了对Replication的支持（不过只支持ASynchronized，One-Way的replication）。它的实现机制大概是，Master将所有修改数据的操作记录下来，生成二进制记录（BinaryLog），Slave连接到Master之后，获取BianryLog，执行同样的操作，对数据进行同样的修改。

实现MySQL的Replication比较简单

首先，需要确认不同MySQL版本之间Replication的兼容性：

		Master	Master	Master
		3.23.33 and up	4.0.3 and up or any 4.1.x	5.0.0
Slave	3.23.33 and up	yes	no	no
Slave	4.0.3 and up	yes	yes	no
Slave	5.0.0	yes	yes	yes

基本规律就是，低版本的Master可以兼容高版本的Slave（向后兼容）。

确认可以进行replication之后，在Master上为Slave创建访问帐号，赋予这个帐号replication权限
mysql> GRANT REPLICATION SLAVE ON *.*
    -> TO ’slavedb’@'%’ IDENTIFIED BY ’slavepass’;

然后修改配置文件，在linux/unix下修改my.cnf，在windows下修改my.ini，在[mysqld]下增加如下内容

#生成的bin-log名
log-bin=mysql-bin
#服务器的标识，replication system中的每个数据库实例应该有唯一的标识
server-id=1
#根据MySQL的文档，如果使用InnoDB，推荐添加这一行
innodb_flush_log_at_trx_commit=1
#启用binlog
sync_binlog=1
#BinaryLog中需要记录的database名
binlog-do-db=test
#BinaryLog中不需要记录的database名
binlog-ignore-db=manual,mysql

重新启动Mysql，登录之后输入以下命令：
mysql> FLUSH TABLES WITH READ LOCK;
mysql> SHOW MASTER STATUS;

此时，database已经锁定不能修改，可以看到当前的Master状态
+—————+———-+————–+——————+

| File          | Position | Binlog_Do_DB | Binlog_Ignore_DB |

+—————+———-+————–+——————+

| mysql-bin.003 | 73       | test         | manual,mysql     |

+—————+———-+————–+——————+

记录下File和Position的值，再输入
mysql> UNLOCK TABLES;

解除锁定（因为我们已经记录了此时的File和Position，Slave会首先恢复到锁定时的状态，再复制之后的更改）。

接下来，把Master的数据复制到Slave上，可以直接拷贝数据文件，也可以用mysqldump实现。

修改Slave上的MySQL配置文件，同样是在[mysqld]下增加如下内容

#本实例的标识
server-id=2
#打开log-bin
log-bin=1
#打开log-warnings
log-warnings=1
log-slave-updates=1
#需要复制的database名
replicate-do-db=test
#Master的地址
master-host=192.168.0.1
#Master上的帐号
master-user=slavedb
#密码
master-password=slavepass

重新启动MySQL，输入以下命令
mysql> CHANGE MASTER TO
    -> MASTER_HOST=’master_host_name’,
    -> MASTER_USER=’replication_user_name’,
    -> MASTER_PASSWORD=’replication_password’,
    -> MASTER_LOG_FILE=’recorded_log_file_name’,
    -> MASTER_LOG_POS=recorded_log_position;
前三项都与配置文件中的相同，LOG_FILE与LOG_POS就是首先锁定MASTER时保存的记录。

最后，敲入
mysql-> start slave;

启动slave进程，replication就告完成。在Master上对需要复制的表进行一些修改，过一会儿，Slave上的数据应该也会发生同样的变化，这说明repliation已经生效。

我试验时，Master和Slave的版本均为MySQL 5.0，操作系统都是Windows，测试成功。

Update:
注意，如果Master和Slave的COLLATION_SERVER变量不同，Slave不会报错，但Slave_IO_Thread不会启动，这个问题很迷惑人。
输入
show variables like ‘collation_server’;
可以看到当前MySQL的COLLATION_SERVER
如果Slave的COLLATION_SERVER与Master不同，解决办法是：
停止Slave进程，修改Slave的my.cnf文件：
#本例中Master使用UTF8的Charset和Collation_server
[mysqld]
character_set_server=utf8
collation_server=utf8_general_ci
重新启动，即可。

在PHP5以前，使用date相关函数的时候，并不需要考虑时区的问题，获得的就是本地时间。
但是，在PHP5种，使用date相关函数，只能获得UTC（格林尼治天文台的时间），很不方便。
根据偏移值处理字符串的解决办法，并不能令人满意，而且很繁琐。
其实，要解决这个问题，只需要在php.ini中修改
date.timezone = PRC;
并把date.timezone之前的注释符 ; 删掉，就好了。

出租车涨价的话题，最近越来越热门了，关于出租车行业种种黑幕的探讨，又一次吸引了人们的目光。我的朋友郭玉闪，一直在关注和研究出租车行业的问题，他的观点，取消价格管制和数量管制的建议，我都很赞同。而且，我认为，他也做了充分的论证。

倒是下面这点出自张维迎教授某位学生笔下的文字，让我觉得匪夷所思——不仅仅是观点，更重要的，是论证似乎根本不成立。

出租车司机都知道，涨价以后，客流会直线下降——各种媒体对乘车人群的调查，也显示了这一点。这个现象很好解释：在市场经济条件下，供给和需求都是可变的，所谓供给与需求之间的平衡，是一种动态的平衡。一般认为，依靠看不见的手，未必能实现完美的均衡，但至少可以保证均衡的趋向。换言之，市场虽然不能保证供给和需求的完美平衡，但需求增加，一般来说，供给是会相应增加的。
如果硬性选择一定的需求（或供给）为既定条件，把目标定为增加供给满足这种供给（或需求），就必须引入强制。这样的做法，一般是违背市场原则的，但并不少见，一般表现为某种“公益事业”，例如为全民提供义务教育，这时候往往需要引入某种类型的强制。
理解了这一点，就不难明白文章概括的“出租车服务特性”存在的问题：如果按照作者的说法，“正由于这几个特性，出租车不能像其他产品一样，仅靠看不见的手就能保证足够量的供给”，需要引入强制，也就等于说，出租车行业，具有某种“公益事业”的性质（实际上，看作者开头的论述，可以认为他确实认可这种性质）。
可是，承认这一点，整个文章就显得很荒谬了——一项具有“公益事业”的性质，居然不需要政府的任何投入，反倒是从业人员需要向运营公司和政府上交不菲的“份钱”，而这些钱还是来自事业的服务对象，也就是受益人，这简直是匪夷所思！让环卫工人向环卫单位上交份钱，让教师向教育局上交份钱，这样做，不是很荒谬吗？

接下来作者从几个方面论述了他的“方案”——也就是，数量管制、特许经营——的合理性。

第一是数量管制，但是，很遗憾，我把数量管制的这一段看了好几遍，也不觉得这是一个成功的论证。既然作者也知道放开数量管制，出租车市场不会无限膨胀，为什么又认为，只有数量管制才能保证出租车数量不会无限膨胀呢？上限或许是必须的、存在的，但管制，并不是实现这个目的的唯一途径。
第二是份钱有激励司机的作用。这个论证更糟糕了，如果固定成本能够激励员工工作的话，我们岂不是可以说，各行各业，都要收取“份钱”，收取这种“固定成本”，能够最好的激励员工？
第三是特许经营保证了出租车公司的利益，逼迫司机多干活，同时政府也得了好处。这一条也很糟糕。特许经营相当于提高了出租车的行业门槛，我们都知道，这种对垄断企业的保护，必然是以损害消费者利益为代价的。这样一来，逻辑的结论就是，特许经营，净收益者是垄断公司和政府，利益受损者是司机和消费者，当然，司机如果多干活，或许能弥补一点消费者的损失？

还有一点我一直没有弄明白，为什么这位作者的脑子里，只有“既存的出租车公司”和“个体”两种选择？既然大公司存在有诸多好处，难道放开管制之后，不会有人成立公司，个体不会自发地形成公司么？这样成立的公司，不是比目前那些敲骨吸髓的公司，要好上一千倍，一万倍么？

---

 出租车服务的经济特性就是：（1）运力不能存储，昨天空着就白空着了，不像别的
产品可以有库存；（2）司机乘客谈判地位随时变化，具体到局部时间局部地点，只要
再开来一辆出租车或者新来一拨乘客，双方的谈判地位马上就变了；（3）市场不同
质，时空分布不均匀，有的地区打车人多、车也多，有的时段打车人多车却不好打；
（4）消费的峰谷特性，不同季节和每天不同时段需求不一样，这和运力不可存储又紧
密相关；（5）消费的瞬时性，只要我想打的时候有车打就行了，我不想打的时候车再
多也没意义；（6）司机的企业家才能，司机可以灵活选择工作时间、地点，可以选择
空驶还是阶段性停运，比如停在路边睡觉下棋。

 我给出租车行业提的目标是，居民只要想打车，等几分钟后就可以打到车，就是居民
可以随时享用服务，换言之，某种意义上要具有普遍服务义务。

 正由于这几个特性，出租车不能像其他产品一样，仅靠看不见的手就能保证足够量的
供给。比如你要买彩电，今天买不到明天买，北京没有的话从外地调过来。出租车不一
样，想打的时候没打到，不想打的时候车再多也没用。

 说白了，出租车是一个解决燃眉之急的服务，必须随时用近水解决近渴。

 我用的是张维迎“资本雇佣劳动的分析逻辑。两个司机，一个交份钱，一个不交，哪
个会多开车？显然是交份钱的那个更容易让人相信。他交的份钱就是一种抵押或担保，
就是告诉大家我每天至少会开几个小时，你们肯定有车打。

 下边的内容是我2次和玉闪讨论的内容。看着你们讨论好玩，我再给你们发一遍。

 出租车为什么要特许经营

 我最近比较忙，没时间细想，书读得也比较少，只是胡乱解释一通。

 假如出租车司机不交份钱或者少交份钱，出租车司机会怎么做？经济学上有一条工资
与工作时间的曲线，在一定工资水平下，提高工资工人愿意多劳动，结果就是会增加劳
动总量或者劳动供给。超过了某个工资水平，提高工资工人反而不愿意多劳动，结果就
是会减少劳动总量或者劳动供给。这个理论肯定也适应出租车司机，不管出租车是公司
还是个体。

 政府在出租车业的目标是什么，是提供充分的出租车服务供给，方便居民出行或者说
方便居民随时打车，而且要保证服务质量。出租车服务供给=出租车数量×每车每天服
务时间。要想实现这个目标，无非几个办法：（1）增加出租车数量；（2）激励司机每
天多开车、时间越长越好；（3）混合使用这两种方式。

 一、出租车数量

 假如没有特许经营，谁想干谁干，出租车数量会怎么样？出租车数量会无限多吗，不
会，因为拉不到活，跟其他工作机会相比，干出租车不划算。尤其是其他交通方式（地
铁）很方便时，出租车更是拉不到活。再加上私家车的增多导致交通拥挤，干出租车不
划算。

 给定一个城市人口经济现状，肯定有一个出租车数量的上限，数量管制可能高于这个
上限也可能低于。比如北京市，最多有10万辆出租车，再多了就有人退出了。数量管制
可能是8万辆，也可能是12万辆。

 二、激励司机每天多开车

 大家都说司机是企业家。怎么保证让司机每天多开车呢。现在的份钱就是一个很好的
制度，司机一睁眼就欠钱，干不够时间挣不到钱。份钱太高的话，司机怎么干都是低收
入，肯定不合适，司机用脚投票转行了。份钱太少，司机随随便便就是高收入。如果没
有特许经营，相当于份钱为0，开出租车收入高的话，大家都干出租车了，收入也高不
了。

 从出租车司机的角度来看，每小时的成本是不一样的，因为每多干一小时，对身体的
伤害要比前一小时大。假如每小时收入一样（因为有峰谷，不可能一样，但不影响分析
结论），第一小时利润最高。每小时收入递减。每天越往后，越不划算，总有一个均衡
点，比如第七个小时的时候达到均衡。（均衡点是动态的，取决于好几个因素。）对司
机来说，份钱是固定成本。每天必须要工作一定的时间，才能把份钱收回来。这就跟卖
东西一样，必须卖够多少个了才能不亏本。

 份钱高了不行，低了也不行，要有一个均衡，目前大家争得也就是均衡在哪里。假如
司机每月只交200元份钱，司机都偷着乐了，司机根本不抱怨。现在的问题是，司机觉
得3900高了。

 三、特许经营的功能是什么

 （1）限制出租车的数量，减少竞争，这是在保护出租车（或出租车公司）的利益
（和司机的利益不是一回事）。如果觉得出租车数量不够多，发牌照增加数量。具体数
量管制怎么来定，我不知道国外怎么定的，也不知道背后的原理是什么，但至少在老百
姓抱怨打车难的时候可以增加。

 （2）提高了出租车公司的谈判地位，把司机弄得半死不活，司机就每天多开车了。

 （3）政府的目的实现了，但是钱别都让出租车公司赚走，政府收点特许经营费来
“分肥”。

 区别个体和公司，在理论上差别不大，个体就是小公司嘛。

 我们可以举出一大堆理论来说明管制俘获怎么坏、怎么寻租。在执行的过程中，肯定
和目标有偏差，也肯定会有很多问题，但我们要看到本质，就是怎么保证足够数量的供
给。

 我不知道是否表述清楚了。请提提意见，或者帮忙找找逻辑上的漏洞，看看有没有可
能做一个模型出来。


 大致浏览了一下玉闪的报告，提点讨论意见。我自己没有研究体系，也没花时间研究
过，只是就是论事。

 1、我们的目的是推进改革还是理论研讨。如果是想推进改革，我们就要找具有可操
作性的方案。我们先提出各方基本都能接受的方案，然后推动政府把出租车改革列入工
作计划和议事日程，然后和利益集团合谋共同推动。如果我们只是想自己过嘴瘾，提的
方案根本不具有可操作性、提完了白提，还不如在家休息，至少不浪费听众的时间。

 2、出租车公司、司机可以用商场、商场出租柜台来做类比，（1）你可以自己开商场
（专卖店），（2）也可以开一个大商场、然后把柜台租出去，（2）也可以自己开大商
场、自己经营柜台。为了简化问题和形象化，可以拿鸡蛋市场来简单类比。

 3、假如个体化而且没有数量管制，司机高收入（按照玉闪的算法、司机可以得4千
多）的结果是更多的司机进入，空驶率提高或者价格下降，结果就是司机收入会下降到
现有水平（现在被公司“盘剥”都不退出，说明现有水平可以忍受，每天十三个小时月
收入两千）。此时油价上涨，司机怎么消化？两种结果：1、还得涨价，2、部分司机退
出、空驶率降低。

 4、数量管制并不排斥高企业家才能的司机替代低企业家才能的司机，低的可以卖给
高的啊，反正自己开也多赚不了，何不以稍高一点的价格卖出去呢。这个道理，想想以
前的批文就知道了。再想想经济学的比较优势理论。现在的公司制，恰恰是转让的结
果，我自己雇司机开没有我把数量卖出去赚的多（我开大商场自己经营柜台，不如把柜
台出租），所以我卖了。

 5、如何看待价格管制，报告的意思似乎是不要价格管制。其仁有篇文章，说出租车
最好一个车型一个价格，否则乘客挑车导致空驶率提高。假如乘客可以和司机侃价，缔
约后机会主义行为将大大增加，比如乘客上车的时候有5辆出租车在等客，乘客可以把
价格压得很低，一旦上路，司机觉得亏了，司机要么饶路、要么重新谈价格，否则把乘
客扔半路上。乘客投诉是要讲证据的，这个证据根本不会有。你强制装摄像头的话，司
机可以把摄像头弄坏。

 6、对于政府打击黑车的评价，我觉得报告可能只注意到了一方面。恰恰是出租车司
机最希望政府打击黑车，出租车公司反倒无所谓（坐收份钱就行了）。

 7、质量管制根本就无从谈起。假如采用个体化+质量管制，结果会怎么样呢。结果就
是乘客实际得到的质量只比政府设定的最低质量高一点点。提供高质量服务的司机可能
反而被淘汰了。因为出租车几乎没有回头客，高质量必然对应着高成本：1、成本可能
体现在时间上，比如司机增加汽车保养时间；2、乘客在上车事前哪知道司机会不会绕
路呢，司机脑门上又没写。也可能司机争着洗脸穿好衣服、擦车换坐套。

 8、出租车公司是一个品牌，比如我印象中银建公司不允许司机拒载，我坐的经历好
象司机很少讲脏话骂人。个体化之后，我如何相信出租车司机呢。

 9、按照玉闪报告同样的道理，公交车也可以采用玉闪建议的改革方案。我们想想公
交车个体化后会怎么样，我自己是受够个体公交车的苦了。

 10、最后，我们再来分析一下现在的黑车市场，基本就是玉闪主张的取消数量管制和
价格管制。黑车市场基本上可以自由进入自由退出、价格也可以自由谈，安全方面稍微
差点也关系不大。与其我们精心设计2套方案，不如我们建议现在的出租车司机都去跑
黑车算了。出租车公司一看司机都跑光了（都跑黑车了），按照报告的逻辑，出租车公
司会和司机商量新的合作方式。

米兰·昆德拉的《身份》里，有这样一段文字（大意）：
……
她感到那些时光被一把无形的扫帚轻轻地扫去了，没有留下任何痕迹，如同被截去了小臂，手腕径直接在大臂上
……

第一次读到这些文字的时候，我已经没有勇气，也没有心情，继续下去了。

这世界，鸦雀无声，同时又热闹非凡，让我感到很正常，又很不正常。我甚至都怀疑，所谓“噤若寒蝉”，是真的么？抑或是刻意的忘却，无论是主动的，还是被动的；无论是有意识的，还是无意识的。

有时候我在想，倘若真的就这样过去，就这样忘却，或许也不是什么坏事。可是，盲动、狂暴、极端的因子，其实依然潜藏在我们身边，或许，就潜藏在我们每个人的心底；没有见识，没有历史，没有教训，大概就真的不知道该怎样克制，怎样面对。
这几年发生的许多事情，我看来，都脱不了似曾相识的影子，那是《八九点钟的太阳》里出现的过的影子，是《乌合之众》中描绘过的影子。

马克思说，历史必定要上演两次，第一次是悲剧，第二次是讽刺剧。
世界果真是如此可悲么？
甚或，要继续不停的上演第三次，第四次……

索尔仁尼琴在《古拉格群岛》里的话，应该也适合我们：
▲惩罚自己的恶人的机会为了什么给予了德国，而俄国却未能得到？如果我们永无清除在我们体内腐烂的秽物之日，那么我们将面临一条怎样的绝路？俄国将给世界做出什么样子？

p.s.
写这篇文章的时候，忽然想到，我们，其实如同《身份》里的女主角一样，只不过，我们被截去的是良心，剩下的是脑袋、脖子、肚子……

五一买了件衬衣，临到要穿了才发现某颗扣子有问题，看起来总是很别扭。无奈保换期过了，更要命的是，小票也不见了，没法，只好自己动手。

刚做了决定，问题就来了——这年头，去哪买针线呢？还是在家的时候好，找缝纫机抽屉里的针线盒就是了；买针线之类，印象中是去百货商店，可那都是老皇历了，如今的百货商店，连布都不卖了，何况针线；万般无奈之下，只好去附近的超市碰碰运气。

连着问了好几个超市服务员，都是一脸迷惘，准备打道回府了，忽然在一个柜台看到要买的东西——一个塑料盒，盖子里稀稀拉拉的躺着几根针，盒子里一圈各种颜色的线，每种都是薄薄的一卷，看起来就很不结实。一打听，还要五块钱，真贵啊！

旁边还有单个的线卷，一块钱一个。我都不记得上一次买线是什么时候了，只记得五毛钱买了一大卷，物价飞涨，物价飞涨啊。
于是决定只买一个线卷，好说歹说，让售货员送了我一根针，据说，她们得自备一些针线，发现卖的衣服有问题，可以自己缝补缝补。

把这一切告诉Patrick的时候，得到如下评价：你真是个鬼毛男！
这家伙，话虽这么说，周末去中关村买音箱的时候，还得拉上我——理由是，“你会砍价些”。

问题是，我其实挺烦砍价的。
：）

他指出：“我们一方面要给予台湾支持，另一方面又不能鼓励那些倾向独立的人。让我说清楚：独立代表战争，也代表美国军人的参与。”

VS

他说，“我们一方面要对台湾给予支持，另一方面又不鼓励一些人企图走向台湾独立，因为台湾独立就意味着战争，”而这又意味着美国士兵可能会因此丧生。

网络上介绍正则表达式的文章汗牛充栋，本文则试图对regex的原理做深入一点的探究。
不当之处，望各位读者不吝指出。

---

要深入了解正则表达式，必须首先理解有穷自动机。

有穷自动机（Finite Automate）是用来模拟实物系统的数学模型，它包括如下五个部分：

• 有穷状态集States
• 输入字符集Input symbols
• 转移函数Transitions
• 起始状态Start state
• 接受状态Accepting state(s)

下图为一台有穷自动机


可以看到，该自动机包含四个状态q0, q1, q2, q3，两个输入字符a, b，转移函数如图所示，起始状态为q0，接受状态为q3。

有穷自动机，按照转移函数的不同，又可分为确定型有穷自动机（Determinism Finite Automate, DFA），与非确定型有穷自动机（Non-determinism Finite Automate, NFA）。
非确定有穷自动机容许转移函数不确定，换句话说，对任意状态，输入任意一个字符，可以转移到0个，1个或者多个状态。
下图是一台非确定有穷自动机，可以看到，对状态q0输入字符a，既可以转移到q0，也可以转移到q1，这就是“非确定”的意义所在。



对某个自动机来说，如果从起始状态，接受一系列输入字符，可以转移到接受状态，即认为这一系列字符可以被自动机接受。

如果两台自动机能够接受的输入字符串（或者叫做“正则语言”Regular Language）完全相同，则这两台自动机是等价的。
可以证明，对于每一个非确定有穷自动机，都存在与之等价的确定型有穷自动机（证明略）。

正则表达式就是建立在自动机的理论基础上的：用户写完正则表达式之后，正则引擎会按照这个表达式构建相应的自动机（可能是NFA，也可能是DFA，但它们必定是等价的），若输入一串文本之后，自动机抵达了接受状态，则这串文本可以“匹配”用户指定的正则表达式。

下面是同一个正则表达式 a|ab 对应的NFA和DFA

在Mastering Regular Expression中，Friedl首先分析了NFA和DFA的区别，DFA比较快，但不提供Backtrack（回溯）功能，NFA比较慢，但提供了Backtrack功能。
在分析两种引擎的匹配过程时，Friedl指出，NFA是基于表达式的（Regex-Directed），而DFA是基于文本的（Text-Directed）。
举例来说，对于正则表达式 to(nite|knight|night)，NFA在匹配最开始两个字符（to）之后，剩下的三个组件（component）是 nite, knight 和 night，于是正则引擎会依次尝试这三个选择分支（每次尝试一个）；而DFA在匹配最开始两个字符之后，会将剩下的三个选择拆分作字符，并行尝试，也就是说，匹配 to 之后，先匹配 k 或者 n ，如果 k 不能匹配，则放弃 knigth 所在的分支，再匹配 i ，再匹配 t 或 g ……这样继续下去，直到匹配结束。

不幸的是，Friedl对匹配过程的分析，是完全错误的——引擎的不同，是指构建的自动机的不同，而不是匹配算法的不同！
DFA引擎在任意时刻必定处于某个确定的状态，而NFA引擎可能处于一组状态之中的任何一个，所以，NFA引擎必须记录所有的可能路径（trace multiple possible routes through the NFA），NFA之所以能够提供Backtrack的功能，原因就在这里。
传统的NFA匹配算法是带回溯的深度优先搜索（backtracking depth-first search，就是上文所说的Regex-Based过程），而新的PCRE算法提供了效率更高的广度优先搜索，可以同时保持所有可能的NFA状态（请参考http://www.cl.cam.ac.uk/Teaching/current/RLFA/，尤其是Lecture Notes的section 2.2）。

Friedl的错误就在这里，他混淆了应用PCRE算法的NFA与DFA的匹配过程。
需要指出的是，即使应用PCRE算法，NFA的速度仍然低于DFA，这是由NFA需要同时保存多种可能的性质决定的。从理论上说，如果我们不需要应用Backtrack，完全可以从NFA构造出等价的DFA，再进行匹配，这样能大大提高速度——代价是，DFA需要更多的空间。

MIT版画风波里面，教授给中国学生的公开信里有一句话，非常有意思：

Many of you, I am sure, plan to return to China to use the skills you learn here to help China become a truly modern country.

truly是非常有意思的词，我见过的翻译，大都翻译成“真正的"，不过，如果是我，我会翻译成”名符其实“的


P.S.
转贴一段文章

老冷

山中方一日，世上已千年。我出差一周回京，接到朋友来信，说起MIT的画报事件，到网上一查，原来已经和超级女声一样时髦。接着又在往复看到施琅引起的争论。不能不感慨：爱国者真多呀。

既
能主持《原道》、又能到深圳挣钱的陈明说：“我一直关注钓鱼岛和台湾岛这些问题，因为成年后我发现对自己思想行为影响最深的就是阅读中国近代史留下的记
忆。我记得自己十几岁时就写过记述当时心情的‘七绝’，有一种‘收取关山五十州’的悲愤与豪迈。”这当然不仅仅是一种近代湖湘小士人的幼年激情，事实上，
到今天，陈明的激情不仅没有衰减，还在继续升温：“如果我知道将孤悬海外的台湾岛收归版图需要一个施琅这样熟谙水战的军事将领而我又具备这样的素质的话，
我就会投笔从戎去征战澎湖！”只有悲壮使人如此豪迈，只有爱国使人如此悲壮。

李泽厚说陈明这是“生物本能，……实际上就是在情绪冲
动的主宰下”，但他没有说这种本能是什么。这种本能不是像食色那样与生俱来的本领，而是后天教养的结果。国家图腾，国家崇拜，国家宗教，在传统中国已经高
度发达，进入近代以后更加登峰造极。爱国成为最高价值，绝对价值。人消失了，地区消失了，惟有国家矗立着。而爱国者所爱的国是什么呢？国家由什么体现、由
谁代表呢？爱国者顾不得想这个。

我读了李泽厚答记者问，再读号称与李泽厚有忘年之交、曾因与李泽厚对话而闻名的陈明的言论，深感历史之倒退。

记
得89年初（也许是88年？）报纸和电视上报道国家最高领导人对外国记者说，这些年的失误，主要是教育上的失误。当时这句话引起许多人的赞美，并引发对于
教育改革的联想。可是一年多以后（可能更短些），他又说：教育的失误，主要是思想政治工作的失误。这么多年过去了，看看今天爱国者的众多，你不能不承认思
想政治工作是可以而且事实上是极为成功的。

MIT校方就画报事件的声明里说：“学校，乃是提供探索思想之自由的圣殿，包容智慧与文
化之多样性的汪洋大海（the very essence of the university as a place for the free
exploration of ideas and the embrace of intellectual and cultural
diversity）。……如果我们期望从历史中学习，我们需要能够直观历史中艰难时刻的勇气（We need to preserve the
ability to confront the difficult parts of human history if we are to
learn from them）。”爱国者听得懂这样的警示吗？