4.6 连接节点(Join node)
当一个连接节点的alpha内存中加入一个事实时,将引发此连接节点的right activation,当一个连接结点的beta内存中加入一个token时,将引发此连接节点的left activation。
连接节点的数据结构包括:指向其alpha内存和beta内存的指针,变量连接检测的说明,指向子节点的指针。
当一个连接节点的alpha内存中加入某个事实时,引发right activation。此处,因为right activation 的顺序不同,有可能产生冗余tokens(即在同一个beta内存里存储有两个或以上的相同的token)。结果这个问题的方法有:每次在beta内存中加入一个新的token时,都检测是否已存在相同的token。这个方法的缺点就是使系统的处理速度变慢。另外一个较好的方法是把right activation的顺序确定下来。
4.7 去除事实(Removals of facts)
当某个事实从工作内存总删除时,需要更新含有此事实的alpha内存和beta内存,有以下几种方法。
在原始的rete算法中,删除操作和添加操作采用同一种方式。称此方式为rematch-based removal。主要思想是给每个添加或删除操作一个tag,用来表明此操作是添加事实或删除事实。删除操作的具体执行过程同上面讨论的添加一个事实的过程类似。此方法与其他方法相比,速度较慢。因为删除操作与添加操作的工作量几乎相同。在添加事实过程中所获得的信息并没有在执行删除操作时加以利用。下面有三种改进的算法。
在scan-based removal中,当一个连接节点的alpha内存中的某个事实w被去除时,把w传给此连接节点的输出内存,在此内存中寻找最后一个元素为w的tokens,将这些tokens删除,并且把这些tokens传给此连接节点的子节点。在在子节点中做类似删除操作。(Scales,1986)通过使用此方法代替原有方法,获得28%的加速。(Barachini,1991)获得了10%的加速。
在list-base removal和tree-based removal中使用了这样一个原理,即给事实集合以及tokens的数据结构上增添额外的指针,当某个事实被删除时,可以沿着这些指针删除需要删除的元素。
在list-based removal(Scales ,1986)中,把每个事实w上添加一个包含此事实的tokens的链表。当w被删除时,只要沿着此链表删除这些tokens。缺点就是需要大量的空间来存储链表,同时在创建一个新token时也可能花费大量的额外时间。
在tree-base removal中,在每个事实w上添加一个链表,这些链表指向把w作为最后一个元素的tokens。同时,在每个tokens上,添加一个指向此tokens的子节点的链表。当w被删除时,遍历以tokens为根的子树,删除子树上的所有元素。当然,这些额外指针将占用更多内存,同时,建立这些指针也耗费时间。经验表明,采用此方法比原始方法要节省时间。
4.6 连接节点(Join node)
当一个连接节点的alpha内存中加入一个事实时,将引发此连接节点的right activation,当一个连接结点的beta内存中加入一个token时,将引发此连接节点的left activation。
连接节点的数据结构包括:指向其alpha内存和beta内存的指针,变量连接检测的说明,指向子节点的指针。
当一个连接节点的alpha内存中加入某个事实时,引发right activation。此处,因为right activation 的顺序不同,有可能产生冗余tokens(即在同一个beta内存里存储有两个或以上的相同的token)。结果这个问题的方法有:每次在beta内存中加入一个新的token时,都检测是否已存在相同的token。这个方法的缺点就是使系统的处理速度变慢。另外一个较好的方法是把right activation的顺序确定下来。
4.7 去除事实(Removals of facts)
当某个事实从工作内存总删除时,需要更新含有此事实的alpha内存和beta内存,有以下几种方法。
在原始的rete算法中,删除操作和添加操作采用同一种方式。称此方式为rematch-based removal。主要思想是给每个添加或删除操作一个tag,用来表明此操作是添加事实或删除事实。删除操作的具体执行过程同上面讨论的添加一个事实的过程类似。此方法与其他方法相比,速度较慢。因为删除操作与添加操作的工作量几乎相同。在添加事实过程中所获得的信息并没有在执行删除操作时加以利用。下面有三种改进的算法。
在scan-based removal中,当一个连接节点的alpha内存中的某个事实w被去除时,把w传给此连接节点的输出内存,在此内存中寻找最后一个元素为w的tokens,将这些tokens删除,并且把这些tokens传给此连接节点的子节点。在在子节点中做类似删除操作。(Scales,1986)通过使用此方法代替原有方法,获得28%的加速。(Barachini,1991)获得了10%的加速。
在list-base removal和tree-based removal中使用了这样一个原理,即给事实集合以及tokens的数据结构上增添额外的指针,当某个事实被删除时,可以沿着这些指针删除需要删除的元素。
在list-based removal(Scales ,1986)中,把每个事实w上添加一个包含此事实的tokens的链表。当w被删除时,只要沿着此链表删除这些tokens。缺点就是需要大量的空间来存储链表,同时在创建一个新token时也可能花费大量的额外时间。
在tree-base removal中,在每个事实w上添加一个链表,这些链表指向把w作为最后一个元素的tokens。同时,在每个tokens上,添加一个指向此tokens的子节点的链表。当w被删除时,遍历以tokens为根的子树,删除子树上的所有元素。当然,这些额外指针将占用更多内存,同时,建立这些指针也耗费时间。经验表明,采用此方法比原始方法要节省时间。
分享到:
相关推荐
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),可以实现用自然语言方式来描述业务规则,使得业务分析...