规则引擎rete算法,网络id算法

Rete算法是Charles Forgy在1979年的论文中首次提出的针对基于规则的知识表示的模式匹配算法。目前，大多数规则引擎都基于rete算法，但已经得到了改进，如drool、踏实冷风等。介绍rete算法的概念

1.Rete算法rete算法是一种高效的模式匹配算法实现生成性规则系统

(用空间换时间，用内存换速度)

这是一种高效的算法，可以避免缓存多次评估相同的条件，但会占用大量内存

Rete在拉丁语中是“net”，有网络的意思； Rete算法根据规则条件生成网络，各规则条件是网络中的节点

rete可以分为规则编译和运行时运行两部分。规则编译是基于规则集生成推理网络的过程，而运行时运行是将数据发送到推理网络进行过滤的过程。

2 .规则编译规则编译是指从规则文件中推理生成网络的过程。推理后的网络节点图如下所示。 (各位，只要看了一下，心里有印象就好了，所以分析说明) )。

图1

2.1根节点(根节点： (图1中的黑色节点)根节点)是所有对象进入网络的入口，然后进入类型节点

2.2类型节点(部分是对象类型节点，图1中的红色节点) :类型节点是我们的fact，也就是我们规则中使用的pojo；每个fact都是类型节点。 type Node是类型检查，引擎只允许与Object类型匹配的对象到达节点，并传播到alpha nodes、leftinputadapternodes (beta nodes左端的输入节点)和beta nodes

例如，有两个fact、Person和cheese。节点映射如下所示：

2.3 alpha节点： (图1中的蓝色节点)用于评估字面条件，例如： person.age10这是alpha node节点，如果一个规则具有多个字面条件，这些字面条件将被链接。

Drools通过散列法优化了从ObjectTypeNode到AlphaNode的传播。每次将一个AlphaNode添加到一个对象类型节点时，都会将“文字值”作为key，AlphaNode作为value添加到HashMap。当新实例进入ObjectTypeNode时，可以直接从HashMap获得正确的alpha node，而无需传递给所有alpha node，从而避免不必要的字面检查。

示例1:条件cheese(name="cheddar "，strengh==”strong " )

说明： name和strengh都是对象Cheese的属性，name和strengh两个条件的关系为，并且需要同时满足的螺母或节点图如下：

示例2:在示例1的条件中添加另一规则cheese(name=“cheddar”，age10 )

解释： name和age都是对象Cheese的属性，且name和age两个条件的关系为，并且必须同时满足。例1的节点图如下所示。

此时，我们发现我们的门共享一个(name==“cheddar”)节点。

2.4 Bate Node: (图1中的绿色节点)用于比较和检查两个对象。约定BetaNode的两个输入称为左侧(连接节点)和右侧。左边通常是对象列表，而右边通常是对象列表。每个Bate节点都有自己的末端节点等

BetaNode有记忆功能。左边的输入叫实地金属，我会记住所有到达的意思。右边的输入将是alpha memory，记住所有到达的对象。

示例：条件cheese(name=“cheddar”) person ) favouriteitecheese==“cheese.name”)。

解释：这两个对象Cheese和Person的关联操作。 Cheese的name=”cheddar "且cheese.ame==favouriteiteCheese。在中，节点映射如下所示：

图中黄色的node我门称为LeftInputAdapterNode，该节点的作用是将单对象转化为单对象数组(single Object Tuple )，并传播到关节节点。因为他说左边的输入通常是对象列表。

示例2 :

rulewhencheese ($ cheddar : name==' cheddar ' ) person:person ) favouritecheese==$cheddar ) thensystem.out .

eddar" );endrulewhen Cheese( $cheddar : name == "cheddar" ) $person : Person( favouriteCheese != $cheddar )then System.out.println( $person.getName() + " does not like cheddar" );end

网络图如下：

Drools 通过节点的共享来提高规则引擎的性能。因为很多的规则可能存在部分相同的模式，节点的共享允许我们对内存中的节点数量进行压缩，以提供遍历节点的过程

从图上可以看到，编译后的RETE网络中，AlphaNode是共享的，而BetaNode不是共享的。上面说的相等和不相等就体现在BetaNode的不同。然后这两条规则有各自的Terminal Node。

2.5 创建 rete 网络

Rete 算法的编译结果是创建了规则集对应的 Rete 网络 , 它是一个事实可以在其中流动的图。创建 rete 网络的过程 [1]如下：

1) 创建根节点；
2) 加入一条规则

a. 取出规则中的一个模式，（模式就是规则中的最axdgb个匹配项例如（age>10,age<20）拿么age>10 就是一个模式，age<20 就是另一个模式。）检查模式中的参数类型，如果是新类型(也就是新的fact类型)，则加入一个类型节点；b. 检查模式对应的 Alpha 节点是否已存在，如果存在则记录下节点位置，如果没有则将模式作为一个 Alpha 节点加入到网络中，同时根据 Alpha 节点的模式建立 Alpha 内存表；c. 重复 b 直到所有的模式处理完毕；d. 组合 Beta 节点，按照如下方式： Beta 左输入节点为 Alpha(1)，右输入节点为 Alpha(2) 。Beta(i) 左输入节点为 Beta(i-1)，右输入节点为 Alpha(i) i>2 并将两个父节点的内存表内联成为自己的内存表； e. 重复 d 直到所有的 Beta 节点处理完毕；f. 将动作（Then 部分）封装成叶节点（Action 节点）作为 Beta(n) 的输出节点；

3) 重复 2) 直到所有规则处理完毕；执行完上述步骤，建立的 rete 网络图

3. 运行时执行

WME ：存储区储存的最小单位是工作存储区元素（Working Memory Element，简称WME），WME是为事实建立的元素，是用于和非根结点代表的模式进行匹配的元素。

Token：是WME的列表，包含有多个WME，（在Forgy的论文中，把Token看成是WME的列表或者单个WME，为了阐述方便，本文将把Token只看成WME的列表）

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

TypeNode存储：每次一个AlphaNode被加到一个 ObjectTypeNode的时候，就以字面值（literal value）也就是file 作为key，以AlphaNode作为value加入HashMap。当一个新的实例进入ObjectTypeNode的时候，不用传递到每一个AlphaNode，它可以直接从HashMap中获得正确的AlphaNode，避免了不必要的字面检查。

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

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

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

bate存储区：每个非根结点都有一个存储区。其中1-input（alpha）结点有alpha存储区和一个输入口；2-input（bate）结点有left存储区和right存储区和左右两个输入口，其中left存储区是beta存储区，right存储区是alpha存储区。存储区储存的最小单位是工作存储区元素（Working Memory Element，简称WME），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和结点对应模式的匹配的过程。

4. Rete 算法的特点：

a． Rete 算法是一种启发式算法，不同规则之间往往含有相同的模式，因此在 beta-network 中可以共享 BetaMemory 和 betanode。如果某个 betanode 被 N 条规则共享，则算法在此节点上效率会提高 N 倍。

b. Rete 算法由于采用 AlphaMemory 和 BetaMemory 来存储事实，当事实集合变化不大时，保存在 alpha 和 beta 节点中的状态不需要太多变化，避免了大量的重复计算，提高了匹配效率。

c. 从 Rete 网络可以看出，Rete 匹配速度与规则数目无关，这是因为事实只有满足本节点才会继续向下沿网络传递。

5. Rete 算法的不足：

a. 事实的删除与事实的添加顺序相同, 除了要执行与事实添加相同的计算外, 还需要执行查找, 开销很高 [3]。

b. RETE 算法使用了β存储区存储已计算的中间结果, 以牺牲空间换取时间, 从而加快系统的速度。然而β存储区根据规则的条件与事实的数目而成指数级增长, 所以当规则与事实很多时, 会耗尽系统资源 [3]。
针对 Rete 算法的特点和不足，在应用或者开发基于 Rete 算法的规则引擎时，提出如下建议：

a. 容易变化的规则尽量置后匹配，可以减少规则的变化带来规则库的变化。 b. 约束性较为通用或较强的模式尽量置前匹配，可以避免不必要的匹配。 c. 针对 Rete 算法内存开销大和事实增加删除影响效率的问题，技术上应该在 alpha 内存和 beata 内存中，只存储指向内存的指针，并对指针建里索引（可用 hash 表或者非平衡二叉树）。 d. Rete 算法 JoinNode 可以扩展为 AndJoinNode 和 OrJoinNode，两种节点可以再进行组合 [5]。