??? XFilter首次利用基于有限狀態(tài)自動(dòng)機(jī)FSM(Finite State Machine)的方法來(lái)過(guò)濾XML文檔，它對(duì)每一個(gè)路徑查詢(xún)使用一個(gè)單獨(dú)的FSM，并在文檔處理的過(guò)程中，同時(shí)運(yùn)行所有的FSM。YFilter在XFilter的基礎(chǔ)上進(jìn)行了改進(jìn)，它將所有的XPath查詢(xún)合并成一個(gè)單獨(dú)的非確定有限自動(dòng)機(jī)NFA(Non-deterministic Finite Automaton)[6]，并共享所有查詢(xún)的公共前綴，YFilter主要考慮了謂詞中的AND謂詞查詢(xún)，采用后置處理的方式，這種方式產(chǎn)生大量中間結(jié)果影響系統(tǒng)性能。
　　XEBT(XPath Evaluation Based on Tree automata)[7]利用樹(shù)自動(dòng)機(jī)技術(shù)作為查詢(xún)處理器，它基于表達(dá)能力豐富的樹(shù)自動(dòng)機(jī)，無(wú)須附加中間狀態(tài)或保存中間結(jié)果，就能處理支持{[]}操作符的XPath，所以能較高效地處理XPath查詢(xún)。在優(yōu)化策略上，主要包括基于DTD的XPath查詢(xún)自動(dòng)機(jī)的構(gòu)造、在空間代價(jià)有限增加的情況下采用局部確定化減少并發(fā)執(zhí)行的狀態(tài)、采用自上而下和自下而上相結(jié)合的查詢(xún)處理策略等。
　　其他處理XML流的方法主要有基于索引（Index-Filter）的方法[2]、基于Bloom Filter[3]的方法以及FiST[5]方法。Index-Filter[2]采用基于索引的技術(shù)處理XML流數(shù)據(jù)，利用XML文檔流的文檔標(biāo)記動(dòng)態(tài)地建立XML文檔的索引，從而避免處理一部分文檔。在Index-Filter的方法中，建立索引要花費(fèi)一定的時(shí)間，而且不能單遍處理XML文檔?；贐loom Filter的XML包過(guò)濾器具一種近似查詢(xún)方法，利用Bloom Filter方法，將XPath表達(dá)式作為字符串，將XPath與XML包之間的匹配轉(zhuǎn)換為字符串之間的匹配，從而提高查詢(xún)性能，但它只是用來(lái)處理簡(jiǎn)單的XPath表達(dá)式且有一定的失誤率。FiST方法針對(duì)Twig Pattern提出的一種有別于YFilter的方法，將一組Twig Pattern轉(zhuǎn)換為prufer序列，并對(duì)一組Twig Pattern與XML流數(shù)據(jù)進(jìn)行整體性匹配。
2 GBRender模型
2.1 GBRender相關(guān)定義
　　當(dāng)XML以流的形式進(jìn)行處理時(shí)，在邏輯上實(shí)際是以先序遍歷的形式對(duì)XML樹(shù)中的結(jié)點(diǎn)進(jìn)行訪問(wèn)，通常采用基于事件的SAX模型來(lái)進(jìn)行解析。這樣，在對(duì)XML結(jié)構(gòu)未知的情況下，可以根據(jù)接收的元素信息來(lái)分析其結(jié)構(gòu)，并根據(jù)得到的結(jié)構(gòu)信息為后續(xù)服務(wù)。
??? 為了用來(lái)更好地描述GBRender查詢(xún)模型，下面介紹幾個(gè)定義：
??? 定義1(組)：XML的任何一個(gè)元素都有一個(gè)從根開(kāi)始的標(biāo)簽路徑，但很多元素都會(huì)有相同標(biāo)簽路徑，即1個(gè)標(biāo)簽路徑可以表示1組對(duì)應(yīng)的元素。這里把XML文檔中每一個(gè)不同的標(biāo)簽路徑稱(chēng)為組。如圖2所示，root/person/name即為一個(gè)組。

??? 定義2(組樹(shù))：組樹(shù)是在處理XML數(shù)據(jù)流過(guò)程中，記錄組、組之間關(guān)系的樹(shù)形結(jié)構(gòu)。其組織結(jié)構(gòu)如圖3所示。組樹(shù)中，各組有指向其子組的鏈接，每個(gè)組有指向父組的鏈接，同時(shí)，同一層的組串接起來(lái)以便于處理時(shí)的需要。
　　定義3(終結(jié)元素)：XPath表達(dá)式對(duì)應(yīng)的最后一個(gè)路徑元素，稱(chēng)為終結(jié)元素，它表示XPath請(qǐng)求所需的結(jié)果。如//A/B//C，C即終結(jié)元素。
　　定義4(著色)：尋找每一個(gè)組的標(biāo)簽路徑處于XPath表達(dá)式中的哪個(gè)位置，即當(dāng)前XML元素的路徑與XPath路徑的關(guān)系并標(biāo)記該組，這個(gè)過(guò)程稱(chēng)為著色過(guò)程。例如，組root/person/name對(duì)應(yīng)XPath表達(dá)式//name的終結(jié)元素name，則可以標(biāo)記該組為該XPath的終結(jié)組。
2.2 GBRender結(jié)構(gòu)模型
　　目前的XML數(shù)據(jù)流XPath查詢(xún)處理，基本結(jié)構(gòu)模型如圖4所示，以XML數(shù)據(jù)流作為XPath分析器的輸入，分析器可能有多個(gè)，也可能合并為1個(gè)。對(duì)XPath查詢(xún)包含的索引信息有2種：一是傳輸之前的索引信息；二是接收端進(jìn)行處理形成的索引信息。

　　GBRender查詢(xún)模型如圖5所示，采用基于著色的方式來(lái)處理查詢(xún)，當(dāng)某個(gè)組首次出現(xiàn)時(shí)，通過(guò)著色器對(duì)其與XPath的關(guān)系進(jìn)行著色。著色之后，再次遇到該組時(shí)不再依賴(lài)于XPath而只依賴(lài)其記錄的組著色信息，尤其在單枝查詢(xún)的情況下，可以直接對(duì)查詢(xún)進(jìn)行回應(yīng)。在GBRender模型中，組著色的過(guò)程，實(shí)際上相當(dāng)于XPath確定化的過(guò)程。例如，對(duì)于圖2的文檔進(jìn)行//name查詢(xún)，當(dāng)首次出現(xiàn)name時(shí)，其組標(biāo)簽路徑為root/person/name，即是對(duì)//祖孫關(guān)系在此文檔上進(jìn)行的確認(rèn)化，而且當(dāng)name出現(xiàn)在另一組時(shí)，會(huì)再一次進(jìn)行確認(rèn)化且不會(huì)相互影響。而常采用的DTD優(yōu)化策略通常也是完成確認(rèn)化的工作，當(dāng)遇到2個(gè)不同組均存在name標(biāo)簽時(shí)，//就需要特殊處理了。

??? 為了同時(shí)響應(yīng)多個(gè)XPath查詢(xún)，本文引入了著色序列的定義。
　　定義5(著色序列)：根據(jù)XPath請(qǐng)求序列，對(duì)同一組生成對(duì)應(yīng)的著色信息序列，此序列即稱(chēng)為著色序列。因?yàn)椴煌腦Path有不同的著色信息，因此也稱(chēng)XPath著色序列。
??? 每組均有著色序列，其組樹(shù)中組的結(jié)構(gòu)如圖6所示。

2.3 GBRender處理模型
??? 基于組樹(shù)的動(dòng)態(tài)建立與組著色機(jī)制，GBRender的任意組，僅當(dāng)首次出現(xiàn)時(shí)進(jìn)行XPath著色處理，之后則根據(jù)著色情況進(jìn)行處理。
　　GBRender的查詢(xún)處理，其數(shù)據(jù)輸入是XML的SAX解析事件流，包括startDocument、endDocument、startElement、endElement和Text事件，這里只給出GBRender處理模型在每一類(lèi)事件的響應(yīng)動(dòng)作，而不討論數(shù)據(jù)緩存處理。
　　startDocument： initiate the GroupTree GT and context?? //初始化組樹(shù)GT
　　StartElement(element)?? 　　　　　// element為新接收元素
　　If(not existsGroup(element))InsertGroupAndDrawXpathColor(element)；??

　　　　　　　　　　　　　　?? 　　　//如果不存在該組，則生成該組并進(jìn)行著色產(chǎn)生著色序列
　　setCurrentElement(element)；　　 //置element為當(dāng)前元素
??? Text (value)??? 　　　　　　　　　// 當(dāng)前元素的值
?????? Add value into currentElement.currentValue；
　　　　　　　　　　　　　　　　　　　?// 增加到當(dāng)前元素值
　　? EndElement(element)??
?????? ProcessXPathColor(element)；?? // 根據(jù)當(dāng)前元素的著色序列信息進(jìn)行處理
?????? setCurrentElement(element.parentGroup)； //
??? EndDocument?
?????? cleanUp( )；???? 　　　　　　　// 處理全部結(jié)束，清理
2.4 GBRender查詢(xún)模型的主要特征
　　? GBRender查詢(xún)模型處理的操作方向與目前主要的查詢(xún)處理不同，分析器并不是與XPath綁定，而是綁定到XML文檔結(jié)構(gòu)上，它對(duì)XPath只在組首次出現(xiàn)時(shí)進(jìn)行著色的處理，之后則根據(jù)著色情況來(lái)進(jìn)行處理。這種模型具有較強(qiáng)的靈活性，主要特點(diǎn)如下：
??? (1)對(duì)XML文檔結(jié)構(gòu)無(wú)需任何考慮。因?yàn)橐越邮盏牧鲾?shù)據(jù)為依據(jù)來(lái)動(dòng)態(tài)建立組樹(shù)。根據(jù)XML流數(shù)據(jù)的順序性與元素之間關(guān)系的局部性，組樹(shù)的訪問(wèn)總是發(fā)生在相鄰元素之間，因此效率很高。
??? (2)無(wú)需依賴(lài)XPath分析器。一旦著色，相當(dāng)于就對(duì)該組進(jìn)行了確定化。同時(shí)，對(duì)于簡(jiǎn)單的XPath表達(dá)式在當(dāng)前組即可直接判定作出處理。
??? (3)可以方便地利用現(xiàn)有的其他XPath查詢(xún)處理機(jī)制，如自動(dòng)機(jī)模型。因?yàn)樵谀撤N程度上，著色類(lèi)似確定化XPath，當(dāng)處理復(fù)雜謂詞時(shí)，其著色信息處理可以方便地吸收自動(dòng)機(jī)模型的思想。
??? (4)非常容易擴(kuò)展XPath查詢(xún)數(shù)目，著色序列長(zhǎng)度的增加對(duì)效率影響很小。
??? (5)方便進(jìn)行類(lèi)似關(guān)鍵詞查詢(xún)的流數(shù)據(jù)處理。如不考慮數(shù)據(jù)來(lái)源的結(jié)構(gòu)，用戶(hù)只關(guān)心信息中的author或name的信息。本文模型可以很容易且高效的去完成處理，僅需傳入//author、//name的XPath表達(dá)式串，就可以應(yīng)用于任意的XML流數(shù)據(jù)源。
3 GBRender的主要算法
　　以單枝查詢(xún)?yōu)槔?jiǎn)要介紹GBRender查詢(xún)模型中的著色算法與處理算法。
　　在單一分枝的查詢(xún)中，由于XPath表達(dá)式中僅有//與/關(guān)系，組標(biāo)簽對(duì)于XPath路徑中的元素只存在3種關(guān)系，即無(wú)、中間元素或終結(jié)元素，而本文關(guān)心的正是那些終結(jié)元素且此處暫不需考慮緩存，為了便于描述，用Color.Empty、Color.Mid以及Color.End來(lái)表示2種著色狀態(tài)。
??? (1)單一分枝下的組著色算法：
??? GroupRendering(G， XPaths)
??? 輸入：組G是當(dāng)前元素所在組，表達(dá)式串XPaths是XPath表達(dá)式集合
??? {
??? 　　Foreach(xpath in XPaths)
??? 　　{
??? 　　? If(G.tagPath not satisfy part xpath)?? //未發(fā)現(xiàn)匹配，e.tagPath為標(biāo)簽路徑
??? 　　　　　? G.XPathColorList.add(Color.Empty)；
　　??? 　 If(G.tagPath satisfy part xpath)?? 　　//有匹配
　　　??????? If(G.tagPath is 終結(jié)元素)?? 　　　　//是終結(jié)元素
???????????? G.XPathColorList.add(Color.End)；
????????? else???? 　　　　　　　　　　　　　　　　//不是終結(jié)匹配但匹配中間元素
????????????? G.XPathColorList.add(Color.Mid)；
??? 　　}
??? }
??? (2)endElement時(shí)根據(jù)組著色情況對(duì)元素進(jìn)行處理的算法：
??? ProcessXPathColor (G)
??? 輸入：組G是當(dāng)前元素所在組
??? {
???? 　　Foreach(color in G.XPathColorList)
???? 　　{? //單枝查詢(xún)情況下只需要對(duì)Color.End元素進(jìn)行處理
　　??????? Costomeri ++；? // XPath逐個(gè)對(duì)應(yīng)
　　??????? If(color is Color.End)
　　??????? {
　　?????????? ToCustomer(Customeri，G.currentElement.Value)； // 輸出結(jié)果
　　??????? }
　　??? }
??? }
4 實(shí)驗(yàn)
　　本文實(shí)現(xiàn)了GBRender查詢(xún)模型并應(yīng)用在單枝查詢(xún)上，軟件環(huán)境是Windows xp+eclipse3.3+jdk1.5。硬件環(huán)境是：聯(lián)想旭日410M筆記本電腦，配置為：CPU雙核T2080，內(nèi)存1 GB，硬盤(pán)120 GB。
??? 在實(shí)驗(yàn)中，綜合了文檔大小與查詢(xún)數(shù)目的多少并與YFilter和Index-Filter作比較，結(jié)果發(fā)現(xiàn)，當(dāng)文檔相對(duì)較大時(shí)查詢(xún)數(shù)量無(wú)論多少，GBRender都顯得非常有效；當(dāng)文檔相對(duì)較小而查詢(xún)數(shù)量較大時(shí)，GBRender與YFilter較為有效。實(shí)驗(yàn)結(jié)果如圖7所示。