[發明專利]XML關鍵字檢索的最低公共祖先快速查找方法

無效

• 申請號: 200810200674.0
• 申請日: 2008-09-27
• 公開（公告）號: CN101364234A
• 公開（公告）日: 2009-02-11
• 發明（設計）人: 周傲英;謝濤;王曉玲
• 申請（專利權）人: 復旦大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 上海東亞專利商標代理有限公司
• 代理人: 羅習群

1、一種XML關鍵字檢索的最低公共祖先快速查找方法，其特征是，該方法首先進行預處理，預處理的具體步驟是：

步驟1，在解析XML文檔的過程中，構建歐拉序列E和深度序列L，記錄XML文檔中每個結點的開始位置，結束位置和深度信息，對XML文檔進行序列化，并在處理文本信息的時候，建立倒排表記錄每個單詞；

步驟2，將深度序列L按長度logn/2劃分成2n/logn個塊，在每個塊上選取最小值組成一個長度為2n/logn的新序列，利用新序列建立SparseTable；

步驟3，枚舉每個等價塊，計算并存儲塊內任意序號間最小值的位置。

2、根據權利要求1所述的XML關鍵字檢索的最低公共祖先快速查找方法，在預處理方法中，是在計算兩個結點的LCA結點時，先判斷兩個結點是否在同一個塊中，如果在同一個塊中，直接取出相應等價塊中兩個結點的間最小值的位置，如果不是，則分別求解在新序列上的最小值和塊內的最小值。

3、根據權利要求1或2所述的XML關鍵字檢索的最低公共祖先快速查找方法，其特征在于，采用預處理后的文檔結構，對XML進行關鍵字進行檢索，給定k個關鍵字結點集S₁，S₂，…，S_k，檢索的方法如下：

步驟1，求出結點集最小的關鍵字集合，假設為S₁，作為SLCA結點的候選結點集；

步驟2，對候選結點集進行k-1次迭代，每次迭代對候選結點集和另一個關鍵字結點集進行SLCA結點的計算，并將結果集作為下一次迭代的候選集；

步驟3，在經過k-1次迭代后，得到k個集合的SLCA結點集，其中SLCA結點計算得出候選slca結點，然后刪除所有非SLCA結點。