|
Reteアルゴリズムとは、プロダクションシステム実装のための効率的なパターンマッチングアルゴリズムである。カーネギーメロン大学のチャールズ・フォーギーが設計したもので、1974年の論文で最初に公表し、1979年の学位論文や1982年の論文でさらに洗練された（参考文献参照）。数々のエキスパートシステムの基盤として使われており、JRules 、OPS5、CLIPS、Jess、Drools 、Soar、LISA 、Microsoft BizTalk Server におけるビジネスルールエンジン 、TIBCO BusinessEvents などがある。Rete とは、ラテン語の 'rete'（網、ネットワーク）が語源である。 素朴なエキスパートシステムの実装では、知識ベース内の既知の事実と規則（ルール）群を順次照合し、適合するルールを実行していく。ルール群や知識ベースがそれほど大きくなくても、この素朴な方法では性能は期待できない。 Reteアルゴリズムはより効率的なエキスパートシステムを実装する基盤を提供する。Reteに基づいたエキスパートシステムでは、ルールやデータの依存関係がノードのネットワークから構成される内部表現に置き換えられる。各ノードはルート（根）となるノード以外はルールの左辺部（Left Hand Side、LHS）に現われるパターンに対応している。ルートノードから末端ノードまでの経路が1つのルールの左辺全体を表す。各ノードにはそのパターンに適合した事実が記憶される。この構造は基本的にトライ木の応用である。 新たな事実が表明されたり、事実が更新されると、それがネットワーク上を伝播していき、あるノードでパターンマッチする。1つまたは複数の事実によってルールの左辺のパターン全てにマッチした場合、その規則を表す経路の末端ノードに到達し、そのルールの右辺部（Right Hand Side、RHS）が起動される。 Reteアルゴリズムは高速化のためにメモリを消費する設計となっている。Reteの性能は理論的にはシステム内のルール数に依存し、非常に大規模なエキスパートシステムではReteアルゴリズムによるメモリ枯渇問題が発生しやすい。これを解決すべく、Reteアルゴリズムの改良版や他のアルゴリズムが考案されてきた。 == 概要 == Reteアルゴリズムは、プロダクションシステムでのデータタプル（事実）とプロダクション（ルール）のパターンマッチ機能の実装を論理的に一般化したものである。プロダクションは1つ以上の条件とそれら条件に適合する事実群が揃ったときに実行されるアクション群で構成される。条件群は事実の属性（型指定や識別子など）に関するものである。Reteアルゴリズムには次のような特徴がある: * ノード共有によってある程度の冗長性を排除する。 * 異なる型の事実群の結合について、部分的なマッチングを保持する。つまり、プロダクションシステムのワーキングメモリに何らかの変化があったとき、全事実を再度評価しなおす必要がなく、変化した部分だけを再評価する。 * ワーキングメモリ上からある事実が排除された場合、関連するメモリ内容を効率的に消去できる。 Reteアルゴリズムは、前向き連鎖型のパターンマッチ・エンジン（推論エンジン）の実装方式として広く使われている。 Rete でのルール群は概念的には有向非輪状グラフとなっている。ルール群はメモリ上に格納されたネットワークで表現されるのが一般的である。このネットワークがルールの条件（パターン）と事実（データタプル）のパターンマッチを行う。Reteネットワークは一種のクエリプロセッサのように働き、関係代数の「射影」、「選択」、「結合」などの操作をデータタプルに対して必要に応じて行う。 プロダクション（ルール）は、アナリストやソフトウェア開発者が高レベルなルール記述言語を使って作成する。それをルール群として集め、（多くの場合実行時に）変換して使用する。 事実がワーキングメモリ上に「表明」されると、エンジンは「ワーキングメモリ・エレメント」(WME)を各事実に対応させて生成する。事実はタプルであり、その中に任意個のデータが含まれている。各 WME はそのタプル全体を格納するか、WME が格納できるタプルのサイズが固定の場合、タプルを複数の WME 群で表現する。後者の場合、タプルはトリプレット（3-タプル）であることが多い。 各 WME はReteネットワークの唯一のルートノードから投入される。ルートノードは WME を子ノードに渡していき、さらにその WME がネットワーク上を転送されていく。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Reteアルゴリズムとは、プロダクションシステム実装のための効率的なパターンマッチングアルゴリズムである。カーネギーメロン大学のチャールズ・フォーギーが設計したもので、1974年の論文で最初に公表し、1979年の学位論文や1982年の論文でさらに洗練された（参考文献参照）。数々のエキスパートシステムの基盤として使われており、JRules 、OPS5、CLIPS、Jess、Drools 、Soar、LISA 、Microsoft BizTalk Server におけるビジネスルールエンジン 、TIBCO BusinessEvents などがある。Rete とは、ラテン語の 'rete'（網、ネットワーク）が語源である。素朴なエキスパートシステムの実装では、知識ベース内の既知の事実と規則（ルール）群を順次照合し、適合するルールを実行していく。ルール群や知識ベースがそれほど大きくなくても、この素朴な方法では性能は期待できない。Reteアルゴリズムはより効率的なエキスパートシステムを実装する基盤を提供する。Reteに基づいたエキスパートシステムでは、ルールやデータの依存関係がノードのネットワークから構成される内部表現に置き換えられる。各ノードはルート（根）となるノード以外はルールの左辺部（Left Hand Side、LHS）に現われるパターンに対応している。ルートノードから末端ノードまでの経路が1つのルールの左辺全体を表す。各ノードにはそのパターンに適合した事実が記憶される。この構造は基本的にトライ木の応用である。新たな事実が表明されたり、事実が更新されると、それがネットワーク上を伝播していき、あるノードでパターンマッチする。1つまたは複数の事実によってルールの左辺のパターン全てにマッチした場合、その規則を表す経路の末端ノードに到達し、そのルールの右辺部（Right Hand Side、RHS）が起動される。Reteアルゴリズムは高速化のためにメモリを消費する設計となっている。Reteの性能は理論的にはシステム内のルール数に依存し、非常に大規模なエキスパートシステムではReteアルゴリズムによるメモリ枯渇問題が発生しやすい。これを解決すべく、Reteアルゴリズムの改良版や他のアルゴリズムが考案されてきた。== 概要 ==Reteアルゴリズムは、プロダクションシステムでのデータタプル（事実）とプロダクション（ルール）のパターンマッチ機能の実装を論理的に一般化したものである。プロダクションは1つ以上の条件とそれら条件に適合する事実群が揃ったときに実行されるアクション群で構成される。条件群は事実の属性（型指定や識別子など）に関するものである。Reteアルゴリズムには次のような特徴がある:* ノード共有によってある程度の冗長性を排除する。* 異なる型の事実群の結合について、部分的なマッチングを保持する。つまり、プロダクションシステムのワーキングメモリに何らかの変化があったとき、全事実を再度評価しなおす必要がなく、変化した部分だけを再評価する。* ワーキングメモリ上からある事実が排除された場合、関連するメモリ内容を効率的に消去できる。Reteアルゴリズムは、前向き連鎖型のパターンマッチ・エンジン（推論エンジン）の実装方式として広く使われている。Rete でのルール群は概念的には有向非輪状グラフとなっている。ルール群はメモリ上に格納されたネットワークで表現されるのが一般的である。このネットワークがルールの条件（パターン）と事実（データタプル）のパターンマッチを行う。Reteネットワークは一種のクエリプロセッサのように働き、関係代数の「射影」、「選択」、「結合」などの操作をデータタプルに対して必要に応じて行う。プロダクション（ルール）は、アナリストやソフトウェア開発者が高レベルなルール記述言語を使って作成する。それをルール群として集め、（多くの場合実行時に）変換して使用する。事実がワーキングメモリ上に「表明」されると、エンジンは「ワーキングメモリ・エレメント」(WME)を各事実に対応させて生成する。事実はタプルであり、その中に任意個のデータが含まれている。各 WME はそのタプル全体を格納するか、WME が格納できるタプルのサイズが固定の場合、タプルを複数の WME 群で表現する。後者の場合、タプルはトリプレット（3-タプル）であることが多い。各 WME はReteネットワークの唯一のルートノードから投入される。ルートノードは WME を子ノードに渡していき、さらにその WME がネットワーク上を転送されていく。」の詳細全文を読む スポンサード リンク
|