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

無效

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

技術領域

本發明屬數據庫技術領域，具體涉及一種高效的對XML數據進行關鍵字檢索的方法。

背景技術

隨著XML的流行，XML上的關鍵字檢索也正在成為一個研究熱點。XML上的關鍵字檢索不需要用戶對所查詢XML的DTD或schema模式、復雜的XML查詢語言(比如XQuery)等相關知識有所了解，因此更容易被用戶接受。通常在Web上的關鍵字檢索，比如google或者百度，他們的返回結果是包含用戶提供的關鍵字的整個網頁。但如果對大XML文檔上的關鍵字檢索，由于XML文檔通常被建模成樹形結構，有著層次性的嵌套關系，用戶通常希望能得到最小結果片斷，此時返回結果應是包含這些關鍵字的結點集，而且結點集中的任一結點的子孫結點都不能再包含所查詢的關鍵字。

以往的XML關鍵字檢索在求解任意兩個結點的最低公共祖先結點(LCA)的時候，都是基于Dewey編碼，所謂Dewey編碼是指每個結點的編碼以父親結點的編碼為前綴，這樣兩個結點的LCA結點就是他們最長公共前綴所指示的結點。使用這種編碼好處在于給定任意兩個結點，只需比較他們的編碼就可以求解出LCA，但同時應看到編碼隨著結點的深度在增加，一方面在求解最長公共前綴時將會比較耗時，另一方面存儲這樣的編碼對空間的耗費也是很巨大的。

發明內容

本發明的目的在于提出了在XML關鍵字檢索中應用基于RMQ(RangeMinimum?Query)的LCA求解算法，該方法在假設XML元素的個數為n的情況下，通過0(nlogn)的預處理可以達到0(1)的LCA求解時間效率，從而消去XML上關鍵字檢索時借助Dewey編碼求解共同祖先的時間系數d，同時由于僅存儲結點的歐拉序列而不是Dewey編碼，可以有效減少存儲空間的開銷。

該方法首先進行預處理，預處理的具體步驟是：

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

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

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

在預處理方法中，是在計算兩個結點的LCA結點時，先判斷兩個結點是否在同一個塊中，如果在同一個塊中，直接取出相應等價塊中兩個結點的間最小值的位置，如果不是，則分別求解在新序列上的最小值和塊內的最小值；無論哪種情況，時間復雜度都為0(1)。相比于現有的算法，本發明不僅避免了求LCA結點時逐層比較兩個結點的Dewey編碼，消去了時間系數d，而且僅存儲結點的歐拉序列而不是Dewey編碼，可以有效減少存儲空間的開銷。

采用預處理后的文檔結構，對XML進行關鍵字進行檢索，給定k個關鍵字結點集S₁，S₂，…，S_k，檢索的方法如下：

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

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

本發明的優點在于，這種檢索方法通過有效的預處理，可以消去XML上關鍵字檢索時借助Dewey編碼求解共同祖先的時間系數d，同時由于僅存儲結點的歐拉序列而不是Dewey編碼，可以有效減少存儲空間的開銷，所以在性能和空間利用上要優于現有算法。

附圖說明

圖1為LCA算法流程圖。

圖2為SLCA算法流程圖。

圖3為XML文檔樹圖。

具體實施方式

1.與本發明有關的一些概念和定義。

1，XML文檔：

在本發明中，一個XML文檔D被建模成有序的帶標記樹T(N，E)。其中樹結點集N包含文檔中的所有元素、屬性或者值。而邊集E表示元素之間的包含關系。為簡便起見，我們忽略了結點間可能的引用邊。

2，LCA結點集：