基于SLCA的XML關(guān)鍵字查詢研究與改進.pdf

1、XML（Extensible Markup Language）即可擴展的標(biāo)記語言，是一套定義語義標(biāo)記的規(guī)范，其目的在于定義計算機和人都能方便識別的數(shù)據(jù)類型。隨著網(wǎng)絡(luò)應(yīng)用的快速發(fā)展，XML已經(jīng)被廣泛應(yīng)用到Internet智能信息檢索、數(shù)字圖書館、數(shù)據(jù)集成、Web Service等領(lǐng)域，這使得XML類型的數(shù)據(jù)已成為主流的數(shù)據(jù)形式，從XML數(shù)據(jù)中提取有用的信息也就成為了當(dāng)前的研究熱點。 目前，XML查詢根據(jù)查詢請求描述特點的不同，可概

2、括為兩大類查詢模式：XML結(jié)構(gòu)化查詢和XML關(guān)鍵字查詢。XML結(jié)構(gòu)化查詢要求用戶必須掌握XML文檔結(jié)構(gòu)及查詢語言，這對用戶來說有著較大的難度，不易使用。而XML關(guān)鍵字查詢則相對比較靈活，它只需要用戶提供簡單的關(guān)鍵字信息，而無需懂得任何查詢語言或文檔結(jié)構(gòu)就可方便使用，因此該模式被廣泛采用，有著重要的研究價值。 XML關(guān)鍵字查詢的基本問題是求解滿足關(guān)鍵字組合語義的最緊致片段，求解最緊致片段算法的性能及對最緊致片段的定義決定了XML

3、關(guān)鍵字查詢的性能和準(zhǔn)確率。 目前，對最緊致片段的最好定義是SLCA，對SLCA求解算法的研究也較為成熟。因此，本文圍繞SLCA展開，分析SLCA求解算法性能上的缺點并提出新的改進算法，之后通過實驗進行驗證。實驗過程中發(fā)現(xiàn)，盡管算法性能有較大提高，但結(jié)果集中存在較多并非期望的節(jié)點，因此，本文又對SLCA的概念進行擴展，提出同源SLCA（Heterogeneous SLCA，HSLCA）的概念，HSLCA在SLCA的基礎(chǔ)上引入標(biāo)簽信

4、息，能夠顯著提高XML關(guān)鍵字查詢的準(zhǔn)確率。 在改進SLCA求解算法性能方面，本文在分析已有經(jīng)典算法基礎(chǔ)上展開，做出了以下創(chuàng)新： 一、提出基于并查集的SLCA求解算法USSSA。針對求解SLCA性能最優(yōu)的LISAⅡ算法空間復(fù)雜度較大，占用存儲空間較多的缺點，USSSA算法使用層次編碼進行求解，算法的空間復(fù)雜度明顯降低，在理論求解時間與LISAⅡ基本相同的情況下，使用了更少的存儲空間。 二、提出基于疊加樹思想的SLC

5、A求解算法IREE_Set。針對LISAⅡ算法在查詢關(guān)鍵字較少時性能較差的缺點，TREE_Set以樹的方式求解SLCA，當(dāng)查 詢關(guān)鍵字較少時，TREE_Set比LISAⅡ具有更好的性能。同時，這種算法具有很強的直觀意義，便于理解，易于實現(xiàn)。 在提高XML關(guān)鍵字查詢準(zhǔn)確率方面，本文在分析SLCA概念本身不足的基礎(chǔ)上展開，所做工作和改進有： 一、對SLCA的概念進行改進，提出新的最緊致片段定義同源SLCA（HSLCA