最近在开发 网络风行者（参见我的博客文章：《Web风行者的设计方案与计划》，《网络风行者（KSpider）的规则体系结构》）的 Web 版，与《Web风行者的设计方案与计划》 中不同的是，新版本采用C#/Asp.Net开发，Web页面解析引擎采用的是 HtmlAgilityPack。开发思想遵照 《网络风行者（KSpider）的规则体系结构》 一文。新版名字改名为 OrcSpider网络风行者，Orc代表兽族的英勇和嗜血。
现有的网络数据提取程序采用的提取规则主要是正则表达式匹配提取，《网络风行者（KSpider）的规则体系结构》一文中的规则是基于树的匹配，在直观性、规则的柔性、规则的制定成本上有很大的优势。树匹配在技术上存在难点，难点主要在于多节点匹配算法（关于节点匹配，参见《网络风行者（KSpider）的规则体系结构》），描述如下：
规则节点列表由一系列有序的规则节点组成，记为 P[P1,P2,…Pm]，给定一个内容节点系列N[N1,N2,…….Nn]。要求在N中查找满足P的内容节点系列。
举例说明，以cnblogs为例（例子猥琐了点，dudu勿怪，俺本世纪以来爬cnblogs页面数在10次以下）：
首页的标签结构摘录如下：
…
<
H3
>
<
A
HREF
>
</
A
>
</
H3
>
<
H4
>
<
A
HREF
>
</
A
>
<
P
CLASS ALIGN
>
<
A
HREF CLASS
>
</
A
>
<
A
HREF CLASS
>
</
A
>
</
P
>
</
H4
>
<
H3
>
<
A
HREF
>
</
A
>
</
H3
>
<
H4
>
<
A
HREF
>
</
A
>
<
P
CLASS ALIGN
>
<
A
HREF CLASS
>
</
A
>
<
A
HREF CLASS
>
</
A
>
</
P
>
</
H4
>
…
可以看出一个规则节点系列：
<
H3
></
H3
>
<
H4
></
H4
>
这一系列代表的是首页的一篇文章。
对于页面节点的子节点列表，采用上面规则节点进行递归匹配，就可以找出页面上所有的文章。
为了让规则使用更广泛，对于规则节点，可引入通配符*,+,?，*代表0个或多个匹配，+代表1个或多个匹配，?代表0个或1个匹配，比如，这样的规则P[P1+,P2?,P3*]，代表匹配的节点列表必须依次为1到多个满足P1的节点，0到1个满足P2的节点，0到多个满足P3的节点。
这个问题和字符串的正则表达式匹配是同类型的问题。为了解决这个问题，俺是跋山涉水啊，翻山越岭啊。先是刨出了java的正则表达式匹配部分代码，近10000行，一堆内部类，吓的俺倒吸一口气。到 sourceforge 查询正则树相关开源程序，只找到一个 C 语言版的，它自定义了一堆语法，文档看的俺头昏。没办法之下，自己手写，边写边测试，改bug，写是写出来了，测试也没问题，只是程序的可读性太差，添加新规则的测试量巨大。
二、解决方案
分析节点列表匹配和字符串匹配的相同点，可以巧妙的借助字符串匹配来解决节点列表的匹配问题。
字符串匹配问题可表述为：给定一个正则表达式R，从字符串S[C1,C2,…,Cn]中找出符合的所有子字符串。
可以将内容节点等同于字符，将规则节点等同于字符集。用Cni表示 内容节点Ni所对应的字符。用Pi{Ci1,Ci2,…}代表一个规则节点，其中{Ci1,Ci2…}代表规则节点能匹配字符的集合。Cnext为下一个未分配的字符。存在大量的内容节点，这些内容节点和任一规则节点都不匹配，这样的节点统一记作一个字符C0，以节省字符使用量。
在 N[N1,N2,…….Nn] 中查找 P[P1,P2,…Pm] 的算法如下：
第一步：为P1……Pn各分配一个字符：P1{C1},P2{C2},….Pn(Cm)；
第二步：遍历N，对于Ni：
（1）如果P1…Pm均不能匹配Ni，则将字符C0分配给Ni；
（2）如果P1…Pm中只有一个能够匹配Ni的规则Pk，则将字符Ck分配给Ni；
（3）如果P1…Pm中有多个能够匹配Ni的规则，则给Ni分配一个新字符Cnext，同时将Cnext加入每一个能够匹配Ni的规则的字符集中。
于是节点串匹配问题归结为字符串匹配问题：
规则 : (C11|C12|…)(C21|C22|…)……(Cm1|Cm2|…)
字符串 : Cn1Cn2Cn3…Cnn
通过正则表达式匹配，可以得到一个Match列表，根据Match的index 和 length 可以取得匹配的内容节点列表。
鉴于需要分配的字符不定，就将第一个需要分配的字符定义为\u0000，依此向上加即可。
在这个算法架构基础上，引入通配符是再简单也不过了。引入其它正则表达式语法也是举手之劳。
本文转自xiaotie博客园博客，原文链接http://www.cnblogs.com/xiaotie/archive/2007/07/19/823639.html如需转载请自行联系原作者
xiaotie 集异璧实验室(GEBLAB)
