基于有序小枝模式的XML文檔過(guò)濾模型的研究.pdf

1、面對(duì)互聯(lián)網(wǎng)上海量的信息，個(gè)性化的定制服務(wù)逐漸成為人們獲取信息的一個(gè)重要手段。其核心技術(shù)是如何對(duì)大量的用XML格式表示的數(shù)據(jù)進(jìn)行快速而有效地處理。針對(duì)XML數(shù)據(jù)流，普遍采用的是XPath表達(dá)式進(jìn)行查詢(xún)。因此，如何在XML數(shù)據(jù)流上對(duì)大量的XPath表示的查詢(xún)進(jìn)行快速處理是XML文檔過(guò)濾的核心問(wèn)題。
　　 對(duì)于基于小枝模式的XML文檔過(guò)濾的研究，目前主要分為兩個(gè)方向。一個(gè)是采用分解的思想，核心是如何高效地對(duì)節(jié)點(diǎn)間位置關(guān)系進(jìn)行匹配。該類(lèi)

2、算法有一個(gè)通病，即在某些情況下需要多次重復(fù)掃描后代節(jié)點(diǎn)列表，這導(dǎo)致大量中間結(jié)果產(chǎn)生，嚴(yán)重影響了算法執(zhí)行效率。并且，對(duì)于含較多相對(duì)路徑表達(dá)式以及含通配符的表達(dá)式查詢(xún)支持有限。另一個(gè)方向是采用整體匹配的思想，即在匹配過(guò)程中，將路徑表達(dá)式中節(jié)點(diǎn)間的位置信息考慮在內(nèi)，作為一個(gè)整體進(jìn)行一次匹配。其主流做法是將XML文檔和查詢(xún)樹(shù)均以某種編碼進(jìn)行轉(zhuǎn)化，使之成為字符串，然后按照某種遍歷策略對(duì)字符串進(jìn)行匹配驗(yàn)證。該思想流行算法很多，但大都不支持邏輯謂詞處

3、理。
　　 本文在對(duì)當(dāng)前主流XML文檔過(guò)濾模型進(jìn)行分析的基礎(chǔ)上提出一種新型過(guò)濾模型——FST(Filtering by Sequencing Twigs)。該模型采用整體匹配的思想，將XML文檔樹(shù)的結(jié)構(gòu)信息存儲(chǔ)在一種新型數(shù)據(jù)結(jié)構(gòu)中，采用普呂弗序列生成算法將XML文檔及小枝模式查詢(xún)語(yǔ)句轉(zhuǎn)化為字符串，于是XML文檔過(guò)濾問(wèn)題被成功的轉(zhuǎn)化為普呂弗序列的匹配問(wèn)題。匹配過(guò)程中利用一個(gè)全局運(yùn)行棧的數(shù)據(jù)結(jié)構(gòu)，保證了匹配的有序性，同時(shí)，利用全局運(yùn)