基于最緊致片段XML關鍵字檢索研究.pdf

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

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

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

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

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