基于SLCA的XML關(guān)鍵字查詢技術(shù)研究.pdf

1、近年來，XM L數(shù)據(jù)已經(jīng)成為互聯(lián)網(wǎng)中數(shù)據(jù)交換事實上的標準。對 XM L數(shù)據(jù)的管理也成為了學(xué)術(shù)界研究的重點。這其中，有關(guān)于XM L數(shù)據(jù)的查詢技術(shù)的研究顯得非常重要?；赬ML數(shù)據(jù)的查詢技術(shù)，可以分為XML結(jié)構(gòu)化查詢和XM L關(guān)鍵字查詢。由于 XM L結(jié)構(gòu)化查詢需要用戶掌握一定的背景知識，越來越多的用戶更傾向于使用XML關(guān)鍵字查詢。XML數(shù)據(jù)分為普通XML數(shù)據(jù)和不確定XML數(shù)據(jù)。隨著互聯(lián)網(wǎng)數(shù)據(jù)采集和處理技術(shù)的進步，普通XML數(shù)據(jù)已經(jīng)無法滿足

2、現(xiàn)實的需要，這是因為現(xiàn)實世界中的數(shù)據(jù)很多都是不確定的，即使用概率來表示。在金融、通信、軍事等領(lǐng)域中，不確定XML數(shù)據(jù)都有著廣泛的應(yīng)用。所以，不確定XML數(shù)據(jù)的關(guān)鍵字查詢算法同樣是研究者們關(guān)注的重點。
　　XM L關(guān)鍵字查詢算法都是基于特定的語義，而本文針對最經(jīng)典的SLC A語義，并結(jié)合普通XML數(shù)據(jù)和不確定XML數(shù)據(jù)分別提出解決方案。針對普通XML數(shù)據(jù)的關(guān)鍵字查詢技術(shù)都是基于編碼后的XM L數(shù)據(jù)，而傳統(tǒng)關(guān)鍵字查詢算法所用到的編碼技

3、術(shù)都是基于前綴編碼。前綴編碼技術(shù)在計算節(jié)點的公共祖先過程中，采用諸位比較的方法，這種方法容易產(chǎn)生字符串重復(fù)比較問題，造成性能上的低效。為了解決這一問題，本文提出了一種基于區(qū)間編碼的XM L關(guān)鍵字查詢算法InSearch。該算法首先對區(qū)間編碼后的XML數(shù)據(jù)構(gòu)建區(qū)間索引結(jié)構(gòu)InIndex。然后，針對每個關(guān)鍵字列表中的節(jié)點，選取最臨近的節(jié)點進行比較計算出節(jié)點的最小范圍值，利用這個值查詢區(qū)間索引結(jié)構(gòu)，確定候選集合。最后，利用過濾規(guī)則得到最終結(jié)果

4、。在此基礎(chǔ)上，基于跳表結(jié)構(gòu)將 InSearch算法進行改進，提出S-InSearc h算法。該算法，使用跳表來保存節(jié)點的范圍值，通過避免冗余的查詢操作，進一步的加快了獲取SLCA節(jié)點的效率。
　　基于不確定XM L數(shù)據(jù)，傳統(tǒng)的關(guān)鍵字查詢算法都是基于“?！苯Y(jié)構(gòu)，需要頻繁的進棧、出棧操作，并且需要頻繁的字符串比較操作，效率較低。針對這一問題，本文提出保存節(jié)點編碼和概率值的數(shù)據(jù)結(jié)構(gòu)ProList，并基于ProList提出不確定XML關(guān)鍵

5、字查詢算法ProSearch。該算法首先初始化關(guān)鍵字對應(yīng)的ProList，然后計算所有ProList得到結(jié)果節(jié)點，并通過計算節(jié)點路徑概率和局部概率得到結(jié)果節(jié)點的概率值。
　　本文針對所提出的SLCA查詢算法設(shè)計并選取了經(jīng)典算法進行對比實驗。通過設(shè)置不同的查詢用例，將 InSearch算法與經(jīng)典算法 ILE算法進行對比，并在此基礎(chǔ)上對比S-InSearch算法。將ProSearch算法與經(jīng)典的PrStack算法進行對比。通過理論分析