一种采用扩展Dewey编码非归并的小枝模式查询算法

摘要

小枝模式查询是XML查询中重要的操作,已经有许多种算法提出,如TwigStack和TJFast算法等,但是他们都是基于归并思想的,不能避免大量的不必要的路径归并.本文提出的TwigWM（Twig Without Merging）算法使用部分栈与链表的结构来实现非归并查询,由于从扩展Dewey编码中能够直接得到祖先元素结点的编码,所以TwigWM算法采用扩展Dewey编码.实验结果表明,TwigWM算法要优于TJFast、Twig2Stack等算法.