XML关键字搜索的替代查询生成

# XML关键字搜索的替代查询生成 在信息检索领域，当把正子树集视为答案集时，可将某些比率分别视为精确率和召回率。生成近似替代查询时，通常会比生成替代查询产生更多的查询，且查询质量会下降。因此，需要向用户提供排序后的近似替代查询。 ## 1. 精确率和召回率的定义 给定输入关键字集 $K$ 和 XML 数据库 $T$，设 $R(K, T) = \{C_1, C_2, ..., C_n\}$ 为 $K$ 在 $T$ 中的搜索结果。对于正子树集 $C_i$ 的近似替代查询 $A$，其精确率和召回率的计算公式如下： - 精确率：$precision = \frac{|C_i \cap C'_j|}{|C'_j|}$ - 召回率：$recall = \frac{|C_i \cap C'_j|}{|C_i|}$ 其中，$C'_j \in R(A, T)$，且 $C'_j$ 的见证模式与 $C_i$ 的见证模式等价。替代查询可视为精确率和召回率均为 1.0 的近似替代查询，后续将主要讨论近似替代查询的生成方法。 ## 2. 近似替代查询的生成方法 ### 2.1 朴素生成方法 从分类后的 XML 搜索结果簇中的一组 XML 子树生成近似替代查询。例如，关键字 “Smith Morgan” 的查询结果分为三个簇，以簇 $C_2 = C(book, \{author, editor\})$ 作为正子树集，负子树集由以 “book” 节点为根但不属于正子树的两个子树组成。 生成近似替代查询的最简单方法是： 1. 提取在任何正子树中至少出现一次的所有术语。 2. 过滤出精确率和召回率超过给定阈值的提取术语的子集。 由于近似替代查询 $\{w_1, w_2\}$ 的召回率 $r$ 满足 $r \leq min(p_{w1}, p_{w2})$（$p_{w1}$ 和 $p_{w2}$ 是两个关键字 $w_1$ 和 $w_2$ 在正子树集中的出现频率），所以该方法仅提取超过阈值的标记关键字，然后统计所有近似替代查询并计算其精确率和召回率。具体算法如下： ```plaintext Algorithm 1. Naive method of generating approximate alternative queries Input: a positive subtree set PSS Input: a witness pattern wp that all positive subtrees have Input: threshold values θr and θp 1: c = getAllCommonWords(PSS,θr) 2: get all Dewey inverted lists in c 3: for all subset s of c do 4: E = getELCA(s) 5: select cluster Ei from E such that the element name of the root node of the witness pattern of Ei corresponds to that of wp 6: calculate precision and recall of s 7: end for 8: return all keywords whose precision and recall exceed θp and θr respectively ``` ### 2.2 优化生成方法 朴素方法中，正子树集中出现的公共关键字越多，需要验证的替代查询候选数量就呈指数级增长。该算法通常通过扫描替代查询候选中每个关键字对应的所有倒排列表来验证候选，因此每当验证包含关键字 $w$ 的候选时都扫描其对应的倒排列表，效率较低。 为此，提出一种优化方法，仅扫描一次所有倒排列表来获取所有近似替代查询候选。此方法在处理时需考虑结构信息，因为原查询在 ELCA 语义下获得的 ELCAs 可能与替代查询候选获得的 ELCAs 不同，可能会得到不满足替代查询定义的关键字集。 该优化算法执行两次并行扫描来生成替代查询，即截断扫描（C - scan）和验证扫描（V - scan）： - C - scan：扫描所有正子树，提取可作为替代查询候选的所有标记关键字。 - V - scan：通过倒排列表统计所有可能的替代查询候选中每个标记关键字集在正子树和负子树中出现的次数，并报告精确率和召回率超过给定阈值的标记关键字集。 具体算法如下： ```plaintext Algorithm 2. Stack algorithm for generating approximate alternative queries Input: a cluster Cl = C(R, (e1, e2, ..., en)), threshold values θp, θr 1: get roots as a keyword inverted list corresponding to R 2: Common = getCommonWordsWithParentName(Cl,θr) 3: stack = ∅, count table PCT = ∅, count table NCT = ∅, List L = ∅ 4: v = getSmallestNode(Common) 5: while ( v != null ) { 6: find the largest node r in the inverted list of root, which is smaller than v 7: if ( r ⪯ v ) ```