1、云計(jì)算專(zhuān)欄基于云計(jì)算思想和機(jī)的主動(dòng)服務(wù)研究木王桐。趙春暉。陸軍（哈爾濱工程大學(xué)信息與通信工程學(xué)院哈爾濱；黑龍江大學(xué)計(jì)算機(jī)學(xué)院哈爾濱）圜云計(jì)算是一個(gè)更先進(jìn)的計(jì)算概念，是網(wǎng)格計(jì)算和分布式計(jì)算的延伸。基于的主動(dòng)服務(wù)具聯(lián)網(wǎng)海量的異構(gòu)半，結(jié)構(gòu)化數(shù)據(jù)，過(guò)濾引擎執(zhí)行效率通常是該系統(tǒng)的瓶頸所在。鑒于此，利用森林原型系統(tǒng)中，并闡述該系統(tǒng)的組成及其關(guān)鍵技術(shù)。有異構(gòu)性、海量性、按需服務(wù)等特點(diǎn)，因此可看作是具有網(wǎng)絡(luò)計(jì)算能力的云計(jì)算的應(yīng)用之一。面對(duì)互文法提出機(jī)算法以提高執(zhí)行匹配能力結(jié)合云計(jì)算思想，將該算法應(yīng)用于提出的主動(dòng)服務(wù)；關(guān)鍵詡海量數(shù)據(jù)；生動(dòng)服務(wù)；云計(jì)算；模式量性、數(shù)據(jù)驅(qū)動(dòng)、按需服務(wù)等特點(diǎn)。因此可看作是具有網(wǎng)絡(luò)引言

2、云計(jì)算【是分布式處理、并行處理、網(wǎng)格計(jì)算、網(wǎng)絡(luò)存計(jì)算能力的云計(jì)算的重要應(yīng)用之一。這類(lèi)服務(wù)通常以、語(yǔ)句作為訂閱模型。用自動(dòng)機(jī)對(duì)查詢進(jìn)行描述，并將其作為過(guò)濾引擎同其他事件代理結(jié)點(diǎn)路由而來(lái)的發(fā)布流進(jìn)行匹配，返回相關(guān)結(jié)果。然而，在處理大規(guī)模異構(gòu)數(shù)據(jù)時(shí)，過(guò)濾引擎的處理效率將成為系統(tǒng)的瓶頸。很多研究表明闈線性有限自動(dòng)機(jī)處理匹配問(wèn)題時(shí)，需要將路徑表達(dá)式中的祖先符，、通配符木等不確定因素改寫(xiě)。以增強(qiáng)運(yùn)行時(shí)的效率。而從到的轉(zhuǎn)換過(guò)程經(jīng)常導(dǎo)致搜索空間的組合爆炸。另外，一些研究引入了樹(shù)自動(dòng)機(jī)來(lái)處理樹(shù)狀結(jié)構(gòu)數(shù)據(jù)。樹(shù)自動(dòng)機(jī)是傳統(tǒng)字符自動(dòng)機(jī)的擴(kuò)展，在很多領(lǐng)域發(fā)揮了巨大優(yōu)勢(shì)。然而，現(xiàn)有的樹(shù)自動(dòng)機(jī)（如二叉樹(shù)自動(dòng)機(jī)或儲(chǔ)等的進(jìn)一步

3、發(fā)展和商業(yè)實(shí)現(xiàn)。由于數(shù)據(jù)具有海量性和異構(gòu)性，如何對(duì)這些海量半非結(jié)構(gòu)數(shù)據(jù)進(jìn)行分析和自動(dòng)處理也就成為云計(jì)算中亟待解決的重要課題。主動(dòng)服務(wù)是在服務(wù)框架模型基礎(chǔ)上按需定制的查詢模式，在這種模型產(chǎn)生前，人們采用傳統(tǒng)搜索引擎（如）進(jìn)行檢索，返回?cái)?shù)以萬(wàn)計(jì)的文檔，仍需在返回結(jié)果中人工篩選，導(dǎo)致“數(shù)據(jù)豐富而信息貧乏（）”的現(xiàn)象。近年來(lái)，由于文檔自身帶有結(jié)構(gòu)和語(yǔ)義信息等優(yōu)勢(shì)越來(lái)越多的信息通過(guò)格式進(jìn)行交互和發(fā)布一互聯(lián)網(wǎng)出現(xiàn)大量基于的主動(dòng)服務(wù)應(yīng)用【：發(fā)布，訂閱系統(tǒng)、實(shí)時(shí)股票系統(tǒng)、個(gè)性化網(wǎng)購(gòu)系統(tǒng)等。與傳統(tǒng)的分布式計(jì)算環(huán)境相比，主動(dòng)服務(wù)具有異構(gòu)性、海）存在一些不足，如兄弟結(jié)點(diǎn)有序性、無(wú)法表述無(wú)根結(jié)點(diǎn)的森林（）問(wèn)題。，而森

4、林文法的出現(xiàn)懈決了這些中國(guó)博士后科學(xué)基金資助項(xiàng)目（），中央高校基本科研業(yè)務(wù)費(fèi)專(zhuān)項(xiàng)資金資助項(xiàng)目）根據(jù)以上分析，本文采用擴(kuò)展森林文法來(lái)更自然地描述路徑表達(dá)式，然后通過(guò)機(jī)進(jìn)行匹配。在此匿丐云計(jì)算專(zhuān)欄基礎(chǔ)上進(jìn)一步將算法用到我們開(kāi)發(fā)的主動(dòng)服務(wù)仿真平臺(tái)上，獲得了良好的效果。機(jī)過(guò)濾算法機(jī)生成過(guò)程森林（）概念是由“最早提出的，其原意為一系列樹(shù)，或稱(chēng)森林。在參考文獻(xiàn)】中第一次將概念引用到領(lǐng)域中。本文將擴(kuò)展森林文法，并通過(guò)該森林文法描述及模式。建立森林機(jī)并通過(guò)模式約束自動(dòng)機(jī)來(lái)優(yōu)化其分析處理能力。定義（非終結(jié)符集合上的正則式和正則集）給定非終結(jié)符集合則之上的正則式和它所表示的正則集可遞歸定義如下：（）占是正則式，其

5、表示的正則集是忙；（）任意是正則式，它表示的正則集是；（）如果、是正則式，分別表示的正則集是三似）和（），則、也都是正則式，分別表示的正則集是（），（）（），（）。僅由有限次使用以上條規(guī)則所定義的表達(dá)式，稱(chēng)為上的正則式且這些正則式表示的字符串集合才是上的正則集。同樣地下文使用的狀態(tài)集合上的正則式可類(lèi)似定義。定義（正則森林文法）正則森林文法定義為一個(gè)五元組（三，），其中：三表示符號(hào)的有限集合；表示數(shù)據(jù)類(lèi)型的有限集合：表示非終結(jié)符的有限集合；由非終結(jié)符組成，且；表示產(chǎn)生式的有限集合每條產(chǎn)生式滿足以下兩種形式之一：（）咄，其中，算；（）口，其中，三，是由非終結(jié)符構(gòu)成的正則式。舟畎腫，可以得到語(yǔ)言（）

6、：，聲，。例：給定正則森林文法（，仁，。？）其中給出的正則森林文法與是可以轉(zhuǎn)換的，即通過(guò)給定可以構(gòu)造一個(gè)相應(yīng)的森林文法。定義（擴(kuò)展正則森林文法）一個(gè)擴(kuò)展正則森林文法定義為一個(gè)六元組：（三，研，其中：三表示符號(hào)的有限集合；表示數(shù)據(jù)類(lèi)型的有限集合；表示樹(shù)變量的有限集合；表示森林變量的有限集合：由非終結(jié)符組成，且；表示產(chǎn)生式的有限集合，每條產(chǎn)生式滿足以下幾種形式之一。），其中，口。，本規(guī)則適用于產(chǎn)生單結(jié)點(diǎn)樹(shù)。，其中，三，鞏，本規(guī)則適用于給森林加一個(gè)結(jié)點(diǎn)。口廠切。，其中，），），本規(guī)則適用于森林中生成子森林或子樹(shù)。定義擴(kuò)展了定義。將樹(shù)的概念擴(kuò)展到森林，通過(guò)這條產(chǎn)生式規(guī)則將二者有機(jī)地統(tǒng)一起來(lái)。根據(jù)正則森

7、林文法本文給出構(gòu)造森林自動(dòng)機(jī)（。）的過(guò)程如下。定義（森林自動(dòng)機(jī)）定義森林自動(dòng)機(jī)為六元組三，仃，其中：三表示符號(hào)的有限集合；表示數(shù)據(jù)類(lèi)型的有限集合；表示狀態(tài)集合；表示狀態(tài)轉(zhuǎn)移函數(shù)：，叮，舢，印表示，三上的正則集；丌為從到的映射，仃：；為終止?fàn)顟B(tài)集。是上的正則集。定理給定正則森林文法（三，），產(chǎn)生的語(yǔ)言為（），則存在一個(gè)接受的語(yǔ)言三（）。證明從略。下文將根據(jù)路徑表達(dá)式來(lái)構(gòu)造，本文稱(chēng)之為（）機(jī)。用來(lái)對(duì)流進(jìn)行過(guò)濾。基于機(jī)流過(guò)濾算法本節(jié)將詳細(xì)描述如何用機(jī)作為過(guò)濾器完成流上的路徑表達(dá)式查詢。教授在參考文獻(xiàn)【】證明了用傳統(tǒng)的轉(zhuǎn)換方法將帶有，的查詢轉(zhuǎn)化為是一個(gè)問(wèn)題并提出了一個(gè)的轉(zhuǎn)換方法即當(dāng)文檔流入時(shí)才在內(nèi)存中

8、組織查詢；還提出了如何在圖模式中優(yōu)化路徑查詢的方法，利用傳統(tǒng)自動(dòng)機(jī)表達(dá)不包含“口”的路徑查詢和圖模式，通過(guò)路徑自動(dòng)機(jī)和圖模式自動(dòng)機(jī)的約束減少路徑查詢中的不確定因素，提高路徑查詢效率。但是，這種方法的處理能力有限，不支持“口竹，也不支持模式。參考文獻(xiàn)用模式對(duì)查詢語(yǔ)句進(jìn)行約束但是該法主要應(yīng)用于中的數(shù)據(jù)。參考文獻(xiàn)】利用）完成了表達(dá)式的重寫(xiě)簡(jiǎn)化轉(zhuǎn)換，該方法基于產(chǎn)生了若干規(guī)則利用規(guī)則等價(jià)重寫(xiě)，并且證明了算法在特定和之上是完備的。參考文獻(xiàn)】和【】給出了支持不同特性的在下包含判定的復(fù)雜性。利用樹(shù)自動(dòng)機(jī)來(lái)表達(dá)和獲取并解釋樹(shù)自動(dòng)機(jī)上基本運(yùn)算的結(jié)果。本文主要目的是利用約束重寫(xiě)的，而不是討論的包含問(wèn)題本文采用基于森

9、林文法的機(jī)來(lái)更好地進(jìn)行描述，給出的算法更具通用性。給定路徑表達(dá)式形，給出對(duì)應(yīng)的機(jī)作為過(guò)濾引擎算法。輸入：路徑表達(dá)式形輸出：正則森林文法（三，）初始化，忍，船行；非終結(jié)符遇到三將產(chǎn)生字母表上的正則式，即三；（非空）如一是葉結(jié)點(diǎn)坳（）吩三，在產(chǎn)生式中加入規(guī)則：鞏；（一），靠硒（訂碼三，在產(chǎn)生式中加人規(guī)則：以血；如一與其父結(jié)點(diǎn)用“”連接，在產(chǎn)生式中加入規(guī)則：三，；：聊射（如，一）；自下而上分析在中，出一指路徑表達(dá)式塒中的結(jié)點(diǎn)，用。三表示產(chǎn)生式集合，口硯。這樣，通過(guò)自下而上掃描）【路徑表達(dá)式，得到相應(yīng)的正則森林文法。隨后，根據(jù)上文給出的得到機(jī)。限于篇幅，算法可行性及完備性證明請(qǐng)參見(jiàn)參考文獻(xiàn)。海量數(shù)據(jù)發(fā)

10、布訂閱服務(wù)云計(jì)算應(yīng)用實(shí)例提出的基于森林機(jī)的過(guò)濾算法在我們開(kāi)發(fā)的主動(dòng)處理海量數(shù)據(jù)的發(fā)布訂閱系統(tǒng)（）原型系統(tǒng)】中起到關(guān)鍵作用得到良好運(yùn)行效果。筆者開(kāi)發(fā)的主動(dòng)服務(wù)系統(tǒng)具有云計(jì)算應(yīng)用的重要特征：可擴(kuò)展性和高可用性。可擴(kuò)展性是指代理結(jié)點(diǎn)能夠無(wú)縫地?cái)U(kuò)展到大規(guī)模的集群之上。甚至包含數(shù)千個(gè)結(jié)點(diǎn)同時(shí)處理。高可用性是指該發(fā)布訂閱系統(tǒng)能夠容忍代理結(jié)點(diǎn)的錯(cuò)誤，甚至有很大一部分結(jié)點(diǎn)發(fā)生失效也不會(huì)影響程序的正確運(yùn)行。下面簡(jiǎn)要描述一下某事件代理結(jié)點(diǎn)的體系結(jié)電信科學(xué)年第期構(gòu)，以說(shuō)明該算法是如何在該云計(jì)算應(yīng)用起到關(guān)鍵作用的。我們將互聯(lián)網(wǎng)中每個(gè)主機(jī)可看作一個(gè)事件代理結(jié)點(diǎn)。整個(gè)云計(jì)算過(guò)程在互聯(lián)網(wǎng)中計(jì)算機(jī)結(jié)點(diǎn)進(jìn)行。每個(gè)事件代理結(jié)點(diǎn)都

11、可以與其他結(jié)點(diǎn)協(xié)作完成訂閱、發(fā)布及事件轉(zhuǎn)發(fā)等功能，即將計(jì)算量分布到互聯(lián)網(wǎng)的結(jié)點(diǎn)上。每個(gè)事件代理結(jié)點(diǎn)主要由三部分構(gòu)成：語(yǔ)義化異構(gòu)事件處理模塊、匹配引擎以及事件轉(zhuǎn)發(fā)模塊如圖所示。（）匹配引擎匹配引擎是系統(tǒng)在線處理部分，包括事件解析器、訂閱器、邏輯優(yōu)化單元及匹配引擎等。其中，事件解析器采用軟件包中的，將發(fā)布事件處理為解析事件流；訂閱器主要負(fù)責(zé)本地的用戶訂閱，在用戶列表中記錄每位用戶的名稱(chēng)、訂閱條件、等信息：邏輯優(yōu)化單元通過(guò)訂閱模型與模式信息對(duì)用戶訂閱條件進(jìn)行確定性查詢重寫(xiě)。匹配引擎由多個(gè)邏輯優(yōu)化單元組合而成，可支持多用戶訂閱。系統(tǒng)中采用的匹配引擎就是基于森林模式自動(dòng)機(jī)約束的機(jī)及其優(yōu)化算法。（）異構(gòu)事

12、件處理模塊異構(gòu)事件處理模塊是其他數(shù)據(jù)驅(qū)動(dòng)系統(tǒng)所不具備的，為模型特色之一，包括數(shù)據(jù)特征生成器、分類(lèi)器、數(shù)據(jù)聚合等主要部分。該模塊采用基于和支持度相結(jié)合的相似性測(cè)度方法，然后在空間對(duì)文檔進(jìn)行二階段聚類(lèi)分析：在自動(dòng)形成若干類(lèi)簇后，提取其模式用于訂閱模型的建立、自動(dòng)維護(hù)和匹配引擎的生成。該模塊詳細(xì)描述請(qǐng)參閱參考文獻(xiàn)】，此不贅述。（）事件轉(zhuǎn)發(fā)事件轉(zhuǎn)發(fā)模塊包括事件加工和事件轉(zhuǎn)發(fā)兩部分。前者負(fù)責(zé)對(duì)中間形式的查詢結(jié)果進(jìn)行處理；后者是將匹配的事件轉(zhuǎn)發(fā)給在該事件代理進(jìn)行訂閱個(gè)性化信息的本地用戶。設(shè)置好敏感信息過(guò)濾以后，一經(jīng)發(fā)現(xiàn)，可立即采用報(bào)警，或者通過(guò)短消息、發(fā)送到用戶的手機(jī)，并做出相關(guān)響應(yīng)；同時(shí)。將該發(fā)布事件繼

13、續(xù)路由至下一事件代理，以達(dá)到連鎖應(yīng)急的效果。如何使事件沿著一種恰當(dāng)?shù)穆窂剑统杀尽⒏咝实氐竭_(dá)各相關(guān)訂閱者，這是路由協(xié)議所要解決的問(wèn)題。原型系統(tǒng)中。路由算法采用協(xié)議和內(nèi)容匹配優(yōu)先相結(jié)合的精確路由算法。首先，每個(gè)事件代理分配有一個(gè)位比特的惟一標(biāo)識(shí)（），并按照協(xié)議自組織成一個(gè)在上呈環(huán)狀結(jié)構(gòu)的網(wǎng)絡(luò)。然后，每個(gè)事件代理結(jié)點(diǎn)構(gòu)建和維護(hù)一棵以自己為根的事件分發(fā)樹(shù)。當(dāng)某事件代理收到客戶端發(fā)布的事件消息時(shí)，將沿三圣霧薹云計(jì)算專(zhuān)欄異構(gòu)事件事件代理圖體系中的事件代理著分發(fā)樹(shù)的結(jié)點(diǎn)從上向下轉(zhuǎn)發(fā)事件消息。當(dāng)某事件代理收到客戶端發(fā)送的訂閱消息時(shí)。將沿著分發(fā)樹(shù)的逆向轉(zhuǎn)發(fā)訂閱消息。其次，對(duì)于分發(fā)樹(shù)的每條路徑設(shè)置一個(gè)事件匹配引擎，它由所有從該路徑逆向轉(zhuǎn)發(fā)來(lái)的訂閱條件匯聚而成，只有事件內(nèi)容與匹配引擎條件匹配的事件消息才能到達(dá)其后續(xù)結(jié)點(diǎn)，從而避免不必要的事件轉(zhuǎn)發(fā)。圖是云計(jì)算拓?fù)涞氖疽鈭D，每個(gè)事件代理節(jié)點(diǎn)都可以進(jìn)行發(fā)布或訂閱操作。結(jié)束語(yǔ)本文采用擴(kuò)展森林文法來(lái)更自然地描述路徑表達(dá)式，然后，通過(guò)機(jī)進(jìn)行主動(dòng)服務(wù)匹配，最后，將森林機(jī)算法應(yīng)用于自主研發(fā)的云計(jì)算系統(tǒng)實(shí)例主動(dòng)服務(wù)仿真原型上，以處理互聯(lián)網(wǎng)上海