一種支持高效檢索的雙重索引策略

摘要：從信息檢索角度出發，提出一種高效的索引，在結構索引中集成了倒排文檔，可同時查詢XML結構部分和關鍵詞。雙重索引策略很好地解決了基于路徑表達式查詢效率低的問題。

關鍵詞：可擴展標記語言； 路徑表達式； 雙重索引； 倒排文檔

中圖分類號：TP311文獻標志碼：A

文章編號：1001-3695(2007)11-0063-02

在當今的萬維網中，XML語言形式無處不在。XML是Web上進行信息表示與交換的一個層次數據格式[1]。隨著大量XML數據的出現，如何有效地索引、存儲和查詢這些XML數據就成為目前值得研究的一個重要課題。

因為XML是一種半結構化的數據形式，傳統的數據庫存儲方法和基于文本數據的信息檢索方法都無法有效地對它進行操作。文獻[2]提出，當前處理半結構化數據的索引技術主要有值索引、字符串索引、路徑索引、節點索引。其中路徑索引和節點索引對查詢條件的結構部分是高效的，而值索引和字符串索引則是傾向于信息檢索的方法，很容易實現對XML文本的檢索，但是對于基于路徑表達式的查詢效率很低。本文提出的索引技術可對包含路徑和關鍵詞的查詢表達式實現高效檢索，并給出了高效的更新算法。

1相關技術

一個XML文檔可以看做是一個有序的、邊標記的樹。在XML樹模型中一般有四種節點類型，即文檔節點、元素節點、屬性節點和文本節點。文檔節點一般指向文檔樹的根節點，在一個文檔樹中有且只有一個。元素節點指向其他的屬性節點或文本節點。

2索引結構

2．1XML摘要樹構造

構造文檔索引結構時首先要確定索引XML文檔中需要的詞條；然后掃描整個解析后的文檔，識別并抽取每一個元素和元素中的詞條，并針對抽取出的每個詞條和元素標志，取共有詞(stopWords)，并抽取詞根(stemmer) [3，4]。在掃描過程中，要按照共有詞條表檢查每個詞條。如果一個詞條不在共有詞條表中，則通過抽取詞根算法加在共有詞條表中。最后就是統計文檔中所有文本內容和標記出現情況。此過程會消除所有重復的路徑和詞條，并得到惟一的XML摘要樹。如圖1所示，XML摘要樹保留了原始的XML文檔結構，并比原始XML文檔占用的存儲空間要小。例如：圖2（a）是一個XML文檔；（b）是相應的XML摘要樹。在摘要樹中相同路徑只出現一次，所有的文本內容和標記都用詞根代替。

2．2雙重索引結構模型

在XML摘要樹中簡化了XML文檔的重復路徑，并減少了存儲空間。但是由于同時混合著XML的結構和內容信息，對它進行查詢的效率太低。當前XML文檔索引技術主要分為倒排索引和路徑索引。路徑索引對路徑表達式的查詢是高效的，但是它對于文檔中的屬性值或關鍵詞的搜索幾乎沒有效率。倒排索引文檔內容的檢索很高效，但它用在路徑表達式時需要連接很多大型倒排文件，其I/O代價和連接的系統開銷均很大。

本文提出利用摘要樹的特點，結合上述兩種索引技術實現對路徑和文本內容更好的檢索。由上述可知，摘要樹中消除了重復路徑，可以利用摘要樹構造結構索引。結構索引是路徑索引的一個分支，其主要思想就是用最少的節點和邊表示文檔樹中所有的路徑信息，把摘要樹中所有的等價節點用一個節點表示。在此定義一個函數F(n)用于記錄節點n在摘要樹中的等價節點。如果從F(a)中的某節點到F(b)的某節點有一條邊，則在索引節點a與索引節點b之間加一條邊。結構索引中的每個節點a均有一個惟一標志符id(a)。

在XML文檔系統庫中，倒排表是在標記名和關鍵詞上構造的，它可以有效支持XML文檔中關鍵詞的搜索。對文檔樹中的每個文本詞條，在倒排表中可以用四元組形式表示：〈docid，start，level，indexid〉。倒排索引是一系列倒排表的集合。docid表示文檔的惟一標志符；start表示詞條在文檔出現的位置；level表示在文檔樹中節點的深度；indexid表示惟一索引id號。

因此基于上述分析，根據路徑和內容關系分離，可以得到結構索引和倒排索引的XML摘要樹雙重索引結構模型，如圖3所示。

在圖3中，倒排表中存儲的是內容數據，結構索引中記錄的則是文檔的所有單路徑信息。其中得到的結構索引中每個節點的惟一標志符id(a)和倒排表中的a.indexid域是等價的。

2．3雙重索引更新算法

當前Web上文檔經常發生變化。在1998年crawler基本上要用一個月才能完成一次網絡的搜索[5]，而現在使用Google可以檢索到三天前在Web上發布的信息。對于每天發展變化的網絡來說，為使用戶及時得到網絡上的更新信息，快速更新索引的內容是一件十分迫切的工作。

以前在倒排索引上，增量更新的工作大多是基于在靜態文檔中增加一個新的文檔[6]。通常是當一個文檔內容發生變化時，先將文檔刪除，再插入新的文檔。當文檔內容頻繁地增加、刪除和更新時，這些過程會消耗大量的存儲空間和時間。

本文提出，XML文檔的插入和刪除即轉換為XML摘要樹的插入和刪除，會使索引結構減小或增加。在XML文檔庫中增加一個文檔時，該文檔相應的摘要樹就會插入到索引結構中；同樣，減少一個文檔也會刪除它所對應的摘要樹。XML文檔的更新是通過一系列的插入、刪除操作完成的。算法1給出了在索引結構中插入一個新的摘要樹的過程。其結構部分存儲在結構索引中，節點的內容存儲在倒排文檔中。

3結束語

本文提出的算法，采用NASA公開的XML檔案文件[7] 數據集進行實驗。結果表明，實驗數據集由857個XML文件組成，約11 MB。在配置Pentium4 2.4 GHz迅馳CPU，256 MB內存，裝有Windows 2000 Server操作系統的PC上運行一個小型的搜索引擎系統。其中采用本文給出的索引策略，用Java編程實現，不到2 min就完成了索引的構建，并占用了3.8 MB的存儲空間。對查詢表達式的檢索結果符合條件，對它進行了50次的查詢，平均檢索時間為0.13 s。由此可見，本文所提出的一種支持高效檢索的雙重索引策略具有較高的理論和實用價值。

參考文獻：

［1］World Wide Web Consortium. Xquery 1.0 and Xpath 2.0 data model[EB/OL]. (2004-07-23).http://www3.org/TR/xpath datamo￣del/.

［2］WANG Xiao－ling，WEN Ji－rong， LIU Wen－yin. Enhancive index for structured document retrieval[C]//Proc of the 12th International Workshop on Research Issues on Data Engineering.2002.

［3］MIKHEEV A. Document centered approach to text normalization[C]//Proc of the Annual ACM Conference on Research and Development in Information Retrieval.2000:136－143.

［4］PORTER M. Porter stemming algorithm[EB/OL]. (2003).http://www.tartarus，org/~martin.

［5］LIM L， WANG Min， PADMANABHAN S. Dynamic maintenance of Web index using landmarks[R]. Budapest， Hungary: ACM， 2003.

［6］BROWN E W， CALLAN J P， CROFT W B.Fast incremental indexing for full－text information retrieval[C]//Proc of the 20th Intl Conf on Very Large Data Bases. 1994:192-202.

［7］XML astronomy archive at NASA[EB/OL]. (2002).http://xml.gsfc.nasa.gov/archive.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”