JPH0341557A - データ検索装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明はデータ検索装置に係り、特に高速大容量データ
処理システムにおいて記憶媒体上の任意のデータを高速
に検索するのに好適なデータ処理装置に関する。

〔従来の技術〕

従来技術としては、特開昭６３−６４１２３号公報に開
示されているように、記憶媒体上のデータを制御回路の
バッファメモリに取込んだ後に、検索処理する方式が知
られている。

〔発明が解決しようとする課題〕

上記した従来技術においては、検索データの有行なうた
め、処理時間が長くするという問題点がある。

また、検索データは小容量であるにもかかわらず、大容
量のバッファが必要になるという問題点がある。

さらに、バッファを介して必要なデータを検索するため
、処理が複雑になり、高速処理できないという問題点が
ある。

本発明は上記した従来技術の問題点に鑑みなされたもの
で、少ないメモリ容量で高速にデータ検索することが可
能なデータ検索装置を提供することを目的としている。

〔課題を解決するための手段〕

本発明のデータ検索装置は、検索データと被検索データ
とを比較して、被検索データから検索データを検出する
データ検索装置に適用されるものであり、特にあらかじ
め指定された検索データを格納する第１の手段と、入力
される被検索データと第１の手段から読み出された検索
データの一致をデータ単位で判定する第２の手段と、あ
らかじめ指定された検索データのデータ長を格納し、検
索データの全てについて一致が取れるまでの残りのデー
タ数をカウントする第３の手段と、第２の手段によって
検索データがデータ単位で全て検索され、第３の手段に
よって全てのデータが検索されたことが確認された場合
、一致を示す信号を出力する第４の手段と、上記第４の
手段から出力される一致を示す信号と入力される被検索
データの数とをカウントし、一致を示す信号が出力され
た場合、上記一致を示す信号のカウント数をアドレスと
し、上記カウントされた検索データ数をデータとして記
憶する第５の手段とから構成されることを特徴としてい
る。

〔作用〕

本発明によれば、入力されたデータと検索データが完全
に一致した場合、一致を示す信号が出力される。また、
この一致を示す信号が出力されたとき、その時までの総
入力データ数をきおきデータとし、かつ一致を示す信号
のカウント値をアドレスとして記憶される。したがって
、検索されたデータが、多数入力される入力データのう
ちの第何番目のデータであるかがデータとして記憶され
、かつそのデータが検索データの何番目のデータである
かがそのアドレスから知ることができる。上位装置はこ
の情報を任意の時点で参照可能になる。

〔実施例〕

以下、添付の図面に示す実施例により、更に詳細に本発
明について説明する。

第１図は本発明のデータ検索装置の一実施例を示す回路
図である１図示しない上位装置から出力される命令ＤＡ
ＴＡ　　ＳＥＴにより、検索データＭＤＡＴＡがクロッ
ク信号ＭＣＬＫのタイミングで順次検索データ格納レジ
スタ１０に格納される。

その際、カウンタ２はクロック信号ＭＣＬＫを計数し、
計数された検索データＭＤＡＴＡのデータ長は検索デー
タ長カウンタ８にセットされる。

検索データＭＤＡＴＡのうちの１番目のデータは、上位
装置から出力される命令１ｓｔＤＡＴＡＳＥＴにより、
クロック信号ＭＣＬＫのタイミングで第１データ格納レ
ジスタ１８に格納される。

図示しない上位装置から命令５ＡＲＣＨが出力されると
、読出しデータＲＤＡＴＡがリードクロック信号ＲＣＬ
Ｋのタイミングで入力され、検索データ格納レジスタ１
０から出力される検索データＭＤＡＴＡと読出しデータ
ＲＤＡＴＡとが反転リードクロック信号ＲＣＬＫのタイ
ミングで、比較器１１によって比較される。比較の結果
、°両者が一致し場合、フリップフロップ１２から信号
ＳＡＭＥが出力される。信号ＳＡＭＥは検索データＭＤ
ＡＴＡが複数のデータから成るとき、各データ単位で出
力される。

また、読出しデータＲＤＡＴＡは、第１データ格納レジ
スタ１８に格納された検索データＭＤＡＴＡ中の第１番
目のデータとも、反転リードクロック信号ＲＣＬＫのタ
イミングで、比較器１９によって比較される。比較の結
果、両者が一致し場合、には、フリッププロップ２０か
ら第１データ検出信号１　ｓｔ　Ｄ　ａｔａが出力され
る。

上記比較器１１による比較の結果一致し、かつ検索デー
タ長カウンタ８のカウント値ＣＮＴがｌである場合アン
ド回路１５のアンド条件が成立し、フリップフロップ回
路１６から検索データＭＤＡＴＡが検出されたことを示
す信号ＦＩＮＤが出力される。

検索データＭＤＡＴＡと読出しデータＲＤＡＴＡがデー
タ単位で一致せず信号ＳＡＭＥが出力された場合、又は
検索データＭＤＡＴＡが検出されて信号ＦＩＮＤが出力
された場合には、信号ＮＥＸＴが出力され、検索データ
長カウンタ８に検索データＭＤＡＴＡのデータ長をカウ
ンタ２から再度ロードする。これによって、検索データ
長カウンタ８が再び初期値にセットされる。これに伴っ
て、検索データＭＤＡＴＡが検索データ格納レジスタ１
０に先頭データから順に再度セットされる。

検索データＭＤＡＴＡと読出しデータＲＤＡＴＡがデー
タ単位で一致せず信号ＳＡＭＥが出力され、かつ不一致
になった読出しデータが第１番目のデータであり信号１
　ｓｔ　Ｄ　ａｔａが出力された場合には、検索処理を
続行する必要がある。そのため、アンド回路４により信
号１ｓｔ　Ｄａｔａが出力されるタイミングで、カウン
タ２から出力されている検索データ長を示す値から−ｌ
減算器３によって１減算した値を検索データ長カウンタ
８にセットする。これに伴って、検索データ格納レジス
タ１０には、検索データＭＤＡＴＡの２番目のデータか
ら順に再設定される。

検索データ長カウンタ８は、データが一致して信号ＳＡ
ＭＥが出力され、しかもこのとき信号ＦＩＮＤが出力さ
れず、（信号ＦＩＮＤが出力される）かつ、読出しデー
タＲＤＡＴＡが第１番目のデータでない（信号１ｓｔ　
Ｄａｔａが出力されない）ときに、カウントダウンされ
る。即ち、この条件が成立すると、アンド回路２１から
信号ＤＥＣが出力され、この信号ＤＥＣがアンド回路６
とオア回路７を介して検索データ長カウンタ８に入力さ
れ、カウントダウンされる。

カウンタ２７は命令５ＡＲＣＨが出力されている期間に
出力されるリードクロック信号ＲＣＬＫを計数するカウ
ンタである。このカウンタ２７の計数値のうち、信号Ｆ
ＩＮＤの出力されたタイミングにおける計数値がメモリ
２５に検出データの所在を示すデータＦＩＮＤ　ＤＡＴ
Ａ　ＡＤＲとして格納される。このときの格納アドレス
ＦＩＮＤＮｏは、信号ＦＩＮＤの数を計数するカウンタ
２４から出力される。そして、この格納アドレスＦＩＮ
ＤＮ。

は、カウンタ２４によって信号ＦＩＮＤが消失する毎に
更新される。

上位装置は、任意のタイミングで、あるいは検出データ
数（ＦＩＮＤＮｏ）の監視・報告、あるいはメモリ２５
の満杯の報告により、検出動作を止め、命令ＲＤＡＤＲ
を出力して、クロック信号ＭＣＬＫのタイミングで検出
データの所在を示すデータＦＩＮＤ　　ＤＡＴＡ　ＡＤ
Ｒをメモリ２５から読み出す。

次に、第２図から第８図に示すタイムチャートに従って
、第１図に示す実施例の動作を説明する。

第２図から第６図は、３つの連続するデータａ。

ｂ、ｃを検索する場合を示している。

第２図は検出すべきデータ“ａｂｃ”を格納する例を示
す、命令ＤＡＴＡ　ＳＥＴが出力され、クロック信号Ｍ
ＣＬＫのタイミングで検索データＭＤＡＴＡを検索デー
タ格納レジスタ１０へ格納する。その際のクロック信号
ＭＣＬＫをカウンタ２で計数し、検索すべきデータ長が
ＩＩ　３　ＩＩであることを検索データ長カウンタ８に
セットする。

検出すべき第１番目のデータａは命令ｌ５ＴＤＡＴＡ　
ＳＥＴによって（命令ＤＡＴＡ　　ＳＥＴの最初のデー
タセラｈ期間に出力される）、クロック信号ＭＣＬＫの
タイミングで検索データＭＤＡＴＡからデータ“ａ”が
抽出されセットされる。

本例においては、検索データ格納レジスタ１０はＦＩＦ
Ｏ（先に書込んだデータから先に読出す）形式であると
する。

第３図は、検出データの所在するアドレスをメモリ２５
に格納するタイミングを示す、命令５ＥＡＲＣＨが出力
されると、リードクロック信号ＲＣＬＫのタイミングで
読み込まれる入力データＲＤＤＡＴＡと連続する検索デ
ータＭＤＡＴＡ中の第１番目のデータとの比較が比較器
１１で行なわれる。

リードクロック信号ＲＣＬＫの立下りタイミングで比較
し、一致した場合、データ一致を示す信号ＳＡＭＥと第
１データ検出を示す信号１ｓｔ　Ｄａｔａが出力される
。次に、第２データ検出を行うため、次のり一ドクロッ
ク信号ＲＣＬＫの立上りタイミングで、検出データ長＝
“３”より“−ｌ”した値“２″が検索データ長カウン
タ８にセットされ、検出すべき次のデータは“ｂ”とな
る。

最終データまで連続して一致した場合（ＣＮＴ＝１であ
る時に、データ一致した場合）、検索データＭＤＡＴＡ
を検出できたことを意味するＦＩＮＤが出力される。

データは一致している（信号ＳＡＭＥがオン）が信号１
ｓｔ　Ｄａｔａがオンされず、かつ、信号ＦＩＮＤもオ
ンされない時には、信号ＤＥＣがオンされる。本例では
、′ａ″を検出したのに続き。

１１　ｂ　Ｉ＋を検出した時点が相当する。４つの連続
したデータ“ａ、ｂ、ｃ、ｄ”の場合では“ａ”ｂ”を
連続して検出したのに続き“Ｃ”も検出した時点も同様
となる。また、５つ以上の連続したデータの場合も、第
１番目のデータと最終データを除くデータの検出時点に
おいて同様となる。

信号ＤＥＣが出力されたとき、リードクロック信号ＲＣ
ＬＫの立上りで検索データ長カウンタ８のカウント値（
ＣＮＴ＝ｎ）は−１され、本例ではＣＮＴ＝１となり、
次に検出すべきデータとして検索データ格納レジスタ１
０から“ｃＩＩが出力される。

検索すべきデータと読出しデータＲＤＡＴＡが一致しな
い場合（信号ＳＡＭＥがオン）、および連続した検索デ
ータの全てを検出できた場合（信号ＦＩＮＤがオンの場
合）、以降も検索が続くなら（命令５ＡＲＣＨがオンの
まま保持）、一連の検索データＭＤＡＴＡを再度検索す
るため、信号ＮＥＸＴが出力され、検索データ長カウン
タ（ＣＮＴ＝ｎ）を初期値′″３″にセットし検出すべ
きデータとして検索データ格納レジスタ１０から第１番
目のデータ“ａｐｔを出力させる。

命令５ＡＲＣＨが出力された後、リードクロック信号Ｒ
ＣＬＫのタイミングで、検索対象データのアドレスＦＩ
ＮＤ　ＤＡＴＡ　ＡＤＲはカウンタ２７でカウントされ
る。

検索データが検出されたことを示す信号ＦＩＮＤが出力
され、リードクロック信号ＲＣＬＫがオン（信号ＲＣＬ
Ｋがオフ）のタイミングで、検索対象データのアドレス
ＦＩＮＤ　ＤＡＴＡ　ＡＤＲがメモリ２５の該当アドレ
スＦＩＮＤＮｏへ格納される。

格納メモリアドレスＦＩＮＤＮｏは信号ＦＩＮＤが出力
され、リードクロック信号ＲＣ：ＬＫがオフとなるタイ
ミングで更新される。

このメモリ２５内のデータ（ＦＩＮＤ　ＤＡＴＡＡＤＲ
）は、任意の時点で読出し命令ＲＤＡＤＨが出力された
とき、クロック信号ＭＣＬＫのオンのタイミングでアド
レス順に読出される。

次に、第４図から第７図を用いて読出しデータＲＤＡＴ
Ａの種々の組み合わせと回路動作について説明する。

第４図は最終データ“Ｃ”が不一致であった直後のデー
タ以降から“ａｂｃ”を検出する例である。′ａ″ｇ、
（ｌｂｌｔを連続して検出した後のり−ドクロック信号
ＲＣＬＫの立上りタイミングで最終データ“Ｃ”が検出
すべきデータとして検索データ格納レジスタ１０から出
力され検索データ長カウンタ８のカウントは“ｌ”とな
る。

しかし１次の入力が“ａ”でも１１　Ｃ３Ｉでもないの
で（注：Ｘは“ａ”　ｕｂ”　１４　ｃＩＩのいずれで
もない任意データ）信号ＮＥＸＴがオンとなり。

検索データ長カウンタ８は初期化され（ＣＮＴ＝３）１
次に検出すべきデータは第１番目の“ａＩ＋となるので
以降に続（”ａｂｃ”の検出が可能となる。

第５図は“ａ、　ｂ、　ｃＩＩを連続して検出する例で
ある。”ａ　、　ｂ、　ｃ、　ａ、　ｂ、　ｃ”と検出
する間借骨ＳＡＭＥはオンのままであるが、最終データ
”Ｑ”を検出する毎に出力される信号ＦＩＮＤをリード
クロック信号ＲＣＬＫの立上りで検出し、検索データ長
カウンタを初期化（ＣＮＴ＝３）Ｌ、次の検出データを
第１番目の“ａ”とするので、以降に続（１１ａ、　ｂ
、　ｃＩＩの検出が可能となる。

第６図は第１データ（（ａｌｌにより検出不一致となっ
た後、以後のデータ“ｂ、ｃＩ＋がその１１　ａ”に連
続することにより、ＩＩ　ａｂｃｌｌを検出する例であ
る。

第１データ１１　ａｌｌを検出した場合、検出すべきデ
ータが″′ａ″以外で不一致（信号ＳＡＭＥがオン）で
あっても、第エデータの検出を示す信号１ｓｔＤＡＴＡ
がオンとなり、その次のデータを第２データ“ｂ”とす
るので、以降“ｂ、ｃ”と続く場合も検出可能となる。

すなわち、検索データＭＤＡＴＡと読出しデータＲＤＡ
ＴＡの連続した一致状態がくずれ、不一致を示す信号Ｓ
ＡＭＥがオンになり、かつ、その不一致の原因が検索デ
ータＭＤＡＴＡの第１番目のデータである場合、継続し
て第２番目以降の一致・不一致を判定する必要がある。

この場合には、上記不一致となった第１番目のデータを
一致状態と等価とみなす論理により、複数の検索データ
ＭＤＡＴＡがオーバラップした場合も検索可能となる。

第７図は２つの連続するデータ“ａｂ”の場合を示す。

検索データ長カウンタ８のカウント値はＩＩ　２　ＩＩ
と１１１　Ｉｔとの遷移のみで、第１データ“ａ”の検
出による信号１ｓｔ　Ｄａｔａのオンにより、検索デー
タ長カウンタを−１し、最終データ１′ｂ　＃ｌの検出
による信号ＦＩＮＤのオンにより検索データ長カウンタ
の初期化が行なわれる。

第８図は、データ長が“ｌ”であるデータ“ａ”を検出
する例である。検出すべきデータＭＤＡＴＡは“ａ”固
定であり、読出しデータＲＤＡＴＡがａ”となるとき、
信号ＳＡＭＥと第１データの検出を示す信号１ｓｔＤＡ
ＴＡと信号ＦＩＮＤとが、同時にオンとなる。

１１　ａｌｌが連続する場合、信号ＦＩＮＤはオンにな
ったままであるが、検出データのアドレスＦＩＮＤ　Ｄ
ＡＴＡ　ＡＤＲの書込み、およびメモリ２５の該当アド
レスＦＩＮＤＮｏへの格納は、夫々反転リードクロック
信号ＲＣＬＫおよびリードクロック信号ＲＣＬＫと信号
ＦＩＮＤとのアンド信号で作るので、検出データの格納
は可能となる。

検出すべきデータが４つ以上となった場合には、第１デ
ータと最終データを除いた中間データの処理を３つの連
続するデータ１１　ａｂＣｌｌの内のｂ″の処理と同様
に考えればよい。

〔発明の効果〕

本発明では、以上の様に読込みデータと並行して検索デ
ータと比較し、検索データの記憶媒体上の所在をメモリ
に格納しておき、上位装置は任意の時点で検出データを
確認できるので、上位装置の負担を大幅に軽減でき、シ
ステムのトータルスループットを向上できる。

検出データの記憶媒体上の所在のみをメモリに格納する
ため、検索対象データの全てをメモリに格納後メモリ内
で検索する方式に比して、メモリ容量は格段に削減でき
る。

【図面の簡単な説明】

第１図はこの発明のデータ検索装置の一実施例を示す回
路図、第２図から第８図は第１図に示す実施例の動作を
示すタイムチャートである。 ２．２４．２７・・・カウンタ、３・・・−１減算器、
８・・・検索データ長カウンタ、１０・・・検索データ
格納レジスタ、１１．１５．１９・・・比較器、１２．
１３．１４・・・フリップフロップ、１８・・・第１デ
ータ格納レジスタ、２５・・・メモリ。

Claims (1)

1. 【特許請求の範囲】 １、検索データと被検索データとを比較して、被検索デ
   ータから検索データを検出するデータ検索装置において
   、 あらかじめ指定された検索データを格納する第１の手段
   と、 入力される被検索データと第１の手段から読み出された
   被検索データの一致をデータ単位で判定する第２の手段
   と、 あらかじめ指定された検索データのデータ長を格納し、
   検索データの全てについて一致が取れるまでの残りのデ
   ータ数をカウントする第３の手段と、 第２の手段によって検索データがデータ単位で全て検索
   され、第３の手段によって全てのデータが検索されたこ
   とが確認された場合、一致を示す信号を出力する第４の
   手段と、 上記第４の手段から出力される一致を示す信号と入力さ
   れる被検索データの数とをカウントし、一致を示す信号
   が出力された場合、上記一致を示す信号のカウント数を
   アドレスとし、上記カウントされた検索データ数をデー
   タとして記憶する第５の手段とから構成されることを特
   徴とするデータ検索装置。