RETE算法国内外研究现状
时间:2018-04-19 21:28 来源:毕业论文 作者:毕业论文 点击:次
| RETE算法之所以能够进行高效快速匹配，其依据主要有两个：（1）事实匹配的时候时间的冗余性[1]；（2）规则库中规则结构相似性。时间的冗余性主要体现在对相似事实进行匹配的时候，每次都要经过相同的匹配，这样就会造成大量的重复劳动，从而会浪费大量的时间在相同的匹配过程中。结构的相似性主要体现在规则库中的大量规则结构具有相似性，或者某一部分甚至是相同的，即规则的前提中（LHS部分）可能存在着大量相同的模块，那么当一个WME进行匹配规则的前提的过程中，就会产生大量重复匹配计算，由此就会产生了冗余性的问题。例如：21449 规则1： LHS a>b and c RHS d=1 规则2： LHS a>b or b>c RHS d=2 规则3： LHS a>b and b>c RHS d=3 当对这三条规则进行匹配的时候，条件a>b将会进行三次匹配计算，而条件b>c将会进行两次匹配计算，这样总体上就会造成三次的重复匹配计算。当在大量的规则下，如果里面包含的很多重复条件，那么进行的重复匹配计算将会极大的影响匹配效率。极端情况下，将会有大部分的时间被执行在重复匹配计算之中，这样就会大大降低匹配的效率。论文网 而RETE算法就是要解决这样的重复匹配计算问题：我们假设将条件a>b转换为M1，将条件b>c转换为M2，那么规则就会转变成如下情况： 规则1： LHS N1 and c RHS d=1 规则2： LHS N1 or N2 RHS d=2 规则3： LHS N1 and N2 RHS d=3 这样的话，就会将条件a>b(即N1)转换成一个结点，所以只需一次匹配计算即可。同样的，条件b>c（即N2）转换成一个共享的结点，那么只需进行一次匹配计算即可，消除了重复匹配计算。只有当N1中的条件元素a或b发生变化时，才会对N1进行重新计算，而且三个规则只需计算一次N1。同样的道理，只有当N2中的条件元素c或b发生变化时，才会对N2进行重新计算，而且三个规则只需计算一次N2。这种方法将会避免重复计算LHS部分的条件元素，只需通过观察LHS部分的条件元素的相关参数是否发生变化，来对相对应的条件表达式进行更新计算，这样当在进行匹配计算的时候就会节省大量的时间和开销，从而大大提高了匹配效率，实现高效快速的匹配。 2 RETE算法特点 从以上实例可知，相比传统的模式匹配算法，RETE算法具有两个明显的优点：（1）状态保存。事实集合中的所有事实（fact），在每次匹配完成之后所形成的状态都会存储在alpha结点和beta结点相对应的存储区之中，即alpha存储区和beta存储区。并且在下一次事实集合产生改变的时候，大部分的匹配结果的状态都不会发生改变。只有因为少数事实的加入或者删除，才会导致少量的存储状态发生变化。RETE算法就是利用这种匹配状态具有的稳定性，通过保存匹配过程中的结果状态，从而能够避免大量的重复计算，节省了大量的时间。但从另一个角度来讲，RETE算法只适合那些事实集比较稳定的系统。如果事实集经常发生大规模的变化，那么RETE算法状态保存的特点非但不明显，而且还会因为经常性的改动存储状态，造成大量额外计算。（2）结点共享。结点共享主要源于不同规则之中包含着相同的模式，从而可以共享相同的一个结点，这样当事实（fact）进行匹配时，对于不同规则中相同的模式只需要进行一次匹配计算，这将节省大量时间。但是RETE算法也有着一些缺陷[2,3,4,5]：（1）RETE算法不提供对时间敏感模式表达的支持。（2）在alpha结点存储区与beta结点存储区进行连接时，如果其中有一个没有值时，没有行为会激活，这将会降低其推理的效率[6]。 2.2 RETE算法相关发展 (责任编辑：qin) |