最近在研读Jena的推理机源代码,Jena推理机的实现主要也是用的RETE算法,所以研究了RETE算法的基本流程。RETE算法是由Forgy在他的论文《A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem》中提出的。
1 RETE算法的基本思想
RETE算法是一个用于产生式系统的高效模式匹配算法。在一个产生式系统中,被处理的数据叫做working memory,用于判定的规则分为两个部分LHS(left-hand-side)和RHS(right hand side),分别表示前提和结论。主要流程可以分为以下步骤:
(1)Match:找出符合LHS部分的working memory集合
(2)Confilict resolution:选出一个条件被满足的规则
(3)Act:执行RHS的内容
(4)返回1
RETE算法主要改进Match的处理过程,通过构建一个网络进行匹配。
2算法详细描述
RETE网络主要分为两个部分,alpha网络和beta网络。如下图所示。
(1)alpha网络:过滤working memory,找出符合规则中每一个模式的集合,生成alpha memory(满足该模式的集合)。有两种类型的节点,过滤type的节点和其他条件过滤的节点(我觉得这两种是依照需要设定的,也并不一定需要两种节点)。
(2)Beta网络:有两种类型的节点Beta Memory和Join Node。前者主要存储Join完成后的集合。后者包含两个输入口,分别输入需要匹配的两个集合,由Join节点做合并工作传输给下一个节点。
3 匹配过程描述
(1)导入需要处理的事实到facts集合中。
(2)如果facts不为空,选择一个fact进行处理。否则停止匹配过程。
(3)选择alpha网的第一个节点运行(建立网络的时候设定的),通过该节点则进入alpha网的下一个节点,直到进入alpha memory。否则跳转到下一条判断路径。
(4)将alpha memory的结果加入到beta memory中,如果不为Terminal节点,则检测另一个输入集合中是否存在满足条件的事实,满足则执行join,进入到下一个beta memory重复执行(3)。若另一个输入集合无满足条件的事实,返回到(2)。如果该节点为Terminal节点,执行ACT并添加到facts中。
4 用一个例子描述过程
(1)现在WME中有以下这些事实。
w1:(B1 ^on B2)
w2:(B1 ^on B3)
w3:(B1 ^color red)
w4:(B2 ^on table)
w5:(B2 ^left-of B3)
w6:(B2 ^color blue)
w7:(B3 ^left-of B4)
w8:(B3 ^on table)
w9:(B3 ^color red)
(2)下面描述规则
下面是三条匹配条件
C1: (<x> ^on <y>)
C2:(<y> ^left-of <z>)
C3:(<z> ^color red)
下面是规则要满足的所有条件,即所有LHS
p1 has conditions C1^C2^C3
p2 has conditions C1^C2^C4^C5
p3 has conditions C1^C2^C4^C3
(3)推理描述
暂且忽略图中的红色节点(用于判定类型)。那么,根据Ci,图中的蓝色alpha结点应该有三种,分别判定on,left-of和color。则黄色的alpha memory中包含三个集合,分别是满足C1:{w1 w2 w4 w8}
满足C2:{w5 w7}
满足C3:{w2 w6 w9}
以p1为例,首先以C1,C2为输入,在绿色Dummy Input节点中进行操作,并传入到梅红色beta momory中,此时这个节点存储的是(w1^w5,w2^w7)。然后以这个集合和C3为输入,操作得出w1^w5^w9,此时发现没有更多的模式需要匹配,到达Terminal节点,匹配结束。这样就得到满足规则的集合组合了。
接下来的时间要研究Jena中Rete算法的具体实现方式。
分享到:
相关推荐
drools-rete算法简介.docx
从老外网站那里下载的最好的描述rete算法的ppt
URULE是一款基于RETE算法的纯Java规则引擎,提供规则集、决策表、决策树、评分卡,规则流等各种规则表现工具及基于网页的可视化设计器,可快速开发出各种复杂业务规则。
改进Rete算法对电信计费规则引擎系统性能的提升,钟小安,,本文详细描述了改进电信计费系统中规则引擎组件Rete算法的两种实现方式-在Alpha存储区对Alpha节点进行哈希查找和在Beta存储区对Beta节点�
Charles L. Forgy的rete文章
在此理论基础上,将一种高效的模式匹配算法——Rete算法引入到实际的故障的诊断系统中,以保证故障诊断的高效性和准确性。为此在实际系统中,借助规则引擎将故障信息规则化,并将故障诊断流程以层次分明的XML文档...
生锈的网 Rete 算法在 Rust 中的实现。
行业分类-设备装置-一种结合Rete算法的RDF数据分布式并行推理方法
Improved rete算法, 基于规则的专家系统采用的快速算法
基于RETE算法的纯Java规则引擎,提供规则集、决策表、决策树、评分卡,规则流等各种规则表现工具及
#资源达人分享计划#
URule是一款纯Java规则引擎,它以RETE算法为基础,提供了向导式规则集、脚本式规则集、决策表、交叉决策表(PRO版提供)、决策树、评分卡及决策流共六种类型的规则定义方式,配合基于WEB的设计器,可快速实现规则的...
提供规则集、决策表、决策树、评分卡,规则流等各种规则表现工具及基于网页的可视化设计器,可快速开发出各种复杂业务规则。 开发工具在软件开发生命周期中扮演着至关重要的角色,它们旨在简化和加速从概念设计到...
针对传统的规则引擎算法――Rete算法会缓存大量的部分匹配结果,而RFID事件通常具有时间约束的特点,提出一种基于部分匹配过期的过期数据回收机制,及时删除过期的部分匹配结果,减小计算过程中缓存的压力。...
动态演化系统中规则引擎的改进Rete算法
网络 网络算法Erlang实验