基于自动机的XML路由改进算法  

An improved algorithm for XML routing based on finite automata

作　　者：陈继明[1,2] 邹志文[1] 潘金贵[2] 翟磊[2] 

机构地区：[1]江苏大学计算机科学与通信工程学院,江苏镇江212013 [2]南京大学计算机软件新技术国家重点实验室,江苏南京210093

出　　处：《江苏大学学报（自然科学版）》2010年第6期705-709,共5页Journal of Jiangsu University：Natural Science Edition

基　　金：国家自然科学基金资助项目(60533080);江苏大学高级专业人才科研启动基金资助项目(09JDG035)

摘　　要：为了有效提高XML路由技术在分布式虚拟环境中的实用性,基于自动机的XML算法研究,提出了一种高效的XML路由匹配算法——DXFilter.该算法根据分布式虚拟环境特点,在结构匹配时,采用"路径模式"的方法对自动机构建索引,降低了Xpath查询匹配的复杂度;在谓词匹配时,利用不同查询之间公共谓词的相关性,构建路径模式与谓词集合间的映射关系,减少了匹配运算的比对范围.以自主开发的分布式虚拟系统AIMNET为仿真平台,对DXFilter算法进行了试验.结果表明,在虚拟对象发布信息量较大的情况下,DXFilter算法能有效地提高XML信息的路由匹配效率,加快XML路由器上数据包的转发速度,增强系统的实时性和实用性.In order to improve the practicability of XML routing in distributed virtual environment（DVE）,an efficient XML matching algorithm（i.e.DXFilter） was proposed based on the research of finite automata-based XML algorithm.By taking account of the characteristics of DVE in the new algorithm,″path pattern″ was adopted to build indexes for finite automata,which reduced the complexity of matching Xpath queries.To the predicate match,mappings between path patterns and predicate sets were set up based on the correlation of public predicates among different queries,which reduced the matching scope.The DXFilter algotithm was tested based on autonomously-developed distributed virtual system as simulation platform.The results show that in the situation of large amount of publishing events,DXFilter algorithm can effectively improve not only the efficiency of XML message matching but also the packet forwarding speed on XML routers.Therefore,the real-time services and availability of the DVE system are highly improved by this new algorithm.

关 键 词：分布式虚拟环境 XML路由 DXFilter 路径模式 自动机 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]