吳紹根

（廣東輕工職業(yè)技術(shù)學(xué)院，廣州 510300）

0 引言

XML即可擴展標(biāo)記語言，自1998年出現(xiàn)以來，已經(jīng)成為系統(tǒng)間進行數(shù)據(jù)交換的標(biāo)準(zhǔn)。訪問XML文檔的方式有兩種：XML文檔檢索和XML文檔過濾。XML文檔檢索是指依據(jù)一定的檢索條件對所存儲的XML文檔進行查詢，并將滿足條件的XML文檔或片段返回給檢索者，是主動式的訪問；XML文檔過濾則是指將XML文檔與所存儲的條件規(guī)則進行匹配，并將滿足條件規(guī)則的XML文檔或片段返回給條件規(guī)則的制定者，是典型的訂閱/發(fā)布式的訪問。

近年來，針對這兩種XML訪問形式的研究和應(yīng)用均有較大的發(fā)展[1-4]，特別是隨著Internet網(wǎng)上數(shù)據(jù)量的劇增，基于XML文檔過濾形式的訪問更是得到了長足發(fā)展。在XML過濾系統(tǒng)中，用戶只需制定相應(yīng)的條件向系統(tǒng)訂閱，隨著XML文檔到達過濾系統(tǒng)，即可將滿足條件的XML文檔推送/發(fā)布給相關(guān)感興趣的用戶，從而極大地提高了信息的時效性。XML文檔過濾是XML相關(guān)技術(shù)領(lǐng)域的一個研究熱點[4]。

在與XML文檔過濾相關(guān)的研究成果中，出現(xiàn)了一些較為成熟的過濾系統(tǒng)，其中基于有限自動機的過濾系統(tǒng)比較突出，同時也得到了廣泛的應(yīng)用，包括首次將有限自動機應(yīng)用于XML文檔過濾的XFilter[5]系統(tǒng)和后續(xù)的 YFilter[6]系統(tǒng)、QFilter[7]系統(tǒng)等。在基于有限自動機的XML過濾系統(tǒng)中，核心組件是過濾引擎，而過濾引擎的核心是過濾有限自動機。過濾有限自動機的效率將直接決定過濾系統(tǒng)的效率。本文將介紹一種高效構(gòu)造過濾有限自動機的方法，并給出了對過濾有限自動機進行動態(tài)在線更新的方法。

1 有限自動機和XM L過濾系統(tǒng)

在介紹過濾有限自動機的構(gòu)造算法之前，首先對有限自動機和XML過濾系統(tǒng)進行簡單的介紹。

1.1 有限自動機

有限自動機是一個五元組 M=（Q，Σ，δ，q0，F(xiàn)），其中，（1）Q 是一個有窮集合，稱為狀態(tài)集；（2）Σ是一個有窮集合，稱為字母表；（3）δ是A→Q是轉(zhuǎn)移函數(shù)，其中 A?Q×Σ，對于任何 b?A，δ（b）=q0；（4）q0∈Q是起始狀態(tài)；（5）F?Q是接受狀態(tài)集。為了直觀，在實際應(yīng)用中，經(jīng)常使用狀態(tài)遷移圖來表示特定的有限自動機。

1.2 XM L過濾系統(tǒng)

XML過濾系統(tǒng)也稱為SDI[5]系統(tǒng)，即Selective Dissemination of Information，它基于用戶的需求（User Profiles）對XML文檔進行過濾并將滿足條件的文檔或文檔片段分發(fā)到相應(yīng)的用戶，其體系結(jié)構(gòu)如圖1所示。

XML過濾系統(tǒng)有兩個輸入：XML文檔和用戶需求。其中XML文檔是來源于任何數(shù)據(jù)源的已格式化為XML格式的數(shù)據(jù)；用戶需求則是用戶所訂閱的匹配條件，存儲在XML過濾系統(tǒng)中。

圖1 XML過濾系統(tǒng)結(jié)構(gòu)

XPath表達式已經(jīng)成為查詢XML文檔的標(biāo)準(zhǔn)語言，在XML過濾系統(tǒng)中，存儲于過濾系統(tǒng)中的用戶需求是用XPath表示的。由于XPath表達式上下層路徑所固有的內(nèi)在關(guān)聯(lián)性，可以使用有限自動機進行一致的表達。例如，對于如下四個XPath表達式：

（1）Q1：/a/b

（2）Q2：/a/*/c

暴怒中的趙仙童，企圖找什么硬件毆打磚子，磚子慌了，撒腿逃出家門，心里苦苦地叫著：生活實驗又開始了，老天爺啊，我快崩潰啦！

（3）Q3：/a//c

（4）Q4：b/c

可以轉(zhuǎn)換為與之對應(yīng)的有限自動機，如圖2所示。

圖2 XPath表達式的有限自動機表示

XML過濾有限自動機的構(gòu)造就是將從XPath表示的條件創(chuàng)建與之等價的有限自動機，并實現(xiàn)對過濾有限自動機的維護。

2 過濾有限自動機的生成及維護算法

2.1 過濾自動機核心數(shù)據(jù)結(jié)構(gòu)

為了將用XPath表示的過濾需求轉(zhuǎn)換為有限自動機的形式，需要首先定義有限自動機的節(jié)點數(shù)據(jù)結(jié)構(gòu)。為此，定義如下的數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)及算法均用偽C表示）來表示過濾有限自動機的狀態(tài)節(jié)點。

struct StateNode{

unsigned int state; //節(jié)點狀態(tài)

XML的元素標(biāo)識

unsigned int shared; //當(dāng)該節(jié)點被多個訂閱需求共享時，記錄共享的次數(shù)

struct StateNode*next; //指向可以由該節(jié)點遷移到的所有的后繼節(jié)點的節(jié)點數(shù)組

unsigned int count; //該節(jié)點的后繼節(jié)點的數(shù)目

unsigned int flag; //是否為接受狀態(tài)，若是則為1，否則為0

struct User*users; //若為接受節(jié)點，則指向訂閱用戶的數(shù)組，否則為null

}

在過濾過程中，當(dāng)XML文檔滿足某個訂閱用戶的需求時，需要將該XML文檔或文檔片段分發(fā)給訂閱用戶，為了表示用戶的個體信息，定義如下的數(shù)據(jù)結(jié)構(gòu)。

2.2 生成過濾有限自動機

生成過濾自動機的基本思路如下：首先判斷過濾自動機是否存在，若不存在，則創(chuàng)建一個只有起始節(jié)點的有限自動機，然后分解XPath參數(shù)路徑中的各個元素，并從過濾自動機的起始節(jié)點開始在過濾自動機中搜索，若搜索到對應(yīng)的element，則相應(yīng)節(jié)點的shared域加1，否則，新增一個節(jié)點。算法描述如下：

StateNode* AddNewXPath （StateNode *machine，string XPath，User*user）

2.3 從過濾有限自動機中刪除一個XPath

隨著時間的推移，用戶所訂閱的需求會發(fā)生變化，為此，需要從過濾有限自動機中將部分無用的需求刪除。

分解XPath參數(shù)路徑中的各個元素，并從過濾自動機的起始節(jié)點開始，在過濾自動機中進行搜索，若搜索到對應(yīng)的element，則相應(yīng)節(jié)點的shared域減1，如果減1后該節(jié)點的shared域的值為0，則從過濾有限自動機中刪除該狀態(tài)節(jié)點及該節(jié)點的所有后繼節(jié)點。算法描述如下：

StateNode* DeleteAXPath （StateNode *machine，string XPath）

2.4 更新過濾有限自動機中的XPath

更新過濾有限自動機中的XPath，其含義是用一個新的XPath替換一個舊的XPath。更新的基本思想是：從過濾有限自動機中刪除舊的XPath，并將新的XPath添加到過濾有限自動機中。算法描述如下：

3 過濾引擎有限自動機的動態(tài)更新

XML用戶可能隨時會對過濾需求進行變更，因而需要對過濾引擎有限自動機進行動態(tài)在線更新。

參照計算機CPU的中斷工作機制可以實現(xiàn)對過濾引擎有限自動機的動態(tài)在線更新。在一個離線的系統(tǒng)中完成對過濾引擎有限自動機的更新并將自動機保存到一個介質(zhì)上，然后向正在工作的過濾系統(tǒng)發(fā)送一個更新消息（相當(dāng)于計算機CPU的中斷管腳置位），當(dāng)正在工作的過濾系統(tǒng)完成當(dāng)前任務(wù)處理后，檢測到該更新消息，從介質(zhì)上加載并更新到新的自動機上。

4 結(jié)語

本文介紹了基于有限自動機的XML過濾引擎有限自動機的構(gòu)造，詳細描述了過濾有限自動機的生成算法、XPath的刪除算法和XPath的更新算法，并借鑒CPU對中斷的處理技術(shù)，介紹了如何實現(xiàn)過濾有限自動機的動態(tài)在線更新。為了實現(xiàn)更加精細的過濾，在過濾有限自動機中實現(xiàn)XPath的謂詞功能和對XPath全集的支持是基于有限自動機的XML文檔過濾的一個重要研究方向并將繼續(xù)予以關(guān)注。

［1］周軍鋒，孟小峰．XML關(guān)鍵字查詢處理研究［J］．計算機學(xué)報，2012（12）：2459-2478．

［2］劉寶龍，劉念，陳樺．基于XPath分解XML文檔的完整性檢查［J］．西安工業(yè)大學(xué)學(xué)報，2012（8）：17-21．

［3］劉丹，陸偉，張宓．XML 結(jié)構(gòu)化檢索研究及實現(xiàn)［J］．現(xiàn)代圖書情報技術(shù)，2009（3）：52-56．

［4］覃泳睿，孫未未，張卓瑤，等．基于有限自動機的XML過濾技術(shù)研究綜述［J］．計算機科學(xué)，2008（12）：19-24．

［5］Altinel M，F(xiàn)ranklin M．Efficient filtering of XML documents for selective dissemination of information［C］．VLDB，2000．

［6］Diao Y，F(xiàn)ischer P，F(xiàn)ranklin N M．YFilter：Efficient and Scalable Filtering of XMLDocuments［C］．ICDE，2002．

［7］Luo B，Lee D G．QFilter：Finegrained runtime XML access control via NFA-based query rewriting．CIKM 2004［C］．Washington D C：Conference on Information and Knowledge Management，2004．