【java规则引擎】之Drools之Rete算法

简介: 一:规则引擎--->规则引擎的核心是Pattern Matcher(模式匹配器)。不管是正向推理还是反向推理,首先要解决一个模式匹配的问题。--->对于规则的模式匹配,可以定义为: 一个规则是一组模式的集合。

一:规则引擎
--->规则引擎的核心是Pattern Matcher(模式匹配器)。不管是正向推理还是反向推理,首先要解决一个模式匹配的问题。

--->对于规则的模式匹配,可以定义为: 一个规则是一组模式的集合。如果事实/假设的状态符合该规则的所有模式,则称为该规则是可满足的。 模式匹配的任务就是将事实/假设的状态与规则库中的规则一一匹配,找到所有可满足的规则。



二:什么是模式匹配

对于模式匹配我们都应该不陌生,我们经常使用的正则表达式就是一种模式匹配。

正则表达式是一种“模式(pattern)”,
编程语言提供的“正则表达式引擎”就是Pattern Matcher。比如python中的re模块。
首先输入“知识”:re.compile(r'string'),
然后就可以让其匹配(match)事实(字符串)。
最后通过正则表达式引擎可以得到匹配后的结果。
对于规则匹配,通常定义如下:

条件部分,也称为LHS(left-hand side)
事实部分,也称为RHS(right-hand side)
假设系统中有N条规则,平均每个规则的条件部分有P个模式,在某个时点有M个事实需要处理。则规则匹配要做的事情就是: 对每一个规则r,判断当前的事实o是否满足LHS(r)=True,如果满足,则将规则r的实例r(o),即规则+满足该规则的事实,加到冲突集中等待处 理。 通常采取如下过程:

从N条规则中取出一条r;
从M个事实中取出P个事实的一个组合c;
用c测试LHS(r),如果LHS(r(c))=True,将RHS(r(c))加入队列中;
如果M个事实还存在其他的组合c,goto 3;
取出下一条规则r,goto 2;
实际的问题可能更复杂,在规则的执行过程中可能会改变RHS的数据,从而使得已经匹配的规则实例失效或者产生新的满足规则的匹配,形成一种“动态”的匹配链。



三:模式匹配算法

上面的处理由于涉及到组合,过程很复杂。有必要通过特定的算法优化匹配的效率。目前常见的模式匹配算法包括Rete、Treat、Leaps,HAL,Matchbox等。





四:Rete算法

Rete算法是目前使用最广泛的规则匹配算法,由Charles L. Forgy博士在1979年发明。Rete算法是一种快速的Forward-Chaining推理算法,其匹配速度与规则的数量无关。 Rete的高效率主要来自两个重要的假设:

时间冗余性。 facts在推理过程中的变化是缓慢的, 即在每个执行周期中,只有少数的facts发生变化,因此影响到的规则也只占很小的比例。所以可以只考虑每个执行周期中已经匹配的facts.
结构相似性。许多规则常常包含类似的模式和模式组。
Rete算法的基本思想是保存过去匹配过程中留下的全部信息,以空间代价来换取执行效率 。对每一个模式 ,附加一个匹配元素表来记录WorkingMemory中所有能与之匹配的元素。当一个新元素加入到WorkingMemory时, 找出所有能与之匹配的模式, 并将该元素加入到匹配元素表中; 当一个无素从WorkingMemory中删除时,同样找出所有与该元素匹配的模式,并将元素从匹配元素表中删除。 Rete算法接受对工作存储器的修改操作描述 ,产生一个修改冲突集的动作 。

Rete算法的步骤如下:

将初始数据(fact)输入Working Memory。
使用Pattern Matcher比较规则(rule)和数据(fact)。
如果执行规则存在冲突(conflict),即同时激活了多个规则,将冲突的规则放入冲突集合。
解决冲突,将激活的规则按顺序放入Agenda。
使用规则引擎执行Agenda中的规则。重复步骤2至5,直到执行完毕所有Agenda中的规则。
五:Tread算法

在 Rete算法中 ,同一规则连接结点上的寄存器保留了大量的冗余结果。实际上, 寄存器中大部分信息已经体现在冲突集的规则实例中。因此 ,如果在部分匹配过程中直接使用冲突集来限制模式之间的变量约束,不仅可以减少寄存器的数量 ,而且能够加快匹配处理效率 。这一思想称为 冲突集支撑策略 。

考虑增删事实对匹配过程的影响,当向工作存储器增加一个事实时 ,冲突集中已有的规则实例仍然保留,只是将与该事实匹配的规则实例加入到冲突集中; 当从工作存储器删去一个事实时,不可能有新的规则实例产生, 只是将 包含该事实的规则实例从冲突集中删去。

基于冲突集支撑策略和上述观察, Treat算法放弃了Rete算法中利用寄存器保存模式之间变量约束中间结果的思想,对于每一个模式 ,除保留原有 a寄存器的外 ,增加两个新链来记录与该模式匹配的增删事实,一个叫做增链 (addlist),另一个叫做删链 (deletelist)。当修改描述的操作符为 “+”时,临时执行部分连接任务;当修改描述的操作符为 “一”时,直接删去冲突集中包含该事实的规则实例。

Treat算法的步骤如下:

行动 :根据点火规则的 RHS,生成修改描述表 CHANGES;
模式匹配:置每一模式的删链和增链为空,对 CHANGES的每一个修改描述 ,执行模式匹配。对于与修改描述中的事实匹配成功的模式,若修改描述的操作符为 “+”, 将该事实加入这一模式的增链;若修改描述的操作符为 “一”,将该事实加入这一模式的 删链。
删去事实的处理:对于任一模式链中的每一个事实,找到冲突集中所有包含该事实 的规则实例,并将这一规则实例从冲突集中删去。相应地修改该模式的 a寄存器 。
新增事实的处理:对 于 每 一 模 式 ,若 其 增 链 非 空 ,则 将 增 链 中 的 所 有 事 实 加 入 该 模 式的a寄存器 ,并对与新增事实相关的每一条规则临时执行部分匹配,寻找该规则新的实 例。具体做法为:首先将第一个模式增链中的事实集合与后一模式的 a寄存器进行连接 , 再将部分连接结果与第三个模式的a寄存器进行连接 ,一直到所有模式均连接完成为止。 其中 ,a寄存器 的内容包括新增 事实。若连接结果非空 ,则将找到 的规则 实例插入到冲突 集中。
六:Leaps 算法

前向推理引擎,包括LEAPS,都包括了匹配-选择-执行(match-select-action)循环。即,确定可以匹配的规则,选择某个匹配 的元 组,此元组相应的规则动作被执行。重复这一过程,直到某一状态(如没有更多的规则动作)。RETE和TREAT匹配算法速度慢的原因是,它们把满足规则条 件的元组都实例化。Leaps算法的最大的改进就是使用一种"lazy"的方法来评估条件(conditions),即仅当必要时才进行元组的实例化。这 一改进极大的减少了前向推理引擎的时空复杂度,极大提高了规则执行速度。

Leaps算法将所有的 asserted 的 facts ,按照其被 asserted 在 Working Memory 中的顺序( FIFO ),放在主堆栈中。它一个个的检查 facts ,通过迭代匹配 data type 的 facts 集合来找出每一个相关规则的匹配。当一个匹配的数据被发现时,系统记住此时的迭代位置以备待会的继续迭代,并且激发规则结果( consequence )。当结果( consequence )执行完成以后,系统就会继续处理处于主堆栈顶部的 fact 。如此反复。

Leaps算法的效率可以比Rete算法和Tread算法高几个数量级。

七:其他算法

对于HAL算法和Matchbox算法,使用的范围不是很广,这里不做过多的介绍。

目录
打赏
0
0
0
1
11
分享
相关文章
大数据大厂之MySQL数据库课程设计:揭秘MySQL集群架构负载均衡核心算法:从理论到Java代码实战,让你的数据库性能飙升!
本文聚焦 MySQL 集群架构中的负载均衡算法,阐述其重要性。详细介绍轮询、加权轮询、最少连接、加权最少连接、随机、源地址哈希等常用算法,分析各自优缺点及适用场景。并提供 Java 语言代码实现示例,助力直观理解。文章结构清晰,语言通俗易懂,对理解和应用负载均衡算法具有实用价值和参考价值。
大数据大厂之MySQL数据库课程设计:揭秘MySQL集群架构负载均衡核心算法:从理论到Java代码实战,让你的数据库性能飙升!
上网行为监控系统剖析:基于 Java LinkedHashMap 算法的时间序列追踪机制探究
数字化办公蓬勃发展的背景下,上网行为监控系统已成为企业维护信息安全、提升工作效能的关键手段。该系统需实时记录并深入分析员工的网络访问行为,如何高效存储和管理这些处于动态变化中的数据,便成为亟待解决的核心问题。Java 语言中的LinkedHashMap数据结构,凭借其独有的有序性特征以及可灵活配置的淘汰策略,为上网行为监控系统提供了一种兼顾性能与功能需求的数据管理方案。本文将对LinkedHashMap在上网行为监控系统中的应用原理、实现路径及其应用价值展开深入探究。
67 3
LRU算法的Java实现
LRU(Least Recently Used)算法用于淘汰最近最少使用的数据,常应用于内存管理策略中。在Redis中,通过`maxmemory-policy`配置实现不同淘汰策略,如`allkeys-lru`和`volatile-lru`等,采用采样方式近似LRU以优化性能。Java中可通过`LinkedHashMap`轻松实现LRUCache,利用其`accessOrder`特性和`removeEldestEntry`方法完成缓存淘汰逻辑,代码简洁高效。
Java中的对称加密算法的原理与实现
本文详细解析了Java中三种常用对称加密算法(AES、DES、3DES)的实现原理及应用。对称加密使用相同密钥进行加解密,适合数据安全传输与存储。AES作为现代标准,支持128/192/256位密钥,安全性高;DES采用56位密钥,现已不够安全;3DES通过三重加密增强安全性,但性能较低。文章提供了各算法的具体Java代码示例,便于快速上手实现加密解密操作,帮助用户根据需求选择合适的加密方案保护数据安全。
172 58
我们来说一说 Java 的一致性 Hash 算法
我是小假 期待与你的下一次相遇 ~
企业上网监控场景下布隆过滤器的 Java 算法构建及其性能优化研究
布隆过滤器是一种高效的数据结构,广泛应用于企业上网监控系统中,用于快速判断员工访问的网址是否为违规站点。相比传统哈希表,它具有更低的内存占用和更快的查询速度,支持实时拦截、动态更新和资源压缩,有效提升系统性能并降低成本。
24 0
如何监控员工的电脑——基于滑动时间窗口的Java事件聚合算法实现探析​
在企业管理场景中,如何监控员工的电脑操作行为是一个涉及效率与合规性的重要课题。传统方法依赖日志采集或屏幕截图,但数据量庞大且实时性不足。本文提出一种基于滑动时间窗口的事件聚合算法,通过Java语言实现高效、低资源占用的监控逻辑,为如何监控员工的电脑提供一种轻量化解决方案。
73 3
解锁“分享文件”高效密码:探秘 Java 二叉搜索树算法
在信息爆炸的时代,文件分享至关重要。二叉搜索树(BST)以其高效的查找性能,为文件分享优化提供了新路径。本文聚焦Java环境下BST的应用,介绍其基础结构、实现示例及进阶优化。BST通过有序节点快速定位文件,结合自平衡树、多线程和权限管理,大幅提升文件分享效率与安全性。代码示例展示了文件插入与查找的基本操作,适用于大规模并发场景,确保分享过程流畅高效。掌握BST算法,助力文件分享创新发展。
解锁分布式文件分享的 Java 一致性哈希算法密码
在数字化时代,文件分享成为信息传播与协同办公的关键环节。本文深入探讨基于Java的一致性哈希算法,该算法通过引入虚拟节点和环形哈希空间,解决了传统哈希算法在分布式存储中的“哈希雪崩”问题,确保文件分配稳定高效。文章还展示了Java实现代码,并展望了其在未来文件分享技术中的应用前景,如结合AI优化节点布局和区块链增强数据安全。

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问