ＲＥＴＥ算法的改進及其應用

摘要： 本文先對Rete模式匹配算法進行了概述，然后又從網絡結構對Rete模式匹配算法加以改進和優化，使Rete模式匹配算法更加高效快捷。 然后我們又分別從規則引擎介紹了Rete算法的應用。

關鍵詞： RETE算法；RETE網絡；模式匹配；規則引擎；業務規則

1 引言

Rete算法是一個用來實現產生式規則系統的高效模式匹配算法。該算法是由卡內基梅隆大學的Charles L.Forgy在1974年發表的論文中所闡述的算法，該算法提供了專家系統的一個高效實現.自Rete算法提出以后，它就被用到一些大型的規則系統中，比如比較流行的商用規則引擎ILog、Jess、JBoss Rules等都實現了RETE算法。而在國內還沒有一個真正的業務規則系統，所以對Rete算法的研究還是很有價值的。

2 Rete算法概述

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

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

3 Rete算法的改進

在Charles L. Forgy最初發表的關于Rete算法的論文中以及之后很多的改進算法中，其網絡結構都時相當復雜，非專業技術人員時很難理解的。朱鰲鑫在論Rete網絡的知識存儲特性的論文中對Rete網絡進行了改進，但仍然顯得復雜，對普通的編程人員來說，Rete網絡仍然顯得難于理解，而且在Charles L.Forgy的Rete算法中不支持OR模式。

為此我們提出了一種改進的，面向對象的Rete網絡結構。該網絡結構包括五種節點：根節點、α節點、β節點、終端節點、對象類型節點。并且我們將β節點又分為ORJionNode和ANDJionNode，以支持Or和And兩種模式，并允許對2種模式進行合理地嵌套以實現模式的靈活組合。而且可以具有\"負模式\"，使規則的組合更較靈活。其網絡結構也包括五層：根節點層、屬性測試層、元素測試層、一致性約束測試層和產生式規則事例層。其改進的Rete網絡如圖1所示：

圖中Rootnode為根節點，，它是整個鑒別網絡的入口點；ObjectTypeNode為類型節點，用來測試由根節點送來的標配所涉及類型是否與本節點所表示的類型一致；AlphaNode為α節點(即單輸入節點)，ANDJionNode為And類型的連結節點，ORJionNode為Or類型的連結節點，TerminalNode為終端節點，也稱為終結節點。

4 RETE算法應用

Rete算法的一個重要應用就是規則引擎，規則引擎是一種嵌入在應用程序中的組件，它的任務是把當前提交給引擎的數據對象與加載在引擎中的業務規則進行測試和對比，激活那些符合當前數據狀態下的業務規則，根據業務規則中聲明的執行邏輯，觸發應用程序中對應的操作。其結構圖如圖2所示：

從圖中我們可以看出，它包括規則集容器、工作存儲器、匹配器、執行器，其中規則集容器是用來從規則庫中提前當前對應于應用系統的規則集，并存儲在規則集容器中，為規則匹配提供規則。工作存儲器是存儲當前應用系統環境提供的應用對象，為規則引擎提供用來匹配的條件。并對應用程序對象進行驗證。匹配器是規則引擎的上下文環境，用來關聯工作存儲器和規則集容器，將工作存儲器中的應用程序對象與規則集容器中的一系列規則進行匹配，并將匹配成功的規則實例放入執行器中。執行器存放匹配成功的規則實例，用來執行規則的動作部分，并將執行結果傳回給應用程序。

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

5 結論

本文通過對網絡結構的改進使Rete算法更加高效快捷，通過規則引擎的介紹使我們更加了解Rete算法。

參考文獻

[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：一種優于Rete算法的多模式/多對象匹配算法.小型微型計算機系統.2002，23(2)：176-179頁.

[3] 朱鰲鑫.論Rete網絡的知識存儲特性[A].第九屆全國信息存儲學術會議論文集[C].長沙，1996.

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

[5] 李德泉，劉遠航，周毅.一個基于rete算法的可視化產生式系統，遼寧師范大學學報(自然科學版)，2002.3 Vo 125 No1.