JPH0283624A - パターン・マツチング・ネツトワーク更新方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 Ａ、産業上の利用分野 本発明はＲＥ　Ｔ　Ｅタイプのネットワークを含む、更
に詳細に説明すればｔ’＋η記ネットワークの性能を向
−ヒさせるパターン・マッチング・ネットワークに関す
る。

Ｂ、従来技術及びその問題点 フォーシイ（Ｆｏｒｇｙ）が示唆したＲＥＴＥのような
。

いわゆる人工知能ないしはパターン・マツチング・プロ
グラミングが開発されつつあり、ここ数年に互って用い
られている。ＲＥＴＥネットワークは一つ又は複数のマ
ツチング規則を用いるパターン・マツチングへの幾つか
のアプローチの１つである。これらのプログラムはよく
知られている。

”ＲＥＴＥ：多パターン／多目的パターン一致間厘の高
速アルゴリズム　（Ａ　Ｆａｓｔ　ＡｌｇｏｒｉＬｈｍ
　ｆｏｒｔｈｅ　　Ｍａｎｙ　　Ｐ複数ｔｅｒｎ／　Ｍ
ａｎｙ　　０ｂｊｅｃｔ　　Ｐ複数ｔｅｒｎ　　Ｍ複数
、ｃｈｐｒｏｂｌｃｍ）、　　ＡＲＴＩＦＩＣＩＡＬ　
　ＩＮ置Ｉ、ＩＧＥＮＣＥ、Ｖｏｌｕｍｅ　　１９゜１
．９８２．　ｐｐ　１．７−３７のチャールス（Ｃｈａ
ｒｌｅｓ）　ｌ７．フォーシイ（Ｆｏｒｇｙ）の論文を
参照されたい、この分野でのもう一つの公知の例は、”
ＲＥ　ＴＥパターン・マツチングの進歩　（Ａ　ｄ　ｖ
　ａ　ｎ　ｃ　ｅ　ｓ　ｉ　ｎ　（（Ｅ　Ｔ　［＞　Ｐ
　ａ　ｔ　Ｌ　ｃ　ｒ　ｎＭ複数ｃｈｉｎｇ　）、　Ｐ
ＲＯＣＥＥＤＩＮＧＳ　　ｏｆ　　１９８６　　ＡＭＥ
ＲＴＣＡＮＡＳＳＯＣＩＡＴＩＯＮ　　ｆｏｒ　　ＡＲ
ＴＩＦＩＣＩＡＩ、　ＩＮ置ＬＩＧＥＮＣＩシＣＯＮ　
Ｆ　Ｅ　Ｉｔ　ＩミＮＣＥ、　１９８６．　ｐｐ　２２
６−２３２　　のマーシャル（Ｍａｒｓｈａｌｌ）　１
．ショア　（Ｓｃｈｏｒ）外の論文にある。

ＲＥ　Ｔ　Ｅネットワーク及び人工知能プログラミング
についての周知の情報は１通常の当業者が本発明を理解
するのに必要とする場合以外は本明ａ＋害には反復記載
しない。

周知のように、前記パターン・マツチング・プログラミ
ングは複数のデータ構造により実行する。

ワーキング・メモリ・ニレメン１〜（ＷＭＥ）は入力デ
ータ構造である。新しいＷＭＥ、変更されたＷＭＥまた
は削除されたＷＭＥはどれも、ＲＥ　ＴＥの更新を必要
とする”デルタ”を生ずる５デルタはＲＥＴ　Ｅの情報
内容がＷＭＥの付加、変更ないしは削除を反映しないこ
とを意味するので、１くＥ　Ｔ　Ｅはそれが現在の入力
の情報の状態を反映するように更新されるようにする必
要がある。ＲＥＴＥを更新する際には、前記”デルタ１
はデルタを正確に表わすように構隻された変更１・−ク
ンによって表わされる。その際、ＷＭＥ変更のため生じ
た変更を反映するようにネットワークを更新するため、
当該変更トークンはＲＥＴＥを介して押込まれる。変更
トークンがＲＥＴＥを介して押込まれ（処理され）、Ｒ
ＥＴＥ内のパターンと一致させられる毎に、パターン一
致動作が構成される。

デルタ即ち変更トークン入力の各々の結合ノードの更新
は、前のメモリ・ノー１くに記憶されたＷＭＥ値から、
パターン検査のための入力引数を計算することを必要と
する。この計算には時間がかかることがあるので、パタ
ーン・マツチング動作の正確さに影響を及ぼすことなく
前記計算を少なくすることが望ましい。

ＲＥＴＥはアルファ部とベータ部とから成る。

アルファ部は通常はメモリ・ノード、即ち部分パターン
・マツチング結果が記憶されるノードを持たない、それ
に対し、ベータ部は前記メモリ・ノードの外、多数の引
数値を必要とする複数の検査を含むことがある結合ノー
ドのような他のノードも含む、アルファ部とベータ部の
中間にはアルファ分配ノードがあり、その全てはアルフ
ァ部で生成された部分パターン・マツチング結果を記憶
するメモリ・ノードである。ＲＥＴＥはいわゆる変更ト
ークンによって更新される。各の変更トークンはＲ，Ｅ
　Ｔ　Ｅシステムにおける新たな又は変更されたＷＭＥ
から生ずる情報の変更（デルタ）もしくは削除されたＷ
ＭＥから生ずる変更を示す情報内容を有する。前記変更
トークンはアルファ分布ノードに記憶される部分一致結
果を生成するためアルファ部分を介して押込められる。

そして変更トークンはアルファ分布ノードからベータ部
に押込められる。

ベータ部では、結合ノードの各は２つの入力部：左側の
入力（Ｌ　Ｔ−（Ｓ　）及び右側の入力（Ｒｌ−Ｉ　Ｓ
　）を１１）ることかできる、変更トークンは該２つの
入力のいずれかに到達するであろう、結合ノードは多数
のパターン・マツチング検査を含むことがある。トー１
ンが１つの入力（Ｌ　ＩＩＳ　又はＲＩＩ　Ｓ　）に到
達すると、これらの検査は変更トークン毎に複数の検査
の反復を必要とすることがある。即ち、向かい合ってい
るメモリが多数の部分一致トークンを有するときは、各
の検査は多くの検査オペレーションを生ずることがある
。これらの検査は２つの部分；該検査の引数を得る第１
の部分及び該検査を実行する第２の部分を有するものと
みなされる。多くのアプリケーションの場合、検査を実
行するのに必要な時間の大部分は該引数を取得するのに
用いられる。多くの場合、検査自身は２つのパターンを
比較して一致するか又は同等であるかをを調べる簡単な
ものである。前記計算はＲＥＴＥのパフォーマンスを低
下させる。ノードが多数の検査を実行されるとき、この
パフォーマンスの低下は特に著しい、全てのタイプのパ
ターン・マッチング・ネットワークの実行時間を少なく
すること、特に、ＲＥＴＥネットワークのベータ部で必
要とされる時間を少なくすることが望ましい。

周知のように、メモリ・ノードの出力はＲＥＴＥの更新
状態を表わす、メモリ・ノードの内容は部分一致トーグ
ンを含み、　”向かい合っているメモリ１のような次の
ノードへの入力となりうる。

変更トークンは該向かい合っているメモリで指定された
部分一致トークンと比較される。市記向かい合っている
メモリは該変更トークンを受取るノードの”向かい合っ
ている°°側での直ぐ前のノードのメモリである。この
マツチングは２種類の情報を用いる。第１の種類の情報
は呼出すべき検査機能のタイプを含むパターン検査、検
査引数の仕様、及び部分一致したＷＭＥデータ・ニレメ
ン１〜・トークンを説明する情報を記述する。この第１
の種類の情報はＲＥＴＥ構造が指定されたパターンから
構築されるときに計算される。第２の種類の情報はＷＭ
Ｅが生成、変更又は削除されるそれによってＷＭＥ変更
トークンがＲＥＴＥを介して押込まれる−ときに計算さ
れる。全ての情報へのアクセスは通常のプログラミング
手順に従って行われ、マツチング・オペレーションは通
常のプログラミングによる比較である。−例として、単
一の結合ノード又は一致ノードの各は単一の検査で１０
０．１０００又はそれ以上の値を利用することができる
。前記値は該ネットワークを介して押込まれる変更トー
クンと比較して一致するものを探すために走査される。

各の前記ノードは１前記検査の多くを受けることがある
。

Ｃ１発明の要旨 本発明は°改良されたパターン・マツチング更新動作を
提供する１本発明に従って、検査を受けるパターン・マ
ツチング結合ノードは該検査のための引数入力が結合ノ
ードの１つの側（のみ）からの変更トークンに依存する
だけであるかどうかを確認するために調へられる。この
調査はＲＥＴＥの構造にだけ依存し、どの部分一致ノー
ドの、どんな現在の内容にも依存しない、その結果、キ
ャッシング（ｃａｃｈｉｎｇ）の利点を判定するための
調査は、ＲＥＴＥが構築されるか又は実質的に変更され
るときに一度実行される。

結合ノードでパターン・マツチング・オペレーションを
実行している間に、噴−の変更トークンから取出された
値を複数の引数値と比較することができる。前記比較は
、プログラム・ループで。

例えば向かい合っているメモリからの複数の可能な部分
一致トークンを走査することにより実行される。このル
ープ中、変更トークン引数の供給した値は、それが一定
であるときは必ず、検査が実行されている結合ノード検
査部にキャッシュされる。このキャッシングは前記入力
のための全ての再計算を回避し、それによりＲＥＴＥオ
ペレーションを向上させる。

最近のＲＥＴＥパターン・マツチングの慣習では、パタ
ーン検査は任意の方法の計算式で組合わされた多重ＷＭ
Ｅ属性値に依存することがある。

これは１つのＷＭＥ値だけを用いる初期のＲＥ　ＴＥの
慣習と対照的である。結合ノードで実行中の特定の検査
は到来する変更トークン、ないしは向かい合っているメ
モリのトークン（向かい合っているメモリでの部分一致
トークン全てにわたり結合ノード・ループで一度に１つ
選択される）、又は両者からＷＭＥ値を参照することが
できる。

結合ノードにおけるキャッシング引数値は一つずつ検査
されることが望ましい、任意の一連の異なる検査では、
該検査の一部についての引数値がキャッシュされること
があり、１官記キヤツシングはＬ　）ｉ　Ｓノード又は
ＲＩＩＳノードのどちらかの入力から取出された引数値
に関するものであると言ってもさしつかえない。

Ｄ、実施例 本記述はド記の参照文献に示すような公知のパターン・
マッチング・ネットワークに基づいている。０ＰＳ５外
で使用されるような公知のプログラミング言語は”共通
リスプ（Ｃｏｍｍｏｎ　Ｌｉ５ｔ’）”である；ガイ　
（Ｇｕｙ）　Ｌ−スティール（Ｓｔｅｅｌｅ）、　Ｊｒ
”共通りスプ（ＣＯＭＭＯＮ　１．ｌ５ｌ））”Ｄｉｇ
ｉｔ、ａｌ　Ｐｒｅｓｓ、　１９８４　（ＱＡ７６．７
３．Ｌ２３５７：＋　＋９８４１ＳＩｌＮ　０−９３２
３７６−４１−Ｘ）参照、既知のＲＥＴＥアルゴリズム
はブロクラミング・エキスパート・システムズ（ＰＲＯ
ＧＩ＋ＡＭＭＴＮＧＥＸＰＥＲＴ　ＳＹＳＴＥＭＳ）　
ＩＮ　０ＰＳ５．アジソンーウェスレイ（Ａｄｄｊｓｏ
ｎ−Ｗｅｓｌｅｙ）、　ｐｐ　２２８−２３９．１９８
５にブラウンストーン　（Ｂｒｏｗｎｓｔｏｎｅ）によ
り記述されている。

本発明は破線の枠で示す内部メモリ１３（第１図）を有
するディジタル・コンピュータ１０（図示せず）で実施
される。プログラム１１はＲＥ　ＴＥプログラムのよう
な以前のマツチング・ネットワーク・プログラムとして
配列される。プログラム１１は共通リスプ（ＬＩＳ））
）、：語で記述することができる。これらのプログラム
はパターン・マツチング・オペレーションを実行するデ
ータ構造（ノード、トークン、ルール）で動作する。１
りＥ　Ｔ　Ｅネットワークを生成又は作成する際の最初
のステップは、ネットワークのロジック経路をルール毎
に１経路ずつ明確に定めるルールのリストを生成するす
ることである。このようなルールの形式は前記ショア件
の文献の２２６頁に示されている。そしてルールは、周
知のように分解され配列される。　＋’ｒｆ記パターン
・マツチング・ノードはルールで明確に定めたロジック
経路−該ネジ１〜ワークを介してルール毎に１つの前記
ロジック経路が根（ｒｏｏｔ）ノード３０から出力位置
６０まで延長されるー　で前のノードと後のノー１〜に
相互接続される。この分解及び配列は根ノードζ（Ｏ、
アルファ・マツチング・ノード３３、アルファ分配ノー
１〜３５及びベータ・ノード３７を有するパターン・マ
ツチング・ネッｌ−ワークをコンパイルする１本明細書
では項［］　３０　、３３　、３５及び３３７の集まり
をＲＥ　Ｔ　Ｅと呼ぶ、根ノー（へ３０はワーキング・
メモリ１５に論理的に接続される。

矢印１６で示すように、ワーキング・メモリ・エレメン
トＷ　Ｍ　Ｅがワーキング・メモリ１５に付加されたり
５メモリ１５から削除されたり又はメモリ１５で変更さ
れたりすると、メモリ１５の情報ステータスはＲＥ　Ｔ
　Ｅの情報ステータスと異なるもの之なり、ＲＥ”ｌ”
Ｅとワーキング・メモリ１５の間にデルタを生ずる。こ
のデルタは該デルタを表わす情報内容を有する変更トー
グンー−ＲＥＴＥのデータ内容をワーキング・メモリ１
５の現在の状態に更新するためＲＥ　Ｔ　Ｅを介して押
込まれる−を必要とする。この変更トークンは１−−ク
ン・アドレスに記憶される。ＲＥＴＩＥにおける該トー
クンのアクセス及びその識別はメモリ領域２０−　メモ
リ１３内のプログラム１１により指定されたもう１つの
領域−の該トークン・ア（−レスに対するアドレス・ポ
インタにより行われる。

前記データ及びデータ構造はメモリ１３に、且つメモリ
１３から周辺データ記憶装′ａ／ｉ（図示せず）にペー
ジングすることができる。他の全ての値及び演算子も同
様にネットワーク３３〜３７で識別される０次の記述は
アルファ分配ノード３５への変更トークン押込みが完Ｙ
しているものと仮定する。

ベータ・ノー１”＆　更１−−クン押込みについて記述
する前に、ベータ・ノード・アレイについて記述する。

ベータ・ノードは種々のタイプのノードから成るが、こ
こで重要なのは結合ノー１へである。

各の結合ノードは計算機実行のパターン・マツチング・
オペレーションが２つの入力間で実行されることを可能
にする。各の結合ノードは２つのノード入力に現われた
２つの引数の間のパターン・マツチング検査を規定する
属性（ρｒｅｄｉｃ複数ｅ）検査のテーブルを含む、プ
ロゲラ１１１１によるベータ・ノー］へ３７の部分の走
査は、部分的には、階層的なノード接続に基づいている
８第１図には幾つかの結合ノード４０〜４３しか示さな
いが、実際のＲＥＴ　Ｅの構造では多くのロジック経路
及び多くの面記結合ノード即ちベータ・ノードがある。

結合ノードで、１つの入力（Ｌ　ＨＳまたはＲＩ（Ｓ　
）は、（向かい合っているノード入力で）向かい合って
いるメモリに記憶されたデーター先行メモリ・ノードの
記憶結果−に、データを一致させる変更１ヘークン（本
明細書ではノードへのデルタ人カバターンと呼ぶ）を受
取る。

各の結合ノード即ちベータ・ノードは２つの入力ボート
及び１つの出力ポートを得ることができる。トークンが
先行ノードから後続ノードに（例えば、ノード４０から
ノード４１に）ｅされるどき、トークン・アドレスは通
常、渡す側の先行ノード４０の出力に記憶される（複数
の後続ノードが共用することを可能にする）、各の出力
ポートは複数の前記１−−クン・アドレスを記憶する多
重マツチングの場合を表わす−ことがある。

結合ノードの左側の［、ＨＳ入力ポートは、ベータ・ノ
ード４０〜４３３については参照番号５１．５；３．５
６及び５８によってそれぞれ表示される。

ベータ・ノード即ち結合ノー（へのいわゆる右側のＲＩ
ｆ　５人カポ−１〜は、ノード４０〜４：３については
参照番号５０．５４．５５及び５７によってそれぞれ表
示される。アルファ分配ノーＩ−：３５はＩくＥ　Ｔ　
Ｅのベータ・ノード部において多数のレベル１のノード
に対し相対的に多数の、珪つ低いレベル（高い番号のレ
ベル）に対し直接に接続される論理出力を有する。レベ
ル１のノー１−は分配ノード即ちメモリ・ノー１−二３
５から１入力又は２入力を得ることができる。先行ノー
ドは関連するノード　−即ち、ノード４０はノード４１
に対し先行ノー１〜であり、ノード４１−はノード４０
に対し後続ノードである−よりもアルファ分配ノー１−
７３５に論理的に近いノードである。構築された実施例
では、結合ノー１〜の数は数百又はそれ以上になること
がある。

ＲＥ’ｒＥとの接続に用いられるデータ構造は既知であ
るのでその説明は省略“する８本発明の理解を容易にす
るため、ベータ・ノード３７の部分データ構造を第２図
に示す、ベータ・ノード・データ構造９９は、周知のよ
うに、結合ノードの特徴即ちタイプを表わすＴＹＰＥフ
ィールド１００を含む、ベータ・ノードのタイプの例は
該ノードでプログラム１１により実行されるパターン・
マツチング検査の特性である。該特性は過度にｊ１ｉ純
化さ九た形態ではＡ　Ｎ　Ｄロジック・ステップ、”存
在しない”ロジック・ステップ、等を含む。ＲＰフィー
ルド１０１はＲＨＳ即ち右先行（ＲＰ）ノードに対する
メモリ・アドレス・ポインタを、もしあれば記憶する。

ＲＳフィールド１０２も同様にＲＨ５即ち右後続（ＲＳ
　）ノードに対するメモリ・アドレス・ポインタを記憶
する。同様に、Ｌ　Ｐフィールド１０５及びＬＳフィー
ルド１０６も左先行ノード及び左後続ノードに対するメ
モリ・アドレス・ポインタを記憶する。

ＭＥＭフィールド１０４はノードの入力に到来するトー
クンから構築された部分一致１−−グンを記憶する。こ
れらのトークンはロジック即ち該ノードのパターン・マ
ツチング検査に合格したことを表わす、いったん所′ｊ
、の検査に関する任１５：の所与の引数の安定度が決定
されると、結合ノー１−で引数から計算され又は取出さ
れた値のキャッシングが、後述するように、適切な引数
ＡＲＧ＋（１２０）のキャッシュ値フィールド１２７又
はＡ　ＲＧ２（１２１）で可能になる。現に討議された
ベータ・ノードを満たす（ｐｒｉｍｅ）ための前記キャ
ッシングは後述する属性検査構造１］９で示される。

図示の実施例では、引数値のキャッシングは検査の場合
だけであり、検査毎にキャッシュ可能引数値について１
回生ずる。よって、キャッシングの概念はノードへの安
定したデルタ入力の部分キャッシングを含み、その場合
、キャッシングは、その時点で安定している、即ちほぼ
一定していると決定された引数についてだけである。変
化するり数はキャッシュされない、構造９９は追加の制
御フィールド（既知であるから図示せず説明も省略する
）を含む。

ベータ・ノードに含まれるのは検査データ構造１１９に
示すような検査の定義である。構造１１９には引数値が
キャッシュされる。ＡＲＧ１フィールド１２０及びＡＲ
Ｇ２フィールド１２１は結合ノード検査のための第１及
び第２の検査引数に対するポインタを含む、属性検査フ
ィールド１２２は、メモリ領域２０に記憶された”プロ
グラム”識別された属性検査をＡＲＧ　ｌ及びＡＲＧ２
の計算値の間で実行する−に対するアドレス・ポインタ
を記憶する。複数の検査構造１１９は１つのベータ・ノ
ードにあることもあり、連結されたリストとして記憶さ
れることもある。検査引数は結合ノードのＬＨ３入力と
もＲ）（Ｓ入力ともロジック関係を持たない。

各の引数は４つのフィールドを含むが、ＡＲＧｌのフィ
ールドだけが図示されている。ＡＲＧ２も同一のフィー
ルド構造を持っている。フィールド１２５は該引数のデ
ータへのアクセス経路の定義を含む、２以」―のアクセ
ス経路が定義されるときは、”引数関数“フィールド１
２８はメモリ領域２０内のプログラム−アクセス経路の
各からのデータを１つの検査引数値に結合するーに対す
るポインタを含む、該１つの値はフィールド１２２で識
別された属性検査で用いられることになっている。フィ
ールド１２８で指定された前記プログラムは、あとで明
確にされるように、複数の値を組合わせるのに使用可能
な任意の式又はプログラム式関数とすることができる。

唯一のアクセス経路が定義されると、通常は、検索され
た値が検査に用いられる。これらのアクセス経路はノー
ドのデルタ人カバターン（ノード入力における変更トー
クン）をキャッシュする結合ノードの候補を決定する際
に用いられる。用語”値”は、属性検査と協同しうる、
数値；任意の記号ストリング；（アレイ；プログラム式
関数又は手順；ハソシンタ・テーブル；ベクトル構造ア
レイ等のような）データ・オブジェクト等を含む。

フィールド１２６は、あとで説明するように、引数の値
がキャッシングの候補であるかどうかを示す、実際にキ
ャッシュされた値はフィールド１２７に記憶される。良
好な実施例では、たとえ両ノード入力がキャッシングの
候補であっても、実行される所与の検査について入力の
一方だけがキャッシュされる。検査式は検査引数の１つ
の多数の検査値と共に用いることができる。これは（受
取った変更ｌ・−クンから取出された）引数値の反復使
用−該引数値は向かい合っているメモリに記憶された多
数の引数値に対する前記反復検査のためキャッシュされ
ることになっているーを必要とする。

プログラム１１により、アルファ分配ノード３５の１つ
からロジック・ライン５０を介して、変更１ヘークンが
押込まれる毎に、一定のベータ・ノード３７が更新され
る。前記更新は特定の結合ノー１−における変更トーク
ンから得られた引数、及び”向かい合っている”先行メ
モリ・ノードにおけるＲＥＴＥに記憶された特定のトー
クンから得られた引数の両者による検査の実施を必要と
することがある。向かい合っているメモリはＲＩ−（Ｓ
の先行する部分一致トークン・メモリである。変更トー
クンがアルファ分配ノー１−３５からノード４０の入力
に押込まれると、プログラム１１により、ノード４０で
、ＲＩＩＳトークン入力（本明細書ではデルタ入力とも
呼ばれる）と向かい合っている即ち１．、　Ｉ（Ｓノー
ド入力におけるメモリの間で検査が実行される（該検査
は定義されノード４０の一部となる）、実際には、この
メモリは、物理的にＬ　ＨＳノード入力にではなく、Ｌ
Ｈ８先行ノードに置かれる。

本発明に従って、結合ノードに存在していることがある
パターン検査の引数のアクセス経路特性が解析される。

パターン検査に対する引数が結合ノードへのデルタ変更
入力にだけ依存し、向かい合っているメモリからのどの
ＷＭＥ値にも依存しないことが決定されると、その引数
の算定値は特有のフィールド１２７にキャッシュされる
。前記キャッシング動作は属性検査に対する引数値の計
算結果を保管し、次に実行される検査−変更トークン引
数値と、′向かい合っている”メモリの部分一致トーク
ンとの間の反復する即ちループ比較を含む−に関する当
該値の次の再計算を排除する、このキャッシングはＷＭ
Ｅ値の先行１ヘークンにおけるアクセスを少なくし、パ
ターン・マツチング速度を高める。キャッシュされた値
は該向かい合っているメモリとの結合ループ比較動作の
期間中維持される。

結合ノードにおけるパターン検査の引数はＬ　Ｈ３，Ｒ
Ｈ８又は両方のノード入力に到来するＷＭＥからの値を
必要とすることがある。この決定は一度行われることが
あり、そのときＲＥ　Ｔ　Ｅ構造がパターン−政体様か
ら構築される。（Ｒ１−（Ｓ又は１．、　ＨＳのどちら
か）１つのノード入力側からの値にだけ依存する引数は
変更トークンが同じ側から到着するときキャッシュする
ことができる。

いったんＲＥ　Ｔ　Ｅが設定又は変更されると、パター
ン一致検査を有する全てのノードのパターン一致検査引
数アクセス経路を解析することにより、キャッシング候
補が決定される。キャッシング候補はパターン検査の引
数毎に自宅的に設定される。

どの結合ノードにおいても前記パターンがないこともあ
り、１つ以北の結合パターンがあることもある。引数ア
クセス経路は、トークンで識別された特定のＷ　Ｍ　Ｅ
に達する少なくとも１つの経路を、トークン・トリー（
１；　ｒ　ｅ　ｅ　）を介して指定する。いったん特定
のＷＭＥが特定の１〜−クンから選択されると、アクセ
ス経路は選択されたＷ　Ｍ　Ｅで識別されたＥ性に対す
るアクセスを含む１部分一致１ヘークンは一般にｎ個の
ＷＭＥの集合であって、前記ｎ個のＷ　Ｍ　Ｅの集合の
間の部分パターン一致を表わし、ＲＥＴＥにおけるその
時点までのパターン・マツチング検査を満足する。

良好な実施例では、ｎ個のＷＭＥの集合はＲＥＴＥにお
けるそれぞれの結合ノードのトリーに並行する構造を有
する２進トリーとして記憶される。

パターン・マツチング検査における特定の引数は１つの
ＷＭＥにある１つの値だけを参照することがしばしばあ
る。このような場合、参照されるＷＭ　ＥがＴ−ＨＳノ
ード入力における部分一致トークン（そこに到着するデ
ルタ変更、即ちＬＩＩＳ先行ノードの部分−Ｍメモリ１
．０４からのトークン）を介してみつかると、該引数は
フィールド１２６で′Ｌ″と記録される。検査における
引数が多数のＷＭＥ値を参照すると、全ての前記値はＬ
　Ｉ（Ｓノード入力を介してアクセスされる。この引数
もフィールド１２６で　１Ｌ”と記録される。同様に、
もし引数の全てのＷＭＥ値がＲＨＳノード入力を介して
アクセスされると、その引数はＲ”と記録される。引数
が両［、Ｈ８及びＲＨ３のアクセス可能なＷＭＥからの
値を含むときは、該引数はｎｏｔ　ｃａｃｈｅａｂｌｅ
″（キャッシュ不可能）と記録される。これらの記録は
記号である。ある実施例では、普通の符号化された表示
が該記号値を表わすのに用いられる。前記記録は（アク
セス経路の解析が終った後）ＲＥＴＥが構築されるとき
１回だけ行われる。それぞれの結合ノードにおける両ノ
ード入力のフィールド１２６の内容はパターン・マツチ
ングの間に用いられ、該記号値のキャッシングを選択的
に実現する。

第３図及び第４図は結合ノードにおける値のキャッシン
グに関連する計算機動作を示す、第３図は全体の順序を
示し、第４図はキャッシュ動作及び非キャッシュ動作を
用いる引数の取得を示す。

ステップ１．５０で、変更１〜−クンをノード入力、Ｌ
　１ｆＳ又はＲ）（Ｓのどちらかで受取る。動作のシー
ケンスは、ノー１−の側が通である以外は、どちらの入
力の場合にも同じである。ステップ１５１で、（前記定
義されたような）結合ノードは、受取った変更トークン
及び向かい合っているメモリ中の部分一致トークンに関
して実行される検査（検査の数は検査Ｏから任意の数の
検査まで変ることがあり、その各は検査されるへき多数
の引数値を有することがある）についても調査される。

ステップ１５２で、もし検査が見つからないなら、プロ
グラム１１は本発明の記述範囲を越えた他の計算機動作
に進む、さもなければ、実行される検査はステップ１５
４で開始され、キャッシュ値フィールド（ＡＲＧＩの１
２７．ＡＲＧ２については図示せず）は消去即ちリセッ
トされる。ＬＩ−１８が受取った変更トークンの向かい
合っているメモリは右の先行ノードにおけるメモリであ
り、Ｒ１−（Ｓが受取った変更１ヘークンの場合は、左
の先行）−ドにおけるメモリである。ステップ１５４に
続いて、検査を実行する検査ループ１６０が開始される
。ステップ１６１及びステップ１６２で、検査の引数Ａ
ＲＧＩ及びＡＲＧ２が、第４図に示すように、引数毎に
取得され計算される１次に、ステップ１６３で、検査が
実行される。ステップ１６５で、プログラム１１はそれ
以上の検査を実行すべきかどうかを判定する。実行され
た最後の検査が失敗したとき、又は全ての検査が首尾よ
く終了したときは追加の検査は行われない、それ以北の
検査が行われない場合、結合ノードを去り、本記述の範
囲外の他の動作に進むのに関連する技術的に既知の計算
機動作のため、制御は図示の計算機動作のセットから脱
出（ｅｘｉｔ）する、それ以りの検査が行われるときは
、プログラム１１は、ステップ１６６で、次の検査を指
定し、検査ループ１６０がもう一度反復される。

ステップ１６１及び１６２で実施される計算機動作は第
４図に示され、ＡＲＧＩのフィールド１２６のキャッシ
ュ許可値又はＡＲＧ２のキャッシュ許可値を調べるステ
ップ］、　７０で開始される。

このキャッシュ許可値はＬ”、′Ｒ”又は　ｎｏｔｃａ
ｃｈｅａｂｌｅ”である、ＬはＬ　ＨＳノード入力（例
えば、ＡＲＧＩ）がキャッシングの候補であることを表
わし、ＲはＲＨＳノード入力（例えば、Ａ　ＲＧ２）が
キャッシングの候補であることを表わす。

ｎｏｔ　ｃａｃｈｅａｂ、ｌｅはどちらの引数もキャッ
シングの候補ではないことを表わす、　ｎｏｔ　ｃａｃ
ｈｅａｂｌｅが受取った変更トークンに関して感知され
ると、引数を取得し計算する従来技術のシステムが用い
られる。従来技術はループ１６０の反復毎にプログラム
１１がステップ１７１で現在の引数の引数値を取得し計
算することを必要とする。受取った変更トークンのキャ
ッシングが許可されると、プログラム１１は、Ｒ及びＬ
の表示を、ノードが変更トークンを受取った側と一致さ
せる。ステップ１７３では、値ＲはＲＮ−（Ｓ入力変更
トークンの側と比較され、ステップ１７４では、値■、
はＬ　）（Ｓ入力変更トークンの側と比較される。もし
不一致があれば、キャッシングは実行されず、再び、ル
ープ反復毎に引数値を取得し計算する従来技術の方法が
用いられる。プログラム１１はステップ１７４からステ
ップ１７１に進み現在の引数の引数計算を実行する。不
一致がないものと仮定すると、ステップ１７５で、プロ
グラム１１は引数取出し及び計算が現在の引数の最初の
パスであるかどうかを判定する。もしそうなら、ステッ
プ１７７で。

現在の引数が取出され計算される。これはステップ１７
１の従来技術の動作と同じである。計算が終ですると、
ステップ１７７で計算された値は、次の検査の反復で用
いるため−もちろん、現在の検査でも用いられる一固有
のＡＲＧＩ又はＡＲＧ２のキャッシュ値フィールドにキ
ャッシュされる（ステップ１７８）、次の反復では、従
来技術におけるような引数値を計算するよりも、ステッ
プ１８０で、キャッシュ値はキャッシュ値フィールドか
ら取得され検査に用いられる。ステップ１７５で、プロ
グラム１１は、その引数取出し及び計算が最初のパスで
はないと判定されると、キャッシュ値が既に存在してお
り、使用可能であることを知る。

Ｅ１発明の効果 本発明によればループ中、変数トークンｒノｊ数の供給
した値が一定であるときに、その値をキャッシュし、後
続のテスト繰り返しにおいて利用し、再計算を不必要に
している。したがって処理ノ高速化を図ることができる
。

【図面の簡単な説明】

第１図は本発明を良好に実施することができるＲ　Ｅ　
Ｔ　Ｅネットワークのｆｆｆｆ略図である。 第２図は第１図に示したネットワークに本発明を実現す
るのに使用可能ないくつかのデータ構造の簡略図である
。 第３図及び第４図は図示されたネットワークで本発明を
実現するための任意の結合ノードで使用可能な計算機動
作を示す簡略化された流れ図である。 １１・・・・プログラム、１３・・・・内部メモリ、１
５・・・・ワーキング・メモリ、２ｏ・・・・メモリ領
域、３０・・・・根ノード、３：３・・・・アルファ・
マツチング・ノード、 ３５・・・・アルファ分配ノード。 ・・・・ベータ ノード。

Claims (1)

1. 【特許請求の範囲】 複数のパターン・マッチング・ノードを含み、これらノ
   ードが論理パスにおいて論理的に相互接続されて種々の
   先祖ノードから引数を受けとるようにされているパター
   ン・マッチング・ネットワークを更新する方法において
   、 予め定められた１のノードにおいて、一組の先祖ノード
   からの変更トークンを当該ノードの第１の入力に供給し
   て当該ノードを更新するステップと、 上記予め定められた１のノードの第２の入力に論理的に
   結合された１の先祖ノードにおいて複数のパターン・マ
   ッチング・トークンをストアするステップと、 実行されるべきテストの各々において、１のテストのテ
   スト繰り返しの間に上記変更トークンが値を変更させる
   かどうかを表示するステップと、上記変更トークンと上
   記第２の入力で利用可能な部分マッチ・トークンとの間
   に実行されるべきテストがあるかどうかを上記予め定め
   られた１のノードにつき検査するステップと、 上記検査の結果、テストがないと判別されたときに他の
   マシーン操作を実行するステップと、上記検査の結果、
   テストがあると判別され、かつ上記１のテストの間に値
   の変更がないときに上記テストの第１の繰り返しに対し
   変更トークン値を計算し、当該変更トークン値を上記ノ
   ードについて一時記憶し、上記テストの後続の繰り返し
   について上記一時記憶した変更トークン値を用いるステ
   ップと、 上記検査の結果、テストがあると判別され、かつ上記１
   のテストの間に変更があるときに、上記の１のテストの
   各繰り返しにおいて変更トークン引数値を計算するステ
   ップとを有することを特徴とする パターン・マッチング・ネットワーク更新方法。