使用RETE算法的模块系统,有四个入口,分别是添加事实(add-wme)、去除事实(remove-wme)、添加规则(add-production)、去除规则(remove-production)。
上面的主要介绍了建立rete网络后添加事实的过程。下面先具体介绍alpha网络的建立和添加事实的过程,然后再介绍另外三个过程。
4.4 Alpha网络
当事实添加到工作内存后,alpha网络对事实进行必要的类型检测并把事实存放到相应的alpha内存里。有几种方法来寻找合适的alpha内存节点。
4.4.1 数据流网络
最直接的方式就是使用一个简单的数据流网络。
下图就是一个采用数据流网络建立的alpha网络。
上面的alpha网络仅仅检测条件中的常量,如attribute项上的常量有on,color,left-of;value项上的常量red maize blue green white。
4.4.2 带Hashing的数据流网络
上面的数据流网络的一个最大的缺点就是,当某个节点的扇出(fan-out)很大时,将会做大量的无用功(wasted work)。比如上图中对颜色的测试,某些专家系统可能含有大量的颜色,那么将会有大量的比较操作,从而造成匹配操作变慢。
一个解决这个问题的方法就是对于那些带有很大扇出的节点,采用hash表(或者平衡二叉树)来判断。
从上面的讨论可知,alpha网络非常有效,随着事实集合的变化,alpha网络可以几乎可以马上作出相应处理。Beta节点的处理占到了整个系统匹配的绝大部分时间。所以一般研究的都针对网络中的beta节点进行。
4.5 内存节点
Alpha内存存储事实集合,beta内存存储tokens(tokens指规则中已经匹配好的事实绑定)。
4.5.1 事实集合的结构
事实集合最简单的结构是采用链表结构。但是为了获得更高的效率,一般也给每个事实内存加上索引(indexing)。最常用的索引方法是采用Hash表。也可以采用树,但在多数rete算法实现上并不常用,(Barachini,1991)发现Hash表一般比非平衡二叉树的性能好。索引方法的缺点有两个:添加删除元素费时,降低了节点的复用度。所以索引方法在那些节点内存中并不包含很多元素的系统中不适用。
4.5.2 Token的结构
可以使用数组或链表来存储token。使用数组需要更多的空间,同时需要更多的时间来创建token。但是,拥有更快的访问速度。通常,选择的标准在于使用链表时访问某个元素的用的时间是否可以承受。
使用RETE算法的模块系统,有四个入口,分别是添加事实(add-wme)、去除事实(remove-wme)、添加规则(add-production)、去除规则(remove-production)。
上面的主要介绍了建立rete网络后添加事实的过程。下面先具体介绍alpha网络的建立和添加事实的过程,然后再介绍另外三个过程。
4.4 Alpha网络
当事实添加到工作内存后,alpha网络对事实进行必要的类型检测并把事实存放到相应的alpha内存里。有几种方法来寻找合适的alpha内存节点。
4.4.1 数据流网络
最直接的方式就是使用一个简单的数据流网络。
下图就是一个采用数据流网络建立的alpha网络。
上面的alpha网络仅仅检测条件中的常量,如attribute项上的常量有on,color,left-of;value项上的常量red maize blue green white。
4.4.2 带Hashing的数据流网络
上面的数据流网络的一个最大的缺点就是,当某个节点的扇出(fan-out)很大时,将会做大量的无用功(wasted work)。比如上图中对颜色的测试,某些专家系统可能含有大量的颜色,那么将会有大量的比较操作,从而造成匹配操作变慢。
一个解决这个问题的方法就是对于那些带有很大扇出的节点,采用hash表(或者平衡二叉树)来判断。
从上面的讨论可知,alpha网络非常有效,随着事实集合的变化,alpha网络可以几乎可以马上作出相应处理。Beta节点的处理占到了整个系统匹配的绝大部分时间。所以一般研究的都针对网络中的beta节点进行。
4.5 内存节点
Alpha内存存储事实集合,beta内存存储tokens(tokens指规则中已经匹配好的事实绑定)。
4.5.1 事实集合的结构
事实集合最简单的结构是采用链表结构。但是为了获得更高的效率,一般也给每个事实内存加上索引(indexing)。最常用的索引方法是采用Hash表。也可以采用树,但在多数rete算法实现上并不常用,(Barachini,1991)发现Hash表一般比非平衡二叉树的性能好。索引方法的缺点有两个:添加删除元素费时,降低了节点的复用度。所以索引方法在那些节点内存中并不包含很多元素的系统中不适用。
4.5.2 Token的结构
可以使用数组或链表来存储token。使用数组需要更多的空间,同时需要更多的时间来创建token。但是,拥有更快的访问速度。通常,选择的标准在于使用链表时访问某个元素的用的时间是否可以承受。
分享到:
相关推荐
URULE是一款基于RETE算法的纯Java规则引擎,提供规则集、决策表、决策树、评分卡,规则流等各种规则表现工具及基于网页的可视化设计器,可快速开发出各种复杂业务规则。
改进Rete算法对电信计费规则引擎系统性能的提升,钟小安,,本文详细描述了改进电信计费系统中规则引擎组件Rete算法的两种实现方式-在Alpha存储区对Alpha节点进行哈希查找和在Beta存储区对Beta节点�
动态演化系统中规则引擎的改进Rete算法
在此理论基础上,将一种高效的模式匹配算法——Rete算法引入到实际的故障的诊断系统中,以保证故障诊断的高效性和准确性。为此在实际系统中,借助规则引擎将故障信息规则化,并将故障诊断流程以层次分明的XML文档...
drools-rete算法简介.docx
从老外网站那里下载的最好的描述rete算法的ppt
基于RETE算法的纯Java规则引擎,提供规则集、决策表、决策树、评分卡,规则流等各种规则表现工具及
URule是一款纯Java规则引擎,它以RETE算法为基础,提供了向导式规则集、脚本式规则集、决策表、交叉决策表(PRO版提供)、决策树、评分卡及决策流共六种类型的规则定义方式,配合基于WEB的设计器,可快速实现规则的...
Charles L. Forgy的rete文章
Drools是Jboss公司旗下一款开源的规则引擎,它完整的实现了Rete算法;提供了强大的EclipsePlugin开发支持;通过使用其中的DSL(DomainSpecificLanguage),可以实现用自然语言方式来描述业务规则,使得业务分析人员也...
NRules NRules是基于匹配算法的.NET开源生产规则引擎。 使用内部DSL以C#编写规则。安装NRule 首先, 。 然后,从Package Manager控制台安装 : PM> Install-Package NRules入门使用以下资源来启动和运行NRule。 ...
Drools规则引擎是一种嵌套在应用程序中的组件, 是用Java语言编写的开放源码规则引擎,使用Rete算法对所编写的规则求值。 它实现了将业务规则从程序代码忠分离出来,规则引擎使用特定的语法编写业务规则,规则引擎...
提供规则集、决策表、决策树、评分卡,规则流等各种规则表现工具及基于网页的可视化设计器,可快速开发出各种复杂业务规则。 开发工具在软件开发生命周期中扮演着至关重要的角色,它们旨在简化和加速从概念设计到...
java 源码编辑 虫洞 · 技术栈 | 沉淀、分享、成长,让自己和他人都能有所收获! 作者: 小傅哥,Java Developer, 本文档是作者小傅哥多年从事一线互联网Java开发的学习历程技术汇总,旨在为大家提供一个较清晰详细...
Drools 是一个基于Charles Forgy's的Rete算法的,专为Java语言所设计的规则引擎。Rete算法应用于面向对象的接口将使基于商业对象的商业规则的表达更为自然。Drools是用Java写的,但能同时运行在Java和.Net上。该文档...
Drools是Jboss公司旗下一款开源的规则引擎,它完整的实现了Rete 算法;提供了强大的Eclipse Plugin开发支持; 通过使用其中的DSL(Domain Specific Language),可以实现用自然语言方式来描述业务规则,使得业务分析...