正向推理规则引擎中的Rete模式匹配算法研究

魏毅峰 (郧阳师范高等专科学校数学与财经系，湖北 十堰 442000)

正向推理规则引擎中的Rete模式匹配算法研究

魏毅峰 (郧阳师范高等专科学校数学与财经系，湖北 十堰 442000)

规则引擎技术是专家系统中的一种比较实用的技术，它的核心算法是Rete模式匹配算法。深入研究了被广泛应用于正向推理规则引擎中的Rete模式匹配算法，对Rete网络的构建和Rete算法的执行全过程进行了详细分析。

规则引擎；正向推理规则引擎；Rete模式匹配算法

Rete算法的核心思想是通过在内存中维护一个极其复杂的数据结构Rete网络来保存中间匹配结果，以达到显著减少计算量的效果，即牺牲内存空间来换取运行时间。Rete网络的构建主要是基于规则的LHS有很大的相似性的这个特点，通过保存规则的条件部分(也称为左端，即LHS, left-hand side)的各个模式的匹配结果，以便别的规则直接利用该模式匹配结果，可以极大地减少重复的匹配运算，从而达到提升模式匹配效率的效果。当前，大部分规则引擎产品的模式匹配算法，基本上都来自于Charles L. Forgy博士于1979 年在其博士论文中提出的Rete算法及其变体， Rete算法是目前在正向推理规则引擎中的效率最高的一个模式匹配算法[1-2]。下面，笔者对Rete网络的构建和Rete算法的执行过程进行了详细的分析。

1 Rete网络的构建

Rete算法在进行模式匹配时，是根据预先构建的Rete网络来进行的[1]。Rete网络的根节点是网络的入口，非根节点有2种类型的节点：Alpha节点和Beta节点。由Alpha节点组成局部网络称为Alpha网络，由Beta节点组成的另一局部网络称为Beta网络。每个非根结点都有一个存储区，用于保存模式匹配的中间结果。其中Alpha节点有一个Alpha存储区和一个输入口，Beta节点有左右2个存储区和左右2个输入口，左存储区也称为Beta存储区，右存储区也称为Alpha存储区。在Alpha节点和Beta节点中，Alpha存储区存储的都是一组事实Fact，Beta存储区存储的都是一组Token，其中每个Token由一个或若干个事实Fact通过join，select，projection等操作合并而成。事实Fact可以做为Alpha节点的输入，也可以作为Beta节点的右输入，Token节点只能作为Beta节点的左输入。每个Alpha节点或Beta节点都对应这一个模式，叶子节点则对应着某一条规则，因此从根节点到叶子节点的路径对应着该规则的LHS，当有Fact或Token被传递到一个叶子节点时，表示该规则的条件已经满足了，可以被触发执行。

Rete网络的构建过程如下所述：

1)创建网络的根节点，根节点是Rete网络的入口。

2)读取规则库中的一条规则，按照如下方式创建Alpha 节点和Beta节点到Rete网络中。其中Alpha节点从1开始编号，Beta节点则从2开始编号。①读取该规则的一个模式，检查该模式的模板类型，如果是新的模板类型，则创建一个子节点，作为代表这一模板类型的类型节点(TypeNode)。②检查该模式是否有对应的Alpha节点已存在，如果存在则记录下节点位置，否则添加一个新的代表该模式的Alpha节到网络中。③重复②直到该规则的所有模式都处理完毕。④按照如下方式创建Beta节点：Beta(2)的左输入节点为Alpha(1)，右输入节点为Alpha(2)；Beta(i)左输入节点为Beta(i-1)，右输入节点为Alpha(i)，其中igt;2。⑤重复④直到没有新的Beta节点需要创建。⑥将规则的执行部分封装成叶子节点，并且其输入节点为Beta(n)。

3)重复2)直到规则库中的所有规则都处理完毕。

2 Rete算法的执行过程

Rete网络构建完毕之后，推理引擎将开始进行匹配操作，即把事实库中的每一个事实Fact从Rete网络的根节点输入到网络中进行匹配。不同的节点处理输入进来Fact或Token所采取的策略也不同，下面是各个情况下的节点处理方法。

1)根节点的直接子Alpha节点也称为类型节点(TypeNode)，每个类型节点和一个事实模板一一对应。当有新的Fact输入到类型节点时，类型节点会判断该Fact是否和自身所代表的事实模板匹配，若匹配则把Fact保存到该节点的Alpha存储区中，并继续向后继子节点传递该Fact；否则该节点不采取任何动作，拒绝输入的Fact。

2)当Fact被传递到某个Alpha节点，该节点会判断输入进来的Fact是否和该结点所代表的模式相匹配，若匹配则把Fact保存到该节点的Alpha存储区中，并继续向后继子节点传递该Fact；否则该节点不采取任何动作，拒绝输入的Fact。

3)当Fact被传递到某个Beta节点的右端时，该Beta节点会先把该Fact加入到它的Alpha存储区中，然后对Beta存储区和Alpha存储区进行匹配操作，类似于关系数据库中2个表之间的join，projection，selection等运算。若2个存储区之间的运算有结果，则把该结果封装为一个新的Token传递到后继子节点的左输入口中；否则该节点不采取任何动作。

4)当Token被传递到某个Beta节点的左端时，该Beta节点会先把该Token加入到它的Beta存储区中，然后对Beta存储区和Alpha存储区进行匹配操作，类似于关系数据库中2个表之间的join，projection，selection等运算。若2个存储区之间的运算有结果，则把该结果封装为一个新的Token传递到后继子节点的左输入口中；否则该节点不采取任何动作。

5)当Fact被传递到某个Beta节点的左端时，则将该Fact封装成一个新的Token，然后按照4)的策略进行处理。

6)当Token被传递到某个叶子结点时，则表示该叶子节点所代表的规则成功被匹配，该规则和相应的Token会被加入到议程器中等待进行冲突解决。

7)当Fact被传递到某个叶子结点时，则将Fact封装成一个新的Token，然后按照6)的策略进行匹配。

3 算法实例与分析

下面通过一个简单的例子来展示Rete算法的过程。假设系统中存在A、B、C和D 4个模板，每个模板都有一个共同的属性ID；系统的事实库中存在以下事实：A(00)、A(01)、B(01)、B(02)、B(03)；系统的规则库中存在以下3个规则：

Rule-1：If A(x) and B(x) then add C(x)

Rule-2：If A(x) and B(x) and C(x) then add D(x)

Rule-3：If A(x) and B(x) and D(x) then delete A(x)

图1 Rete网络实例

Rete算法会首先根据上述3条规则构建如图1所示的Rete网络。在图1中，Alpha网络中的子节点的功能主要是根据传递进来的Fact的类型来对Fact进行分类，并把符合条件的Fact保存到自己的Alpha存储区中。而Beta网络中的节点都是双输入的，从左输入的Token会被保存到该Beta节点的Beta存储区中，从右输入的Fact则会被保存到Beta节点Alpha存储区中；每次当存储区有新的Token或Fact进来之后，Alpha存储区和Beta存储区之间都会进行匹配运算，这类似于关系数据库中的表的连接操作，若匹配成功则把该结果封装为新的Token传递到后续子节点。

显然，Rule-1规则会首先被触发执行，进而在事实库中添加事实C(01)。C(01)从Rete网络的根节点开始依次沿着路径向下匹配，最终触发Rule-2，创建事实D(01)到事实库中。同样的道理，D(01)从Rete网络的根节点开始沿着路径往下匹配，最后也触发执行Rule-3，进而删掉事实A(01)。在整个过程中Alpha节点和Beta节点都保存了相应的匹配中间结果，所以极大地加快了Rete算法的匹配速度。

[1]鲍金玲.基于规则引擎技术的Rete算法的研究[J].科技信息，2008(32):90-103.

[2]姜涛.Drools规则引擎的研究与应用[EB/OL].http://www.paper.edu.cn/index.php/default/releasepaper/downpaper/，2008-12-14.

[编辑] 洪云飞

10.3969/j.issn.1673-1409(N).2012.03.031

TP311

A

1673-1409(2012)03-N093-03

2011-12-23

魏毅峰(1978-)，男，1999年大学毕业，硕士，讲师，现主要从事模式识别与智能系统方面的教学与研究工作。