(注：本文参考自P.-Y.LeeandA.M.K.Cheng,“HAL:A Faster Match Algorithm”,IEEE Trans. Knowledge and Data Eng.,vol.14,no.5,Sept./Oct. 2002.）
HAL：快速的匹配算法 一、 简介前向推理的产生式系统已经应用在各种领域中。这些产生式系统的基本结构分为三个部分。第一个部分是控制规则的推理引擎。第二个部分是针对要解决问题的所有的事实或断言组成的工作内存。第三个部分是规则集，每条规则都由LHS和RHS所组成。其中，LHS由一个或多个与事实相关的条件组成，RHS是对工作内存中的元素的操作。下图就是一个OPS5中规则和工作内存的例子
上图中，p表明了一个规则的开始，rule-one是此规则的名字。Class_X是事实所在类的名字。尖头“^”表明类中的一个属性。“al”是属性的名字。“< >”表明其中的是变量名。
通常，产生式系统一般都是下面这样的匹配过程：
1、匹配（match）：规则中的条件与工作内存中的事实相匹配，所有条件均被匹配成功的规则将被实例化并且进入冲突集中。
2、 选择（select）：通过某种冲突策略，选择冲突集中的某个规则实例化。
3、 执行（act）：选定规则的动作将被执行，有可能改变工作内存的元素状态。
产生式系统中的工作内存的状态在前向推理的操作过程中很少改变。因此，很多算法都是很重视限制匹配过程中的链接操作，防止出现所有事实和所有规则的组合匹配问题。主要是通过分别维护每个规则的匹配网络解决的。这些网络中的节点都存储相关的事实。当工作内存中的元素被删除或添加时，相应的更新这些节点，但是不用重新编译匹配网络。尽管如此，目前的算法仍然会出现组合问题，把匹配作为一个NP难（NP-hard）的问题来处理。
McDermott et al.认为产生式系统中，建立匹配网络的过程的花费要比进行匹配测试的过程少的多。RETE和TREAT算法都是主要关注于工作内存中的事实空间，Matchbox则主要关注于绑定空间中变量和变量的绑定值而不是条件和事实。Matchbox仍然在绑定空间中采用了组合网络结构。这些匹配算法的组合性质极大的影响了产生式系统的执行速度。
本文介绍的一种新的算法，称为启发式—标注—连接（Heuristically-Annotated-Linkage, HAL），支持链接匹配，但不进行笛卡尔积匹配。规则节点提供反馈消息，从而与相关类型节点建立关于事实实例化的启发式关联。当工作内存中的事实集有变动，并且新的节点内容部分匹配条件元素时，相应的规则将被某个类节点或中间节点激发。HAL支持相等条件匹配，否定条件匹配，和不等条件匹配（>, <）。HAL主要使用类的启发式信息，而不是规则的，因为一个程序中，规则的定义要比类的多。类的数量一般是固定的，而随着程序的改变，规则的数量一般会发生变化。基于类的定义，一个全局fixed-traversal-distance匹配支持结构已经足够，而其他的匹配算法中，针对每个规则都要建立相应的匹配支持结构。
HAL使用以下的匹配过程：
预处理（preprocessing）
规则和类转化为三类节点：规则节点(rule nodes)，类节点（class nodes）和中间节点（intermediate nodes）。中间节点介于规则节点和类节点之间。预处理的阶段和传统匹配阶段中的建立各个规则的局部匹配网络相似。预处理假定，规则和类定义都不会发生变化。规则节点包含直接指向相关的类节点的指针。
1. 选择(select)
那些含有与规则完全匹配的事实实例化的节点将进入冲突集。这些规则实例化根据冲突策略选中某个进行规则动作执行。
2. 操作(operate)
根据规则动作执行的操作有可能是改变相关类节点的的内容。
3. 激发（stimulate）
被修改的类节点有可能激发与其相关的规则节点，或者相关的中间节点。
以上三个操作（1，2，3）循环执行，直到没有相关的类节点被执行，或者遇到一个终止指令。
二、 各种匹配算法下面用上面的例子来介绍一下RETE，TREAT，和Matchbox的匹配过程。
RETE为每一条规则建立了一个包括alpha和beta内存的本地网络。网络的深度和宽度成正比。网络的顶部是alpha内存节点，存放部分匹配条件元素的tokens。其余的网络节点都是beta节点，存放条件元素变量绑定和连接的tokens。如下图所示。
与RETE相比，TREAT网络中仅仅为每条规则建立一个本地alpha节点。TREAT中的alpha节点要比RETE中更加负责，alpha节点分成三个部分。分别是旧（old）节点，新添加（new-add）节点，新删除（new-delete）节点。当alpha节点中插入新的事实时，将引发一个搜索，有可能导致冲突集的变化。如下图
因为这些匹配算法的组合特性（combinatorial nature）,匹配时间有可能很长。含有条件较多的规则，匹配时间变得很长。节点中的冗余数据进一步加剧了这一情况。HAL算法在节点间使用启发式引入了一种反馈机制减少了判断某个规则是否匹配的时间从而解决了匹配时间问题。同时，通过引入一个全局匹配网络消除了局部支持匹配网络的数据冗余问题。
三、 HAL算法HAL算法除了运用对类的操作外，吸收了其他匹配算法的优点。HAL算法建立了一个全局的固定高度的伪双向网络（global fixed-height pseudobipartite network）。在这个网络中含有两类节点，分贝位于头部和底部，在这两类节点中间可能存在第三种节点，中间节点。伪双向网络的特点减少了传统TREAT算法中的节点数目。通过引入中间节点，使得HAL算法也支持传统Matchbox算法的绑定空间匹配。同时，通过引入启发式知识（如关于规则匹配的条件值的优先级信息等）使得此算法适合于实时系统的应用。另外，建立和维护支持网络的花费也很少，因为就只有一个全局匹配支持网络。HAL网络的负责程度主要由类的多少决定，而一般情况下类的数目要比规则数目少。
3.1 HAL算法匹配算法HAL算法的匹配过程：
1. 建立一个全局的伪双向网络，为每个规则建立一个规则节点，每个类一个类节点。对于每条规则，如果其中的类涉及到变量绑定，则为此规则建立一个中间节点。规则中含有变量绑定，则其规则节点和中间节点之间有双向通信链接。没有变量绑定的规则，其类节点与规则节点直接相连。
2. 遍历所有未被检查或者新更新的事实，选择其中一个。检查此事实中的类所对应的类节点。如果此类节点连着一个中间节点，则当添加事实时，把新事实信息发送给中间节点，当删除事实时，把新事实信息发送给中间节点和规则节点。转到步骤3。如果没有中间节点，则检查类节点的测试条件，看是否满足。如果满足，则激发相应的规则节点，转到步骤4。如果没有新的事实或改动，则算法终止。
3. 在每个中间节点，如果新的绑定值不是被监听的事实或者是一个删除操作，则激发所有相关的类节点。如果新添加的事实是被监听的事实，即此事实满足某一变量绑定集合，则激发相应规则节点。转步骤4。
4. 检查新添加的实例化条件元素或者删除信息，确定是否所有的条件元素都被满足或者部分不满足。如果全部满足，则执行RHS部分的操作。如果部分不满足，则修改相应条件元素的状态。如果没有“停止”操作则转步骤2，否则结束算法。
3.2 匹配过程示例
HAL伪双向网络
上文的实例在HAL算法中的匹配如下所示：
添加事实（A 1）。中间节点（x-y）被触发。相应的，(x-y)节点激发B节点，B节点开始监听（B 1 *）来匹配规则1。
加入事实（A 2）。中间节点(x-y)被触发。相应的，(x-y)触发B节点来监听（B 2 *）来匹配规则1。
加入事实（B 1 3）。中间节点（x-y）被触发，触发C节点来监听（C 3）来匹配规则1。
加入事实(B 3 5)。中间节点（x-y）被触发，触发C节点来监听（C 5）同时触发A节点监听（A 3）进行匹配。
加入事实（B 3 7）。触发中间节点（x-y）。触发C节点监听（C 7）。
3.3 讨论HAL比较适合与实时系统的一个原因是，算法中引入了A类型匹配(Type A matching)和B类型匹配(Type B matching)。A类型匹配是指规则中的某个元素匹配成功后可以使整个规则的成功匹配。所有不属于A类型匹配的匹配都叫做B类型匹配。在HAL中，仅A类型匹配需要在全局匹配网络中更新三类节点的信息，B类型匹配中仅需要在两类节点间传递相关局部信息。在实时系统中，涉及到A类型匹配的赋予一个比B类型高的优先级。
HAL达到比较好的性能的是因为把匹配支持结构精简到使用类定义而不是规则定义的单一结构。
把产生式系统应用到实时环境中的一个要求是产生式系统的反应时间不应该超过应用程序所确定的上限。HAL算法，通过适当的修改，可以很好的应用于基于规则的实时系统。通过添加一个第四类节点，即断定节点（the assertion node），可以构建出一个类似的伪双向网络。可以在规则匹配执行阶段确定允许时间的上下限。
对于那些类变量和规则数目一样多的产生式程序，HAL运行时复杂度可能与其他基于规则表示的程序相同。同时，因为遍历HAL的双向网络是一个常数，因此HAL应该允许的更快些。一般，在很多的应用中，规则的数目比类变量的数目要多，HAL在这中情况下表现的更好。
3.4 结论HAL算法的主要特点就是引入了一个全局匹配支持网络。HAL吸收了现有算法的优点，同时减少了匹配时间。同时，通过尽可能减少冗余内容而减少了匹配支持网络。这主要是通过建立相关规则和类直接的启发式反馈通道。相比，其他的匹配算法仅仅使用单向的通信。
未来的工作，要看HAL在大型的基于规则系统中的性能表现，同时看HAL随着规则数目的增多期性能的变化。接下来，进一步优化OPS5系统和与OPS5类似的系统。最终，把HAL充分有效的应用到OPS5与CLIPS的基于规则的系统中。