著者

松下 光範 馬野 元秀 鳩野逸生 田村 坦之

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.37, no.6, pp.988-997, 1996-06-15

---

Reteアルゴリズムをはじめとする従来のプロダクション・システムの高速化手法では ルールの条件部をデータフローネットワークに展開し 作業記憶要素をトークンとして流している.これらの高速化手法は有効であるが 作業記憶の更新が頻繁に起こるような場合には そのネットワーク中の定数をテストするノードにおいてまだ無駄な処理を行っている.そこでこの無駄な処理を解消するために マッチング候補の概念を用いたデータフローネットワークによる高速推論アルゴリズムを提案する.このネットワークでは Reteネットワークでは定数をテストするノードとして同一に扱われているノードをパターン間テストノードとパターン内テストノードに分類して それらの間にマッチング候補メモリノードを持つことで 無駄な処理を行うことを従来手法に比べて少なくすることができる. また マッチする作業記憶要素と条件パターンの組を少ない比較回数で特定するために ID3決定木作成アルゴリズムの考え方を用いたパターン間テストノード作成アルゴリズムを提案する.Some fast pattern matching algorithms have been proposed to improve the reasoning speed of production systems. In almost all of these methods, rule conditions are represented in a data-flow network and elements in a working memory flow through this network as tokens. These algorithms are effective, however, excessive constant testing still cannot be avoided for instances when the working memory must be frequently updated. This paper proposes a fast pattern matching algorithm for a production system. It uses an improved reasoning network employing matched candidates to circumvent such constant testing which is inherent in conventional networks. Using an example conventional network, the Rete network, we classify constant-test nodes into inter-pattern test nodes and intra-pattern test nodes. Then we introduce memory nodes for matching candidates between these test node classes. This is done in order to find unnecessary matching patterns more quickly. The ID3 algorithm is used to make an efficient inter-pattern test network which is capable of finding patterns in the rule conditions for the working memory element. This algorithm is implemented in Austin Kyoto Common Lisp (AKCL) and is applied to several rule bases with good results.