RETEアルゴリズム

Reteアルゴリズムとは、プロダクションシステム実装のための効率的なパターンマッチングアルゴリズムである。カーネギーメロン大学のチャールズ・フォーギーが設計したもので、1974年の論文で最初に公表し、1979年の学位論文や1982年の論文でさらに洗練された（参考文献参照）。数々のエキスパートシステムの基盤として使われており、[http://www.ilog.com/products/jrules/ JRules]、OPS5、CLIPS、Jess、[http://drools.org/ Drools]、Soar、[http://lisa.sourceforge.net/ LISA]、[http://www.microsoft.com/technet/prodtechnol/biztalk/biztalk2004/planning/business-rules-framework-overview.mspx Microsoft BizTalk Server におけるビジネスルールエンジン]、[http://www.tibco.com/software/complex_event_processing/businessevents/default.jsp TIBCO BusinessEvents] などがある。Rete とは、ラテン語の 'rete'（網、ネットワーク）が語源である。素朴なエキスパートシステムの実装では、知識ベース内の既知の事実と規則（ルール）群を順次照合し、適合するルールを実行していく。ルール群や知識ベースがそれほど大きくなくても、この素朴な方法では性能は期待できない。Reteアルゴリズムはより効率的なエキスパートシステムを実装する基盤を提供する。Reteに基づいたエキスパートシステムでは、ルールやデータの依存関係がノードのネットワークから構成される内部表現に置き換えられる。各ノードはルート（根）となるノード以外はルールの左辺部（Left Hand Side、LHS）に現われるパターンに対応している。ルートノードから末端ノードまでの経路が1つのルールの左辺全体を表す。各ノードにはそのパターンに適合した事実が記憶される。この構造は基本的にトライ木の応用である。新たな事実が表明されたり、事実が更新されると、それがネットワーク上を伝播していき、あるノードでパターンマッチする。1つまたは複数の事実によってルー