RETE算法

最近面试的时候，经常被问及自己参加的项目中rete算法的原理，但是RETE算法是一个比较复杂的算法，在短时间内不能阐述的足够清晰，在这里做个简单的介绍。转载请注明来自 http://chillwarmoon.iteye.com
RETE算法是一个用来实现产生式规则系统的高效模式匹配算法。该算法是由卡内基美隆大学的Charles L. Forgy在1974年发表的论文中所阐述的算法。RETE算法提供了专家系统的一个高效实现。
规则推理引擎做为产生式系统的一部分，当进行事实的断言时，包含三个阶段：匹配、选择和执行，称做match-select-act cycle。RETE算法可以对匹配阶段进行高效实现，下面从鉴别网络和模式匹配过程两个方面对该算法进行介绍。

鉴别网络（如下图所示）：
由RETE算法在进行模式匹配时，是根据生成的鉴别网络来进行的。网络中非根结点的类型有1-input结点（也称为alpha结点）和2-input结点（也称为beta结点）两种。1-input结点组成了Alpha网络，2-input结点组成了Beta网络。
每个非根结点都有一个存储区。其中1-input结点有alpha存储区和一个输入口；2-input结点有left存储区和right存储区和左右两个输入口，其中left存储区是beta存储区，right存储区是alpha存储区。存储区储存的最小单位是工作存储区元素（Working Memory Element，简称WME），WME是为事实建立的元素，是用于和非根结点代表的模式进行匹配的元素。Token是WME的列表，包含有多个WME，（在Forgy的论文中，把Token看成是WME的列表或者单个WME，为了阐述方便，本文将把Token只看成WME的列表，该列表可以包含一个WME或者多个WME），用于2-input结点的左侧输入。事实可以做为2-input结点的右侧输入，也可以做为1-input结点的输入。
每个非根结点都代表着产生式左部的一个模式，从根结点到终结点的路径表示产生式的左部。

规则匹配：
推理引擎在进行模式匹配时，先对事实进行断言，为每一个事实建立WME，然后将WME从RETE鉴别网络的根结点开始匹配，因为WME传递到的结点类型不同采取的算法也不同，下面对alpha结点和beta结点处理WME的不同情况分开讨论。

（1）如果WME的类型和根节点的后继结点TypeNode（alpha结点的一种）所指定的类型相同，则会将该事实保存在该TypeNode结点对应的alpha存储区中，该WME被传到后继结点继续匹配，否则会放弃该WME的后续匹配；

（2）如果WME被传递到alpha结点，则会检测WME是否和该结点对应的模式相匹配，若匹配，则会将该事实保存在该alpha结点对应的存储区中，该WME被传递到后继结点继续匹配，否则会放弃该WME的后续匹配；

（3）如果WME被传递到beta结点的右端，则会加入到该beta结点的right存储区，并和left存储区中的Token进行匹配（匹配动作根据beta结点的类型进行，例如：join，projection，selection），匹配成功，则会将该WME加入到Token中，然后将Token传递到下一个结点，否则会放弃该WME的后续匹配；

（4）如果Token被传递到beta结点的左端，则会加入到该beta结点的left存储区，并和right存储区中的WME进行匹配（匹配动作根据beta结点的类型进行，例如：join，projection，selection），匹配成功，则该Token会封装匹配到的WME形成新的Token，传递到下一个结点，否则会放弃该Token的后续匹配；

（5）如果WME被传递到beta结点的左端，将WME封装成仅有一个WME元素的WME列表做为Token，然后按照（4）所示的方法进行匹配；

（6）如果Token传递到终结点，则和该根结点对应的规则被激活，建立相应的Activation，并存储到Agenda当中，等待激发。

（7）如果WME被传递到终结点，将WME封装成仅有一个WME元素的WME列表做为Token，然后按照（6）所示的方法进行匹配；

以上是RETE算法对于不同的结点，来进行WME或者token和结点对应模式的匹配的过程。

评论

13 楼 chillwarmoon 2007-12-30  

在jamocha规则引擎中采用了基于插槽位置的模式匹配方法，在建立rete网络时，输入的是规则所对应的对象，对于该对象中的每一个CE，有如下的处理：
一 建立alpha网络
（1）对于第一次出现的变量，建立被绑定元素；
（2）对于出现的字面量约束，建立Alpha结点；如果rete网络中有相同约束的结点，则共享节点；
（3）将建立的所有被绑定元素加入到规则中。

二 建立beta网络
（1）对于非第一次出现的变量，建立绑定元素，并将被绑定元素的属性值填充至绑定元素；
（2）依据不同的CE和约束类型建立不同的beta结点；填充与该CE对应的绑定元素列表到该beta结点；
（3）连接beta结点到rete网络。

PS：目前做为规则引擎jamocha的开发人员，主要负责rete网络和模式匹配。如果大家感兴趣，可以去http://sourceforge.net/projects/jamocha看看。

12 楼 gb1981 2007-12-23  

能不能把Rete网络的编译算法解释一下？
即现在已经给定了一些事实、模式和规则，rete网络是如何构造的？

11 楼 chillwarmoon 2007-12-22  

gb1981 写道

我看过网上的文章，感觉你的文章写的不错。 关于rete算法，我还看过sina博客“小爽的老公”关于rete算法的文章： http://blog.sina.com.cn/s/blog_4a7a7aa30100089g.html。 我对rete算法，其中最开始的一点有疑惑： rete算法中的用来构造alpha节点的模式，他的顺序是有何要求的？如果没有要求，那么这个内存里的rete网络如果遇到模式为P1^P2和P2^P1,是怎么构造beta节点的？

<br/>
<br/>
顺序没有要求，但是对于规则的优化，最好是将具有相同事件类型结点下的模式的顺序保持一致。如果遇到同一事件类型下的，类似于(A)(B) 和(B)(A)这样的模式，一般是不能进行alpha结点共享的。如果有什么好的alpha结点共享的算法，可以一起讨论。

10 楼 gb1981 2007-12-20  

我看过网上的文章，感觉你的文章写的不错。
关于rete算法，我还看过sina博客“小爽的老公”关于rete算法的文章：
http://blog.sina.com.cn/s/blog_4a7a7aa30100089g.html。
我对rete算法，其中最开始的一点有疑惑：
rete算法中的用来构造alpha节点的模式，他的顺序是有何要求的？如果没有要求，那么这个内存里的rete网络如果遇到模式为P1^P2和P2^P1,是怎么构造beta节点的？

9 楼 chillwarmoon 2007-11-28  

fuzidd1212003 写道

能不能通过一个例子，解释一下这个算法．．

<br/>
<br/>
这个算法的解释你可以参看一下我写的另外一篇文章http://chillwarmoon.iteye.com/blog/138059<br/>
<br/>
关于怎么由规则生成rete network的过程是很复杂的。估计一月份之后我会把详细的生成过程和模式匹配的过程写到我的博客上。

8 楼 chillwarmoon 2007-11-28  

yangyang 写道

能不能通过一个项目来说明这个算法的使用。

<br/>
<br/>
在AI领域，产生式系统是一个很重要的概念，rete算法是实现产生式系统中模式匹配的一个高效算法。例如Drools引擎就是利用rete算法对规则进行分析，形成rete network，从而进行模式匹配的。

7 楼 fuzidd1212003 2007-11-26  

能不能通过一个例子，解释一下这个算法．．

6 楼 yangyang 2007-11-26  

能不能通过一个项目来说明这个算法的使用。

5 楼 free49498445 2007-11-22  

网络术语太多了。。。

4 楼 chillwarmoon 2007-11-16  

shijiyu 写道

能否将RETE算法说的清楚点？有没有相关的资料？

<br/>
<br/>
不知道你哪不清楚，如果有不清楚的地方，可以提出来。

3 楼 shijiyu 2007-11-12  

能否将RETE算法说的清楚点？有没有相关的资料？

2 楼 tornyz 2007-11-07  

图不清晰。

1 楼 laiseeme 2007-11-06  

高深 学习学习