【IT168技术文档】最近面试的时候，经常被问及自己参加的项目中rete算法的原理，但是RETE算法是一个比较复杂的算法，在短时间内不能阐述的足够清晰，在这里做个简单的介绍。

     RETE算法是一个用来实现产生式规则系统的高效模式匹配算法。该算法是由卡内基美隆大学的Charles L. Forgy在1974年发表的论文中所阐述的算法。RETE算法提供了专家系统的一个高效实现。

     规则推理引擎做为产生式系统的一部分，当进行事实的断言时，包含三个阶段：匹配、选择和执行，称做match-select-act cycle。RETE算法可以对匹配阶段进行高效实现，下面从鉴别网络和模式匹配过程两个方面对该算法进行介绍。

     鉴别网络（如下图所示）：
     由RETE算法在进行模式匹配时，是根据生成的鉴别网络来进行的。网络中非根结点的类型有1-input结点（也称为alpha结点）和2-input结点（也称为beta结点）两种。1-input结点组成了Alpha网络，2-input结点组成了Beta网络。
每个非根结点都有一个存储区。其中1-input结点有alpha存储区和一个输入口；2-input结点有left存储区和right存储区和左右两个输入口，其中left存储区是beta存储区，right存储区是alpha存储区。存储区储存的最小单位是工作存储区元素（Working Memory Element，简称WME），WME是为事实建立的元素，是用于和非根结点代表的模式进行匹配的元素。Token是WME的列表，包含有多个WME，（在Forgy的论文中，把Token看成是WME的列表或者单个WME，为了阐述方便，本文将把Token只看成WME的列表，该列表可以包含一个WME或者多个WME），用于2-input结点的左侧输入。事实可以做为2-input结点的右侧输入，也可以做为1-input结点的输入。
每个非根结点都代表着产生式左部的一个模式，从根结点到终结点的路径表示产生式的左部。