RETE算法简述 & 实践

1. 概述

Rete 算法是卡内基梅隆大学的 Charles L.Forgy 博士在 1974 年发表的论文中所阐述的算法。 该算法提供了专家系统的一个高效实现。

Rete 在拉丁语中译为”net”（即网络）。Rete 是一种进行大量模式集合和大量对象集合间比较的高效方法，通过网络筛选的方法找出所有匹配各个模式的对象和规则。

其核心思想是用分离的匹配项构造匹配网络，同时缓存中间结果。以空间换时间。规则编译（rule compilation）和运行时执行（runtime execution）。

2. 规则编译（rule compilation）

规则编译是指根据规则集生成高效推理网络的过程

2.1. 相关概念：

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

2.2. RETE网络节点类型

RETE网络示意图

13416824241499e42e8e218c.png

image.png

  • Root Node：所有对象进入网络的入口，在一个网络中只有一个根节点。借用Rete算法经典的示例：

  • 1-input node：可分为ObjectTypeNode, AlphaNode, LeftInputAdapterNode等。

Object Type Node：事实从根节点进入Rete网络后，会立即进入Object Type Node节点。Object Type Node提供了按对象类型过滤对象的能力，通过此类节点可使规则引擎不做额外的工作。Cheese类型的事实进入网络后，只需经过类型为Cheese的Object Type Node之后的节点。如下图

13416824520f19a1d3b1abbc.png

RootNode.png

Alpha Node：Alpha 节点是规则的条件部分的一个模式。通常用于评估字面的条件。如下图，两个Alpha Node 分别评估了Cheese事实的name和strength属性。

1341682440b8f67eb6f193a0.png

image.png

Left Input Adapter Node：作用是输入一个对象，传播为一个单对象列表（元组）。这块有疑问。后续会考究。

  • 2-input node（Beta Node）: 拥有两个输入的节点。Beta Node 节点用于比较两个对象。两个对象可能是相同或不同的类型。Beta Node主要包含Join Node 和 Not Node两种类型。
    Join Node：用作连接（join）操作的节点，相当于数据库的表连接操作。
    NotNode：根据右边输入对左边输入的对象数组进行过滤，两个 NotNode 可以完成‘ exists ’检查。

  • Terminal Node：到达一个终端节点，表示单条规则匹配了所有的条件，网络中有多个终端节点。当单条规则中有or时，也会产生多个终端节点。

完整的示例：

  • 规则文件

rule1
when
Cheese($cheddar : name == “cheddar” )
$person : Person( favouriteCheese == $cheddar )
then
System.out.println($person.getName() + “ likes cheddar” );
end

rule2
when
Cheese( $cheddar : name == “cheddar” )
$person : Person( favouriteCheese != $cheddar )
then
System.out.println($person.getName() + “ does not like cheddar” );
end

Rete网络：

134168244573bbcc0037a1cd.png

image.png

从图上可以看到，编译后的RETE网络中，AlphaNode是共享的，而BetaNode不是共享的。两条规则的BetaNode的不同。然后这两条规则有各自的Terminal Node。

2.3. 创建Rete网络

RETE算法通过构建一个网络进行匹配，具体过程如下：

  1. 创建root节点（根节点），推理网络的入口。
  2. 拿到规则1，从规则1中取出模式1（模式就是最小的原子条件）。
  • 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）

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

3. 运行时执行（runtime execution）

推理引擎在进行模式匹配时，先对事实进行断言，为每一个事实建立WME(Working Memory Element)，然后将WME从RETE鉴别网络的根结点开始匹配，因为WME传递到的结点类型不同采取的算法也不同，所以需要对alpha结点和beta结点处理WME的不同情况而分开讨论。

1
2
3
4
5
6
7
8
9
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传递到终结点，则和该根结点对应的规则被激活，建立相应的Activation，并存储到Agenda当中，等待激发。

7)如果WME被传递到终结点，将WME封装成仅有一个WME元素的WME列表做为Token，然后按照 6) 所示的方法进行匹配；

4. 一些实践

由于从事运输行业，故以业内的典型场景作为实践示例。
例如：我们需要将提供“机票+酒店”、“机票+酒店+贵宾休息室”两种类型的产品给旅客。
机票、酒店、贵宾休息室需要满足一些基本的限制条件。并且：
“机票+酒店”产品要保障：酒店位于目的地且到达当天可以入住。
“机票+酒店+贵宾休息室”产品要保障：酒店位于目的地且到达当天可以入住。贵宾休息室位于出发城市。

下图展示了打包规则所构成的RETE网络。

1341682465b456a664322229.png

机加酒，机加酒加贵宾休息室.png

基于Drools实现相关规则：

  • 数据模型
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
package com.myspace.packagedproduct;
public class Location implements java.io.Serializable {
    static final long serialVersionUID = 1L;
    @org.kie.api.definition.type.Label(value = "\u56FD\u5BB6")
    private java.lang.String country;
    @org.kie.api.definition.type.Label(value = "\u7701\u4EFD")
    private java.lang.String province;
    @org.kie.api.definition.type.Label(value = "\u57CE\u5E02")
    private java.lang.String city;
   ...Getter、Setter方法...
}

public class Segment implements java.io.Serializable {
    static final long serialVersionUID = 1L;
    @org.kie.api.definition.type.Label("产品编码")
    private java.lang.String proCode;
    @org.kie.api.definition.type.Label("产品名称")
    private java.lang.String proName;
    @org.kie.api.definition.type.Label("出发城市")
    private java.lang.String startCity;
    @org.kie.api.definition.type.Label("到达城市")
    private java.lang.String arriveCity;
    @org.kie.api.definition.type.Label("舱位")
    private java.lang.String cabin;
    @org.kie.api.definition.type.Label("航班日期")
    private java.util.Date flightDate;
        ...Getter、Setter方法...
}

public class Hotel implements java.io.Serializable {
    static final long serialVersionUID = 1L;
    @org.kie.api.definition.type.Label("产品编码")
    private java.lang.String proCode;
    @org.kie.api.definition.type.Label("产品名称")
    private java.lang.String proName;
    @org.kie.api.definition.type.Label("房型")
    private java.lang.String roomType;
    @org.kie.api.definition.type.Label("入住日期")
    private java.util.Date checkInDate;
    @org.kie.api.definition.type.Label("位置")
    private com.myspace.packagedproduct.Location location;
    @org.kie.api.definition.type.Label(value = "\u662F\u5426\u53EF\u6253\u5305\u9500\u552E")
    private java.lang.Boolean ifCanPackageSale;
        ...Getter、Setter方法...
}

public class ReservedLounge implements java.io.Serializable {
    static final long serialVersionUID = 1L;
    @org.kie.api.definition.type.Label("产品编码")
    private java.lang.String proCode;
    @org.kie.api.definition.type.Label("产品名称")
    private java.lang.String proName;
    @org.kie.api.definition.type.Label("位置")
    private com.myspace.packagedproduct.Location location;
    @org.kie.api.definition.type.Label("是否自营")
    private boolean selfSupport;
        ...Getter、Setter方法...
}

public class PackagedProduct implements java.io.Serializable {
    static final long serialVersionUID = 1L;
    @org.kie.api.definition.type.Label(value = "\u6210\u5458\u4EA7\u54C1ID\u5217\u8868")
    private java.util.List<java.lang.String> itemProductCodes;
      ...Getter、Setter方法...
}

  • 规则
language-package
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
 import java.util.Date;
 import java.text.SimpleDateFormat;
 import java.math.BigDecimal;
 import java.util.List;
 import com.alibaba.fastjson.JSON;
 import com.alibaba.fastjson.JSONObject;
 import com.alibaba.fastjson.JSONArray;
 import com.myspace.packagedproduct.*;
 import com.myspace.packagedproduct.PackagedProduct
 import java.util.ArrayList;
 global java.util.Date now;
 global java.text.SimpleDateFormat dateFormat;

rule "segment_hotel"
    when
        seg : Segment( startCity in ( "XMN", "PEK", "FOC", "HGH", "TSN", "JJN" ) , cabin == "Y" )
        hotel : Hotel( ifCanPackageSale == true , location != null , location.city == seg.arriveCity )
    then

        System.out.println("【机+酒产品】"+seg.getProCode()+" + "+hotel.getProCode());

end

rule "segment_hotel_lounge"
    dialect "java"
    when
        seg : Segment( startCity in ( "XMN", "PEK", "FOC", "HGH", "TSN", "JJN" ) , cabin == "Y" )
        hotel : Hotel( ifCanPackageSale == true , location != null , location.city == seg.arriveCity )
        lounge:ReservedLounge(selfSupport==true,location.city == seg.startCity)
    then
    System.out.println("【机+酒+休息室产品】"+seg.getProCode()+" + "+hotel.getProCode()+" + "+lounge.getProCode());
end

  • 规则调用语句
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
@Test
 public void testPackagedProduct() throws ParseException {
     SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd");
     Date date1 = sdf.parse("2018-09-30");
     Date date2 = sdf.parse("2018-09-31");
     KieSession kieSession = this.getKieSessionBySessionName("mapAndList-rules");
     Segment seg = new Segment();
     seg.setArriveCity("PEK");
     seg.setStartCity("XMN");
     seg.setFlightDate(date1);
     seg.setCabin("Y");
     seg.setProCode("seg1");
     Segment seg2 = new Segment();
     seg2.setArriveCity("PEK");
     seg2.setStartCity("XMN");
     seg2.setFlightDate(date1);
     seg2.setCabin("T");
     seg2.setProCode("seg2");
     Segment seg3 = new Segment();
     seg3.setArriveCity("XMN");
     seg3.setStartCity("TSN");
     seg3.setFlightDate(date1);
     seg3.setCabin("Y");
     seg3.setProCode("seg3");
     Hotel hotel = new Hotel();
     hotel.setCheckInDate(date1);
     hotel.setIfCanPackageSale(true);
     hotel.setLocation(new Location("", "", "XMN"));
     hotel.setProCode("hotel1");
     Hotel hotel2 = new Hotel();
     hotel2.setCheckInDate(date2);
     hotel2.setIfCanPackageSale(true);
     hotel2.setLocation(new Location("", "", "XMN"));
     hotel2.setProCode("hotel2");
     Hotel hotel3 = new Hotel();
     hotel3.setCheckInDate(date1);
     hotel3.setIfCanPackageSale(true);
     hotel3.setLocation(new Location("", "", "NRT"));
     hotel3.setProCode("hotel3");
     Hotel hotel4 = new Hotel();
     hotel4.setCheckInDate(date1);
     hotel4.setIfCanPackageSale(true);
     hotel4.setLocation(new Location("", "", "PEK"));
     hotel4.setProCode("hotel4");

     ReservedLounge lounge = new ReservedLounge();
     lounge.setLocation(new Location("", "", "XMN"));
     lounge.setSelfSupport(true);
     lounge.setProCode("lounge1");
     ReservedLounge lounge2 = new ReservedLounge();
     lounge2.setLocation(new Location("", "", "PEK"));
     lounge2.setSelfSupport(true);
     lounge2.setProCode("lounge2");
     ReservedLounge lounge3 = new ReservedLounge();
     lounge3.setLocation(new Location("", "", "XMN"));
     lounge3.setSelfSupport(false);
     lounge3.setProCode("lounge3");
     kieSession.insert(seg);
     kieSession.insert(seg2);
     kieSession.insert(seg3);
     kieSession.insert(hotel);
     kieSession.insert(hotel2);
     kieSession.insert(hotel3);
     kieSession.insert(hotel4);
     kieSession.insert(lounge);
     kieSession.insert(lounge2);
     kieSession.insert(lounge3);
     kieSession.fireAllRules();
     kieSession.dispose();
 }

  • 执行结果

【机+酒产品】seg1 + hotel4
【机+酒产品】seg3 + hotel1
【机+酒产品】seg3 + hotel2
【机+酒+休息室产品】seg1 + hotel4 + lounge1

5. 为何RETE算法效率高

5.1. RETE算法优于普通代码逻辑

借用上面的示例， 如：Segment，Hotel，ReservedLounge类型的产品分别有10个。按照一般的程序处理逻辑，我们要写三个For循环去处理三类产品的打包操作，计算次数为三类产品数目的笛卡尔积级别的，即：10*10*10 =1000。

而RETE算法采用空间换时间的策略，将中间的计算结果缓存下来（Alpha Memory，Beta Memory）。计算次数为10+10+10（Alpha节点计算次数）加上2次join/projection操作（Beta节点计算次数）。基于内存中的数据做join/projection/selection操作效率很高。

5.2. Rete算法优于传统的模式匹配算法。

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

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

c. 从 Rete 网络可以看出，Rete 匹配速度与规则数目无直接关系，这是因为事实只有满足本节点才会继续向下沿网络传递。

6.RETE算法的缺点

RETE算法使用了存储区存储已计算的中间结果，以空间换取时间，从而加快系统的速度。然而存储区根据规则的条件于事实的数目成指数级增长，极端情况下会耗尽系统资源。

7. RETE算法的衍生

KIE团队改良了原生的Rete算法：ReteOO …