JPS6132695B2

JPS6132695B2 -

Info

Publication number: JPS6132695B2
Application number: JP2365477A
Authority: JP
Inventors: Tamotsu Nakazawa; Kenzo Ina; Takashi Minagawa
Original assignee: Canon Inc
Current assignee: Canon Inc
Priority date: 1977-03-04
Filing date: 1977-03-04
Publication date: 1986-07-29
Also published as: JPS53108743A

Description

【発明の詳細な説明】本発明は最大値（または最小値）を検索する検
索装置に関する。

フアイル処理を実現する上で、ソーテング処理
（あるキーワード（Key Word）によつて、フア
イル中のレコードを昇順または降順に並びかえる
操作がしばしば必要となる。

従来ソーテイング・テクニツクとしては、主記
憶装置上でのみ実行するインターナル・ソーテン
グ（挿入法、置換法、トーナメント法……）と、
磁気テープ、または、磁気デイスク等の記憶装置
を用いるエクスターナル・ソーテング（基数分類
法、各種マージ法……）とが有るが、前者は、主
記憶装置上に、対象とするデータのすべてを格納
する必要があるために、多量のデータの実行に
は、不適当であり、後者においても、多数の磁気
テープ記憶装置が必要であつたり、デイスク上に
ソーテングのための、ワーク・エリヤを多く必要
とする。

しかるに、本方式は、フアイル記録媒体として
磁気デイスク等の高速大容量な装置を用いた場
合、特にその威力を発輝する方式であり、デイス
ク等の読出し回路に直結された、または同期して
作動する検索ユニツトを付加することにより、読
出データ中の最大または最小値を検索し、ソート
処理をするものである。

本願は被検索データを格納する格納手段、上記格納手段から被検索データを読み出す手
段、上記読み出し手段によつて読み出されるデータ
が検索領域条件を満たすかどうかを判定する判定
手段、上記判定手段による判定結果に基づいて、上記
検索領域条件を可変としたことを特徴とする検索
装置であり、Cpu（Central Rrocessing Unit）
側のプログラム処理も含めてその処理の概要を第
１図に示す。同図に基づいて説明するならば、ま
ずCpuよりデイスク等の読出し制御回路へ検索対
象フアイルのエリア（スタート／エンドアドレ
ス）を指示し、さらに当検索ユニツトに対し検索
するキーワード（以下キーと称する）の上、下の
限界値及び最大または最小値検索のいずれかの指
定を行ない起動する。

一方、検索ユニツト側の機能として、以下に説
明する動作により、指定された限界値内での最大
または最小のキー値を有するレコードを検索し
て、そのレコードの格納アドレス、つまり該当ア
ドレスを保持して終了するものとすれば、Cpu
は、当アドレスにより、該当レコードを取出し、
所定の処理を行なう。さらに、次の順位のレコー
ドが必要ならば、前回のレコードのキーを、イン
クリメント、またはデイクリメントして、前回同
様に、検索ユニツトへ限界値としてセツトしなお
し、実行させればCpu側から見て、取出しレコー
ドのキー値は順次昇順または降順となる。また、
検索ユニツト側では常に、Cpuから指定される限
界値内で最小または、最大のキー値を有するレコ
ードの検出を行なうだけで良い。

この様にして、従来のソーテングと等価な処理
が可能となる。なお、このままの順番読出し方式
では、同一キー値を有するレコードが複数存在し
た場合には、これらをすべて取出すことが出来な
い。

そこで、本装置では、前記した最大または最小
値検索の基本的な動作以外に、次の機能が必要に
なる。

つまり、当検索ユニツトは必らず指示されてい
るエンド・アドレスまで、検索処理を実行せねば
ならない故に、指定された限界値内で、同一値を
有する複数の最大または最小値のキーのレコード
が在存すると、前記検索終了後の保持アドレス
は、よりエンド・アドレスに近い最後のレコード
のアドレスが該当アドレスとして格納されてい
る。

従つて、同一値の最大または最小値を検索した
ならば、セツトするステータス・フラツグを設け
（以後「複数存在」フラツグと呼ぶ）検索終了
後、同フラツグがセツトしていたならば、上、下
の限界値等は前回同様サーチ・エリヤのエンド・
アドレスのみを、前記該当アドレスより−１した
値に変えて検索処理を再実行する。

つまり、前回の該当アドレスのレコードは読出
し、必要な処理行なわれてしまつたものとすれ
ば、この該当アドレス以後のエリヤには、当面必
要とするレコードは存在しないことになるから、
検索対象エリヤはその直前までで良く、再び同フ
ラツグがセツト状態で終了したならば、同様に、
エンド・アドレスを狭ばめて、繰返せば結局、同
一キー値のレコードは格納アドレスの大きい順
に、すべて取出すことができる。

また、この様にして同一値の最後のレコードを
検索すると、この「複数存在」のフラツグは、セ
ツトしていない。従つて、次のキー順位のレコー
ドを取出すためには、サーチ・エリヤのエンドア
ドレスを初期値に戻し、正常ルーチンへ復帰せね
ばならない。このための情報として第１図の如
く、同一値を検出して、エンド・アドレスによ
り、サーチ・エリヤを狭めるルーチンの先頭でセ
ツトしておいたフラツグＦ４を使用する。

さらに、検索の結果、与えられた限界値の条件
を満すキーのレコードが存在しない場合、これを
示すステータス・フラツグ「該当なし」を設けて
おき、全体としての処理を終了することができ
る。

本方式によるソート処理のメリツトとして、次
の事柄が考えられる。

◎ソートのためのワーク・エリヤが不要故、媒体
の利用効率が非常に高い。

◎フアイル編成として、サーチ・フアイルが使用
でき、格納するレコード位置の制約が皆無のた
めに、アツプ・デートの追加、抹消、要求が高
くても、実時間内にこれらに対応できる。

つまり、いつでも望む時に順番読出しが可能
である。

◎フアイル処理のためのプログラムが非常に簡単
になる。

以下、本願発明の検索装置について、詳細な説
明を行なう。

第２図において、Cpuよりの限界値やデイスク
等のサーチ・アドレス等の格納のためのルート
や、各種カウンタ、フリツプ・フロツプ等のイニ
シヤル・セツト線等は省略したが、初期値につい
て考えると、15のカウンタはCpuより与えられる
サーチ・エリヤのスタート・アドレス値、他のカ
ウンタとフリツプ・フロツプはすべて“ゼロ”、
また、必要なときにタイミング１，２などは得ら
れるし、Cpuより与えられたサーチ・エリヤのエ
ンド・アドレスを監視しており、処理を終了する
機能等は当然有るものとする。

さらに第３図において、Ａ，Ｂ，ｉ，Ｆ１，Ｆ
２……等の記号は第２図の名称と同一内容を示
す。

第２図において、１は被検索データ（フアイ
ル）の格納されているメモリ、この読出し出力を
ｉと呼ぶ。２は最大値検索の場合には、Cpuより
上限値を、最小値検索の場合には下限値が格納さ
れるメモリで、この出力をＡと呼ぶ。３は、上記
メモリ１とメモリ２の出力を比較する比較回路、
比較条件はメモリ２１から与えられるものとし
て、最大値検索の場合には、Ａ≧ｉを検出し、最
小値検索の場合には、Ａ≦ｉを検出する。その出
力は、アンドゲート１１，１３へ与えられる。４
は、メモリ２と反対に最大値検索の場合には下限
値が、最小値検出の場合には上限値がCpuより格
納されるメモリであり、入力端にはｉが、リー
ド／ライトの制御端子には、オアゲート１９の出
力が与えられており、当端子＝Ｈならば読出し、
＝Ｌならば書込の機能を有する。また、出力端子
はアンドゲート６へ導かれている。５は、メモリ
４と同機能を有するメモリで、リード／ライト制
御端子にはオアゲート１８の出力が与えられてお
り、出力端子がアンドゲート７へ導かれているこ
と以外はメモリ４と同様な結線である。６及び７
はアンドゲートで、メモリ４，５出力をフリツ
プ・フロツプ１７の状態によりオン／オフする。
８はアンドゲート６及び７の出力のオアゲート、
オアゲート８の出力は、比較回路９に導かれ、こ
のデータを以下Ｂと呼ぶこととする。

比較回路９は、前記Ｂとｉの比較を行ない、比
較条件はメモリ２１から与えられるが、最大値検
索の場合には、ｉ≧Ｂを検出し最小値検索の場合
には、ｉ≦Ｂを検出する。また、その出力は比較
回路３と異なり、等号出力（＝）と、大小出力
（〓）との２系統で出力される。１１はオアゲー
ト１０の出力と、比較回路３の出力の論理積を取
るためのアンド・ゲート、当ゲートの出力により
メモリ１からのデータｉがCpuより指定された限
界値AorBに対して、Ａ≦ｉ≦Ｂまたは、Ａ≧ｉ
≧Ｂの条件が成立したことを知る。

１２はフリツプ・フロツプで最大または最小値
検索の対象キーの比較の結果ｉ＝Ｂならば、比較
回路９の等号（＝）出力端子からパルスが出力さ
れアンドゲート２３を経由してセツトする。ま
た、そのクリヤ端子にはアンドゲート１３よりの
出力が与えられており、これによつてクリヤされ
る。

なお、当フリツプ・フロツプの出力Ｆ１は前述
の「複数存在」のステータス・フラツグとなる。
１３はアンドゲートであり、比較回路３の出力と
比較回路９の大小出力（〓）の出力との論理積を
取り、Ａ≦ｉ＜Ｂまたは、Ａ≧ｉ＞Ｂの条件が成
立したことを示す。

１４はフリツプ・フロツプで、アンドゲート１
１の出力によりセツトされる。つまり、当検索ユ
ニツトの処理が始まつて、Ａ≦ｉ≦Ｂまたは、Ａ
≧ｉ≧Ｂなる条件成立が１度でも成立したなら
ば、当フリツプ・フロツプ１４はセツトしている
ことになり、前述した「該当なし」のステータ
ス・フラツグはオフ（₃＝０）となる。１５は
アドレス・カウンタでメモリ１のフアイルから読
出されるレコードのアドレスを、タイミング２な
るパルスでカウントする。１６はアンドゲート１
１よりの条件成立パルスがロード端子に与えられ
たラツチ回路、ロード・パルス毎にアドレスカウ
ンタ１５の内容を取込む、つまり処理中最後に取
込んだアドレス値を保持していることからラツチ
回路１６の出力をCpuに導びけば、最大または最
小のキー値を有するレコードのアドレスを与える
ことができる。１７はアンドゲート１１の条件成
立パルスが出力される毎にセツト、リセツトを操
返すフリツプ・フロツプ。その出力はＦ２と呼
ぶ。１８はオア・ゲートで、一方はフリツプ・フ
ロツプ１７のＱ側、他方は検出回路２２よりの出
力が与えられている。１９も同様にオア・ゲート
であり、フリツプ・フロツプ１７の側と検出回
路２２よりの出力が与えられている。

オア・ゲート１８，１９の出力はそれぞれメモ
リ４，５のリード／ライト端子へ導かれ機能的に
は負論理の論理積として作用する。

２０はメモリ１より読出されるデータに同期し
てそのウエイトをカウントするカウンタで、その
出力はメモリ２，４，５、そして２１のアドレス
端子に導かれている。このことより各メモリ２，
４，５及び２１はメモリ１よりの読出しレコード
に同期してアクセスできることになる。

また、カウンタ２０は各レコード毎にイニシヤ
ル・セツトされるものとする。

メモリ２１は、当検索ユニツトの処理開始以前
にメモリ１より読出されるレコードの、アイテム
（又はフイールド）構成や各アイテムに対する検
索条件等がコードで格納されるメモリで、その出
力は比較回路３，９及び検出回路２２に導かれて
いる。

検出回路２２は、メモリ２１の出力を受けて最
大または最小値を検索するアイテムの通過時間を
検出し、その時間中負信号をオアゲート１８，１
９に出力する検出回路。２３はアンド・ゲート
で、フリツプ・フロツプ１２のステータス・フラ
ツグの「複数存在」のセツト条件をフリツプ・フ
ロツプ１４のセツト後のみに限定するためのゲー
トである。つまり１回の処理中で、２回目の条件
成立時から比較回路９及びフリツプ・フロツプ１
２によりｉ＝Ｂを検出する。

２４は、ステータス・フラツグ「複数自在」の
フリツプ・フロツプ１２がセツトした場合、ラツ
チ回路１６に格納されている。２４は最後に存在
した同一値を有するレコードのアドレスを−１し
て制御回路２５内のエンド・アドレスを作成する
ためのデエクリメンタ。２５はデイスク等の制御
回路で、Cpuまたは、デユクリメンタ２４等から
サーチ・エリヤのスタート／エンド・アドレスを
受けて、このエリヤ内を連続して、読出す制御を
行なう。なお、エンド・アドレスとして、Cpuよ
り与えられた情報と、デイクリメンタ２４からの
情報と、いずれのものを採用するかの判別のため
のフラツグＦ４（第１図で説明済）を内蔵してい
る。

次に、第２図、第３図、第４図を使用して、実
際の動作を順次説明する。今、対象とするフアイ
ル即ちメモリ１に10個のレコードがアドレス00よ
り09まで記録されており、各レコードの対象とす
るキーの値が第４図の順番であつたとする、そし
て、Cpu側からの要求として、キーの値が100か
ら1000までのレコードを昇順（つまり、最小値検
索）にリードしたいものとする。

まづ、Cpuの制御により、サーチエリヤとして
アドレス“00”と“09”を第２図の制御回路２５
へ格納し、次に、下限値の100を第２図のメモリ
２へ、上限値の1000を第２図のメモリ４へ、対象
キーのレコード中の位置及び最小値検索の旨の制
御データを第２図のメモリ２１へそれぞれ格納後
検索ユニツトをスタートさせる。

これにより、当ユニツトはＡ＝100、Ｂ＝1000
となるから、100≦ｉ≦1000を検索することにな
る。最初のレコードをリードする際に第２図のフ
リツプ・フロツプ１７は、イニシヤルでリセツト
されている故に、アンドゲート６がオンし、メモ
リ４の出力がＢとなる。一方、オアゲート１８で
は、フリツプ・フロツプ１７のＱ側が“Ｌ”故
に、その出力は検出回路２２よりの出力が“Ｌ”
となる期間中“Ｌ”となり、メモリ５は書込モー
ドとなり、ｉ＝50を記憶する。

ｉ＝50であることより、50≦1000で比較回路９
は、条件成立出力を出す。しかし、比較回路３か
らは、100≦50が成立しないために出力が発生せ
ず、アンドゲート１１はオンしない。従つて、そ
の他の部分に変化は起らない。次に、２個目のレ
コードｉ＝408をリードすると、メモリ４，５及
びフリツプ・フロツプ１７等は前回と同様な動作
を行なうが、100≦408であることから比較回路３
の出力と、408≦1000より比較回路９の出力、つ
まりオアゲート１０の出力が発生し、アンドゲー
ト１１により100≦408≦1000の成立パルスが、フ
リツプ・フロツプ１４、ラツチ回路１６及びフリ
ツプ・フロツプ１７に与えられ、それぞれフリツ
プフロツプ１４の「該当なし」のステータス・フ
ラツグをオフ（₃＝０）し、また該当したレコ
ードのアドレスつまり“01”をアドレス・ラツチ
１６へ保持し、さらにフリツプ・フロツプ１７を
セツトする。また、メモリ５には４０８が記憶さ
れている。この状態から３番目、４番目及び５番
目のレコードをリードすると、フリツプ・フロツ
プ１７がセツトしていることから、メモリ４はラ
イト・モードに、メモリ５はリードモードになつ
ている。また、アンドゲート６はオフ、アンドゲ
ート７はオンとなつていることから、比較回路９
への入力データＢは、メモリ５の出力に切換り、
以後100≦ｉ≦408の条件で検索することになる。
よつて1573、671、85等のデータは無視される。
（ただし、アドレス・カウンタ１５は、各レコー
ド毎に＋１を行なつているものとする。）次に、６番目のレコード、ｉ＝270をリードす
ると、前記検索条件を満足する故に、前回ｉ＝
408のレコードの際と同様に、アンドゲート１１
より条件成立信号が出力され、この信号によりフ
リツプ・フロツプ１４はセツト（₃＝０、２回
目以後は無意味）ラツチ回路１６へは、該当アド
レスとして“05”を再ロードしなおす。さらに、
メモリ４へ書込まれたｉ＝270を以後Ｂとすべ
く、フリツプ・フロツプ１７をリセツトする。以
上の動作により、７番目のレコード以後は100≦
ｉ≦270の検索条件に変り、メモリ５はライト・
モードとなる。従つて、７番目のｉ＝320のレコ
ードは無視され、次の８番目のレコードｉ＝270
で、再度、条件成立信号が発生し、ラツチ回路１
６へアドレスが保持され、フリツプ・フロツプ１
７のセツトが行なわれる。しかし、今回の特別な
動作として、比較回路９よりの成立信号は、ｉ＝
270故に、等号（＝）側の出力が発生する。する
と、アンドゲート２３を経てフリツプ・フロツプ
１２がセツトし、「複数存在」のステータス・フ
ラツグがオンしたことになる。

この状態から、９番目のレコードｉ＝150を読
込むと、検索条件成立となり、ラツチ回路１６に
は“08”が、フリツプ・フロツプ１７はリセツト
が行なわれ、以後100≦ｉ≦150の条件で検索を行
なうこととなる。一方、比較回路９の出力は、
270≠150より大小比較（〓）側から成立信号が
出、アンドゲート１３を経てフリツプ・フロツプ
１２をクリヤする。

つまり、「複数存在」のステータス・フラツグ
はオフされる。次の10番目のレコードｉ＝670は
無視されるから、この状態で処理を終了する。

従つて、Cpu側では、処理の終了を検知した
後、まず、ステータスフラツグの「該当なし」
３をチエツクし、これが“Ｌ”ならば、ラツチ回
路１６のアドレスを抜取つて、該当レコードのア
ドレス“08”を使用してｉ＝150なるレコードを
リードする。当レコードに必要処理を行なつた後
に、次順位の最小値レコードを検索するために、
メモリ４へ格納する下限値を、当レコードのｉ＝
150に＋１して151として、再格納。また、上限値
は、再び1000をメモリ５へ格納して、検索ユニツ
トをスタートさせる。

すると、今回はｉ＝150のレコードは無視され
ることにより、処理結果としては、該当レコード
ｉ＝270で、そのアドレスは“07”、そして、ステ
ータス・フラツグの「複数存在」＝“Ｈ”という状
態で処理を終了する。

従つて、概要説明で述べた如く、当レコードを
読出し、必要処理を行なつた後、そのアドレス
“07”−１＝“06”をサーチのエンド・アドレスと
して、検索のためのその他の条件は前回のまま検
索ユニツトを動作させると、今回の該当レコード
はｉ＝270、そのアドレス“05”が検索され「複
数存在」のフラツグはオフとして終了する。従つ
て、今回以後はエンド・アドレスを初期値に戻
し、取出したレコードのキー値ｉ＝270に＋１し
て、指示しなおす。この様にして、順次320、
408、670及び671が取出せ、さらに、もう１回の
アクセスで「該当なし」が返えり、全体の処理が
終了する。

なお、従来テクニツクでは、ソート処理中、同
一値のキーが発生すると、あらかじめプライオリ
テイを付けた複数のキーを設けておき、初めに優
先度の最も高いキーについて、ソート処理を行な
い、同一値が発生するたびに、次々に優先度の低
いキーについてソート処理を実行し、すべてを出
力または並び替えを行なうのが一般的方法であ
る。

しかるに、前述の説明では、同一値のキー値レ
コードの識別情報として、その格納アドレスを採
用したが、本方式においても、第５図の如く、従
来ソートと同様に、あるキーで同一値が発生し、
「複数存在」のフラツグがセツトしたならば、
Cpuの制御により検索ユニツトへ、今までのキー
部（アイテム）に対しては、今回検索した、最大
または最小値のデータと等号比較の検索を指示
し、さらに、ソートのために約束された次順位の
プライオリテイのアイテムに対して最大または最
小値の検索を指示し、与えた条件がすべて満足す
るレコードのみを対象として、最大または最小値
を検索するように検索ユニツトに指示する。この
ことにより当ユニツトは前回のアイテムで等しい
値を有したレコードのみを対象に、今回のアイテ
ム中の最大or最小値を検索する。また、前述のプ
ライオリテイの深いキーのソート状態からステー
タス・フラツグの「該当なし」が返えれば、最大
または最小値検索の対象キーのプライオリテイを
浅くし、「複数存在」が返れば、反対に対象キー
のプライオリテイを深くすれば良い。従つて、両
者のステータス・フラツグが共にオフの場合のみ
基本的動作の「取出したレコードのキー値をイン
クリメントまたはデクリメントし、検索ユニツト
に指示しなおす」という動作を繰返せば良い。つ
まり本方式は、ソート処理時、同一値のキーを取
出す手段として、いずれの方式でも可能である。

以上述べた如く本発明による検索方式はメモリ
のワークエリアをとらないし、また、処理に要す
る時間を減少させることができる。

【図面の簡単な説明】

第１図は本発明による検索方式の概要説明図、
第２図は本発明による検索方式を用いた検索ユニ
ツトのブロツク図、第３図は第２図に示すブロツ
ク図の作動説明図、第４図は第２図に示されるブ
ロツク図の検索説明図、第５図は本発明による検
索方式の他の実施例を説明する説明図である。４，５……メモリ、１７……フリツプ・フロツ
プ。

Claims

【特許請求の範囲】１被検索データを格納する格納手段、前記格納手段から被検索データを読み出す読み
出し手段、検索条件となるデータを記憶する記憶手段、前記読み出し手段によつて読み出されるデータ
が前記記憶手段に記憶された検索条件を満たすか
どうかを前記読み出し手段による読み出しに同期
して判定する判定手段、前記判定手段による判定結果に基づいて、前記
検索条件となるデータを記憶する前記記憶手段の
データを変える制御手段、とを有することを特徴とする検索装置。２前記検索条件のデータとして、前記格納手段
のアドレスを記憶する第２記憶手段を有し、前記
アドレスによつて、前記検索条件を指定する指定
手段を有することを特徴とする特許請求の範囲第
１項記載の検索装置。