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

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

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

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