规则引擎研究-整理

《规则引擎研究-整理》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、规则引擎研究-整理规则引擎研究一一Rete算法介绍一、RETE概述Rote算法是一种前向规则快速匹配算法，其匹配速度与规则数冃无关。Rote是拉丁文，对应英文是net,也就是网络。Rete算法通过形成一个rete网络进行模式匹配，利用基于规则的系统的两个特征，即时间兀余性(Temporalredundancy)和结构相似性(structuralsimilarity),提高系统模式匹配效率。二、相关概念2.1事实(FACT):事实：对象之间及对象属性之间的多元关系。为简单起见，事实用一个三元组来表示：(identifier"attributevalue),例如如

2、下事实:wl:(BlonB2)w6:(B2colorblue)w2:(B「onB3)w7:(B3left-ofB4)w3:(Blcolorred)w8:(B3ontable)w4:(B2"ontable)w9:(B3*colorred)w5:(B2^1eft-ofB3)2.2规则(RULE):由条件和结论构成的推理语句，当存在事实满足条件时，相应结论被激活。一条规则的—•般形式如下：(namo-of-this-productionLHS/*oneormoreconditions*/—>RHS/*oneormoreactions*/)其中LHS为条件部分，RHS

3、为结论部分。下而为一条规则的例子：(find-stack-of-two-blocks-to-thoTeft-of-a-rod-block「on)「left-of)(colorred)-->…RHS...)2.3模式(PATTEN):模式：规则的IF部分，已知事实的泛化形式，未实例化的多元关系。「on)「left-of)(^colorrod)三、模式匹配的一般算法规则主要由两部分组成：条件和结论，条件部分也称为左端(记为LHS,lefthandside),结论部分也称为右端(记为RIIS,right-handside)o为分析方便,假设系统中冇N条规则，每个规

4、则的条件部分平均有P个模式，工作内存中有M个事实，事实可以理解为需要处理的数据对象。规则匹配,就是对每一个规则r,判断当前的事实o是否使LHS(r)=True,如果是，就把规则r的实例r(o)加到冲突集当中。所谓规则r的实例就是用数据对象o的值代替规则r的相应参数，即绑定了数据对象o的规则门规则匹配的一般算法：1)从N条规则屮取出一条"2)从M个事实中取出P个事实的一个组合c；3)用c测试LHS(r),如果LHS(r(c))=True,将RHS(r(c))加入冲突集中；4)取出下一个组合c,goto3；1)取出下一条规则r,goto2；四、RETE算法Rete

5、算法的编译结果是规则集对应的Rete网络，如F图。Rete网络是一个事实可以在其中流动的图。Rete网络的节点可以分为四类:根节点(root)、类型节点(typenode)>alpha节点、beta节点。其中，根结点是一个虚拟节点，是构建rete网络的入口。类型节点中存储事实的各种类型，各个事实从对应的类型节点进入mtc网络。4.1建立RETE网络Rete网络的编译算法如F：1)创建根；2)加入规则1(Alpha节点从1开始，Beta节点从2开始)；a.取出模式1,检查模式中的参数类型，如果是新类型，则加入一个类型节点；b.检查模式1对应的Alpha节点是否已

6、存在，如果存在则记录下节点位置，如果没冇则将模式1作为一个Alpha节点加入到网络中，同时根据Alpha节点的模式建立Alpha内存表；c.重复b直到所有的模式处理完毕；d.组介Beta节点，按照如下方式：Beta(2)左输入节点为Alpha(l),右输入节点为Alpha(2)Beta(i)左输入节点为Beta(i-l),右输入节点为Alpha(i)i>2并将两个父节点的内存表内联成为自己的内存农；e.重复d直到所有的Beta节点处理完毕；f・将动作(Then部分)封装成叶节点(Action节点)作为Beta(n)的输出节点；3)重复2)直到所有规则处理完毕；

7、可以把rete算法类比到关系型数据库操作。把事实集合看作一个关系，每条规则看作一个杳询，将每个事实绑定到每个模式上的操作看作一个Select操作,记一条规则为P,规则中的模式为cl,c2,…,ci,Select操作的结果记为r(ci),则规则P的匹配即为r(cl)Or(c2)◊(rci)。其中◊表示关系的连接(Join)操作。R.dcnetworkforthreepnxliKtiojtRKeicnctsvcrlAuonepriKlucliouwithvondiboc1<=•^v«i)C2C)C5:人colorred)PIcunditurnM

8、Cl^2^P2h»cimdition%