资源描述:
《规则引擎研究-整理》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
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%