Computer Engineering and Applications ›› 2012, Vol. 48 ›› Issue (11): 123-128.

Previous Articles     Next Articles

POTwigStack:improved algorithm of XML twig pattern matching

SHI Junfeng1, ZHANG Jianmei2   

  1. 1.The Center of Modern Education Technology, Shanxi University, Taiyuan 030006, China
    2.Changzhi University, Changzhi, Shanxi 046011, China
  • Online:2012-04-11 Published:2012-04-16

POTwigStack:一种改进的XML小枝模式匹配算法

石隽锋1,张剑妹2   

  1. 1.山西大学 现代教育技术中心,太原 030006
    2.长治学院,山西 长治 046011

Abstract: At present, the algorithms of XML query based on twig pattern are hotspot of research. Most of them use recursive functions in accordance with preorder to find matching nodes, which brings too many unnecessary “use and return” operations. To solve this problem, an algorithm named POTwigStack is proposed, which uses a function named POgetNext to find matching nodes. The function is a recursive algorithm in accordance with postorder, which can avoid the useless operations of “use and return” effectively, and therefore the algorithm POTwigStack performs better.

Key words: Extensible Markup Language(XML), query, twig pattern, recursion;preorder, postorder, “use and return&rdquo, operation

摘要: 目前,基于小枝模式的XML查询算法是研究的热点。它们多数在寻找匹配节点的函数中采用了前序递归的算法,产生了大量不必要的“调用/返回”操作。因此,提出了POTwigStack算法,调用POgetNext函数来寻找匹配的节点,该函数采用后序递归的算法,可以有效地避免无用的“调用/返回”操作,从而使算法的效率进一步提高。

关键词: 可扩展标记语言(XML), 查询, 小枝模式, 递归, 前序, 后序, &ldquo, 调用/返回&rdquo, 操作