JPS63500548A - ル−ルベ−スのデ−タ検索方法及び装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 発明の名称 ルールベースのデータ検索方法及び装置技術分野 本発明は一般的に、データ処理システムの分野に関し、より詳細には、データ処 理システムに用いるメモリシステムに関する。

背景技術 人工知能システムに用いられる実質的に全てのデータ処理システムは、情報が記 憶され且つ這択的に検索されることを要する。情報は、一度に１つ検索されるべ き多数のレコードから成る、メモリに記憶されるデータベースとして通常は構成 される。

通常、各レコードは、１単位として検索される。データベース検索の最も単純な 例は、１つ又はそれ以上のキーワードを含む全てのレコードの検索を含むもので ある０例えば、データベースがルコード当り１つの記事として、特定の組の科学 雑誌における全ての記事からなる。ここで、１つ又はそれ以上のキーワードを含 む全ての記事、例えば、「計算」及び「人工知能」という語を含む全てのレコー ドを検索したくなったとしよう。

「エキスパートシステム」において、データベースは１種々のル返し探索されな ければならない、この所与の仕様は、又は「問合せシーケンス」と呼ぶことがで きる。「ルールベース」探索と呼ばれる、この型の探索は、上記の１つ又はそれ 以上のキーワードを含むレコードのための探索とは大きく異なる。ルールベ−ス 探索において、システムは、データベースにおける多くのルールの内どれが現在 存在する問題に次に適用されるかを選択しなければならない、この選択は解決さ れる問題における変数間のデータ及び関係に依存する。エキスパートシステムは 、同一のデータ及び（又は）変数の間の関係を含むこれらのルールを選択しなけ ればならない、キーワード探索は、システムが、同じデータを含むルールを選択 することのみを要求する０例えばこれらのルールは、次の形式となる。

ＩＦ＜条件〉、ＴＨＥＮ＜行動又は結論〉である。

データベースにおけるこれらのルールの１つは以下のようＩＦ（Ｘが食べる）、 ＴＨＥＮ（Ｘは空腹である）。

問題が情報「ビータが食べる」を含む場合、システムは、（Ｘが食べる）を含む 情報を見つけるために全てのルールを探索するタスクに直面する。ここで、Ｘは 、既知の情報における任意のエレメントに置き換えられる可変エレメントである 。上記のルールは、「食べる」を含む任意の他のルールと共に検索される。

一旦、システムがこのルールを検索すると、システムは、Ｘにビータを置き換え 、次にビータは空腹であると結論する。

このルールベースの探索は、１つ又はそれ以上のキーワードを含む全ての記録が 検索される単純なキーワード又はキーエレメント探索とは大きく異なる。ルール ベース探索において、データベース記憶に含まれるエレメントの数と順序は両方 とも重要である。３つのレコード（ａ、ｘ、ｂ）、（ａ　＋　ｚ　ｒ　ｂ）及び （ｂ、（ｄ、ｅ）、ａ）を含むデータベースを考えることにする。「ａ」及び「 ｂ」を含む全てのレコードへの要求は、上記のレコードの全てを検索する。

しかしながら、形式（ｉ、ｂ）の全ての「ルール」への要求は、各レコードが、 ３個のエレメントを含んでおり且つ要求されたルールが２つしかエレメントを含 んでいないため、これらのレコードのどれによっても満足されない、フオーム（ ａ、？、ｂ）、即ち？は、任意のベース、副表現、又は別の変数によって満足し 得る可変エレメントを示す所のこのフオームの全てのルールに対する要求は、「 ａ」及びｒｂ」が第３のレコードにおいて異なった順序で現われるため、最初の ２つのレコードを検索するが、第３のレコードは検索しない、従って変数の概念 によっても、ルールベースの検索システムは、規定されていない順序にあるキー エレメントに基づくレコードを選択するのに都合よく用いることができない。

同様にして、キーワード探索システムは、エレメントが異なった順序で現われる かあるいは好ましくない付加的なエレメントと共に存在している多くのレコード を検索するため、ルールベースの検索問題にはよく適していない、これらの余分 なレコードは、それらが検索された後システムによって捨てられなければならず 、これは、好ましくないルールを記憶するための処理時間及び付加的なメモリの 両方を必要とする。

現在入手可能なコンピュータハードウェアを用いる人工知能システムを実現する にあたり遭遇する１つの問題は、大きなデータベースを探索して特定の間合せシ ーケンスに一致するレコードを見つけるのに要する時間である。有用なものとす るためには、斯かるシステムは、非常に多くのレコードを含まなければならない 、データベースを探索するのに必要な時間は、データベースの長さに比例するた め、固定探索速度を有するシステムが、新しいルールの型をとる新しい情報の付 加によって「より賢く」なると、この時間も、遅くなる。この問題は、探索され るべきデータベースのサイズが増加する時にシステムの探索速度を早くすること によってのみ解決され得る。

集積回路技術においてなされてきた多くの改良にも拘わらず、最新のコンピュー タは、元来のノイマン型の設計と殆んど異なっていない、古典的なノイマン型マ シンは、中央処理装置及び固定された長さのワードで構成される独立のメモリか らなってい置、即ちそのアドレスを規定することにより一度に１ワードずつメモ リからデータを取り出す。

上記の探索を実行するために、ノイマン型の中央処理装置は、この後、メモリか らデータベースの各ワードを検索し、次にこれをこれもまたメモリに記憶されて いる間合せシーケンスにおけるワードの各々と比較する。１つの処理装置が実行 することができる速度には限度があるため、実用におけるノイマン型のマシンは 、アクセスされ得るデータベースのサイズについて限定されている８秒当り一千 万個の比較の速度においてさえも、ノイマン型のマシンは、例えば米国における 種々の管轄に関する司法リポータ−シリーズのみを含んでいるライブラリーの内 容を探索するのに困難を窮める。

速度の限界に加えて、ノイマン型アーキテクチュアはまた、その固有のハードウ ェア依存性の故に多くの限界を示す、メモリアドレスを規定するために、固定さ れた数のアドレスラインが用いられる。Ｎ個のアドレスラインを有するシステム は、２Ｎワードのメモリをアドレス指定することができるだけである。

この限界を越えてメモリ容量を増加するには、アドレスラインの数を増加しなけ ればならない、たいがいのシステムは、コンピュータの命令セットが、アドレス 指定することのできる最大メモリサイズを規定するため、ハードウェアとソフト ウェアの両方の変更を伴う、更に、メモリの一部が、その成分の１つの故障によ って作動不能となった場合、再プログラミングすることなしにこの記憶をメモリ の損傷のないセグメントに転送することは困難である。メモリのサイズが、より 多くの数のデータレコードの記憶の必要性に応答して大きくなると、メモリのあ る成分における斯かる故障の確率が大きくなる。

最後に、大きなデータベースの探索の問題は、中央処理装置に存在するわずかな 命令のみの使用しか必要とはしないことである。典型的な中央処理装置は、外界 を取り扱うための入力／出力命令から、数を表わすメモリワードを組み合わせる ための数学的な命令までの様々な文字通り何百という命令を有している。データ ベース探索問題は、これらの命令の多くてもＩＯ乃至２０シか必要としない、従 って、データベースの探索の問題は、中央処理装置の命令のレパートリを十分に 使えない。

中央処理装置の速度上の制限は、各々がメモリに対するアクセスを有する多重中 央処理装置を有するシステムを構成することによりある程度克服することができ る。しかしながら、この解決方法にも、その限界がある。与えられたメモリを共 有することができる中央処理装置の数は、各中央処理装置がメモリにアクセスす るのに要する時間によって究極的には制限される。

メモリバスが、この時間の１八。にわたって各中央処理装置に専用されなければ ならない場合、１０個以下の中央処理装置しか、同一のメモリを効果的に共有す ることができない、斯くして、中央処理装置を反復するのは、ノイマン型マシン の速度上の制限に関する最良の解決方法ではない。

反復された中央処理装置を用いてこの探索時間を効果的に減らすことができても 、依然としてハードウェアによって課せられる制限が残っている。遅かれ早かれ 、ノイマン型マシンにおいては実行することが困難であるこれらのハードウェア 上の制限を越えてデータベースを拡大したくなるであろう。

データベースのサイズの増大が、アドレスラインの数を増加するという付随的な 必要性を見ることなく、要求する時は必ずシステムに付加することができるモジ ュラ−メモリを希望するのが理想的である。メモリを拡大するこの能力は、永久 的に増え続ける量の情報を獲得し且つ用いることのできるマシンを構成すること をめるこれらの人工知能システムにおいては段々と重要になろう。

発明の開示 本発明は、人工知能システムにおいてルールを表わすのに用いられ得る記号のシ ーケンスの記憶及び検索のためのメモリシステムからなる。記憶されたデータシ ーケンスは、各々が、３つのクラス、即ち定数、変数、又は区切り文字の１つに 属する複数の記号からなる。記憶されたデータシーケンスは、記憶されたデータ シーケンスを含む記号と同じ３つのクラスに属する複数の記号からなる間合せシ ーケンスに応答して本発明の装置によって検索される。記憶されたデータシーケ ンスは、データシーケンスと間合せシーケンスの２つのシーケンスが、これら２ つのシーケンスに限われる各可変エレメントを、定数又は定数の組合せであって 、区切り文字から始まり区切り文字に終る組合せで置き換えることにより、同等 と成り得る場合に与えられた間合せシーケンスに応答して検索される。置き換え られた各可変エレメントに対して、異なった定数又はその組合せを用いることが できる。この装置は、メモリ、該装置に結合された間合せシーケンスを受信する ための手段、及び記憶されたデータシーケンスの各々と間合せシーケンスとを比 較するための且つ間合せシーケンスに対応するこれらのデータシーケンスを検索 するためのデータ処理システムを設けている。データ処理システムは、並列に働 く複数のプロセッサを含むように構成することができ、これらのプロセッサの各 々は、与えられた間合せシーケンスに対応するデータシーケンスを見つけるのに 必要な時間を減少させるべく記憶されたデータシーケンス記号の異なったグルー プにおいて作動する。

従って、本発明の目的は、ルールベースの人工知能システムに適用可能なルール の記憶及び検索のための改良されたメモリシステムを提供することにある。

本発明の別の目的は、並列の処理オペレーションによりこれらのルールを検索す るのに必要な時間を減少することにある。

本発明の上記及び他の諸口的は、本発明の以下の詳細な説明及び添付の図面から 明らかとなろう。

図面の簡単な説明 第１図は、本発明に係るメモリシステムの略ブロック線図である。

第２図は、第１図に示されているメモリシステムにデータシーケンスを記憶する ためのメモリの例示的な割当てを示す図である− 第３図、第３（ａ）図及び第３（ｂ）図は、間合せシーケンスも、本発明の装置 に記憶される、本発明に従うメモリシステムを説明するための図である。

第４図は、本発明の第２の実施例を示すブロック線図である。

第５図及び第５（ａ）図は、第４図に示されている検索プロセッサのより詳細に 説明するためのブロック線図である。

第６図は、本発明の第３の実施例を示すブロック線区である。

発明を実施するための最良の形態 本発明によると、ルールは、３つの型のエレメント、即ち区切り文字、定数及び 変数を含み得る記号のストリングの形で記憶される。「（」及び「）」で表わさ れる区切り文字は、データシーケンスとデータシーケンス内の副表現の境界をマ ークするのに用いられる。このストリング（ａ、ｂ、（ｆ、ｇ）、Ｃ）は、第１ エレメントとして「ａ」、第２エレメントとして「ｂ」、第３エレメントとして 組合せ’ｆ、ｇＪ及び第４エレメントとして「ｃ」を有するデータシーケンスを 表わしている。定数は、固定された値を有するエレメント、例えば、上記の問題 における「食べる」及び「空腹」である、（ａ、ｂ、ｅ）に対する要求は、定数 ａ、ｂ、及びＣの３つの全てが、それらの間に他のエレメントがない状態で示さ れている順序で存在する場合にのみ満足され得る。「？」又は「？Ｘ」で表られ される変数であって、Ｘが選択的ネームである変数は、任意の定数又は別の変数 あるいは一対の区切り文字によって包囲されている定数と変数の組合せによって 満足され得る。これらは、「一致する任意のもの」のための速記を構成している 。斯くして、形式（ａ、　？　、ｂ）の全てのデータシーケンスを見つけるため の要求は、（ａ、ｘ、ｂ）　、（ａ、　？　、ｂ）　、（ａ、ｚ、ｂ）　、（ａ 、（ｄ、ｅ）　、ｂ）、等を戻す。

上記の例において、メモリが探索されて、形式「（ＩＦ（？ｘが食べる）、ＴＨ ＥＮ（？ｘは、？ｙである））」のルールが見い出される。形式「（もし、？で ある場合、？である）」の全てのデータシーケンスに対する要求は、上記にリス トされたデータシーケンスを含む全ての「もし−である」データシーケンスを検 索する。

従来のシステムにおいて、探索時間は、探索されているデータベースの長さに比 例するため、探索時間は、データベースを記憶するメモリを、それぞれがそれ自 身の処理ユニットを有している幾つかのザブユニットに分解することにより減少 することができる。これは、探索タスクを、それぞれが、間合せシーケンスの関 連部分及び１つ又はそれ以上のデータシーケンスを保持するのに十分なメモリを 有する幾つかの小型のノイマン型マシンに分割することと同等である。斯かるシ ステムについての最も早い探索は、メモリの各ワードに組込まれている１つの処 理装置を有するメモリでもって達成される０次に、１つのメモリサイクルにおい て、メモリは、それ自身を間合せ記号と比較し、この間合せ記号が現われた各デ ータシーケンスを識別すルコとかできた。データベースワードの処理装置に対す る最適化は、メモリの複雑性に対する処理装置の相対的な複雑性に明らかに依存 する。処理装置は、探索機能を実行するのに数個の命令しか必要としないため、 汎用中央処理装置よりもかなり単純な構造を有することができる。その結果、か なり高い密度の処理装置が可能である。この型の高度の複製のモジュラ−・構造 は、最新のＶＬＳＩ集積回路組立技術に特によく適している。

複製されたこの型のコンピュータハードウェアは、メモリ容量の各単位が、それ と共にそれ自身の探索能力をその内蔵処理装置の形として備えているため、処理 時間が、データベースのサイズが増加する時には増加しないというデータベース 探索問題にもよく適している。従って、システムの計算能力は、データベースが 拡大すると拡大する。更に、このシステムの中央処理装置は、メモリにおける探 索機能を提供する処理ユニットのオーバーヘッドに対するものとして、この型式 ではかなりオーバーヘッドが少ないアドレス即ちメモリの内容に関連した他のデ ータに絶えず注意する必要がない、探索の結果をどこに記憶すべきかについての 命令を有する幾つかのモジュールから構成されているメモリユニットにこの間会 せシーケンスを送るだけでよい。

本発明に係る装置のブロック図が、第１図の１０に略示されている。大ざっばに 言えば、この装置は、検索手段３２に接続されているメモリ手段１２、及びこの 装置に間合せシーケンスを結合するための且つ本発明の装置を外部データ処理シ ステムに接続するバス４７を通して規定のデータシーケンスを読み出すための特 衣昭６ａ−５ｏｏ５４ａ　（６） 受信手段４６から成っている。メモリは、スロット１４に分割される。各スロワ ｌ〜は、通信バスを通して通信される記号の間合せシーケンスに応答して検索さ れるべき記号のデータシーケンスを含む記号の１つを記憶するのに用いられる。

メモリ手段１２に記憶されている記号の典型的なデータシーケンスが、第２図の ２１に示されている。このデータシーケンスは、３つの型の記号。

即ち定数、区切り文字、及び変数から成っている。定数は、アルファベットの文 字によって、変数は「？」によって区切り文字は、「（」及び「）」によって示 されている。全てのデータシーケンスは、区切り文字から始まり区切り文字に終 る。データシーケンスが他の「特別な」記号で始まり他の「特別な」記号で終る あるいはデータシーケンスの終りを規定する情報は、データシーケンスの終りに 先行する特別な記号でもってコード化される他の実施例は、データ処理システム の技術における当業者には明白であろう、データシーケンスはまた、データシー ケンスの内部に埋め込まれている記号のサブシーケンスを含み得る。斯かるサブ シーケンスはまた、区切り文字から始まり区切り文字で終る。第２図において２ ３に始まり２５に終るサブシーケンスは、斯かるサブシーケンスの典型である。

再び第１図について説明すると、検索手段３２は、通信バス４７を介してそれに 結合された間合せシーケンスに対応する全ての記憶されたデータシーケンスを検 索する。データシーケンスは、このデータシーケンスと与えられた間合せシーケ ンスの２つのシーケンスとが、各変数を定数又は定数の組合せによって置き換え ることにより同等となり得る場合、この与えられた間合せシーケンスに対応する ものと定義され、上記の定数の組合せは、区切り文字に始まり区切り文字に終る 。この定数又は定数の組合せは、一般的に、置き換えられた各変数に対して異な っている０例えば、データシーケンス （ａ、　？　、ｄ、ｅ、（ｋ、ｌ）　、ｅ）は、データシーケンスにおける変数 を定数「ｆ」に且つ間合せシーケンスにおける変数を組合せ（ｋ、１）、即ち、 区切り文字で始まり区切り文字で終る定数の組合せでもって置き換えることによ り、間合せシーケンス （ａ、ｆ、ｄ、ｅ、　？　、ｅ）に同等となり得る。

与えられた間合せシーケンスに対応する全てのデータシーケンスのための探索は 、３つの段階を要求する。先ず、装置は、探索のために初期化されなければなら ない、これは、下記に述べる特定のインジケータのセツティングを伴う、第２に 、用いられるべき間合せシーケンスは、受信手段４６によって検索手段３２に通 信されなければならない０次に検索手段３２は、間合せシーケンスにおける記号 と記憶されたデータシーケンスにおける記号との幾つかの対による比較を実施す る。最後に、間合せシーケンスに対応するこれらのデータシーケンスは、受信手 段４６によって通信バス４７を介して読み出される。これらの段階の正確な順序 は、以下に述べるように、本発明の装置の特定の実施例に応じて変化する。

本発明の好ましい実施例において用いられるメモリ手段１２は、読出し専用メモ リかあるいは読み書きメモリのどちらかであり得る。記憶されたデータシーケン スによって表わされるデータベースが更新されないシステムにおいては、斯かる メモリは、ノイズ又は他のソースからのエラーを蓄積する可能性がより少ないた め、読出し専用メモリが好ましい、外部データ処理システムに与えられる特定の 問題に応答して本発明の装置に記憶されているデータベースを変えるシステムに おいては、簡単に再プログラムされ得るメモリが好ましい、好ましい実施例にお いて、この再プログラミングは、メモリに記憶されるべき１つ又はそれ以上のデ ータシーケンスがその後に続く、１つ又はそれ以上の特別な目的の間合せシーケ ンス記号を検索手段３２に送ることによって開始され得る９選択的に再プログラ ムされ得る他のメモリ手段、例えば、電気的に消去可能なプログラマブル読出し 専用メモリは、データ処理ハードウェアの技術における当業者には明白であろう 。

並列処理を伴なわない本発明に従う装置は第３図の１４０に示されている。大ざ っばにいって、この装置は、記号のデータシーケンスを記憶するためのメモリ手 段２１２、記号の上記データシーケンスを検索するのに必要なオペレーションを 実行するための検索手段２３２、及び間合せシーケンスを装置に結合するための 受信手段２４６から成っている。この実施例において、上記受信手段２４６は、 この装置をバス４７に結合するための受信回路モリ手段２２を含んでいる。この 間合せ記憶メモリ手段を必要としない実施例は以下に述べられる９間合せシーケ ンスが、従来の設計の通信バス４７を介して受信手段２４６によりこの装置に接 続されている外部データ処理システムによってこの装置に送られると仮定する。

メモリ手段２１２は、各々は、１つのデータ記号を記憶するのに用いられる複数 のデータスロット２１４から成っている。好ましい実施例において、各データス ロットは、第３（ａ）図に示されるように、２つのグループ、即ちデータグルー プ２０及び識別グループ１８に分割される複数の１ビツト２進記憶セル１６から 成っている。識別グループは、スロットに記憶される、記号の型、即ち定数、変 数、又は区切り文字を規定する情報を記憶するのに用いられる。３つの型の記号 が存在するため、少なくとも２つの２進ビツトが、この目的のために割り当てら れなければならない、データグループは、スロットに記憶されている特定の記号 に関連する情報を記憶するのに用いられる。

例えば、スロットに記憶されている記号が、定数「ａ」であった場合、識別グル ープは、定数に対するコードを含み、データグループは、「ａ」に対するコード を含む、可能な定数の数は、２Ｎに等しく、この場合Ｎは、データグループ２０ におけるビットの数である。好ましい実施例において、Ｎは、３０より大きく、 従って、異なった定数の数は、百方より大きい、従って、１つの定数は、上記の 例において用いられているアルファベットの単なる文字ではなく、ワード即ち完 全な英語の表現を表わし得る。Ｎが７であったシステムは、標準的なＡＳＣＩＩ コードでコード化されたアルファベットの文字であった記号を含むデータシーケ ンスを検索するのに有用であろう。

区切り文字は常に、対応する対でもって存在する。スロットが、閉区切り文字を 記憶するのに用いられると、その関連のデータグループ２０は、その対応の閉区 切り文字の位置を確認するのに必要な情報を記憶するのに好ましい実施例におい て用いられる０例えば、各対の区切り文字がラベルを付けられる場合、このラベ ルは、各区切り文字を記憶するのに用いられるスロットのデータグループ２０に 記憶される。

変数の場合、選択的な名前は、データグループ２０に記憶され得る。この名前は 、本発明の装置によっては用いられないが、データシーケンスをより英語官話の ように読ませるのに有用である。更に、斯かるネームは、異なった型の変数に基 づく決定を行う他のより高いレベルのアルゴリズムによって用いられ得る。この 場合、本発明の装置は、本発明の装置によって与えられるデータシーケンスのサ ブセットを選択するよりも高いこのアルゴリズムを用いるデータ処理の使用のた めのデータシーケンスを選択するのに用いられる。

第３図に示されるように、間合せ記憶メモリ手段２２はまた、第３（ｂ）図に示 されるように、それぞれが識別グループ２８及びデータグループ３０に分割され る複数の１ビツト記憶セル１６からなる２４に示される複数のデータスロットを 含んでいる。識別グループ２８は、スロットに記憶されている間合せ記号の型を 規定する情報を含み、データグループ３０は、記憶されている特定の記号に関連 する情報を含んでいる。好ましい実施例において、間合せ記号に用いられる識別 及びデータグループは、データ記号に用いられるグループと同じである。

検索手段２３２は、間合せ記憶メモリ手段２２に記憶されている間合せシーケン スをメモリ手段２１２に記憶されているデータシーケンスの各々と比較する。こ の比較は、間合せシーケンス記号と比較されているデータシーケンスにおける対 応した記号との一連の対による比較として実行される。比較されるべき第１の記 号は、各上記シーケンスにおける第１の記号である。比較されるべきこの後の記 号は、前の比較において比較される記号に依存する。前の比較が、変数及び閉区 切り文字を伴なわなかった場合、比較されるべき次の間合せシーケンス記号は、 前の比較において用いられる間合せシーケンス記号に続く記号であり、用いられ る次のデータシーケンス記号は、前の比較において用いられたデータシーケンス 記号に続く記号である。

１つのシーケンスにおける変数が、他方のシーケンスにおける記号のサブシーケ ンスの開始をマークする閉区切り文字と比較される場合、比較されるべき次の記 号は、変数に続く記号及び問題のサブシーケンスの終りをマークする区切り文字 に続く記号である。これは、一方のシーケンスにおける変数を、他方のシーケン スにおける任意の長さの埋め込まれたサブシーケンスによって満足ならしめる０ 例えば、データシーケンス（ａ、？、ｘ） が、間合せシーケンス （ａ、（ｋ、ｓ）、ｙ） と比較された場合、検索手段２３２によって実行される対による比較は、以下の 通りとなる。先ず、データシーケンスにおける「（」は、間合せシーケンスにお ける「（」と比較される。第２に、データシーケンスにおける「ａ」は、間合せ シーケンスにおける「ａ」と比較される。第３に、データシーケンスにおける「 ？」は、問合せシーケンスにおける「（」と比較される。「（」は、サブシーケ ンスｒｋ、ＩＩ」の始めをマークするため、比較されるべき次の記号、間合せシ ーケンスにおける「）」に続く「ｙ」及びデータシーケンスにおける「？」に続 くｘである。

副表現の回りのこれらの「ジャンプ」の故に、各シーケンスにおける次のシンボ ルを、このシーケンスからとられたデータシーケンス記号と間合せシーケンスか らとられた間合せシーケンス記号との次の対による比較において用いるように指 示するための第１及び第２のインジケータ手段が必要である。これら２つのイン ジケータは、間合せシーケンスと実際に比較されているメモリ手段２１２に記憶 されている各データシーケンスに対して必要となる。第３図に示されている実施 例において、一度に１データシーケンスだけ比較される。一度に幾つかのデータ シーケンスが比較される他の実施例は以下に論じられる。これらのインジケータ を実現する好ましい方法は、データシーケンスに対して選択される記憶のモード に依存する０種々の代替が、以下に論じられる。

データ又は間合せシーケンスに埋め込まれている与えられた副表現はまた、１つ 又はそれ以上のサブシーケンスを含み得ることを銘記すべきである。斯くして、 例えば、比較されるべきａ、ｂ、（ｄ、ｅ、（ｆ、ｇ、）、ｈ、）ｉ）従って、 シーケンス又はサブシーケンスの終りをマークするどの閉区切り文字「）」が、 「ジャンプ」されなければならないシーケンス又はサブシーケンスの初めをマー クする、所与の開区切り文字「（」に対応するのかを、確認するための特定の手 段が与えられなければならない、３つの手段が好ましい、先ず、１つのラベルが 、各対の区切り文字に関連付けられる０例えば、上記のシーケンスにおける各対 の区切り文字には、数、例えば、（ｏａ、ｂ、＋ｄ、ｅ、（ｚｆ、ｇ）ｚｈ、ｉ ）＋ｋ）ｏを割り当てることができる８次に、検索手段が、「（」に遭遇すると 、検索手段は、関連のラベルを読み出して、次にそれが同じラベルを有する「） 」に遭遇するまで問題のシーケンスにおいて探索を進めるだけでよい、このシス テムが首尾良く作動するために、特定の対の区切り文字をマークするのに用いら れるラベルは、上記の対の区切り文字によってマークされるサブシーケンス内で 反復されなくてもよい。

第２に、対応の開区切り文字の位置は、記号のシーケンス又はサブシーケンスの 初めをマークする各閉じ切り文字と共に記憶され得る。検索手段は、次に、閉じ 切り文字において規定される位置に「ジャンプ」する、この手段を用いる好まし い実施例において、この位置は、対応の開区切り文字の後の次の記号に到達する ためにスキップする記号の数として記憶される。対応の区切り文字の位置をコー ド化するこのフオームは、２つの利点を有している。先ず、それが配置されてい るデータ又は間合せシーケンスの絶対的位置に依存しないことである。従って、 このジャンプ位置を変化させなくてもデータシーケンスをメモリに再配置できる 。第２に、このジャンプ数は、記憶されているデータシーケンスの最大炎より少 ないため、この情報を記憶するのに必要なメモリ記憶は、メモリにおける特定の 固定点に対する相対的な上記区切り文字の位置を記憶するのに要するメモリ記憶 よりも小さい、対応の開区切り文字のメモリ位置をジャンプ位置として用いたシ ステムは、メモリ手段２１２に記憶されている記号の数と同じ位の閉じ切り文字 の各々を有する数を記憶することが必要となる。

最後に、対応する開区切り文字の位置は、問題の閉じ切り文字の後に遭遇される 閉じ切り文字及び開区切り文字の数を計数することによって確認され得る０例え ば、検索手段２３２は、検索手段が閉じ切り文字を含むシーケンスの段階を一度 に１記号ずつ踏む時遭遇される閉じ切り文字及び開区切り文字の数を計数するの に用いられるカウンタを含み得る。このカウンタは、閉じ切り文字が遭遇される 毎に増分され且つ開区切り文字が遭遇される毎に減分される。カウンタがその初 期状態に戻ると、元の閉じ切り文字によってマークされるサブシーケンスは、ジ ャンプされる。比較に用いられる次のシンボルは、カウンタがその初期位置に戻 るという結果になる開区切り文字の後の記号である。ここで、第１開区切り文字 はまた、このカウンタによって計数されなければならない。

上記のように、検索手段２３２は、間合せシーケンス記号とデータシーケンス記 号との対による比較を実行する。再び第３図について説明すると、比較されるべ きデータシーケンス記号は、第１インジケータ手段３４によって規定される。比 較において用いられるべき間合せシーケンス記号は、第２インジケータ手段３６ によって規定される。好ましい実施例において、これらのインジケータ手段３４ ．３６の各々は、問題のメモリブロックの長さ全体に沿って動作するシフトレジ スタによってそれぞれ実現される３３及び３７に示されているポインタからなる 。上記シフトレジスタにおける１ビツトは、「１」にセットされ且つ残りのビッ トは、「０」にセットされる。ポインタは、シフト命令をこのレジスタに送るこ とによって歩進される。

上記第１及び第２のインジケータ手段によって示されるこれらの記号は、比較手 段２８によって比較される。上記第１インジケータ手段３４によって示されるデ ータ記号は、第１のインジケータ手段３４の一部である第１宛先指定回路４０に よって上記比較手段２８に送られる。同様にして、上記第２インジケータ手段３ ６によって示される間合せシーケンス記号は、上記第２インジケータ手段３６の 一部である第２宛先指定回路４２によって上記比較手段２８に送られる。好まし い実施例において、宛先指定回路４０及び４２は、従来の多重化回路である。

比較手段２８は、２つの代替状態、即ち「一致する」及び「一致しない」状態を 有する出力信号を発生する。この一致される信号は、比較される２つの記号が、 同じかあるいはこれらの記号の一方が変数である時に発生する。２つの代替状態 を有するフラグ手段４８は、この出力信号をモニタする。フラグ手段４８は、第 １の間合せシーケンス記号とデータシーケンスの一方における対応する記号との 比較が開始されると第１の即ち一致した状態にセットされる０間合せ記号と上記 データシーケンスからのデータ記号との対による比較のどれかが一致した出力を 発生できなかった場合、フラグ手段４８は、問題のデータシーケンスが、間合せ シーケンスに一致しなかったこと及び突き合せプロセスが中断されたことを示す 、第２の即ち一致されない状態にセットされる。最後の間合せシーケンス記号、 問題のデータシーケンスにおける対応のデータシーケンス記号と比較された後フ ラグ手段４８が依然として第１状態にセットされている場合、このフラグ手段は 、上記データシーケンスをイネーブルして、受信手段４６に読み出させる。

検索手段２３２に含まれているインジケータ歩道手段４４は、第１及び第２イン ジケータ手段を制御するのに且つ種々の初期化操作を実行するのに用いられる。

この実施例において、間合せシーケンスにおける最後の記号の受信は、突き合せ オペレーションの開始を示す信号を送出するのに用いられる。インジケータ歩進 手段は、第１インジケータ手段３４をセットしてメモリ手段２１２に記憶されて いる第１データシーゲンスにおける第１記号を示し且つ第２インジケータ手段３ ６をセットして間合せシーケンスの第１記号を示す０次にこのインジケータ歩進 手段は、フラグ手段４８をその第１状態に初期化して、比較手段３８に信号を送 ることによって第１比較を開始する。各比較が完了した後、インジケータ歩道手 段４４は、フラグ手段４８をテストして、それが、記号が一致しなかったことを 示すその第２状態にセットされているかを決定する。フラグ手段４８がその第２ 状態にある場合、インジケータ歩進手段は、第１指示手段３４を次のデータシ間 合せシーケンスの第１記号を示し、フラグ手段４８をその第１状態にリセットし 、次に比較されるべき指示された記号のために信号を送る。

フラグ手段４８は、２つの記号が一致したことを示す場合、インジケータ歩進手 段４４は、間合せシーケンスにおける最後のシーケンスは、それに対応するデー タシーケンス記号と比較されたかを見るためにテストする。比較されている場合 、インジケータ歩進手段４４は、受信手段２４６における受信回路４５に合図し て、問題のデータシーケンスを読み出１．インジゲータ歩進手段４４は次に、第 １指示手段３４を進めて、次のデータシーケンスの第１の記号を示し、第２イン ジケータ手段をリセットして、第１間合せシーケンス記号を示し、比較手段に信 号な送って開始させる。

比較された最後の間合せ記号は、間合せシーケンスにおける最後の記号でなかっ た場合、インジケータ歩進手段４４は、第１指示手段３４を進めて、たった全比 較されたばかりの記号に続くデータシーケンス記号を示し、第２インジケータ手 段３８を進めて、たった全比較されたばかりの記号に続く次の間合せシーケンス 記号を示すが、たった全比較されたばかりの記号の内一方が変数であり、他方が 開区切り文字であった場合はそうではない、この場合、インジケータ歩進手段４ ４は、この変数を有するシーケンスにおける指示手段を進めて、上記変数に続く 記号を示し、そしてこのインジケータ歩進手段４４は、この開区切り文字を有す るシーケンスにおける指示手段を進めて、上記開区切り文字に対応する開区切り 文字に続く記号を示す。

メモリ手段２１２に記憶されている最後のデータシーケンスの最後のデータシー ケンス記号が、比較手段３８によって比較された時、インジケータ歩進手段４４ は、別の間合せシーケンスが受信手段４６に送られるまで待機状態に入る。

インジケータ歩進手段４４はまた、受信手段からデータシーケンスをメモリ手段 ２１２にコピーする。好ましい実施例にＪ３いて、これは２問題のデ・−タシー ケンスに先行する所定の記号によって示される。この記号が、１つ又はそれ以上 のパスライン４７を通しで信号によりで示される実施例は、当業者には明白であ る結合されるデータ処理システムの速度及び記憶密度要求条件に依存する。原則 的に、データシーケンスは、下記に述べるように、幾つかの異なった物理メモリ デバイスの任意のデバイスに記憶することができる６好ましい実施例において、 記憶データシーケンスを検索するのに必要な時間を低減するのに並列処理が用い られる。これを達成するために、検索手段３２は、間合せ記号をデータシーケン ス記号と比較するための幾っがの検索プロセッサによって実施される。記憶され たデータシーケンスを探索して特定の間合せシーケンスに対応するシーケンスを 見つけるのに必要な時間は、上記検索プロセッサの速度及び数に依存する。プロ セッサのメモリ位置に対する比が大きいシステムは、最小量の時間で対応のデー タシーケンスを検索し、上記間合せシーケンス記号は、本発明の装置に結合され た時に、与えられた間合せシーケンス記号に比較されるべき各データシーケンス 記号が、対応の検索プロセッサに得られることを保証するのに十分な速度を有す る最短の検索時間は、記憶されたデータ毎に１つのプロセッサについて得られる 。このシステムは、付加的な検索プロセッサを構成するのに用いられたであろう 回路が付加的なメモリスロットを構成するのに用いられているより少ない検索プ ロセッサを有するシステムよりもメモリ密度が低く記憶データ記号当りの高いコ ストを有する。従って、速度と記憶データ記号当りのコストの間にはかね合いが 存在する。

データシーケンスを記憶するための可能なメモリデバイスは、２つの広いクラス 、即ち静的デバイス及び循環記憶デバイスの２つに分割することができる。コン ピュータメモリにおいて用いられる標準的なランダムアクセスメモリチップは、 静的記憶デバイスの典型である。磁気ディスク及び光学ディスク等の回転記憶デ バイス及びシフトレジスタ記憶ループは、循環記憶デバイスの典型である。使用 される記憶デバイスの型は、間合せシーケンスがデータシーケンスに比較される 最適モードを決定する。

静的記憶システムが、データシーケンスに用いられる場合、間合せシーケンスは 、データシーケンスを通って「循環」する突き合せシステムが最適である。ここ で、間合せシーケンスの各記号は、記憶データシーケンスの各々において対応す る記号と比較される。与えられた間合せシーケンス記号を伴なうこれら全ての比 較が完了すると、次の間合せシーケンス記号は、記憶されたデータシーケンスに おける対応の記号の各々と比較され、以下同様にして行なわれる。比較オペレー ションの各段階における上記間合せシーケンスとの依然として可能な突き合せで あるこれら全てのデータシーケンスに絶えず注意するために、フラグが、データ シーケンスの各々と関連しなければならない。

フラグは、検索オペレーションの開始においてセットされる。

これら対による突き合せの一方が一致しない場合、突き合せに一致しない記号を 含むデータシーケンスに関連するフラグがリセットされる。最後の間合せシーケ ンス記号が、記憶されたシーケンスにおけるその対応する記号と比較された後そ の初期状態にあるフラグによって依然としてマークされるこれらのデータシーケ ンスは次に、本発明の装置が接続されている外部データ処理システムに結合され る。

この実施例は、対による比較に現在用いられている間合せシーケンス記号が、本 発明の装置に記憶されることだけを要求する。従って、任意長さの間合せシーケ ンスを伴う探索に適用可能である。データシーケンスにおける変数は、間合せシ ーケンスにおける非常に長いサブシーケンスと突き合せ可能ななめ、この装置に 記憶されるべきデータシーケンスの最大炎を知っていた場合でも、遭遇され得る 最長間合せシーケンスを前もって決定することが可能でない。

データシーケンスの記憶のための静的メモリシステム及び比較を実行するための 多重プロセッサを用いる本発明の実施例が、第４図の８０に示されている。ここ で、第１図に示されているメモリ手段１２は、複数の独立の静的メモリ９２とし て実施されている。各静的メモリ９２は、スロット１４４の連続ブロックからな っている。各スロット１４４は、第３図に関して上記で述べた様式でもって１つ のデータシーケンス記号を記憶するのに用いられる。これらの静的メモリ９２の 各々は、上記静的メモリに記憶されたデータシーケンス記号とバス８６によって 本発明の装置に結合された間合せ記号との全ての対的比較を行うための比較回路 を含む独立の検索プロセッサ９４に接続されている０本実施例の好まし２い形に おいて、この間合せ記号は、データシーケンス記号を記憶するのに用いられるス ロット１４４に用いられるものと同様の１ビツト記憶セルのブロックから構成さ れたバッファ８２に保持される。受信手段８４は、本発明を外部データ処理シス テムに接続する通信バス８６からバッファ８２をロードする。個々の検索プロセ ッサ９４は、互いのプロセッサと且つ検索手段８４と第２バス９８を介して通信 する。バッファ８２の内容は、間合せバス９９を通して検索プロセッサ９４の各 々と通信している。バッファ８２が本発明の装置に結合されている外部データ処 理システムに含まれている実施例は、当業者には明白であろう。

例示的検索プロセッサ９４及びその関連の静的゛メモリ９２のより詳細な略図が 第５図の９３に示されている。各検索プロセッサ９４は、検索プロセッサ９４に 結合されている静的メモリ９２に記憶されているデータシーケンス記号を間合せ バス９９を通して通信される間合せ記号と比較するための比較手段１２２を含ん でいる。

上記間合せ記号と比較されるべきデータシーケンス記号は、上記データシーケン ス記号を比較手段１２２及びポインタ１２１と結合するための宛先指定回路１２ ６を含むインジケータ手段１２０によって識別される。上記インジケータ手段１ ２０は、インジケータ歩進手段１２４の制御下にある。

この実施例は、与えられた間合せ記号を次の間合せ記号を伴う比較に進む前に記 憶されたデータシーケンスの各々において対応する記号の各々と比較することに よって動作するため、間合せ記号と比較されるべきデータシーケンスにおける次 のデータシーケンス記号を示す各データシーケンスに対して独立のポインタ手段 が維持されなければならない。これらのポインタは、インジケータ歩道手段１２ ４に接続されている独立のポインタメモリ手段１００に記憶される。ポインタメ モリ手段１００は、第５（ａ）図に示されるように、各々は、３つのグループの １ビツト・記憶セル１０８からなるポインタ１０２に分割される。

各ポインタは、この比較手段１２２によって比較されるべき１対の記号を、間合 せシーケンスからの１つの記号及び上記比較手段１２２に結合された静的メモリ ９２に記憶されたデータシーケンスからの１つの記号を規定する。ポインタグル ープ１０６は、問題のインジケータ歩進手段１２４に接続されている静的メモリ ９２に記憶されている記号を有するデー・タシーケンスの１つにおいて比較され るべき次のデータシーケンス記号の位置を示す。

第２グループは、２つの代替状態、即ち「保持」及び「レディ」の内一方を有す る保持フラグ１０４からなる。保持状態は、その位置が第１グループ１０６にお いて示されているデータシーケンス記号に比較されるべき間合せ記号が、まだ間 合せバス９９にないことを示す。第３グループ１０７は、与えられた間合せシ・ −ゲンス開区切り文字に対応する開開合せシーゲンス区切り文字を識別するのに 必要な情報を記憶するのに用いられる。

第３図における実施例に示されている第２インジケータ手段３６及び第２の宛先 指定回路４２は、この実施例においては必要ない、保持フラグ１０４及び第３グ ループｉ０７は、第３図に示される実施例において供される第２．インジケータ 手段３６と同じ機能を供する。即ち、これらは、対による比較において用いられ るべき次の問合せシーケンス記号を識別する。任意の与えられた時間において１ つの間合せ記号しか得られないため、現在の間合せ記号又はまだ受け取られてい ない間合せ記号が、比較されるべき記号であるか否かを示すのに、二状態デバイ スしか必要とされない、第２宛先指定回路４２は、この実施例においては必要な い、第４図に示されている実施例において、この宛先指定機能は、間合せシーケ ンスを一度に１記号だけ本発明の装置に与える外部データ処理システムによって 実行される。

各間合せシーケンス記号が間合せバス９９を通して検索プロセッサ９４に結合さ れると、インジケータ歩進手段１２４は、その関連のポインタメモリ手段１００ におけるポインタを介して循環する。

レディ状態にあるその関連の保持フラグ１０４を有する各ポインタ１０２に対し て、インジケータ歩道手段１２４は、比較手段１２２に、上記ポインタ１０２の ポインタグループ１０６によって識別されるデータシーケンス記号を間合せバス ９９における間合せシーケンス記号と比較させる。比較手段１２２が、問題のデ ータシーケンス記号が上記間合せ記号に対応することを示す出力信号を発生する 場合、インジケータ歩道手段１２４は、間合せ記号との対による比較に用いられ るべき上記データシーケンスにおける次のデータシーケンス記号を識別するべく 、問題のデータシーケンスに関連するポインタグループ１０６を変える。これら ２つの記号は、同等であるかあるいは上記記号の一方が変数であった場合、比較 手段１２２は、問題のデータシーケンス記号が、上記間合せ記号に対応したこと を示す上記出力信号を発生する。

可変データシーケンス記号は、間合せバス９９の開区切り文字問合せシーケンス 記号と比較される場合、インジケータ歩道手段は、問題の可変データシーケンス 記号を規定したポインタ１０２に含まれる保持フラグ１０４をセットし、上記ポ インタ１０２の第３グループ１０７における対応する開区切り文字を認識するの に必要なデータを記憶する。インジケータ歩道手段が、保持状態にある保持フラ グ１０４に遭遇すると、インジケータ歩道手段は、現在間合せバス９９にある間 合せ記号をテストして、それが、上記保持フラグ１０４に上記保持状態にセット せしめた開区切り文字に対応する開区切り文字であるかを決定する。そうである 場合、インジケータ歩道手段は、上記保持フラグ１０４をレディ状態゛にリセッ トする。

上記ポインタ１０２の１つによって示されるデータシーケンス記号は、上記記号 が、それが比較された間合せシーケンス記号と対応したことを示す出力の上記比 較手段１２２からの発生の結果をもたらさなかった場合、問題のポインタ１０２ におけるポインタグループＩＯ６は、このポインタがこれ以上、データシーケン ス記号を規定するように働かないことを示す所定の値にセットされる。全ての斯 かるインジケータは、この所定の状態にセットされる場合、間合せシーケンスに 対応するデータシーケンスが何も装置の中には存在せず、特別な出力信号が５通 信バス８６信する。これにより、上記外部データプロセッサは、間合せシーケン スを妨げて、これにＪ４り処理時間を節約する。

特定のデータシーケンスは、２つ以、Ｊ二の静的メモリ９２における記憶スロッ ト１４４を占有する場合、１つの検索プロセッサ９４におけるインジケータ歩進 手段１２４は、上記データシーケンスからの記号な用いてなされるべき次の比較 が、隣接の静的メモリ９２におけるスロット１４４に記憶されている記号を含む 時、バス９８を通して隣接のインジケータ歩進手段１２４に合図する。上記隣接 のインジケータ歩進手段１２４は次に、そのポインタメモリブロック１００にお けるポインタ１０２を上記データシーケンスに割り当てる。

ｆｉｆ＆の間合せ記号が上記間合せバスを通して通信され且つその対応のデータ シーケンス記号に比較された後、検索プロセッサにおけるポインタ１０２によっ て示されるように全ての対による比較を通過した任意のデータシーケンスは、次 に、通信バス８６を通して外部データ処理システムに読み出される。これらは、 データシーケンスの最後の記号が、この間合せシーケンスの最後の記号と比較さ れたデータシーケンスである。

可能な並列処理の度合は、検索プロセッサ９４の数に依存する。

各々の記憶されたデータシーケンスがらの１つのデータシーケンス記号のみが、 与えられた間合せ記号に比較されるため、最高の度合の並列処理が、記憶データ シーケンス毎に１つの検索プロセッサ９４について達成される。

循環メモリ記憶システムがデータシーケンスに用いられる場合、間合せシーケン スは、静的状態を保ち、データシーケンスは、各データシーケンスが間合せシー ケンスのそばと「流れる」時、間合せシーケンスに対して突き合わされる。循環 メモリを用いている本発明の実施例が、第６図の５０に示されている。データシ ーケンスは、各々が、１つのデータシーケンス記号のための記憶を提供している 複数のスロット３１４を含むメモリルー１５２に記憶されている。これらのスロ ットは、各々は、識別グループと及びこの実施例における対応のグループと同じ 機能を果たすデータグループに分割される、第３図に示される実施例のスロット と同様の様式でもって１ビツト記憶セルのブロックから構成され得る。メモリル ー１５２に記憶されているデータは、それが比較手段２３８への結合のために且 つインジケータ歩進手段２４４による読出し及び書込みのために得られるタップ 点５４を通って循環する。この実施例において、第３図に示されている第１イン ジケータ手段３４の諸機能は、２つの代替状態、即ち、「保持」及び、比較手段 ２３８に現在結合されているデータシーケンス記号は、インジケータ手段２３６ によって識別される間合せ記号に比較されるべきであるか否かを示す「レディ」 の１つを有する保持フラグ５６によって実行される。保持フラグは、保持状態に ある場合、比較手段２３８は、現在タップ点５４にあるデータシーケンス記号を 比較しないように抑止される。インジケータ歩進手段２４４は、間合せシーケン スの第１間合せ記号が、データシーケンスの第１記号に比較される時に保持フラ グをレディ状態にセットする。保持フラグ５６は、可変間合せシーケンス記号が 、閉区切り文字に比較された時に保持状態にセットされる。

保持フラグ５６は、上記保持フラグ５６を保持状態にセットせしめた閉区切り文 字に対応する閉区切り文字が、タップ点５４においてインジケータ歩進手段２４ ４によって読み出された時にレディ状態にリセットされる。

各比較において用いられるべき間合せシーケンス記号は、インジケータ手段２３ ６によって規定される。インジケータ手段２３６は、インジケータ歩進手段２４ ４の制御下にある。インジケータ手段２３６は、規定された間合せ記号を比較手 段２３８に結合するための宛先指定回路２４２及び間合せシーケンスが記憶され る間合せ記憶メモリ手段２２２におけるスロットを識別するためのプリンタ２３ ７を含んでいる。

フラグ手段２４８は、上記シーケンスの１つに含まれているデータシーケンス記 号と上記間合せシーケンスからの間合せ記号との間の全ての対による比較の結果 、第３図に示されている比較手段３８と同じように機能する比較手段２３８から の一致された出力信号が生じたデータシーケンスにフラグを立てるのに用いられ る。斯かるフラグの立てられたシーケンスは、最後の間合せシーケンス記号は、 問題のデータシーケンスにおける！ｆ＆のデータシーケンス記号に比較された後 受信手段２４６を介して読み出される。

第４図に示されている静的メモリシステムとは対照的に、この実施例は、本発明 の装置が、このシーケンスにおいて探索されている現在の記号だけでなく、間合 せシーケンスの全体のための記憶を行うことを要求する０間合せシーケンスは、 受信手段２４６の一部である間合せ記憶メモリ手段２２２に、上記のように記憶 される。このメモリは、第３図に示されている実施例における間合せ記憶メモリ 手段２２の所で述べた構造と同じ構造を有するスロットで構成される０間合せシ ーケンス全体が、本発明の装置に含まれるべきであるという要求は、探索され得 る間合ちれる可能性のある最長間合せシーケンスの推定を通常行うことができる ため、これは厳しい制限ではない、また、間合せシーケンスは、幾つかのより小 さなシーケンスに分割することができ且つ装置をリセットし、次に突き合せプロ セスを継続することなしに第２間合せシーケンスをロードされるための手段を組 み込むことができる。

間合せシーケンスは、問題の間合せシーケンスがその後に続く受信手段２４６に 特別な所定の間合せ記号を送ることにより、第６図に示されている本発明の装置 にロードされる０間合せシーケンスの初めをマークする閉区切り文字に対応する 閉区切り文字によって合図される間合せシーケンスの′終りの受信は、突き合せ プロセスの開始を合図するのに用いられる。この信号を受信する際、インジケー タ歩道手段２４４は、第３図に示されている実施例に示されているインジケータ 歩道手段４４によって用いられる方法と同様の方法でもって種々のフラグをそれ らの初期状態にセットし、第２インジケータ手段２３６をセットして間合せシー ケンスの第１記号を示し、次に、データシーケンスの第１記号がタップ点におい て読み出されるのを待機する。上記第１記号が存在する時、突き合せプロセスは 、第３図に述べられている本発明の実施例と同様の方法で始められる。

本発明の静的実施例及び循環実施例の両方において、検索手段２３２及び３３２ はそれぞれ、標準的なマイクロプロセッサチップから構成され得る。また、ＶＬ ＳＩ回路設計の当業者にとって良く知られた方法を用いて、特種な目的のプロセ ッサを構成することもできる。このプロセッサはまた、第１及び第２メモリ手段 と同じＶＬＳＩチップの上に実施され得る。

上記の実施例の内どれが与えられたシステムにとって最適であるかという選択は 、一般的に、所望のシステムの記憶密度及び比較速度の要求条件に依存する。各 データ記憶データシーケンスを有する１つの検索プロセッサ９４が存在する第４ 図及び第５図に述べられているシステムと同様の静的システムは、最短の可能な 探索時間を提供する。斯かるシステムは、間合せシーケンスの各記号を１つの比 較サイクルにおける記憶データシーケンスの各々におけるその対応の記号と比較 することができる。

しかしながら、検索プロセッサを構成するのに必要な「チップスペース」が、記 号を記憶するのに用いられるスロットを構成するのに必要なチップスペースを超 過するため且つデータシーケンスの潜在的な数が大きいため、この型のメモリは 、非常に低い密度のメモリを有し、従って記憶記号当りのコストが高くなる。

間合せシーケンスのための静的記憶バッファを有する循環メモリに基づくシステ ムは、より高い密度の記憶を提供し、しばしばより低いコストを提供する。磁気 ディスク等の回転記憶媒体は、標準ランダムアクセスメモリチップを用いて得ら れるコストよりもかなり低いワード当りコストでもってデータを記憶することが 可能である。光学ディスクは、これもまた、記憶記号当りのコストの何分の−か で、集積回路メモリより高い記憶密度を提供する可能性を有している。しかしな がら、これらのデバイスは、所望のデータ記号がタップ点のそばを通過するのを 待機しなければならないため、上記で論じた静的データシーケンス記憶システム より固有的に遅い、この要求条件は、本発明の循環メモリ実施例における探索を 完了するのに必要な時間をセットする。特定のデータシーケンスは、間合せシー ケンスに対応できない場合、検索手段は、データシーケンスの全体がタップ点を 通過するのを依然として待機しなければならない。

従って、探索を実行する時間は、メモリルーズの内容の全体がタップ点を通過す るのに必要な時間である。

対照的に、記憶データシーケンス当り１つの比較回路を含む１つの検索プロセッ サを用いる本発明の静的メモリ実施例において探索を実行するのに必要な最大時 間は、間合せシーケンスを読み出すのに必要な時間である。静的メモリ実施例に おいて、データシーケンスの全てが、対による比較のプロセスにおいて早い時期 に不一致だった場合、この結果は、即座に出力され、次の探索は、間合せシーケ ンスの全体が受信されるのを待機しなくても開始され得る。

循環記憶システムの速度上の制限は、並列の幾つかの読出しステーションを用い ることになりある程度克服することができる。各ステーションは、循環ループに おける異なったタップ点を通過する時のデータを見る。これらのタップ点の各々 は、間合せシーケンスへのアクセスを有する独立の検索プロセッサを含んでいる 。従って、メモリ全体を読み出すのに必要な時間は、タップ点の数に等しい因数 だけ低減する。

本発明は、主に、人工知能システムの使用に意図されているが、外部データ処理 システムなしに用いられ得る。例えば、キーボード及び表示端末装置からなるシ ステムは、本発明の装置を作動するのに十分である。この単純なシステムにおい て、データシーケンスは、読出し専用メモリに記憶されている固定ライブラリの 形となり得る。このライブラリへのエントリは、間遠の間合せシーケンスを規定 する記号をタイプすることにより選択される。検索プロセッサは、装置への及び 装置からの情報の流れを制御するための特定の命令キーに応答するようにプログ ラムされる。

本発明の種々の実施例が、本明細書に述べられてきたが、本発明の請求の範囲か ら逸脱することなく種々の変更及び修正をなすことができることを了解されよう 。

国際調査報告

Claims (19)

【特許請求の範囲】
1. １．記号の１つ又はそれ以上のデータシーケンスの記憶及び検索のためのメモリ システムにおいて、記号の１つ又はそれ以上のデータシーケンスを記憶するため のメモリ手段であって、上記記号が、定数、変数、及び区切り文字を含むメモリ 手段；上記メモリシステムに結合された記号の問合せシーケンスを受信するため の手段；記号の上記問合せシーケンスに対応する上記メモリ手段がら記号の各デ ータシーケンスを検索するための手段であって、上記２つのシーケンスが、各変 数を、定数又は定数及び区切り文字の組合せであって、区切り文字から始まり区 切り文字に終る組合せで置き換えることにより同等となり得る場合、記号のデー タシーケンスは、上記記号の問合せシーケンスに対応すると定義される検索手段 を含むことを特徴とするメモリシステム。
2. ２．上記メモリシステムに結合された記号のデータシーケンスを上記メモリ手段 に記憶せしめるための手段を更に含むことを特徴とする請求の範囲第１項に記載 のメモリシステム。
3. ３．上記受信手段が、記号の上記問合せシーケンスを記憶するための問合せ記憶 メモリ手段を含むことを特徴とする請求の範囲第１項に記載のメモリシステム。
4. ４．上記記号の問合せシーケンスに対応する上記メモリ手段がら記号の各データ シーケンスを検索するための上記手段が、データシーケンス記号を識別するため の第１インジケータ手段；問合せシーケンス記号を識別するための第２インジケ ータ手段；上記第１指示手段によって識別されるデータシーケンス記号を、上記 第２インジケータ手段によって識別される問合せシーケンス記号と比較するため の且つ２つの代替状態、即ち比較された上記の２つの記号が同一であったかある いは上記記号の少なくとも１つが変数であったかを示す一致された状態、及び上 記２つの記号は、異なり、両方とも変数でなかったことを示す一致されない状態 の内１つを有する出力信号を発生するための比較手段；上記比較手段出力信号に 応答するフラグ手段であって、一致されない状態にある任意の出力信号の発生を 示すためのフラグ手段；上記第１インジケータ手段に選択されたデータシーケン スの第１記号を示させるための、上記第２インジケータ手段に上記問合せシーケ ンスの第１記号を示させるための、且つ上記比較手段に上記の識別された記号を 比較させるための手段、及び上記第１インジケータ手段に次のデータシーケンス 記号を識別させるための、上記第２インジケータ手段に次の問合せシーケンス記 号を識別させるために、且つ上記比較手段に終了条件が検出されるまで上記識別 された記号を比較させるための手段を含むインジケータ歩進手段；上記終了条件 を検出するための手段；及び上記終了条件に応答する手段であって、上記フラグ 手段が、上記比較のどれも、一致されない出力信号の発生という結果を生じない ことを示す場合、上記の選択されたデータシーケンスを出力するための手段を含 むことを特徴とする請求の範囲第１項に記載のメモリシステム。
5. ５．上記比較手段が、上記問合せシーケンスの最後の記号をデータシーケンス記 号と比較する時、上記終了条件が生じると定義されることを特徴とする請求の範 囲第４項に記載のメモリシステム。
6. ６．上記比較手段が、上記の選択されたデータシーケンスの最後の記号を問合せ シーケンス記号と比較する時、上記終了条件が生じると定義されることを特徴と する請求の範囲第４項に記載のメモリシステム。
7. ７．上記比較手段が、上記の選択されたデータシーケンスの最後の記号を、上記 問合せシーケンスの最後の記号と比較する時あるいは一致されない状憲にある出 力信号が発生された時に、上記終了条件が生じると定義されることを特徴とする 請求の範囲第４項に記載のメモリシステム。
8. ８．上記区切り文字が、対応の対、即ち、記号のシーケンス又は記号のシーケン スに埋め込まれた記号のサブシーケンスの始めをマークするのに用いられている 開区切り文字及び記号の上記シーケンスのあるいは記号のサブシーケンスの終り をマークするのに用いられている対応する閉区切り文字の形で存在し、且つ、上 記インジケータ歩進手段が、上記の選択されたデータシーケンス又は上記問合せ シーケンスにおける与えられた關区切り文字に対応する閉区切り文字を決定する ための手段を含み、耳つ、上記インジケタ歩進手段によって識別せしめられる上 記の次のデータシーケンス記号及び上記の次の問合せシーケンス記号は、上記比 較手段によって前に比較された記号の後の次の順次データシーケンス記号及び上 記比較手段によって前に比較された記号に続く次の順次問合せ記号であり、しか し、上記の前に比較された記号が変数及び開区切り文字である場合はそうではな く、このような場合には、上記次の記号は、上記の変数に続く記号及び上記開区 切り文字に対応する閉区切り文字に続く記号であることを特徴とする請求の範囲 第４項に記載のメモリシステム。
9. ９．どの閉区切り文字が与えられた開区切り文字に対応するかを決定するための 上記手段が、各上記区切り文字と共にラベルを記憶するための手段を含み、上記 ラベルが、対応する対の区切り文字の各上記区切り文字に対して同一であり且つ 上記ラベルが、上記対の区切り文字によってマークされるシーケンス又はサブシ ーケンスの記号内の任意の他の対の区切り文字において反復しないことを特徴と する請求の範囲第８項に記載のメモリシステム。
10. １０．どの閉区切り文字が与えられた閉区切り文字に対応するかを決定するため の上記手段が、上記閉区切り文字を含む記号のシーケンスにおけるその対応の閉 区切り文字の位置を各開区切り文字の一部として記憶するための手段を含むこと を特徴とする請求の範囲第８項に記載のメモリシステム。
11. １１．どの閉区切り文字が記号のシーケンスにおける与えられた開区切り文字に 対応するかを決定するための上記手段が、区切り文字を計数するための手段を含 み、上記計数手段は、上記第２インジケータ手段が、記号の上記問合せシーケン スの第１の記号を示す時に所定の初期状態に初期化され、上記計数手段は、開区 切り文字が記号のシーケンスにおいて遭遇される毎に増分され、且つ上記計数手 段が、閉区切り文字が上記記号のシーケンスにおいて遭遇される毎に等量減分さ れ、上記対応の閉区切り文字は、上記計数手段をその初期状態に戻さしめる区切 り文字であることを特徴とする請求の範囲第８項に記載のメモリシステム。
12. １２．上記メモリ手段が、各々が、１つの記号を有するのに用いられ且つ連続１ ビット記憶セルのブロックを含んでいる複数のスロットを含み、且つ、上記スロ ットが、２つのグループ、即ち識別グループ及びデータグループに分割され、上 記識別グループが、上記スロットに記憶されている記号の型を識別するための少 なくとも２つの１ビット記憶セルから成り、上記データグループ、上記１ビット 記憶セルの残りを含むことを特徴とする請求の範囲第８項に記載のメモリシステ ム。
13. １３．どの閉区切り文字が各区切り文字に対応するかを決定するための上記手段 は、その識別グループが上記スロットが開区切り文字を記憶していることを示す スロットにおいて、上記開区切り文字に対応する閉区切り文字のアイデンティテ ィを示すデータをデータグループに含むための手段を含むことを特徴とする請求 の範囲第１２項に記載のメモリシステム。
14. １４．上記区切り文字が、対応の対、即ち、記号のシーケンス又は記号のシーケ ンスに埋め込まれた記号のサブシーケンスの始めをマークするのに用いられる開 区切り文字及び記号の上記シーケンス又はサブシーケンスの終りをマークするの に用いられる対応する閉区切り文字の形で存在し、上記検索手段は、与えられた 開区切り文字に対応する閉区切り文字を識別するための手段；記号の対応する対 、即ち上記問合せシーケンスからの１つの記号及び上記データシーケンスの１つ の記号を規定するための手段；記号の各規定された対応する対を比較するための 手段であって、２つの状態を有する出力信号、即ち比較された上記記号が同一で あったかあるいは上記記号の少なくとも１つが変数であったかを示す一致された 出力信号及び上記記号が、一致せず、上記記号の両方共変数でなかったことを示 す一致されない出力状態を発生するための手段；インジケータ歩進手段であって 、上記規定手段に各データシーケンスの第１記号及び上記問合せシーケンスの第 １記号を記号の第１の対応する対として初期的に規定せしめるための手段であっ て、上記比較手段は、記号の上記第１の対応する対と比較するためにこれに応答 して作動する手段上記規定手段に、上記比較手段が一致された出力信号を発生し 且つ比較されたどの記号も、データシーケンスの最後の記号あるいは上記問合せ シーケンスの最後の記号でなかった毎に、次のデータシーケンス記号及び次の問 合せシーケンス記号からなる直後の対応する対の記号を連続的に規定させるため の手段であって、上記比較手段が、斯かる上記の直後の対応する対の記号を比較 するためにこれに応答して作動し、上記次のデータシーケンス記号は、上記比較 手段によって前に比較された記号に続く隣接のデータ記号であり且つ上記次の問 合せシーケンス記号は、上記比較手段によって前に比較された記号に続く隣接の 問合せシーケンス記号であり、しかし、前の比較が、変数と開区切り文字との間 で行なわれた場合はそうではなく、この場合は、規定されるべき次の記号は、上 記変数に続く隣接の記号及び上記開区切り文字に対応する閉区切り文字に続く隣 接の記号である手段；上記データシーケンスの最後の記号は、上記問合せシーケ ンスの最後の記号と比較されている各データシーケンスを読み出すための手段を 含むインジケータ歩進手段を含むことを特徴とする請求の範囲第１項に記載のメ モリシステム。
15. １５．上記メモリ手段は、それぞれが１データシーケンス記号を記憶する複数の 連続ブロックのスロットを含んでおり、且つ上記比較手段は、各々が、各上記ブ ロックに作動的に接続されている複数の比較回路を含んでおり、各上記比較回路 は、上記比較回路に有効に接続されているスロットのブロックにおけるデータシ ーケンス記号を含む上記の規定された対応する対の記号の間の比較を行うことを 特徴とする請求の範囲第１４項に記載のメモリシステム。
16. １６．１つ又はそれ以上のデータシーケンスの記号を記憶せしめているメモリシ ステムであって、上記データシーケンス記号は、３つの型の記号、即ち、定数、 変数、及び区切り文字を含むように定義され、上記区切り文字が、対応する対、 即ち記号のシーケンスあるいは記号のシーケンスに埋め込まれている記号のサブ シーケンスの開始をマークするのに用いられる開区切り文字及び記号の上記シー ケンス又はサブシーケンスの終りをマークするのに用いられる対応の閉区切り文 字の形で存在するメモリシステムにおける、上記データシーケンスの記号に対し て定義されたと同じ３つの型の記号から成る問合せシーケンスの記号に対応する 記号のデータシーケンスを検索するための方法において、（ａ）フラグを第１状 態にセットする段階；（ｂ）上記データシーケンスの記号における第１データシ ーケンス記号を示す段階；（ｃ）上記問合せシーケンスの記号における第１問合 せシーケンス記号を示す段階；（ｄ）段階（ｂ）及び（ｃ）において示された上 記記号を比較する段階；（ｅ）上記フラグは、上記記号が対応しなかった場合に 上記データシーケンスの記号は、上記問合せシーケンスの記号に対応しなかった ことを示す第２状態にセットする段階であって、上記記号は、上記データシーケ ンス記号が上記問合せシーケンス記号に同等であったかあるいは上記記号の少な くとも１つが変数であった場合に対応すると定義される段階、及び（ｆ）次のデ ータシーケンス記号及び次の問合せシーケンス記号を示す段階であって、上記次 のデータシーケンス記号は、上記データシーケンスの記号における前に示された データシーケンス記号に続く記号であり且つ上記次の問合せシーケンス記号は、 上記問合せシーケンスの記号における前に示された問合せシーケンス記号に続く 記号であり、しかし、前に示された記号は、開区切り文字及び変数であった場合 はそうではなく、この場合は、段階（ｇ）を実行する段階、；（ｇ）上記開区切 り文字に対応する閉区切り文字を決定する段階であって、このように示されるべ き次の記号が、上記変数に続く記号及び上記開区切り文字に対応する閉区切り文 字に続く記号である段階、（ｈ）上記問合せシーケンスの記号における最後の記 号が比較されるまで段階（ｂ）から（ｈ）を反復する段階；及び（ｉ）上記フラ グが上記第１状態にある場合に上記データシーケンスを検索する段階を含むこと を特徴とする検索方法。
17. １７．どの閉区切り文字が上記データシーケンスの記号あるいは上記問合せシー ケンスの記号の１つにおける与えられた開区切り文字に対応するかを決定するた めの段階は、上記開区切り文字に対応する閉区切り文字を識別する上記開区切り 文字の一部として記憶されたラベルを読み出すための段階を含むことを特徴とす る請求の範囲第１６項に記載の方法。
18. １８．どの区切り文字が、上記データシーケンスの記号あるいは上記問合せシー ケンスの記号の１つにおける与えられた開区切り文字に対応するかを決定するた めの段階は、上記開区切り文字が上記変数に比較された時にカウンタを初期状態 にセットし、次に上記カウンタを増分する段階、上記開区切り文字を含むシーケ ンスにおける各連続記号を読み出す段階、開区切り文字が読み出される毎に上記 カウンタを増分し且つ閉区切り文字が読み出される毎に等量上記カウンタを減分 する段階、及び上記カウンタを上記対応の閉区切り文字としての上記初期状態に 戻させる閉区切り文字を識別する段階を含むことを特徴とする請求の範囲第１６ 項に記載の方法。
19. １９．どの閉区切り文字が、上記データシーケンスの記号又は上記問合せシーケ ンスの記号の１つにおける与えられた開区切り文字に対応するかを決定するため の段階が、上記開区切り文字を含むシーケンスにおける上記閉区切り文字の位置 を規定する上記開区切り文字の一部として記憶されているデータを読み出す段階 を含むことを特徴とする請求の範囲第１６項に記載の方法。