JPH05127908A - 照合処理の高速化方法 - Google Patents

Abstract

(57)【要約】 【目的】 事実データの削除による処理効率の低下を回
避することにより、照合処理の高速化を実現する 【構成】 照合を実施する各事実データＤ１〜Ｄ３に、
最初にノードメモリエレメントとしてノードメモリＮ１
〜Ｎ３への記憶を実施する際、この記憶領域を特定する
ノードメモリポインタＮＰを設ける。さらに、各ノード
メモリエレメントに、関連する他のノードメモリエレメ
ントを特定するチェインポインタＣＰを設け、各事実デ
ータＤ１〜Ｄ３毎に、関連する全てのノードメモリエレ
メントを把握できる状態を設定する。事実データＤ１〜
Ｄ３の削除を実施する際、ノードメモリポインタＮＰ及
びチェインポインタＣＰを参照し、削除する事実データ
Ｄ１〜Ｄ３に関連する全てのノードメモリエレメントを
削除する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、人工知能の応用技術に
用いられるルールの条件部と事実データの照合処理の高
速化を実現する照合処理の高速化方法に関するものであ
る。

【０００２】

【従来の技術】人工知能の応用技術の一つに、エキスパ
ートシステムを挙げることができる。このエキスパート
システムにおいては、ルールと事実データの照合を行な
うため、リートネットワーク（ＲＥＴＥネットワーク）
が利用される。このリートネットワークを機能させる際
には、リートネットワークに予めルールを設定する必要
がある。

【０００３】図２に、ルールの説明図を示す。図に示し
た、ルール１（Rule１）は、条件項Ｐ１〜Ｐ３の３つの
条件から構成されている。各条件項は、ファクト名とＩ
Ｆ部（属性及び値の列挙）から構成されている。ファク
ト名は、条件項を特定するための情報が記述された箇所
である。ＩＦ部は、事実データとの照合が実施される情
報が記述された箇所である。ファクト名とＩＦ部、そし
てＩＦ部中の属性及び値の対を区別するため、べき乗記
号が利用されている。条件項Ｐ２を例に挙げると、ＩＦ
部は属性“ｂ１”，“ｂ２”，“ｂ３”、値“３”，
“４”，“＞＝ ＜Ｘ＞”から構成される。

【０００４】ここで、以上の構成のルール１が設定され
たリートネットワークについて説明する。図３は、従来
一般のリートネットワークの概念図である。図に示した
リートネットワークＲＮは、事実データの入力するルー
トＲ１を基準に、先に図２において説明した各条件項の
ファクト名及びＩＦ部の内容に合致するか否かを照合す
るノード１１〜１３，２１〜２３，３１〜３３が用意さ
れている。さらにノード１３，２３，３３の出力側に
は、それぞれのノードを通過した事実データの記憶を行
なうノードメモリＮ１〜Ｎ３が設けられている。

【０００５】ノードメモリＮ１，Ｎ２の出力側には、条
件項Ｐ２のＩＦ部（属性“ｂ３”）の内容に合致するか
否かを照合するノード２４が設けられ、ノード２４の出
力側には、ノード２４を通過した事実データの記憶を行
なうノードメモリＮ４が設けられている。ノードメモリ
Ｎ４及びノードメモリＮ３の出力側には、条件項Ｐ３の
ＩＦ部（属性“ｃ３”）の内容に合致するか否かを照合
するノード３４が設けられている。最後にノード３４を
通過した事実データを記憶するインスタシエーション２
が設けられている。

【０００６】事実データをルートＲ１に入力し照合を行
なう目的として、事実データの追加と事実データの削除
を挙げることができる。一般に、ルートＲ１に入力する
事実データには、追加のために入力されたのか削除のた
めに入力されたのかを区別するトークンが付与される。
追加を示すトークンはプラストークン、削除を示すトー
クンはマイナストークンと呼ばれている。

【０００７】ここで、ルートＲ１に事実データを入力し
た場合のリートネットワークＲＮの動作を図４を参照し
ながら説明する。図４は、事実データの説明図である。
なお、事実データにはプラストークンが付与されている
ものとする。まず、事実データＤ１がルートＲ１に入力
すると、ノード１１に入力される。ノード１１では事実
データＤ１のファクト名が“ａ”であるかを照合する。
照合の結果が一致するため、ノード１２において、属性
“ａ１”の値が“１”であるかを照合する。

【０００８】この照合の結果も一致するため、ノード１
３において、属性“ａ２”の値が“２”であるかを照合
する。ノード１３における照合結果も一致した場合、ノ
ードメモリＮ１には、事実データＤ１がノードメモリエ
レメントとして記憶され、ノード２４において属性“ｂ
３”の照合が実施されるのを待つ。

【０００９】次に事実データＤ２がルートＲ１に入力す
ると、ノード１１においてファクト名の照合が実施され
るが、照合の結果が不一致となるため、ノード２１にお
ける照合に移る。ノード２１〜２３においては、事実デ
ータＤ２に対する照合が一致するため、ノードメモリＮ
２には事実データＤ２がノードメモリエレメントとして
記憶される。

【００１０】ノード２４では、ノードメモリＮ２に事実
データＤ２が記憶されたのを受けて、事実データＤ１の
属性“ａ３”と事実データＤ２の属性“ｂ３”の照合を
行ない、結果が一致した場合には、ノードメモリＮ４
に、事実データＤ１，Ｄ２の対をノードメモリエレメン
トとして記憶し、ノード３４において属性“ａ３”が照
合されるのを待つ。

【００１１】最後に、事実データＤ３がルートＲ１に入
力すると、ノード１１，２１において照合結果が不一致
となり、ノード３１〜３３において一致する。ノードメ
モリＮ３には、事実データＤ３がノードメモリエレメン
トとして記憶され、ノード３４において属性“ａ３”と
属性“ｃ３”の照合が実施される。ノード３４における
照合の結果一致した場合には、インスタシエーション２
には、事実データＤ１，Ｄ２，Ｄ３の組がノードメモリ
エレメントとして記憶される。以上のような処理を、値
の異なる事実データをルートＲ１に入力して繰り返すこ
とにより、インスタシエーション２に記憶される事実デ
ータを増加させる。

【００１２】さて、事実データの削除を行なう場合、マ
イナストークンを付与し、事実データをルートＲ１に入
力する。この事実データの内容は、先にプラストークン
を付与してルートＲ１に入力したものと同一となる。例
えば事実データＤ１の削除を行なう場合、事実データＤ
１にマイナストークンを付与してルートＲ１に入力す
る。この事実データは、先の説明と同様に、ノード１１
〜１３において照合され、一致した場合、ノードメモリ
Ｎ１に記憶された事実データＤ１の削除が実施される。

【００１３】ノードメモリＮ４では、ノードメモリＮ１
における削除の実施を認識すると、削除された事実デー
タと対を構成する事実データ、この場合、事実データＤ
１，Ｄ２を削除する。さらにインスタシエーション２で
もノードメモリＮ４における削除の実施を認識すると、
削除された事実データと組を構成する事実データ、この
場合、事実データＤ１，Ｄ２，Ｄ３を削除する。以上の
ような処理の流れにより、事実データの追加及び削除を
実施する。

【００１４】

【発明が解決しようとする課題】さて、事実データの削
除を実施する場合、ノードメモリから事実データを削除
する処理以外の各ノードにおける照合の処理は、必ずし
も必要な処理とはいえない。即ち、ノードメモリを削除
するためにルートＲ１に事実データを入力したときに実
行される照合の処理は、削除する事実データが記憶され
ているノードメモリを特定するためのものであり、ノー
ドメモリのデータを削除するときに必ずしも必要な処理
ではない。通常、エキスパートシステム等の知識ベース
の推論処理においては事実データの追加と削除は、ほぼ
同じ頻度で実施される。このため、事実データを削除す
る際に実行される照合の処理は処理効率の著しい低下を
もたらすといった問題が生じていた。本発明は以上の点
に着目してなされたもので、事実データの削除による処
理効率の低下を回避することにより、照合処理の高速化
を実現する照合処理の高速化方法を提供することを目的
とする。

【００１５】

【課題を解決するための手段】本発明の照合処理の高速
化方法は、ルートから入力された事実データの照合を行
なうノードと、前記ノードにおける照合結果であるノー
ドメモリエレメントを記憶するノードメモリを有するリ
ートネットワークにおいて、前記事実データに、当該事
実データを基に生成された前記ノードメモリエレメント
の格納場所を特定するノードメモリポインタを設け、か
つ前記ノードメモリエレメントには、当該ノードメモリ
エレメントを基に新たに生成された他のノードメモリエ
レメントの格納場所を特定するチェインポインタを設
け、前記事実データを削除する場合、前記ノードメモリ
ポインタ及び前記チェインポインタを参照し、当該事実
データ及び関連する前記ノードメモリエレメントの削除
を行なうものである。

【００１６】

【作用】この方法は、照合を実施する各事実データに、
最初にノードメモリエレメントとしてノードメモリへの
記憶を実施する際、この記憶領域を特定するノードメモ
リポインタを設ける。さらに、各ノードメモリエレメン
トに、関連する他のノードメモリエレメントを特定する
チェインポインタを設け、各事実データ毎に、関連する
全てのノードメモリエレメントを把握できる状態を設定
する。事実データの削除を実施する際、ノードメモリポ
インタ及びチェインポインタを参照し、削除する事実デ
ータに関連する全てのノードメモリエレメントを削除す
る。

【００１７】

【実施例】ここでは、本発明を先に説明した図２乃至図
４の条件で実施した場合について説明する。図１は、本
発明の概念図である。なお、事実データＤ１〜Ｄ３が、
アドレスＡ１〜Ａ３で示される記憶領域上に用意され、
これら領域上の事実データＤ１〜Ｄ３が順次ルートＲ１
に入力されたものとする。事実データＤ１は、ノード１
１〜１３において照合され、ノードメモリＮ１上のアド
レスＡ４で特定される記憶領域上に、ノードメモリエレ
メントＥ１として記憶されることになる。

【００１８】このノードメモリエレメントＥ１は、事実
データＤ１に関連するノードメモリＮ４上の記憶を特定
するチェインポインタＣＰと、事実データＤ１の記憶領
域を示す事実データポインタＦＰ（内容はアドレス“Ａ
１”）の形態で記憶される。なお、チェインポインタＣ
Ｐの内容は、ノード２４における照合の結果が一致する
まで、いずれの記憶領域も特定しない例えば内容“０”
が設定される。一方、事実データＤ１には、ノードメモ
リエレメントＥ１の記憶領域を示すノードメモリポイン
タＮＰ（内容はアドレス“Ａ４”）が付加される。

【００１９】次に、事実データＤ２がルートＲ１に入力
すると、ノード２１〜２３において照合され、ノードメ
モリＮ２上のアドレスＡ５で特定される記憶領域上に、
ノードメモリエレメントＥ２として記憶されることにな
る。このノードメモリエレメントＥ２は、事実データＤ
２に関連するノードメモリＮ４上の記憶を特定するチェ
インポインタＣＰと、事実データＤ２の記憶領域を示す
事実データポインタＦＰ（内容はアドレス“Ａ２”）の
形態で記憶される。

【００２０】ノードメモリＮ２への事実データＤ２に関
する記憶が完了すると、ノード２４における照合が実施
され、ノードメモリ２４にノードメモリエレメントＥ４
が記憶される。このノードメモリエレメントＥ４は、事
実データＤ１，Ｄ２の対に関連するインスタンシエーシ
ョン２上の記憶を特定するチェインポインタＣＰと事実
データＤ１，Ｄ２の記憶領域を示す２つの事実ポインタ
ＦＰ（内容はアドレス“Ａ１”，“Ａ２”）の形態で記
憶される。なお、ノードメモリエレメントＥ４のチェイ
ンポインタＣＰの内容は、ノード３４における照合の結
果が一致するまで、いずれの記憶領域も特定しない例え
ば内容“０”が設定される。また、ノードメモリエレメ
ントＥ１，Ｅ２のチェインポインタＣＰの内容は、それ
ぞれノードメモリエレメントＥ４の記憶領域を特定する
アドレス“Ａ７”に設定される。

【００２１】最後に、事実データＤ３がルートＲ１に入
力すると、ノード３１〜３３において照合され、ノード
メモリＮ３上のアドレスＡ６で特定される記憶領域上
に、ノードメモリエレメントＥ３として記憶されること
になる。このノードメモリエレメントＥ３は、事実デー
タＤ３に関連するインスタンシエーション２上の記憶を
特定するチェインポインタＣＰと、事実データＤ３の記
憶領域を示す事実データポインタＦＰ（内容はアドレス
“Ａ３”）の形態で記憶される。

【００２２】ノードメモリＮ３への事実データＤ３に関
する記憶が完了すると、ノード３４における照合が実施
され、インスタンシエーション２にノードメモリエレメ
ントＥ５が記憶される。このノードメモリエレメントＥ
５は、事実データＤ１〜Ｄ３の対に関連するインスタン
シエーション２上の記憶領域を特定するチェインポイン
タＣＰと事実データＤ１〜Ｄ３の記憶領域を示す３つの
事実ポインタＦＰ（内容はアドレス“Ａ１”〜“Ａ
３”）の形態で記憶される。なお、ノードメモリエレメ
ントＥ３のチェインポインタＣＰの内容は、ノードメモ
リエレメントＥ５の記憶領域を特定するアドレス“Ａ
８”に設定される。

【００２３】以上のような手順でノードメモリエレメン
トを生成した後、例えば事実データＤ１の削除を行なう
場合、事実データＤ１に付随したノードメモリポインタ
ＮＰの内容を読み取る。この結果アドレス“Ａ４”を把
握し、このアドレス“Ａ４”で特定される記憶領域、即
ちノードメモリエレメントＥ１のチェインポインタＣＰ
の内容を読み取り、ノードメモリエレメントＥ１の削除
を行なう。

【００２４】さらに、ノードメモリエレメントＥ１のチ
ェインポインタＣＰが示していたアドレス“Ａ７”によ
り特定される記憶領域、即ちノードメモリエレメントＥ
４のチェインポインタＣＰの内容を読み取り、ノードメ
モリエレメントＥ４の削除を行なう。そして最後に、ノ
ードメモリエレメントＥ４のチェインポインタＣＰが示
していたアドレス“Ａ８”により特定される記憶領域、
即ちノードメモリエレメントＥ５のチェインポインタＣ
Ｐの内容を読み取り、ノードメモリエレメントＥ５の削
除を行なう。

【００２５】この場合、ノードメモリエレメントＥ５の
チェインポインタＣＰの内容が“０”であるため、ノー
ドメモリエレメントの削除が完了したものとして事実デ
ータの削除を処理を終了する。なお、ノードメモリエレ
メントＥ２，Ｅ３のチェインポインタは、それぞれノー
ドメモリエレメントＥ４，Ｅ５が削除されると、内容が
“０”に設定される。

【００２６】図５に、本発明に係る第１のフローチャー
トを示す。図は、事実データの追加を行なう場合の処理
を示したものである。まず、照合を実施した結果、ノー
ドメモリに事実データを記憶させる事態が生じた場合、
このノードメモリが、照合の過程で最初に事実データの
記憶を行なうノードメモリであるかを判断する（ステッ
プＳ１）。結果がＹＥＳの場合、事実データに付随する
ノードメモリポインタＮＰに、このノードメモリ上の記
憶領域を示す（ノードメモリエレメントを特定する）ア
ドレスを格納する（ステップＳ２）。

【００２７】その後、ノードメモリポインタＮＰに格納
したアドレスを、作業領域（WORK）に格納する（ステッ
プＳ３）。そして、ノードメモリ上に新たに設けられた
ノードメモリエレメントのチェインポインタＣＰに
“０”を代入し（ステップＳ４）。ステップＳ１の結果
がＮＯの場合、作業領域からアドレスを読み取り、先に
“０”を代入したチェインポインタＣＰに格納し（ステ
ップＳ５）、ステップＳ３に移る。

【００２８】図６に、本発明に係る第２のフローチャー
トを示す。図は、事実データの削除を行なう場合の処理
を示したものである。まず、削除する事実データからノ
ードメモリポインタを取り出し、作業領域に代入する
（ステップＳ１１）。そして、作業領域の内容が示すノ
ードメモリエレメントの削除を実施し（ステップＳ１
２）、削除したノードメモリエレメントのチェインポイ
ンタの内容を作業領域に代入する（ステップＳ１３）。
作業領域の内容が“０”であるか判断を行ない（ステッ
プＳ１４）、結果がＮＯの場合、ステップＳ１２に戻り
処理を継続し、結果がＹＥＳの場合、ノードメモリエレ
メントの削除を終了し、残ったノードメモリエレメント
のチェインポインタの内容を変更する等の処理を行な
う。以上の説明のように、事実データの削除が、ノード
における照合を行なうことなく実現することができる。

【００２９】

【発明の効果】以上説明したように、本発明によると、
事実データの削除を実施する際、ノードにおける照合を
必要とせず、単にアドレスの認識、認識したアドレスの
示す領域の削除を実施すれば良いため、結果の明白な処
理に長い時間を費やすことなく処理効率を上げることが
できる。

【図面の簡単な説明】

【図１】本発明の概念図である。

【図２】ルールの説明図である。

【図３】従来一般のリートネットワークの概念図であ
る。

【図４】事実データの説明図である。

【図５】本発明に係る第１のフローチャートである。

【図６】本発明に係る第２のフローチャートである。

【符号の説明】

ＣＰ チェインポインタ Ｄ１〜Ｄ３ 事実データ Ｅ１〜Ｅ５ ノードメモリエレメント ＦＰ 事実データポインタ ＮＰ ノードメモリポインタ

Claims (1)

【特許請求の範囲】
1. 【請求項１】 ルートから入力された事実データの照合
   を行なうノードと、前記ノードにおける照合結果である
   ノードメモリエレメントを記憶するノードメモリを有す
   るリートネットワークにおいて、 前記事実データに、当該事実データを基に生成された前
   記ノードメモリエレメントの格納場所を特定するノード
   メモリポインタを設け、 かつ前記ノードメモリエレメントには、当該ノードメモ
   リエレメントを基に新たに生成された他のノードメモリ
   エレメントの格納場所を特定するチェインポインタを設
   け、 前記事実データを削除する場合、 前記ノードメモリポインタ及び前記チェインポインタを
   参照し、当該事実データ及び関連する前記ノードメモリ
   エレメントの削除を行なうことを特徴とする照合処理の
   高速化方法。