规则引擎常用算法(RETE, PHREAK)简介

常见的模式匹配算法有RETE,LFA,TREAI,LEAPS。Rete算法是目前效率最高的一个演绎法推理算法，许多规则引擎都是基于Rete算法来进行推理计算的。 

        Rete 算法最初是由卡内基梅隆大学的 Charles L.Forgy 博士在 1974 年发表的论文中所阐述的算法 , 该算法提供了专家系统的一个高效实现。自 Rete 算法提出以后 , 它就被用到一些大型的规则系统中 , 像 ILog、Jess、JBoss Rules 等都是基于 RETE 算法的规则引擎。Forgy的论文原文：RETE Match Algorithm - Forgy OCR.pdf

        Rete 在拉丁语中译为”net”，即网络。Rete算法由Carnegie Mellon University的Dr Charles L. Forgy设计发明，是一个用来实现产生式规则系统（production/inference）的高效模式匹配算法。

        Rete 匹配算法是一种进行大量模式集合和大量对象集合间比较的高效方法，通过网络筛选的方法找出所有匹配各个模式的对象和规则。

        其核心思想是将分离的匹配项根据内容动态构造匹配树，以达到显著降低计算量的效果。        

        RETE算法可以分为两部分：规则编译（rule compilation）和运行时执行（runtime execution）。规则编译是指根据规则集生成推理网络的过程，运行时执行指将数据送入推理网络进行筛选的过程。

        当Rete算法进行事实的断言时，包含三个阶段：匹配、选择和执行，称做 match-select-act cycle。

        foreward-chaining的Rete引擎，按优先级匹配条件语句，实施规则语句。规则实施后会激发事实的变化，引擎又会重新进行条件匹配，直到不能再匹配为止，Rete的算法保证了服从的最高。

• 事实（Fact）：对象之间及对象属性之间的关系
• 规则（rule）：是由条件和结论构成的推理语句，一般表示为if…Then。一个规则的if部分称为LHS（left-hand-side），then部分称为RHS（right hand side）。
• 模式（module）：就是指IF语句的条件。这里IF条件可能是有几个更小的条件组成的大条件。模式就是指的不能在继续分割下去的最小的原子条件。

RETE推理网络的生成过程：从规则集{规则1，规则2……..}中拿出一条来，根据一定算法，变成RETE推理网络的节点。不断循环将所有规则都处理完，RETE推理网络就生成了。RETE网络主要分为两个部分，alpha网络和beta网络。如下图所示。 

•  alpha网络：过滤working memory，找出符合规则中每一个模式的集合，生成alpha memory（满足该模式的集合）。有两种类型的节点，过滤type的节点和其他条件过滤的节点（我觉得这两种是依照需要设定的，也并不一定需要两种节点）。
• Beta网络：有两种类型的节点Beta Memory和Join Node。前者主要存储Join完成后的集合。后者包含两个输入口，分别输入需要匹配的两个集合，由Join节点做合并工作传输给下一个节点。

在一个产生式系统中，主要流程可以分为以下步骤：

1. Match：找出符合LHS部分的working memory集合
2. Confilict resolution：选出一个条件被满足的规则
3. Act：执行RHS的内容
4. 返回1

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

具体过程如下：

1. 创建root节点（根节点），推理网络的入口。

2. 拿到规则1，从规则1中取出模式1（前面说了，模式就是最小的原子条件，所以规则模式的关系是1：n）。

        a)   检查模式1中的参数类型，如果是新类型，添加一个类型节点。

        b)   检查模式1对应的Alpha节点是否存在，如果存在记录下节点的位置；如果没有，将模式1作为一个Alpha节点加入到网络中。同时根据Alpha节点建立Alpah内存表。

        c)   重复b，直到处理完所有模式。

        d)   组合Beta节点：Beta(2)左输入节点为Alpha(1)，右输入节点为Alpha(2)；Beta(i)左输入节点是Beta(i-1),右输入节点为Alpha(i)，并将两个父节点的内存表内联成为自己的内存表

        e)   重复d，直到所有Beta节点处理完毕

        f)   将动作Then部分封装成最后节点做为Beta（n）

3.重复2，直到所有规则处理完毕

规则P1:

LHS:

• C1:(年纪：研2)
• C2:(性别：男)
• C3:(身材：较瘦)
• C4:(身高：大于175cm)

RHS:

• 标点符

Rete算法优于传统的模式匹配算法的特点

• 状态保存。事实集合中的每次变化，其匹配后的状态都被保存再alpha和beta节点中。在下一次事实集合发生变化时，绝大多数的结果都不需要变化，rete算法通过保存操作过程中的状态，避免了大量的重复计算。Rete算法主要是为那些事实集合变化不大的系统设计的，当每次事实集合的变化非常剧烈时，rete的状态保存算法效果并不理想。
• 节点共享

Drools中用到的RETE算法

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

下图是Drools中的RETE节点类型：

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

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”）：

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

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的使用：

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

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

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

　　这两条rule在它们的LHS中基本都是一样的，只是最后favouriteCheese，一条规则是等于$cheddar，而另一条规则是不等于$cheddar。下面是这两条规则的节点图：

• 从图上可以看到，编译后的RETE网络中，AlphaNode是共享的，而BetaNode不是共享的。上面说的相等和不相等就体现在BetaNode的不同。然后这两条规则有各自的Terminal Node。
• RETE算法的第二个部分是运行时（runtime）。当一个应用assert一个对象，引擎将数据传递到root node。从那里，它进入ObjectTypeNode并沿着网络向下传播。当数据匹配一个节点的条件，节点就将它记录到相应的内存中。这样做的原因有以下几点：主要的原因是可以带来更快的性能。虽然记住完全或部分匹配的对象需要内存，它提供了速度和可伸缩性的特点。当一条规则的所有条件都满足，这就是完全匹配。而只有部分条件满足，就是部分匹配。（我觉得引擎在每个节点都有其对应的内存来储存满足该节点条件的对象，这就造成了如果一个对象是完全匹配，那这个对象就会在每个节点的对应内存中都存有其映象。）

参考链接：http://docs.jboss.org/drools/release/6.0.0.Final/drools-docs/html/HybridReasoningChapter.html#ReteOO

• 不同规则之间的相同模式是可以共享节点和存储区的，所以做过的判断不需要重复执行，是典型的空间换时间的做法
• 使用AlphaMemory和BetaMemory存储事实，当事实部分变化时，可以只计算变化的事实，提高了匹配效率

• Rete 算法是一种启发式算法，不同规则之间往往含有相同的模式，因此在 beta-network 中可以共享 BetaMemory 和 betanode。如果某个 betanode 被 N 条规则共享，则算法在此节点上效率会提高 N 倍。

• Rete 算法由于采用 AlphaMemory 和 BetaMemory 来存储事实，当事实集合变化不大时，保存在 alpha 和 beta 节点中的状态不需要太多变化，避免了大量的重复计算，提高了匹配效率。

• 从 Rete 网络可以看出，Rete 匹配速度与规则数目无关，这是因为事实只有满足本节点才会继续向下沿网络传递。不做无意义的匹配。

a. 事实的删除与事实的添加顺序相同, 除了要执行与事实添加相同的计算外, 还需要执行查找, 开销很高 。

b. RETE 算法使用了β存储区存储已计算的中间结果, 以牺牲空间换取时间, 从而加快系统的速度。然而β存储区根据规则的条件与事实的数目而成指数级增长, 所以当规则与事实很多时, 会耗尽系统资源。

针对 Rete 算法的特点和不足，在应用或者开发基于 Rete 算法的规则引擎时，改进方向：

a. 容易变化的规则尽量置后匹配，可以减少规则的变化带来规则库的变化。

b. 约束性较为通用或较强的模式尽量置前匹配，可以避免不必要的匹配。

c. 针对 Rete 算法内存开销大和事实增加删除影响效率的问题，技术上应该在 alpha 内存和 beata 内存中，只存储指向内存的指针，并对指针建里索引（可用 hash 表或者非平衡二叉树）。

d. Rete 算法 JoinNode 可以扩展为 AndJoinNode 和 OrJoinNode，两种节点可以再进行组合 。

RETE网络图：

RETE网络中的元素整理如下：

平台有如下规则：

付费会员生日当天购物满1000元，可获得礼包A
付费会员生日当天购物满500元，可获得礼包B
付费会员生日当天购物满100元，可获得礼包C

这些规则建立的RETE网络大概是：

RETE网络的创建流程：

1. 创建根节点
2. 加入一条规则
   1. 取出规则中的一个模式（模式就是规则中的最小一个匹配项例如： age>10 、 age<20 ），检查模式中的参数类型，如果是新类型(也就是新的Fact类型)，则加入一个类型节点；
   2. 检查模式对应的 Alpha 节点是否已存在，如果存在则记录下节点位置，如果没有则将模式作为一个 Alpha 节点加入到网络中，同时根据 Alpha 节点的模式建立 Alpha Memory；
   3. 重复 b 直到所有的模式处理完毕；
   4. 组合 Beta 节点，按照如下方式： Beta 左输入节点为 Alpha(1)，右输入节点为 Alpha(2) 。Beta(i) 左输入节点为 Beta(i-1)，右输入节点为 Alpha(i) i>2 并将两个父节点的内存表内联成为自己的内存表；
   5. 重复 d 直到所有的 Beta 节点处理完毕；
   6. 将动作（Then 部分）封装成Beta(n) 的输出节点；
3. 重复2直到所有规则处理完毕

RETE如何处理模式之间的or关系？由于模式之间只有NOT和EXIST两种关系，Beta Node并不能表述or的关系，所以Drools将其拆分成两条规则来看待。

PHREAK是由Drools团队设计和实现的一种算法，并在Drools 6中引入。PHREAK是一种慵懒匹配算法，在模型上基本延续了RETE，节点及其作用都是一样的。

PHREAK和RATE算法的性能比较结果：

PHREAK算法在RETE之上的改进点：

• 延迟规则评估 ：当PHREAK引擎启动后，所有规则都处于一种 unlinked 的状态，这种状态的规则不会被Drools执行。当 insert 、 update 、 delete 等操作修改了KIE会话的状态时，修改只会传播到alpha子网，并在进入beta子网之前排队。与RETEOO不同，在PHREAK中，不会执行Beta节点以用作这些操作的结果。 引擎会先用试探法确定哪个规则最有可能导致匹配，从而在它们之间强加一个执行顺序。
• 面向集合传播 ：在RETEOO中，每次insert/update/delete事实时，都会从顶部（入口点）到底部（最佳情况下的规则终端节点）遍历网络。网络中执行评估的每个节点都创建了一个元组，该元组传播到路径中的下一个节点。PHREAK不是这样工作的。一个Beta节点上所有排队的insert/update/delete操作会被批处理评估，并且结果会放到一个Set中。这个Set会被转发到下一个节点，并且执行上面同样形式的评估，并把结果放到同一个Set中。面向集合传播在某些规则上具有性能优势，并且为将来做多线程评估提供了可能。
• 分割网络 ：在分段中，一个KIE Base中的节点是可以在不同规则之家共享的。PHREAK将规则是为分段的路径，而不是节点的路径。一个不与其他任何规则共享其节点的规则由单个段组成。路径中每个段都分配有1 bit的标志位。当节点包含足够评估的数据时，该标志位设置为on。当段中所有节点都为on时，段本身将设置为on。当规则的所有段都为on时，该规则会被标记为 linked 。Drools利用这些标志位来避免对已经评估的节点和段进行重新评估，从而让PHREAK网络的评估效率更高。

想了解更多关于PHREAK的新消息，可参考：

Drools提供一整套解决方案。
如果只是想要简单使用，那就是只用到Drools的核心BRE，引入几个Maven依赖，编写Java代码和规则文件即可。