JPH0516607B2 - - Google Patents

Description

【発明の詳細な説明】 技術分野 本発明は情報検索装置の検索データ及び検索デ
ータの該当データを格納するメモリ制御方式に関
する。

従来技術 従来多量情報が格納されている磁気デイスク等
を用いた情報検索装置において、オペレータが要
求する情報を得る場合該磁気デイスク装置の制御
装置に所望する情報の特徴（あるいは「キー」と
呼ばれる見出し）を与え、該磁気デイスク装置へ
アクセスし、与えた情報と一致した情報を、ある
いは最も近い情報等を抽出し、要求のあつたオペ
レータに知らせている。抽出されたデータはあら
かじめ決められたバツフアメモリに格納され、上
位装置からの要求により抽出される。すなわちバ
ツフアメモリと、検索データ格納メモリとが各々
別個に存在している為、極小値、極大値検索（ソ
ーテイング）を磁気デイスク等を用いた装置でリ
アルタイムに処理する時に所望する情報が格納さ
れているメモリから順次データを読み出しながら
ソーテイングを実施する場合には、ある時間帯
（仮りにtxとする）に被検索データである情報が
tx＋１の時間には検索データとして利用される事
があり、連続時間で被検索データと検索データと
が切替わらなければならない。一般に連続的に処
理が不可能な装置では、該磁気デイスク上のセク
タフオーマツトをスプリツトセクタ方式（読出し
順番が基点から１セクタ飛びあるいは複数セクタ
飛びで読出し、ある領域全てを読出すのに、１個
飛びなら２倍、ｎ個飛びならｎ倍の時間を要す
る）等を用い、読出し以外の時間で処理し、デー
タの移動を行うといつた欠点を有しており、高速
処理が困難であつた。

目 的 本発明は前述した従来の欠点を除去することを
目的とし、連続セクタ方式で情報が格納されてい
る磁気デイスク等を用いた情報処理装置において
空時間が生じる事なく磁気デイスク等の実時間で
所望するデータが抽出でき、しかも磁気デイスク
装置へのデータの登録も、読出しを考慮する事な
く自由に、任意なアドレスにでき、情報検索装置
への登録及び出力も高速に処理できるメモリ制御
方式を提供する。

実施例 以下に本発明の一実施例を図面を参照して説明
する。第１図は本発明を実現した情報検索装置の
ブロツクダイヤグラムである。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

効 果 以上述べた様に本発明によれば、検索対象のデ
ータを順次１つずつ読み出して、指定された位置
に格納するとともに、この読み出されたデータ
と、それまでに格納された順位付けられた複数の
データのそれぞれとを比較し、この比較の結果、
読み出されたデータより順位の低いデータが１つ
以上あつた時、そのうちで順位つけられた順位の
最も低いデータの格納位置を、次に読み出される
検索対象のデータの格納位置に指定し、順位付け
を変更し、また、この時、読み出されたデータの
格納・比較の処理が、読み出しに同期して行われ
ることにより、処理が検索対象の全データについ
て一巡した時に、順位の高い順に複数個（ｎ個と
する）のデータを順位つけて検索することが可能
となる。

更に、これを利用して全データのソーテイング
を行なうことにより、全データについて一巡する
毎に１つのデータしか検索できない従来の方法に
比べて、処理時間がｎ分の１となるメモリ制御方
式を提供できる。

また、読み出されたデータが、それまでに格納
されたデータより高い順位のデータであるか否か
によらず、同じように格納処理が行われるため、
高い順位のデータである場合にも、その後格納位
置を移動することなく、以後の比較処理に利用で
きる高速な処理が実現したメモリ制御方式を提供
できる。

そして更にまた、この比較・格納の処理を読み
出しに同期して行う様にしたので、高速な処理が
実現できるメモリ制御方式が提供できる。

【図面の簡単な説明】

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

Claims (1)

1. 【特許請求の範囲】 １ 検索対象データを記憶する第１のメモリより
   順次１つずつデータを読み出し、 読み出されたデータを、該データの読み出しに
   同期して、順位付けがなされた所定の複数個のデ
   ータを記憶するために当該所定個分の格納位置を
   具えた第２のメモリにおける指定格納位置に記憶
   させるとともに、 前記読み出されたデータと、前記第２のメモリ
   の前記指定格納位置以外の格納位置に記憶されて
   いるデータのそれぞれとの順位を比較し、各比較
   の結果、前記第２のメモリの前記指定格納位置以
   外の格納位置に記憶されているデータの内に、前
   記読み出されたデータよりより順位の低いデータ
   があつた場合には、前記第１のメモリからの次の
   データの読み出しに先立つて、前記順位付けによ
   る順位の最も低いデータの格納位置を新たな指定
   格納位置とし、前記順位付けを変更することを特
   徴とするメモリ制御方式。