（计算机科学与技术专业论文）规则引擎中模式匹配算法及规则引擎应用的研究.pdf

知 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他教 育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：童趟 日期： 2 , o l o 另悉 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即：研 究生在校攻读学位期问论文工作的知识产权单位属北京邮电大学。学校有权保留并 向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借阅；学 校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段 保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在年解密后适用本授权书。非保密论文 注释：本学位论文不属于保密范围，适用本授权书。 本人签名：谴 导师签名：篮鲤 日期矽d 墨 日期 o l 。器 |i，h11。i - r o - a 。 北京邮f 乜人学顾 ：o f 究生学位论文 规则引擎中模式匹配算法及规则引擎应用的研究 摘要 近年来计算机应用业界开始致力于将基于规则的专家系统技术 应用于企业服务，由此出现了规则引擎。规则引擎帮助复杂企业级应 用分离其中随外部条件不断变化的业务规则，分离商业决策者的商业 决策逻辑和应用开发者的技术决策，以实现应用系统的灵活性。 本文研究了规则引擎中模式匹配算法，并从功能性和易整合性上 对最常用的r e t e 算法进行了改进。在规则中引入或逻辑、非逻辑和 存在量词来扩展了规则的表示能力，同时为了不增加算法的复杂度， 本文提出了规则拆分算法和初始事实策略，从功能性上对r e t e 算法 进行了改进。当用普通对象替代由规则引擎a p i 管理的事实后，引入 了影子代理策略从易整合性上对r e t e 算法进行了改进。本文详细阐 述了规则引擎的系统架构，并在算法研究的基础上，实现了规则引擎 中模式匹配系统的系统原型。 本文参照j a v a 规则引擎规范，设计了c + + 规则引擎通用接口供 系统开发人员和规则引擎厂商参考。最后本文还提出了一套规则引擎 与应用系统的整合方案，同时将电信中内容计费系统向基于规则引擎 的内容计费系统改进，对规则引擎与应用系统的整合方案进行了验 证，对规则引擎中的模式匹配系统进行了测试。 关键字规则引擎模式匹配r e t e 算法 北京邮电大学硕一f ：研究生学位论文 l l 趴 北京邮电人学硕：i ：研究生学位论文 r e s e a r c ho ni a t t e r nm a t c ha l g o r i t h m i nr u l ee n g i n ea n da p p l i c a t i o nf o r r u l ee n g i n e a bs t r a c t i nr e c e n t l yy e a r s ，s o f t w a r ea p p l i c a t i o ni n d u s t r yi sd e d i c a t e dt oa p p l y r u l e b a s e de x p e r ts y s t e mt e c h n o l o g yt oe n t e r p r i s es e r v i c e ，w h i c hs p u r r e d t h ew i l di n t e r e s t si nr u l ee n g i n es y s t e m s b ys e p a r a t i n gb u s i n e s sr u l e s f r o mt h es p e c i f i c e n t e r p r i s ea p p l i c a t i o n ，t h er u l ee n g i n es y s t e mc a n s i g n i f i c a n t l yr e d u c et h eu n d e r l y i n gc o m p l e x i t yo fv a f i o u sa p p l i c a t i o n sa s w e l la sh e l p i n gt oa c h i e v eg o o ds y s t e mf l e x i b i l i t y i nt h i sw o r k , w ef o c u so nt h er e s e a r c ho nt h ep a t t e mm a t c h a l g o r i t h mi nr u l ee n g i n e ，a n dr e s o l v et oi m p r o v er e t ea l g o r i t h mf r o m b o t h f u n c t i o n a l i t ya n di n t e g r a t i o n w h e n o r l o g i c ，n o tl o g i c a n d e x i s t e n t i a lq u a n t i f i c a t i o na r ei n t r o d u c e dt oe n h a n c er u l e s r e p r e s e n t i n g a b i l i t y , r e t ea l g o r i t h mw i l lb e c o m ec o m p l i c a t e d i no r d e rt or e d u c et h e c o m p l e x i t y , t h i sw o r kp r o p o s e sar u l ed e c o m p o s i t i o na l g o r i t h ma n di n i t i a l f a c t s t r a t e g y t o i m p r o v er e t ea l g o r i t h m f r o mt h e p e r s p e c t i v e o f f u n c t i o n a l i t y b yu s i n gc o m m o no b j e c t si n s t e a do ff a c t sm a n a g e db yr u l e e n g i n ea p i ，s h a d o wp r o x ys t r a t e g yi s i n t r o d u c e dt o p r o v i d ee a s y i n t e g r a t i o nf o rr e t ea l g o r i t h m t h i sp a p e rp r o p o s e san o v e la r c h i t e c t u r e i i i 北京邮电人学硕+ ：研究生学位论文 o ft h er u l ee n g i n es y s t e m ，a n di m p l e m e n t sap r o t o t y p eo ft h ep a t t e r n m a t c h s y s t e mi nr u l ee n g i n e t h i s p a p e rp r o v i d e sc + + r u l ee n g i n eg e n e r a li n t e r f a c ef o rt h e r e f e r e n c eo fs y s t e md e v e l o p m e n t e n g i n e e r sa n dr u l ee n g i n ev e n d o r s t h i s p a p e ra l s op r o p o s e sas o l u t i o no nt h ei n t e g r a t i o no fr u l e e n g i n ei n t o a p p l i c a t i o ns y s t e ma st h ef o l l o w i n gt h r e es t e p s ：f i r s tc o n s t r u c t i n gt h ed a t a m o d e la n dc o n d i t i o nm o d e lt od e s c r i b et h ed a t a s e tt h a tw i l lb ei n s e r t e d i n t ot h er u l ee n g i n eb ya p p l i c a t i o ns y s t e m ，t h e nr e v i s i n gt h ec o n d i t i o n p a r t i nt h e o r i g i n a la p p l i c a t i o ns y s t e mb yi t e r a t i v er e v i s i o ns t r a t e g y , f i n a l l yi n v o k i n gr u l ee n g i n ea c c o r d i n gt ot h eo r d e rp r e s e n t e di nt h i sw o r k i nt h ee n do ft h i sp a p e r , w ev e r i f yt h ei n t e g r a t i o ns o l u t i o na n dt e s tt h e p a t t e r nm a t c hs y s t e mb ye m b e d d i n gr u l ee n g i n ei n t oc o n t e x t b i l l i n g s y s t e m k e yw o r d s ：r u l e e n g i n e p a t t e r nm a t c h r e t ea l g o r i t h m i v _ 一 r ， 北京邮电人学硕一l j 研究生学位论文 目录 摘要i a b s t r a c t i i i i 第一章引言1 1 1 论文背景及目的1 1 2 论文工作及成果4 1 2 1 规则引擎的研究4 1 2 2 规则引擎中模式匹配系统的研究与实现4 1 2 3 规则引擎通用接口的研究4 1 2 4 规则引擎与应用系统的整合。4 1 3 论文结构4 第二章规则引擎介绍6 2 1 基于规则的专家系统及其原理6 2 2 知识表示产生式规则8 2 2 1o p s 5 系统中规则表示9 2 2 2c l i p s 中规则表示l o 2 2 3d r o o l s 中规则表示1 1 2 3 规则引擎核心模式匹配算法1 3 2 3 1r e t e 算法1 3 2 3 2t r e a t 算法l8 2 3 3l f a 算法2 0 2 3 4l e a p s 算法2 l 2 4j a v a 规则引擎a p i ( j s r 9 4 ) 2 3 第三章规则引擎中模式匹配系统设计与实现2 5 3 1 业务规则管理系统2 5 3 2 规则编译系统2 6 3 3 模式匹配系统3 0 3 3 1r e t e 算法改进3 4 3 3 2 规则编辑4 3 3 3 3 运行执行环境4 6 北京邮电人学硕1 ：研究生学位论文 第四章规则引擎通用接口5 2 4 1 运行时客户端通用接口。5 3 4 2 规则管理通用接口。5 5 第五章规则引擎整合方案及系统测试5 6 5 1 规则引擎整合方案5 6 5 1 1 构建模型5 7 5 1 2 定义规则5 7 5 1 3 调用规则引擎5 8 5 2 整合方案验证及规则引擎测试一5 9 第六章研究总结及展望6 5 6 1 课题工作总结。6 5 6 2 下一步的研究方向6 5 参考文献6 7 致谢6 9 作者攻读学位期间发表的学术论文7 0 北京邮电大学硕i ：研究生学位论文 1 1 论文背景及目的 第一章引言 复杂企业级项目的开发以及其中随外部条件不断变化的业务规则，迫切需要 分离商业决策者的商业决策逻辑和应用开发者的技术决策，并把这些商业决策放 在中心数据库或其他统一的地方，让它们能在运行时可以动态地管理和修改从而 提供软件系统的柔性和适应性。 企业管理者对企业级i t 系统的开发有着如下的要求：( 1 ) 为提高效率，管理 流程必须自动化，即使现代商业规则异常复杂；( 2 ) 市场要求业务规则经常变化， i t 系统必须依据业务规则的变化快速、低成本的更新；( 3 ) 为了快速、低成本的 更新，业务人员应能直接管理i t 系统中的规则，不需要程序开发人员参与。而 项目开发人员则碰到了以下问题：( 1 ) 程序= 算法+ 数据结构，有些复杂的商业规 则很难推导出算法和抽象出数据模型；( 2 ) 软件工程要求从需求 设计 编码，然 而业务规则常常在需求阶段可能还没有明确，在设计和编码后还在变化，业务规 则往往嵌在系统各处代码中；( 3 ) 对程序员来说，系统已经维护、更新困难，更 不可能让业务人员来管理【巧j 。 基于规则的专家系统的出现给以开发人员解决上述问题的契机。规则引擎由 基于规则的专家系统中的推理引擎发展而来，是一种嵌入在应用程序中的组件， 实现了将业务决策从应用程序代码中分离出来，并使用预定义的语义模块编写业 务决策，接受数据输入，解释业务规则，并根据规则做出业务决策。规则引擎优 于“i f t h e n ”这样的硬编码，也优于脚本框架，规则引擎具有以下的优点【2 i 】： 声明式编程，规则引擎允许业务人员描述业务规则，而不用去考虑系统如何 实现。声明式编程使规则更容易对复杂的问题进行表述，并使规则比编码更 容易阅读。规则系统能够解决非常困难的问题，最终给出解决方案，并对解 决问题的过程进行解释。 逻辑与数据分离，数据保存在领域对象中，逻辑保存在规则中。这根本性的 打破了面向对象系统中将数据和逻辑耦合起来的局面，这点是有利的也是不 利的，在于使用者的观察角度。因为逻辑保存在规则中，所以当逻辑发生改 变时更容易被维护，这在跨领域或多领域的逻辑中尤其有用。取代了逻辑被 分散在多个领域对象和控制器中，逻辑将被组织在一个或数个清晰的规则文 件中。 北京邮电人学硕i ：g f 究生学位论文 速度及扩展性，r e t e 算法、l e a p s 算法以及衍生出来的d r o o l s 中r e t e o o 算 法，提供了领域对象数据和规则模式匹配一种高效方法。当数据集不完全改 变时，因为规则引擎能够记忆之前的部分匹配，这种模式匹配算法尤为高效。 知识集中化，通过使用规则，将建立一个可执行的规则库。规则库是现实业 务策略的唯一对应，理想情况下可读性高的规则还可以被当作文档使用。 解释机制，通过将规则引擎的决断与决断的原因一起记录下来，规则系统提 供了很好的“解释机制”。 易懂的规则，通过建立对象模型，非技术人员与领域专家可以用接近自然语 言的方式来编写规则，并用他们自己的逻辑来理解规则。 规则引擎也有缺点：1 ) 规则引擎产品价格昂贵，通常很容易就达到7 位数。2 ) 除了主要的行业规范和众多记录在纸上的标准外，规则引擎缺乏事实上的标准。 3 ) 随着越来越多的软件项目采用敏捷、轻量级的快速开发方法，规则引擎这种 重量级的工具的使用范围变得狭窄。 规则引擎有着自己的应用时机，当没有令人满意的传统程序设计方法能够解 决某个问题时，系统就可以考虑使用规则引擎。所谓没有传统解决方法是指：1 ) 对于传统代码来说，问题需要的精确度太高。这种问题可能并不复杂，但是你找 不到一种稳定的方法去建立它。2 ) 问题超越了任何有明显运算法则的方案。它 是一个难以解决的复杂问题，没有明显的传统解决方案或者问题没有一个准确的 定论。3 ) 业务逻辑经常发生改变，逻辑本身是简单的( 但不是指过于简单) ， 但是规则经常发生变化。在许多软件组织中正式版本的间隔是较长并且较少的， 规则可以在适当的安全前提下帮助提供一定的敏捷性。4 ) 领域专家( 或者业务 分析师) 是非技术人员，领域专家通常对业务规则和流程具有很好的认知，领域 专家通常是不了解软件技术的人员，但是具有很好的逻辑性。规则能够让领域专 家用自己的术语来描述业务逻辑，当然他们仍然需要严密的思考和拥有良好的逻 辑思维能力。 在一个面向对象的应用中，规则引擎通常被用在包含业务逻辑的关键部分 ( 具体与应用相关) ，特别是在十分繁杂凌乱的部分。这是对面向对象中将所有 逻辑封装在对象中的一个倒置。但这并不是说应该抛弃对象模型，相反的来说在 任何一个现实应用中业务逻辑仅仅是应用的一部分。如果在原来应用程代码中有 很多“i f e l s e ”、“s w i t c h c a s e 和其它凌乱的逻辑，程序员总是要回过 头去修改它们( 可能是由于提供给程序员的逻辑是错误的，或是程序员的理解变 化了) ，那么可以考虑使用规则。如果系统设计人员面对的问题没有合适算法或 者模式来解决的时候，也可以考虑使用规则。 规则引擎可以被嵌入应用程序，或者作为一个服务使用。通常规则被当作一 2 。北京邮f 毪人学硕1 ：研究生学位论文 个有状态的组件使用因此它们通常是应用程序中一个完整的部分。如果考虑 在组织中使用规则，那么在产品中更新规则的方法是很重要的( 因为更新规则的 方法选择很多，但是不同的组织问有不同的需要，这通常超出了应用者项目团 队的控制) 。 规则引擎只是一个复杂的应用或方法中的一部分。实际上，规则引擎不是用 于规则的工作流引擎或进程管理工具。因为规则引擎是动态的( 动态的在这里意 味着规则可以象数据一样保存、管理和更新) ，它们通常被看作发布软件系统的 一种解决方案( 解决软件系统由于灵活性不足，而过早的被遗弃) 。如果应用程 序厂商希望使用规则引擎来防止应用程序被遗弃，则应当意识到在可以写出公开 发布的规则时，规则引擎能够以最佳方式工作。应用程序厂商也可以采取另一种 解决方案，即数据驱动的设计或者脚本流程引擎，在数据驱动设计中可以通过 控制表中保存的元数据来影响应用的行为来增加系统的灵活性，在脚本流程引 擎中可以采用带有能够在数据库中管理并能够动态更新的脚本来增加系统的灵 活性。 现阶段有很多版本的j a v a 规则引擎如i l o gj r u l e s 、j b o s sd r o o l s 等，但是 c c + + 规则引擎相当稀少，本文对规则引擎核心模式匹配系统进行研究并对规则 的模式匹配算法一r e t e 算法【l j 进行改进，然后给出了c c + + 版本的实现。 过去大部分的j a v a 规则引擎开发并没有规范化，有其自有的a p i ，这使得 其与外部程序交互集成不够灵活。转而使用另外一种产品时往往意味需要重写应 用程序逻辑和a p i 调用，代价较大。规则引擎工业中标准的缺乏成为令人关注 的重要方面。2 0 0 3 年1 1 月定稿并于2 0 0 4 年8 月最终发布的j s r9 4 9 j ( j a v a 规 则引擎a p i ) 使得j a v a 规则引擎的实现得以标准化。j a v a 规则引擎a p i 是访问 规则引擎的标准企业级a p i 。j a v a 规则引擎a p i 允许客户程序使用统一的方式和 不同厂商的规则引擎产品交互，就像使用j d b c 编写独立于厂商访问不同的数据 库产品一样。本文参照了j a v a 规则引擎规范，对c c + + 规则引擎接口进行研究， 制定出通用接口供应用程序调用和c c + + 规则引擎厂商参考。 规则引擎本身作为一种应用程序的组件，应用程序为了提高系统的灵活性而 使用规则引擎。拥有现有应用系统的厂商不愿意改变目前系统的框架，只是希望 使程序的局部嵌入规则引擎，从而最低限度的减少成本和风险。本文提出了一套 规则引擎与应用系统的整合方裂3 1 】，来保证应用系统以较小的代价嵌入规则引 擎，而提高系统的柔性。 北京邮电人学硕l ：研究生学位论文 1 2 论文工作及成果 1 2 1 规则引擎的研究 a ) 对基于规则的专家系统的系统架构及其原理进行了研究，对基于规则的推理 引擎的推理方式进行了研究。 b ) 对知识的表示方式产生式规则进行了研究，并描述了本文实现的c + + 规 则引擎的规则的表示方法。 c ) 研究了几种常见的规则的模式匹配算法。模式匹配算法是规则引擎的核心部 分，模式匹配算法的好坏直接关系到规则引擎的可用性和工作的效率。 1 2 2 规则引擎中模式匹配系统的研究与实现 a ) 介绍了规则引擎的系统架构，对规则引擎各模块之间的关系进行了研究，着 重介绍了模式匹配系统。 b ) 对当今规则引擎中采用最多的模式匹配算法叫e t e 算法进行优化，主要是 从算法的功能上和易整合性上进行考虑。 c ) 对模式匹配系统的需求进行分析，更小粒度的划分了模式匹配系统，并对各 个模块进行了详细设计。 1 2 3 规则引擎通用接口的研究 a ) 对j a v a 规则引擎规范j s r 9 4 进行了研究。 b ) 设计c + + 规则引擎通用接e l 。使得应用系统更容易调用规则引擎，同时也给 c + + 规则引擎厂商提供了参考。 。 c ) 封装本文实现的c + + 规则引擎的接口为通用接口，即对设计的通用接口进行 实现。 1 2 4 规则引擎与应用系统的整合 a ) 对应用系统中使用规则引擎的方法进行了总结，包括如何修改原有应用系统 和如何用规则表示原有应用系统的逻辑等。 b ) 提出了规则引擎与应用系统的整合方案，通过电信中内容计费系统向基于规 则引擎的内容计费系统的改造，验证了该整合方案的可行性。 4 北京邮电人学硕士研究生学位论文 1 3 论文结构 本论文按以下章节进行组织： 第一章为引言部分，主要介绍论文背景和目的，论文的工作及成果和论文的 结构。 第二章介绍了规则引擎，其中包括基于规则的专家系统及其原理，知识表示 产生式规则的多种表现形式，几种常见的规则的模式匹配算法，以及对规则 引擎规范j s r 9 4 进行了介绍。 第三章介绍了规则引擎中模式匹配系统的研究与实现，首先介绍了规则引擎 的系统整体架构，然后对三个子系统进行了介绍。并着重阐述了模式匹配系统， 其中包括了r e t e 算法的改进以及各个功能模块的详细设计。 第四章介绍了规则引擎通用接口，首先说明了通用接口应该包含的内容，然 后分两个部分设计了通用接口。 第五章介绍了规则引擎与应用系统的整合方案，并实现了某省级电信内容计 费系统向基于规则的内容计费系统的改造。 第六章对全文做出了总结，并指出了下一步的工作。 5 北京邮电人学硕l ：研究生学位论文 第二章规则引擎介绍 2 1 基于规则的专家系统及其原理 规则引擎起源于基于规则的专家系统，而基于规则的专家系统又是专家系统 的其中一个分支。 专家系统【2 9 】【3 0 1 是早期人工智能的一个重要分支，它可以看作是一类具有专 门知识和经验的计算机智能程序系统，一般采用人工智能中的知识表示和知识推 理技术来模拟通常由领域专家才能解决的复杂问题。一般来说，专家系统= 知识 库+ 推理机，因此专家系统也被称为基于知识的系统。一个专家系统必须具备三 要素：i 领域专家级知识；2 模拟专家思维；3 达到专家级的水平。 基于规则的专家系统( i 强e s ) 的知识表示方式为产生式规则，r b e s 包括 三部分：r u l eb a s e ( k n o w l e d g eb a s e ) 、w o r k i n gm e m o r y ( f a c tb a s e ) 和i n f e r e n c e e n g i n e ，图2 1 为基于规则的专家系统架构图。 图2 - 1 基于规则的专家系统架构 其中知识库( r u l eb a s e ) 是中心数据库，存储各类模拟人类问题求解的产生 式规则。一个规则分为前件部分和后件部分。前件( a n t e c 9 d e n t ) ：又称条件部分、 模式部分或左部( l e f t h a n d - s i d e ，l h s ) ，是规则触发的条件。单独的条件称为条 件元素或一个模式。后件( c o n s e q u e n t ) ：又称右部( r i g h t h a n d s i d e ，r h s ) ，是规则 触发时将要执行的一系列行为。 工作存储区( w o r k i n gm e m o r y ) 是应用于规则的事实的全局数据库，它保 存系统的当前状态。 推理引擎( i n f e r e n c ee n g i n e ) 包括三部分：模式匹配器( p a t t e r nm a t c h e r ) 、 议程( a g e n d a ) 和执行引擎( e x e c u t i o ne n g i n e ) ： 模式匹配器( p a t t e r nm a r c h e r ) ：通过比较事实和规则的模式部分，决定选 6 北京邮电人学硕：嘲口f 究生学位论文 择执行哪个规则，何时执行规则。模式匹配是基于规则的推理机的关键， 它决定了推理机的推理效率。 议程( a g e n d a ) ：由推理机创建的一个规则优先级表，这些规则都匹配工 作内存中的事实。如果同时有多个规则和事实匹配，则优先级最高的被 触发。被触发规则的动作可能会产生新的事实，新的事实也被加入工作 内存。 执行引擎( e x e c u t i o ne n g i n e ) ：负责执行议程中的规则和其他动作。 推理引擎的推理步骤如下： 1 将初始数据输入工作存储区。 2 使用模式匹配器比较规则库中的规则和数据。 3 如果执行规则存在冲突( c o n f l i c t ) ，即同时激活了多个规则，将冲突的 规则放入冲突集合。 4 解决冲突，将激活的规则按顺序放入a g e n d a 。 5 使用执行引擎执行a g e n d a 中的规则。重复步骤2 至5 ，直到执行完毕所 有a g e n d a 中的规则。 上述即是规则引擎的原始架构，规则引擎就是从这一原始架构演变而来的。 和人类的思维相对应，推理引擎存在两种推理方式：演绎法前向推理 ( f o r w a r d - c h a i n i n g ) 和归纳法逆向推理( b a c k w a r d c h a i n i n g ) 。两种方法都使 用的系统称为混合型产生式规则系统。理解这两种操作方法是理解产生式规则系 统之所以不同和怎样从中选择最合适的系统的关键。 正向推理是数据驱动的，它是用事实去匹配规则，事实被传递到工作存储区 中，在那里有一个或多个规则与这些事实匹配，并由a g e n d a 安排执行规则。 图2 - 2 正向推理 7 北京邮电大学硕：i ：研究生学位论文 逆向推理是由目标驱动的，它是用规则( 规则中的条件) 去匹配事实，这意 味着我们从一个引擎需要满足的结论开始进行推理。在这个结论不能满足时，将 搜索一些能够满足的结论来推理，称为子目标，这些子目标将帮助完成当前目标 的某些未知部分引擎持续这个过程，直到最初的结论被证明或没有可证明的 子目标。 2 2 知识表示产生式规则 图2 - 3 逆向推理 用产生式规则进行的知识表示，在不同的系统中有着不同的具体形式，但大 体上都是条件部分推导出执行部分的形式。下面首先以三个系统中产生式规则说 北京邮电大学硕i j 研究生学位论文 明知识表示的具体形式，再进行比较后说明本文所采用的规则形式。o p s 5 ( t h e5 t h g e n e r a t i o no fo 伍c i a lp r o d u c t i o ns y s t e m ) 以第一个成功用于专家系统的产生式系 统计算机语言而著称，o p s 系统是由卡内基梅隆大学c h a r l e sf o r g y 在上世纪7 0 年代用l i s p 语言开发的，它是基于r e t e 算法的，其效率之高以至于可以解决包 含上千个规则的问题【2 2 1 。c l i p s ( cl a n g u a g ei n t e g r a t e dp r o d u c t i o ns y s t e m ) 是一个 用于构建专家系统的公共领域的软件工具。第一个版本的c l i p s 是由美国国家 航空航天局一约翰逊航空中心研发的。由于c l i p s 的快速、高效和免费，它有 可能是现在最广泛使用的专家系统工具。尽管现在c l i p s 在公共领域使用，但 是仍然由原作者g a r y r i l e y 维护和更新，c l i p s 是由c 语言编写，其接口与l i s p 语言非常相似【2 3 1 。d r o o l s 是一款成功的开源规则引擎，它采用面向对象的方式实 现了高效的模式匹配r e t e 算法，它采用的语言是当前流行的面向对象的语言 j a v a 。 2 2 1o p s 5 系统中规则表示 一个工作存储区中的事实对象，加上其属性值对，称为一个工作存储区元 素( w o r k i n gm e m o r ye l e m e n t s ，w m e ) ，其形式为( e l e m e n t fa t t r i b u t e lv a l u e lf a t t r i b u t e 2v a l u e 2 ) ，符号f 用于区分属性和值。下面是一个典型的w m e ，它 表示类e x p r e s s i o n 的名字为e x p r l ，第一个参数为2 ，操作为枣，第二个参数为v ： ( e x p r e s s i o n fn a m e e x p r lfa r g l2fo p fa r 9 2 模式是对w m e 的部分描述，如果它的每一个属性与w m e 的相对应的属性匹配 的话，就说该模式与w m e 匹配。比如模式 ( e x p r e s s i o n fn a m ee x p r lla r g l2 ) 与w m e ( e x p r e s s i o nfn a m ee x p r l fa r g l2fo r , 宰 趣2v ) 匹配。在o p s 5 中一些非常量符号对于定义模式也是可用的，其中有两个最重要 的元素是变量和谓词。一个变量以符号 结束。谓词包括= ( 等于) ， ( 不等) ， ( 大于) ， = ( 大于或等于) 。 个谓词被放在属性和值的中间，用来表示被匹配的值必须与模式中的值相关。 一个规则的左部由一系列模式组成。规则的右部是一系列无条件动作。动作 包括m a k e ，m o d i f y ，r e m o v e 。m a k e 表示构造一个新的事实元素，并加入到 w o r k i n gm e m o r y 中；m o d i f y 修改己有元素的属性值；r e m o v e 用于从w o r k i n g m e m o r y 中删除已有的事实。 一个o p s 5 规则有以下5 部分组成：1 ) 符号p ；2 ) 规则的名字；3 ) 条件部分 9 北京邮l 乜人学硕f ：研究生学位论文 l h s ；4 ) 符号 ；5 ) 执行部分r h s ， o p s 5 规则分别表示乘以0 和加上0 ， ( p t i m e o x 每一项都在圆括号中。下面是典型的两条 第三个参数存放运算的结果。 ( g o a lft y p es i m p l i f yfo b j e c t ) ( e x p r e s s i o n fn a m e f a r g l0 fo p 幸) ( m o d i f y 2f a r 9 30 ) ) ( pp l u s o x ( g o a lft y p es i m p l i f yfo b j e c t ) ( e x p r e s s i o nfn a m e f 删0f0 p +fa r 9 2 ) _ ( m o d i f y 2 f a r 9 3 ) ) 2 2 2c l i p s 中规则表示 c l i p s 中采用模块的形式方便用户更好的书写规则，荚形式如下 ( d e r e m p l a t ec h e e s e ( s l o tn a m e ( t y p es t ri n g ) ) ) ( d e f l e m p l a t ep e r s o n ( s l o tn a m e ( t y p es t r i n g ) ) ( s l o tf a v o r i t e c h e e s e ( t y p es t r i n g ) ) ) 定义了两个名为c h e e s e 和p e r s o n 的模板，其实相当于面向对象中定义的两个类， c h e e s e 这个模板有一个属性名为n a n l e ，类型为s t r i n g ；p e r s o n 这个类有两个属性 分别为n a m e 和f a v o r i t e c h e e s e ，类型都为s t r i n g 。其中规则的表示如下 ( d e f r u l el i k e ( c h e e s e ( n a m e ? c n a m e ) ) ( p e r s o n ( n a m e ? p n a m e ) ( f a v o r i t e c h e e s e ? c n a m e ) ) = ( p r i n t o u tt ? p n a m e ”l i k ec h e e s e ”? c n a m ec r lo 1 0 北京邯i 乜人学硕i ：研究生学位论文 ) 规则表述的逻辑为：如果某人喜欢的奶酪名字与当前工作区中某奶酪的名字相 同，则打印一句话。以? 开头的表示一个变量，如变量? c n a m e 绑定在c h e e s e 的 n a m e 属性上。插入事实的结构和模板的形式表示一致，如下 ( a s s e l l ( c h e e s e ( n a m e ”a ”) ) ( a s s e l l ( p e r s o n ( n a m e ”z h a n g s a n ”) ( f a v o f i t e c h e e s e ”a ”) ) ) 上述代码在c l i p s 中的运行截图如图2 - 4 所示。 c l i p s ( p p d e ft e m p l a t ec h e e s e ) ( d e et e m p l a t em a i n ：c h e e s e ( s l o tn a m e ( t y p es t r i n g ) ) ) c l i i ：x 3 ( p p d e ft e m p l a t ep e r s o n ) ( d e ft e m p l a t em a i n ：p e r s o n ( s l o tn a 3 t e ( t y p es t r i n g ) ) ( s l o tf a v o r i t e c h e e s e ( t y p es t r i n g ) ) ) c l i p s ( p p d e f r u l el i k e ) ( d e f r u l em a i n ：1 i k e ( c h e e s e ( n a m e ? c n a m e ) ) ( p e r s o n ( n a m e ? p n a m e ) ( f a v o r i t e c h e e s e ? c n a m e ) ) 互 ( p r i n t o u tt ? p n a m e 。1 i k ec h e e s e 。? c n a m ec r l f ) ) c z i p s ( a s s e r t ( c h e e s e ( n a m e 。a 。) ) ) ( f a c t - i c z i p s ( a s s e r t ( p e r s o n ( n a m e 。z h a n g s a n 。) ( f a v o r i t e c h e e s e 。矗。) ) ) c z i p s ( r u n ) z h a n g s a n1i k ec h e e s ea c l i p s 一 i 图2 - 4c l i p s 中的运行截图 2 2 3d r o o l s 中规则表示 d r o o l s 规则指定“w h e n 作为一系列条件的集合( 称为l h s ) ，然后在“t h e n ” 中指定一系列操作( 称为r h s ) 。规则必须有一个名称，并且在一个包中是唯一 的。如果你在同一个d r l 中定义同名规则两次，在装载时将产生一个错误，其 语法如图2 5 所示。 北京邮电大学硕十研究生学位论文 图2 5d r o o l s 规则语法 属性是可选的，最好保持每行一条，如图2 - 6 描述：规则的l h s 部分跟随 w h e n 关键字( w h e n 最好在单独的一行上) ，r h s 部分跟随t h e n 关键字( 最好也 单独一行) 。规则使用e n d 关键字结尾。规则不能进行嵌套。 图2 - 6d r o o l s 规则书写格式 d r o o l s 中的规则文件以d r l 作为后缀名结束，在2 2 2 节表述的规则在d r o o l s 中表示如图2 7 所示，p a c k a g e 是一个规则包的名字定义，它可以包含多条规则， 示例的规则包中只是包含一条规则，i m p o r t 关键字表明引入两个类的定义，关键 字w h e n 和t h e n 之间包含了规则的条件部分，其形式简单易懂，t h e n 和e n d 之间 是规则的执行部分完全符合j a v a 语言语法。 1 2 北京邮电人学硕十研究生学位论文 譬a ( 7 k a g ec o i o r e s c j 4 i m p o r tt o m 暑锄p l e c h e e s e ； i m 蟹o r tc o m s a m pi s p e c s o n - “r u l e ”l i k e ” w h e n c h e e s ec搴c n a z 晤：n 8 m e ) s p e c s o n ：p e r s o ncs p n a m e ：n a 舱，f a v o u r i t e c h e e s ei l 宰c n 锄ei t h e n s y s t e m o u c p r i n t i n ls p n m 曲e + ”l i k e sc h e e s e ”+ $ c n a m e ) ； ，e n d 图2 7 i ) r o o l s 中的规则表示 综合比较上述三种规则的表示形式，d r o o l s 中的规则表示简单易懂，且采用 面向对象的表现形式，所以本文采用类似于d r o o l s 中规则的表示方式，区别在 本文实现是c c + + 规则引擎，其t h e n 和e n d 之间是规则的执行部分的语句要求 符合c c + + 语言语法，不妨将这种规则的表示方式称