本記事では、Reteアルゴリズムについて調べたことをまとめていきます。
Reteアルゴリズムとは
計算機科学者であるCharles L. Forgy氏が考案したパターンマッチングアルゴリズムです。
以下の手続きを効率的に行うことができます。
- Inputデータが特定の規則(ルール)に合致しているかの照合
- ルール条件に合致するデータに対して、ルールで定められた処理の実行
過去に記事で紹介しているDroolsをはじめ、多くのルールエンジンの基盤となっているアルゴリズムです。
処理の流れ
Reteアルゴリズムの処理の中には、主に以下のような要素が登場します。
| 要素 | 説明 |
|---|---|
| working memory(WM) | ルールへのInputデータや、ルールによって生成されたデータが保管される場所 |
| rete network | ルールの条件をもとに作成されるネットワーク 後述するrete node, type nodeなどから構成される |
| rete node | root nodeとも称される アルゴリズムにおいて、一番最初にデータが渡されるnode |
| type node | rete nodeの次にデータが渡されるnode データの型に応じてどのtype nodeに送信されるかが決定される |
| alpha node | データの属性値を何らかの定数値と照合するnode 条件に合致するデータのみを次のnodeに送信する |
| beta node | 二つのデータの属性値を照合するnode 条件に合致するデータのみを次のnodeに送信する |
| terminal node | すべてのbeta nodeの条件に合致するデータが最終的に送信されるnode ここに到達したデータはルールのすべての条件を満たしたことになる |
| agenda | terminal nodeに送られたデータと、データが満たすルールの情報が保管される場所 agenda上の(データ・ルール)の組み合わせに対して、順次ルールで定義したアクションが実行される |
具体例を交えて、データとルール条件との照合がどのように行われるかみていきます。
題材としては、顧客と注文データをもとに、クレジットカードのポイントが付与される簡単なルールを取り上げます。
| ルール名 | 顧客 | 注文.顧客名 | 注文.決済方式 | ポイント |
|---|---|---|---|---|
| カード払いであれば10ポイント付与 | 〇 | ==顧客.名前 | =="カード払い" | 10 pt |
上記決定表では、注文が顧客に紐づくもので、決済方式がカード払いだった場合、10ポイントを付与するルールとなっています。
このルールは、以下のようなrete networkで表現されます。
-
WMに保存された「注文」と「顧客」データがrete nodeに送信されます
-
注文データは注文用のtype node(画像左側)に、顧客データは顧客用のtype node(画像右側)に渡されます
-
alpha nodeに到達した注文データに対して、決済方式の条件をみたしているかチェックします
カード払いでないデータは、次のnodeに渡されることはありません -
alpha nodeの条件をみたした注文データと、顧客データはbeta nodeに到達します
ここで、注文データが顧客に紐づくものであることをチェックします -
beta nodeのルール条件をみたす注文・顧客データは、terminal nodeに渡されます
-
terminal node に到達した注文・顧客データと、ルールの情報がagendaに保存され、ルールのアクション(10ptのポイント生成)が実行されます
Reteネットワーク上では、以下の操作をすることで、無駄なデータ⇔ルールの照合が発生しにくくなっています。
(A) データ型に応じたtype nodeへのデータ振り分け
(B) 各nodeにおける、ルール条件によるチェックと、後続のnodeへの送信判断
Droolsでの利用
Droolsでは、Reteアルゴリズムの性能を改善したPhreakアルゴリズムというものが利用されているようです。
今後こちらについても紹介できたらと思います。
※ 実装されているのは、おそらくこのあたりかと
参考