JPH02224127A - パターン突合せネットワークの併合方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 Ａ、産業上の利用分野 本発明はパターン突合せネットワークに関し、詳細には
そのようなネットワークと、モジュール式に変更可能な
ネットワークを含む合成ネットワークとを組み合わせる
方法、及びパターン突合せネットワークの所定の部分を
要求に応じて更新する方法に関するものである。

Ｂ、従来の技、術 フォージー（Ｆｏｒｇｙ）　によって教示されたＲＥＴ
Ｅなどの、いわゆる人工知能またはパターン突合せプロ
グラミングが、最近の数年間に開発され使用されてきた
。ＲＥＴＥアルゴリズムは、１組または数組の突合せ規
則を使用する、いくつかのパターン突合せ手法の１つで
ある。これらのプログラムは周知のものである。これに
ついては、たとえばＡＲＴＩＦＩＣＩＡＬ　ＩＨ置ＬＩ
ＧＥＮＣＥＸＶ　ｏ　１　、　１９（１９８２年）、り
り、１７−３７に所載のチャールズ・Ｌ・フォージーの
論文ｒＲＥＴＥ　：多数パターン／多数オブジェクト・
パターン突合せ問題用の高速アルゴリズム（ＲＥＴＥ：
Ａ　Ｆａｓｔ　Ａｌｇｏｒｉｔｈｍｆｏｒ　　ｔｈｅ　
　Ｍａｎｙ　　Ｐａｔｔｅｒｎ／Ｍａｎｙ　　０ｂｊｅ
ｃｔ　　ＰａｔｔｅｒｎＭａｔｃｈ　Ｐｒｏｂｌｅｍ）
　Ｊの記載を参照されたい。当技術分野における他の公
知例は、マーシャル・シ望ア（Ｍａｒｓｈａｌｌ　５ｃ
ｈｏｒ）他の論文ｒＲＥＴＥパターン突合せにおける進
歩（Ａｄｖａｎｃｅｓ　ｉｎ　ＲＥＴＥＰａｔｔｅｒｎ
　Ｍａｔｃｈｉｎｇ）　Ｊ　、ＰＲＯＣＥＥＤＩＨＧＳ
　ｏｆ　１９８６ＡＭＥＲＩＣＡＮ　ＡＳＳＯＣＩＡＴ
ＩＯＨｆｏｒ　ＡＲＴＩＦＩＣＩΔＬＩＨ置ＬＩＧＥＨ
ＣＥ　Ｃ０ＮＦＥＲＥＮＣＥ１１９８６年、ｐｐ。

２２８−２３２に出ている。ＲＥＴＥネットワーク及び
知能プログラミングについての周知の情報は、当業者が
本発明を理解するために必要なもの以外はここでは繰り
返さない。フォージーが述べているように、ＲＥＴＥと
して定義される、より大きくより複雑な性能と機能性を
高めるネットワークが重要性を増してきている。性能を
高めるのみならずパターン突合せネットワークの機能性
をも高めることが望まれる。

周知のように、このようなパターン突合せプログラミン
グは多数のデータ構造で実行される。作業用記憶素子（
ＷＭ　Ｅ　）は入力データ構造である。

新しいＷＭＥ１変更されたＷＭＥ、または除去されたＷ
ＭＥはどれも「トークン」　（またはデルタ）をもたら
す。トークンとはある関連データ操作と共に１つまたは
複数のＷＭＥからなるデータ構造である。ＲＥＴＥの現
在の情報内容はＷＭＥの追加、変更または削除を反映し
ないので、ネットワークを通じてトークンを伝搬させる
ことによって、入力の現情報状態を反映するように、Ｒ
ＥＴＥを更新する必要がある。トークンがＲＥＴＥを通
じてブツシュ（処理）され、ＲＥＴＥ内でパターンと突
き合わされる各回がパターン突合せ動作となる。

フォージーによって教示されるように、ＲＥＴＥはアル
ファ部とベータ部からなる。変更トークンがＲＥＴＥを
通じて処理されたとき、新しいＷＭＥまたは変更された
ＷＭＥの情報内容、または削除されたＷＭＥによる情報
変更が、「ルート・ノード」を経てネットワークに使用
可能になった後、まずアルファ部を通過する。ルート・
ノードはＲＥＴＥへの入口点であるネットワークのデー
タ域である。１組の「トップ」ノードが、ルート・ノー
ドに接続されている。トップ・ノードは°次々に後続ノ
ードに接続され、最終的にはプロダクション（推論）ノ
ードまたはマツチ・ノードと呼ばれる多数の終端ノード
またはボトム・ノードに達する。各ノード・データは、
入ってくるトークンに対する突合せテストを含むことが
できる。当技術分野で周知のように、ノードのいくつか
はテーブル中に走査すべき記憶項目を有する。これらの
ノードは「記憶ノード」と呼ばれる独立のノードとして
実施することができ、またテーブルを突合せ動作を表す
ノードに直接関連づけることもできる。

特定ノード用の関連する記憶テーブルを、ノードの「結
果記憶域」と呼ぶことにする。結果記憶テーブルは、ベ
ータ・ノード及び後述のアルファ配布ノードと関連づけ
られる。

記憶項目用のテーブルは、ネットワーク内のその点まで
の部分突合せ結果を表す値（数値、テキストなど）を含
む。これらの値はその後の突合せ動作で「結合」ノード
への入力の１つとして使用できる。テーブルへのアクセ
スは通常のプログラミング手順に従って行ない、また突
合せ動作は通常のプログラミングで行なわれる比較であ
ることを理解されたい。

ＲＥＴＥのアルファ部は、結果記憶域、すなわち部分パ
ターン突合せ結果が記憶されるテーブルを持たないが、
これに対してベータ部はそのようなテーブルを含む。ア
ルファ部とベータ部の間にアルファ配布ノードと呼ばれ
るノードがあるが、これらのノードはすべて、アルファ
部で生成された部分パターン突合せ結果を記憶する結果
記憶域を有する。これらのアルク１配布ノードから、ト
ークンはベータ部にブツシュされる。「ブツシュされる
」という言葉は、プログラムがブツシュされるトークン
の情報内容を使って、後続ノードでパターン突合せ動作
を実行することを意味する。

ＲＥＴＥで使用されるノードには、入力接続数からいっ
て、１人カノードと２人カノードの２種がある。すべて
のアルファ・ノードは、（後述のプロダクション・ノー
ドまたはマツチ・ノードと同様に）アルファ配布ノード
と同じく１人力を有する。このような１人力をｒＲＨ８
入力」または単に「入力」と呼ぶことにする。これに対
してほとんどのベータ・ノードは、プロダクション・ノ
ード、マツチ・ノードまたは他の特殊目的ノードを除き
、２つの入力、すなわち左側（ＬＨ８）と右側（ＲＨ８
）の入力を有する。この２つの入力は、結合テスト（テ
ストが行なわれないこともある）に合格した（各側から
の入力からなる）トークンの対が結合されて、結合ノー
ドの関連する結果記憶テーブルを更新するために使用さ
れる新しい融合したトークンとなるので、「結合ノード
」と呼ばれる。

ＲＥＴＥアルゴリズムは、ＷＭＥの追加、修正または削
除を表す変更トークンで始まる。次いで、アルゴリズム
を実行するプログラムは、変更トークンの内容を必要に
応じて当該アルファ・ノードの突合せ情報項目と突き合
わせするために複数のアルファ・ノードを走査する。す
なわち、各アルファ・ノードは、トークンで表されるＷ
ＭＥの種々の態様をテストし、トークンをアルファ・ノ
ードの様々な後続ノードにパスするか、またはそこでブ
ロックする（パスしない）。この動作は、従来技術で周
知のように、アルファ・ノード部の下底に達するまで継
続する。この時点で、アルファ・ノードのテストが成功
したと想定すると、最初の結果記憶域（アルファ配布ノ
ード）はトークンを受は取り、ＷＭＥ操作（追加、修正
、削除）の種類に応じてその記憶域を更新することがで
きる。

一方、トークンのテストが不合格の（一致しなかった）
場合には、トークンのパスがアルファ部の下底にまで達
しないことがある。トークンをパスするには、周知のよ
うに複数の論理経路が必要となることがある。このパタ
ーン突合せ動作に続いて、ＲＥＴＥのベータ部がＲＥＴ
Ｅ動作を継続する。

原型ベータ結合ノードの１人力に達するトークンでは、
そのノードは、トークンの内容と、結合ノードの反対側
の入力にソース・ノードとして論理的に接続されている
先行ノードにある結果記憶域に含まれる１組の部分突合
せトークンとの間のパターン突合せ機能を指定する。次
いで、プログラムは、結合ノードで定義されるように、
トークンと結果記憶域の間でテストを行なう。この結果
記憶域は「反対側記憶域」と呼ばれる。

ＲＥＴＥは、１組のパターン突合せ規則からコンパイル
される。各規則はＲＥＴＥを通るルート・ノードから出
力ノードまでの論理経路を定義する。

規則で定義されたＲＥＴＥを通る経路は、一般にかなり
複雑になっている。したがって現在の所、ＲＥＴＥは、
−度コンパイルされると、結果記憶テーブルの更新を除
いては、比較的静的な構造となる。ＲＥＴＥ及び他のパ
ターン突合せネットワークをよりフレキシブルで変更可
能なものにすることが望ましい。

一般に前述のＲＥＴＥは、併合されるＲＥＴＥが、可能
ならば併合の相手方ＲＥＴＥとノードを共用し、一方新
しいＲＥＴＥの併合不能で従って共用されない部分は、
併合の相手方ＲＥＴＥ内の既存の結果記憶域からの部分
突合せ情報で正しく初期設定されるように、新しいＲＥ
ＴＥ部分を正しく併合する能力を示さない。新しいパタ
ーン突合せネットワーク全体を再コンパイルし次いで更
新することなしに、要求主導型の動的変更ができるよう
に、パターン突合せネットワークの機能性を高めること
が望まれる。

ダン・スケールズ（Ｄａｎ　５ｃａｌｅｓ）の論文「Ｓ
。

ＡＲ１０ＰＳ５７”ロダクシ日ン・システム用の効率の
良い突合せアルゴリズム（Ｅｆｆ　ｉｃｉｅｎｔＭａｔ
ｃｈｉｎｇ　Ａｌｇｏｒｉｔｈｍｓ　ｆｏｒ　ｔｈｅ　
５ＯＡＲ１０ＰＳ５Ｐｒｏｄｕｃｔｉｏｎ　Ｓｙｓｔｅ
ｍ）　Ｊ　、スタンフォード大学コンピュータ科学部技
術報告書（ＳｔａｎｆｏｒｄＬｌｎｉｖｅｒｓｉｔｙ　
Ｔｅｃｈｎｉｃａｌ　Ｒｅｐｏｒｔ　ｏｆ　ｔｈｅＤｅ
ｐａｒｔｍｅｎｔ　　ｏｆ　　Ｃｏｍｐｕｔｅｒ　　５
ｃｉｅｎｃｅ）Ｎ　　１　９　８　６　年の報告によれ
ば、従来の０ＰＳ５／ＲＥＴＥは、前述のように効率を
高められた。この教示は、要求主導型のまたはモジュー
ル式に更新可能なパターン突合せネットワークを教示も
示唆もしていない。

Ｃ０発明の要旨 本発明の目的は、パターン突合せネットワークにおいて
要求主導型パターン突合せを実現することである。

本発明の他の目的は、入カバターン突合せデータ構造と
既存パターン突合せネットワークの効率的で高速の併合
を実現することである。

２つのパターン突合せネットワークを併合すると、既存
のネットワークに、新たに加えられた構造（ここではノ
ードと呼ぶ）のいくつかを併合し、新たに加えられたが
併合不能なすべてのノードを接続することによって、加
えられるデータ構造の数が最小限になる。修正されたネ
ットワークを更新すると、パターン突合せ結果の重複も
欠落もない、正しい結果が生成される。

本発明の他の目的は、突合せパターンの出所に応じて各
種の併合モードを提供することである。

突合せパターンの出所は、規則の条件部分（一般に「規
則のＬＨ８部分」と呼ばれる）でも、活動部分の作業か
らくる要求時パターン突合せ構造でもよい。修正された
ネットワークの更新によって、パターン突合せ結果の重
複も欠落もない、正しい結果が作成される。

本発明の他の目的は、突合せパターンの出所に応じた各
種の併合モードを提供することである。

突合せパターンの出所は、規則の条件部分（一般に「規
則ＬＨ８部分」と呼ばれる）でも、規則の活動部分また
は任意の手順プログラミング・コードから来る要求時パ
ターン突合せ構造でも、トップ・レベル、すなわちある
ユーザによって入力された再使用の可能性のない要求時
パターンでもよい。

併合のスパン（持続時間）は「永久的」でも「−時的」
でもよい。既存のＲＥＴＥと永久モードで組み合わされ
た新しいＲＥＴＥ　（ミニＲＥＴＥと呼ぶことにする）
は、その結果得られる併合ネットワークの不可分の部分
となる。一方、既存ＲＥＴＥに一時モードで接合された
ミニＲＥＴＥは、要求時にのみ使用可能である。これら
のＲＥＴＥの未併合部分は、併合の相手方ＲＥＴＥと永
久的には接続されない。−時的併合では、併合されたＲ
ＥＴＥの再使用の可能性に応じて、シナプス・ノードが
保管されることも保管されないこともある。たとえば、
トップ・レベルのパターン突合せ要求は、保管されない
シナプス・ノードを生成し、一方規則の活動部分にある
要求時パターンは保管される。

Ｄ、実施例 添付の各図面をさらに詳しく参照するが、各図で、同じ
参照番号は、同じ部品及び構造上の特徴を示す。後述及
び前述のプログラミング・ステップを実施するための周
知のプログラミング言語は、”Ｃｏｍｍｏｎ　　ＬＩＳ
Ｐ”である。これについては、ガイ・Ｌ・スティール・
ジュニア（Ｇｕｙ　Ｌ。

５ｔｅｅｌｅ、　Ｊｒ、）、ｒｃＯＭＭＯＮ　　ＬＩＳ
ＰＪ、Ｄｉｇｉｔａｌ　Ｐｒｅｓｓｘ　　１９８４年、
（ＱＡ７６．７３．Ｌ２３５７３１９８４　ｌ５ＢＨＯ
−９３２３７６−４１−Ｘ）を参照のこと。既知のＲＥ
ＴＥアルゴリズムは、ブラウンストーン（Ｂｒｏｖｎｓ
ｔｏｎｅ）、ｒＯＰｓ５によるエキスパート・システム
ノフロクラミング（ＰＲＯＧＲＡ１４１４ＩＮＧ　ＥＸ
ＰＥＲＴＳＹＳＴＥＭＳ　Ｉ）ｌ　０ＰＳ５）　Ｊ　、
Ａｄｄｉｓｏｎ−ＷｅｓｌｅｙＰｕｂｌｉｓｈｉｎｇ　
Ｃｏｎ＋ｐａｎｙ１１９８５年、ｐｐ、２２８−２３９
に記載されている。従来のパターン突合せシステムなら
びにその好ましい実施例は、ディジタル・コンピュータ
（図示せず）を使用し、パターン突合せネットワークの
骨格を構成するデータ構造が、ディジタル・コンピュー
タの記憶域部分に記憶されるものである。すべての図は
、本発明が理解できるように、記憶された構造の一部を
詳細に示している。

第１図では、ＲＥＴＥＩＯが作業用記憶域１１に対する
変更によって（周知のようにプログラムの実行を介して
）論理的に駆動される（作業用記憶域１１は、ＲＥＴＥ
システムの制御データ及び入力データ要素を記憶するた
めのディジタル・コンピュータのプログラム指定部分で
ある）。制御データ及び入力データは、作業用記憶要素
（ＷＭＥ）と呼ばれ、矢印１３で示すように作業用記憶
域１１に受は取られる。ＷＭＥは、作業用記憶域１１に
追加し、そこから削除し、またはその中で変更すること
ができる。このような追加、削除、または変更の結果、
作業用記憶域１１の内容が、ＲＥＴＥ　１０の現状況と
は異なるようになる。ＲＥＴＥ　１０は後述する記憶ノ
ードに部分パターン突合せ結果を記憶することを銘記さ
れたい。作業用記憶域１１とＲＥＴＥ　１０の間のこの
相違またはデルタは、当技術分野で周知のように、「ト
ークン」によって表される。トークンは１つのＷＭＥに
対する１回の変更（追加、更新、または修正）を表す。

トークンは、矢印１５で示すように、プログラム制御に
よって作業用記憶域１１からＲＥＴＥＩＯのルート・ノ
ード２０に転送される。トークンがルート・ノード２０
に入ると、周知のＲＥＴＥプログラム（図示せず）がト
ップＲＥＴＥ入カノード（第３図に示すアルファ部デー
タ構造）２１Ａ−２１Ｃを走査する。実際の実施例では
、このようなＲＥＴＥ入カノードが多数存在することも
ある。トークンがＲＥＴＥノードのいずれかに関連する
パターン突合せテストに合格すると、パターン突合せ動
作はそのＲＥＴＥノードからＲＥＴＥ内を下方に進む。

たとえば、ノード２１Ｂでの突合せの結果、次にノード
２２Ｂでパターン突合せ動作が行なわれる。アルファ・
ノード２１Ａ−２１Ｃ及び２２Ａ−２２Ｃは、前述のフ
ォージーによって教示されたＲＥＴＥのアルファ部を表
す。このようなアルファ部では、単一のＲＥＴＥ入カノ
ードから、スペース２３で図式的に示したアルファ・ノ
ードのいくつかの階層または層が走査される。アルファ
部の論理的下底は、１組のアルファ配布ノード２４Ａ−
２４Ｄから構成される。図示された実施例で部分パター
ン突合せ結果を記憶しないアルフＴ・ノードは、周知の
ようにパターン突合せ動作を実行する。アルファ・ノー
ドでパターン突合せテストに合格したトークンは、ＲＥ
ＴＥのアルファ部の下限でそれぞれ終端するアルファ配
布ノードに記憶される。

アルファ配布ノード２４Ａ−２４Ｄは、ＲＥＴＥ内で結
果記憶域を有する一番上の（論理的にルート・ノード２
０に最も近い）ノードである。これらのノードは、後述
するようにベータ・シナプス・ソース・ノードとして指
定することができる。

ベータ・ノードと呼ばれる、論理的にアルファ配布ノー
ドの下にあるノードのすべてが、ＲＥＴＥのベータ部を
構成する。多くのベータ・ノードは、２つの入力を有す
る結合ノードである。各結合ノードは、ベータ結合ノー
ド２５Ｄについて図示しであるように、ＬＨ８入力とＲ
Ｈ８入力を有する。他のベータ・ノード２５Ａ−２５Ｃ
も、図示した各ベータ・ノードの横の当該の省略水平線
で示すように、同様の入力を有する。変更トークンはＬ
Ｈ８入力とＲＨ８入力のいずれかを通って、結合ノード
にパスすることができる。パスされたトークンは、結合
ノード中で指定された述語テストを用い、反対側記憶域
（反対側の入力（すなわちＲＨ８またはＬＨ８）に接続
された先行ノードの結果記憶域）からの複数の引数値と
比較される、１組の引数値を構成する。すべてのテスト
に合格した場合、トークンは適切な後続ノードにパスさ
れる。

ＲＥＴＥ　１０の下限または下底境界は、いわゆるプロ
ダクシロン・ノードを含む出力ノード２８Ａ−２８Ｄか
ら成る。これらの出力ノードを除き、ＲＥＴＥ内のすべ
てのノードは、後続ノード（現ノードの走査の後に続く
パターン突合せ動作でＲＥＴＥプロラムによって走査さ
れるノード）を持つことができる。先行ノードとは、所
与のノードの走査より前に走査されるノードである。ア
ルファ・ノードは、その当該のアルファ配布ノードの先
行ノードである。ベータ・ノードは、アルファ配布ノー
ド及びアルファ・ノードの後続ノードである。ベータ・
ノードは、他のベータ・ノードの先行／−ドとなること
ができる。パターン突合せテストで使用されるデータ、
実際のデータ構造及びテスト定義は、すべてデータ域ま
たは記憶域１６に記憶される。ＲＥＴＥのデータ内容は
、データ域１６に、適切なデータ構造を指すポインタを
含む。

本発明の１態様によれば、１つまたは複数のミニＲＥＴ
Ｅまたはミニ・ネットワーク１８が、既存ＲＥＴＥ、元
のＲＥＴＥ、または主ＲＥＴＥと呼ばれるＲＥＴＥ　１
０に併合または接合される。

後述する一点鎖線構造は、そのような併合、及び好まし
い実施例の併合プロセスの要求時パターン突合せ（後で
説明する）を簡略して示したものである。ミニＲＥＴＥ
は、規則から構築されたＲＥＴＥなど、様°々なパター
ンに対応する独立に構築されたＲＥＴＥネットワークで
ある。

本発明の１態様によれば、「シナプス・ノード」と呼ば
れる１組の特殊ノードが、併合動作がＲＥＴＥ構造を変
更した後にＲＥＴＥの「延期」部分を更新する目的で生
成される。このような延期部分は、既存のＲＥＴＥ　（
主ＲＥＴＥとも称する）に接合されたノード、（後で明
らかになるように）選択的に更新されたノードなどであ
る。ＲＥＴＥの更新は「ソース・ノード」と呼ばれる１
組のノードまでさかのぼる。ＲＥＴＥの延期部分の最初
のノードは「ドレイン・ノード」と呼ばれる。シナプス
・ノードは、指定されたソース・ノードとドレイン・ノ
ードの間の結合を識別する。ＲＥＴＥの延期部分にある
ドレイン・ノードの後続ノードは、ＲＥＴＥに新たに接
合または付加され、まだＲＥＴＥの現在状況に更新され
てはいない。このようなシナプス・ノードは、ＲＥＴＥ
の延期部分に対するソース更新点（２つの入力結合ノー
ドの例では複数の点）を指定する。

結果記憶域中のデータ・テーブルは、ベータ結合メート
に記憶されたテスト定義に従って、ベータ結合ノード中
でトークン内容とパターン突合せ比較を行なうための、
引数値（数値、テキストなど、実際には任意の構造）を
含む。テーブルへのアクセスは通常のプログラミング手
順に従い、突合せ動作は通常のプログラミングで実施さ
れる比較であることを理解されたい。

ベータ部では、各結合ノードは２つの入力、すなわち左
側（ＬＨ８）入力と右側（ＲＨ８）入力を持つ。結合ノ
ードの出力は、入カドークンと、反対側結果記憶トーク
ンの間のパターン突合せの成功を表すトークンから成る
。

本発明の１態様によれば、２種類のシナプス・ノード、
すなわち「アルファ・シナプス・ノード」と「ベータ・
シナプス・ノード」が構築される。

これらのシナプス・ノードは、すでに計算されて既存の
ＲＥＴＥ内に存在する部分突合せ情報が共用されるよう
に、既存ＲＥＴＥに新しいＲＥＴＥが接続される、方式
と場所を識別する働きをする。

これらのシナプス・ノードは、ＲＥＴＥの延期部分を更
新するために使用され、併合動作によってＲＥＴＥ構成
が変更されている。

このような延期部分は、既存のＲＥＴＥに接合されたノ
ード、（後で明らかになるように）選択的に更新された
ノードなどである。ベータ・シナプス・ノードは１組の
ＲＥＴＥノードを識別する。

すなわち、各ベータ・シナプス・ノードは、１つまたは
２つの「ソース」ノードを「ドレイン」ノードと関連づ
ける。ソース・ノードは併合の相手方ＲＥＴＥ内のノー
ドであり、ドレイン・ノードは既存ＲＥＴＥと組み合わ
される新しいＲＥＴＥ中のノードである。アルファ・シ
ナプス・ノードは、後述のように、ミニＲＥＴＥのトッ
プ・ノードを、その「ソース」が特定のトップ・ノード
に関連するＷＭＥであるドレイン・ノードとして識別す
る。

ＲＥＴＥの更新は、このようなシナプス・ノード中で識
別されたソース・ノードまでさかのぼり、ＲＥＴＥの延
期部分にある後続ノードは（ＲＥＴＥ内の新たに接合ま
たは追加されたノードを含めて）　、ＲＥＴＥの現状況
に更新されてはいない。

ソース・ノードはＲＥＴＨの延期部分に対するソース更
新点となる。

併合プロセスが完了すると、接合されたパターン突合せ
ネットワークは、併合中に作成された１組のシナプス・
ノード（ソース・ノードをドレイン・ノードに接続する
ノード）を使って更新される。更新アルゴリズムには２
種類ある。１つは送出の順序づけを必要としないもので
あり、もう１つは順序づけを必要とするが、最適化され
た性能を有するものである。第１の更新アルゴリズムは
、ソース・ノードが「停止」ノードとなり、ドレイン・
ノードが「再開」ノードとなるという、同時係属の特許
出願に記載されているような、汎用更新アルゴリズムで
ある。延期ＲＥＴＥのベータ部にあるソース・ノードと
その後続ノードは、ベータ・シナプス・ノードのリスト
によって識別される。第２の更新アルゴリズムは、トー
クン送出順序を指定することを必要とするが、空間と時
間の効率がより高い。この更新アルゴリズムによって、
実行プログラムは、まず後で定義する「左ソース・ノー
ド」　（ベータ・シナプス・ノードの一部）に記憶され
ているトークンを、汎用更新アルゴリズムにおけるシャ
ドウィングと右後続ノードへの送出を飛び越して、昇順
でドレイン・ノードに送る。

ノードからのトークンの昇順送出は、ホー・Ｓ・！Ｊ　
−（Ｈｏ　Ｓ、　Ｌｅｅ）他の同時係属の特許出願に詳
しく定義されている。アドレスされたベータ・シナプス
・ノードを介するネットワークの更新は、一番下のレベ
ルの左ソース・ノード（更新スヘキ延期ＲＥＴＥ中のす
べてのドレイン・ノードのうち一番下のレベルのドレイ
ン・ノードに論理的に接続されたソース・ノード）から
ドレイン・ノード（同時係属の特許出願では再開ノード
と称している）へのトークンの送出で始まる。左ソース
・ノードから接続されたドレイン・ノードへのトークン
の一連の昇順ブツシュによって、更新プロセスの第１ス
テツプが完了する。ドレイン・ノードの論理的順序は、
余分の探索努力なしに、併合アルゴリズムの副産物とし
て得ることができる。２つのドレイン・ノード間に明白
な順序がない場合は、この２つのドレイン・ノードへの
トークンの送出順序は任意である。第２ステツプとして
、アルファ・シナプスによって指定されるアルファ・ト
ップ（ソース）ノードに関連するＷＭＥが、その後続ノ
ードに任意の順序で送出される。最適化された更新アル
ゴリズムを使用すると、実行時間性能が向上する。

第２図は、好ましい実施例に従って、パターン突合せネ
ット、ワーク併合を行なうマシン動作を示す。マシン・
ステップ３０で、周知のように、突合せパターンが構築
されていると仮定する。第４図及び第６図は、このよう
な突合せパターンの結果を示している。このような突合
せパターンは、ある例ではＲＥＴＥの１つの規則を構成
するが、それだけに限定されるものではない。

突合せパターンからＲＥＴＥネットワークを構築するた
めの周知の方法を用いて、突合せパターンからミニ・ネ
ットワークが作成される。その結果得られるミニ・ネッ
トワークは、自己併合されてもされなくてもよく、どち
らも本発明でカバーされる。自己併合されたネットワー
クとは、より高いレベルのノード（すなわちルート・ノ
ードにより近いノード）が可能ならば共用され、その結
果、共用されたこれらのノードが複数の後続ノードをも
つようなネットワークである。

マシン・ステップ３２で、マシン・ステップ３１で作成
されたミニ・ネットワークが現ネットワークまたは既存
のネットワーク１０に組み合わされる。第１４図及び第
１５図に、併合処理の詳細を示す。併合の結果、現ネッ
トワーク１０は増補されて、修正されたネットワークま
たはＲＥＴＥ３４なり、要求時に情報を供給するために
使用される。併合ステップ３２の一環として、１組のシ
ナプス・ノード３３（第３図はこのようなシナプス・ノ
ードのデータ構造態様を示す）を作成することもできる
。シナプス・ノードは、同時係属の特許出願に記載され
ているように、ソース・ノードと呼ばれる一番下の併合
の相手方ノードと、延期ＲＥＴＥ部分への入口点でもあ
る、未併合ミニ・ネットワークの一番上の部分との間の
結合点を識別する。一番下の併合された元のＲＥＴＥノ
ードの後続ノード（ミニＲＥＴＥが併合された先の７−
ド）としては、併合される修正済ネットワークの当該の
一番下のノードに接続された、つまりミニＲＥＴＥノー
ドが併合された相手の一番下の既存ノードに接続された
、ミニＲＥＴＥ中のノードが含まれる。ミニＲＥＴＥか
ら接続された後続ノードはどれも、作業用記憶域１１中
のどのＷＭＥ活動からのどのパターン突合せ情報によっ
ても更新されていない。したがって併合後に、このよう
な後続ノードと作業用記憶域１１の現状況との間にデル
タまたは相違が生じる。「ソース・ノード」は更新され
た他の後続ノードを有する可能性がきわめて高いことに
留意されたい。このような他の後続ノードは、併合前に
はＲＥＴＥにあったか、または作業用記憶域の現状況に
更新されていた。更新ステップ４６では、生成されたば
かりのシナプス・ノード３３を使用して、上記のソース
・ノードまたは併合ノードから始めて、既存のＷＭＥデ
ータ１１によってまだ更新されていない併合されたミニ
ＲＥＴＥの後続ノードにトークンをブツシュし、後で明
らかになるように、１つまたは一連の各ノード中の一番
下の併合ノードすべての接合されたミニＲＥＴＥ後続ノ
ードを、すべてに更新する。このようなシナプス・ノー
ドは、ＲＥＴＥの「延期」部分中でＲＥＴＥノードを選
択的に更新するため、後述のゲート活動を提供するのに
も使用できる。

ＲＥＴＥ　１０内に示す破線のデータ構造は、修正ネッ
トワーク３４を部分更新する必要性を示すためのもので
ある。これらのプロセスの詳細を第４図ないし第１６図
に示す。いくつかの代表的な更新が示されている。たと
えば、ミニＲＥＴＥ　１８からのデルタＴ・ノード３７
は、アルファ・ノード２１Ａにその直接後続ノードの１
つとして接続されている。接合されたノード３７の出力
接続は、そのミニＲＥＴＥ内のノード３７の以前に存在
したノードまたは後続ノード（図示せず）であり、ノー
ド３７と共に、そのミニＲＥＴＥから更新されたＲＥＴ
Ｅまたはネットワーク３４に「接合ＲＥＴＥＪ部分とし
て運ばれる。ノード３７は、ＲＥＴＥ入カノード２ＬＡ
と併合された直前の先行ノードへの、ＲＥＴＥ入カノー
ド（図示せず）をミニＲＥＴＥ内に有していた。したが
って、ノード３７のミニＲＥＴＥ入カノードは、既存の
ＲＥＴＥ入力ノード２ＬＡに併合されて、廃棄された。

ノード２ＬＡの出力とノード３７の入力の間の接続は、
後述のいわゆる「併合リンク」により、ノード３７のミ
ニＲＥＴＥ先行ノードからノード３７へのリンクの切断
は「併合切断」と呼ばれる。

アルファ部併合の他の場合では、ミニＲＥＴＥは、併合
されるとＲＥＴＥ入カノードとなるトップ・ノード４１
、中間アルファ・ノード４２、アルファ配布ノード４３
、ベータ・ノード４４及び出力ノード（プログクシ１ン
・ノードまたはマツチ・ノードでもよい）４０を含む。

これらのノードのいずれも既存のＲＥＴＥノードのいず
れとも併合されていない。ベータ・ノード４４へのＬＨ
８入力は、ミニＲＥＴＥ　１　Ｂ内のベータ・ノード４
４のＬＨ８先行ノードと併合されたＲＥＴＥ　１０内の
ノードに接続される。ノード４０−４４については、図
示したノードでは併合は見られなかった。したがって、
これらのノードはすべてＲＥＴＥＩＯに加えられ、加え
られたノードは接合ＲＥＴＥ部分である。

特定のアルファ・トップ・ノードでは、ミニＲ、。

ＥＴＥのアルファ・ノードのすべてが既存の主ＲＥＴＥ
にうまく組み合わされていない場合、ミニＲＥＴＥ内の
部分的に組み合わされたアルファ部のトップ・ノードが
、アルファ・シナプス・ノードによってｔ旨定されたソ
ース・ノードになる。自己併合されたミニＲＥＴＥネッ
トワークでは、同じアルファ・トップ・ソース・ノード
を指定する複数のアルファ・シナプス・ノードが、トッ
プ・ノード１つ当りただ１つのアルファ・シナプス・ノ
ードが作成されるように、併合される。併合が可能かど
うかテストするためにミニＲＥＴＥのアルア１部を走査
する間に、アルファ配布ノードとの併合テストが成功し
た場合、ミニＲＥＴＥ内のアルファ配布ノードの先行ノ
ードからアルファ配布ノードに向う正方向ポインタが、
正しい突合せ結果を得るために除去される。

次に、たとえば記憶ノード３８が既存ＲＥＴＥのベータ
部に加えられるという例を考えてみる。

ノード３８の先行ノードが、元のＲＥＴＥ　（図示せず
）内の１つのノードとうまく併合されたベータ・ノード
である、すなわちミニＲＥＴＥ　１８内のノード３８の
先行ノードが主ＲＥＴＥ　１０内の既存ベータ・ノード
に併合されたと仮定する。したがって、ベータ・ノード
３８は、併合されたミニＲＥＴＥの一部分の一番上のノ
ードであり、ＲＥＴＥ　１０のどの既存ベータ・ノード
とも併合されなかったベータ・ノードである。ノード３
８は、全体で接合されたＲＥＴＥを構成する、ブロダク
シ日ソ・ノード（図示せず）またはマツチ・ノードのい
ずれかで終わる後続ノードのネットワークを有すること
がある。主ＲＥＴＥ内のノードとの併合リンクを有する
ミニＲＥＴＥ内のノードの直接先行ノードは、「最終併
合ノード」と呼ばれ、ミニＲＥＴＥ内の最終併合ノード
の後続ノードはすべて主ＲＥＴＥに併合できないことを
意味する。

たとえば、ミニＲＥＴＥ　１８内の７−ド３８の直接先
行ノードは、最終併合ノードである。ミニＲＥＴＥ内の
記憶ノードが既存ＲＥＴＥのどれかと併合されている場
合、後述するように、いわゆる「ベータ・シナプス・ノ
ード・トリプル」がＲＥＴＥＩＯの適切な更新を保証す
るために生成される。ベータ・シナプス・ノード・トリ
プルの各ノードは、第３図のシナプス・ノード５０とし
ての構造を持つ。いわゆる「併合プロセス」で、ミニＲ
ＥＴＥが検査されて、元のＲＥＴＥ内と同等なノードを
含むミニＲＥＴＥの順序づけられた１組の併合可能ノー
ドが確立される。このシーケンスは、併合プロセスによ
って作成される後述のシナプス・ノードの順序と配置に
影響を及ぼすので、重要である。ミニＲＥＴＥ内のノー
ドは、併合テストのため、あるノードの先行ノードを走
査して決定された順序で選択される。２人カノード（た
とえば、結合ノード）の場合、左側の先行ノードが右側
の先行ノードより先に走査される。トップ・ノードに達
すると走査は停止する。

走査で見つかったミニＲＥＴＥ内のトップ・ノードは、
既存の主ＲＥＴＥ　）ツブ・ノードと併合されているか
どうかテストされる。ノードは、同じパターン・テスト
機能を果たす場合、互いに併合させることができる。同
じパターン・テスト機能を果たすかどうか調べるための
ノードの比較は周知のアルゴリズムであり、現在、新し
いパターンの構築時に、それらのパターンのためにＲＥ
ＴＥを併合する目的で０ＰＳ５中で実施されている。

上述の分析と走査の目的は、トップ・ノードから出発し
て、ミ、＝ＲＥＴＥの下底ノードへと、併合がもはや不
可能になる点を探すことである。トップ・ノードが併合
可能な場合、その後続ノードがテストされる。すべての
７−ドが併合されるか、または併合不能なノードが見つ
かるまでそれを続ける。ノードの併合が発生した場合、
元のＲＥＴＥ内とミニＲＥＴＥ内のすべての先行ノード
も併合される。ノードの併合は、先行ノードによっての
み決定され、後続ノードは所与のノードの併合に何の影
響も及ぼさない。ベータ・シナプス・ノード・トリプル
は３つのノード、つます右ソース・ノード、左ソース・
ノード及びドレイン・ノードから成る。ベータ・シナプ
ス・ノード・トリプルの右及び左ソース・ノードは、そ
れぞれ主ＲＥＴＥ内の併合ノードを指し、一方ドレイン
・ノードは、ミニＲＥＴＥ内のノードを指す。併合切断
活動が発生する前は、ドレイン・ノードはミニＲＥＴＥ
内の最終併合ノードの直接後続ノードである。

最終併合ミニＲＥＴＥノードの先行ノード、及び最終併
合ミニＲＥＴＥノード自体はすべて併合されている。つ
まり、このような先行ミニＲＥＴＥノードは、結果とし
て得られる併合されたＲＥＴＥに組み込まれず、すでに
主ＲＥＴＥ内にある既存のＲＥＴＥ構造が同じ効果のた
めに再利用される。主ＲＥＴＥの併合ノードの直接先行
ノードは、このノードの併合によって変更されない、ミ
ニＲＥＴＥが主ＲＥＴＥに永久的に併合される／Ｎｌｌ
ターンを表す場合、併合される先の元のノードは、新し
い直接後続ノード、つまりミニＲＥＴＥ最終併合ノード
の直接後続ノードであるドレイン・ノードを受は取る。

すなわち、この直接後続ノードは、このとき延期または
接合されたＲＥＴＥ部分のトップ・ノードであるドレイ
ン・ノードになっている。

これは、併合より後まで維持され元のＲＥＴＥソース・
ノード（併合ノードとも呼ばれる）に接続されるために
分析される論理経路中のミニＲＥＴＥの最高レベルのノ
ードである。

併合されたミ＝ＲＥＴＥが、将来突合せが要求されたと
き要求時突合せ動作のため再現可能な要求時突合せパタ
ーンから構築されている場合、シナプス・ノードは永久
に記憶される。要求時突合せパターン接合が、新たに指
定されたドレイン・ノードを、主ＲＥＴＥノードの後続
ノードとして主ＲＥＴＥに永久にリンクすることはない
。この選択的論理接続は、要求時ネットワークに関連す
るパターン突合せ活動が、要求時データ変更以外のデー
タ変更が行なわれるときに処理されないようにする。

再現可能要求時ミニＲＥＴＥパターンでは、シナプス・
ノードを含む特別リンクが、延期部分の突合せパターン
が（再現可能要求時突合せパターンを含む）他のどのパ
ターン断片によってももはや使用されないときにはいつ
でも、延期部分を除外する計算を可能にする。このシナ
プス接続はこのような望ましくない突合せパターンの簡
単な削除を可能にする。新しい規則ＬＨ８（規則ＬＨ８
をＬＨ３Ｈ３入力同しないこと）及び再現不能な要求時
パターンを表すミニＲＥＴＥパターンの場合、シナプス
・ノードは、ＲＥＴＥの新たに追加または接合された部
分である延期ＲＥＴＥ部分を更新するために１度使用さ
れた後に、廃棄される。

というのは、ＲＥＴＥの新たに追加または接合された部
分の初期「ブライミング」が完了すると、そのようなシ
ナプス・ノードをさらに維持する必要はないからである
。

第３図は、本発明の説明に使用されるデータ構造を示す
。ＲＥＴＥまたは他の形式のパターン突合せネットワー
クの実際の実施例では、当技術分野で周知のように、さ
らに多くのデータ構造が使用されることを理解されたい
。ベータ・シナプス・ノード５０は、（接続シナプス・
ノードが使用されていないときの延期部分である）接合
されたＲＥＴＥの境界を識別する。シナプス・ノードは
、後で明らかになるように、元のまたは主ＲＥＴＥを、
要求時更新の実施及びその他の目的のための「ゲート」
として、接合されたＲＥＴＥに選択的に接続する。各ベ
ータ・シナプス・ノード５０は３つのポインタを有する
。第１フイールドＲＰＲＥＤ５１は右先行ノードを指す
ポインタを宵し、第２フイールドＬＰＲＥＤ５２は左先
行ノードを指すポインタを有し、フィールドＤＲＡＩＮ
５３はドレイン・ノードを指すポインタを有する。

フィールド５１または５２（ただし両方ではない）は、
その側のドレイン・ノードの先行ノードが主ＲＥＴＥ内
にないことを指示するゼロでもよい。

先行ノードがあるかもしれないが、「ゼロ」フィールド
５１または５２に対するそのような先行ノードは、ミニ
ＲＥＴＥ内にある。このような先行ノードは主ＲＥＴＥ
ノードと併合することができないので、主ＲＥＴＥ内に
残る。各アルファ・シナプス・ノードは、ベータ・シナ
プス・ノードとは異ナリ、アルファ・トップ・ノードを
指す単一のポインタを有する。したがって、アルファ・
シナプス・ノードはドレイン・ノードのみを指す。

ベータ・シナプス・ノード・フィールド５３によって指
されるドレイン・ノードは、主ＲＥＴＥノードに併合さ
れない、すなわち主ＲＥＴＥノードに併合することがで
きないミニＲＥＴＥ経路中の最高のノードである、ミニ
ＲＥＴＥのベータ・ノードを識別し、したがってこのド
レイン・ノードは接合された主ＲＥＴＥ内に残る。ベー
タ・シナプス・ノードによって指されるドレイン・ノー
ドは、それが結合ノードであるとき、２つのノード入力
、ＬＨ３Ｈ３入力Ｈ８入力を持つ。主ＲＥＴＥノードに
併合されなかったドレイン・ノードのすべての後続ノー
ドは、接合されたＲＥＴＥ内になければならない。すな
わち延期ＲＥＴＥ部分のメンバー・ノードとなる。

ミニＲＥＴＥが既存ＲＥＴＥに永久的に追加される新し
い規則を表す場合は、主ＲＥＴＥノードに併合できない
ノード列中の一番上のミニＲＥＴＥノードが、元のＲＥ
ＴＥの併合ノードの追加の直接後続ノードとなる。すな
わち、このような併合ノードは、ミニＲＥＴＥノードの
最終併合ノードが併合される先の主ＲＥＴＥノードであ
る。この実施例では、各アルファ・シナプス・ノードは
、作成されたミニＲＥＴＥ内のトップ・メートを指す。

主ＲＥＴＥのトップ・ノードは複数の直接後続ノードを
宵することができるので、ミニＲＥＴＥトップΦノード
へのアルファ・シナプス−ノード点ができると、主ＲＥ
ＴＥ内の既に初期設定されたＲＥＴＥへのトークンの伝
播を防止しながら、トークンを正しくミニＲＥＴＥ部分
に伝播させる方法がもたらされる。このようなアルファ
・シナプス・ノードは、修正されたＲＥＴＥ内の最終併
合アルファ・ノードにトークンをパスするために、ミニ
ＲＥＴＥの（恐らくは自己併合された）トップ・ノード
を指す。アルファ・シナプス・ノードがすべて、アドレ
ス可能な連係リスト中にあり、またベータ・シナプス・
ノードがすべて別のアドレス可能な連係リスト中にある
ことが好ましい。

各併合は、そのアルファ及びベータ・シナプス・ノード
用に別々のアドレス可能連係リストを有することができ
、またはすべてのアルファ及びベータ・シナプス・ノー
ド用に１つのリストを設け、シナプス・ノードによって
指示される種々の論理接続に対してリスト中でオフセッ
トを指示することもできる。更新ステップの後に、規則
ＲＨＳパターンから構築されたミニＲＥＴＥなど、その
ソースが再現可能な要求時パターン突合せであったミニ
ＲＥＴＥの場合を除き、シナプス・ノードはすべて廃棄
される。繰返し動作で使用される要求時突合せパターン
の場合には、作成された１組のシナプス・ノードが、後
で開始される更新動作のために記憶される。

新たに永久的に追加された規則パターンを表すミニＲＥ
ＴＥ１または（１回パターン突合せ要求など）再現性の
必要がない要求時パターン突合せ用に作成されたシナプ
ス・ノードは、１度だけ使用され、更新が完了すると廃
棄される。主ＲＥＴＥに併合された他のミニＲＥＴＥは
、その主ＲＥＴＥの永久部分となることができ、つまり
その主ＲＥＴＥに包含される（この結果得られる延期さ
れた部分を識別するシナプス・ノードは廃棄され、併合
されたミニＲＥＴＥはその元の主ＲＥＴＥの先行ノード
すべてを指すポイントを有する）。すなわち、併合及び
延期部分の最初の更新の完了後には、指定されたソース
・ノード及びドレイン・ノードは存在しない。

アルファ部ノード構造５８（ノード２１Ｃなど）は、デ
ータ構造をＲＥＴＥアルファ・ノードまたはトップ・ノ
ードとして識別するタイプ・フィールド６０を含む。ア
ルファ・ノードのＰＰＲＥＤフィールド６１は、その唯
一の直接先行ノードを指すアドレス・ポインタを記憶し
、一方トツブまたは入力アルファ・ノード・フィールド
６１は、このトップ・ノードに関連する入力ＷＭＥの識
別に適したＲＥＴＥまたは他のトップ情報のクラスの識
別を記憶する。ＰＰ０Ｍフィールド６２は、アルファ・
ノードに関連する固有のプログラム部分を指すアドレス
・ポインタを記憶する（このフィールドは空白でもよい
）。ＤＶＥＣフィールド６３は、すべての直接後続ノー
ドを指す１　ｔａｉｌのポインタで、ある（しかし通常
、アルファ・ノードはアルファ配布ノードを含むこさが
ある）。ＰＴＥＳＴフィールド６４は、実施すべきテス
ト用のポインタを記憶する（通常トップ・ノードではテ
ストは実施されない）。ベータ・ノード・データ構造６
Ｅｌ　（ＲＥＴＥ　１０のベータ・ノード２５Ａ以下、
ならびにアルファ配布ノード２４Ａ以下）は、データ構
造をベータ・ノードまたはアルファ・ノードとして識別
するタイプ・フィールド６７を含む。ＰＰＧＭＲフィー
ルド６８及びＰＰＧＭＬフィールド６９は、それぞれＲ
Ｈ８及びＬＨ８項目または入力を用いて実行すべきプロ
グラミングを指す。フィールドＰＲＰ７０及びＰＲＰ７
１は、それぞれ右及び左先行ノードを指すアドレス・ポ
インタを記憶する。右または左先行ノードがない場合、
当該のフィールドは空白（ＮＩＬと称する）である。Ｐ
ＲＰフィールド７０がＮＩＬのときは、ＰＰＧＭＲフィ
ールド６８もＮＩＬである。フィールド６９と７１につ
いても同じことが言える。ＰＲＳフィールド７２は、右
後続ノードがある場合、そのすべてを識別するデータ構
造を指すポインタを含む。右後続ノードがない場合は、
このフィールドはＮＩＬである。ＰＲ８Ｓフィールド７
３は、そのノードに関連するすべての非−時シナプス・
ノードを識別するデータ構造を指すポインタを含む。こ
の場合、そのノードは要求時ドレイン・ノードの右先行
ノードであるという関連がある。ＰＭＥＭフィールド７
４は、今説明しているベータまたはアルファ配布ノード
の関連する結果記憶域を指すアドレス・ポインタを記憶
する。ＶＡＲフィールド７５は、このノードに関連し、
このノードを走査するときＲＥＴＥプログラムによって
実行される、パターン突合せテストを表すデータ構造を
ｔ旨すアドレス・ポインタを含む。ＰＬＳフィールド７
６は、次の１組の左直接後続ノードを指すアドレス・ポ
インタを記憶する。ＰＲ８７２またはＰＬＳ７Ｅ！でい
ずれかで識別された後続ノードが多数存在することがあ
る。ＰＬＳＳフィールド７７は、このノードに関連する
すべての非−時シナプス・ノードを識別するデータ構造
を指すアドレス・ポインタを含む。この場合、そのノー
ドは要求時ドレイン・ノードの左先行ノードであるとい
う関連がある。６６のＰＲ３Ｓ及びＰＬＳＳノードを除
き、これらの構造は周知のＲＥＴＥアルゴリズムで使用
される一般的なものである。アルファ・ノードは記憶域
または結果記憶ノードではなく、アルファ配布ノード、
ベータ結合ノード及びボトム・ノードは記憶域または結
果記憶ノードであり、そしてシナプス・ノードは、ドレ
イン・ノードまたはソース・ノードとして指定される他
のノードを指すアドレスのみを提供することを想起され
たい。

第４図及び第５図は、規則をコンパイルしてＲＥＴＥに
入れることに関して使用される既知のＲＥＴＥ併合機能
を示す。第４図は４つのコンパイルされた規則ｗ１ｘ１
ｙ、ｚを、それぞれボトム・ノード９０−９３として示
す。このようなボトム・ノードは、プロダクション・ノ
ードでよい。ノード９４．９Ｂ−９８，１００−１０２
は、タイプＡ１Ｂ、Ｃ，Ｄのアルファ配布ノードであり
、これらはパターン・テストに合格したＷＭＥを記憶す
る。この場合ＡのすべてのＷＭＥは同一のアルファ・テ
ストに合格し、ＢのすべてのＷＭＥは同一であるが別の
アルファ・テストに合格し、以下同様である。ベータ結
合ノード９５．９９．１０３は、規則Ｘはベータ結合ノ
ードをもたない当該の規則のベータ部を構成し、アルフ
ァ・ノードは話を簡単にするために省略しである。規則
Ｗ、Ｘ。

ＹｌＺを表す個別のミニＲＥＴＥから併合されたＲＥＴ
Ｅを作成するため、すべての同一ノードが１つの論理削
減ステップとして組み合わされる。

したがって２つのＢノード９６と９７は、組み合わされ
て第５図のノード９６になり、後続ノード９５と９９は
このとき共通の先行ノード８９６（第５図のみ）を有す
る。同様に第４図の３つのＣノード９８．１００．１０
１は、組み合わされて、３つの後続ノード９１．９９．
１０３を持つ単一のＣノード１００（第５図のみ）にな
る。ノードＡ９４及びＤ１０２はそのままに保たれる。

第５図は、第４図に示した規則の併合されたＲＥＴＥを
表す。第５図に示す併合されたＲＥＴＥは、周知のよう
に、トップ・ルート・ノードからのトークンをブツシュ
することによって更新することができる。ＬＨ８入力は
、第４図及び第５図では、記号の左側から入る矢印で表
され、ＲＨ８入力は、記号の右側から入る矢印で表され
ている。トップ入力は、ＲＥＴＥ　１０のトップ・ノー
ド２１Ａ以下である（第１図）。

本発明によれば、追加の規則を既存ＲＥＴＥに接合する
ことができ、接合部分はシナプス・ノード・ポインタを
使って更新することができる。このようなシナプス・ノ
ードを修正されたＲＥＴＥと共に使ってミニＲＥＴＥの
ソースとは関係なく併合によって作成された延期ＲＥＴ
Ｅ部分を更新する（修正されたＲＥＴＥはミニＲＥＴＥ
を既存のＲＥＴＥに接合または接続して作成されている
）。

ここに例示した実施例では、ミニＲＥＴＥは２つの方式
のうちの１つで併合させることができる。

新しい規則を表すミニＲＥＴＥでは、併合論理がミニＲ
ＥＴＥの未併合の付加された部分を「プライミングした
」後、ＷＭＥが作成される前に付加部分が存在していた
かのように、続いて起こるＷＭＥの変更が（従来技術の
ＲＥＴＥアルゴリズムを利用して）付加部分に正確に影
響を及ぼすように併合が行なわれる。従来技術は、付加
された未併合部分が既存のＷＭＥによって「ブライミン
グされる」ことができるという、ノードの追加によるこ
の上うなＲＥＴＥとパターン突合せネットワークの動的
修正を、提供していない。

要求時パターン突合せ要求を表すミニＲＥＴＥは、上述
の方法によるようには永久的に接続されていない。とい
うのは、ＷＭＥが変更されるときにパターンの未併合部
分を連続的に更新するのではなく、要求に応じてのみそ
のパターン突合せ結果を計算することが望ましいためで
ある。この種の併合プロセスの後、（ＲＥＴＥの延期部
分を構成する）未併合の追加部分は、ＷＭＥデータ変更
の際に発生する通常のＲＥＴＥノード更新プロセスに関
与することを妨げられる。シナプス・ノードは延期ＲＥ
ＴＥ部分のトップ・ノードを指し、これらの追加ノード
の選択的アドレッシングを可能にする。適切なシナプス
・ノードがプログラミング（図示せず）によってアクセ
スされるときのみ、この種のミニＲＥＴＥの延期部分が
パターン突合せ動作で使用される。シナプス・ノードを
介するこのようなアクセスは、この種の延期ノードのユ
ーザ要求更新と呼ばれる。このようなユーザ要求動作が
発生しないときは、延期ＲＥＴＥノードは、主ＲＥＴＥ
の後続ノードとして正常に接続しないことによって絶縁
され、そのような追加の延期部分を更新しないことによ
って、より速いパターン突合せを可能にする。

パターンが１回しか使用されない（繰り返さない）要求
時パターンから生じるミニＲＥＴＥでは、１組のシナプ
ス・ノードを作成するプロセスは、他の場合とまったく
同じである。しかしながら、トップ・レベルの突合せパ
ターンから作成されるミニＲＥＴＥの併合された部分は
、主ＲＥＴＥ内にとどまる必要がない。パターン突合せ
動作が終了すると、他に必要がなければ、併合のいかな
る部分も削除することができる（このような削除は、規
則が削除されるときに行なわれることがある）。

このようなミニＲＥＴＥの突合せ出力が得られ、シナプ
ス・ノードを介する接続が除去できる。また、必要な記
憶項目を参照するには、シナプス・ノードのアドレス・
ポインタを持つことで十分である。１回の一時的併合で
ある再使用なしのこの種の要求パターンの実際の用途は
、情報を実際に変更することなしにＲＥＴＥ　１０から
情報を得ることである。このようなアクセスは、ＲＥＴ
Ｅに記憶された、突合せパターンによって識別可能な情
報の情報検索動作である。ノード併合のためのアルファ
及びベータ・ノード互換性要件は広範囲である。ノード
は同じ形式であってはならないのみならず、２つの候補
ノード中で記述または定義されたいかなるテストも同じ
テストを持たなければならない。同形式（アルファ、ベ
ータまたはアルファ配布）の２つのＲＥＴＥ候補ノード
を併合するための一般規則は、それらの当該の先行ノー
ドがすべて併合され、２つの候補ノード自体が併合され
ていることである。２つの入力ベータ・ノードの場合、
先行ノード併合要件がＬＨ８及びＲＨ８入力に拡張され
る。

ミニＲＥＴＥの主ＲＥＴＥとの併合を決定するために最
初に行なわれる反復的走査及び分析では、Ｔ（併合テス
ト合格または併合成功）とＮＩＬ（併合テスト不合格ま
たは併合不成功）の２つの併合マークのみが、併合テス
トの結果を識別するために使用される。分析されるミニ
ＲＥＴＥは、元のＲＥＴＥノードと併合されていてもよ
いが、ミニＲＥＴＥの最終併合ノードでなくてもよい。

すなわち、一番下のうまく併合されたミニＲＥＴＥノー
ドでなくてもよい。

ＲＥＴＥ併合の好ましい実施例では、まずミニＲＥＴＥ
は、重複するデータ構造を除去するために自己併合され
る。この自己併合は、１組の規則からのＲＥＴＥの元の
コンパイルと同様である。

第６図及び第７図に、自己併合プロセスを簡略化した形
で示す。第６図に示したミニＲＥＴＥは、単一の出力ノ
ード、すなわちボトム・ノードＰ１２１を含んでいる。

ミニＲＥＴＥのトップ・ノードは、同一の２つのＡノー
ド１２２．１２４及びノードＢ１２３を含む。この図の
一番上のノードは、アルファ配布ノードである。このミ
ニＲＥＴＥのベータ部は、図示された論理接続を有する
２つのベータ結合ノード１２５及び１２６から成る。

このようなミニＲＥＴＥは、規則のパターン仕様または
要求時パターン突合せ動作（再現可能または不能）から
構築することができる。このような構築されたミニＲＥ
ＴＥには、第６図に示すようにノードが共用されない。

このようなミニＲＥＴＥ内の各ノードは、併合されたＲ
ＥＴＥ内の多くの直接後続ノードとは違って、１つの後
続ノードしかもたない。自己併合によって重複ノードが
なくなり、ＲＥＴＥ併合処理が簡単になる。

第７図は、自己併合によって得られる第６図のミニＲＥ
ＴＥの構造を示す。ここに例示した自己併合ではトップ
Ａノード１２４がなくなっている。

結合ノード１２６へのＲＨ８入力は、Ａノード１２４か
ら残っているＡノード１２２へ移される。

このような再接続は、２つのノードのポインタを変える
ことによって行なわれる。結合ノード１２６では、その
ＰＲＰフィールド７０（第３図）が、ノードＡ１２４で
はなくノードＡ１２２を指すように変更される。結合ノ
ード１２６のアドレスがＡノード１２２のＰＲＳ７２　
（第３図）に加えられ、Ａノード１２４は削除される。

この動作で、このミニＲＥＴＥの簡単な自己併合が完成
する。

実際の実施例では、ミニＲＥＴＥはもっと複雑な構造を
とることを理解されたい。自己併合は周知のパターン突
合せプロセスである。ミニＲＥＴＥが入カバターンで更
新されていないので、シナプス・ノードを作る必要はな
い。従来技術による自己併合でもシナプス・ノードは作
成されなかった。

第８図及び第９図には、ミニＲＥＴＥの既存のまたは主
ＲＥＴＥへの併合及び単一アルファ・シナプス・ノード
の作成を簡単な形で示す。主ＲＥＴＥは、ＲＥＴＥのア
ルファ部にあると想定した１人力ノードとして部分的に
示されている。併合されるミニＲＥＴＥは、永久的に接
合される新しい規則からのものであると想定する。主Ｒ
ＥＴＥの一番上の併合可能なノードに１３０は、１つの
人力ノードと、複数の直接後続Ｌ１Ｍ、Ｎノード１３１
−１３３を有する。Ｍノード１３２は、上記のＲＥＴＥ
併合に含まれる出力ノード１４０を有する。他のノード
Ｌ１３１とＮ１３３の後続ノードは話を簡単にするため
に省略する。ノード１３１と１３２の間の省略符号は、
追加の直接後続ノードがノードに１３０に接続されてい
ることを示すものである。主ＲＥＴＥと併合されるミニ
ＲＥＴＥは、主ＲＥＴＥの７−ドに１３０と併合されて
いるトップ入力ノードに１３５を有する。ノードに１３
５の直接後続メートであるミニＲＥＴＥノードＭ１３６
は、直接後続ノードＲ１３７を有する。

ミニＲＥＴＥの図示された３つの７−ド部分１３５−１
３７は、２つのノード１３５及び１３６を有し、これら
は主ＲＥＴＥノードに１３０及びＭ２Ｂ５との併合を示
す。２つのノードに１３５及びＭ２Ｂ５は併合処理によ
って削除され、一方ミニＲＥＴＥのノードＲ１３７とそ
の後続ノードは、接合されて主ＲＥＴＥの一部となる。

第９図は、ミニＲＥＴＥ　１３５−１３７が元の主ＲＥ
ＴＥに併合された後の修正された主ＲＥＴＥを示す。第
８図の図との違いは、−容土の併合不能なノードＲ１３
７が主ＲＥＴＥの併合ノードＲ１３７に再接続されてい
ることだけである。この場合、ノードＭ１３６は最終的
に併合されたノードである。この再接続の結果、ノード
Ｒ１３７と併合ノード１３２の間に併合リンクが確立さ
れる。

その後は、最終併合ノードＭ１３６から上向きに到達で
きるトップ・ノードが、後述のようにアルファ・シナプ
ス・ノードとして認識される。併合リンク１４１は、ノ
ードＭ１３２及びＲ１３７のポインタの変更によって行
なわれる。この併合には１つの入力アルファ・ノードが
含まれるので、ノードＲ１３７のＰＰＲＥＤフィールド
８１（第３図）はノードＭ１３２を指すように変更され
、ノードＲ１３７のアドレスがノードＭ１３２のＤＶＥ
Ｃフィールド６３（第３図）に加えられる。

作成されたアルファ・シナプス・ノードは最終併合ノー
ドＭ１３６から上向きに到達可能なトップ・ノートをｔ
旨ｔシングル・ポインタであり、このノードをミニＲＥ
ＴＥの一番上のまたはトップ・ノードとして識別する。

このとき（ノードＲ１３７の後続アルファ配布ノードや
結合ノードなど、図示せず）記憶ノードは、パターン情
報で更新されていないことに留意されたい。第９図の修
正された主ＲＥＴＥの今付加されたばかりの部分の初期
設定を完了するために、後述の適当な更新手順をＲＥＴ
Ｅ併合の完了時に使用する。

第１０図は、その結果２つのシナプス・ノードが作成さ
れる、ミニＲＥＴＥの主ＲＥＴＥへの併合を示す。この
図はまた、いつシナプス・ノードを作成すべきかを決定
する際に、併合完了後に接合されたＲＥＴＥの正確な更
新を維持しながら、シナプス・ノードの数を最少にし、
要求時パターン突合せを制御するための「到達可能性」
原理を示している。第１と第２ノードの間の到達可能性
とは、第１ノードが第２ノードの先行ノードまたは後続
ノードのいずれかであり、すなわちネットワークの確立
された論理的経路をたどることによって論理的に第２ノ
ードに到達することができるという意味である。再びア
ルファ・ノードが示されており、同じ手順と原理がアル
ファ配布ノードとベータ・ノードを併合するのにも適用
される。はるかに大きな主ＲＥＴＥの２つのノード１４
７及び１５１だけが示されている。主ＲＥＴＥのトップ
・ノード８１４７はＲＥＴＥ入力ノードであり、その直
接後続ノードの１つとしてアルファ・ノードｖ１５１を
有する。併合すべきミニＲＥＴＥは、図では３つのＲＥ
ＴＥ入カノード１４８−１５０を有する（このミニＲＥ
ＴＥは図では自己併合されていない）。ＲＥＴＥ入カノ
ード５１４８は、どの主ＲＥＴＥノードとも併合されな
い直接後続ノード１５２Ｙ１及びどの主ＲＥＴＥノード
とも併合されないその直接後続ノードＸ１５３を存する
。ＲＥＴＥ入カノード１４８はＲＥＴＥ入カノード５１
４７と併合され、その結果、併合切断１５４が生じてＲ
ＥＴＥ入カノード５１４８が７−ドＹ１５２から切断さ
れる。ノードＹ１５２の後には、ノードＹ１５２から、
このとき併合ノードとなったＲＥＴＥ入カノード５１４
７への併合リンク１５５が続く。第１アルフア・シナプ
ス・ノード１５７は、アルファ・ノード１４８から上方
の到達可能なトップ・ノードをｔ旨す。

ミニＲＥＴＥノード５１４９及びＹ１５９は、ノード５
１４７及びＹ１５２と併合される。この併合によって併
合切断１６１が生じて、ノードＧ１６０のＰＰＲＥＤ６
１が削除され、併合リンク１６２が加えられる（ノード
ＧのＰＰＲＥＤ６１がノードＹ１５２を指すように変更
され、ＤｖＥＣ６３にＧ１６０が加えられる）。この併
合リンクは、ノードＧ１６０　（このノードはどの主Ｒ
ＥＴＥノードとも併合されない）をノードＹ１５２に論
理的に接続する。

ノードＳのためのアルファ・シナプス・ノードが（ノー
ド５１５７が併合されたときに）すでに作成されており
、そのアルファ・シナプス・ノードのトップ・ノード（
ノード５１５７）からブツシュされたトークンが両アル
ファ・セグメントＹ１５２−Ｘ１５３及びＹ１５２−Ｇ
１６０を初期設定するので、ノード５１４９のためのア
ルファ・シナプス・ノードは実際は複製であり、したが
ってこの併合のためのアルファーシナプス・ノードの集
合に加えられることはない。

言い換えれば、シナプス・ノード１５７からノードに到
達可能なため、削除されたノード５１４９及びＹ１５９
のためのシナプス・ノードは作成されない。到達可能性
の原理は、あるＲＥＴＥから別のＲＥＴＥへの接合ノー
ドが現シナプス・ノードの１つから到達可能である場合
、前のシナプス・ノードの活動化が接合されたＲＥＴＥ
で更新される必要のあるすべての接合ノードに到達する
ので、追加のシナプス・ノードは作成されないというも
のである。破線で示したボックス１６３は、シナプス・
ノード１５７からボックス１６３内のすべてのノードに
到達可能なことを示している。ノードＧ１８０への後続
ノードは示されていないが、記憶ノード及び非記憶ノー
ドを含むことができ、ちょうどノードＸ１５３の後続ノ
ードがボトム・ノード（図示せず）で終わるのと同じよ
うに、異なる複数のボトム・ノード（図示せず）で終わ
ることができる。ＲＥＴＥ　１０中で経路を分岐させる
ことによって、単一のボトム・ノードが、ノードＸ１５
３及びＧ１６０からパターン突合せ結果を受は取ること
ができる。第１１図は、この点に関する本発明のある併
合制御を示す。

破線で示したボックス１６８で示すように、第１の併合
不能ノードＷ１６５及びその後続ノードニ到達してそれ
らを識別するために、ノードｗ１６５が主ＲＥＴＥに接
合された後に、第２のアルファ・シナプス・ノード１６
９が作成される。ノードＷ１６５は、この併合で第２の
接合されたＲＥＴＥとなるミニＲＥＴＥの後続ノード・
リストの上部ノードである。トップ・ノードまたはＲＥ
ＴＥ人カノード１５０は、トップ・ノードまたはＲＥＴ
Ｅ入力１４７ノードに併合されて、併合ノード１４７及
びノードＷ１６５から併合切断１６６及び併合リンク１
６３を作成する。シナプス・ノード１５７からノードＷ
１６５への論理経路は存在せず、したがって、到達可能
性の原理から新しいシナプス・ノード１６９が必要とな
る。アルファ・シナプス・ノード１６９は、主ＲＥＴＥ
の一部分となる接合されたＲＥＴＥのトップ・ノードで
あるノードＷ１６５のみを指す。上述のＲＥＴＥの接合
及びアルファ・シナプス・ノードの作成により、パター
ン突合せ結果の重複や欠落が防止される。

ノード５１４９及びＹ１５９のための第２シナプス・ノ
ードが作成された場合、追加シナプス・ノードが活動化
されると、トークンが２回更新、作成され、併合りンク
１６１を介して送出され、その結果、パターン突合せが
重複される。到達可能性の原理を使用すると、この望ま
ない重複とその結果としての望ましくないパターン突合
せ結果が防止される。図に示した実施例では、各併合プ
ロセスはそれ自体のシナプス・ノードの集合を作成する
。つまり、到達可能性の原理が各併合に他の併合とは無
関係に適用される。アルファ・シナプス・ノードの場合
について説明した到達可能性の原理は、ベータ・シナプ
ス・ノードの作成にも例外なく同様に適用できる。

つまり、ドレイン・ノード候補（主ＲＥＴＥノードと併
合できず、最終併合可能ノードの後続ノードである、ミ
ニＲＥＴＥのベータ部にあるミニＲＥＴＥノード）が、
現アルファまたはベータ・シナプスで指定されたドレイ
ン・ノードから到達可能である場合、それはドレイン・
ノードとしてベータ・シナプス・ノードのリストに加え
られない。

第１１図は、要求時併合に必要なより複雑なＲＥＴＥ併
合を示す。第１１図に示す接合のモードは、第１０図に
示した規則パターン併合のための接合モードとは異なる
。第１０図の新しい主ＲＥＴＥでは、作成された併合リ
ンクは、接合されたＲＥＴＥのドレイン・ノードから元
の主ＲＥＴＥの併合ノードを指し、またその逆に向う正
方向ポインタ及び逆方向ポインタを含む。この両方向併
合リンキングによって、接合されたＲＥＴＥが完全に元
のＲＥＴＥに組み込まれて、接合されたＲＥＴＥはすべ
てのＲＥＴＥ動作に関与するようになる。すなわち、次
のＷＭＥデータ変更は、接合光の部分を含めて、通常の
方式で修正されたＲＥＴＥの全体を通してブツシュされ
る。これに対して、第１１図は、要求時に生成されたパ
ターン突合せミニＲＥＴＥを用いた部分併合を示す。第
１０図と第１１図の主な相違は、接合されたＲＥＴＥを
主ＲＥＴＥにリンクする際に生じる。第１１図に示すＲ
ＥＴＥ内でのリンキングは、直接先行併合ノードへのソ
ースまたは上方指示リンクに限られている。つまり接合
された部分への接続はシナプス・ノードを通じて行なわ
れる。これらのシナプス・ノードは、ドレインまたはダ
ウン・リンキングを完成するために、プログラム・ユー
ザの要求時に選択的にアクセスされることができる。

後述の更新手順などの適切な更新手順を用いて予期され
ないパターン突合せ結果が防止される。第１１図では、
既存の主ＲＥＴＥは、それぞれＡｌＢ及びＣ（図示せず
）をそのトップ・ノードとする、３つのトップ・ノード
またはアルファｉＬ［ノードＡ１７５、Ｂ１７８、Ｃ１
７７、及び出力ノードまたはボトム・ノードＰ１７８を
含む。既存の主ＲＥＴＥに併合すべきミニＲＥＴＥは、
アルファ配布ノードＣ１７９、Ａ１８０、Ｄ１８１及び
出力突合せノードまたはボトム・ノード１８２を有する
。主ＲＥＴＥの図に示した部分は、図のように接続され
たＡＮＤノード１８４と１８５を含む。

ミニＲＥＴＥはＡＮＤノード１８６と１８７を有する。

アルファ配布ノードＡ１８０とＣ１７９だけは、主ＲＥ
ＴＥの図に示した部分のどのノードとも併合される。ノ
ードＣ１７９はＣ１７７に併合される。併合切断１９５
及びＡＮＤノード１８６からノードＣ１７７への併合リ
ンク１９６（逆方向ポインタのみ）を参照のこと。ノー
ドＡ１８０はまたノードＡ１７５と共に主ＲＥＴＥに併
合される。しかしながら、ミニＲＥＴＥは要求時突合せ
パターンから導かれるため、第１０図に関連して説明し
たような完全併合は行なわれない。それが完全併合でな
いため、リンク１９６は一方向ソースまたはアップ・リ
ンクとなる。ベータ・ノード１８６は、ノードＣ１７７
を指すように変更されたフィールドＰＬＰ７１と、ノー
ドＡ１７５を指すように変更されたフィールドＰＲＰ７
０を有する。接合されたＲＥＴＥの更新中、ベータ・シ
ナプス・ノードにソース・ノードとして記録された２つ
のノード（Ｃ１７７及びＡ１７５）は、ＬＨＳソース・
ノード及びＲＨＳソース・ノードとして働く。すなわち
、ベータ・シナプス・ノードは、ドレイン・ノード１８
６を前述のソース・ノードと関連づける。非再現性要求
時結合では、ノードＡ１７５でもノードＣ１７７でもポ
インタは変更されない。再現性要求時結合では、一部の
ベータ・シナプス・ノードがノード１７５及びノード１
７６をソース・ノードとして指定することが、ノード１
７５及び１７６のＰＲ８Ｓフィールド７３及びＰＬＳＳ
フィールドに記録され、適切な論理によって、もはや使
われないＲＥＴＥ部分が削除できるようになる（たとえ
ば、一部のベータ・シナプス・ノードがあるノードをソ
ース・ノードとして使用する限り、このソース・ノード
は削除を妨げられることがある）。ノード１８１．１８
２．１８６．１８７からなる接合されたＲＥＴＥを更新
するため、ベータ・シナプス・ノードは活動化されると
、ＲＥＴＥ内に要求時動作を起こさせる。ノード１８１
．１８２．１８６．１８７の要求時突合せパターンに対
応するミニＲＥＴＥｇ分が、このパターンのためのシナ
プス・ノード・リストを用いてアクセスされる。後で同
じ突合せパターンについて要求時突合せ計算が反復され
る場合には、アルファ及びベータ・シナプス・ノードの
計算をキャッシュに記憶して、要求時プログラミングに
よって再使用することもでき、ノードをその都度再計算
することもできる。

第１２図と第１３図のマシン動作図は、ＬＨ８と称する
併合、反復使用される要求時併合、及び反復使用なしの
要求時併合の、３種のパターン突合せネットワーク併合
を可能にするパターン突合せネットワーク併合プロセス
を示す。第１２図は、併合動作中に併合が行なわれるか
どうかについてのミニＲＥＴＥ中の各ノードの最初の検
査を示す。

この図は、第２図の併合ステップ３２を図に示した実施
例で実施されるものとして詳しく示したものである。こ
の説明では、ミニＲＥＴＥはすでに自己併合されたもの
と想定している。自己併合は当技術分野では周知の用語
で、単に、冗長なノードと結合がミニＲＥＴＥから除去
されていることを意味する。併合プロセスのステップは
、矢印２００で示すように通常通り開始される。まず、
マシン・ステップ２０１で、検査すべきミニＲＥＴＥノ
ードが、取り出されてコンピュータの処理記憶部分（図
示せず）に入れられる（取り出されたノードは、検査さ
れる「現」ノードである）。

併合プロセスは、ボトム・ノードからミニＲＥＴＥを登
行することによって始まる。「登行」という用語は、プ
ログラムが、一番下のノードから始めて次々に論理的に
より高いノード、すなわちミニＲＥＴＥ中の先行ノード
へと７−ドを走査することを意味する。マシン・ステッ
プ２０１で、（プロダクション・ノードやマツチ・ノー
ドなど）ミニＲＥＴＥノードのボトム・ノードが取り出
される。ミニＲＥＴＥの登行はトップ・ノードに達する
まで続く。トップ・ノードに達すると、既存ＲＥＴＥま
たは主ＲＥＴＥ内の既存ノードと併合される一番下のミ
ニＲＥＴＥノードを見つけるため、ミニＲＥＴＥのトッ
プ・ノードから始まるミニＲＥＴＥの走査が、下方に向
かって行なわれる。

併合テストは、（１）併合テストが必要でなくなるか、
または（２）（マシン・ステップ２１１及び２１２で）
ミニＲＥＴＥのボトム・ノードに出会うまで続く。

走査されるミニＲＥＴＥノードが２入力ノードである場
合、ノードのＬＨ８先行ノードが最初に検査される。マ
シン・ステップ２０２で、直接ＬＨ８先行ノードが存在
するか否かを確かめるために、ノード・タイプ（たとえ
ば、フィールド・タイプ８０または６７）が検査される
。ベータ・ノードがＬＨ８先行ノードを有する（ステッ
プ２０２でイエス）場合、マシン・ステップ２０３で、
ＰＬＰ７１に記憶されたアドレス・ポインタを用いてそ
の先行ノード・データ構造が得られる。１入力ノードの
場合、ステップ２０４及び２０５（ステップ２０５は先
行ノードを取り出す）で、トップ（クラス）・ノードに
出会うまで登行プロセスが続く。この登行の間、後のス
テップ２１０で登行光のノードを見つけるこ七ができる
ように、登行光のノードが、スタックまたは類似のデー
タ（１４造中にブツシュされる。１入力ノードの入力は
ＲＨ８入力（先行）と呼ばれることに留意されたい。

メートがＲＨ８入力のみを有する場合、マシーン・ステ
ップ２０４で、ＲＨ８先行ノードがトップ・ノードであ
るかどうかを調べるためにテストが行なわれる。ノード
がトップ・ノードであるかどうかは、そのタイプ・フィ
ールド（第３図）を読み取ることによって決定される。

好ましい実施例では、トップ・ノードはアルファ・ノー
ドと同じデータ構造５８を有する。タイプ・フィールド
６０は入力（クラス・ノードを含む）ノードを指示し、
ＰＰＲＥＤフィールド６１はアドレス・ポインタの代り
にクラス名または識別を記憶するというのがその違いで
ある。現在ノードがトップ・ノードでない場合、トップ
・ノードに達するまで、ステップ２０５を用いて登行プ
ロセスが繰り返される。

一方、ノードがトップ・ノードである場合は、ステップ
２０６で、同じクラスの既存の主ＲＥＴＥ中のトップ・
ノードを識別するための試みが行なわれる。

ノード併合は、ＲＥＴＥノードを比較するための周知の
アルゴリズムを用いて決定される。Ｔの場合に併合が成
功したことを示すフラグが生成される（そうでない場合
はＮＩＬ）。おそらく多くの後続ノードのうちで、その
ノードを通じて現ノードが走査される場合、そのノード
の後続ノードは以前の後続ノード・と呼ばれる。その先
行ノードの併合状態を示すフラグがその以前の後続ノー
ドに渡される。マシン・ステップ２０６で、主ＲＥＴＥ
のトップ・ノード２ＬＡ以下が、ミニＲＥＴＥと併合で
きるかどうか走査される。走査中の一連のノード比較を
累積的に表すマシン・ステップ２０６で、既存の主ＲＥ
ＴＥ中で併合可能なトップ・ノードを見つける試みが失
敗した場合、ミニＲＥＴＥノードとどの主ＲＥＴＥノー
ドの間でも併合は見つからなかったことになる。したが
って、マシン・ステップ２０７では、ミニＲＥＴＥトッ
プ・ノードが、第１図のノード４１などの新しい入力ノ
ードとして既存のＲＥＴＥに加えられる。さらに、ノー
ド４１を指すアルファ・シナプス・ノードが生成され、
この併合に関するアルファ・シナプス・ノードのリスト
に加えられる。これは、重複シナプス・ノードの生成を
防ぐための前記の到達可能性の制限を受ける。同時に、
併合検査が停止したことを知らせるため、フラグＮＩＬ
が、以前の後続ノードに渡される。既存のＲＥＴＥ内で
併合可能なトップ・ノードを見つけるのに成功した場合
、最終併合ノードを見つけるためにさらに併合テストが
必要であることを知らせるフラグＴがその以前の後続ノ
ードに渡される。

ノードの併合が可能かどうか調べるための各テストが、
マシン・ステップ２１０で、現ノードの後続ノードから
開始される。ミニＲＥＴＥのベータ部を走査する際、ま
ず各ミニＲＥＴＥノードのＬＨＳ入力が分析され、次い
で各ミニＲＥＴＥノードのＲＨ８入力がマシン・ステッ
プ２０２及び２１４と同様に分析される。ＬＨ８及びＲ
Ｈ８入力の両方が（第１３図のマシン・ステップ２３１
で）主ＲＥＴＥノードと併合される場合、ステップ２１
６で、検査されるミニＲＥＴＥノードが主ＲＥＴＥと併
合されているかどうかテストされる。

ミニＲＥＴＥノードが主ＲＥＴＥノードに併合されてい
る場合、現ノードより上に位置するミニＲＥＴＥ内のす
べての先行ノードが適切な主ＲＥＴＥノードと併合され
ることを暗示している。併合されているかどうか検査さ
れるミニＲＥＴＥノードに対する主ＲＥＴＥまたは既存
ＲＥＴＥ候補ノードという用語（ミニＲＥＴＥのトップ
・ノード以外）は、ミニＲＥＴＥ内の検査されるノード
の対応する直接先行ノードと併合されている、直接先行
ノードの後続ノードである主ＲＥＴＥを意味する。

ステップ２１４で、検査されるノードの先行ノードであ
るさらに多くのミニＲＥＴＥノードを、主ＲＥＴＥノー
ドと併合されているかどうか検査すべきかどうかを決定
する。ＹＥＳの場合、ステップ２１５を含む論理経路を
たどり、そこで、現在検査されているミニＲＥＴＥノー
ドより１ステツプ上の（ミニＲＥＴＥのボトム・ノード
からさらに離れている）ミニＲＥＴＥノードについてス
テラ７’２０２−２１３を繰り返すために、別のノード
が取り出される。今説明した繰返しは、上記の２つの終
了条件の１つが溝足されるまで反復される。

マシン・ステップ２１６で、検査されたミニＲＥＴＥノ
ードが主ＲＥＴＥノード候補ノードと併合されているか
どうかがテストされる。併合アルゴリズムは、あるノー
ドのすべての先行ノードが最初にうまく併合されない限
りそのノードが併合されないようにする。

併合テストからの併合マークの値が、前に定義したその
以前の後続ノードに伝播される。マシン・ステップ２１
７でノード併合が見つからない場合は、ステップ２０９
で併合マークがＮＩＬに設定される。ステップ２０９に
通じる経路２１９は便宜上２つの部分に分けて示されて
いる。ステップ２１７で併合マークがＴに等しい場合（
ＹＥＳ条件）、ステップ２０８以下が繰り返される。

併合テストからのシナプス・ノードの生成を詳しく示し
たマシン動作図を第１３図に示す。第１３図はまた、そ
のようなミニＲＥＴＥノードを既存の主ＲＥＴＥノード
と併合することが可能かどうかをテストするために１人
カノード及び２人カノードを扱い、次いで併合が見つか
ったときはいつでもそれらのノードを併合する際に使用
されるマシン・ステップの詳細も示す。経路２１６には
、併合と指示された各ステップなど、前記のマシン動作
図の様々な所から入ることが可能である。第１２図と第
１３図は、マシン・ステップ２０８．２０９．２４４．
２４８などに、併合テストの結果をＴまたはＮＩＬのい
ずれかで表した併合マークを示す。併合マークＴは、ミ
ニＲＥＴＥ内の主ＲＥＴＥノードとのノード併合が可能
であることを意味し、それがＮＩＬであれば併合テスト
の失敗を表す。したがって、併合マークがＮＩＬの場合
、ミニＲＥＴＥのボトム・ノードへの下向きのノード走
査を行なう間に、併合テストはもはや必要でない。

第１３図のマシン・ステップ２３０で、ミニＲＥＴＥノ
ードがそのタイプによって１人カノードまたは２人カノ
ードに分類される。ノードが１人カノードである場合、
そのＲＨ８先行ノードが併合マークとしてＴを渡すたび
に、ノード併合がテストされる（ステップ２３８）。そ
うである場合、その現ミニＲＥＴＥノードが主ＲＥＴＥ
ノードと関連してテストされ、それらが併合できるかど
うか検査される。マシン・ステップ２４０で、併合テス
トが２つのノードが併合可能である（Ｎｏ”と記した出
口に相当する）ことを示した場合には、ミニＲＥＴＥノ
ードはまだ完全には併合されていない可能性があり、し
たがって併合テストの結果Ｔを以前の後続ノードに送る
ことによって、さらに併合テストが行なわれる（ステッ
プ２４３）。

この時点で、併合テストに合格したノードのタイプがア
ルファ配布ノードである場合、ミニＲＥＴＥ内の先行ノ
ードからこのノードへの正方向ポインタが正しい突合せ
結果が得られるように削除される。一方、それらのノー
ドが併合不能である（２４０で”ＹＥＳ″と記した出口
に相当する）場合には、先行ミニＲＥＴＥノードは、ボ
トム・ノードまたは出力ノードへ向かうミニＲＥＴＥの
この部分に対するノード鎖中の最後併合可能ノードであ
り、最終併合ミニＲＥＴＥノードと呼ばれる。この時点
で、予め存在する主ＲＥＴＥノードと、主ＲＥＴＥノー
ドとうまく併合されなかったミニＲＥＴＨの非共用部分
との間の接続点を記録するためのシナプス・ノードが作
成される。マシン・ステップ２４１で、先行ノードが関
連する結果メモリ情報を持っているかどうかがテストに
よって決定される。これは、たとえば、主ＲＥＴＥ中の
先行ノードがアルファ配布ノードであるときに起こる。

関連する結果メモリを持っていない場合には、ステップ
２４２で、アルファ・シナプス・ノードが作成される。

関連する結果メモリを持っている場合には、ベータ・シ
ナプス・ノードが作成される。

２人カノードは、マシン・ステップ２３１でＬＨＳ及び
ＲＨ８先行ノードの両方が併合マークＴを渡す場合にの
み、併合テストを受けることができる。２人カノードの
併合テストは、１人カノードの場合と同じである。１人
カノードでは、テスト中のミニＲＥＴＥノードが主ＲＥ
ＴＥノードと併合可能である場合、併合が見つかる。

２人カノードの場合には、ノード併合と同様に別の条件
も満足すべきである。この条件とは、テスト中のノード
とミニＲＥＴＥ内のそのＬＨＳ及びＲＨ８先行ノードと
の関係が、主ＲＥＴＥ中のそれらに相当するノードと矛
盾しないというものである。マシン・ステップ２３５で
、このような併合テストが実行される。併合テストが成
功した場合、マシン・ステップ２３６及び２４４に示す
ように、最大の共用を実現するために、さらに後続の併
合テストが必要である。一方、併合テストが失敗した場
合、前記のようにＲＥＴＥ併合が起こり、１組のベータ
・シナプス・ノードと共に（必要に応じて）併合リンク
が作成される。ミニＲＥＴＥ中の２人カノードでは、２
つの先行ノードから渡された併合マークがマシン・ステ
ップ２３２及び２４３におけるようにＴ及びＮＩＬであ
る場合、Ｔフラグを渡すミニＲＥＴＥ先行ノードは最終
的に併合可能である。したがって、１組のベータ・シナ
プス・ノードと共に併合リンクもマシン・ステップ２３
７で作成される。

ミニＲＥＴＥノードが最終併合可能であると確認される
と、前記の併合切断及び併合リンクが作成される。同時
に、シノプス・ノードが作成される可能性がある。しか
しながら、誤った突合せ結果が得られないようにするた
めに、シナプス・ノードを作成する前に、マシン・ステ
ップ２３７及び２４２で、いくつかのテスト（図示せず
）が必要である。新しいアルファ・シナプス・ノードは
、それが既存のアルファ・シナプス・ノードの１つと同
じでない限り、作成される。同様に、ミニＲＥＴＥが既
存のアルファまたはベータ・シナプス・ノードへの後続
ノードである場合、それは主ＲＥＴＥノードに併合され
るが、ベータ・シナプス・ノードは作成されない。そう
でない場合は、併合リンクとシナプス・ノードが作成さ
れる。併合プロセスの目的の１つは、正しい１組のシナ
プス・ノードを得ることであることを想起されたい。

「正しい１組」という用語は、オーバーラツプする後続
ノードも、ミニＲＥＴＥから追加または接合された後続
ノードも持たない最小数のシナプス・ノードが作成され
ることを意味する。

要求主導型パターン突合せの最終段階は、接合されたＲ
ＥＴＥの更新である。規則ＬＨ８突合せパターンや要求
時非反復使用パターンの更新とは異なり、突合せ、要求
時突合せ反復使用の更新は、最初の更新を除き、トーク
ン・ブツシュ動作の開始前に、要求時接合ＲＥＴＥの７
−ド中のすべてのメモリをクリアする事前処理を必要と
する。

（これは１つの実施例にすぎず、他の実施例では、たと
えばシナプス・ノードにトークン変更を蓄積し、それら
の変更を要求時ＲＥＴＥの非共用部分にブツシュするこ
とに留意されたい。）要求時パターンのための接合ＲＥ
ＴＥは、その後、セーブされたシナプス・ノードを用い
て更新される。接合されたＲＥＴＥの更新は、前記の関
連特許出願明細書にさらに詳しく記載されているように
、汎用ＲＥＴＥ更新原理を用いて実現することができる
。汎用更新アルゴリズムを適用する際、ベータ・ソース
・ノードからのトークン（またはアルファ・シナプス・
ノードからのＷＭＥ）の送出順序は重要ではない。

前記の関連特許出願明細書に記載された汎用更新法に代
わる方法として、シナプス・ノードによって表される特
別な場合を利用する代替更新アルゴリズムを使用しても
よい。この最適化された更新アルゴリズムの手順は、従
来の汎用更新アルゴリズムと比べて時間及びスペースの
点でより効率的である。

最適化されたアルゴリズムは、一般の場合に比べて次の
ような制約によって使用可能になる。まず、ソース・ノ
ードは「更新」トークンのみを含み、「最終仕上げ」　
トークンを持たない。更新トークンとは、メモリ・ノー
ドによって受は取られたが、まだ受取り側メモリ・ノー
ドの後続ノードにブツシュまたは伝播されていないノー
ドである。

最終仕上げトークンとは、メモリ・ノードによって受は
取られ、少なくとも１つの後続（直接後続ノードでも、
介在する後続ノードを伴う遠隔後続ノードでもよい）メ
モリ・ノードを含む後続ノードにブツシュされたノード
である。次に、実施される操作は追加であり、修正や除
去（削除）ではない。最適化されたアルゴリズムは、２
つの段階、すなわちベータ更新段階とその後のアルファ
更新段階で、延期ＲＥＴＥ部分を更新する。

ベータ更新では、右ソース・ノードに記憶されたすべて
のトークンがドレイン・ノードに送出されない。すなわ
ち前記の関連特許出願明細書に記載されているように、
「シャドウ」されない。そして、各トークンごとに個別
に行なわれる汎用更新アルゴリズムの最初の２ステツプ
が削除される。

接合されたＲＥＴＥの更新は、トークン送出処理の特定
の順序を用い、ドレイン・ノードのいわゆる「昇順」走
査を使って、汎用更新アルゴリズムの最終ステップを実
行することによって行なわれる。トークン送出順序は、
前記の関連特許出願明細書に詳しく記載されているよう
に、ドレイン・ノード中の到達可能性によって決定され
る。あるドレイン・ノードが別のドレイン・ノードから
下向きで到達可能な場合は、前者のドレイン・ノードが
最初に処理される。ミニＲＥＴＥの併合中に作成された
ドレイン・ノードの順序は、その昇順と同じである。し
たがって、併合を決定するための処理の副次効果として
、余分の走査なしで、ドレイン・ノードの順序づけが得
られる。昇順の更新では、互いに到達可能なノードのサ
ブセ−／　）中のより低い（ボトムまたは出力ノードに
最も近い）ドレイン・ノードが、より高いノードより先
に処理される。いくつかのドレイン・メートの間に到達
可能性の関係がない場合には、これらのドレイン・ノー
ドの処理順序は任意である。ドレイン・ノードが最適化
された更新アルゴリズムのそのステップで処理されると
き、（ＬＨ８入力に）接続されたソース・ノードは、そ
の関連する結果メモリ中にあるすべてのトークンを、Ａ
ＤＤトークンとしてドレイン・ノードに送出する。ベー
タ更新の後、何らかのアルファ・シナプス・ノードが併
合プロセス中に作成された場合、アルファ・シナプス・
ノードによって指されるアルファ・トップ・ノードに対
応するＷＭＥが、アルファ・シナプス・ノードに関連す
るアルファ・トップ・ノードに送られ、それによってそ
のトップ・ノードに接続されたすべての後続ノードに任
意の順序で送られる。

各個別ノードでの更新は、従来技術の場合と同様である
。

【図面の簡単な説明】

第１図は、本発明によるパターン突合せネットワーク併
合を示す、付属データ構造を伴うＲＥＴＥの概略図であ
る。 第２図は、第１図に示したネットワークの併合プロセス
で実施されるステップを示す簡略化した流れ図である。 第３図は、第２図に示した併合プロセスと共に使用され
る簡略化した１組の制御データ構造の構成図である。 第４図及び第５図は、従来技術で実施されたパターン突
合せ規則ネットワークのＲＥＴＥへの併合を示す図であ
る。 第８図及び第７図は、ミニＲＥＴＥネットワークの自己
併合を示す図である。 第８図及び第９図は、本発明のネットワーク併合切断ス
テップ及びリンク・ステップを示す図である。 第１０図は、第１図に示したパターン突合せネットワー
ク用に作成、されたシナプス・ノードの到達可能性特性
を示す図である。 第１１図は、第１図に示したＲＥＴＥのための、ＲＨ８
併合プロセスのベータ・シナプス・ツートノ結果と追加
のノード・ポインタを示す図である。 第１２図及び第１３図は、様々なタイプのＲＥＴＥ併合
を実施するために使用可能なマシン動作を簡略形で示す
マシン動作図である。 １０・・・・ＲＥＴＥｌ　１１・・・・作業用記憶域、
１６・・・・データ域、１８・・・・ミニＲＥＴＥ、２
０・・・・ルート・ノード、２１・・・・ＲＥＴＥ入カ
ノード、２２・・・・アルファ・ノード、２４・・・・
アルファ配布ノード、２５・・・・ベータ・ノード、２
６・・・・出力ノード。 出願人　　インターナショナル・ビジネス・マシーンズ
・コーポレーション 復代理人　弁理士　　澤　　１）　俊　　夫ｌセ５−５ ＦＩ５．７ １セ５−４ ｆセ５−５

Claims (1)

1. 【特許請求の範囲】 複数のパターン突合せノードからなるパターン突合せネ
   ットワークを、ネットワークを通って入力側から出力側
   に延びる複数の規則定義論理経路に配列するステップと
   、 前記ノードのいくつかを前記論理経路への入力ノードと
   して指定し、他のいくつかの前記ノードを前記経路の前
   記出力側の出力ノードとして指定して、前記論理経路を
   通って前記入力側から論理的により低い出力側に至る、
   パターン突合せ動作の論理流れが生じるようにネットワ
   ークを配列するステップと、 複数の前記パターン突合せノードから各々なる複数のパ
   ターン突合せモジュールを前記パターン突合せネットワ
   ークにおいて確立し、かつ論理的に結合し、各々の前記
   パターン突合せモジュールが前記パターン突合せネット
   ワーク内の他の前記パターン突合せモジュールの前記パ
   ターン突合せノードのあらかじめ定められたものとパタ
   ーン突合せ情報項目の授受を行ない、当該パターン突合
   せモジュール外のパターン突合せノードとパターン突合
   せ情報を共有するステップと、 各モジュールの外側の前記ネットワーク内で、ノードの
   １つを各モジュールのソース・ノードとして指定するス
   テップと、 それぞれ指定されたソース・ノード及び前記のモジュー
   ルを指すポインタを作成して維持するステップと、 前記の各ポインタを用いて包括されたモジュールにアク
   セスすることを含めて、所定の前記モジュールが所与の
   パターン突合せ動作に包括され、またはそこから除外さ
   れるように、パターン突合せネットワークを動作させる
   ステップとをコンピュータで実行することを特徴とする
   パターン突合せネットワーク操作方法。