`
daniel_tu
  • 浏览: 184566 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
社区版块
存档分类
最新评论

JBoss Rules 学习(二): RETE算法

阅读更多

JBoss Rules 学习(一):什么是Rule 中, 我们介绍了JBoss Rules中对Rule的表示,其中提到了JBoss Rule中主要采用的RETE算法来进行规则匹配。下面将详细的介绍一下RETE算法在JBoss Rule中的实现,最后随便提一下JBoss Rules中也可以使用的另一种规则匹配算法Leaps。

1.Rete 算法

Rete 在拉丁语中是 ”net” ,有网络的意思。 RETE 算法可以分为两部分:规则编译( rule compilation )和运行时执行( runtime execution )。

编译算法描述了规则如何在 Production Memory 中产生一个有效的辨别网络。用一个非技术性的词来说,一个辨别网络就是用来过滤数据。方法是通过数据在网络中的传播来过滤数据。在顶端节点将会有很多匹配的数据。当我们顺着网络向下走,匹配的数据将会越来越少。在网络的最底部是终端节点( terminal nodes )。在 Dr Forgy 1982 年的论文中,他描述了 4 种基本节点: root , 1-input, 2-input and terminal 。下图是 Drools 中的 RETE 节点类型:

 

Figure 1. Rete Nodes

根节点( RootNode )是所有的对象进入网络的入口。然后,从根节点立即进入到 ObjectTypeNode ObjectTypeNode 的作用是使引擎只做它需要做的事情。例如,我们有两个对象集: Account Order 。如果规则引擎需要对每个对象都进行一个周期的评估,那会浪费很多的时间。为了提高效率,引擎将只让匹配 object type 的对象通过到达节点。通过这种方法,如果一个应用 assert 一个新的 account ,它不会将 Order 对象传递到节点中。很多现代 RETE 实现都有专门的 ObjectTypeNode 。在一些情况下, ObjectTypeNode 被用散列法进一步优化。

Figure 2 . ObjectTypeNodes

ObjectTypeNode 能够传播到 AlphaNodes, LeftInputAdapterNodes BetaNodes

1-input 节点通常被称为 AlphaNode AlphaNodes 被用来评估字面条件( literal conditions )。虽然, 1982 年的论文只提到了相等条件(指的字面上相等),很多 RETE 实现支持其他的操作。例如, Account.name = = “Mr Trout” 是一个字面条件。当一条规则对于一种 object type 有多条的字面条件,这些字面条件将被链接在一起。这是说,如果一个应用 assert 一个 account 对象,在它能到达下一个 AlphaNode 之前,它必须先满足第一个字面条件。在 Dr. Forgy 的论文中,他用 IntraElement conditions 来表述。下面的图说明了 Cheese AlphaNode 组合( name = = “cheddar” strength = = “strong” ):

Figure 3. AlphaNodes

 

Drools 通过散列法优化了从 ObjectTypeNode AlphaNode 的传播。每次一个 AlphaNode 被加到一个 ObjectTypeNode 的时候,就以字面值( literal value )作为 key ,以 AlphaNode 作为 value 加入 HashMap 。当一个新的实例进入 ObjectTypeNode 的时候,不用传递到每一个 AlphaNode ,它可以直接从 HashMap 中获得正确的 AlphaNode ,避免了不必要的字面检查。

<!-- [if !supportEmptyParas]-->

2-input 节点通常被称为 BetaNode Drools 中有两种 BetaNode JoinNode NotNode BetaNodes 被用来对 2 个对象进行对比。这两个对象可以是同种类型,也可以是不同类型。

我们约定 BetaNodes 2 个输入称为左边( left )和右边( right )。一个 BetaNode 的左边输入通常是 a list of objects 。在 Drools 中,这是一个数组。右边输入是 a single object 。两个 NotNode 可以完成‘ exists ’检查。 Drools 通过将索引应用在 BetaNodes 上扩展了 RETE 算法。下图展示了一个 JoinNode 的使用:

Figure 4 . JoinNode


注意到图中的左边输入用到了一个 LeftInputAdapterNode ,这个节点的作用是将一个 single Object 转化为一个单对象数组( single Object Tuple ),传播到 JoinNode 节点。因为我们上面提到过左边输入通常是 a list of objects

<!-- [if !supportEmptyParas]-->

Terminal nodes 被用来表明一条规则已经匹配了它的所有条件( conditions )。 在这点,我们说这条规则有了一个完全匹配( full match )。在一些情况下,一条带有“或”条件的规则可以有超过一个的 terminal node

Drools 通过节点的共享来提高规则引擎的性能。因为很多的规则可能存在部分相同的模式,节点的共享允许我们对内存中的节点数量进行压缩,以提供遍历节点的过程。下面的两个规则就共享了部分节点:

rule
    when
        Cheese( $chedddar : name 
==   " cheddar "  )
        $person : Person( favouriteCheese 
==  $cheddar )
    then
        System.out.println( $person.getName() 
+   "  likes cheddar "  );
end


<!-- <br><br>Code highlighting produced by Actipro CodeHighlighter (freeware)<br>http://www.CodeHighlighter.com/<br><br>--> rule
    when
        Cheese( $chedddar : name 
==   " cheddar "  )
        $person : Person( favouriteCheese 
!=  $cheddar )
    then
        System.out.println( $person.getName() 
+   "  does likes cheddar "  );
end

 

这里我们先不探讨这两条 rule 到的是什么意思,单从一个直观的感觉,这两条 rule 在它们的 LHS 中基本都是一样的,只是最后的 favouriteCheese ,一条规则是等于 $cheddar ,而另一条规则是不等于 $cheddar 。下面是这两条规则的节点图:

 

Figure 5 . Node Sharing

从图上可以看到,编译后的 RETE 网络中, AlphaNode 是共享的,而 BetaNode 不是共享的。上面说的相等和不相等就体现在 BetaNode 的不同。然后这两条规则有各自的 Terminal Node

<!-- [if !supportEmptyParas]-->

RETE 算法的第二个部分是运行时( runtime )。当一个应用 assert 一个对象,引擎将数据传递到 root node 。从那里,它进入 ObjectTypeNode 并 沿着网络向下传播。当数据匹配一个节点的条件,节点就将它记录到相应的内存中。这样做的原因有以下几点:主要的原因是可以带来更快的性能。虽然记住完全或 部分匹配的对象需要内存,它提供了速度和可伸缩性的特点。当一条规则的所有条件都满足,这就是完全匹配。而只有部分条件满足,就是部分匹配。(我觉得引擎 在每个节点都有其对应的内存来储存满足该节点条件的对象,这就造成了如果一个对象是完全匹配,那这个对象就会在每个节点的对应内存中都存有其映象。)

 

2. Leaps 算法:

 

Production systems Leaps 算法使用了一种“ lazy ”方法来评估条件( conditions )。一种 Leaps 算法的修改版本的实现,作为 Drools v3 的一部分,尝试结合 Leaps RETE 方法的最好的特点来处理 Working Memory 中的 facts

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

分享到:
评论

相关推荐

    解压软件 ZArchiver.apk

    解压软件 ZArchiver.apk

    毕设项目:基于SSM框架+mysql开发的教务管理系统分前后台【附含源码+数据库+毕业论文】

    二、技术实现 后端:spring,springmvc,mybatis,mysql 前端采用:vue,css 运行环境及开发工具:jdk8,idea或者eclipse,Navicat 三、系统功能 系统登录角色分为:管理员、老师、学生 用户登录 用户注册 首页 个人中心 修改密码 个人信息 班级管理 成绩类型管理 公告类型管理 教程类型管理 第几节管理 院系管理 职称管理 专业管理 公告管理 课程管理 成绩管理等功能

    设计和仿真一个用于控制双质量弹簧阻尼系统位移的多变量控制系统.docx

    设计和仿真一个用于控制双质量弹簧阻尼系统位移的多变量控制系统.docx

    1-全国各地级市金融机构本外币与人民币存款和贷款2010-2020年-社科数据.zip

    这份数据集详细记录了2010至2020年间中国各城市金融机构的本外币存款和人民币贷款情况。数据涵盖了商业银行、农村合作银行、信用社等多种金融机构的存款数据,包括本币和外币存款情况。这些数据不仅反映了各城市金融机构的存款规模,也为分析金融市场的发展趋势、资金流动状况及城市经济活动提供了重要视角。数据来源于中国区域统计年鉴和各省市统计年鉴,以面板数据形式呈现,包含1948个样本。通过这些数据,金融机构、政策制定者、研究人员和投资者可以深入了解各城市的金融市场格局,辅助做出更准确的决策和分析。

    开发一个带有 PCIe Endpoint 设备的驱动程序并实现热插拔功能.docx

    开发一个带有 PCIe Endpoint 设备的驱动程序并实现热插拔功能

    NovaMaker-2.4.29-win-64-bit.zip

    NovaMaker-2.4.29-win-64-bit.zip

    Spring Boot相关的资源.txt

    Spring Boot相关的资源.txt

    Hive简易操作入门中文最新版本

    本文档主要讲述的是Hive简易操作入门;本流程中以putty为例,如果使用别的SSH客户端,界面上会不同,基本过程相似。希望本文档会给有需要的朋友带来帮助;感兴趣的朋友可以过来看看

    ASP+ACCESS软件信息发布系统设计(源代码+论文+开题报告+任务书+答辩PPT)(源代码+论文+说明文档).zip

    【项目资源】:包含前端、后端、移动开发、操作系统、人工智能、物联网、信息化管理、数据库、硬件开发、大数据、课程资源、音视频、网站开发等各种技术项目的源码。包括STM32、ESP8266、PHP、QT、Linux、iOS、C++、Java、python、web、C#、EDA、proteus、RTOS等项目的源码。【项目质量】:所有源码都经过严格测试,可以直接运行。功能在确认正常工作后才上传。【适用人群】:适用于希望学习不同技术领域的小白或进阶学习者。可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。【附加价值】:项目具有较高的学习借鉴价值,也可直接拿来修改复刻。对于有一定基础或热衷于研究的人来说,可以在这些基础代码上进行修改和扩展,实现其他功能。【沟通交流】:有任何使用上的问题,欢迎随时与博主沟通,博主会及时解答。鼓励下载和使用,并欢迎大家互相学习,共同进步。

    浅析Sybase数据库系统性能调优中文最新版本

    本文档主要讲述的是浅析Sybase数据库系统性能调优;性能调优”是对应用程序的性能优化。SYBASE数据库“性能调优”的主要目的是减少对系统公共资源的争用。对sybase数据库系统的性能进行优化,是一项长期且受诸多因素影响的工作,希望本文档会给有需要的朋友带来帮助;感兴趣的朋友可以过来看看

    用VBS制作自己的进度条

    用VBS制作自己的进度条

    校际运动会管理系统程序设计基础课程设计报告.doc

    校际运动会管理系统程序设计基础课程设计报告.doc

    ORACLECRS日常维护命令中文最新版本

    本文档主要讲述的是ORACLE CRS日常维护命令;希望本文档会给有需要的朋友带来帮助;感兴趣的朋友可以过来看看

    [net毕业设计]ASP.NET教务信息管理系统的设计与实现(源代码+论文).zip

    【项目资源】:包含前端、后端、移动开发、操作系统、人工智能、物联网、信息化管理、数据库、硬件开发、大数据、课程资源、音视频、网站开发等各种技术项目的源码。包括STM32、ESP8266、PHP、QT、Linux、iOS、C++、Java、python、web、C#、EDA、proteus、RTOS等项目的源码。【项目质量】:所有源码都经过严格测试,可以直接运行。功能在确认正常工作后才上传。【适用人群】:适用于希望学习不同技术领域的小白或进阶学习者。可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。【附加价值】:项目具有较高的学习借鉴价值,也可直接拿来修改复刻。对于有一定基础或热衷于研究的人来说,可以在这些基础代码上进行修改和扩展,实现其他功能。【沟通交流】:有任何使用上的问题,欢迎随时与博主沟通,博主会及时解答。鼓励下载和使用,并欢迎大家互相学习,共同进步。

    1-全国各省商品市场分割指数相对价格法计算过程+计算结果2000-2020年-社科数据.zip

    全国各省商品市场分割指数相对价格法的计算过程和结果数据集提供了2000至2020年间中国各省份市场分割的量化分析。该数据集基于12大类商品,包括粮食、纺织品、服装鞋帽等,利用地区间商品价格差异来分析市场分割状况。核心计算方法为相对价格法,通过比较不同地区同一商品的价格指数,来衡量市场分割程度。数据集包含原始数据、计算过程和最终结果,原始数据主要来源于统计年鉴中的商品价格指数。计算步骤包括计算历年资本边际产出比值、求均值、方差等,最终得出资本市场一体化程度。该数据集为研究中国国内市场一体化进程提供了重要参考。

    1-全国上市公司绿色投资者原始数据+计算代码+参考文献2008-2022年-社科数据.zip

    全国上市公司绿色投资者数据集(2008-2022年)提供了中国上市公司在环保和可持续发展方面的资金吸引力的详细视角。该数据集涵盖了股票代码、年份、会计年度、股票简称、STPT标识、行业名称及代码,以及绿色投资者数量等关键指标。它记录了超过42,000个观测值,涉及4,700多家样本企业,为投资者、金融分析师、政策制定者和环境研究者提供了评估企业环保表现、理解绿色投资趋势以及制定相关策略的辅助工具。数据集包括是否有绿色投资者的虚拟变量,以及绿色投资者数目加1的自然对数两个指标,可以用于衡量企业绿色治理情况。这些数据不仅展示了中国上市公司在环境保护方面的资金流向,也反映了投资者对绿色投资的关注动态,对于研究绿色投资与企业行为的关系提供了宝贵的实证数据支持。

    15da2b5d3ceeddc8af2f6a7eed26d7e0.JPG

    15da2b5d3ceeddc8af2f6a7eed26d7e0.JPG

    前端工程化实践课程下载

    视频课程下载——前端工程化实践

    yolo算法-行人数据集-7203张图像带标签-人-主人.zip

    yolo系列算法目标检测数据集,包含标签,可以直接训练模型和验证测试,数据集已经划分好,包含数据集配置文件data.yaml,适用yolov5,yolov8,yolov9,yolov7,yolov10,yolo11算法; 包含两种标签格:yolo格式(txt文件)和voc格式(xml文件),分别保存在两个文件夹中; yolo格式:<class> <x_center> <y_center> <width> <height>, 其中: <class> 是目标的类别索引(从0开始)。 <x_center> 和 <y_center> 是目标框中心点的x和y坐标,这些坐标是相对于图像宽度和高度的比例值,范围在0到1之间。 <width> 和 <height> 是目标框的宽度和高度,也是相对于图像宽度和高度的比例值

    模拟电路.txtrdhhffthg

    c语言入门

Global site tag (gtag.js) - Google Analytics