正向推理規(guī)則引擎中的Rete模式匹配算法研究

魏毅峰 (鄖陽師范高等專科學校數(shù)學與財經(jīng)系，湖北 十堰 442000)

正向推理規(guī)則引擎中的Rete模式匹配算法研究

魏毅峰 (鄖陽師范高等專科學校數(shù)學與財經(jīng)系，湖北 十堰 442000)

規(guī)則引擎技術(shù)是專家系統(tǒng)中的一種比較實用的技術(shù)，它的核心算法是Rete模式匹配算法。深入研究了被廣泛應(yīng)用于正向推理規(guī)則引擎中的Rete模式匹配算法，對Rete網(wǎng)絡(luò)的構(gòu)建和Rete算法的執(zhí)行全過程進行了詳細分析。

規(guī)則引擎；正向推理規(guī)則引擎；Rete模式匹配算法

Rete算法的核心思想是通過在內(nèi)存中維護一個極其復雜的數(shù)據(jù)結(jié)構(gòu)Rete網(wǎng)絡(luò)來保存中間匹配結(jié)果，以達到顯著減少計算量的效果，即犧牲內(nèi)存空間來換取運行時間。Rete網(wǎng)絡(luò)的構(gòu)建主要是基于規(guī)則的LHS有很大的相似性的這個特點，通過保存規(guī)則的條件部分(也稱為左端，即LHS, left-hand side)的各個模式的匹配結(jié)果，以便別的規(guī)則直接利用該模式匹配結(jié)果，可以極大地減少重復的匹配運算，從而達到提升模式匹配效率的效果。當前，大部分規(guī)則引擎產(chǎn)品的模式匹配算法，基本上都來自于Charles L. Forgy博士于1979 年在其博士論文中提出的Rete算法及其變體， Rete算法是目前在正向推理規(guī)則引擎中的效率最高的一個模式匹配算法[1-2]。下面，筆者對Rete網(wǎng)絡(luò)的構(gòu)建和Rete算法的執(zhí)行過程進行了詳細的分析。

1 Rete網(wǎng)絡(luò)的構(gòu)建

Rete算法在進行模式匹配時，是根據(jù)預先構(gòu)建的Rete網(wǎng)絡(luò)來進行的[1]。Rete網(wǎng)絡(luò)的根節(jié)點是網(wǎng)絡(luò)的入口，非根節(jié)點有2種類型的節(jié)點：Alpha節(jié)點和Beta節(jié)點。由Alpha節(jié)點組成局部網(wǎng)絡(luò)稱為Alpha網(wǎng)絡(luò)，由Beta節(jié)點組成的另一局部網(wǎng)絡(luò)稱為Beta網(wǎng)絡(luò)。每個非根結(jié)點都有一個存儲區(qū)，用于保存模式匹配的中間結(jié)果。其中Alpha節(jié)點有一個Alpha存儲區(qū)和一個輸入口，Beta節(jié)點有左右2個存儲區(qū)和左右2個輸入口，左存儲區(qū)也稱為Beta存儲區(qū)，右存儲區(qū)也稱為Alpha存儲區(qū)。在Alpha節(jié)點和Beta節(jié)點中，Alpha存儲區(qū)存儲的都是一組事實Fact，Beta存儲區(qū)存儲的都是一組Token，其中每個Token由一個或若干個事實Fact通過join，select，projection等操作合并而成。事實Fact可以做為Alpha節(jié)點的輸入，也可以作為Beta節(jié)點的右輸入，Token節(jié)點只能作為Beta節(jié)點的左輸入。每個Alpha節(jié)點或Beta節(jié)點都對應(yīng)這一個模式，葉子節(jié)點則對應(yīng)著某一條規(guī)則，因此從根節(jié)點到葉子節(jié)點的路徑對應(yīng)著該規(guī)則的LHS，當有Fact或Token被傳遞到一個葉子節(jié)點時，表示該規(guī)則的條件已經(jīng)滿足了，可以被觸發(fā)執(zhí)行。

Rete網(wǎng)絡(luò)的構(gòu)建過程如下所述：

1)創(chuàng)建網(wǎng)絡(luò)的根節(jié)點，根節(jié)點是Rete網(wǎng)絡(luò)的入口。

2)讀取規(guī)則庫中的一條規(guī)則，按照如下方式創(chuàng)建Alpha 節(jié)點和Beta節(jié)點到Rete網(wǎng)絡(luò)中。其中Alpha節(jié)點從1開始編號，Beta節(jié)點則從2開始編號。①讀取該規(guī)則的一個模式，檢查該模式的模板類型，如果是新的模板類型，則創(chuàng)建一個子節(jié)點，作為代表這一模板類型的類型節(jié)點(TypeNode)。②檢查該模式是否有對應(yīng)的Alpha節(jié)點已存在，如果存在則記錄下節(jié)點位置，否則添加一個新的代表該模式的Alpha節(jié)到網(wǎng)絡(luò)中。③重復②直到該規(guī)則的所有模式都處理完畢。④按照如下方式創(chuàng)建Beta節(jié)點：Beta(2)的左輸入節(jié)點為Alpha(1)，右輸入節(jié)點為Alpha(2)；Beta(i)左輸入節(jié)點為Beta(i-1)，右輸入節(jié)點為Alpha(i)，其中igt;2。⑤重復④直到?jīng)]有新的Beta節(jié)點需要創(chuàng)建。⑥將規(guī)則的執(zhí)行部分封裝成葉子節(jié)點，并且其輸入節(jié)點為Beta(n)。

3)重復2)直到規(guī)則庫中的所有規(guī)則都處理完畢。

2 Rete算法的執(zhí)行過程

Rete網(wǎng)絡(luò)構(gòu)建完畢之后，推理引擎將開始進行匹配操作，即把事實庫中的每一個事實Fact從Rete網(wǎng)絡(luò)的根節(jié)點輸入到網(wǎng)絡(luò)中進行匹配。不同的節(jié)點處理輸入進來Fact或Token所采取的策略也不同，下面是各個情況下的節(jié)點處理方法。

1)根節(jié)點的直接子Alpha節(jié)點也稱為類型節(jié)點(TypeNode)，每個類型節(jié)點和一個事實模板一一對應(yīng)。當有新的Fact輸入到類型節(jié)點時，類型節(jié)點會判斷該Fact是否和自身所代表的事實模板匹配，若匹配則把Fact保存到該節(jié)點的Alpha存儲區(qū)中，并繼續(xù)向后繼子節(jié)點傳遞該Fact；否則該節(jié)點不采取任何動作，拒絕輸入的Fact。

2)當Fact被傳遞到某個Alpha節(jié)點，該節(jié)點會判斷輸入進來的Fact是否和該結(jié)點所代表的模式相匹配，若匹配則把Fact保存到該節(jié)點的Alpha存儲區(qū)中，并繼續(xù)向后繼子節(jié)點傳遞該Fact；否則該節(jié)點不采取任何動作，拒絕輸入的Fact。

3)當Fact被傳遞到某個Beta節(jié)點的右端時，該Beta節(jié)點會先把該Fact加入到它的Alpha存儲區(qū)中，然后對Beta存儲區(qū)和Alpha存儲區(qū)進行匹配操作，類似于關(guān)系數(shù)據(jù)庫中2個表之間的join，projection，selection等運算。若2個存儲區(qū)之間的運算有結(jié)果，則把該結(jié)果封裝為一個新的Token傳遞到后繼子節(jié)點的左輸入口中；否則該節(jié)點不采取任何動作。

4)當Token被傳遞到某個Beta節(jié)點的左端時，該Beta節(jié)點會先把該Token加入到它的Beta存儲區(qū)中，然后對Beta存儲區(qū)和Alpha存儲區(qū)進行匹配操作，類似于關(guān)系數(shù)據(jù)庫中2個表之間的join，projection，selection等運算。若2個存儲區(qū)之間的運算有結(jié)果，則把該結(jié)果封裝為一個新的Token傳遞到后繼子節(jié)點的左輸入口中；否則該節(jié)點不采取任何動作。

5)當Fact被傳遞到某個Beta節(jié)點的左端時，則將該Fact封裝成一個新的Token，然后按照4)的策略進行處理。

6)當Token被傳遞到某個葉子結(jié)點時，則表示該葉子節(jié)點所代表的規(guī)則成功被匹配，該規(guī)則和相應(yīng)的Token會被加入到議程器中等待進行沖突解決。

7)當Fact被傳遞到某個葉子結(jié)點時，則將Fact封裝成一個新的Token，然后按照6)的策略進行匹配。

3 算法實例與分析

下面通過一個簡單的例子來展示Rete算法的過程。假設(shè)系統(tǒng)中存在A、B、C和D 4個模板，每個模板都有一個共同的屬性ID；系統(tǒng)的事實庫中存在以下事實：A(00)、A(01)、B(01)、B(02)、B(03)；系統(tǒng)的規(guī)則庫中存在以下3個規(guī)則：

Rule-1：If A(x) and B(x) then add C(x)

Rule-2：If A(x) and B(x) and C(x) then add D(x)

Rule-3：If A(x) and B(x) and D(x) then delete A(x)

圖1 Rete網(wǎng)絡(luò)實例

Rete算法會首先根據(jù)上述3條規(guī)則構(gòu)建如圖1所示的Rete網(wǎng)絡(luò)。在圖1中，Alpha網(wǎng)絡(luò)中的子節(jié)點的功能主要是根據(jù)傳遞進來的Fact的類型來對Fact進行分類，并把符合條件的Fact保存到自己的Alpha存儲區(qū)中。而Beta網(wǎng)絡(luò)中的節(jié)點都是雙輸入的，從左輸入的Token會被保存到該Beta節(jié)點的Beta存儲區(qū)中，從右輸入的Fact則會被保存到Beta節(jié)點Alpha存儲區(qū)中；每次當存儲區(qū)有新的Token或Fact進來之后，Alpha存儲區(qū)和Beta存儲區(qū)之間都會進行匹配運算，這類似于關(guān)系數(shù)據(jù)庫中的表的連接操作，若匹配成功則把該結(jié)果封裝為新的Token傳遞到后續(xù)子節(jié)點。

顯然，Rule-1規(guī)則會首先被觸發(fā)執(zhí)行，進而在事實庫中添加事實C(01)。C(01)從Rete網(wǎng)絡(luò)的根節(jié)點開始依次沿著路徑向下匹配，最終觸發(fā)Rule-2，創(chuàng)建事實D(01)到事實庫中。同樣的道理，D(01)從Rete網(wǎng)絡(luò)的根節(jié)點開始沿著路徑往下匹配，最后也觸發(fā)執(zhí)行Rule-3，進而刪掉事實A(01)。在整個過程中Alpha節(jié)點和Beta節(jié)點都保存了相應(yīng)的匹配中間結(jié)果，所以極大地加快了Rete算法的匹配速度。

[1]鮑金玲.基于規(guī)則引擎技術(shù)的Rete算法的研究[J].科技信息，2008(32):90-103.

[2]姜濤.Drools規(guī)則引擎的研究與應(yīng)用[EB/OL].http://www.paper.edu.cn/index.php/default/releasepaper/downpaper/，2008-12-14.

[編輯] 洪云飛

10.3969/j.issn.1673-1409(N).2012.03.031

TP311

A

1673-1409(2012)03-N093-03

2011-12-23

魏毅峰(1978-)，男，1999年大學畢業(yè)，碩士，講師，現(xiàn)主要從事模式識別與智能系統(tǒng)方面的教學與研究工作。