正向推理规则引擎中的Rete模式匹配算法研究

2012-11-09魏毅峰郧阳师范高等专科学校数学与财经系湖北十堰442000

长江大学学报(自科版) 2012年7期

关键词：引擎规则

魏毅峰 (郧阳师范高等专科学校数学与财经系，湖北十堰 442000)

正向推理规则引擎中的Rete模式匹配算法研究

魏毅峰 (郧阳师范高等专科学校数学与财经系，湖北十堰 442000)

规则引擎技术是专家系统中的一种比较实用的技术，它的核心算法是Rete模式匹配算法。深入研究了被广泛应用于正向推理规则引擎中的Rete模式匹配算法，对Rete网络的构建和Rete算法的执行全过程进行了详细分析。

规则引擎；正向推理规则引擎；Rete模式匹配算法

Rete算法的核心思想是通过在内存中维护一个极其复杂的数据结构Rete网络来保存中间匹配结果，以达到显著减少计算量的效果，即牺牲内存空间来换取运行时间。Rete网络的构建主要是基于规则的LHS有很大的相似性的这个特点，通过保存规则的条件部分(也称为左端，即LHS, left-hand side)的各个模式的匹配结果，以便别的规则直接利用该模式匹配结果，可以极大地减少重复的匹配运算，从而达到提升模式匹配效率的效果。当前，大部分规则引擎产品的模式匹配算法，基本上都来自于Charles L. Forgy博士于1979 年在其博士论文中提出的Rete算法及其变体， Rete算法是目前在正向推理规则引擎中的效率最高的一个模式匹配算法[1-2]。下面，笔者对Rete网络的构建和Rete算法的执行过程进行了详细的分析。