一种基于有序对的含父子边的小枝模式匹配算法  

Matching algorithm for twig patterns with parent-child edges based on ordered pair

作　　者：王瑞[1] 陶世群[1] 

机构地区：[1]山西大学计算机与信息技术学院,山西太原030006

出　　处：《计算机应用》2009年第10期2778-2780,2790,共4页journal of Computer Applications

摘　　要：随着Internet的发展和网上XML数据规模的与日剧增,如何准确、高效地查询XML数据已经成为研究的热点问题。目前,已经提出了很多小枝模式匹配算法,但没有解决含有父子边的小枝模式查询。针对该问题,提出了一种基于有序对的新算法PCTw ig,通过在查询树和文档树上分别建立父子关系的有序对来进行查询。查询过程中避免了产生中间结果,也不需要进行归并操作,实验证明该算法是有效的。With the development of Internet and the constantly increasing scale of XML data, how to query the XML data exactly and efficiently becomes a hot issue. At present, there are many algorithms for twig pattern matching, but they don＇t have good method to solve the twigs which have parent-child edges. The new algorithm called PCTwig was proposed for this problem, which was based on the ordered pair. The twigs were queried through setting the ordered pair of parent-child relationship on query tree and document tree. In query process, it can avoid useless intermediate result and merge operation. The experiment shows the effectiveness of the approach.

关 键 词：XML文档 XPATH 小枝模式匹配 有序对 父子关系 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]