rete算法简介

  Rete算法是Charles Forgy在1979年的论文中首次提出的，针对基于规则知识表现的模式匹配算法。目前来说，大部分规则引擎还是基于rete算法作为核心，但都有所改进，比如drool，jess等等，下面介绍rete算法的概念，一些术语，以及使用规则引擎需要注意的问题。

  先来看看如下的表达式：

     (name-of-this-production
        LHS /* one or more conditions */
       -->
        RHS /* one or more actions */
      )

 

   name-of-this-production就是规则，LHS（left hand side）一系列条件，RHS（right hand side）这个是我们满足条件后应该执行的动作。

    

     

 

     

 

 

   结合该图介绍几个概念：

    production memory（PM）是由所有的production形成。

    working memory（WM）由外界输入根据匹配算法形成的，反映了运行中的规则引擎的状态，记录各种数据， WM中每一个item称为working memory element（WME） ，由外界的输入产生。

    agenda负责匹配，冲突解决，执行动作。

   

    rete是网络的意思（拉丁语），它将所有的规则最终解释（或编译）生成一个识别网络，其中包括了alpha网络，beta网络。alpha网络是根据LHS生成的网络，它根据外界的输入快速识别是否存在condition成立，并且跟其beta网络交互更新整个网络的状态，如下图：

 

     

    最基本的alpha网络就如上图所示，类似于这样，所有的condition被parse到这样的网络，当外界输入wme时，该wme会进入这样一个网络进行辨识，如果到达最底端，证明一个condition成立了，当然，如图这个网络算是最简单的实现了，实际规则引擎需要提供更快速的算法去辨识输入的wme，比如将图中color的各种值存入hashtable，或者是jumptable，又或者是trie tree。整个alpha network是一个巨大的字符串匹配和过滤网络，需要将各种数据结构组合在一起去实现海量condition情况下的快速匹配。各种规则引擎的实现又是不一致的，比如jess，如下图：

 

    (defrule done
       (TESTING)
       (number ?number)
       (TEST IS DONE)
       (INIT CREDIT 5)
       (CUSTOMER AGE ?age)
       (has ?type "PP"))
=>
     (assert (TEST COMPLETED)))

 

    
这个production的解释后生成的网络，这里我们先注意红色的节点，这些节点就是alpha网络的节点，这个图只是描述了大致的过程，以第一列为例，第一个红色node表示输入是否匹配TESTING这个字符串，第二个node匹配在TESTING后面的参数数量（slot）是否匹配0，如果我们assert TESTING进入WM，那么这个fact是可以匹配到done这个rule的第一个condition的，其他可以依次类推，值得注意的是最后一个condition，has是我们自定义的function，类似这样的function，jess没有单独生成一列，只是将它作为CUSTOMER AGE ?age这一列的最后一个node，这样的condition有个特点就是需要执行一段代码去判断某个事实是否成立（不仅仅只是做字符串的操作），这段代码不仅仅是字符串的匹配，同时还具有实时性，类似这样的condition开发中需要注意，因为alpha network在运行期会不止一次去执行这个condition是否成立，这个是匹配算法的特性决定，所以，我们需要用cache或者规则语言的特性去避免不必要的执行code以提高性能。

  下面贴个比较复杂的例子：

   
 

 

   图太大，一个截不下来。。。。。。

   下面我们结合两个例子说说beta网络，当alpha网络过滤后condition成立，WME被传递到beta网络时，绿色的node就要发挥作用了，这个node就是join node，它有两个input，一个join node ，一个alpha node（红色），join node是由多个WME组成的，对于初始的join node 我们称为left input adapter 如图中黄色的node，该node是空的，那么第一个把这个node作为left input的join node就只包含了一个WME，下一个join node则包含了两个WME，以此类推。图中天蓝色的node上方的join node 完全匹配了production执行需要的condition，所以这个rule就被激活等待执行了。

 

    假设我们需要编辑业务逻辑，那么最好的描述载体就是流程图，简单的流程图包含以下一些基本单元：起始节点，逻辑判断，执行动作，结束节点。这些节点可以完成最简单的业务逻辑描述，那么我们把这些流程parse到规则的时候，我们会怎么去做，第一个逻辑判断单元返回true，于是我们执行某个动作，第二，三个逻辑判断单元返回true我们执行某个动作，相当于会parse到两个规则，符合condition1，production1触发，符合condition2，3，production2触发，有了beta网络，我们在触发production2时只需要判断condition2，3是否成立，对于更复杂的情况，beta网络提高了速度，避免了重复匹配。

   

    开发中使用规则引擎也遇到些问题，总结如下：

    1）规则引擎中对于特殊condition的处理，由于condition会在部分production中重复出现，所以会造成condition的重复匹配问题，影响了程序的性能，这个要结合项目去优化rule脚本的parse或者使用cache去提升性能。

    2）内存消耗问题，rete算法是空间换时间，所以对于内存的消耗是比较大的，特别是加载rule的时候（生成网络），在运行期内存会缓慢增长，所以gc效率需要注意，同时单个服务器所能承受的压力（多个WM）也跟规则引擎息息相关。

    3）测试，对于使用规则去表达业务的系统，如何测试是必须解决的问题，对于这个问题，也只能保证基本的流程分支覆盖测试，对于复杂情况下的defect很难发现，不过有些原则需要注意，如果要使用规则引擎，我们必须完全以规则引擎为核心，对于业务逻辑必须尽可能的抽取到规则引擎去实现，对于扩展实现的function粒度必须小且简单，不要再代码中去实现业务逻辑。

    4）大部分的condition需要是不变的，也就是说基本信息需要保持稳定不变。比如某客户公司上属集团信用额度大于100w这样的condition，这个额度变化的频度不会很高，不需要去实时匹配。

    5），remove WME production是较复杂的操作，规则较复杂时，应该尽量少去做这样的操作。 

 

 

 

 

 

 

评论

4 楼 Element&lina 2009-03-10  

xsjleilei 写道

今天我又来啦，

“又” 额。。

3 楼 xsjleilei 2009-03-10  

今天我又来啦，

2 楼 sukerinwh 2009-03-05  

哈哈，我看到了

1 楼 comsci 2009-03-02  

不错，大家应该多关注AI，以后是AI的时代。。。。。