Rete匹配算法是一种进行大量模式集合和大量对象集合间比较的高效方法,通过这种方法找出所有匹配各个模式的对象。
Rete算法以牺牲内存换取高速的策略
Rete算法分为两个部分:规则编译(rule compilation)、运行时执行(runtime execution).
规则编译
功能:如何在Production Memory中产生一个有效的辨别网络,它具有过滤数据功能
方法:数据通过在网络中流通被过滤。在顶端节点(RootNode)会有很多匹配的数据,经过中间的一些节点(**Node)过滤而变少,最后到达终端节点(TerminalNode)。
在1982年Forgy的论文("Rete: A Fast Algorithm for the Many Pattern/ Many Object Pattern Match Problem", Charles L. Forgy, Artificial Intelligence 19 (1982), 17-37)中,他描述了4种节点:
RootNode
所有对象进入网络的入口,进入后立即进入ObjectTypeNode。ObjectTypeNode确保引擎接下来只作它需要做的事情,即对对相进行过滤、分拣。ObjectTypeNode后流入:AlphaNodes, LeftInputAdapterNodes和BetaNodes。
1-input 通称AlphaNode
AlphaNode用来评估字面条件(literal conditions),当一个对象有多个字面条件的话,逐条评估顺序进入相应AlphaNode。
Drools用散列法优化从ObjectTypeNode到AlphaNode的流向。即以字面值(literal value)为Key,以AlphaNode为Value加入HashMap。这样进入ObjectTypeNOde的对象根据HashMap就可以找到确切的AlphaNode.
2-input 通称BetaNode
用来对2个队形进行比较,他们可以是同种或不同种类型,分别叫作左边(LHS left-hand-side)和右边(RHS right-hand-side)。一个BetaNode的左边输入通常是一组对象,右边输入是单个对象。
如果左边输入的是单个对象怎么办?用适配器LeftInputAdapterNode。它将单个对象转化为一个单对象数组(Single Object Tuple),然后再作为左边传到JoinNode。
Drools中有两种:JoinNode和NotNode。左边输入是一个对象数组。NotNode可以完成“exists”检查。Drools通过将所因应用在BetaNodes上扩展了Rete算法(??)。
TerminalNode
用来表明一条规则已经匹配了他的所有条件(conditions),这条规则有了一个完全的匹配(full match)。
一条规则可以有不止一个TerminalNode,如:带“or”规则。
多个规则间肯能存在部分相同的条件,在规则引擎编译过程中就表现为存在相同的节点。为了提高性能,Drools进行了节点共享。
运行时执行
当一个应用assert一个对象,引擎将数据传递到root node,中这里开始遍历网络。当对象匹配一个节点的条件,节点就将它记录到相应的内存中(可以带来更快的性能)(这里是不是就是用索引?为了尽量少用内存)。
分享到:
相关推荐
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算法
Treat 算法论文原文 英文 treat 算法 rete算法相关 This paper presents the TREAT match algorithm for AI production systems. The TREAT algorithm introduces a new method of state saving in production ...