[發(fā)明專利]一種規(guī)則引擎的模式匹配方法和RETE網(wǎng)絡(luò)

有效

• 申請?zhí)枺?/td>: 201110098097.0
• 申請日: 2011-04-19
• 公開（公告）號: CN102170360A
• 公開（公告）日: 2011-08-31
• 發(fā)明（設(shè)計）人: 李曉靜
• 申請（專利權(quán)）人: 北京神州數(shù)碼思特奇信息技術(shù)股份有限公司
• 主分類號: H04L12/14
• 分類號: H04L12/14;H04L12/24
• 代理公司: 北京輕創(chuàng)知識產(chǎn)權(quán)代理有限公司 11212
• 代理人: 楊立

技術(shù)領(lǐng)域

本發(fā)明涉及電信行業(yè)中的內(nèi)容計費(fèi)過程，具體來說是一種用于內(nèi)容計費(fèi)的規(guī)則引擎模式匹配方法和RETE網(wǎng)絡(luò)。

背景技術(shù)

復(fù)雜企業(yè)級項目的開發(fā)和維護(hù)面臨著軟件必須“隨需而變”的問題。由于隨外部條件和需求經(jīng)常變動的商業(yè)決策和業(yè)務(wù)邏輯被固化在代碼中，這使得軟件的開發(fā)和維護(hù)變得異常困難，耗費(fèi)大量的時間和成本，因此迫切需要分離商業(yè)決策者的商業(yè)決策邏輯和應(yīng)用開發(fā)者的技術(shù)決策，并把這些商業(yè)決策放在中心數(shù)據(jù)庫或其他統(tǒng)一的地方，讓它們能在運(yùn)行時可以動態(tài)地管理和修改，從而提高軟件系統(tǒng)的柔性和適應(yīng)性。規(guī)則引擎正是應(yīng)用于上述動態(tài)環(huán)境中的一種解決方法，它增加了軟件的可維護(hù)性，為軟件提供可供用戶直接修改業(yè)務(wù)邏輯的功能，使得軟件項目不會因為維護(hù)成本太高而最后虧本。

規(guī)則引擎(Rule?Engine)由推理引擎發(fā)展而來，是一種嵌入在應(yīng)用程序中的組件，實(shí)現(xiàn)了將業(yè)務(wù)決策從應(yīng)用程序代碼中分離出來，并使用預(yù)定義的語義模塊編寫業(yè)務(wù)決策。規(guī)則引擎接受數(shù)據(jù)輸入，解釋業(yè)務(wù)規(guī)則，并根據(jù)規(guī)則做出業(yè)務(wù)決策。

RETE算法是Charles?Forgy博士于1979年提出的一種效率很高的模式匹配算法，廣泛應(yīng)用于各種規(guī)則引擎中，其核心思想是將分離的匹配項根據(jù)內(nèi)容動態(tài)構(gòu)造匹配樹，以達(dá)到顯著降低計算量的效果。

對于內(nèi)容計費(fèi)來說，實(shí)際上是針對“內(nèi)容產(chǎn)品”展開的計費(fèi)。內(nèi)容計費(fèi)業(yè)務(wù)種類多，而且計費(fèi)規(guī)則經(jīng)常變動，系統(tǒng)維護(hù)困難。因此需要將規(guī)則引擎應(yīng)用在內(nèi)容計費(fèi)上，把計費(fèi)規(guī)則從代碼中分離，用規(guī)則引擎進(jìn)行管理。

現(xiàn)有的RETE算法是這樣的：規(guī)則引擎的RETE算法子系統(tǒng)根據(jù)編譯子系統(tǒng)生成的規(guī)則包，構(gòu)建RETE網(wǎng)絡(luò)。當(dāng)有事實(shí)插入（Insert）時，生成事實(shí)句柄FactHandle，然后在RETE網(wǎng)絡(luò)中與各節(jié)點(diǎn)匹配，同時會在匹配成功的每個節(jié)點(diǎn)對應(yīng)的內(nèi)存中保存該事實(shí)信息；在匹配之后要撤銷（Retract）每個事實(shí)句柄，來刪除在RETE網(wǎng)絡(luò)中進(jìn)行匹配時記錄的所有事實(shí)信息。這樣，會占用很多內(nèi)存來記錄事實(shí)信息，匹配過程也的時間開銷也很大，在匹配完執(zhí)行規(guī)則之后，還要花費(fèi)時間Retract事實(shí)來刪除匹配過程中在RETE網(wǎng)絡(luò)中留下的事實(shí)記錄。這樣必然導(dǎo)致使用規(guī)則引擎的運(yùn)算過程要比把規(guī)則直接固化到代碼中的系統(tǒng)運(yùn)算速度慢得多。

因此，使用現(xiàn)有的規(guī)則引擎存在著性能上的問題。規(guī)則引擎的核心算法是RETE算法，由于該算法中，事實(shí)匹配規(guī)則的過程不一定獨(dú)立，多個事實(shí)同時滿足某個條件時才執(zhí)行該條規(guī)則所對應(yīng)的動作，原RETE算法在插入事實(shí)的過程中在RETE網(wǎng)絡(luò)中保存了所有事實(shí)的信息，這樣就使得該算法建網(wǎng)匹配過程復(fù)雜，并且占用大量的內(nèi)存空間，使得應(yīng)用規(guī)則引擎的系統(tǒng)性能大大低于將業(yè)務(wù)邏輯固定在代碼中的系統(tǒng)，從而使得規(guī)則引擎無法在計費(fèi)系統(tǒng)中進(jìn)行廣泛的應(yīng)用。

發(fā)明內(nèi)容

本發(fā)明所要解決的技術(shù)問題是提供一種改進(jìn)的規(guī)則引擎模式匹配方法，使其在兼容現(xiàn)有RETE算法的同時，使應(yīng)用改進(jìn)后的規(guī)則引擎的內(nèi)容計費(fèi)系統(tǒng)的處理效率接近原內(nèi)容計費(fèi)系統(tǒng)。

本發(fā)明解決上述技術(shù)問題的技術(shù)方案如下：

一種用于規(guī)則引擎的模式匹配方法，包括以下步驟：

步驟1：構(gòu)建RETE網(wǎng)絡(luò)，所述RETE網(wǎng)絡(luò)中包含一RETE節(jié)點(diǎn)，所述RETE節(jié)點(diǎn)下僅有一個對象類型節(jié)點(diǎn)（ObjectTypeNode節(jié)點(diǎn)），所述對象類型節(jié)點(diǎn)下有AlphaNode節(jié)點(diǎn)、EvalNode節(jié)點(diǎn)、LeftInputAdapterNode節(jié)點(diǎn)（左輸入適配節(jié)點(diǎn)）和TerminalNode節(jié)點(diǎn)（終止節(jié)點(diǎn)）；

步驟2：插入事實(shí)，并直接在所述RETE網(wǎng)絡(luò)中進(jìn)行條件匹配，不生成所述事實(shí)的事實(shí)句柄，不保存所述事實(shí)的信息；

步驟3：將所匹配的規(guī)則放入一優(yōu)先級隊列，并順序執(zhí)行。

其中，事實(shí)即為數(shù)據(jù)，是指用戶插入的、符合規(guī)則引擎中用戶定義的事實(shí)類的對象。比如，本發(fā)明中提到的應(yīng)用規(guī)則引擎后的內(nèi)容計費(fèi)系統(tǒng)中，用戶訂購關(guān)系數(shù)據(jù)即是事實(shí)。

RETE節(jié)點(diǎn)為RETE網(wǎng)絡(luò)的根節(jié)點(diǎn)，為整個RETE網(wǎng)絡(luò)的入口。

對象類型節(jié)點(diǎn)的作用是提供對對象所屬類進(jìn)行篩選，根據(jù)內(nèi)容計費(fèi)的具體需要，本發(fā)明中只定義了一種對象類型節(jié)點(diǎn)。

AlphaNode節(jié)點(diǎn)用來提供對象屬性值的篩選，即評估對象的字面條件（literal?conditions），當(dāng)一個對象有多個字面條件的話，逐條評估順序進(jìn)入相應(yīng)AlphaNode節(jié)點(diǎn)。

LeftInputAdapterNode節(jié)點(diǎn)用于提供事實(shí)到元組的轉(zhuǎn)換。