drools -Rete算法

u012373815 · · 2281 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

Rete算法是Charles Forgy在1979年的论文中首次提出的,针对基于规则知识表现的模式匹配算法。目前来说,大部分规则引擎还是基于rete算法作为核心,但都有所改进,比如drool,jess等等,下面介绍rete算法的概念

1.rete 算法

Rete算法是一种高效的模式匹配算法用来实现产生式规则系统
(空间换时间,用内存换取匹配速度)

它是高效的算法,它通过缓存避免了相同条件多次评估的情况,但是带来了大量的内存使用

Rete 在拉丁语中是 ”net” ,有网络的意思;Rete算法通过规则条件生成了一个网络,每个规则条件是网络中的一个节点


rete可以被分为两部分:规则编译和运行时执行。规则编译是指根据规则集生成推理网络的过程,运行时执行指将数据送入推理网络进行筛选的过程。

2.规则编译

规则编译就是根据规则文件推理生成网络的过程。下面展示一下推理后的网络节点图。(大家只用看一下,心里有个印象就好,下面我会分析讲解)

图一
这里写图片描述

2.1 Root Node:

(如图一的黑色节点) 根节点(RootNode)是所有对象进入网络的入口,然后进入到TypeNode

2.2 Type Node

(有的叫ObjectTypeNode,图一的红色节点): type Node 就是我们的fact 也就是我们规则所用到的pojo;每个fact 就是一个 type node。 type Node 就是类型检查,引擎只让匹配Object 类型的对象到达节点,它能够传播到 AlphaNodes、LeftInputAdapterNodes (作为betaNodes的左端输入节点)和 BetaNodes

举例:有两个fact ,Person 和cheese 。那么节点图就如下所示。

这里写图片描述

2.3 Alpha Node

:(图一的蓝色节点)用来评估字面条件,例如。person.age>10 这就是一个 alpha node 节点,当一条规则有多条字面条件,这些字面条件被链接到一起。

Drools 通过散列法优化了从 ObjectTypeNode 到 AlphaNode 的传播。每次一个 AlphaNode 被加到一个 ObjectTypeNode 的时候,就以字面值( literal value )作为 key ,以 AlphaNode 作为 value 加入 HashMap 。当一个新的实例进入 ObjectTypeNode 的时候,不用传递到每一个 AlphaNode ,它可以直接从 HashMap 中获得正确的 AlphaNode ,避免了不必要的字面检查。

举例 1:条件 Cheese (name=”cheddar” ,strengh==”strong”)

解释:name 和 strengh 都是对象Cheese 的属性,且name 和 strengh两个条件的关系是且,必须同时满足拿么节点图如下所示:

这里写图片描述


举例 2:在举例1 的条件上添加另外一条规则 Cheese (name=”cheddar” ,age>10)

解释:name 和 age 都是对象Cheese 的属性,且name 和 age两个条件的关系是且,必须同时满足,拿么结合举例1的节点图,如下所示:

这里写图片描述

此时我们发现我门共享了(name==“cheddar“) 节点。

2.4 Bate Node:

(如图一的绿色节点)用来对2个对象进行对比、检查。约定BetaNode的2个输入称为左边(Join Node)和右边。左边通常是一个a list of objects,右边(NotNode)通常是 a single object。每个Bate节点都有自己的终端节点等组成

BetaNode 具有记忆功能。左边的输入被称为 Beta Memory,会记住所有到达过的语义。右边的输入成为 Alpha Memory,会记住所有到达过的对象。


举例:条件 Cheese (name=”cheddar” ) Person(favouriteiteCheese==”cheese.name”)。

解释:这个两个对象Cheese和Person 的关联操作。Cheese的name=”cheddar” 且cheese.ame ==favouriteiteCheese。那么节点图如下所示。

这里写图片描述

图中黄色的node 我门称为LeftInputAdapterNode,这个节点的作用是将一个single Object转化为一个单对象数组(single Object Tuple),传播到JoinNode节点。因为我们上面提到过左边输入通常是a list of objects。


举例2:

rule
when
    Cheese( $cheddar : name == "cheddar" )
    $person : Person( favouriteCheese == $cheddar )
then
    System.out.println( $person.getName() + " likes cheddar" );
end
rule
when
    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. 取出规则中的一个模式 ,(模式就是规则中的最小一个匹配项例如(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]。

本文来自:CSDN博客

感谢作者:u012373815

查看原文:drools -Rete算法

入群交流(该群和以上内容无关):Go中文网 QQ交流群:798786647 或 加微信入微信群:274768166 备注:入群; 公众号:Go语言中文网

2281 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传