基于规则的知识推理算法——RETE算法

6.4.3　基于规则的知识推理算法——RETE算法

在实现蕴涵知识发现推理时使用的是惠普实验室开发的开源Jena 2工具包，它提供了基于规则的推理引擎，使用的算法是RETE算法—一种多模式快速匹配算法。RETE算法是为了解决规则模式如何快速匹配事实这一核心问题，而作为Markov算法的改进而提出来的。

Markov算法(Markov algorithm)是Markov发明的，其基本思想就是把一组按优先级排序的规则顺序作用于输入串，如果最高优先级的规则不适用，则尝试次高优先级的规则，依此类推。如果最低优先级的规则不适用输入串或使用了一个终止规则，则算法结束。Markov算法具有明确的规则控制策略，它总是严格按照规则的优先级别来进行匹配，这对于规则数量较多或规则复杂的推理系统来说是低效的，因为其每一次匹配都是对整个知识库内容将其所有规则严格按优先级别重新匹配一次。在推理系统中，效率是一个重要的问题，不管一个系统的其他方面如何好，如果推理匹配过程较长，导致用户响应时间过长，则这个系统就不会被使用。因此，Markov算法就需要改进，不能对系统知识库去顺序匹配每一条规则。Markov算法的改进之一就是RETE算法，它最先是由美国卡耐基·梅隆大学的Charles L.Forgy在其博士论文中提出的^［25］。

如果知识库中的事实与规则中的模式只需匹配一次，那么推理机就可以检查每条规则，并寻找事实来决定规则的模式是否已满足，如果满足，则将此规则记入内存中。然而在推理过程中，匹配过程不断重复进行。通常，事实库在每次匹配过程中都会被修改，添加新的事实到事实列表中，这些新的事实可能会让先前某些不满足条件的规则的模式得到满足，反之亦然。因此匹配问题成了不断进行的过程，Markov算法的低效也就显而易见了。在每次匹配循环中，随着新事实的添加，必须对已满足条件的规则集合进行维护和更新，并启动再一次的匹配过程。如果每一次匹配之后，像Markov算法一样，对整个新的事实库将所有规则再一次顺序匹配的话，虽然是最简单直接的方法，但其缺点也是致命的:速度太慢。

一般地说，一条规则匹配成功并执行，对事实库的改动是非常小的，一般表现为极少新的断言事实被添加进来，也就是说，推理系统中的事实库随时间改变很慢。相应的是，事实库的每一次匹配变化一般只会影响很少部分的规则，也就是说，一个完整的匹配后，对变动很小的事实库再进行一次所有规则匹配是没必要的。这是因为在再一次的匹配过程中，大多数规则所找到的事实很可能与上一匹配过程是相同的。

推理系统中的规则是不变的，而事实库是变化的。有效的匹配算法应当是在不断匹配过程中，存储记录那些规则是已经匹配好了的，然后只计算那些新添加的事实所引起的必要变化，让新的事实去匹配相应的规则，这就避免了很多不必要的计算。RETE算法正是如此。它的实现就是通过存储不断循环匹配过程的状态，并且只重新匹配事实库中的新事实。也就是说，如果在一次规则匹配执行周期中，某一条规则的一组模式匹配到了规则执行所需4个事实中的3个，那么它就将已经匹配好的这3个事实存入内存中，在下一周期中，就无需对已经匹配好了的3个事实进行检查，只需要重新匹配该规则的第四个模式所匹配的事实了。在规则匹配成功并执行过程中，就有新的断言事实被添加到事实库中，匹配过程的状态才被更新。但如果新添加的断言事实数量与事实库中所有事实和规则的所有模式的总数相比很小的话，匹配速度就会很快。(www.xing528.com)

RETE用内存空间换取时间:匹配的中间结果加入存储器中为以后重用做准备，从而减少匹配的数量。RETE算法存储的匹配中间状态信息，称之为模式部分匹配信息。规则模式的部分匹配是满足规则模式的任何一组事实，比如一条有三个模式的规则对第一个模式，第一和第二个模式，及第一、第二和第三个模式都有部分匹配。一条规则的所有模式的部分匹配也就是该规则的激活。

规则的匹配是通过一个包含了匹配中间结果信息的有向图数据结构来执行。第一层结点被称为alpha结点，每一个alpha结点表示一个单一的模式。当规则中不止一个模式时，alpha结点被beta结点连接起来完成两个结点的联合，该beta结点所存储的就是它连接的。alpha结点所表示模式的部分匹配信息。Beta结点再连接到更远的beta结点，直至生成一个单独的结点。这个最终的结点表示了规则的完全匹配并被执行之后所断言的新事实。

当一个新事实被断言时，一个令牌就被创建并被送入RETE匹配网路中处理该事实类型的alpha结点。令牌是一个关于该事实并包含特殊信息的包，这些特殊信息比如该事实是被肯定还是退回。如果这个令牌在一个alpha结点中匹配模式成功，它将被传到下一结点，同时模式中所有的变量都被存入一张表中，这被称为结点存储。beta结点从alpha结点的存储表中获取并试图将它们合在一起，验证同名的变量是否值也相等。例如，如果一张表中某行包含变量A=1和B=2，另一张表中的一行包含变量A=1和C=3，于是一个新行就被创建在beta结点中，这行包含值A=1，B=2，C=3，于是令牌通过了。如果两张表中A的值不相同就不会生成新的行，令牌也不会被通过。当令牌在RETE网络中走过所有的路径就会出现一个表示整个规则的终端结点。由于令牌到达终端结点，规则中的所有的范式必须已被匹配，因此规则能被激活。

RETE算法的主要优势在于规则的条件仅在一个事实被断言或删除时被再评估。用这种方式，断言一个新的事实仅仅是向网络中传递一个令牌，只有很小数量的匹配被执行。在常规执行中，每一个新的事实都将与每一个规则的每个范式进行比较，这意味着大量的时间复杂度。RETE算法有编译时间和运行时间之分。在编译时间规则被编译到一个判别网络中，由操作代码语言表示。RETE网络是一个数据流网络，在规则环境下表示数据的相关性。在运行时间数据项表示工作存储中内容的变化，称为变换令牌，在网络的根部进入沿着路径执行。变换令牌或者表示向工作存储中添加操作或者表示从中删除操作。网络包含有两种结点:测试结点和联合结点。当一个令牌表示向工作存储区添加数据项。它从根部进入网络按照深度优先的方式在网络中进行处理。

RETE算法的使用大大提高了规则匹配的效率，但是它为保存中间结果占用了大量的存储空间。由于存储空间的几何增长，这一算法不适合大规模的规则数据库。RETE算法的空间复杂度取决于O(R.F.P)，R是规则的数量，F是断言事实的数量，P是每一规则中模式的平均值。不采用RETE算法仅比较规则库的常规运行中的O(F)。为提高RETE算法的存储效率，一些其他的算法也相应提了出来。典型的就是TREAT算法和RETE*算法，前者去掉了beta结点根据需要重新计算了存储空间，后者允许在存储消耗和匹配速度之间选取合适的平衡度^［26］。