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

一:规则引擎
--->规则引擎的核心是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算法,使用的范围不是很广,这里不做过多的介绍。

时间: 2024-10-22 22:26:17

【java规则引擎】之Drools之Rete算法的相关文章

Java规则引擎工作原理及其应用

摘 要 Java规则引擎是一种嵌入在Java程序中的组件,它的任务是把当前提交给引擎的Java数据对象与加载在引擎中的业务规则进行测试和比对,激活那些符合当前数据状态下的业务规则,根据业务规则中声明的执行逻辑,触发应用程序中对应的操作. 引言 目前,Java社区推动并发展了一种引人注目的新技术--Java规则引擎(Rule Engine).利用它就可以在应用系统中分离商业决策者的商业决策逻辑和应用开发者的技术决策,并把这些商业决策放在中心数据库或其他统一的地方,让它们能在运行时可以动态地管理和修

Java规则引擎工作原理及应用

引言 目前,Java社区推动并发展了一种引人注目的新技术--Java规则引擎(Rule Engine).利用它就可以在应用系统中分离商业决策者的商业决策逻辑和应用开发者的技术决策,并把这些商业决策放在中心数据库或其他统一的地方,让它们能在运行时可以动态地管理和修改,从而为企业保持灵活性和竞争力提供有效的技术支持. 规则引擎的原理 1.基于规则的专家系统(RBES)简介 Java规则引擎起源于基于规则的专家系统,而基于规则的专家系统又是专家系统的其中一个分支.专家系统属于人工智能的范畴,它模仿人类

【java规则引擎】之规则引擎解释

转载:http://www.open-open.com/lib/view/open1417528754230.html 现实生活中,规则无处不在.法律.法规和各种制度均是:对于企业级应用来说,在IT技术领域,很多地方也应用了规则,比如路由表,防火墙策略,乃至角色权限控制(RBAC),或者Web框架中的URL匹配.不管是那种规则,都规定了一组确定的条件和此条件所产生的结果. 举一个例子: IF 汽车是红色车是运动型的驾驶员是男性驾驶员在16-25岁之间THEN 保险费用增加20% 从这个例子可以看

Java规则引擎与其API应用详解

详解 本文对Java规则引擎与其API(JSR-94)及相关实现做了较详细的介绍,对其体系结构和API应用有较详尽的描述,并指出Java规则引擎,规则语言,JSR-94的相互关系,以及JSR-94的不足之处和展望 本文对Java规则引擎与其API(JSR-94)及相关实现做了较详细的介绍,对其体系结构和API应用有较详尽的描述,并指出Java规则引擎,规则语言,JSR-94的相互关系,以及JSR-94的不足之处和展望 复杂企业级项目的开发以及其中随外部条件不断变化的业务规则(business l

详解什么是Java规则引擎(上)

问题描述 本文对Java规则引擎与其API(JSR-94)及相关实现做了较详细的介绍,对其体系结构和API应用有较详尽的描述,并指出Java规则引擎,规则语言,JSR-94的相互关系,以及JSR-94的不足之处和展望 复杂企业级项目的开发以及其中随外部条件不断变化的业务规则(businesslogic),迫切需要分离商业决策者的商业决策逻辑和应用开发者的技术决策,并把这些商业决策放在中心数据库或其他统一的地方,让它们能在运行时(即商务时间)可以动态地管理和修改从而提供软件系统的柔性和适应性.规则

Java规则引擎与其API(JSR-94)

简介:本文对Java规则引擎与其API(JSR-94)及相关实现做了较详细的介绍,对其体系结构和API应用 有较详尽的描述,并指出Java规则引擎,规则语言,JSR-94的相互关系,以及JSR-94的不足之处和展望 复杂企业级项目的开发以及其中随外部条件不断变化的业务规则(business logic),迫切需要分离 商业决策者的商业决策逻辑和应用开发者的技术决策,并把这些商业决策放在中心数据库或其他统一的地 方,让它们能在运行时(即商务时间)可以动态地管理和修改从而提供软件系统的柔性和适应性.

jboss规则引擎KIE Drools 6.3.0-高级讲授篇

在生产环境怎么用BRMS 回溯BRMS开发教程中的那张"业务变现加速器"架构图,考虑下面的问题 业务开发人员开发规则 IT人员提供FACT 关键在于"全动态" SQL语句改了怎么办?不重启 DAO层改了怎么办?不重启 Mybatis的配置文件改了怎么办?不重启 按照上次的<jboss规则引擎KIE Drools 6.3.0 Final 教程>,一起来看一个实际的场景 如何熊掌与鱼兼得? 做到以下几点是否就可以"全得"? 规则更改不重启

【java规则引擎】模拟rete算法的网络节点以及匹配过程

转载请注明:http://www.cnblogs.com/shangxiaofei/p/6340655.html 本文只用于理解rete算法,通过一个规则的编译成的网络结构,以及匹配过程去理解rete算法的核心思想.具体实现,截止写本文之时,还不了解.只是提供一个rete算法的实现思路.再次重申,只用于理解rete算法.如有不正确,请交流指正,一定会非常感谢.     (1)规则内容 IF: 年级是三年级以上, 性别是男的, 年龄小于10岁, 身体健壮, 身高170cm以上,   THEN: 这

【java规则引擎】之Drools引擎中模拟ReteooStatefulSession内部设计结构

该片文章只是抽取drools中java代码实现的一些代码结构,帮助我们理解drools是如何实现rete算法的. 该部分只是抽取ReteooStatefulSession工作过程中的代码架构        利用了多线程设计的一个代理模式(自己起的名字) 利用了23中设计模式中的命令模式 一:模拟drools中ReteooStatefulSession的实现对象StatefulSession 1 package com.nonbankcard.drools.module; 2 3 4 5 /**