求解最小子树根节点的新型算法

摘 要：求解最小子树根节点的新型算法，利用Dewey码有重构XML文档的功能，首先为XML文档树设计Dewey码，然后查找关键词对应的Dewey码前缀，根据Dewey码前缀计算对应的先序编码，再逐层（从MinMax（D1，D2……Dn）开始）进行求交集的运算，最后求得的先序编码交集即为最小子树根节点集合，进而根据最小子树根节点得出对应的最紧致片段。

关键词：Dewey码；先序编码；交集；最小子树根节点

中图分类号：TP311 文献标识码：A 文章编号：1674-7712 （2014） 02-0000-01

一、引言

在求解最小子树根节点的新型算法中，主要涉及到的算法有三类，第一类是基于索引的搜索算法，第二类是基于堆栈的算法，最后一类是基于扫描的算法。

第一类算法主要是利用dewey码进行操作，并且在进行操作的过程中是通过修改B+树结构来实现的。第二类算法在存储的过程中利用的存储结构是栈，不再利用B+树，相对来说这类算法比第一类算法操作简单。但是，该算法时间的复杂度和空间的复杂度方面相对第一类算法差。第三类算法在时间复杂度和空间复杂度方面都不是很理想。

根据上述这种情况，本文设计了求解最小子树根节点的新型算法。该算法不仅仅能够保证查全率，并且在查准率方面也有所提高。

二、算法设计

最小子树根节点定义：对应XML数据的标签有向树G=（V（g），E（g），R，A），其中：V（g）表示树中节点的集合；E（g）表示树中所有边的集合；R为标签有向树的根；A表示所有节点标签的集合。另外，关键词序列设为k，则k={k1，k2，…，ki}。那么，最小子树根节点问题就是求解G中所有满足如下条件子树的根节点：（1）子树必须包含关键词序列k，即k中的任一关键词必然分布于该子树的叶节点；（2）子树中不存在更小的子树同样包含k。

最小子树根节点有如下两个特点：（1）如果某节点属于最小子树根节点，那么它必然唯一地从属于某一“层”；（2）根据最小子树根节点定义，如果m个分别包含给定m个关键词的叶节点在第i层有最小子树根节点，那么它们不可能都成为第（i+1）层的最小子树根节点所在子树的叶节点。

根据上述定义和特点，从最大层MinMax（D1，D2……Dn）-1开始，首先应该获得Di中所对应层次中的Dewey前缀码，然后把获得的Dewey前缀码整数化成Dewey的先序编码。先序编码如下：D1’，D2’，……Dn’，根据Dewey先序编码最终求得Di’集合的交集。交集出现两种情况，第一种情况，交集是非空集时，非空集合当中的所有元素就是求得的第一批最小子树根节点；第二种情况，交集为空时，则说明在该层上没有出现对应于关键词的最小子树根节点。最后，当到达了第二层或者是D1’，D2’，……Dn’为空时，此时循环结束，计算终止。

三、实验

查询效率通常是用查准率（Precision）和查全率（Recall）的高低作为其标准。查准率表示查询的有关文档篇数在查出的文档总数中所占的比例。查全率是查出的有关文档篇数在信息库中有关文档总数中所占的比例。一般情况下，没有任何一个检索工具能够查询出所有的信息，所以查全率不容易比较。因此，在评价查询性能时，主要是看查准率，而查准率不可能达到100%。在下表中涉及的是十组数据的查询内容，如表1：

四、结束语

本文对提出的求解最小子树根节点的新型算法进行了实验，通过实验验证，该算法无论是从查准率，还是从查全率方面都有一定程度地提高与改进。

参考文献：

[1]孔令波，唐世渭，杨冬青.XML数据的查询技术[J].软件学报，2007（06）：1400-1418.

[2]宗传霞.基于父节点的XML查询优化算法[J].电子测试，2012（15）：63-65.

[3]孔令磊等.面向XML文档的关键字查询的研究[D].北京：北京交通大学，2008（06）.

[4]孙登峰，玉晓峰.XML查询语言处理[J].计算机工程，2003（13）：4-7.

[5]G.Gou，R.Chirkova.Efciently Querying LargeXml Data Repositories：ASurvey.IEEE Trans.Knowl.Data Eng，2007（10）：13811403.

[作者简介]宗传霞（1985-），女，山东章丘人，烟台南山学院，软件设计师；郝鑫弟（1984-），男，山东龙口人，烟台南山学院。