ＲＥＴＥ算法的改進(jìn)及其應(yīng)用

摘要： 本文先對(duì)Rete模式匹配算法進(jìn)行了概述，然后又從網(wǎng)絡(luò)結(jié)構(gòu)對(duì)Rete模式匹配算法加以改進(jìn)和優(yōu)化，使Rete模式匹配算法更加高效快捷。 然后我們又分別從規(guī)則引擎介紹了Rete算法的應(yīng)用。

關(guān)鍵詞： RETE算法；RETE網(wǎng)絡(luò)；模式匹配；規(guī)則引擎；業(yè)務(wù)規(guī)則

1 引言

Rete算法是一個(gè)用來(lái)實(shí)現(xiàn)產(chǎn)生式規(guī)則系統(tǒng)的高效模式匹配算法。該算法是由卡內(nèi)基梅隆大學(xué)的Charles L.Forgy在1974年發(fā)表的論文中所闡述的算法，該算法提供了專家系統(tǒng)的一個(gè)高效實(shí)現(xiàn).自Rete算法提出以后，它就被用到一些大型的規(guī)則系統(tǒng)中，比如比較流行的商用規(guī)則引擎ILog、Jess、JBoss Rules等都實(shí)現(xiàn)了RETE算法。而在國(guó)內(nèi)還沒(méi)有一個(gè)真正的業(yè)務(wù)規(guī)則系統(tǒng)，所以對(duì)Rete算法的研究還是很有價(jià)值的。

2 Rete算法概述

一條規(guī)則由左(LHS)、右(RHS)部分組成，構(gòu)成if(LHS) then (RHS)的結(jié)構(gòu)。左邊(LHS)由一個(gè)或多個(gè)正、負(fù)模式組成，右邊(RHS)由一個(gè)或多個(gè)動(dòng)作(Action)組成。如果一條規(guī)則所包含的模式都得到滿足，那么稱這條規(guī)則被滿足。

Rete算法將規(guī)則的左邊模式編譯成類似于數(shù)據(jù)流網(wǎng)絡(luò)形式的模式識(shí)別網(wǎng)絡(luò)。反映工作存儲(chǔ)器變化的標(biāo)牌從網(wǎng)絡(luò)頂端流入，并在網(wǎng)絡(luò)的節(jié)點(diǎn)間流動(dòng)。網(wǎng)絡(luò)中的單輸入結(jié)點(diǎn)負(fù)責(zé)測(cè)試標(biāo)牌是否能夠匹配一個(gè)模式，成功通過(guò)測(cè)試的標(biāo)牌被存到Alpha存儲(chǔ)器。雙輸入結(jié)點(diǎn)負(fù)責(zé)測(cè)試2個(gè)匹配于不同模式的標(biāo)牌是否滿足變量的一致性約束，通過(guò)測(cè)試的2個(gè)標(biāo)牌被合成一個(gè)并被存到Beta存儲(chǔ)器。標(biāo)牌分為2種類型---正標(biāo)牌和負(fù)標(biāo)牌，正標(biāo)牌表示工作存儲(chǔ)器增添了新元素，負(fù)標(biāo)牌表示工作存儲(chǔ)器中有元素被刪除。 。如果有標(biāo)牌流動(dòng)到某一規(guī)則所對(duì)應(yīng)的終結(jié)結(jié)點(diǎn)，則表示此標(biāo)牌滿足終結(jié)結(jié)點(diǎn)所對(duì)應(yīng)的規(guī)則；此時(shí)要將規(guī)則的所包含的動(dòng)作(Action)放入動(dòng)作執(zhí)行隊(duì)列(Agent-data)中，即沖突集(Conflict Set)就發(fā)生了變化。

3 Rete算法的改進(jìn)

在Charles L. Forgy最初發(fā)表的關(guān)于Rete算法的論文中以及之后很多的改進(jìn)算法中，其網(wǎng)絡(luò)結(jié)構(gòu)都時(shí)相當(dāng)復(fù)雜，非專業(yè)技術(shù)人員時(shí)很難理解的。朱鰲鑫在論Rete網(wǎng)絡(luò)的知識(shí)存儲(chǔ)特性的論文中對(duì)Rete網(wǎng)絡(luò)進(jìn)行了改進(jìn)，但仍然顯得復(fù)雜，對(duì)普通的編程人員來(lái)說(shuō)，Rete網(wǎng)絡(luò)仍然顯得難于理解，而且在Charles L.Forgy的Rete算法中不支持OR模式。

為此我們提出了一種改進(jìn)的，面向?qū)ο蟮腞ete網(wǎng)絡(luò)結(jié)構(gòu)。該網(wǎng)絡(luò)結(jié)構(gòu)包括五種節(jié)點(diǎn)：根節(jié)點(diǎn)、α節(jié)點(diǎn)、β節(jié)點(diǎn)、終端節(jié)點(diǎn)、對(duì)象類型節(jié)點(diǎn)。并且我們將β節(jié)點(diǎn)又分為ORJionNode和ANDJionNode，以支持Or和And兩種模式，并允許對(duì)2種模式進(jìn)行合理地嵌套以實(shí)現(xiàn)模式的靈活組合。而且可以具有\(zhòng)"負(fù)模式\"，使規(guī)則的組合更較靈活。其網(wǎng)絡(luò)結(jié)構(gòu)也包括五層：根節(jié)點(diǎn)層、屬性測(cè)試層、元素測(cè)試層、一致性約束測(cè)試層和產(chǎn)生式規(guī)則事例層。其改進(jìn)的Rete網(wǎng)絡(luò)如圖1所示：

圖中Rootnode為根節(jié)點(diǎn)，，它是整個(gè)鑒別網(wǎng)絡(luò)的入口點(diǎn)；ObjectTypeNode為類型節(jié)點(diǎn)，用來(lái)測(cè)試由根節(jié)點(diǎn)送來(lái)的標(biāo)配所涉及類型是否與本節(jié)點(diǎn)所表示的類型一致；AlphaNode為α節(jié)點(diǎn)(即單輸入節(jié)點(diǎn))，ANDJionNode為And類型的連結(jié)節(jié)點(diǎn)，ORJionNode為Or類型的連結(jié)節(jié)點(diǎn)，TerminalNode為終端節(jié)點(diǎn)，也稱為終結(jié)節(jié)點(diǎn)。

4 RETE算法應(yīng)用

Rete算法的一個(gè)重要應(yīng)用就是規(guī)則引擎，規(guī)則引擎是一種嵌入在應(yīng)用程序中的組件，它的任務(wù)是把當(dāng)前提交給引擎的數(shù)據(jù)對(duì)象與加載在引擎中的業(yè)務(wù)規(guī)則進(jìn)行測(cè)試和對(duì)比，激活那些符合當(dāng)前數(shù)據(jù)狀態(tài)下的業(yè)務(wù)規(guī)則，根據(jù)業(yè)務(wù)規(guī)則中聲明的執(zhí)行邏輯，觸發(fā)應(yīng)用程序中對(duì)應(yīng)的操作。其結(jié)構(gòu)圖如圖2所示：

從圖中我們可以看出，它包括規(guī)則集容器、工作存儲(chǔ)器、匹配器、執(zhí)行器，其中規(guī)則集容器是用來(lái)從規(guī)則庫(kù)中提前當(dāng)前對(duì)應(yīng)于應(yīng)用系統(tǒng)的規(guī)則集，并存儲(chǔ)在規(guī)則集容器中，為規(guī)則匹配提供規(guī)則。工作存儲(chǔ)器是存儲(chǔ)當(dāng)前應(yīng)用系統(tǒng)環(huán)境提供的應(yīng)用對(duì)象，為規(guī)則引擎提供用來(lái)匹配的條件。并對(duì)應(yīng)用程序?qū)ο筮M(jìn)行驗(yàn)證。匹配器是規(guī)則引擎的上下文環(huán)境，用來(lái)關(guān)聯(lián)工作存儲(chǔ)器和規(guī)則集容器，將工作存儲(chǔ)器中的應(yīng)用程序?qū)ο笈c規(guī)則集容器中的一系列規(guī)則進(jìn)行匹配，并將匹配成功的規(guī)則實(shí)例放入執(zhí)行器中。執(zhí)行器存放匹配成功的規(guī)則實(shí)例，用來(lái)執(zhí)行規(guī)則的動(dòng)作部分，并將執(zhí)行結(jié)果傳回給應(yīng)用程序。

規(guī)則引擎的推理步驟如下：(1)將初始數(shù)據(jù)輸入至工作內(nèi)存；(2)使用模式匹配將規(guī)則庫(kù)中的規(guī)則和數(shù)據(jù)比較；(3)如果執(zhí)行規(guī)則存在沖突，即同時(shí)激活了多個(gè)規(guī)則，將沖突的規(guī)則放入沖突集合中；(4)解決沖突，將激活的規(guī)則按順序放入執(zhí)行器中；(5)執(zhí)行其中的規(guī)則；重復(fù)(2)至(5)，直到執(zhí)行完畢執(zhí)行器中的所有規(guī)則。

5 結(jié)論

本文通過(guò)對(duì)網(wǎng)絡(luò)結(jié)構(gòu)的改進(jìn)使Rete算法更加高效快捷，通過(guò)規(guī)則引擎的介紹使我們更加了解Rete算法。

參考文獻(xiàn)

[1] Charles L.Forgy Rete： a fast Algorithm for the many pattern/many object pattern match problem[J].Artificial Intelli-gence，1982：17-37.

[2] 宋震，郭富順，李蓮治.MPR：一種優(yōu)于Rete算法的多模式/多對(duì)象匹配算法.小型微型計(jì)算機(jī)系統(tǒng).2002，23(2)：176-179頁(yè).

[3] 朱鰲鑫.論Rete網(wǎng)絡(luò)的知識(shí)存儲(chǔ)特性[A].第九屆全國(guó)信息存儲(chǔ)學(xué)術(shù)會(huì)議論文集[C].長(zhǎng)沙，1996.

[4] 王永慶人.工智能原理方法應(yīng)用[M].西安：西安交通大學(xué)出版社，199464.73.

[5] 李德泉，劉遠(yuǎn)航，周毅.一個(gè)基于rete算法的可視化產(chǎn)生式系統(tǒng)，遼寧師范大學(xué)學(xué)報(bào)(自然科學(xué)版)，2002.3 Vo 125 No1.