RETE 算法是卡内基梅隆大学的 [[Charles L.Forgy]] 博士在 1974 年发表的论文中实现的算法，是一种[[模式匹配算法]]。简易版本的论文发表于 1982 年 （http://citeseer.ist.psu.edu/context/505087/0）。拉丁语的 rete 表示 ”net” 和 “network”。

这个算法设计的目的是为了在大量的规则，Objects（或者说 Facts）中寻找匹配的规则。其核心思想是通过分离的匹配项，根据内容动态的构造匹配树，缓存中间结果，以空间换取时间，降低计算量。

RETE 算法主要可以分成两个部分：

  • 规则编译 rule compilation，构建 RETE 网络，一个有向无环图。
  • 规则执行 runtime execution
    • 找出符合 LHS 部分的集合
    • 选择一个条件被满足的规则
    • 执行 RHS 内容

RETE 算法通过规则条件生成了一个网络，每个规则条件是网络中的一个节点。

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

在 Dr. Forgy 1982 年的论文中，他定义了 4 种基本节点：

  • root
  • 1-input
  • 2-input
  • terminal

rete nodes

RETE 网络中的节点，除了根节点之外，每一个节点都对应一个 Pattern，对应规则的条件部分模式。从根节点到叶子节点定义了完整的 left-hand-side 的条件。每一个节点都保存满足这个 Pattern 的部分内存。

当一个新的 Fact 被插入或被修改时，会沿着网络传播，当满足 Pattern 时，标记节点。当一个 Fact 或者一组 Facts 满足所有 Patterns 是，就达到了叶子节点，对应的规则就被触发了。

RETE 算法设计用内存来换取执行时间。

规则

首先来看一下 Drools 的最简单的一条规则：

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

规则中可以看到 when-then 的结构，当满足 when 中的条件时，则执行 then 语句。

可以看到条件中有两个 Fact，分别是 Cheese 和 Person。

假设有两个 Fact，Person 和 Cheese。

RETE nodes example

相关概念

  • Fact 事实，通常是一个 Object，通常一个 Fact 会有很多对象的属性
  • Rule 规则：条件和结果的推理语句，条件部分叫做 LHS(Left-hand-side)，结果部分为 RHS(right-hand-side)。
  • Pattern 模式：规则的条件部分
  • RETE 网络：Drools 会根据规则在编译阶段构建一个 RETE 网络

Alpha Network

Alpha 网络形成一个 discrimination network，负责根据条件选择每一个独立的 WMEs。

在 discrimination network 中每一个 AlphaNode （ 1-input node）分支，

用非专业的术语来描述 discrimination network 就是一种当数据在其中传播的时候过滤数据的网络。在网络顶层的节点会有很多的匹配，当随着网络传播，会越来越少匹配。在网络的底部是 Terminal Nodes（结束节点），当走到这个节点意味着之前所有的 Pattern 都需要满足。

Alpha 网络，用来过滤 Fact，通过模式匹配找出事实集中所有符合模式的集合，Alpha 网络中包含 - ObjectTypeNode，类型节点，根节点的直接子节点，对象的类型 - Alpha Node，条件节点

Beta Network

Beta 网络则执行不同 WMEs 之间的 joins。这个网络中包含 2-input nodes（两个输入的节点）。每一个 Beta Node 都会将结果发送给 Beta Memory。

  • Beta 网络，用于匹配规则，通过连接操作将模式集组合成匹配集，最终将匹配集转化为规则结果并执行，包含两类节点
    • BetaNode 连接节点，接受条件节点的输入，将规则中关联的条件节点组合起来
    • Terminal Node 终端节点，规则的 THEN 部分

RETE 网络中的节点

RETE 网络中的节点：

  • RootNode，根节点，所有对象通过 RootNode 进入网络，虚拟节点，然后对象会立即进入 ObjectTypeNode
  • ObjectTypeNode，对象类型节点，保证对应类型的对象才会进入，比如两个对象 Cheese 和 Person。为了保证效率，引擎只会将对象传递到符合对象类型的节点。ObjectTypeNode 会继续传播到 AlphaNode, LeftInputAdapterNodes, BetaNodes。
  • AlphaNode 用来计算 Literal conditions，规则的条件部分的一个模式，一个对象只有和本节点匹配成功后，才能继续向下传播。在 1982 年的论文中，只提到了相等条件，当很多 RETE 实现了更多的操作。比如 Account.name == “Mr Trout”。
    • 当一个单一对象有多个 literal conditions 条件的时候，会连接到一起，这意味着当插入一个对象 Account 时，必须先满足第一个条件，然后才会继续到第二个 AlphaNode。
  • BetaNode 节点用于比较两个对象和它们的字段，两个对象可能是相同或不同的类型。我们将这两个输入称为左和右。BetaNode 的左输入通常是一组对象的数组。BetaNode 具有记忆功能。左边的输入被称为 Beta Memory，会记住所有到达过的语义。右边的输入成为 Alpha Memory，会记住所有到达过的对象。
    • JoinNode，用作 join 节点， 相当于 and，属于 BetaNode 类型的节点。
    • NotNode，exists 检查
  • LeftInputAdapterNodes，当个对象转换和数组
  • Terminal Nodes，表明一条规则已经匹配了它的所有条件

比如如下的 Alpha_Nodes 就表明是 Cheese( name =="cheddar", strength == "strong" )

alpha nodes

构建 RETE 网络

编译的结果是规则集对应的 RETE 网络，一个 Fact 可以流动的图。

  • 创建根节点
  • 加入一条规则 Account(name=”abc”, age>10)
    • a. 取出规则中的一个模式，模式就是规则中最小的匹配项，比如 age > 10, age < 20 就是两个基本的模式，如果是新类型，加入一个 ObjectTypeNode 节点
    • b. 检查模式对应的 AlphaNode 节点是否存在，如果存在则记录下节点位置，如果没有则将模式作为 Alpha 节点加入到网络，同时根据 Alpha 节点的模式建立 Alpha 内存表
    • 重复 b 直到所有的模式处理完毕
    • d. 组合 Beta 节点，按照： Beta 左输入节点为 Alpha（1），右输入节点为 Alpha（2），Beta（i）节点左输入节点为 Beta（i-1)，右输入节点为 Alpha（i） ，并将两个父节点的内存表内联成自己的内存表
    • e. 重复 d 直到所有的 Beta 节点处理完毕；
    • f. 将动作 Then 部分，封装成叶节点（Action 节点）作为 Beta（n）的输出节点；
  • 重复上面的步骤，添加规则，直到所有的规则处理完毕。

运行时执行

Working Memory Element，简称 WME，用于和非根节点代表的模式进行匹配的元素

当 facts 被插入到 Working Memory，引擎会为每一个 Fact 创建 Working memory elements(WMEs)。Facts 是一个 n 位元祖。

当 WME 从根节点进入 到 RETE 网络之后，根节点会将 WME 传到子节点中，然后每一个 WME 会通过网络传播下去，直到达到 Terminal Node。

1)如果 WME 的类型和根节点的后继结点 TypeNode(alpha 节点的一种)所指定的类型相同，则会将该事实保存在该 TypeNode 结点对应的 alpha 存储区中，该 WME 被传到后继结点继续匹配，否则会放弃该 WME 的后续匹配； 2)如果 WME 被传递到 alpha 节点，则会检测 WME 是否和该结点对应的模式相匹配，若匹配，则会将该事实保存在该 alpha 结点对应的存储区中，该 WME 被传递到后继结点继续匹配，否则会放弃该 WME 的后续匹配： 3)如果 WME 被传递到 beta 节点的右端，则会加入到该 beta 结点的 right 存储区，并和 left 存储区中的 Token 进行匹配(匹配动作根据 beta 结点的类型进行，例如：join，projection，selection)，匹配成功，则会将该 WME 加入到 Token 中，然后将 Token 传递到下一个结点，否则会放弃该 WME 的后续匹配： 4)如果 Token 被传递到 beta 结点的左端，则会加入到该 beta 结点的 left 存储区，并和 right 存储区中的 WME 进行匹配(匹配动作根据 beta 结点的类型进行，例如：join，projection，selection)，匹配成功，则该 Token 会封装匹配到的 WME 形成新的 Token，传递到下一个结点，否则会放弃该 Token 的后续匹配； 5)如果 WME 被传递到 beta 结点的左端，将 WME 封装成仅有一个 WME 元素的 WME 列表做为 Token，然后按照 4) 所示的方法进行匹配： 6)如果 Token 传递到 Terminal，则和该根结点对应的规则被激活，建立相应的 Activation，并存储到 Agenda 当中，等待激发。 7)如果 WME 被传递到 Terminal Node，将 WME 封装成仅有一个 WME 元素的 WME 列表做为 Token，然后按照 6) 所示的方法进行匹配；

特点和不足

特点：

  • 启发式算法，不同规则间共享相同的模式，如果 BetaNode 被多个规则共享，会提高 N 倍
  • 当事实集合变化不大时，保存在 Alpha 和 Beta 节点的状态不需要太多变化，避免了大量的重复计算，提高了匹配效率。
  • RETE 匹配速度与规则数目无关，只有 Fact 满足本节点才会继续向下沿网络传递

不足：

  • RETE 算法使用存储区存储已计算的中间结果，牺牲空间换取时间，加速系统的速度，存储区根据规则和事实成指数级增长，当规则和事实很多的时候，会耗尽系统资源。

建议：

  • 容易变化的规则尽量后置，减少规则的变化带来的规则库变化
  • 约束性通用或较强的模式尽量前置，避免不必要的匹配
  • 针对 Rete 算法内存开销大和事实增加删除影响效率的问题，技术上应该在 alpha 内存和 beata 内存中，只存储指向内存的指针，并对指针建索引（可用 hash 表或者非平衡二叉树）。 d. Rete 算法 JoinNode 可以扩展为 AndJoinNode 和 OrJoinNode，两种节点可以再进行组合

一个 Python 实现的 RETE 算法

reference

  • 《一种基于共享度模型的改进 Rete 算法》 孙新, 严西敏, 尚煜茗, 欧阳童, 董阔