Rete algorithm（网络算法）

Rete算法是目前使用最广泛的规则匹配算法，由Charles L. Forgy博士在1979年发明。Rete算法是一种快速的Forward-Chaining推理算法，其匹配速度与规则的数量无关。ILog、Jess、JBoss Rules等都是基于RETE算法的规则引。Drools采用了Reteoo算法（Rete算法的实现版），Drools也采用过Leaps算法，后来无人维护撤销了。
Rete算法的基本思想是保存过去匹配过程中留下的全部信息,以空间代价来换取执行效率 。对每一个模式 ,附加一个匹配元素表来记录WorkingMemory中所有能与之匹配的元素。当一个新元素加入到WorkingMemory时, 找出所有能与之匹配的模式, 并将该元素加入到匹配元素表中; 当一个无素从WorkingMemory中删除时,同样找出所有与该元素匹配的模式,并将元素从匹配元素表中删除。 Rete算法接受对工作存储器的修改操作描述 ,产生一个修改冲突集的动作 。
Rete算法的步骤如下：

1. 将初始数据（fact）输入Working Memory。
2. 使用Pattern Matcher比较规则（rule）和数据（fact）。
3. 如果执行规则存在冲突（conflict），即同时激活了多个规则，将冲突的规则放入冲突集合。
4. 解决冲突，将激活的规则按顺序放入Agenda。

使用规则引擎执行Agenda中的规则。重复步骤2至5，直到执行完毕所有Agenda中的规则。

Uni-Rete algorithm

Tread algorithm

在Rete算法中 ,同一规则连接结点上的寄存器保留了大量的冗余结果。实际上, 寄存器中大部分信息已经体现在冲突集的规则实例中。因此 ,如果在部分匹配过程中直接使用冲突集来限制模式之间的变量约束,不仅可以减少寄存器的数量 ,而且能够加快匹配处理效率 。这一思想称为 冲突集支撑策略 。
考虑增删事实对匹配过程的影响，当向工作存储器增加一个事实时 ,冲突集中已有的规则实例仍然保留,只是将与该事实匹配的规则实例加入到冲突集中; 当从工作存储器删去一个事实时，不可能有新的规则实例产生, 只是将 包含该事实的规则实例从冲突集中删去。
基于冲突集支撑策略和上述观察, Treat算法放弃了Rete算法中利用寄存器保存模式之间变量约束中间结果的思想,对于每一个模式 ,除保留原有 a寄存器的外 ,增加两个新链来记录与该模式匹配的增删事实,一个叫做增链 (addlist),另一个叫做删链 (deletelist)。当修改描述的操作符为 “+”时,临时执行部分连接任务;当修改描述的操作符为 “一”时,直接删去冲突集中包含该事实的规则实例。

Leaps algorithm（跳跃算法）

前向推理引擎，包括LEAPS，都包括了匹配-选择-执行（match-select-action）循环。即，确定可以匹配的规则，选择某个匹配的元 组，此元组相应的规则动作被执行。重复这一过程，直到某一状态（如没有更多的规则动作）。RETE和TREAT匹配算法速度慢的原因是，它们把满足规则条 件的元组都实例化。Leaps算法的最大的改进就是使用一种”lazy”的方法来评估条件（conditions），即仅当必要时才进行元组的实例化。这 一改进极大的减少了前向推理引擎的时空复杂度，极大提高了规则执行速度。
Leaps算法将所有的 asserted 的 facts ，按照其被 asserted 在 Working Memory 中的顺序（ FIFO ），放在主堆栈中。它一个个的检查 facts ，通过迭代匹配 data type 的 facts 集合来找出每一个相关规则的匹配。当一个匹配的数据被发现时，系统记住此时的迭代位置以备待会的继续迭代，并且激发规则结果（ consequence ）。当结果（ consequence ）执行完成以后，系统就会继续处理处于主堆栈顶部的 fact 。如此反复。
Leaps算法的效率可以比Rete算法和Tread算法高几个数量级。

HAL algorithm

Matchbox algorithm

参考

CSDN：规则引擎系列—规则引擎背后的算法
https://blog.csdn.net/y510662669/article/details/105606196
新浪博客：规则引擎研究（一）——Rete算法（1-3）
http://blog.sina.com.cn/s/blog_4a7a7aa3010008b9.html
新浪博客：规则引擎研究（一）——Rete算法（4）——Rete算法的特例Uni-Rete算法
http://blog.sina.com.cn/s/blog_4a7a7aa3010008mk.html
ITEYE：规则引擎中常用的模式匹配算法
https://www.iteye.com/blog/duyangsss-2034598