JPH0320819A - ベクトルデータ検索装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔、産業上の利用分野〕 この発明はベクトルデータの最大位，最小値の検索Ｖこ
関し、特に検索結果である最大値または最小｛１１’Ｌ
　ｋｃ対応した装索番号もデータに伴って検索すること
ができるベクトルラゞ一夕倹索装置に関する。

し従来の技術〕 第３図は従来のべクトな・データ検索装ａｔ示すブロッ
ク図である。同図におーて、１は頴序づけられた一連の
ベクトルデータが保持されたベクトルデータ保持亭段、
２はこのベクトルデータ保持手Ｒ１から読み出畜れたベ
クトルデータがセットきれるレジスタ、３はこのベクト
Ａ・データに対応した要素番号を生或する要素番号生成
手段、４はらの要ＸＩＩ号虫成手Ｒ３から生成きれた要
素番号がセットきれるレジスタ、５はレジスタ２に格納
されてーるデータと下記のレジスタ８に格納きれている
データｋを比較し遡択信号１１１を出力する比較手段、
６はレジスタ２に格納されているベクトルデータＦ１と
下記のレジスタ８に格納されてしるベクトルデータＦ！
の一方を選択傷号Ｔｏによって逃択する選択手段、Ｔは
レジスタ４に格納されている要素番号Ｇ１こ下記のレジ
スタ９に格納濾れている要素番号Ｇ．の一方？：選択信
号ＴＯによって選択する選択手段、８は遡択手段６によ
り週択されたベクトルデータを格納するレジスタ、９は
選択手段７１ＣよＤ選択きれた要素番号を格納するレジ
スタである。

なか、要素番号はデータに対して１対１の関係で付与さ
れているので、要素番号の大小関係においては等しいと
いう場合は存在しない。

次に上記構成によるベクトルデータ検索装置の動作につ
いて説明する。筐ず、第１のサイクルタイムで、ベクト
ル保持手段１から順序づけられた一連のベクトルデータ
の最初のデータが出力しレジスタ２にセットされる。一
方、このベクトルデータκ対応した要素番号が！！素番
号生或手段３で生成しレジスタ４にセットされる。そし
て、データ比較手段５はレジスタ２Ｋ格納されたベクト
ルグータとレジスタ８に格納されたベクトルデータを比
較するが、このときレジスタ８にはベクトルデータが格
納されていないためにデータ比較を行なわず、選択手段
６シよび選択手段Ｔがそれぞれレジスタ２かよびレジス
タ４Ｋ格納されているデータを選択するような選択信号
Ｔ，を生成し出力する。次に、第２のサイクルタイムで
、ベクトルデータ保持手段１に保持されている２番目の
デ−タが出力し、レジスタ２にセットされる。一方、こ
のベクトルデータに対応した要素番号生成手段３で生威
し、レジスタ４にセットされる。同時に、データ比較手
段５で、選択手段６および選択手段７を選択するように
生或された選択信号Ｔ．に基づいて、レジスタ８および
レジスタ９にはそれぞれレジスタ２およびレジスタ４の
データ、すなわち順序づけられた一連のベクトルデータ
の最初のデータに対応した要素番号が格納される。デー
タ比較手段５ではレジスタ２およびレジスタ８に格納さ
れているベクトルデータの値Ｆ１　＃　Ｆ　２すなわち
ベクトルデータの２番目のデータと最初のデータの値を
その比較対象として比較を行い、命令が最大値検索指定
の時には大きい方の値を、命令が最小値検索指定の時に
は小さい方の値を選択手段６が選択するような選択信号
Ｔｏを生成し出力する。また、レジスタ２に格納されて
いるベクトルデータの値とレジスタ８に格納されている
ベクトルデータの値が等しい場合には常にレジスタ８の
値の方を選択手段６が選択するような信号Ｔｏを生或し
出力する。これをさらに説明すると、比較手段５は比較
対象Ｆ１ｔＦ１を入力として命令が最大値検索指定の時
にはＦ”１＞Ｆ’，ならばＦ１を、Ｆ，≦Ｆ，ならばＦ
！を、また命令が最小値検索指定の時にはＦｌ＜Ｆ２な
らばＦｌを、Ｆ１≧Ｆ！ならばＦ２を、選択手段６が選
択するような信号’ｒｅを生或する。一方、選択手段７
は選択手段６と同一の選択信号ＴＯに基づいて、ベクト
ルデータの最初のデータに対応した要素番号が格納され
ているレジスタ９の出力Ｇ，とベクトルデータの２番目
のデータに対応した要素番号が格納されているレジスタ
４の出力Ｇ１のどちらか一方を選択して出力する。同様
にして、ｎ個（ただし、ｎは自然数）のベクトルデータ
に対して第ｎ　＋　１のサイクルタイムで、レジスタ８
にベクトルデータの中の最大値または最小値が格納され
る一方、レジスタ９にレジスタ８に格納された最大値ま
たは最小値に対応した要素番号を格納することができる
。

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

上述した従来のベクトルデータ倹索装置は、デ−タ比較
手段に入力する比較対象となるデータが等しい時には常
に同一のレジスタの出力を選択する構成になっているの
で、要素番号が小さい順に並べられて入力すれば要素番
号の小さい方が、要素番号が大きい順に並べて入力すれ
ば要素番号の大きい方が、そして要素番号が大小順に並
べられていない状態で入力すれば該当する要素番号の中
の任意の１つが結果に付随した要素番号となる。

したがって、検索結果に付随した要素番号として、もし
検索対象となるベクトルデータの中に最大値または最小
値が複数個存在した場合に、最小の要素番号が必要なと
きにはｌ！素番号が小さい順にベクトルデータ検索装置
に入力するようにベクトルデータを並べかえるという処
理が、また最大の要素番号が必要な場合には要素番号が
大きい順にベクトルデータ検索装置に入力するようにベ
クトルデータを並べかえるという処理が検索処理を行う
前κ必要となシ、全体の処理時間が増加するという欠点
がある。

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

この発明に係るベクトルデータ検索装置は、検索対象と
なるベクトルデータを入力として最大値を検索するか最
小値を検索するのかを指定する命令に基づいて最大値ま
たは最小値を示す信号を生或し出力するデータ比較手段
と、検索対象となるベクトルデータをデータ比較手段か
ら送出される最大値または最小値を示す信号に基づいて
最大値または最小値を選択し出力する選択手段と、検索
対象となるベクトルデータの夫々κ対応した要素番号を
入力として要素番号の大小関係を示す信号を生或し出力
する要素番号比較手段と、データ比較手段から送出され
る最大値または最小値を示す信号と要素番号比較手段か
ら送出される要素番号の大小関係を示す信号を入力とし
最大値または最小値が複数個存在した場合にはこの要素
番号の中の最小の要素番号を出力するか最大のｌ！素番
号を出力するかを指定する命令に基づいてどの要素番号
を選択すべきか判断しそのための選択信号を生或レ出力
する選択信号生戒手段と、検索対象となるベクトルデー
タの夫々に対応した要素番号を入力として選択信号生或
手段から送出される選択信号に基づいて最大値または最
小値に対応した要素番号を選択し出力する選択手段とを
有している。

〔作用〕

この発明は検索対象となるベクトルデータの中に最大値
または最小値が複数個存在する場合に、必要に応じて出
力すべき要素番号の中の最小の要素番号を出力するか、
最大の要素番号を出力するかを命令で指定することがで
きる。

〔実施例〕

第１図はこの発明に係るベクトルデータ検索装置の一実
施例を示すブロック図である。同図にかいて、１０は選
択信号８．に基づいてレジスタ２０出力ＤＩ　とレジス
タ８の出力Ｄ雪のうちのどちらか一方を選択してレジス
タ８に出力する選択手段、１１は選択信号Ｓ＝に基づい
てレジスタ４の出力Ｅ．とレジスタ９の出力Ｅ３のうち
のどちらか一方を選択してレジスタ９Ｋ出力する選択手
段、１２はレジスタ４の出力Ｅ１とレジスタ９の出力Ｅ
ｓ−″ｊ″なわちベクトルデータの中の２番目のべクト
ルデータに対応した要素番号の値と最初のベクトルデー
タに対応した要素番号の値を比較し、大小関係を求めて
それを示す比較情報信号Ｓ！を生成し出力する要素番号
比較手段、１３はデータ比較手段５の出力８，と要素番
号比較手段１２の出力Ｓ１を比較するが、（Ａ）　　比
較対象となるデータの値が等しくない場合には選択手段
１ｏが選択するデータに対応する要素番号、すなわち選
択手段１０がレジスタ２の出力Ｄｌを選択するときには
レジスタ４の出力Ｅ１を生或し出力し、また選択手段１
０がレジスタ８の出力Ｄ！を選択するときにはレジスタ
９の出力Ｅ，を選択するような選択信号Ｓ３を生成し出
力し、（Ｂ）　　比較対象となるデータが等しい場合に
は、（Ｂ−１　）　　命令が最大要素番号指定の時には
要素番号比較手段１２がら送出される比較情報信号Ｓ！
を基にして大きい方の要素番号を選択手段１１が選択す
るような選択信号Ｓ，を生威し出力し、（Ｂ−２）　　
命令が最小要素番号指定のときには小さい力の要素番号
を選択手段１１が選択するような選択信号Ｓ３を生威し
て出力する選択信号生或手段である。

次に、上記構成によるベクトルデータ検索装置の動作に
ついて脱明する。まず、第１のサイクルタイムで、ベク
トル保持手段１から順序づけられた一連のベクトルデー
タの最初のデータが出力してレジスタ２にセットされる
。一方、このベクトルデータに対応した要素番号が要素
番号生戒手段３で生或してレジスタ４にセットされる。

そして、データ比較手段５はレジスタ２に格納されたベ
クトルデータとレジスタ８に格納されたベクトルデータ
を比較するが、この場合レジスタ８にはベクトルデータ
が格納されていないため、データ比較を行なわず、選択
手段１０はレジスタ２の出力Ｄ１を選択するような選択
信号８．を生或して出力する。一方、要素番号比較手段
１２で比較対象とする要素番号はレジスタ４に格納され
ている値とレジスタ９に格納されている値であるが、レ
ジスタ９には比較対象となるｌ！素香号が格納されてい
ないので、比較を行なわず選択手段１１がレジスタ４の
出力Ｅ１を選択するような選択信号Ｓｓ’ｋ生或するよ
うに選択信号生或手段１３に対して指示する。次に、第
２のサイクルタイムで、ベクトルデータ保持手段１に保
持している２番目のデータを読み出してレジスタ２にセ
ットすると共にそのデータに対応した要素番号を要素番
号生或手段３で生或しレジスタ４にセットする。また、
レジスタ８にはレジスタ２の出力Ｄ１がセットされ、レ
ジスタ９にはレジスタ４の出力Ｅ！がセットされる。デ
ータ比較手段５はレジスタ２の出力Ｄ１とレジスタ８の
出力Ｄ富、すなわちベクトルデータの中の２番目のデー
タと最初のデータを比較し、命令が最大値検索指定の時
には大きい方の値を、命令が最小値検索指定の時には小
さい方の値を選択手段１０が選択するような選択信号８
．を生威し出力する。１た、レジスタ２に格納されてい
るデータの値とレジスタ８に格納されているデータの値
とが等しい場合には常κレジスタ２の出力ＤＩを選択手
段１０が選択するような選択信号Ｓｏを生或し出力する
。このため、選択手段１０はこの選択信号８ｅに基づい
てレジスタ２の出力ＤＩと？ジスタ８の出力ＤＩのうち
のどちらか一方を選択してレジスタ８■出力する。また
、データ比較手段５は選択信号生戒手段１３に対して、
選択手段１０がレジスタ２の出力Ｄ！とレジスタ８の出
力ＤＩのどちらかを選択するように指示する信号と共に
、レジスタ２の出力Ｄ１とレジスタ８の出力Ｄ，が等し
いか否かを示す信号も合わせてＳ．として出力する。そ
して、！！素番号比較手段１２はレジスタ４の出力Ｅ！
とレジスタ９の出力Ｅｈすなわちベクトルデータの中の
２番目のデータに対応する！！素番号の値と最初のデー
タに対応した要素番号の値を比較し、大小関係を求め、
それを示す比較情報信号Ｓ１を生成し出力する。選択信
号生戒手段１３はデータ比較手段５の出力Ｓ１と要素番
号比較手段１２の出力Ｓ１を入力とし、比較対象となる
データの値が等しくない場合には選択手段１０が選択す
るデータに対応する要素番号、すなわち選択手段１０が
レジスタ２の出力Ｄ１を選択するときにはレジスタ４の
出力Ｅ，を、レジスタ８の出力Ｄ，を選択するときには
レジスタ９の出力Ｅ１を選択するような選択信号Ｓ３を
生威し出力し、比較対象となるデータの値が等しい場合
には命令が最大要素番号指定のときには要素番号比較手
段１２から送出される比較情報信号ＳＳを基にして大き
い方の要素番号を、命令が最小要素番号指定のときには
小さい方の要素番号を選択手段１１が選択するような選
択信号８ｓを生成し出力する。このため、選択手段１１
は選択信号Ｓ３に基づいてレジスタ４の出力Ｅ１とレジ
スタ９の出力Ｅ３のうちのどちらか一方を選択しレジス
タ９に出力する。以下同様にして、ｎ個（ただし、ｎは
自然数）のベクトルデータに対して第ｎ　＋　１のサイ
クルタイムでレジスタ８にはｎ個のベクトルデータの中
の最大値または最小値が、レジスタ９Ｋはベクトルデー
タの中に最大値または最小値が複数個存在した場合には
要素番号指定命令に従って対応する要素番号の中の最大
の要素番号筐たは最小の要素番号を格納することができ
る。

第２図はこの発明に係るベクトルデータ検索装置の他の
実施例を示すブロック図であり、データ比較手段に３人
カデータ比較手段を用いた場合である。この実施例では
、ベクトルデータ保持手段は順序づけられた一連のベク
トルデータを２つのベクトルデータ保持手段１ａとベク
トルデータ保持手段１ｂに分けて格納し保持している。

筐た、要素番号生戒手段はそれぞれベクトルデータ保持
手段１１，１ｂに格納保持されているベクトルデータに
対応した要素番号を出力するため、要素番号生戒手段３
ｍ，３ｂに分かれてかシ、等しい！！素番号は存在しな
い。このため、レジスタ２，４はそれそれレジスタ２ａ
，２ｂｊ？よびレジスタ４ｍ，４ｂに分けられている。

同様に、データ比較手段５および要素番号比較手段１２
は３人力である。！た、選択手段１０．１１はそれぞれ
選択信号Ｕ．　，　ｔｙ３に基づいてデータおよび要素
番号を選択して出力する。

次に上記構成によるベクトルデータ検索装置の動作につ
いて説明する。まず、第１サイクルタイムで、ベクトル
データ保持手段１ａ，１ｂの最初のデータが読み出され
てそれそれレジスタ２ａ，２ｂＫセットされると共に、
それぞれのデータに対応した１ｉ！素番号生戊手段３ａ
，３ｂで生或し出力し、レジスタ４１，４ｂにセットす
る。そして、３人力データ比較手段５はレジスタ２ｂの
出力Ｊ’、レジスタ２ａの出力Ｊｓｋよびレジスタ８の
出力Ｊ４を比較するが、このときレジスタ８には比較対
象となるデータが格納されていないので、出力Ｊ４を比
較対象とはせず、出力Ｊ３と出力Ｊｓとの比較を行ない
、最大値検出か最小値検出かの命令指定に基づいて選択
手段１０が適当な値を選択するような選択信号Ｕ．を生
威し出力する。３人力要素番号比較手段１２の比較対象
となる要素番号の値はレジスタ４ｂの出力Ｋ３とレジス
タ４ａの出力Ｋ３、レジスタ９の出力Ｋ４であるが、レ
ジスタ９には比較対象となる要素番号が格納されていな
いので、出力Ｋ４を比較対象とはせず、出力Ｋ３と出力
Ｋ３との大小関係を求め、比較情報信号Ｕ！として出力
する。そして、３人カデータ比較手段５で生成し出力す
るデータ比較情報信号Ｕ．は選択信号１０にどの値を選
択すべきかを指示したかを示す信号とその値の他にその
値と等しい値はどれであるかを示す信号とからなｂ１選
択信号生或手段１３は３人力データ比較手段５に入力す
る比較データの中に選択すべきデータの値と等しい値の
データがない場合には選択すべきデータに対応した要素
番号を、等しい値のデータがある場合には要素番号指定
の命令に従って比較情報信号Ｕ１を基にして適当な要素
番号を選択手段１１が選択するように選択信号Ｕｓを生
或し出力する。そして、選択手段１０および選択手段１
１はそれぞれ選択信号ｔｙ．　Ｉ　ｕｓに基づいてデー
タおよびｌ！素番号を選択し出力する。次に、第２サイ
クルでは、ベクトルデータ保持手段１ｍ，１ｂからそれ
ぞれ２番目のデータを読み出して、レジスタ２ａ　＊　
２　ｂ　Ｋセットすると共に、そのデータに対応した！
！素番号を要素番号生或手段ａｍ，ａｂで生或し出力し
レジスタｊａ，４ｂにセットする。また、レジスタ８か
よびレジスタ９Ｋはそれぞれ選択手段１ｏおよび選択手
段１１の選択結果が格納される。このとき、３人カデー
タ比較手段５０比較対象はレジスタ２ｂの出力Ｊ！、レ
ジスタ２ａの出力Ｊ３およびレジスタ８の出力Ｊ４であ
シ、この３個のデータの比較した処理を行なう。同様の
処理をくシ返えして行なうことによ，９２ｎ個のベクト
ルデータに対して第ｎ　＋　１のサイクルタイムで、レ
ジスタ８には２ｎ個のベクトルデータの中の最大値また
は最小値で、レジスタ９にはベクトルデータの中に最大
値または最小値が複数個存在した場合にはＡ累謄号指定
命令に従って対応する要素番号の中の最大の要素番号ま
たは最小の要素番号を格納することができる。

〔発明の効果〕

以上詳細に説明したように、この発明に係るベクトルデ
ータ検索装置によれば、要素番号についても比較を行い
、その比較情報をもとに、検索対象となるベクトルデー
タの中に最大値または最小値が複数個存在し゛Ｃいる場
合にも必要に応じて、対応丁る要索番号の中に最大のも
のを結果として求めるか、最小のものを結果として求め
るか命令によって指定し求めることによう、検索に必要
な処理時間を大幅に縮めることができ、さらにデータに
対応した各要素番号を小さい順または大きい順に入力す
る必要がないので、データと１！素番号を検索の前に並
べかえる必要がなく、処理時間の短縮と共に利用者に使
い易い環境を提供することができるなどの効果がある。

【図面の簡単な説明】

第１図はこの発明に係るベクトルデータ検索装置の一実
施例を示すブロック図、第２図はこの発明に係るベクト
ルデータ検索装置の他の実施例を示すブロック図、第３
図は従来のベクトルデータ検索装置を示すブロック図で
ある。 １０および１１●●●●選択手段、１２●●●●要素番
号比較手段、１３●●・・選択信号生戒手段。

Claims (1)

【特許請求の範囲】
1. 順序づけられた一連のベクトルデータを入力として、こ
   のベクトルデータの中の最大値または最小値とこの最大
   値または最小値に対応した要素番号とを検索し出力する
   ベクトルデータ検索装置において、前記ベクトルデータ
   の中に最大値または最小値が複数個存在する場合に出力
   すべき要素番号の中の最小の要素番号を出力するか、最
   大の要素番号を出力するかを命令で指定できることを特
   徴とするベクトルデータ検索装置。