1.相關(guān)概念

• Fact（事實(shí)）:對(duì)象之間及對(duì)象屬性之間的關(guān)系
• Rule（規(guī)則）:是由條件和結(jié)論構(gòu)成的推理語句，一般表示為if…Then。一個(gè)規(guī)則的if部分稱為L(zhǎng)HS（left-hand-side），then部分稱為RHS（right hand side）。
• Module（模式）：就是指IF語句的條件。這里IF條件可能是有幾個(gè)更小的條件組成的大條件。模式就是指的不能在繼續(xù)分割下去的最小的原子條件。

2.RETE網(wǎng)絡(luò)節(jié)點(diǎn)類型

image.png

• Root Node：所有對(duì)象進(jìn)入網(wǎng)絡(luò)的入口，在一個(gè)網(wǎng)絡(luò)中只有一個(gè)根節(jié)點(diǎn)。借用Rete算法經(jīng)典的示例：

• 1-input node：可分為ObjectTypeNode, AlphaNode, LeftInputAdapterNode等。

Object Type Node：事實(shí)從根節(jié)點(diǎn)進(jìn)入Rete網(wǎng)絡(luò)后，會(huì)立即進(jìn)入Object Type Node節(jié)點(diǎn)。Object Type Node提供了按對(duì)象類型過濾對(duì)象的能力，通過此類節(jié)點(diǎn)可使規(guī)則引擎不做額外的工作。Cheese類型的事實(shí)進(jìn)入網(wǎng)絡(luò)后，只需經(jīng)過類型為Cheese的Object Type Node之后的節(jié)點(diǎn)。如下圖

image.png

Alpha Node：Alpha 節(jié)點(diǎn)是規(guī)則的條件部分的一個(gè)模式。通常用于評(píng)估字面的條件。如下圖，兩個(gè)Alpha Node 分別評(píng)估了Cheese事實(shí)的name和strength屬性。

image.png

• 2-input node（Beta Node）: 擁有兩個(gè)輸入的節(jié)點(diǎn)。Beta Node 節(jié)點(diǎn)用于比較兩個(gè)對(duì)象。兩個(gè)對(duì)象可能是相同或不同的類型。Beta Node主要包含Join Node 和 Not Node兩種類型。
  Join Node：用作連接（join）操作的節(jié)點(diǎn)，相當(dāng)于數(shù)據(jù)庫的表連接操作。
  NotNode：根據(jù)右邊輸入對(duì)左邊輸入的對(duì)象數(shù)組進(jìn)行過濾，兩個(gè) NotNode 可以完成‘ exists ’檢查。
• Terminal Node：到達(dá)一個(gè)終端節(jié)點(diǎn)，表示單條規(guī)則匹配了所有的條件，網(wǎng)絡(luò)中有多個(gè)終端節(jié)點(diǎn)。當(dāng)單條規(guī)則中有or時(shí)，也會(huì)產(chǎn)生多個(gè)終端節(jié)點(diǎn)。

3.完整示例

• 規(guī)則文件

rule1
when
Cheese($cheddar : name == "cheddar" )
$person : Person( favouriteCheese == $cheddar )
then
System.out.println($person.getName() + " likes cheddar" );
end

rule2
when
Cheese( $cheddar : name == "cheddar" )
$person : Person( favouriteCheese != $cheddar )
then
System.out.println($person.getName() + " does not like cheddar" );
end

Rete網(wǎng)絡(luò)：

image.png

從圖上可以看到，編譯后的RETE網(wǎng)絡(luò)中，AlphaNode是共享的，而BetaNode不是共享的。兩條規(guī)則的BetaNode的不同。然后這兩條規(guī)則有各自的Terminal Node。

為何RETE算法效率高

RETE算法優(yōu)于普通代碼邏輯

如：Segment，Hotel，ReservedLounge類型的產(chǎn)品分別有10個(gè)。按照一般的程序處理邏輯，我們要寫三個(gè)For循環(huán)去處理三類產(chǎn)品的打包操作，計(jì)算次數(shù)為三類產(chǎn)品數(shù)目的笛卡爾積級(jí)別的，即：101010 =1000。

而RETE算法采用空間換時(shí)間的策略，將中間的計(jì)算結(jié)果緩存下來（Alpha Memory，Beta Memory）。計(jì)算次數(shù)為10+10+10（Alpha節(jié)點(diǎn)計(jì)算次數(shù)）加上2次join/projection操作（Beta節(jié)點(diǎn)計(jì)算次數(shù)）?；趦?nèi)存中的數(shù)據(jù)做join/projection/selection操作效率很高。

RETE算法的缺點(diǎn)

RETE算法使用了存儲(chǔ)區(qū)存儲(chǔ)已計(jì)算的中間結(jié)果，以空間換取時(shí)間，從而加快系統(tǒng)的速度。然而存儲(chǔ)區(qū)根據(jù)規(guī)則的條件于事實(shí)的數(shù)目成指數(shù)級(jí)增長(zhǎng)，極端情況下會(huì)耗盡系統(tǒng)資源。