基于哈希表和流索引的XML過濾模型的研究.pdf

1、XML(eXtensibleMarkupLanguage,可擴(kuò)展標(biāo)記語言)白1998年出現(xiàn)以來,已經(jīng)成為互聯(lián)網(wǎng)數(shù)據(jù)交換格式的標(biāo)準(zhǔn)。大量與之相關(guān)的應(yīng)用,如消息通知系統(tǒng)、個人個性化信息等都需要對信息進(jìn)行過濾。如何對XML的數(shù)據(jù)進(jìn)行高效的過濾,已經(jīng)成為近年來XML的熱點研究問題之一。
　　 近些年,人們在對XML過濾的研究中,已經(jīng)取得了一系列成果。其中,許多理論模型和工具,都已經(jīng)很成熟。例如,XPath、白動機(jī)等有關(guān)理論已經(jīng)形成了各種

2、各樣的應(yīng)用機(jī)制。以XFilter的出現(xiàn)為代表,YFilter、lazyDFA等一系列與自動機(jī)有關(guān)的理論,被廣泛應(yīng)用到XML的過濾中,而各種自動機(jī)的有關(guān)模型也不斷的被研究出來,這也是當(dāng)前XML過濾應(yīng)用所廣泛使用的技術(shù)。
　　 在XML的過濾中,要考慮的是如何減少過濾時的開銷,提高過濾的效率,從而追求效益的最大化,這其中,如何減少無效元素的處理,減少文檔的解析量,便成為一個重要途徑,本文相關(guān)的研究工作也由此而展開。減少無效元素的處理

3、,包括兩個方面,一是如何快速斷定某些元素是無效元素,二是如何對這些無效元素進(jìn)行處理。本文通過引入哈希表,來對無效元素進(jìn)行判斷,通過引入流索引,來對無效元素進(jìn)行跳過,從而提高過濾的效率。
　　 哈希表存儲了元素的位置信息,可以快速判斷文檔中任意兩個元素的層次關(guān)系,以便判斷元素是否為無效元素。過濾時,祖先后代關(guān)系“∥”的處理往往需要消耗大量時間,因為如果有元素可以匹配該關(guān)系,那么無論該元素在文檔的何種深度,都滿足過濾條件,而對該元素

4、判斷的過程中,需要大量的壓入堆棧操作,所耗用的時間和空間太大。在本文中,通過引入哈希表,在遇到祖先后代關(guān)系“∥”,可以不必先將其壓入堆棧,而是通過查找哈希表,看需要過濾的元素是否滿足過濾條件,如果是,壓入堆棧進(jìn)行操作,如果否,則結(jié)合流索引進(jìn)行跳過。
　　 流索引標(biāo)記了元素的開始位置和結(jié)束位置,當(dāng)遇到無效元素時,可以通過結(jié)束標(biāo)記,對無效元素及其了孫元素進(jìn)行直接跳過,從而避免無效元素的處理,從而提高解析效率。實驗表明,當(dāng)輸入的文檔深