规则引擎研究——Rete算法介绍一、R ETE概述Rete算法是一种前向规则快速匹配算法，其匹配速度与规则数目无关。

Rete是拉丁文，对应英文是net，也就是网络。

Rete算法通过形成一个rete网络进行模式匹配，利用基于规则的系统的两个特征，即时间冗余性（Temporalredundancy）和结构相似性（structuralsimilarity），提高系统模式匹配效率。

二、相关概念2.1事实（FACT）：事实：对象之间及对象属性之间的多元关系。

为简单起见，事实用一个三元组来表示：（identifier^attributevalue），例如如下事实：w1:(B1^onB2)w6:(B2^colorblue)w2:(B1^onB3)w7:(B3^left-ofB4)w3:(B1^colorred)w8:(B3^ontable)w4:(B2^ontable)w9:(B3^colorred)w5:(B2^left-ofB3)2.2规则（RULE）:由条件和结论构成的推理语句，当存在事实满足条件时，相应结论被激活。

一条规则的一般形式如下：(name-of-this-productionLHS/*oneormoreconditions*/-->RHS/*oneormoreactions*/)其中LHS为条件部分，RHS为结论部分。

下面为一条规则的例子：(find-stack-of-two-blocks-to-the-left-of-a-red-block(^on)(^left-of)(^colorred)-->...RHS...)2.3模式（PATTEN）：模式：规则的IF部分，已知事实的泛化形式，未实例化的多元关系。

(^on)(^left-of)(^colorred)三、模式匹配的一般算法规则主要由两部分组成：条件和结论，条件部分也称为左端（记为LHS,left-handside），结论部分也称为右端（记为RHS,right-handside）。

为分析方便，假设系统中有N条规则，每个规则的条件部分平均有P个模式，工作内存中有M个事实，事实可以理解为需要处理的数据对象。

规则匹配，就是对每一个规则r,判断当前的事实o是否使LHS(r)=True，如果是，就把规则r的实例r(o)加到冲突集当中。

所谓规则r的实例就是用数据对象o的值代替规则r的相应参数，即绑定了数据对象o的规则r。

规则匹配的一般算法：1)从N条规则中取出一条r；2)从M个事实中取出P个事实的一个组合c；3)用c测试LHS(r)，如果LHS(r（c）)=True，将RHS(r（c）)加入冲突集中；4)取出下一个组合c，goto3；5)取出下一条规则r，goto2；四、RETE算法Rete算法的编译结果是规则集对应的Rete网络,如下图。

Rete网络是一个事实可以在其中流动的图。

Rete网络的节点可以分为四类：根节点（root）、类型节点（typenode）、alpha节点、beta节点。

其中，根结点是一个虚拟节点，是构建rete网络的入口。

类型节点中存储事实的各种类型，各个事实从对应的类型节点进入rete网络。

4.1建立RETE网络Rete网络的编译算法如下：1)创建根；2)加入规则1(Alpha节点从1开始，Beta节点从2开始)；a.取出模式1，检查模式中的参数类型，如果是新类型，则加入一个类型节点；b.检查模式1对应的Alpha节点是否已存在，如果存在则记录下节点位置，如果没有则将模式1作为一个Alpha节点加入到网络中，同时根据Alpha节点的模式建立Alpha内存表；c.重复b直到所有的模式处理完毕；d.组合Beta节点，按照如下方式：Beta(2)左输入节点为Alpha(1)，右输入节点为Alpha(2)Beta(i)左输入节点为Beta(i-1)，右输入节点为Alpha(i)i>2并将两个父节点的内存表内联成为自己的内存表；e.重复d直到所有的Beta节点处理完毕；f.将动作（Then部分）封装成叶节点（Action节点）作为Beta(n)的输出节点；3)重复2)直到所有规则处理完毕；可以把rete算法类比到关系型数据库操作。

把事实集合看作一个关系，每条规则看作一个查询，将每个事实绑定到每个模式上的操作看作一个Select操作，记一条规则为P，规则中的模式为c1,c2,…,ci,Select操作的结果记为r(ci),则规则P的匹配即为r(c1)◇r(c2)◇…◇(rci)。

其中◇表示关系的连接（Join）操作。

4.2使用RETE网络进行匹配使用一个rete的过程：1)对于每个事实，通过select操作进行过滤，使事实沿着rete网达到合适的alpha节点。

2)对于收到的每一个事实的alpha节点，用Project(投影操作)将那些适当的变量绑定分离出来。

使各个新的变量绑定集沿rete网到达适当的bete节点。

3)对于收到新的变量绑定的beta节点，使用Project操作产生新的绑定集，使这些新的变量绑定沿rete网络至下一个beta节点以至最后的Project。

4)对于每条规则，用project操作将结论实例化所需的绑定分离出来。

下面为的图示显示了连接（Join）操作和投影（Project）的执行过程。

4.3R ETE算法的特点Rete算法有两个特点使其优于传统的模式匹配算法。

1、状态保存事实集合中的每次变化，其匹配后的状态都被保存在alpha和beta节点中。

在下一次事实集合发生变化时，绝大多数的结果都不需要变化，rete算法通过保存操作过程中的状态，避免了大量的重复计算。

Rete算法主要是为那些事实集合变化不大的系统设计的，当每次事实集合的变化非常剧烈时，rete的状态保存算法效果并不理想。

2、节点共享另一个特点就是不同规则之间含有相同的模式，从而可以共享同一个节点。

Rete网络的各个部分包含各种不同的节点共享。

使用RETE算法的模块系统，有四个入口，分别是添加事实（add-wme）、去除事实（remove-wme）、添加规则（add-production）、去除规则（remove-production）。

上面的主要介绍了建立rete网络后添加事实的过程。

下面先具体介绍alpha网络的建立和添加事实的过程，然后再介绍另外三个过程。

4.4A LPHA网络当事实添加到工作内存后，alpha网络对事实进行必要的类型检测并把事实存放到相应的alpha内存里。

有几种方法来寻找合适的alpha内存节点。

4.4.1数据流网络最直接的方式就是使用一个简单的数据流网络。

下图就是一个采用数据流网络建立的alpha网络。

上面的alpha网络仅仅检测条件中的常量，如attribute项上的常量有on，color，left-of；value项上的常量redmaizebluegreenwhite。

4.4.2带H ASHING的数据流网络上面的数据流网络的一个最大的缺点就是，当某个节点的扇出(fan-out)很大时，将会做大量的无用功（wastedwork）。

比如上图中对颜色的测试，某些专家系统可能含有大量的颜色，那么将会有大量的比较操作，从而造成匹配操作变慢。

一个解决这个问题的方法就是对于那些带有很大扇出的节点，采用hash表（或者平衡二叉树）来判断。

从上面的讨论可知，alpha网络非常有效，随着事实集合的变化，alpha网络可以几乎可以马上作出相应处理。

Beta节点的处理占到了整个系统匹配的绝大部分时间。

所以一般研究的都针对网络中的beta节点进行。

4.5内存节点Alpha内存存储事实集合，beta内存存储tokens(tokens指规则中已经匹配好的事实绑定)。

4.5.1事实集合的结构事实集合最简单的结构是采用链表结构。

但是为了获得更高的效率，一般也给每个事实内存加上索引（indexing）。

最常用的索引方法是采用Hash表。

也可以采用树，但在多数rete算法实现上并不常用，（Barachini,1991）发现Hash表一般比非平衡二叉树的性能好。

索引方法的缺点有两个：添加删除元素费时，降低了节点的复用度。

所以索引方法在那些节点内存中并不包含很多元素的系统中不适用。

4.5.2T OKEN的结构可以使用数组或链表来存储token。

使用数组需要更多的空间，同时需要更多的时间来创建token。

但是，拥有更快的访问速度。

通常，选择的标准在于使用链表时访问某个元素的用的时间是否可以承受。

4.6连接节点(J OINNODE)当一个连接节点的alpha内存中加入一个事实时，将引发此连接节点的rightactivation，当一个连接结点的beta内存中加入一个token时，将引发此连接节点的leftactivation。

连接节点的数据结构包括：指向其alpha内存和beta内存的指针，变量连接检测的说明，指向子节点的指针。

当一个连接节点的alpha内存中加入某个事实时，引发rightactivation。

此处，因为rightactivation的顺序不同，有可能产生冗余tokens（即在同一个beta内存里存储有两个或以上的相同的token）。

解决这个问题的方法有：每次在beta内存中加入一个新的token时，都检测是否已存在相同的token。

这个方法的缺点就是使系统的处理速度变慢。

另外一个较好的方法是把rightactivation的顺序确定下来。

4.7去除事实（R EMOVALSOFFACTS）当某个事实从工作内存总删除时，需要更新含有此事实的alpha内存和beta内存，有以下几种方法。

在原始的rete算法中，删除操作和添加操作采用同一种方式。

称此方式为rematch-basedremoval。

主要思想是给每个添加或删除操作一个tag，用来表明此操作是添加事实或删除事实。

删除操作的具体执行过程同上面讨论的添加一个事实的过程类似。

此方法与其他方法相比，速度较慢。

因为删除操作与添加操作的工作量几乎相同。

在添加事实过程中所获得的信息并没有在执行删除操作时加以利用。

下面有三种改进的算法。

在scan-basedremoval中，当一个连接节点的alpha内存中的某个事实w被去除时，把w传给此连接节点的输出内存，在此内存中寻找最后一个元素为w的tokens，将这些tokens删除，并且把这些tokens传给此连接节点的子节点。

在在子节点中做类似删除操作。

（Scales，1986）通过使用此方法代替原有方法，获得28％的加速。

(Barachini,1991)获得了10％的加速。

在list-baseremoval和tree-basedremoval中使用了这样一个原理，即给事实集合以及tokens的数据结构上增添额外的指针，当某个事实被删除时，可以沿着这些指针删除需要删除的元素。