文章目录一、概要：二、算法细节：术语描述：更好地理解Rete算法：算法细节描述：解析Rete网络内容：分析Rete网络创建流程：运行时运行流程分析： Rete网络创建流程原因有以下三点。 Rete算法的缺点：针对Rete算法的特点和不足，在应用或开发基于Rete算法的规则引擎时，提出以下建议。 参考资料：
一、概述：
Rete算法是卡内基梅隆大学的Charles L.Forgy博士在1974年发表的论文中叙述的算法。 该算法提供了专家系统的有效实现。
Rete用拉丁语翻译成“net”，也就是网络。 Rete是一种比较多个模式集合和多个对象集合的高效方法，通过网络过滤器的方法找到与各个模式匹配的所有对象和规则。 其核心思想是用分离的匹配项建立匹配网络，同时缓存中间结果，在空间上改变时间。 步骤大致分为规则编译(rule compilation )和运行时执行(runtime execution )。
二、算法细节：facts (指事实、对象之间及对象属性之间的关系。
patterns :模板是指事实的一个模型，所有事实库中的事实必须至少与模板之一相匹配。
conditions :条件、规则的构成要素也必须至少与一个模板一致。
(对于上述三种关系，可以很容易地理解patterns是接口，conditions是实现该接口的类，而facts是该类的实例。 ）
规则由一个或多个条件组成。 通常用and或or连接conditions。
(如果将一个rule视为if-then语句，则if部分为lhs (左手侧)，then部分为RHS (右手侧)。 ）
module :模式是指上述if语句的条件。 这里的条件可能是由几个更小的条件组成的大条件。 模式是指不能继续分割的最小原子条件。
动作：动作，激活rule执行的动作之一。
有关Rete算法的详细信息，Rete算法是生成系统的一种高效模式匹配算法。
在一个生成系统中，处理的数据被称为工作内存，用于判定的规则分为两个部分lhs (左手边)和RHS (右手边)，分别给出前提和结论。 主要过程分为以下几个步骤。
match :找到符合lhs部分的工作内存集合。
Conflict Resolution :选择一个符合条件的规则。
act :执行RHS的内容。
返回。
Rete算法主要改进Match的处理过程，通过建立网络进行匹配。
算法详细说明： Rete网络主要分为两个部分： alpha网络和Rete网络。 如下图所示。
Rete网络内容分析：过滤alpha网络(工作内存)，找出每个符合规则的模式的集合，生成alpha memory。 有两种类型的节点可以过滤type，也可以在其他条件下过滤。
beta网络：有beta内存和join node两种节点。 前者主要保存join完成后的集合后者包含两个输入端口，分别输入需要匹配的两个集合，join节点进行合并工作后转发到下一个节点。
根节点，所有对象进入网络入口。 (一个网络中只有一个根节点。)
(输入节点)单输入节点可以分为对象类型节点、alpha节点、LeftInputAdapterNode等。
对象类型节点： facts在从根节点进入Rete网络时立即进入对象类型节点。 对象类型节点提供了按对象类型过滤对象的功能。 这样的节点可以防止规则引擎执行额外的工作。 Cheese类型的facts进入网络后，只需通过Cheese类型的对象类型节点之后的节点。 下图：
阿尔法节点是规则的条件部分的模式。 通常，用于评价字面的条件。 如下图所示，2个alpha节点分别评价了Cheese事实的name和strength属性。
•LeftInputAdapterNode :角色是输入对象并传播到单个对象列表(元组)。
(输入节点)双输入节点，包括连接节点和不连接节点。 JoinNode和NotNode也是用于比较两个对象及其域的测试节点。 2-input node有左内存区域、右内存区域和左右两个输入端口，其中有左内存
储区是beta存储区，right存储区是alpha存储区。存储区储存的最小单位是工作存储区元素（Working Memory Element，简称WME），WME是为fact建立的元素，是用于和非根结点代表的module进行匹配的元素。•Join Node：用作连接（join）操作的节点，相当于数据库的表连接操作。
•NotNode：根据右边输入对左边输入的对象数组进行过滤，两个 NotNode 可以完成 ‘exists’ 检查。
⑥Terminal Node：终端节点，到达一个终端节点，表示单条rule匹配了所有的条件。（网络中有多个终端节点；当单条规则中有or时，也会产生多个终端节点） Rete网络创建流程分析：
①创建Root Node，推理网络的入口。
②拿到rule1，从rule1中取出module1（模式就是最小的原子条件）。
⑴检查module1中的参数类型，如果是新类型，添加一个Object Type Node。
⑵检查module1对应的AlphaNode是否存在，如果存在记录下节点的位置；如果不存在，将module1作为一个AlphaNode加入到网络中。同时根据AlphaNode建立Alpah内存表。
⑶重复⑵，直到处理完所有模式。
⑷组合Beta节点：Beta2左输入节点为Beta1，右输入节点为Alpha2；Beta(i)左输入节点是Beta(i-1)，右输入节点为Alpha(i)，并将两个父节点的内存表内联成为自己的内存表。
⑸重复⑷，直到所有Beta节点处理完毕。
⑹将动作then部分封装成最后节点做为Beta(n)。
③重复②，直到所有规则处理完毕。
推理引擎在进行模式匹配时，先对facts进行断言，为每一个fact建立WME（Working Memory Element），然后将WME从Rete鉴别网络的Root Node开始匹配，因为WME传递到的结点类型不同采取的算法也不同，所以需要对alpha结点和beta结点处理WME的不同情况而分开讨论。
①如果WME的类型和Root Node的后继结点TypeNode（alpha结点的一种）所指定的类型相同，则会将该fact保存在该TypeNode对应的alpha存储区中，该WME被传到后继结点继续匹配，否则会放弃该WME的后续匹配。
②如果WME被传递到alpha结点，则会检测WME是否和该结点对应的module相匹配。若匹配成功，则会将该fact保存在该alpha结点对应的存储区中，该WME被传递到后继结点继续匹配，否则会放弃该WME的后续匹配。
③如果WME被传递到beta结点的右端，则会加入到该beta结点的right存储区，并和left存储区中的Token进行匹配（匹配动作根据beta结点的类型进行，例如：join，projection，selection）。若匹配成功，则会将该WME加入到Token中，然后将Token传递到下一个结点，否则会放弃该WME的后续匹配。
④如果Token被传递到beta结点的左端，则会加入到该beta结点的left存储区，并和right存储区中的WME进行匹配（匹配动作根据beta结点的类型进行，例如：join，projection，selection）。若匹配成功，则该Token会封装匹配到的WME形成新的Token，传递到下一个结点，否则会放弃该Token的后续匹配。
⑤如果WME被传递到beta结点的左端，将WME封装成仅有一个WME元素的WME列表做为Token，然后按照④所示的方法进行匹配。
⑥如果Token传递到Terminal Node，则和该Root Node对应的规则被激活，建立相应的Activation，并存储到Agenda当中，等待激发。
⑦如果WME被传递到Terminal Node，将WME封装成仅有一个WME元素的WME列表做为Token，然后按照⑥所示的方法进行匹配。
①Rete 算法是一种启发式算法，不同规则之间往往含有相同的模式，因此在 beta-network 中可以共享 BetaMemory 和 betanode。如果某个 betanode 被 N 条规则共享，则算法在此节点上效率会提高 N 倍。
②Rete 算法由于采用 AlphaMemory 和 BetaMemory 来存储事实，当事实集合变化不大时，保存在 alpha 和 beta 节点中的状态不需要太多变化，避免了大量的重复计算，提高了匹配效率。
③从 Rete 网络可以看出，Rete 匹配速度与规则数目无直接关系，这是因为fact只有满足本节点才会继续向下沿网络传递。
①facts的删除与facts的添加顺序相同，除了要执行与facts添加相同的计算外，还需要执行查找，开销很高。
②Rete算法使用了BetaMemory存储已计算的中间结果，以空间换取时间，从而加快系统的速度。然而BetaMemory根据规则的条件与facts的数目而成指数级增长，极端情况下会耗尽系统资源。
①容易变化的规则尽量置后匹配，可以减少规则的变化带来规则库的变化。
②约束性较为通用或较强的模式尽量置前匹配，可以避免不必要的匹配。
③针对 Rete 算法内存开销大和facts增加删除影响效率的问题，技术上应该在 AlphaMemory 和 BetaMemory 中，只存储指向内存的指针，并对指针建里索引（可用 hash 表或者非平衡二叉树）。
④Rete 算法 JoinNode 可以扩展为 AndJoinNode 和 OrJoinNode，两种节点可以再进行组合。
Rete 算法
Production Matching for Large Learning Systems