基于多槽哈夫曼Trie树的规则引擎快速匹配算法  

A Fast Matching Algorithm for Rule Engines Based on Multi-Slot Hafuman Trie Tree

作　　者：罗谦[1,2] 唐常杰[1] 于磊[3] 郑皎凌[1] 

机构地区：[1]四川大学计算机学院,四川成都610065 [2]中国民用航空总局第二研究所信息公司,四川成都610047 [3]西南交通大学信息科学与技术学院,四川成都610031

出　　处：《四川大学学报（工程科学版）》2011年第5期102-108,共7页Journal of Sichuan University (Engineering Science Edition)

基　　金：国家自然科学基金资助项目(60773169);中国民用航空局科研项目(MHRD200924)

摘　　要：为了提高机场类企业数据在海量规则集合中的匹配能力,提出了基于多槽哈夫曼Trie树(MSTHTrie)的规则引擎快速匹配算法。该算法充分利用了规则点属性名数与规则条数之间的不对称特性,将对规则的线性比对转换为对多槽的并行比对,从而在稳定的空间复杂度下提高了规则引擎的匹配效率。首先对通用规则进行了严格的形式化描述,并在合理假设条件下证明了槽内规则分布命题和动作数定理;然后基于动作数定理提出了简化操作符的MSH tree算法;随之扩展操作类型提出了MSHTrie算法,使规则引擎有了普适性;最后在国内枢纽机场的业务数据上完成对比实验,表明新算法在空间复杂度上较传统线性匹配算法节约了52.6%,匹配性能上与Policytree算法相比提高了21.3%。In order to improve the matching rate for business data with massive rules,a fast matching algorithm of rule engines named Multi_Slot Hafuman Trie Tree（MSTHTrie） was proposed.It changed rule＇s Linear matching into Multi_Slot matching by using the asymmetry of number between rule point＇s attributes and rules.The concepts of general rule was proposed,and the theorem of rule distributing in slot and action number was proved.The MSHTree algorithm was proposed by reducing operator,and the improved MSHTrie algorithm was proposed by extended operators.Extensive experiments over real data of Hub Airport showed the effectiveness of MSHTree algorithm and MSHTrie algorithm.The average Space complexity is decreased by 52.6% and matching time is decreased by 21.3% when it is compared with traditional Linear matching and Policytree.

关 键 词：规则引擎 匹配 多槽 哈夫曼树 TRIE树 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]