基于最緊致片段XML關(guān)鍵字檢索研究.pdf

1、XML(Extensible Markup Language)是被W3C基于標(biāo)準(zhǔn)的廣義標(biāo)記語(yǔ)言所創(chuàng)建，被用作定義語(yǔ)義標(biāo)記。在Web服務(wù)、電子商務(wù)、數(shù)字圖書館等諸多網(wǎng)絡(luò)相關(guān)應(yīng)用領(lǐng)域已經(jīng)成為描述數(shù)據(jù)的事實(shí)上的標(biāo)準(zhǔn)。為了方便用戶從海量的XML數(shù)據(jù)中提取他們所需要的信息，許多XML數(shù)據(jù)查詢算法應(yīng)運(yùn)而生，使得XML數(shù)據(jù)查詢成為XML數(shù)據(jù)管理領(lǐng)域的一個(gè)熱點(diǎn)。
　　 通常，XML數(shù)據(jù)查詢算法按照查詢模式描述的不同分為兩類，即XML結(jié)構(gòu)查詢和X

2、ML關(guān)鍵字查詢。前者多采用了正則表達(dá)式的描述方法，偏向于傳統(tǒng)的結(jié)構(gòu)化的查詢方式，能夠清楚的表述用戶的查詢意圖；后者融入了信息檢索領(lǐng)域常用的查詢思想和方法，允許用戶僅僅輸入關(guān)鍵字就能夠進(jìn)行查詢。
　　 XML結(jié)構(gòu)查詢算法根據(jù)精確的查詢條件，能夠輸出理想的查詢結(jié)果。然而，該算法對(duì)進(jìn)行查詢的用戶也提出了更高的要求，即不僅要熟悉結(jié)構(gòu)查詢算法所采用的查詢語(yǔ)言，而且還要了解待查詢的XML文檔樹結(jié)構(gòu)。以上要求對(duì)于絕大多數(shù)用戶而言是不切實(shí)際的，

3、而XML關(guān)鍵字查詢很好的解決了以上的問題，所以從用戶的角度出發(fā)，XML關(guān)鍵字查詢是一種能夠被廣泛使用的查詢方法。
　　 XML關(guān)鍵字查詢方式中最關(guān)鍵的問題是如何求解包含所有關(guān)鍵字的最緊致片段，即SLCA(Smallest Lowest Common Ancestors)問題。目前已有許多求解算法，包括Stack、ILE、SE、LISA和LISAⅡ等。ILE和SE在與Stack的實(shí)驗(yàn)對(duì)比中表現(xiàn)得效率更高，適合需要頻繁I/O操作的海

4、量XML查詢，他們僅需要順序讀取XML數(shù)據(jù)一遍；相比ILE和SE，LISA和LISAⅡ在輕量級(jí)XML查詢中，無(wú)論是在理論分析上還是試驗(yàn)對(duì)比中都表現(xiàn)出了更好的性能。
　　 然而，LISA不僅需要頻繁掃描節(jié)點(diǎn)，而且需要引入集合交操作，耗費(fèi)了大量CPU周期。LISAⅡ雖然在避免不必要掃描方面改進(jìn)了LISA算法，但卻使用了自己獨(dú)有的編碼，不僅引入了編碼映射，而且也使得該算法的通用性大大削弱。這兩種算法即便作為一種僅在內(nèi)存中執(zhí)行的算法，以

5、上缺點(diǎn)也影響了查詢速度。
　　 本文圍繞SLCA展開，本文在已有經(jīng)典算法基礎(chǔ)上對(duì)已有算法做出了改進(jìn)，本文的主要貢獻(xiàn)為：
　　 1、分析SLCA現(xiàn)有成熟的求解算法上的缺點(diǎn)并提出新的改進(jìn)算法，針對(duì)LISAⅡ算法使用前序編碼的擴(kuò)展Dewey碼，該編碼具有許多冗余信息，浪費(fèi)了存儲(chǔ)空間的缺點(diǎn)。本文提出了一種新的基于層次編碼的SLCA求解算法UBS，該算法的空間復(fù)雜度明顯降低，在理論求解時(shí)間和LISAII基本相同的情況下，使用了更少