在JBoss Rules 學(xué)習(xí)（一）:什么是Rule中，我們介紹了JBoss Rules中對Rule的表示，其中提到了JBoss Rule中主要采用的RETE算法來進(jìn)行規(guī)則匹配。下面將詳細(xì)的介紹一下RETE算法在JBoss Rule中的實(shí)現(xiàn)，最后隨便提一下JBoss Rules中也可以使用的另一種規(guī)則匹配算法Leaps。
1.Rete
算法
：
Rete
在拉丁語中是
”net”
，有網(wǎng)絡(luò)的意思。
RETE
算法可以分為兩部分：規(guī)則編譯（
rule compilation
）和運(yùn)行時(shí)執(zhí)行（
runtime execution
）。
編譯算法描述了規(guī)則如何在
Production
Memory
中產(chǎn)生一個(gè)有效的辨別網(wǎng)絡(luò)。用一個(gè)非技術(shù)性的詞來說，一個(gè)辨別網(wǎng)絡(luò)就是用來過濾數(shù)據(jù)。方法是通過數(shù)據(jù)在網(wǎng)絡(luò)中的傳播來過濾數(shù)據(jù)。在頂端節(jié)點(diǎn)將會有很多匹配的數(shù)據(jù)。當(dāng)我們順著網(wǎng)絡(luò)向下走，匹配的數(shù)據(jù)將會越來越少。在網(wǎng)絡(luò)的最底部是終端節(jié)點(diǎn)（
terminal nodes
）。在
Dr Forgy
的
1982
年的論文中，他描述了
4
種基本節(jié)點(diǎn)：
root , 1-input, 2-input and
terminal
。下圖是
Drools
中的
RETE
節(jié)點(diǎn)類型：
?
Figure 1.
Rete Nodes
根節(jié)點(diǎn)（
RootNode
）是所有的對象進(jìn)入網(wǎng)絡(luò)的入口。然后，從根節(jié)點(diǎn)立即進(jìn)入到
ObjectTypeNode
。
ObjectTypeNode
的作用是使引擎只做它需要做的事情。例如，我們有兩個(gè)對象集：
Account
和
Order
。如果規(guī)則引擎需要對每個(gè)對象都進(jìn)行一個(gè)周期的評估，那會浪費(fèi)很多的時(shí)間。為了提高效率，引擎將只讓匹配
object type
的對象通過到達(dá)節(jié)點(diǎn)。通過這種方法，如果一個(gè)應(yīng)用
assert
一個(gè)新的
account
，它不會將
Order
對象傳遞到節(jié)點(diǎn)中。很多現(xiàn)代
RETE
實(shí)現(xiàn)都有專門的
ObjectTypeNode
。在一些情況下，
ObjectTypeNode
被用散列法進(jìn)一步優(yōu)化。
Figure 2 .?ObjectTypeNodes
ObjectTypeNode
能夠傳播到
AlphaNodes,
LeftInputAdapterNodes
和
BetaNodes
。
1-input
節(jié)點(diǎn)通常被稱為
AlphaNode
。
AlphaNodes
被用來評估字面條件（
literal conditions
）。雖然，
1982
年的論文只提到了相等條件（指的字面上相等），很多
RETE
實(shí)現(xiàn)支持其他的操作。例如，
Account.name
= = “Mr Trout”
是一個(gè)字面條件。當(dāng)一條規(guī)則對于一種
object type
有多條的字面條件，這些字面條件將被鏈接在一起。這是說，如果一個(gè)應(yīng)用
assert
一個(gè)
account
對象，在它能到達(dá)下一個(gè)
AlphaNode
之前，它必須先滿足第一個(gè)字面條件。在
Dr. Forgy
的論文中，他用
IntraElement conditions
來表述。下面的圖說明了
Cheese
的
AlphaNode
組合（
name = = “cheddar”
，
strength = = “strong”
）：
Figure 3.?AlphaNodes
Drools
通過散列法優(yōu)化了從
ObjectTypeNode
到
AlphaNode
的傳播。每次一個(gè)
AlphaNode
被加到一個(gè)
ObjectTypeNode
的時(shí)候，就以字面值（
literal value
）作為
key
，以
AlphaNode
作為
value
加入
HashMap
。當(dāng)一個(gè)新的實(shí)例進(jìn)入
ObjectTypeNode
的時(shí)候，不用傳遞到每一個(gè)
AlphaNode
，它可以直接從
HashMap
中獲得正確的
AlphaNode
，避免了不必要的字面檢查。
2-input
節(jié)點(diǎn)通常被稱為
BetaNode
。
Drools
中有兩種
BetaNode
：
JoinNode
和
NotNode
。
BetaNodes
被用來對
2
個(gè)對象進(jìn)行對比。這兩個(gè)對象可以是同種類型，也可以是不同類型。
我們約定
BetaNodes
的
2
個(gè)輸入稱為左邊（
left
）和右邊（
right
）。一個(gè)
BetaNode
的左邊輸入通常是
a list of objects
。在
Drools
中，這是一個(gè)數(shù)組。右邊輸入是
a single object
。兩個(gè)
NotNode
可以完成‘
exists
’檢查。
Drools
通過將索引應(yīng)用在
BetaNodes
上擴(kuò)展了
RETE
算法。下圖展示了一個(gè)
JoinNode
的使用：
Figure 4 .?JoinNode
注意到圖中的左邊輸入用到了一個(gè)
LeftInputAdapterNode
，這個(gè)節(jié)點(diǎn)的作用是將一個(gè)
single Object
轉(zhuǎn)化為一個(gè)單對象數(shù)組（
single Object Tuple
），傳播到
JoinNode
節(jié)點(diǎn)。因?yàn)槲覀兩厦嫣岬竭^左邊輸入通常是
a list of objects
。
Terminal nodes
被用來表明一條規(guī)則已經(jīng)匹配了它的所有條件（
conditions
）。
在這點(diǎn)，我們說這條規(guī)則有了一個(gè)完全匹配（
full match
）。在一些情況下，一條帶有“或”條件的規(guī)則可以有超過一個(gè)的
terminal node
。
Drools
通過節(jié)點(diǎn)的共享來提高規(guī)則引擎的性能。因?yàn)楹芏嗟囊?guī)則可能存在部分相同的模式，節(jié)點(diǎn)的共享允許我們對內(nèi)存中的節(jié)點(diǎn)數(shù)量進(jìn)行壓縮，以提供遍歷節(jié)點(diǎn)的過程。下面的兩個(gè)規(guī)則就共享了部分節(jié)點(diǎn)：
rule
????when
????????Cheese(?$chedddar?:?name?
==
?
"
cheddar
"
?)
????????$person?:?Person(?favouriteCheese?
==
?$cheddar?)
????then
????????System.out.println(?$person.getName()?
+
?
"
?likes?cheddar
"
?);
end
rule
????when
????????Cheese(?$chedddar?:?name?
==
?
"
cheddar
"
?)
????????$person?:?Person(?favouriteCheese?
!=
?$cheddar?)
????then
????????System.out.println(?$person.getName()?
+
?
"
?does?likes?cheddar
"
?);
end
這里我們先不探討這兩條
rule
到的是什么意思，單從一個(gè)直觀的感覺，這兩條
rule
在它們的
LHS
中基本都是一樣的，只是最后的
favouriteCheese
，一條規(guī)則是等于
$cheddar
，而另一條規(guī)則是不等于
$cheddar
。下面是這兩條規(guī)則的節(jié)點(diǎn)圖：
Figure 5 .?Node
Sharing
從圖上可以看到，編譯后的
RETE
網(wǎng)絡(luò)中，
AlphaNode
是共享的，而
BetaNode
不是共享的。上面說的相等和不相等就體現(xiàn)在
BetaNode
的不同。然后這兩條規(guī)則有各自的
Terminal Node
。
RETE
算法的第二個(gè)部分是運(yùn)行時(shí)（
runtime
）。當(dāng)一個(gè)應(yīng)用
assert
一個(gè)對象，引擎將數(shù)據(jù)傳遞到
root
node
。從那里，它進(jìn)入
ObjectTypeNode
并沿著網(wǎng)絡(luò)向下傳播。當(dāng)數(shù)據(jù)匹配一個(gè)節(jié)點(diǎn)的條件，節(jié)點(diǎn)就將它記錄到相應(yīng)的內(nèi)存中。這樣做的原因有以下幾點(diǎn)：主要的原因是可以帶來更快的性能。雖然記住完全或部分匹配的對象需要內(nèi)存，它提供了速度和可伸縮性的特點(diǎn)。當(dāng)一條規(guī)則的所有條件都滿足，這就是完全匹配。而只有部分條件滿足，就是部分匹配。（我覺得引擎在每個(gè)節(jié)點(diǎn)都有其對應(yīng)的內(nèi)存來儲存滿足該節(jié)點(diǎn)條件的對象，這就造成了如果一個(gè)對象是完全匹配，那這個(gè)對象就會在每個(gè)節(jié)點(diǎn)的對應(yīng)內(nèi)存中都存有其映象。）
2. Leaps
算法：
Production systems
的
Leaps
算法使用了一種“
lazy
”方法來評估條件（
conditions
）。一種
Leaps
算法的修改版本的實(shí)現(xiàn)，作為
Drools v3
的一部分，嘗試結(jié)合
Leaps
和
RETE
方法的最好的特點(diǎn)來處理
Working Memory
中的
facts
。
古典的
Leaps
方法將所有的
asserted
的
facts
，按照其被
asserted
在
Working Memory
中的順序（
FIFO
），放在主堆棧中。它一個(gè)個(gè)的檢查
facts
，通過迭代匹配
data
type
的
facts
集合來找出每一個(gè)相關(guān)規(guī)則的匹配。當(dāng)一個(gè)匹配的數(shù)據(jù)被發(fā)現(xiàn)時(shí)，系統(tǒng)記住此時(shí)的迭代位置以備待會的繼續(xù)迭代，并且激發(fā)規(guī)則結(jié)果（
consequence
）。當(dāng)結(jié)果（
consequence
）執(zhí)行完成以后，系統(tǒng)就會繼續(xù)處理處于主堆棧頂部的
fact
。如此反復(fù)。