JPH0365571B2 - - Google Patents

Description

【発明の詳細な説明】 技術分野 本願発明は、検索対象のデータから優先順位に
複数個のデータを順位付けて検索するための該当
データのアドレス格納制御方式に関するものであ
る。

従来技術 従来ハードウエアを用いて情報検索を行う場
合、検索データと一致のとれた被検索データのア
ドレスを格納する方法として、アドレス格納専用
メモリを用意し、該当のとれたレコードアドレス
を格納すると共に処理を一時的に終了するか、も
しくは順次新規該当レコードアドレスを更新する
方法がある。但し従来の検索手法では単一処理内
に抽出可能なレコード数は１件であり、複数件数
をリアルタイムに抽出する事は困難であり、可能
ならしめるには大きなハードウエアを必要とし
た。

磁気デイスク等の外部記憶装置を備えた情報検
索装置では所望の情報を抽出する場合、外部記憶
装置内の多量な情報を一担中央処理装置内の主メ
モリに格納し、メモリ内で検索する方法がとられ
ていた。又磁気デイスクからの読み出し情報をリ
アルタイムに処理し、所望の情報を抽出するに
は、１回のアクセスに対し１件の情報しか得られ
ず、多量の件数を必要とするアプリケーシヨンに
おいては、その件数分だけ前記外部記憶装置への
アクセスを必要とし、多くの時間を要する欠点が
あつた。

目 的 本発明は上述した従来の欠点を改良すると共
に、単一処理時間内に複数件の情報の抽出を可能
とし、検索の結果の該当レコードアドレスの格納
方式を柔軟なかつ安価で高速処理可能とする構成
のアドレス格納制御方式を提供することを目的と
する。

実施例 以下に本発明の一実施例を図面を参照して説明
する。

第１図は本発明を実現した情報検索装置のブロ
ツクダイヤフラムである。

１は本情報検索装置の制御下にある外部記憶装
置、２は前述した外部記憶装置１のデータ及びク
ロツクを制御及び送受信用のインタフエイスＡ。
３は前述した外部記憶装置１のアドレス及び外部
記憶装置１からのリターン情報を送受信するイン
タフエイスＢ。４は前述の１，２，３及び本発明
情報検索装置全体の制御を司る制御部MCT。５
は後述する内部バスラインを切変え、前記制御部
MCT４の指示でデータの方向をも制御するスリ
ーステートゲート。６は検索情報の検索手法を指
示する情報を一時記憶するメモリJM。７は検索
情報の初期値を格納するメモリＱ１である。メモ
リＱ２，８、メモリＱ３，９はメモリJM６、メ
モリＱ１，７の内容に従つて、外部記憶装置１よ
り抽出された被検索データが一時格納、もしくは
一時格納された被検索データが第２、第３の抽出
データを検索する為の検索データ格納メモリとな
るバツフアメモリ兼用検索レジスタである。１０
は外部記憶装置１からインタフエイスＡ２を介し
て読み出されるデータと、メモリＱ１，７から読
み出されるデータとを比較する比較器CM１。１
１及び１２は上述のCM１，１０同様読み第しデ
ータとメモリＱ２，８又はメモリＱ３，９より読
み出されるデータとを比較する比較器CM２又は
CM３。１３はメモリJM６、メモリＱ１，７、
メモリＱ２，８、メモリＱ３，９のアドレス及び
被検索データの長さを制御するレングスカウンタ
Ｌ，Ｃ。１４はCM１，１０，CM２，１１，
CM３，１２の各比較器出力の論理制御を司り
LC１３の動作を制御し、後述する該当レコード
アドレス格納メモリADM１６及び該当レコード
ステータス格納メモリSTM７に所定の制御情報
を送出する検索論理回路制御部IRCT。１５は
MCT４の出力情報に従い、被検索データの区切
りをカウントし、各データの一連のまとまり（レ
コード）毎に該アドレスとして保持し、IRCT１
４の指示によりAPM１６へ送出するレコードア
ドレスカウンタRADC。１６は前述した如く、
RADC１６の内容を、IRCT１４の指示により一
時的にレコードアドレスを格納するメモリ
ADM。１７は被検索データの状態（該当の有無
や、以前に同一データが存在した事を表わす複数
該当の有無情報等）を格納するメモリSTM。１
８は本発明の情報検索装置と上位装置等を接続す
る為のバスインタフエイスBIF。１９は前述した
外部記憶装置１からの生情報が行きかう高速バス
ラインMBCS。２０はMLT４の制御下で各メモ
リの状態及びカウンタ値やBI１８への情報が行
きかうSBUS。２１は本情報検索装置と上位装置
間の通信手段LBUSで、BIF１８により任意な通
信手段を構築することが出来る。

次に本発明の好適な実施例である情報検索装置
の動作原理を図面を参照して詳述する。

第２図は本発明の動作フローチヤートである。
第１図のLBUS２１を介し所定フオーマツトで本
情報処理装置へインストラクシヨン及び検索すべ
き被検索データの格納されている外部記憶装置１
のアドレス又は各フアイル単位のフアイル名等が
上位装置より送出され、出された情報は制御部
（MCT）４にて解読され、各検索レジスタ及びイ
ンタフエイスＢ３を介して外部記憶装置１への制
御等が実行され検索処理が開始となる。検索レジ
スタJM，Ｑ１に所定の初期値が設定されると
（ステツプ１００，１０１）、外部記憶装置１はデ
ータの読み出しサイクルに入る（ステツプ１０
２）。そして外部記憶装置１が検索をすべきアド
レスに到達するまで待ち時間となり、検索指示ア
ドレスに到達すると（ステツプ１０３−Ｙ）、
MCH４よりLC１３及びRADC１５に検索開始指
令が送出され（ステツプ１０４）、外部記憶装置
１の読み出し速度に同期して、JM６の内容に従
い、Ｑ１，７とインタフエイスＡ２を介し、
MBUS１９上に出力されている外部記憶装置１
の読み出しデータとの比較が実行される（ステツ
プ１０５）。この比較は１クロツクサイクルの前
後半を利用して、被検索データに対し上限値（又
は下限値）、下限値（又は上限値）の初期値であ
る２種情報を比較し、被検索データが初期設定し
た値の中に含まれるか否かを判別する。次に“Ｑ
１にて該当あり”と判断されると、該データが第
一優先順位のデータか否か選択される（ステツプ
１０６）、第一優先順位でない場合は次に第二優
先順位のデータか否か選択される（ステツプ１０
７）。

第一優先順位として選択される条件は (1) 検索指示された範囲内で最初に該当があつた
場合。

(2) Ｑ２，Ｑ３に格納されている該当データよ
り、より極限値に近い場合。

第二優先順位として選択される条件は、 (1) 検索指示された範囲内で、２回目に該当があ
つた場合でかつ１回目の該当データより極限値
から遠いか、もしくは１回目の該当データと等
しい場合。

(2) Ｑ２，Ｑ３に格納されている第一優先、第二
優先順位のデータに対し、既第一優先順位デー
タより極限値から遠く既第二優先順位データよ
り極限値に近い場合（この場合該データは既第
二優先順位データにかわり、第二優先順位デー
タとなる）。

もし第一優先順位のデータと判断されると（ス
テツプ１０６−Ｙ）、Ｑ２，８及びＱ３，９に格
納されているデータが同一内容であるか否かのフ
ラツグ；FSDBを判断し（ステツプ１０８）、も
しFSDB≠１ならば（同一内容でなければ）検索
開始から最初の該当データか、もしくはＱ２，８
及びＱ３，９に格納されているデータより優先度
の高いデータが被検索データとして入力されたこ
とになる。このため、過去に第一優先順位データ
と同一データの被検索データがあつたことを示す
FDBLフラツグがセツトされているかを判断し
（ステツプ１１３）、もしセツトされていればそれ
をリセツトする（ステツプ１１４）。その後ワー
ク領域に格納されている被検索データを第一優先
順位のデータとするため被検索データの記録され
ていたレコードアドレスカウンタの値をメモリ
ADMにセツトする（ステツプ１１１）と共に、
Ｑ２，８，Ｑ３，９内の被検索データに格納され
ているワーク領域を検索データ領域とし、Ｑ２，
８，Ｑ３，９内の極限値より遠いデータを削除
し、該データ格納場所が新規ワーク領域となる
（ステツプ１１２）。

又FSDB＝１ならＱ２，８，Ｑ３，９に格納さ
れている既該当データは等しく被検索データすな
わち該第一優先データが既該当データより極限値
に近い為、既該当データのうち一方を削除しなけ
ればならないが、過去に既該当データと等しいデ
ータが存在したことを示すためFDBLフラツグを
セツトし（ステツプ１０９）、その後既該当デー
タが同一であることを示すFSDBフラツグをリセ
ツトする（ステツプ１１０）。

そして前述したFSDB＝１の時と同様レコード
アドレスカウンタの値をメモリADMにセツト時
間的に後ろの既該当データ（検索指示範囲内アド
レスの後方に近い既該当データをさす。）が削除
され（ステツプ１１１）、前述したＱ２もしくは
Ｑ３の削除されたデータ領域が次レコードの為の
ワーク領域として確保される（ステツプ１１２）。

次に第一優先順位でないと判断されると（ステ
ツプ１０６−Ｎ）、前述した第二優先順位の条件
を満足しているか否かを判別し（ステツプ１０
７）、第二優先順位のデータと判断されると、該
第二優先順位データが既第一優先順位データと等
しいか判断し（ステツプ１１５）、等しければＱ
２，８，Ｑ３，９レジスタに格納されているデー
タが等しい事を意味し、次に該当データが第一優
先順位データとして上位に割込んできたときに、
前記FDBLをセツトする為のフラツグ、FSDB
（Ｑ２，Ｑ３の既該当データが等しい事を表わ
す。）をセツトし（ステツプ１１６）、レコードア
ドレスカウンタの値をメモリADMにセツトし
（ステツプ１１４）、今まで第二優先順位のデータ
が格納されていた領域を新たにワーク領域とし、
被検索データの格納されていた領域を新たな第二
優先順位のデータの検索データとする（ステツプ
１１２）。

又第二優先順位データが第一優先順位データと
異なつた場合 例えば小順ソート処理で、 第一優先順位データ＜第二優先順位データの時
は、通常の該当ありデータとして処理され特別な
フラツグのセツトやリセツトを伴わない。すなわ
ちレコードアドレスをメモリADMにセツトし
（ステツプ１１１）、削されたデータ領域が新たな
ワーク領域として確保される（ステツプ１１２）。

又ステツプ１０７で第二優先順位でないと判断
された場合は、該データが第二優先順位データと
等しいか否かを判断し（ステツプ１１７）、もし
等しいならばＱ２，８Ｑ３，９に格納されている
該当データと同じデータが存在する事を示す
FDBLフラツグをセツトする（ステツプ１１８）。
その後『該当なし』として処理される（ステツプ
１１９）。

次に第３図を用いて実際のデータの格納状態及
び比較状態を時間の流れによつて説明する。第３
図は任意な数値情報を50〜125まで小順ソートを
実行した時のデータの流れとＱ１，７，Ｑ２，
８，Ｑ３，９のデータの格納状態及びレコードア
ドレスの格納状態を表わす。図において時間はＴ
０〜Ｔ１，Ｔ２，……Tnと流れ、被検索データ
はデイスク装置等の外部記憶装置からのリード出
力、各データの区別としてレコードＮ０，Ｒ０，
Ｒ１，……Rnがある。Ｑ１，７にはソートする
場合の極限値、下限と上限が格納され第１図比較
器７により被検索データが所望の値の中に含まれ
ているかをチエツクする。すなわちフローチヤー
トのステツプ１０５であり、Ｔ０では50＜123＜
125ゆえＲ０＝123は『該当あり』と判別され、Ｑ
２，８のワーク領域Ｗに格納される。Ｔ１ではＱ
１で50＜99＜125であり同様にＲ１＝99は『該当
あり』と判別されＱ２，８で99＜123が成立する
ゆえ、Ｒ１＝99が第一優先順位データとなりＲ０
＝123は第二優先順位データとなる。又各該当レ
コードアドレスは第３図のレコードアドレスの格
納状態に示されており上が第一優先、下が第二優
先順位を表わす。Ｔ２ではＱ１で50＜105＜125ゆ
え『該当あり』であるが、Ｑ２及びＱ３では、99
＜105＜123が成立するゆえ、今まで第二優先順位
であつたＲ０＝123が削除される。レコードアド
レスも１とＲ２を格納する。Ｔ３ではＱ１の条件
はＴ２同様であるがＱ２，Ｑ３では99＝99＜105
となるＲ２＝105が削除され、第一、第二優先順
位データが等しい為FSDBがセツトされる。Ｔ４
ではＱ１の条件では満足されるが、Ｑ２，Ｑ３で
の条件99＝99＜102となりＲ４のデータは優先順
位が低いため『該当なし』と判別される。Ｔ５で
はＱ１は『該当あり』Ｑ２，Ｑ３では91＜99＝99
が成立する為第一優先順位データとなりＲ３＝99
が削除される。Ｒ３＝99とＲ１＝99は等しい為前
述の如くFSDB＝１で第一優先順位データが存在
したゆえ、FDBLがセツトされ、レジスタに格納
されたデータ以外に等しいデータの存在の有無を
知る事ができる。Ｔ６ではＱ１の条件は満足する
がＱ２，Ｑ３で91＜Ｒ６≦99はＲ６＝100ゆえ成
立しない為、『該当なし』となる。Ｔ７ではＱ１
の条件は満足、Ｑ２，Ｑ３ではＲ７（85）＜91＜
99が成立するゆえ、第一優先順位データとなりＲ
７＝85が第一で、Ｒ５＝91が第二優先順位とな
り、Ｒ１＝99が削除される。よつてＱ２，Ｑ３に
は（99）がなくなる為FDBLはリセツトする。

レコードアドレスは毎レコードメモリADMへ
格納されるが、『該当あり』と判断されるとレコ
ードアドレスの先頭該当有無情報を付加して
ADMへ格納される。ADMはｎ段のスタツク構
造で、任意時間（このレコードの読み取りが終了
するまでの任意な時間）にACTがADMのデータ
がチエツクするより前述した如く１回のソート処
理で複数件のレコード（被検索データ）を抽出
し、そのレコードのアドレスも知る事ができる。
物理的にＱ２，Ｑ３の大きさを外部記憶装置の大
さに近づける事により、より多くのデータが１回
で抽出可能となる。すなわちデイスク装置等にラ
ンダムに記憶（数値的に大小関係を表わした場合
の順不同を表わす。）された情報をデイスクの１
回サーチにより小順あるいは大順にならびかえる
事が可能となる。このレコードアドレスの構成を
第４図に示す。また第５図に各レジスタと被検索
データとの関係を表わす。Ｉ１，Ｉ２，……１５
は各レコード（RN，RN＋１……）内のアイテ
ムを表わす。各アイテムは各々が検索時のキー対
称となりうると共にＩ１，Ｉ２，Ｉ３の如く各ア
イテムの論理積検索及びＩ１＋Ｉ２＋Ｉ３の始論
理和検索が可能な一情報の単位である。この様な
検索はＱ２，Ｑ３の大きさにより時分割にて同一
被検索データに対して複個の比較検索データを対
象として比較することによつて極めて容易な構成
で高速な検索処理が実現する。

効 果 以上述べた様に本発明のアドレス格納制御方式
を用いることにより単一処理時間内に複数件の情
報の検索を実現すると共に高速処理を可能とする
情報検索が実現し、検索対象のデータを順次１つ
ずつ処理し、処理が全対象データについて一巡し
たときに、優先順に複数個のデータを順位付けて
検索することが可能となる。

【図面の簡単な説明】

第１図は本実施例のブロツクダイヤグラム、第
２図は動作フローチヤート、第３図は小順ソート
実行時のデータの流れを示す図、第４図はレコー
ドアドレスの構成を示す図、第５図は被検索デー
タと各レジスタとの対応を示す図である。 図において、１……外部記憶装置、２……イン
タフエイスＡ、３……インタフエイスＢ、４……
制御部、６……メモリJM、７……メモリＱ１、
８……メモリＱ２、９……Ｑ３、１０……比較器
CM１、１１……比較器CM２、１２……比較器
CM３、１３……レングスカウンタ、１４……検
索論理回路制御部、１５……レコードアドレスカ
ウンタ、１６……メモリADM、１７……メモリ
STM、１８……バスインタフエイスである。

Claims (1)

1. 【特許請求の範囲】 １ 外部記憶装置を用いた情報検索装置におい
   て、 前記外部記憶装置より読み出された１個の被検
   索データ及び所定の複数個の検索データを格納す
   るデータ格納手段と、 被検索データを、前記複数個の検索データと比
   較する比較手段と、 該比較手段に比較条件を与える比較条件格納手
   段と、 前記比較手段による比較により該当するデータ
   のアドレスを優先順位に従つて複数個格納するア
   ドレス格納手段とを備え、 前記被検索データが前記比較手段による比較に
   より該当する場合は、当該データのアドレスを前
   記アドレス格納手段に格納し、前記データ格納手
   段に格納された当該データを以後の検索における
   検索とし、これにより検索が前記所定の個数をこ
   える場合は、前記優先順位において最下位の検索
   データを検索データより除外することを特徴とす
   るアドレス格納制御方式。