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

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

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

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

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