XML文檔過濾引擎有限自動(dòng)機(jī)的構(gòu)造

吳紹根

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

0 引言

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

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

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

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

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

1.1 有限自動(dòng)機(jī)

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

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

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

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

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

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

（1）Q1：/a/b

（2）Q2：/a/*/c

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

（3）Q3：/a//c

（4）Q4：b/c

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

圖2 XPath表達(dá)式的有限自動(dòng)機(jī)表示

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

2 過濾有限自動(dòng)機(jī)的生成及維護(hù)算法

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

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

struct StateNode{

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

XML的元素標(biāo)識(shí)

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

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

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

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

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

}

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

2.2 生成過濾有限自動(dòng)機(jī)

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

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

2.3 從過濾有限自動(dòng)機(jī)中刪除一個(gè)XPath

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

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

StateNode* DeleteAXPath （StateNode *machine，string XPath）

2.4 更新過濾有限自動(dòng)機(jī)中的XPath

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

3 過濾引擎有限自動(dòng)機(jī)的動(dòng)態(tài)更新

XML用戶可能隨時(shí)會(huì)對(duì)過濾需求進(jìn)行變更，因而需要對(duì)過濾引擎有限自動(dòng)機(jī)進(jìn)行動(dòng)態(tài)在線更新。

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

4 結(jié)語(yǔ)

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

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

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

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

［4］覃泳睿，孫未未，張卓瑤，等．基于有限自動(dòng)機(jī)的XML過濾技術(shù)研究綜述［J］．計(jì)算機(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．