Reteアルゴリズム

Reteアルゴリズムとは、プロダクションシステム実装のための効率的なパターンマッチングアルゴリズムである。カーネギーメロン大学のチャールズ・フォーギーが設計したもので、1974年の論文で最初に公表し、1979年の学位論文や1982年の論文でさらに洗練された（参照）。数々のエキスパートシステムの基盤として使われており、JRules、、CLIPS、Jess、Drools、Soar、LISA、Microsoft BizTalk Server におけるビジネスルールエンジン、TIBCO BusinessEvents などがある。Rete とは、ラテン語の 'rete'（網、ネットワーク）が語源である。 素朴なエキスパートシステムの実装では、知識ベース内の既知の事実と規則（ルール）群を順次照合し、適合するルールを実行していく。ルール群や知識ベースがそれほど大きくなくても、この素朴な方法では性能は期待できない。 Reteアルゴリズムはより効率的なエキスパートシステムを実装する基盤を提供する。Reteに基づいたエキスパートシステムでは、ルールやデータの依存関係がノードのネットワークから構成される内部表現に置き換えられる。各ノードはルート（根）となるノード以外はルールの左辺部（LHS）に現われるパターンに対応している。ルートノードから末端ノードまでの経路が1つのルールの左辺全体を表す。各ノードにはそのパターンに適合した事実が記憶される。この構造は基本的にトライ木の応用である。 新たな事実が表明されたり、事実が更新されると、それがネットワーク上を伝播していき、あるノードでパターンマッチする。1つまたは複数の事実によってルールの左辺のパターン全てにマッチした場合、その規則を表す経路の末端ノードに到達し、そのルールの右辺部（RHS）が起動される。 Reteアルゴリズムは高速化のためにメモリを消費する設計となっている。Reteの性能は理論的にはシステム内のルール数に依存し、非常に大規模なエキスパートシステムではReteアルゴリズムによるメモリ枯渇問題が発生しやすい。これを解決すべく、Reteアルゴリズムの改良版や他のアルゴリズムが考案されてきた。