| 主权项 |
一种针对XML文档的关键字检索方法，其特征在于具体步骤如下：1)提出一个基于栈的回退算法，来进行XML数据库的关键字搜索；2)提出每个返回结果的熵的概念，并以此作为一个评分模型，对关键字检索的结果进行排序；定义形式化XML文档树、XLCA、关键字簇和最小连通树如下：(1)将用户提交的查询定义为一个包含k个关键字的集合W＝{wi|i＝1，...，k}，将XML数据定义为一棵XML文档树如下：一棵XML文档树被表示为一个9元组T＝(V，E，label(v)，depth(v)，pre(v)，lca(V′)，lm(v，V′)，rm(v，V′)，isancestor(v1，v2)，其中：V是树上所有结点的集合，并且每个结点使用自己的Dewey编码作为标识符，如果V中任一个结点v的标签中含有关键字，则称v为T上的一个关键字结点； <mrow> <mi>E</mi> <mo>⊆</mo> <mi>V</mi> <mo>×</mo> <mi>V</mi> <mo>,</mo> </mrow>是树上边的集合；label(v)为标签函数，用来获得任意结点v的标签；depth(v)函数，用来获得任意结点v在树T中的深度，T的根结点的深度是1；pre(v)函数，返回一个可比较的数值用来反映两个结点之间的先序顺序关系，pre(v1)＜pre(v2)表明在先序遍历时v1在v2前面；lca(V′)函数，用来获得v′中所有结点的最低公共祖先结点，其中 <mrow> <msup> <mi>V</mi> <mo>′</mo> </msup> <mo>⊆</mo> <mi>V</mi> <mo>;</mo> </mrow>lm(v，V′)为取得v在V′中的“左邻”结点的函数，v在V′中的“左邻”结点v′为V′中pre值最大的一个满足pre(v′)≤pre(v)的结点；rm(v，V′)为取得v在V′中的“右邻”结点的函数，v在V′中的“右邻”结点v′为V′中pre值最小的一个满足pre(v′)≥pre(v)的结点；isancestor(v1，v2)为一个布尔函数，其中v1和v2是V中任意两个结点，当v1是v2的祖先结点时函数返回true，否则返回false，另外当isancestor(v1，v2)为true时用 <mrow> <msub> <mi>v</mi> <mn>1</mn> </msub> <mo><</mo> <msub> <mi>v</mi> <mn>2</mn> </msub> </mrow>表示；(2)XLCA，XML文档树上的一个结点x是一个XLCA结点，当且仅当以x为根的子树中至少包含一组关键字结点S，并且S满足：(1)S包含所有的关键字；(2)S中的每个结点到x的路径上不存在除x外其它的XLCA结点；(3)关键字簇，一组关键字结点的集合C是一个关键字簇，当：(1)C中包含所有关键字；(2)lca(C)是一个XLCA结点；(3) <mrow> <mo>∀</mo> <mi>v</mi> <mo>∈</mo> <mi>C</mi> <mo>,</mo> </mrow>v到lca(C)的路径上不含有其它XLCA结点；(4)C中加入任何一个其它的关键字结点不能构成一个簇；一个lca(C)为x的簇C又被称为XLCA结点x的簇；SLCA方法是找出一部分簇，并且每个簇中结点的LCA都是一个SLCA；(4)最小连通树，一个结点集合S的最小连通树被定义为以lca(S)为根，以descendant(S)中的所有结点为叶子的树，其中descendant(S)为所有S中不包含后代的结点；步骤1)中，用基于栈的回退方法算法寻找进行所有关键字搜索的XLCA包括下列基本步骤：(a)令每个关键字对应的关键字结点集按XML文档树的先序顺序排列，形成多个关键字集合，并将寻找任意多个关键字集合的XLCA的问题转化为求解两个集合的XLCA的问题；(b)求解任意两个关键字集合的XLCA；(c)寻找所有关键字集合的簇；(1)将寻找任意多个关键字集合的XLCA的问题转化为求解两个集合的XLCA的问题基于上述定论，存在下述两个结论：结论1.一组关键字结点{v1，…，vk}分别对应关键字{w1，…，wk}，则它们的最小连通树MCT({v1，…，vk})中至少包含一个{w1，…，wk}的XLCA结点；结论2.令Si(i＝1，…，k)是T上所有标签中含有关键字wi的结点的集合，定义xlca(S1，…，Sk)为k个关键字在XML文档树上的所有XLCA结点的集合，则对于任意k＞2以下公式成立：xlca(S1，…，Sk)＝xlca(xlca(S1，…，Sk-1)，Sk)；由结论2可以将求任意多个关键字的XLCA的问题转化为求解两个集合的XLCA的问题，并且可以在求XLCA的过程中求得所有簇；给定两个关键字集合S1和S2，两者中的关键字结点都按照先序顺序排列，首先将集合S1中的所有结点复制并加入S2使S2成为一个所有结点按先序顺序排列的集合S12，同时令S1中每一个结点指向S12中自己的拷贝，S12中每个结点由标识标示出原本是属于S1还是S2，由此每个S1的结点在S2中的左邻或右邻可以方便的从S12中相应位置往左或右遍历获得；(2)求解任意两个关键字结点集合的XLCA其基本步骤是：(a)遍历关键字结点集合，寻找SLCA，同时记录所有可能成为SLCA的结点以及它们对应的场景；(b)每找到一个SLCA后，将它的后代结点在所有关键字集中删除，并“回退”到前面的场景，计算由于当前SLCA的删除产生的新的SLCA结点；(c)当前面的场景不能再找出SLCA时，则继续遍历寻找后面的SLCA结点；(3)求解所有关键字结点集合求解步骤如下：(a)在得到两个集合的XLCA集合Xlcas之后，再以Xlcas和下一个集合作为参数执行get_xlca算法；(b)因为不能保证Xlcas中的结点是按先序顺序排列的，所以必须先将它进行一次排序，这里用快排算法实现；(c)另外Clusters为一个与Xlcas同步的簇的集合，每一次在get_xlca中找到一个XLCA时，将它的后代结点加入该集合的对应项；步骤2)中，搜索结果的评分函数如下：定义最小连通树的熵，对于关键字W和XML文档树T，一棵最小连通树T′的熵E(T′)被用来表示该最小连通树与搜索语句(关键字集合W)的相关程度，它的数值可以由以下公式计算获得： <mrow> <mi>E</mi> <mrow> <mo>(</mo> <msup> <mi>T</mi> <mo>′</mo> </msup> <mo>)</mo> </mrow> <mo>=</mo> <mfrac> <mrow> <mi>α</mi> <mo>·</mo> <mi>depth</mi> <mrow> <mo>(</mo> <mi>root</mi> <mrow> <mo>(</mo> <msup> <mi>T</mi> <mo>′</mo> </msup> <mo>)</mo> </mrow> <mo>)</mo> </mrow> <mo>+</mo> <mi>β</mi> <mo>·</mo> <mfrac> <mrow> <mi>kNum</mi> <mrow> <mo>(</mo> <msup> <mi>T</mi> <mo>′</mo> </msup> <mo>)</mo> </mrow> </mrow> <mrow> <mi>tNum</mi> <mrow> <mo>(</mo> <msup> <mi>T</mi> <mo>′</mo> </msup> <mo>)</mo> </mrow> </mrow> </mfrac> <mo>+</mo> <mi>γ</mi> <mo>·</mo> <mfrac> <mrow> <msub> <mi>f</mi> <mi>k</mi> </msub> <mrow> <mo>(</mo> <msup> <mi>T</mi> <mo>′</mo> </msup> <mo>)</mo> </mrow> </mrow> <mrow> <mi>f</mi> <mrow> <mo>(</mo> <mi>T</mi> <mo>)</mo> </mrow> </mrow> </mfrac> </mrow> <mrow> <mi>α</mi> <mo>·</mo> <mi>h</mi> <mo>+</mo> <mi>β</mi> <mo>+</mo> <mi>γ</mi> </mrow> </mfrac> <mo>,</mo> </mrow>其中：a，β和γ是由管理员根据文档的特性(比如哪些结构返回给用户比较有意义，或者那些特性应该获得更多的重视)定义的三个不小于零的参数；root(T′)是T′的根结点；kNum(T′)和tNum(T′)分别是T′中关键字结点的数目和结点总数；fk(T′)和f(T)分别表示T′中关键字出现的频率和XML文档树T上出现的总词频；而h是T的高度；易知，E的值域为(0，1]。 |
