漫話規則引擎(2): 模式比對算法

本文最新版已更新至：http://thinkinside.tk/2012/12/05/algorithm_of_pattern_match.html

前面提到，規則引擎的核心是Pattern Matcher(模式比對器)。不管是正向推理還是反向推理，首先要解決一個模式比對的問題。

對于規則的模式比對，可以定義為： 一個規則是一組模式的集合。如果事實/假設的狀态符合該規則的所有模式，則稱為該規則是可滿足的。 模式比對的任務就是将事實/假設的狀态與規則庫中的規則一一比對，找到所有可滿足的規則。

2.1 什麼是模式比對

對于模式比對我們都應該不陌生，我們經常使用的正規表達式就是一種模式比對。

• 正規表達式是一種“模式（pattern）”，
• 程式設計語言提供的“正規表達式引擎”就是Pattern Matcher。比如python中的re子產品。
• 首先輸入“知識”：re.compile(r'string')，
• 然後就可以讓其比對（match）事實（字元串）。
• 最後通過正規表達式引擎可以得到比對後的結果。

對于規則比對，通常定義如下：

• 條件部分，也稱為LHS(left-hand side)
• 事實部分，也稱為RHS(right-hand side)

假設系統中有N條規則，平均每個規則的條件部分有P個模式，在某個時點有M個事實需要處理。則規則比對要做的事情就是： 對每一個規則r，判斷目前的事實o是否滿足LHS(r)=True,如果滿足，則将規則r的執行個體r(o)，即規則+滿足該規則的事實，加到沖突集中等待處理。 通常采取如下過程：

1. 從N條規則中取出一條r；
2. 從M個事實中取出P個事實的一個組合c；
3. 用c測試LHS(r)，如果LHS(r（c）)=True，将RHS(r（c）)加入隊列中；
4. 如果M個事實還存在其他的組合c，goto 3；
5. 取出下一條規則r，goto 2；

實際的問題可能更複雜，在規則的執行過程中可能會改變RHS的資料，進而使得已經比對的規則執行個體失效或者産生新的滿足規則的比對，形成一種“動态”的比對鍊。

2.2 模式比對算法

上面的處理由于涉及到組合，過程很複雜。有必要通過特定的算法優化比對的效率。目前常見的模式比對算法包括Rete、Treat、Leaps，HAL，Matchbox等。

為了友善，将前面的圖仍然放在這裡：

2.2.1 Rete算法

Rete算法是目前使用最廣泛的規則比對算法，由Charles L. Forgy博士在1979年發明。Rete算法是一種快速的Forward-Chaining推理算法，其比對速度與規則的數量無關。 Rete的高效率主要來自兩個重要的假設：

1. 時間備援性。 facts在推理過程中的變化是緩慢的, 即在每個執行周期中,隻有少數的facts發生變化，是以影響到的規則也隻占很小的比例。是以可以隻考慮每個執行周期中已經比對的facts.
2. 結構相似性。許多規則常常包含類似的模式和模式組。

Rete算法的基本思想是儲存過去比對過程中留下的全部資訊,以空間代價來換取執行效率 。對每一個模式 ,附加一個比對元素表來記錄WorkingMemory中所有能與之比對的元素。當一個新元素加入到WorkingMemory時, 找出所有能與之比對的模式, 并将該元素加入到比對元素表中; 當一個無素從WorkingMemory中删除時,同樣找出所有與該元素比對的模式,并将元素從比對元素表中删除。 Rete算法接受對工作存儲器的修改操作描述 ,産生一個修改沖突集的動作 。

Rete算法的步驟如下：

1. 将初始資料（fact）輸入Working Memory。
2. 使用Pattern Matcher比較規則（rule）和資料（fact）。
3. 如果執行規則存在沖突（conflict），即同時激活了多個規則，将沖突的規則放入沖突集合。
4. 解決沖突，将激活的規則按順序放入Agenda。
5. 使用規則引擎執行Agenda中的規則。重複步驟2至5，直到執行完畢所有Agenda中的規則。

2.2.2 Tread算法

在 Rete算法中 ,同一規則連接配接結點上的寄存器保留了大量的備援結果。實際上, 寄存器中大部分資訊已經展現在沖突集的規則執行個體中。是以 ,如果在部分比對過程中直接使用沖突集來限制模式之間的變量限制,不僅可以減少寄存器的數量 ,而且能夠加快比對處理效率 。這一思想稱為 沖突集支撐政策 。

考慮增删事實對比對過程的影響，當向工作存儲器增加一個事實時 ,沖突集中已有的規則執行個體仍然保留,隻是将與該事實比對的規則執行個體加入到沖突集中; 當從工作存儲器删去一個事實時，不可能有新的規則執行個體産生, 隻是将 包含該事實的規則執行個體從沖突集中删去。

基于沖突集支撐政策和上述觀察, Treat算法放棄了Rete算法中利用寄存器儲存模式之間變量限制中間結果的思想,對于每一個模式 ,除保留原有 a寄存器的外 ,增加兩個新鍊來記錄與該模式比對的增删事實,一個叫做增鍊 (addlist),另一個叫做删鍊 (deletelist)。當修改描述的操作符為 “+”時,臨時執行部分連接配接任務;當修改描述的操作符為 “一”時,直接删去沖突集中包含該事實的規則執行個體。

Treat算法的步驟如下：

1. 行動 :根據點火規則的 RHS,生成修改描述表 CHANGES;
2. 模式比對:置每一模式的删鍊和增鍊為空,對 CHANGES的每一個修改描述 ,執行模式比對。對于與修改描述中的事實比對成功的模式,若修改描述的操作符為 “+”, 将該事實加入這一模式的增鍊;若修改描述的操作符為 “一”,将該事實加入這一模式的 删鍊。
3. 删去事實的處理:對于任一模式鍊中的每一個事實,找到沖突集中所有包含該事實 的規則執行個體,并将這一規則執行個體從沖突集中删去。相應地修改該模式的 a寄存器 。
4. 新增事實的處理:對 于 每 一 模 式 ,若 其 增 鍊 非 空 ,則 将 增 鍊 中 的 所 有 事 實 加 入 該 模 式的a寄存器 ,并對與新增事實相關的每一條規則臨時執行部分比對,尋找該規則新的實 例。具體做法為:首先将第一個模式增鍊中的事實集合與後一模式的 a寄存器進行連接配接 , 再将部分連接配接結果與第三個模式的a寄存器進行連接配接 ,一直到所有模式均連接配接完成為止。 其中 ,a寄存器 的内容包括新增 事實。若連接配接結果非空 ,則将找到 的規則 執行個體插入到沖突 集中。

2.2.3 Leaps 算法

前向推理引擎，包括LEAPS，都包括了比對-選擇-執行（match-select-action）循環。即，确定可以比對的規則，選擇某個比對的元 組，此元組相應的規則動作被執行。重複這一過程，直到某一狀态（如沒有更多的規則動作）。RETE和TREAT比對算法速度慢的原因是，它們把滿足規則條 件的元組都執行個體化。Leaps算法的最大的改進就是使用一種"lazy"的方法來評估條件（conditions），即僅當必要時才進行元組的執行個體化。這 一改進極大的減少了前向推理引擎的時空複雜度，極大提高了規則執行速度。

Leaps算法将所有的 asserted 的 facts ，按照其被 asserted 在 Working Memory 中的順序（ FIFO ），放在主堆棧中。它一個個的檢查 facts ，通過疊代比對 data type 的 facts 集合來找出每一個相關規則的比對。當一個比對的資料被發現時，系統記住此時的疊代位置以備待會的繼續疊代，并且激發規則結果（ consequence ）。當結果（ consequence ）執行完成以後，系統就會繼續處理處于主堆棧頂部的 fact 。如此反複。

Leaps算法的效率可以比Rete算法和Tread算法高幾個數量級。

2.2.4 其他算法

對于HAL算法和Matchbox算法，使用的範圍不是很廣，這裡不做過多的介紹。