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

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

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

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

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

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

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

1相關(guān)技術(shù)

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

2索引結(jié)構(gòu)

2．1XML摘要樹構(gòu)造

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

2．2雙重索引結(jié)構(gòu)模型

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

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

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

因此基于上述分析，根據(jù)路徑和內(nèi)容關(guān)系分離，可以得到結(jié)構(gòu)索引和倒排索引的XML摘要樹雙重索引結(jié)構(gòu)模型，如圖3所示。

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

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

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

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

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

3結(jié)束語

本文提出的算法，采用NASA公開的XML檔案文件[7] 數(shù)據(jù)集進行實驗。結(jié)果表明，實驗數(shù)據(jù)集由857個XML文件組成，約11 MB。在配置Pentium4 2.4 GHz迅馳CPU，256 MB內(nèi)存，裝有Windows 2000 Server操作系統(tǒng)的PC上運行一個小型的搜索引擎系統(tǒng)。其中采用本文給出的索引策略，用Java編程實現(xiàn)，不到2 min就完成了索引的構(gòu)建，并占用了3.8 MB的存儲空間。對查詢表達式的檢索結(jié)果符合條件，對它進行了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.

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