JPS6072031A

JPS6072031A - 計算機システムの高速処理方式

Info

Publication number: JPS6072031A
Application number: JP58177955A
Authority: JP
Inventors: Setsuo Tsuruta; 節夫鶴田; Shoji Miyamoto; 宮本　捷二; Makoto Nomi; 能見　誠
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 1983-09-28
Filing date: 1983-09-28
Publication date: 1985-04-24
Anticipated expiration: 2009-03-02
Also published as: JPH0616266B2

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】〔発明の利用分野〕本発明は、経験則や自然の法則と初期事実から新事実や
仮説を推論する（プロダクション）システムの高速制御
方式に係わり、特に、大規模で時間がかかりすぎたり、
リアルタイム性を要求される場合に好適な、高速推論の
だめの計算機システムの高速処理方式に関する。

〔発明の背景〕

規則と事実から推論を行なうのに、推論の各サイクル毎
に全ての規則と事実の照合をとって実行規則を決めるの
がプロダクションシステムであるが、規則と事実の増大
と共に推論時間が爆発的に増大し実用規模では有用でな
い。これを防止するだめ、規則や事実のコード化とその
インデキシングを行なっている。特に、弁別ネットを用
いた高速方式が効率・適用性において優れているが、規
則の各項目によっては弁別ネットのオーツくヘッドは大
きく、リアルタイムシステムへの実用化上問題がある。

〔発明の目的〕

経験則や自然法則などのルールをプロダクションメモリ
に、事実や仮説をワーキングメモリに持ち、条件部の内
容がワーキングメモリに存在するルールを順次適用する
ことにより計算機に推論を行ワスプロダクションシステ
ムが存在する。本発明の目的はプロダクションシステム
の推論速度を、実用上充分高速に、しかも、従来のよう
にルールや条件の数、事実数に依存しない処理方式を提
供することにある。

〔発明の概要〕

規則の条件部と結論部を調べて、どの条件が成立すると
どの規則が起動され、結論部の実行により、どの規則の
条件が新たに成立したシネ成立になったりするのかの関
係をネットワーク構造にして登録しておく。ただし、規
則に変数を含む場合の処理を行うために、変数の具体値
によシ照合する可能性のある条件項と結論部をグループ
化し、その代表を連想環とし、連想環の個別部により事
実を貯えるようにし、連想環を核に上記ネットワークを
構成した。

〔発明の実施例〕

以下、本発明の一実施例を、ＭＥ　１〜第１５図により
説明する。

第１Ａ図は、本発明の方式を実現するだめのシステム構
成である。

連想ネット作成プロセッサ１００は、規則ファイル１０
３から、規則を取出し、規則の起動条件やその起動が他
の規則の起動や推論に及ぼす影響を分析し、その結果を
連想ネット（但し、事実組込み前のもの）１０６として
出力する。また、初期事実を連想ネットに効率良く組込
むための連想フィルタ１０５を作成する。初期事実組込
みプロセッサ１０１は、初期事実ファイル１０４から事
実を取出し、連想ネット１０６の該当場所に組込む。推
論実行プロセッサ１０２は、連想ネット１０６をベース
に、高速推論を行ない推論結果１０７を出力する。

第１Ｂ図は、本発明の方式の計算機システム上での実現
構成図である。

連想ネット作成プロセッサ１００１初期事実組０２込みプロセッサ１０１、推論実行プロセッサ、連想フィ
ルタ１０５は、推論プログラム１５１として、また、連
想ネット１０６は推論用知識１５２として、それぞれＣ
ＰＵ　１５０に置かれる。

コンソールディスプレー１５３（キーボード。

コンソールタイプライタでも良い）から、規則や初期事
実を入力する。実際のシステムでは、初期事実の入力は
、センサーにども用いることも可能である。推論の実行
（あるいは連想ネット１０６の作成など推論の準備）な
ど推論制御指令１６（Ｊもコンソールディスプレー１５
３から入力する。

推論結果は、（ライン）プリンタ１５４やＣＢ、Ｔ１５
５、あるいは、ディスクやＭ／Ｔなどの補助記憶装置１
５６に出力する。推論制御指令１６０　・により、推論
結果に至るまでの推論経過の出力も可能である。

補助記憶装置１５６には、規則ファイル１０３、初期事
実ファイル１０４、連想ネット１０６を保存し、エラー
回復や前処理に利用できる。

第２図は高速に推論を実行するだめの連想ネット１０６
の構成を示す。

２００は、規則のリストであり、その要素２０１はコー
ド化された規則２１０であり、条件部２１１と行動部２
１２から成る。条件部、行動部の各項２２０もコード化
されており、それぞれ条件項２１３、行動部２１５〜２
１７から構成される。

行動部は、さらに、削除項２１５、追加項２１６、停止
項２１７などに分れる。

上記の各項２２０は、項コード２２１、項を条件部に持
つ規則（連想規則２５１）のリスト２５０を値として持
つ規則連想属性２２２、共通の型の項（連想項２４５）
のリスト（連想項リス）２４４）を、値として持つ項連
想属性２２３、連想項間の共通部２３０を値として持つ
共通部属性２２４、個別な部分（個別構造２４０その要
素は個別要素２４３）を値として持つ個別部属性２２５
、項が既知事実かどうかを示す事実属性２２６項が含む
変数（関数でも良い。以後同様）２４２を順番に並べた
変数列２４１を値に持つ変数属性２２７、項の内容２４
６（その要素音２４７に示す。）を値として持つ内容層
性２２８、から構成される。

具体値（列）す・スト２４８は、項の変数の具体値の列
（具体値列２４９）のリストであり、項が変数２４２を
含む時の事実属性２２６の値である。

共通部２３０は、そのコード２３５と、その内容である
共通構造（その要素である共通要素２３４は、項の要素
のうちの個別要素２４３に対応するものを−”（アンダ
ーライン）に変換し、他の項の要素はそのままにしたも
の）２３３を匝として持つ構造属性２３１と、この共通
部を持つすべての項（共通部コード２３６）のリストで
ある共通部コードリスト２３５を直として持つ連想項属
性２３２とから成る。

候補規則リスト２６０は、（実行）候補規則２６１のリ
ストである。

第３図は、コードリストのデータ構造を示す。

すなわち、コード化した項２２０を登録するコードリス
ト３００は、項の内容２２１と対応するコード２４６か
ら成るコードベア３０１を要素とするリストである。項
のコード化（後述。ブロック６０２）に用いる。

第４図は、連想ネット共通部のデータ構造である。本デ
ータ構造は、連想ネット共通部作成（ブロック６０３゜
後述）の途中段１者のものである。

すなわち共通部候補４０１は、共通部の候補であり、連
想ネット共通部作成処理終了時点以降は、共通部２３０
と一致する。同様に、共通部リスト４００は、共通部コ
ードは共通部候補４０１、作成後は共通部２３０を要素
とするリストである。

共通部コード４０２、構造属性４０３、項連想属性４０
４、共通要素４０６、連想項リスト４０５も、共通部候
補に関するものであることを除いては、第２図で説明し
た共通部に関するそれらと同様である。

第５図は、連想フィルタ１０５の構成を示す。

連想フィルタは、初期ノード（ノード爵号５０１が０の
ノード）から始まるノード５００のトリー構造体である
。各ノード５００は、ノード番号５０１、変数特徴属性
５０２、定数特徴属性５０３、終端属性５０４か・ら成
る。システムは、ノード上を動きながら、初期事実の要
素（定数、変数）を読み込むが、変数特徴属性５０２は
変数を読み込んだ時にシステムが動く先のノード次ノー
ド（５０７）を、定数特徴属性５０３は、どの定数５０
８を読み込んだら次ノード５０９がどのノードであるか
のペア５０６を要素とする表（定数特徴属性値５０５）
を、それぞれ値として持つ。終端属性５０４ば、ノード
５００が共通部リスト４００に登録された共通部のいず
れかをシステムが読み込んだ時、初期ノードから到達す
る先のノードである時、その共通部２３０の共通部コー
ド２３５を、そうでない時には空を値として持つ。

第６図は、連想ネット作成処理を示す。

まず、規則の項のうちその内容が記号列として互いに異
なるものにユニークな番号をつけるために、新コード番
号を１に、規則の項を取出すだめのポインタを１に初期
設定する（ブロック６００）。次に、規則ファイル１０
３から規則の項を取出すとともにポインタを更新する（
ブロック６０１）。取出した項は、照合の高速化のだめ
にコード化して、連想ネット］０６の規則２１０に埋込
むとともに、規則連想属性２２２を設定する（ブロック
６０２）。さらに、連想ネノｌ−１０６の共通部２３０
を作成する。以上の処理を規則ファイル１０３の全ての
規則の項に対して行なった後、連想ネツｌ−１０６の個
別構造２４０を作成する（ブロック６０４）。また、連
想フィルタ１０５を作成する（ブロック６０５）。

第７図は、項をコード化した規則２１０を作成し、規則
連想属性２２２を設定するだめの処理である。

ブロック７０１では、ブロック６０１で取出した規則の
項が、コードリス）３００に既登録かどうかをチェック
する。既登録なら、登録されている該コードを現コード
とする（ブロック７ｏ２）。

未登録なら、項の内容２４６と新コード番号のペア（コ
ードベア３０１）を、コードリスト３００に追加しくブ
ロック７０３）、現コード番号の値を新コード番号の値
に設定し、新コード番号を更新する（ブロック７０４）
。ブロック７０５では、現コード番号にユニークに対応
する環コード２２１を持つ項２２０の変数桿性２２７と
して、取出した項が含む変数２４２を先頭から順にリス
ト結合したもの（変数リス）２４１）を、内容属性２２
８として、項の′内容２４６を設定する。

さて、ブロック７０２あるいは、ブロック７０５の処理
が終了したら規則２１０の項２２０の環コード２２１を
現コードとし、条件部２１１、もしくは行動部２１２か
らネットワークを張って、連想ネット１０６の一部とす
る（ブロック７０６）。

さらに、処理中の項が、条件部２１３なら、その規則連
想属性２２２の値、つまり連想規則リスト２５０の要素
２５１として、１項が属する規則の規則コード２１４を
追加する。

第８図は、連想ネット１０６の項の共通部２３０を抽出
、作成するための処理フローである。

ブロック８０１では、ブロック６０１で取出した規則の
項の変数（関数を含む、以後同様）を−に変えたものを
（共通部）候補項４０１とする。

この候補項のコート責将来の共通部コード）４０２は、
たとえば、取出した項のコードがｆｉのときａｉとする
。次に、ブロック８０２では、候補項４０１０項連想属
性４０４として、上記の候補項のコード４０２を設定す
る。

さて、ブロック８０３では、（共通部）候補項４０１と
、共通部リスト４００に登録ずみの各候補項との照合を
とり、既登録かどうかのチェックを行なう。ただし、こ
の照合では、−はどの要素（定数、変数）とも照合が成
功するものとする。

既登録なら、まず、候補項と照合した共通部リスト内の
候補項の一以外の要素４０６のうち、候補項の−と照合
した要素を−に置替えたものを、改めて候補項とする。

この候補項のコードは、上記の照合した共通部リスト内
の候補項のコード４０２とする（ブロック８０４）。次
に、この新しい候補項の連想項リストに、もとの候補項
の連想項リストを結合する（ブロック８０６）。さらに
、もとの候補項と照合した共通部リスト内の候補項を共
１ｍ部リスト４００から削除する。ブロック８０３から
ブロック８０６までの処理を、ブロック８０３の処理結
果が既登録である間中くシ返し、結果が未登録になれば
、連想ネット１０６の共通部リスト４００に候補項４０
１を追加して（ブロック８０７）、ブロック６０１で取
出した項に対する共通部作成処理を終了する。

第９図は、連想ネット１０６のうち各項に個別な部分（
個別構造２４０）を、作成するだめの処理方式を示す。

共通部リスト４００の要素、つまり共通部２３０（以後
の処理では、共通部リストが確定しているので、（共通
部）候補項４０１は、すべて共通部２３０になる。）を
順次取出しくブロック９０１）、その項連想属性２２３
の値、つまり連想項リスト２４４をとシ出す（ブロック
９０２）。次に、その要素、つまり、共通部を共有する
連想項のグループ（連想グループ）のメンバーとなる項
（連想項２４５）を順次取出す（ブロック９０３）。

連想項リストの要素の取出しが全て終了すれば、ブロッ
ク９０１に戻って、共通部リスト４００から次の要素を
取出し、共通部リストの要素を全て取出すまで繰返し同
じ処理を行う。

さて、ブロック９０４では、取出した連想項９０４に対
して、共通部２３０の共洒構造２３３の要素２３４の値
が−である要素の共通構造内の相対位置にある連想項の
要素２４７を取出してリストにしたものを同連想項の個
別部属性２２６の値として、個別構造２４０に設定する
。次に、連想項の共通部属性２２４として、ブロック９
０１で取出した共通部２３０のコード２３５を設定しく
ブロック９０５）、ブロック９０３の処理に戻る。

第１０図は、初期事実１０４を連想ネット１０６に組込
むだめの連想フィルタ１０５を作成するための処理方式
を示す。

ブロック１００１では連想フィルタ１０５のノードに与
える番号（新ノード番号）を１に設定する。

次に、共通部リスト４００から順次、その要素２３５を
取出す（ブロック１００２　）。取出す要素がなくなれ
ば処理を終了する。取出す要素があれば、まず、現在の
ノードを出発ノード（例えば、番号０のノード）とする
（ブロック１００４）。次に、共通部２３０の要素２３
４を順次取出す（ブロック１００４）。ブロック１００
６では、取出した要素２３４が、−（変数に対応）かど
うかをチェックしくブロック１００６）、Ｙｅｓなら、
現在のノード５００の変数特徴属性５０２の値が空かど
うかを調らべ（ブロック１００７　）　、空なら、新ノ
ード番号を現ノードの変数特徴属性５０２として設定す
る（ブロック１００８）。空でなければ、変数特徴属性
５０２の値を現ノードとする゛（ブロック１０１０）。

ブロック１００６の処理結果がＮＯなら、ブロック１０
０４で取出した要素２３４が、現在のノード５００の定
数特徴属性５０２に含まれるかどうかをチェックしくブ
ロック１０１１）、含まれなければ、取出した要素２３
４と新ノード番号の対を現在のノードの定数特徴属性５
０３に追加しくブロック１０１２　）　、含まれれば、
マツチした定数特徴属性値５０５の要素５０６に対応す
るノード５０７を現在のノードとする。また、ブロック
１００８．１０１２の処理が終了すれば、ブロック１０
０９において、新ノード番号のノードを現ノードにし、
新ノード番号を更新する。ブロック１００９．１０１０
．１０１３の処理の後１００４に戻り、共通部２３０の
要素２３４がなくなるまで、ブロック１００６以下の処
理を繰返す。取出す要素がなくなると、現在のノード５
００の終端属性５０４に、ブロック１００２で取出した
共通部２３０のコード２３５を設定する（ブロック１ｏ
ｏｓ）。

第１１図は、初期事実１０４を連想ネット１０６に組込
むだめの処理を示す。

まず、初期事実ファイル１０４から事実を先頭から順に
取出しくブロック１１００　）　、取出す事実がある間
、以下の処理を行う。つまり、ブロック１１０１では、
事実を連想フィルタ１０５に通して、対応する共通部２
３０と個別具体値を取出す（事実のフィルタリング処理
（第１２図）。つぎに、この共通部２３０の連想項リス
ト２３５の中から、上で取出した個別具体値に、その個
別構造２４０が照合する連想項２３６を選択し、その事
実属性２２６に具体値列２４９を追加する（ブロック１
１０２）。

第１２図は、事実のフィルタリング処理を示す。

まず、個別具体値（リスト）を空に設定し、さらに、現
在のノード５００を出発ノード（ノード番号０）としく
ブロック１２０１）、ブロック１１００で取出した事実
に対して、その要素（すなわち事実の文を構成する定数
や変数）を、前から順次取出す（ブロック１２０２）。

取出した要素に対して、それが、現在のノード５００の
定数特徴属性値５０５に含まれるかどうかをチェック−
しくブロック１２０３）、含まれなければ、現在のノー
ドの変数特徴属性５０２の値が空かどうかをチェックし
くブロック１２０４）、空なら、事実フィルタリング処
理の結果に空を設定（ブロック１２０８）Ｌ、処理を終
了する。空でなければ、ブロック１２０２で取出した要
素を個別具体値（リスト）に追加する。この後、あるい
は、ブロック１２０３の処理結果がＹｅｓＯ時、前者で
は変数特徴属性５０２によって示される次ノードを、後
者では、取出した要素とその定数部５０８が一致する定
数特徴属性値５０５の要素の次ノード部５０９が示す次
ノードを現在のノード５００とし、ブロック１２０２の
処理に戻る。ブロック１２０２で取出す要素がなくなれ
ば、現在のノード５００の終端属性５０４が空かどうか
をチェックしくブロック１２０７　）　、空でないこと
が確認できたら、事実のフィルタリング処理の結果とし
て、終端属性５０４の値（つまり共通部コード２３５）
と、個別具体値（リスト）を設定する（ブロック１２０
９）。終端属性５０４が空なら、事実のフィルタリング
処理の結果を空とする（ブロック１２ｏｓ　）。

第１３図は、初期事実に対応する事実属性２２６の値と
して、具体直列２４９を組込むための処理（事実属性設
定処理）である。

ブロック１３０１では、事実のフィルタリング処理の結
果が空でなければ、共通部の項連想属性２３２の値、つ
まシ、（共通部）連想環リスト２３５を取出す。結果が
空なら事実属性設定処理を終了する。次に、（共通部）
連想環リスト２３５か、ら連想環２３６を先頭から順に
取出しくブロック１３０２）、以下の処理を行う。

まず、事実のフィルタリング処理の結果でおる事実の個
別具体値と上記の連想環２３６０個別構造２４０との照
合をとる。個別構造２４０の要素２４３が変数の時は、
対応する位置の個別具体値の要素が、その変数に対する
変数具体値として設定される（ブロック１３０３　）。

照合が不成功ならブロック１３０２に戻り、次の連想環
をとり出す。

照合が成功すれば、上記の連想環２３Ｇの変数属性２２
７の値が空かどうかをチェックしくブロック１３０４）
、空なら、さらに事実属性２２６が空かどうかをチェッ
クする（ブロック１３０８）。空でなければ、すでに、
連想ネットに組込み済みの事実であるから、ブロック１
３０２に戻り、次の連想環の処理を行う。空であれば、
上記の連想環の事実属性を空風外、例えばｔに設定しく
ブロック１３０９　）、同じく規則連想属性２２２の値
である連想規則リスト２５０を、候補規則リスト２６０
に結合しくブロック１３０７　）　、ブロック１３０２
に戻る。

ブロック１３０４で、連想環の変数属性値が空でなけれ
ば、ブロック１３０３で設定した変数具体値（列）が連
想環の事実属性２２６の値（具体値リス）２４８　）の
要素である具体直列２４９のどれかに一致するかをチェ
ックしくブロック１３０５）、一致すれば、ブロック１
３０２に戻り、次の連想環の処理を行う。一致しなけれ
ば、変数具体値（列）を具体値リスト２４８に追加し、
ブロック１３０７の処理を行う。

第１４図は、推論実行プロセッサ１０２の処理方式を示
す。

推論の実行のためには、まず、候補規則リスト２６０が
空かどうかをチェックしくブロック１４０１　）　、空
なら推論実行処理を終了する。空でなければ、候補規則
リスト２６０の要素でおる候補規則２６１の中から最初
に実行する規則を選択する（ブロック１４０２・・・競
合解消処理）。この場合、不変属性が設定されている規
則は、推論結果が新事実の生−成や事実の削除など、環
境の変化に寄与しないので選択の対象外とする。次に、
選択された規則を実行しくブロック１４０３　）、その
結果が変化（上記の環境の変化に寄与する場合）なら、
候補規則２６１で不変属性が設定されているものは、す
べてその不変属性を解除しくブロック１４０４　）　、
ブロック１４０１へ戻る。結果が不変なら、実行した規
則に不変属性を設定しくブロック１４０５）ブロック１
４０１へ戻る。結果が不成立なら（規則の条件が成立し
ない場合）、実行した規則２６１を、候補規則リスト２
６０から削除しくブロック１４０６）、やはり、ブロッ
ク１４０１へ戻る。結果が“停止”なら、本処理（推論
実行処理）を終了する。

第１５図は規則実行処理（ブロック１４０３　］を示し
たものである。まず、結果を″不成立”にしくブロック
１５００）　、次に実行規則の条件部２１１が満足され
るかどうかをチェックする。変数に対しては具体値が矛
盾なく決めることができるかをチェックする（以上ブロ
ック１５０１　）。条件が不成立なら、本処理（規則実
行処理）を直ちに終了する。条件が成立すれば、行動部
２１２を実行しくブロック１５０２１．その結果が１不
変”なら本処理の結果を６不変″としくブロック１５０
５）、ブロック１５０１に戻り、条件部２１１が、異な
る具体値の組に対して成立するかをチェックする。

行動部実行結果が６停止”なら規則実行処理結果を６停
止”に設定しくブロック１５０３）、”変化”なら本処
理の結果を１変化”にして（ブロック１５０４）、規則
実行処理を終了する。

第１６図は実行条件判定処理（ブロック１５０１１を示
す。

実行規則の条件部２１１の先頭から順に条件部２１３を
取出しくブロック１６０１）、取出した条件部２１３の
事実属性２２６をチェックしくブロック１６０２）　、
その値がｔ（つまり変数を含まない項でしかも条件が成
立する）なら、次の条件部を取出すためにブロック１６
０１に戻る。事実属性の値が空なら、条件が不成立であ
るから、条件判定処理の結果を６不成立＃に設定して（
ブロック１６０６）、本処理、すなわち、実行条件判定
処理を終了する。事実属性の値が、ｔや全以外であれば
・その要素、つまり具体直列２４９を順次取出しくブロ
ック１６０３］、取出した具体直列と変数属性２２７の
値（変数列２４１）との照合をとる（条件項変数部照合
処理・・・ブロック１６０４］。照合が成功すれば、す
なわち変数の具体値が矛盾なく定まれば（詳細は第１７
図）、次の条件部を調べるためにブロック１６０１に戻
り、照合が成功しなければ、次の具体値を取出すために
、ブロック１６０３に戻る。ブロック１６０３において
、次に取出すべき具体直列がなくなれば、ブロック１６
０６の処理を行う。ブロック１６０１で、次に取出すべ
き条件部がなくなれば、条件判定処理の結果を１成立”
に設定して（ブロック１６０５）　、本処理を終了する
。

第１７図は、条件項変数部照合処理（ブロック１６０４
　）を示す。

変数列２４１から、その要素である変数２４２を順番に
取出しくブロック１７０１）、取出した変数１７０２の
値が、同じ規則内の前の条件部との照合においてすでに
定まっているか（つまり既束縛変数かどうか）をチェッ
クしくブロック１７０２）、未束縛なら該変数を未束縛
変数列に加え、具体直列の対応要素を束縛値としくブロ
ック１７０３）、次の変数を処理するためにブロック１
７０１に戻る。

既束縛変数に対しては、束縛値と具体直列２４９の対応
要素が一致するかどうかをチェックし、一致すればブロ
ック１７０１に戻り、一致しなければ、未束縛変数列の
変数をすべて未束縛にし、未束縛変数列をクリアしくブ
ロック１７０５　）　、本処理（条件項変数部照合処理
）の結果を１′照合不成功”に設定しくブロック１７０
６）　、本処理を終了する。

さて、ブロック１７０１において、変数列２４１から取
出すべき要素がなくなれば、本処理の結果を“照合成功
”に設定して（ブロック１７０７）、本処理を終了する
。

第１８図は、行動部実行処理（第１５図のブロック１５
０２）を示す。

まず、本処理（行動部実行処理）の処理結果を、”不変
”に初期設定する（ブロック１８０１　）。つぎに、実
行規則の行動部２１２の行動部２１５〜２１７を先頭か
ら順番に取出す（ブロック１８０２）。

取出した行動部が追加項２１６かどうかチェックしくブ
ロック１８０３　）　、追加項なら、追加処理を行う（
ブロック１８０４　）。次に、行動部が削除項２１５か
どうかをチェックしくブロック１８０５）、もしそうな
ら削除処理を行ない（ブロック１８０６）、そうでない
なら停止環かどうかをチェックしくブロック１８０７’
Ｊ　、停止環２１７なら行動部実行処理の結果を１停止
”に設定して（ブロック１８０９）本処理を終える。行
動部が以上のいずれの項でもなければ、該当する処理を
行ない（ブロック１８０８）　、ブロック１８０２に戻
り次の行動部の処理を行う。ブロック１８０４．１８０
６の処理の後も、同様にブロック１８０２に戻る。ブロ
ック１８０２で取出すべき行動部がなくなれば、変数２
４２の束縛値をクリアしくブロック１８１０　）、本処
理を終了する。

第１９図は、追加処理（第１８図のブロック１８０４）
を示す。

まず、追加値２１６の事実属性２２６の値をチェックす
る（ブロック１９００）。ｔ（追加項は変数を含まず、
かつ既知事実である。）なら、直ちに追加処理を終了す
る。空なら、追加項の変数属性２２７が空かどうかをチ
ェックしくブロック１９０３　’Ｊ、Ｙｅｓなら追加項
の事実属性２２６にｔをセットしくブロック１９０４）
、Ｎｏなら追加項の事実属性２２６に、変数属性２２７
の値、つまり変数列２４１の各要素２４２を具体化させ
たものＣ以下、変数の具体値と呼ぶ）を追加する（ブロ
ック１９０２）。ブロック１９００の結果が、ｔ、６る
いは空以外なら、追加項の変数の具体値が、具体値リス
ト２４８の要素のどれかと一致するかをチエンドしくブ
ロック１９０１）　、一致すれば追加項目は既知事実で
あるから追加処理を終了し、不一致なら、上述のブロッ
ク１９０２の処理を行う。

ブロック１９０２、ブロック１９０４の処理の後、行動
部実行結果を６変化”にセットしくブロック１９０５）
、追加項の規則連想属性２２２のｆ１α、つまり連想規
則リスト２５０を候補規則リスト２６０に結合する（ブ
ロック１９０６）。

次に、追加項の項連想属性２２３をとり出す（ブロック
１９０７）。項連想属性２２３が空なら追加処理を終了
し、空でないなら、その値の要素（連想環２４５）を順
次取出す（ブロック１９０８）。連想環２４５の処理が
全て終了すれば、追加処理を終了する。そうでなければ
、連想環の個別構造２４０と、追加項の個別構造（ただ
し変数は具体化されている。）との照合をとる（ブロッ
ク１９０９）、照合が不成功ならブロック１９０８に戻
シ次の連想環を取出す。照合が成功すれば、連想環の変
数の具体値（ブロック１９０２で説明したもの。）が連
想環の具体値ＩＪスト２４８の要素２４９のどれかと一
致するかチェックしくブロック１９１０）　、どれかと
一致すれば、直ちに、どれとも一致しなければ、連想環
２４５の規則連想属性２２２の値、すなわち連想規則リ
ス）２５０を候補規則２６０に結合した（ブロック１９
１１）後、ブロック１９０８に戻９１次の連想環の処理
を行なう。

第２０図は、削除処理〔第１８図のブロック１８０６）
を示す。

まず、削除環２１５の事実属性２２６の値をチェックす
る（ブロック２００１）。空なら削除処理を終了する。

ｔ（削除環は変数を含まず、しかも既知事実である。）
なら、削除環２１５の事実属性２２６を空にしく２００
４）、さらに、候補規則リスト２６０から削除環２１５
の規則連想属性２２２の値、つまり連想規則リストの要
素２５１を全て削除する（ブロック２００５）。ブロッ
ク２００１の結果が、ｔや空以外なら、削除環２１５の
変数属性２２７の１直（変数列２４１）の各要素（変数
２４２）を具体化させたもの（変数の具体値。ブロック
１９０２で定義したものと同じ。）が、同じ削除環２１
５の具体値リスト２４８の要素２４９のどれかと一致す
るかをチェックしくブロック２００２　）　、一致しな
ければ、削除処理を終了し、一致すれば、上記の変数の
具体値を、削除環２１５の事実属性２２６の値、すなわ
ち具体直列リストから削除する（ブロック２００３）。

ブロック２００３、ブロック２００５の終了後、行動部
実行結果を、６変化２に設定する（ブロック２００６）
。

次に、削除環２１５の項連想属性２２３をチェックする
（ブロック２００７）。空なら、削除処理を終了する。

空でなければ、項連想属性の値、すなわち、連想環リス
ト２４４の要素（連想環２４５）を順次取出す（ブロッ
ク２００８）。全ての連想環を取出せば、削除処理を終
了する。連想環に対しては、その個別構造２４０が、削
除環の個別構造（ただし変数要素を具体化したもの）と
照合する＼か（具体化してない変数は全ての定数と照合することを
前提とする。）をチェックしくブロック２００９）　、
照合が不成功なら、次の連想環の処理をするためにブロ
ック２００８に戻る。照合が成功した場合、連想環の変
数属性２２７が空かどうかをチェックしくブロック２０
１０　）　、空でなければ、連想環の変数の具体値（ブ
ロック２０６２で定義したもの）が、同じ連想環の具体
値リスト２４８の要素２４９のいずれかと一致すればこ
れを削除して、いずれとも一致しなければ何もしないで
、ブロック２００８に戻る。ブロック２０１０の結果が
空なら、連想環は定義しか含まないから、まず、連想項
の事実属性２２６を空にしくブロック２０１２）、次に
、候補規則リスト２６０から連想項の規則連想属性２２
２の値、つまυ連想規則リスト２５０の要素２５１を全
て削除しくブロック２０１３）、ブロック２００８に戻
る。

〔発明の効果〕

（１）する規則の実行後、次に起動される可能性のおる
規則群が事前に連想ネットに保存されているので、次に
実行する規則を探す時間が全体の規則数に依存しない。

（２）条件項が事実かどうかを事実属性として保持して
いるため、従来のように事実空間内の全事実と照合をと
る必要がない。つまり、条件項が事実かどうかのチェッ
クに要する時間が事実の数に依存することがない。この
ことと（１）とから、推論時間が規則Ｘ事実の数に独立
になる。規則数か数１００事実数が５０以上の実用的な
推論システムでは、このだめの効率向上は基本的なオー
バヘッドを考慮しても数百倍以上となる。

（３）マルチプロセッサや連想メモリ等の特殊なアーキ
テクチャ−の計算機、素子を用いていないので安価に高
速化が実現できる。また、ソフトウェアの移行性も高い
。

（４）規則の実行によって追加されたり削除されたシす
る事実に対しては、その定数要素などの共通要素の関連
は事前に分析し連想ネットに組み込んであるので、変数
要素の具体値（実行時に変数のとる値）だけ既存の事実
と照合すればよく、オーバヘッドの大半を占める照合時
間が短縮される。通常、事実を表わす文の変数要素は、
文の要素の１〜２割程度であるから照合時間は、５〜１
０倍に向上すると考える。

（５）定数要素や変数要素を文の任意の位置に書いた規
則、つまり、自然語的に表現された規則や事実を入力し
、推論結果もこの形式（自然語的な表現形式）で出力す
るので、マンマシンインタフェース、操作性が性能向上
と引き換えに損われることがない。

（６）　条件項で、その一部の変数要素が特別な定数値
と指定してるるものとないものを統合し、連想項グルー
プとして効率良く処理できるため、知識の記述・表現な
どシステムの操作性を損わずに効率の向上が可能である
。

（７）初期事実の連想ネットへの組込みは、連想フィル
タを用いたため、組込み時間は、（全規則の項の総数）
×（事実数］に比例する時間かかるはずのものが、その
対数時間に減少する。

（８）事実を削除した時・連想項のうち定数型のものを
条件部に持つ規Ａｌｌだけを候補規則集合から削除する
ことにより、少ないオーバヘッドで無駄な規則の条件チ
ェック数を減らせるので全体の処理速度が向上する。

（９）実行した結果、新事実の追加や削除などによシ環
境を変化させることのなかった規則に不変属性を設定し
て実行を抑止することにより、無駄な条件チェック時間
、実行時間が減り、全体の処理速度が向上する。

αＱ　実行の結果、新事実の追加や削除などにより環境
変化が生じた場合は、他の変数具体値に対して同じ規則
の実行を行うのでなく、候補規則集合をチェックして環
境の変化によシ先に実行すべき規則ができたらそれを実
行するので自然な競合解消処理が行える。

（１１）候補規則集合（リスト）に、追加あるいは削除
すべき規則が、項を構成する変数の照合だけで決定でき
るため、不要となった定数部の照合時間だけ、全体の処
理効率が増す。

（呻事実は変数に対応する部分のみ、その変数の具体値
として記憶するため、項ごとに事実を記憶しても所要メ
モリは少なくて済む。

（Ｖ）連想フィルタにおいて終端ノート責最終状態）を
特に作成せず、ノードが終端と非終端の両属性を持てる
方式であるため、処理が簡単な上、メモリ効軍も良い。

（１＋）不変属性（（９）参照）を、他の規則が実行さ
れて環境が変化したらクリアすることは、その環境の変
化が不変属性を持つ規則の処理結果が、新環境を変化さ
せるかという複雑な処理を行うことなく、不変属性を持
つ規則の新環境での実行の機会を与える。

ｕｒ＄行時に条件が成立しないことが判明した規則は、
候補規則集合から削除されるので、無駄な条件照合チェ
ックにより処理効率が低下することがない。

（１ω事実が追加されることによって規則の条件項のう
ち１つでも満足されれば、その規則を候補規則としく候
補規則集合に加え）、その規則の時他の条件のチェックは実へに行なうため、全実行条件が
満足されないと候補規則に加えない方式と比べて（この
方式では、事実が削除された時の処理が複雑になる。）
簡単なチェックで候補規則が絞れるために全体の処理効
率が向上する。

いり）連想フィルタは共通項のみを識別すれば良いので
、同一状態（ノード）にある時、多種の変数を入力した
場合のような複雑な変数処理が不要であるため、処理が
簡単で処理効率が良い。

特に、連想フィルタは、事実の組込みなど多用され全体
の性能に影響を与えるので、その処理効率の向上は、シ
ステム全体の性能の向上に寄与する。

なお、上述した説明では推論について説明したが、上述
した方式は、一般の情報処理にも当てはまる。

【図面の簡単な説明】

第１図は、本発明を実現するシステムの一構成例の全体
図、第２図は連想ネットの構成図、第３図および第４図
は、それぞれコードリストおよび連想ネット共通部（作
成時）のデータ構造の一例を示す図、第５図は連想フィ
ルタの構成図、第６図は連想ネット作成処理フローを示
す図・第７〜１０図はその詳細処理フローを示す図、第
１１〜１３図は（初期）事実組込み処理フローを示す図
、第１４〜２０図は、推論実行処理フローを示す図であ
る。１００・・・連想ネット作成プロセッサ、１０１・・・
初期事実組込みプロセッサ、１０２・・・推論実行プロ
セッサ、１０３・・・規則ファイル、１０４・・・初期
事実ファイル、１０５・・・連想フィルタ、１０６・・
・連想ネット、２００・・・規則リスト、２１０・・・
規則、２１３・・・条件項、２１５・・・削除項、２１
６・・・追加項、２２１・・・環コード、２５１・・・
連想規則、２４５・・・連想環、２４０・・・個別構造
、２４９・・・具体位動、２４１・・・変数列、２３０
・・・共通部、２３３・・・共通Ｔ　Ｉ　Ａ　旧％　Ｉ　Ｂ　ｉ￥ＦＪ　３　図 ′￥Ｊ　４　図第　乙　図％７１１Ｄ第６図葛　９　図毫　ｌρ　図ぢ　１１　図菓　１２　口 ’３４　１３　図％　ｌＩＪ　図不　１５　図 ′ｆＪ１６　図第　７７　図％　Ｉｇ　図条／ｑ図

Claims

【特許請求の範囲】１、条件部と行動部を持つ規則と事実又は仮説が与えら
れると、規則に従って事実又は仮説を変更するサイクル
を繰返すことにより情報処理ｔを行う計算機システムに
おいて、規則の行動部のうち事実又は仮説の追加・削除
に関する項が、どのような具体値に対し、どの規則のど
の条件項を成立にするかを表わす連想ネットと呼ぶネッ
トワークを、共通の定数部を持つ各項を共通部と個別部
からなる連想項としてグループ化し、これを介して情報
処理実行前に作成し、与えられた事実又は仮説を関係す
る連想項の変数の具体値としてその個別部に設定するこ
とによって連想ネットに組込み、以後連想ネットをたど
つ理字臥。２、前記の条件項や行動部の構成要素のうち定数以外を
１つの特別なコードに置き換えるとともに、対応する定
数がすべて一致する２つの項の定数どうしが対応しない
位置の要素をすべて上記の特別コードで置き換えること
を全ての項に対して繰返すことにより連想ネットワーク
の共通部を作成し、かつ事実がこの共通部のどれかと同
じ定数部を持つ場合だけ、その共通部の項のコードが得
られる状態に遷移する機械である連想フィルタを作成し
、これを用いて、事実がどの共通部を持つかを認識させ
、連想ネットに組込む特許請求の範囲第１項記載の計算
機システムの高速処理方式。