文档章节

数学之美-【算法】 - Rete算法

止静
 止静
发布于 2014/09/18 11:24
字数 1088
阅读 4.1K
收藏 2

   

     阅读背景: 

            1: 还请您  对于【jboss rule】 有所了解

            2: 对于 【规则引擎】有所了解  

                       参考地址:http://www.cnki.com.cn/Article/CJFDTotal-JSJS200801006.htm

          

      阅读目的:

                了解什么是Rete算法,为如何将Rete算法分布式化做好准备

                  Githup参考地址:目前已经有人将Rete算法实现了Storm版本:

                            https://github.com/mmavcy/reteonstorm


       

Jena推理机的实现主要也是用的RETE算法,所以研究了RETE算法的基本流程。RETE算法是由Forgy在他的论文《A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem》中提出的。

 

1 RETE算法的基本思想 

RETE算法是一个用于产生式系统的高效模式匹配算法。在一个产生式系统中,被处理的数据叫做working memory,用于判定的规则分为两个部分LHSleft-hand-side)和RHSright hand side),分别表示前提和结论。主要流程可以分为以下步骤:

(1)Match:找出符合LHS部分的working memory集合

(2)Confilict resolution:选出一个条件被满足的规则

(3)Act:执行RHS的内容

(4)返回1  

RETE算法主要改进Match的处理过程,通过构建一个网络进行匹配。

2算法详细描述

 

RETE网络主要分为两个部分,alpha网络和beta网络。如下图所示。

 

(1)alpha网络:过滤working memory,找出符合规则中每一个模式的集合,生成alpha memory(满足该模式的集合)。有两种类型的节点,过滤type的节点和其他条件过滤的节点(我觉得这两种是依照需要设定的,也并不一定需要两种节点)。

(2)Beta网络:有两种类型的节点Beta MemoryJoin Node。前者主要存储Join完成后的集合。后者包含两个输入口,分别输入需要匹配的两个集合,由Join节点做合并工作传输给下一个节点。

3 匹配过程描述

 

 

(1)导入需要处理的事实到facts集合中。

(2)如果facts不为空,选择一个fact进行处理。否则停止匹配过程。

(3)选择alpha网的第一个节点运行(建立网络的时候设定的),通过该节点则进入alpha网的下一个节点,直到进入alpha memory。否则跳转到下一条判断路径。

(4)将alpha memory的结果加入到beta memory中,如果不为Terminal节点,则检测另一个输入集合中是否存在满足条件的事实,满足则执行join,进入到下一个beta memory重复执行(3)。若另一个输入集合无满足条件的事实,返回到(2)。如果该节点为Terminal节点,执行ACT并添加到facts中。


4 用一个例子描述过程

(1)现在WME中有以下这些事实。

w1:(B1 ^on B2)

w2:(B1 ^on B3)

w3:(B1 ^color red)

w4:(B2 ^on table)

w5:(B2 ^left-of B3)

w6:(B2 ^color blue)

w7:(B3 ^left-of B4)

w8:(B3 ^on table)

w9:(B3 ^color red)


(2)下面描述规则

下面是三条匹配条件

C1: (<x> ^on <y>)

C2:(<y> ^left-of <z>)

C3:(<z> ^color red)

下面是规则要满足的所有条件,即所有LHS

p1 has conditions C1^C2^C3

p2 has conditions C1^C2^C4^C5

p3 has conditions C1^C2^C4^C3

 

(3)推理描述

     暂且忽略图中的红色节点(用于判定类型)。那么,根据Ci,图中的蓝色alpha结点应该有三种,分别判定on,left-of和color。则黄色的alpha memory中包含三个集合,分别是满足C1:{w1 w2 w4 w8}

满足C2:{w5 w7}

满足C3:{w2 w6 w9}

     以p1为例,首先以C1,C2为输入,在绿色Dummy Input节点中进行操作,并传入到梅红色beta momory中,此时这个节点存储的是(w1^w5,w2^w7)。然后以这个集合和C3为输入,操作得出w1^w5^w9,此时发现没有更多的模式需要匹配,到达Terminal节点,匹配结束。这样就得到满足规则的集合组合了。

     接下来的时间要研究Jena中Rete算法的具体实现方式。具体的实现请参看本ID对

reteonstorm


      代码的分析。    

                        

    

  

      

© 著作权归作者所有

止静
粉丝 122
博文 134
码字总数 125762
作品 0
东城
技术主管
私信 提问
开源规则流引擎实践

基于 rete 算法的规则引擎 在 AI 领域,产生式系统是一个很重要的理论,产生式推理分为正向推理和逆向推理产生式,其规则的一般形式是:IF 条件 THEN 操作。rete 算法是实现产生式系统中正向...

银月光海
2016/02/18
353
0
大数据、机器学习及人工智能必读书目——《数学之美》

  计分析、机器学习即人工智能必读书目系列之数学之美      我们已经进入了全新的数据时代,大数据、云计算、物联网、机器学习、人工智能等等一系列技术纷至沓来,数据的管理和应用已经...

爱编程爱统计
2017/09/09
0
0
2018-10-22-今日得到-《数学之美》

今天分享的主题来自得到的每天听本书系列之《数学之美》 关于作者 吴军,得到App专栏《吴军的谷歌方法论》主理人。计算机科学家,硅谷投资人,著名自然语言处理专家和搜索专家。曾先后供职于...

韬声依旧在路上
2018/10/24
0
0
想买两本书,大家都有没有看过

今天网上逛了一下想买两本书看看,不知道这两本有没有看过的?感觉怎样? 1.算法导论,买中文版的,等我中文看懂了再去看英文版吧。 2.数学之美。网上评价不错,我数学思维不太强。 有看过的...

byhard
2012/10/24
133
2
图灵社区| 算法小时代: 从数学到生活的改变

date: 2019-01-25 21:44:30 title: 图灵社区| 算法小时代: 从数学到生活的改变 读后感 算法小简史: 算法改变了什么, 算法正在改变什么, 算法准备改变什么 偏向人文关怀的书, 没有大段大段的理...

daydaygo
2019/01/29
0
0

没有更多内容

加载失败,请刷新页面

加载更多

应急广播户户通平台

一、平台概述 应急广播户户通平台为软硬一体化广播服务解决方案。实现了应急广播、视音频及图片文字信息、调频及数字广播FM、天气预报信息接收功能,以及视音频播放、智能机器人、电子日历等...

neocean
49分钟前
47
0
如何为Apache 2.2启用mod_rewrite

我已经在我的Vista机器上安装了新的Apache 2.2,一切正常,除了mod重写。 我没有注释 LoadModule rewrite_module modules/mod_rewrite.s 但是我的重写规则都没有,即使是简单的重写规则 Re...

javail
54分钟前
23
0
移除Python unicode字符串中的重音符号的最佳方法是什么?

我在Python中有一个Unicode字符串,我想删除所有的重音符号(变音符号)。 我在网上发现了一种用Java实现此目的的优雅方法: 将Unicode字符串转换为长规范化格式(带有单独的字母和变音符号)...

技术盛宴
今天
48
0
ActiveMQ学习之SpringBoot整合ActiveMQ------>主题生产者和消费者

一、pom <!--聚合工程集成关系--> <!--统一整合第三方框架依赖信息--> <parent> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-parent</a......

冥焱
今天
89
0
两周自制脚本语言-第11天 优化变量读写性能

第11天 优化变量读写性能 以变量值的读写为例,向读者介绍基于这种理念的语言处理器性能优化方式。 11.1 通过简单数组来实现环境 假如函数包含局部变量x与y,程序可以事先将x设为数组的第0个...

果汁分你一半
今天
58
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部