JP3348314B2 - 検索装置 - Google Patents

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、図形や文字などの認識
のための入力パターンの特徴量とパターン辞書に記憶さ
れたテンプレートとの照合、データベースにおける類似
レコードの検索、知識処理の類推的推論における類似概
念・類似規則の検索など、情報照合および情報検索技術
に関する。

【０００２】

【従来の技術】パターン認識やデータベース検索、知識
ベース検索などの情報照合や情報検索において、あらか
じめ記憶されたパターンのテンプレートやデータベース
のレコード、知識記述などから、入力パターンや検索要
求パターンに完全には一致しなくても、ある選好基準に
従ってもっとも好ましいものを見つけ出したいという要
求が多く存在する。このような情報照合や情報検索を実
現する従来の方法として、好ましさの度合をスカラ量と
して表せる評価関数を定義し、この評価関数を最大とす
るものを照合結果や検索結果とする方法が最も一般的で
ある。この方法によると、評価関数は必然的に、入力パ
ターンや検索要求パターンと、記憶されたテンプレート
やレコードと、ユーザが選好基準を指定するためのパラ
メータとの３つの変量を一つのスカラ量へと写像する関
数となる。ここで、これらの三つの変量はスカラ量には
限定されず、ベクタ量または構造をもった量でもあり得
る。記憶された複数の要素の中から評価関数を最大にす
る要素を見つけ出すことを最適要素検索と呼ぶことにす
る。

【０００３】以下、従来技術によるデータベースの類似
レコードの検索を説明する。図３は、要素の記憶形態の
一例のデータベースを示し、Ｎ個の要素ｅ〔１〕、ｅ
〔２〕、．．．、ｅ〔Ｎ〕から成る。レコード３０１₁
は、見出し３０２₁ とＭ個（Ｍは少なくとも１以上）の
属性に対する実数値で表される重みの並び３０
３₁₁、．．．、３０３_1Mから成る。ここで、符号の第１
番目の添字は、要素の番号１、２、．．．、Ｎを示し、
重みの並びの符号の第２番目の添字は、重みの番号を示
す。以下では簡単のため、例えばレコード３０１₁ をレ
コード３０１として、符号の添字を省略して説明を行
う。このデータベースのレコード３０１の重み３０３の
並びと同様の重み並びを持つ検索要求パターンに対し、
類似度の最も大きいレコードをデータベースより検索す
ることを考える。ここで類似度は、検索要求パターンの
重み並びと、データベース中のレコード３０１の重みの
並び３０３と、ユーザの選好基準を表すパラメータとか
ら計算される実数のスカラ量である。ここでパラメータ
は、データベースの各属性の重要さを属性毎に実数値で
表した重要度の並びである。類似度の一例としては、検
索要求パターンの重み並びを、 Ｗ_i ＝（Ｗ_i1，Ｗ_i2，．．．，Ｗ_iM） （ただしＭは重み並びの個数を表す整数）とし、データ
ベースのレコードの重み並びを、 Ｗ_j ＝（Ｗ_j1，Ｗ_j2，．．．，Ｗ_jM） とし、パラメータである重要度の並びを、 Ｘ ＝（Ｘ₁ ，Ｘ₂ ，．．．，Ｘ_M ） とした場合に、

【０００４】

【数１】

【０００５】で定義される関数Ｒ（Ｗ_i ，Ｗ_j ，Ｘ）で
計算される値が考えられる。この関数は一例に過ぎず、
検索要求パターンの重み並びと、データベースのレコー
ド３０１の重み３０３並びと、パラメータである重要度
並びの３つを特定できる変量から実数のスカラ量を計算
できる関数であれば、原理的にはどのようなものでも良
い。また、直接に重みの並びではなく見出し３０２を指
定し、その見出し３０２に対応するデータベースのレコ
ード３０１の重み３０３並びを検索要求パターンやパラ
メータの重要度並びとして用いることも考えられる。

【０００６】図７は、このような検索を行う従来の検索
装置のシステム構成を示し、要素記憶部２０１と、評価
値計算部２０２と、検索制御部２０５とから成る。

【０００７】要素記憶部２０１はデータベースのレコー
ド３０１を格納する。評価値計算部２０２はユーザが与
えた検索要求パターンとパラメータとレコードとから上
述の関数Ｒにより類似度を計算する。

【０００８】検索制御部２０５は、検索途中における類
似度の最大値を保持する最大評価値格納変数２０６と、
該類似度の最大値を与えるレコードを保持する最適要素
格納変数２０７とを有し、検索動作を司る。

【０００９】図８は、従来技術による検索制御部２０５
の動作を説明するフローチャートである。以下、同図に
より従来技術の検索動作を説明する。

【００１０】ステップ８０１）ユーザからの検索要求パ
ターンとパラメータを入力し、データベースから第１番
目のレコード３０１を取り出す。

【００１１】ステップ８０２）評価関数Ｒを用いて第１
番目のレコード３０１の類似度を算出する。

【００１２】ステップ８０３）算出された類似度、即ち
評価値を最大評価値格納変数２０６に格納し、第１番目
のレコード３０１を最適要素格納変数２０７に格納す
る。

【００１３】ステップ８０４）この時点までにデータベ
ースの中から取り出されたことのない別レコードを取り
出す。

【００１４】ステップ８０５）評価関数Ｒを用いて別レ
コードの類似度を算出する。

【００１５】ステップ８０６）別レコードの類似度が最
大評価値格納変数２０６に格納された類似度の最大値よ
り大きくなければステップ８０８に進む。

【００１６】ステップ８０７）別レコードの類似度を最
大評価値格納変数２０６に格納し、別レコードを最適要
素格納変数２０７に格納する。

【００１７】ステップ８０８）データベース中に未だ取
り出していないレコードが残っている場合にはステップ
８０４に進む。

【００１８】ステップ８０９）最適要素格納変数２０７
に格納されたレコードを検索結果として出力する。

【００１９】上記説明の通り、従来技術による検索装置
の検索制御部２０５は、すべてのレコードを取り出し、
このレコードの評価関数を計算するような制御を行って
おり、このような検索制御部を持つ検索装置を全走査型
検索装置と呼ぶ。

【００２０】また、従来、検索要求パターンの要素に完
全に一致する要素を検索する場合には、インデックス付
けやハッシュなどの方法を利用した高速な検索装置が実
現されている。類似度などの評価関数の計算値を最大と
する場合で、かつ、評価関数が検索する際のパラメータ
によって変化する最適要素検索の場合には、上記従来技
術による高速検索装置は利用できない。従って、上述の
データベースの類似レコード検索装置の例に限らず、最
適要素検索を行う従来の検索装置は、すべて全走査型検
索装置である。

【００２１】

【発明が解決しようとする課題】従来技術である全走査
型検索装置は、要素記憶部に格納された要素すべてに対
し評価関数を計算するため、要素記憶部に格納された要
素数に比例して検索時間が増大する。このため、要素記
憶部に格納された要素が多い場合に検索時間が長くかか
るという問題がある。

【００２２】本発明の目的は、上記のように要素数が多
いときに検索時間が長くかかるという問題を解決する高
速な検索装置を提供することにある。

【００２３】

【課題を解決するための手段】図１は、本発明の原理構
成図である。

【００２４】本発明の検索装置は、被検索情報である複
数の要素を格納する要素記憶部１０１と、二つの要素と
パラメータを入力されて所定の評価関数に従って評価値
を計算する評価値計算部１０２と、外部より入力された
検索要求の要素と検索要求のパラメータ及び要素記憶部
１０１よりの要素を評価値計算部１０２に入力して要素
記憶部の複数の要素のうち検索要求の要素と同じ要素以
外のすべての要素のなかから評価値を最大とする要素を
検索する検索動作を制御する検索制御部１０５とから構
成される検索装置において、要素記憶部１０１に格納さ
れた複数の要素のうち二つの要素の組合せに対し、該二
つの要素と所定のパラメータとを用いて計算された評価
値を事前評価値とし、該二つの要素のうち一方の要素毎
に該二つの要素のうちの他方の要素と該事前評価値の組
を該事前評価値の大きい順に所定の個数だけ格納する事
前評価値記憶部１０３と、事前評価値と、対応する他の
要素と、任意のパラメータとを入力されて、上記所定の
パラメータ値における事前評価値の増加に対して単調増
加である上界関数に従って上界値を計算する有界値計算
部１０４とから構成され、検索制御部１０５は、上記外
部よりの検索要求の要素及び検索要求のパラメータを入
力されて、検索要求の要素に対応して事前評価値記憶部
１０３に格納された要素と事前評価値の組を事前評価値
記憶部１０３より順次取り出し、検索要求の要素と、事
前評価値記憶部１０３から取り出された要素と、検索要
求のパラメータとを用いて評価値計算部１０２により算
出された最大の評価値を最大評価値とし、事前評価値と
検索要求の要素及び検索要求のパラメータとを上記有界
値計算部１０４に与えて計算された上界値が最大評価値
よりも小さい場合には、上界値に対応する事前評価値よ
りも小さい上記組の事前評価値記憶部からの順次取り出
しを打ち切る。

【００２５】さらに、本発明の検索装置は、被検索情報
である複数の要素を格納する要素記憶部１０１と、二つ
の要素とパラメータを入力されて所定の評価関数に従っ
て評価値を計算する評価値計算部１０２と、外部より入
力された検索要求の要素と検索要求のパラメータ及び要
素記憶部１０１よりの要素を評価値計算部１０２に入力
して要素記憶部の複数の要素のうち検索要求の要素と同
じ要素以外のすべての要素のなかから評価値を最小とす
る要素を検索する検索動作を制御する検索制御部１０５
とから構成される検索装置において、要素記憶部１０１
に格納された複数の要素のうち二つの要素の組合せに対
し、該二つの要素と所定のパラメータとを用いて計算さ
れた評価値を事前評価値とし、該二つの要素のうち一方
の要素毎に該二つの要素のうちの他方の要素と該事前評
価値の組を該事前評価値の大きい順に所定の個数だけ格
納する事前評価値記憶部１０３と、事前評価値と、対応
する他の要素と、任意のパラメータとを入力されて、上
記所定のパラメータ値における事前評価値の減少に対し
て単調減少である下界関数に従って下界値を計算する有
界値計算部１０４とから構成され、検索制御部１０５
は、上記外部よりの検索要求の要素及び検索要求のパラ
メータを入力されて、検索要求の要素に対応して事前評
価値記憶部１０３に格納された要素と事前評価値の組を
事前評価値記憶部１０３より順次取り出し、検索要求の
要素と、事前評価値記憶部１０３から取り出された要素
と、検索要求のパラメータとを用いて評価値計算部１０
２により算出された最小の評価値を最小評価値とし、事
前評価値と検索要求の要素及び検索要求のパラメータと
を上記有界値計算部１０４に与えて計算された下界値が
最小評価値よりも小さい場合には、下界値に対応する事
前評価値よりも小さい上記組の事前評価値記憶部からの
順次取り出しを打ち切る。

【００２６】

【作用】検索要求の要素と、要素記憶部１０１内の検索
要求の要素以外の要素と、検索要求のパラメータとを入
力されて評価値計算部１０２にて計算された評価値は、
事前評価値と、検索要求の要素と、検索要求のパラメー
タとを入力されて有界値計算部１０４にて計算された上
界値を越えない。従って、要素記憶部１０１内の検索要
求の要素以外のある要素に対して事前評価値記憶部１０
３に記憶された事前評価値と、検索要求の要素と、検索
要求のパラメータとにより計算された上界値が、探索制
御部１０５による探索動作中に探索制御部１０５に保持
される最大評価値よりも小さい場合には、検索要求の要
素と、上記検索要求の要素以外の要素と、検索要求のパ
ラメータとにより計算された評価値は、探索動作中に保
持される最大評価値を越えることがない。また、上界値
は事前評価値の増加に対して単調増加であるため、上記
検索要求の要素以外の要素に対する事前評価値よりも小
さい事前評価値に対する上界値は、上記検索要求の要素
以外の要素に対する上界値より必ず小さい。従って、上
記検索要求の要素以外の要素に対する事前評価値よりも
小さい事前評価値を与える他の要素に対する評価値は、
上記最大評価値を越えないことが保証される。

【００２７】以上の説明からわかるように、本発明によ
る評価値を最大とする要素を検索する検索装置では、上
界値を計算し最大評価値と比較することにより、最適要
素に成りえない要素を判定し、この最適要素に成りえな
い要素に対する評価値の計算を打ち切ることによって、
高速に検索を行うことを可能としている。

【００２８】さらに、本発明による評価値を最小とする
要素を検索する検索装置では、下界値を計算し最小評価
値と比較することにより、最適要素に成りえない要素を
判定し、この最適要素に成りえない要素に対する評価値
の計算を打ち切ることによって、高速に検索を行うこと
を可能としている。

【００２９】

【実施例】以下図面と共に、本発明の一実施例を詳細に
説明する。

【００３０】図２は本発明の一実施例の検索装置の構成
を示し、要素記憶部２０１と、評価値計算部２０２と、
事前評価値記憶部２０３と、上界計算部２０４と、検索
制御部２０５とから成る。

【００３１】要素記憶部２０１は、被検索情報を表す要
素を格納し、任意の要素を検索制御部２０５からの要求
に従って取り出すことができる。図３は、本発明の一実
施例による要素記憶部２０１の記憶形態を説明する図で
あり、Ｎ個の要素ｅ〔１〕、ｅ〔２〕、．．．、ｅ
〔Ｎ〕から成る。各要素は、レコード型のデータ構造に
より表され、例えば、要素ｅ〔１〕に対応するレコード
３０１₁ は、見出し３０２ ₁ とＭ個（Ｍは少なくとも１
以上）の属性に対する実数値で表される重みの並び３０
３₁₁、．．．、３０３_1Mから成る。同図において、符号
の第１番目の添字は、要素の番号１、２、．．．、Ｎを
示し、重みの並びの符号の第２番目の添字は、重みの番
号を示す。以下では簡単のため、例えばレコード３０１
₁ をレコード３０１として、符号の添字を省略して説明
を行う。

【００３２】評価値計算部２０２は、上記レコード型の
二つの要素ｅ〔ｉ〕、ｅ〔ｊ〕（ｉ、ｊは１からＮの任
意の整数）とパラメータｐが検索制御部２０５から与え
られた場合に、所定の評価関数Ｆ（ｅ〔ｉ〕，ｅ
〔ｊ〕，ｐ）に従って評価値を計算し検索制御部２０５
に出力する。本発明の一実施例による評価関数として、
例えば、一方の要素ｅ〔ｉ〕の重み並びを、Ｗ_i ＝（Ｗ
_i1，Ｗ_i2，．．．，Ｗ_iM）（ただしＭは重み並びの個数
を表す整数）とし、他方の要素ｅ〔ｊ〕の重み並びを、
Ｗ_j ＝（Ｗ_j1，Ｗ_j2，．．．，Ｗ_jM）とし、パラメータ
の重み並びを、Ｘ ＝（Ｘ₁ ，Ｘ₂ ，．．．，Ｘ_M ）と
した場合に、

【００３３】

【数２】

【００３４】で定義される類似度関数Ｒ（Ｗ_i ，Ｗ_j ，
Ｘ）を利用する。この評価関数の値、即ち評価値は、０
から１の範囲の実数値である。また、パラメータ個々の
重みＸ _k は、１か１より大きい定数値のいずれかの値を
取るとする。以下の説明では、１より大きい定数値をＣ
で表すことにする。但し、本発明において利用される評
価関数は、上記類似度関数Ｒに限定されることはなく、
ある特定のパラメータｐ ₀ のもとでの評価値ｖ₀ （ｉ，
ｊ）と、一方の要素ｅ〔ｉ〕と、パラメータｐとから上
界値を計算でき、かつ、特定のパラメータ値ｐ₀ におけ
る評価値ｖ₀ （ｉ，ｊ）の増加に対して単調増加である
ような上界関数Ｓ（ｖ₀ （ｉ，ｊ），ｅ〔ｉ〕，ｐ）を
求めることが可能であるという性質を有する評価関数で
あればどのような関数でも構わない。

【００３５】事前評価値記憶部２０３は、要素記憶部２
０１に格納された個々の要素ｅ〔１〕，ｅ
〔２〕，．．．，ｅ〔Ｎ〕に対して、個々の要素以外の
要素との間で、ある特定のパラメータｐ₀ のもとで評価
関数に従って計算された評価値、即ち事前評価値に基づ
き、事前評価値とこの事前評価値を与える個々の要素以
外の要素の組を事前評価値の大きい順に所定の個数格納
する。図４は、本発明の一実施例による事前評価値記憶
部２０３における格納形態を示し、要素ｅ〔ｉ〕に対し
て、他の要素ｅ〔ｊ〕との間で特定のパラメータｐ₀ の
もとで計算された事前評価値をｖ₀ （ｉ，ｊ）で表し、
個々の要素ｅ〔１〕，ｅ〔２〕，．．．，ｅ〔Ｎ〕につ
いて、要素４０１₁₁、．．．、４０１_1L、．．．、４０
１₂₁、．．．、４０１ _2L、．．．、４０１_N1、．．．、
４０１_NLと事前評価値４０２₁₁、．．．、４０
２_1L、．．．、４０２₂₁、．．．、４０２_2L、．．．、
４０２_N1、．．．、４０２_NLの組が、事前評価値の大き
い順にリスト構造で連なっている。ここで、Ｎは要素の
個数を表し、Ｌは上記事前評価値の大きい順の所定の個
数を表す。例えば、同図において最左端に示すリスト構
造は、要素ｅ〔１〕に対して事前評価値の大きい順に要
素と事前評価値の組が上方から下方に連なっている。同
様に左から２番目のリスト構造は、要素ｅ〔２〕に対し
て事前評価値の大きい順に要素と事前評価値の組が連な
っている。尚、事前評価値記憶部２０３に格納される要
素は、要素記憶部２０１に格納される要素に対応するの
で、要素の値そのものを格納する代わりに、要素記憶部
２０１内における要素のアドレスを指し示すポインタを
格納することも可能である。事前評価値記憶部２０３の
上記説明の構造を利用することにより、特定の要素に対
して、その要素との間で計算された事前評価値の大きい
要素を順次取り出すことが可能である。尚、図４に記述
された要素の番号は説明の便宜上の一例にすぎず、実際
の事前評価値の大小によって変わる。さらに、ここで説
明した事前評価値記憶部２０３における格納形態は一例
であり、特定の要素に対してその要素との事前評価値が
大きい要素を順次取り出すことが可能であればどのよう
なものでも良い。例えば、リスト構造の代わりに表形式
の格納形態を利用することも可能である。

【００３６】上界計算部２０４は、検索制御部２０５よ
り入力される事前評価値ｖ₀ （ｉ，ｊ）と、一方の要素
とｅ〔ｉ〕と、パラメータｐとから上界関数Ｓ（ｖ
₀ （ｉ，ｊ），ｅ〔ｉ〕，ｐ）に従って上界値を計算
し、その結果を検索制御部２０５に出力する。上界関数
は、評価関数と事前評価値の計算に用いた特定のパラメ
ータｐ₀ によって決定される。但し、同一の評価関数及
び同一の事前評価値計算に用いるパラメータに対して、
複数の上界関数が存在することもあり得る。以下に、本
発明の一実施例による式（１）に示す評価関数Ｒに対す
る上界関数の導出法を説明する。事前評価値の計算にＸ
₁ ＝Ｘ₂ ＝・・・＝Ｘ_M ＝１なるパラメータを用いる場
合、事前評価値は、パラメータの要素がすべて１の場合
の類似度であり、これをｖ₀ （ｉ，ｊ）或いは簡単のた
めｖ₀ とすると、ｖ₀ は（１）式により、

【００３７】

【数３】

【００３８】と書ける。ここで、任意のパラメータを考
え、値がＣである要素の集合をＫと書くと、類似度の計
算式は、

【００３９】

【数４】

【００４０】と書き直せる。ここで、

【００４１】

【数５】

【００４２】

【数６】

【００４３】

【数７】

【００４４】と書くこととし、またＣ² −１をαと書く
と、（３）式は、

【００４５】

【数８】

【００４６】と書ける。ここで、内積の関係より、

【００４７】

【数９】

【００４８】なる関係があるので、

【００４９】

【数１０】

【００５０】が成り立つ。類似度と事前評価値の比Ｒ
（Ｗ_i ，Ｗ_j ，Ｘ）／ｖ₀ をγとし、（９）式の関係を
用いて（７）式を書き換えると、

【００５１】

【数１１】

【００５２】となる。（１０）式から、Ｓ_ijとＳ_iiの変
化に対する極大値を求めることにより上界を得ることが
できる。最初に、Ｓ_ijに関してγの極大を調べ、次に、
Ｓ_iiに対する変化を調べると、γの極大値γ^' _m は、

【００５３】

【数１２】

【００５４】となる。γは、評価値（類似度）と事前評
価値の比であるので、この比が最大の時の評価値（類似
度）、即ち評価値（類似度）の上界関数Ｓ（ｖ₀ （ｉ，
ｊ），ｅ〔ｉ〕，ｐ）は、

【００５５】

【数１３】

【００５６】と計算できる。さらに、（１２）式におい
て、ｖ₀ （ｉ，ｊ）を増加させた場合、ｖ₀ （ｉ，ｊ）
の増加割合に対し、右辺の項、

【００５７】

【数１４】

【００５８】の増加割合は必ず小さくなるので、上記上
界関数はｖ₀ （ｉ，ｊ）の増加に対して単調増加であ
る。尚、上記上界関数により計算される上界値は、要素
ｅ〔ｉ〕やパラメータｐに依存しないが、これは本発明
の一実施例で用いている評価関数に特有の性質であり、
一般に上界関数は事前評価値ｖ₀ （ｉ，ｊ）と、一方の
要素ｅ〔ｉ〕と、パラメータｐとをすべてその式に含む
形式となる。

【００５９】検索制御部２０５は、最大評価値格納変数
２０６と最適要素格納変数２０７を有し、外部から与え
られた検索要求の要素に対し、外部から与えられた検索
要求のパラメータのもとで、要素記憶部２０１の複数の
要素のうち、検索要求の要素と同じ要素以外のすべての
要素のなかから評価値を最大とする要素を検索する検索
動作を制御する。

【００６０】さらに、本発明の一実施例による検索制御
部２０５は、あらかじめ、要素記憶部２０１に格納され
る個々の要素ｅ〔ｉ〕（ｉは１からＮまでの整数）に対
し、特定のパラメータｐ₀ を用いて、あらゆる要素ｅ
〔ｊ〕（ｊは１からＮまでの整数）についての事前評価
値ｖ₀ （ｉ，ｊ）＝Ｆ（ｅ〔ｉ〕，ｅ〔ｊ〕，ｐ₀ ）を
評価値計算部２０２において計算させ、次に、要素ｅ
〔ｊ〕と事前評価値ｖ₀ （ｉ，ｊ）の組を、事前評価値
の大きい順に一定個数を事前評価値記憶部２０３に格納
し、外部から検索要求パターンである要素ｅ〔Ｉ〕とパ
ラメータｐが与えられたときに、事前評価値記憶部２０
３から要素ｅ〔ｊ〕と事前評価値ｖ₀ （Ｉ，ｊ）を取り
出しながら、検索要求要素ｅ〔Ｉ〕と事前評価値記憶部
２０３から取り出した事前評価値ｖ₀ （Ｉ，ｊ）とパラ
メータｐとを上界計算部２０４に与えて計算させた上界
値を得て、この上界値がそれまで取り出した要素に対す
る評価値のうちの最大値を越えていない場合には、上界
値を与えた要素よりも小さい事前評価値を与える要素の
事前評価値記憶部２０３からの取り出しを打ち切ること
により検索動作を制御する。

【００６１】次に、本発明の一実施例により、上界値が
最大評価値よりも小さい要素に対しては、その要素に関
する事前評価値よりも小さい事前評価値を与える要素に
関する評価を打ち切っても正しく検索結果が得られるこ
とを図面と共に説明する。図５は、本発明の一実施例に
よる事前評価値とパラメータを与えた場合の評価値と上
界値との関係の一例を説明する図である。同図の横軸
は、事前評価値記憶部２０３に格納されている一の要素
に対して、その他の要素との間で計算された事前評価値
の大きい順序を示し、上記一の要素以外のＬ個の要素が
事前評価値の大きい順に左から並んでいる。同図の縦軸
は、事前評価値及び評価値の値を示し、上方ほど値が大
きい。同図において事前評価値５０１₁ 、５０
１₂ 、．．．、５０２_L を●で示し、検索要求の要素と
事前評価値を与える要素と検索要求のパラメータとから
計算される評価値５０２₁ を○で、評価値５０２₂ を◎
で示し、検索要求の要素と検索要求のパラメータと事前
評価値とから計算される上界値５０３ ₃ 、．．．、５０
３_L を−で示す。各符号の添字１、２、．．．、Ｌは、
事前評価値の大きさの順序による要素の順番を表してい
る。

【００６２】図５では、１番目及び２番目に大きい事前
評価値に対して、その評価値を与える要素に関する評価
値を計算した時点での評価値と上界値との関係を示して
いる。この時点での最大評価値は、同図の◎で示される
２番目の事前評価値を与える要素に対するものである。
この時点において、３番目の事前評価値に関する上界値
は、上記最大評価値を越えないので、３番目の事前評価
値を与える要素に対する評価値は、その要素が如何なる
要素であっても、決して上記最大評価値を越えることは
ない。さらに、４番目移行の事前評価値を与える要素に
関する上界値は、上界値の単調性により３番目の事前評
価値に関する上界値さえ越えないので、上記最大評価値
を越えることはあり得ない。このことから、この時点で
得られた上記最大評価値がすべての要素に対する評価値
の中での最大値であることがわかる。従って、３番目以
降の事前評価値を与える要素に対しては、評価値の計算
を打ち切っても、最大評価値を与える要素、即ち検索結
果が正しく得られる。

【００６３】図６は、本発明の一実施例の検索制御部２
０５の動作を説明するためのフローチャートである。以
下、検索要求の要素をＥ₁ 、検索要求のパラメータをＰ
とする。

【００６４】ステップ６０１）外部からの検索要求の要
素Ｅ₁ と検索要求のパラメータＰが入力される。

【００６５】ステップ６０２）最大評価値格納変数２０
６を評価値が取り得る最小値以下、本発明の一実施例で
は例えば０とし、最適要素格納変数２０７を「空」とし
て、最大評価値格納変数２０６と最適要素格納変数２０
７を初期化する。

【００６６】ステップ６０３）事前評価値記憶部２０３
より検索要求の要素Ｅ₁ に対する事前評価値が最大の要
素の要素と事前評価値の組を取り出す。また、取り出し
た要素と事前評価値の組には例えば取り出されたことが
識別できる印を付与して、取り出されていない要素と事
前評価値の組と区別できるようにする。

【００６７】ステップ６０４）検索要求の要素Ｅ₁ と検
索要求のパラメータＰと事前評価値記憶部２０３より取
り出した要素とを評価値計算部２０２に入力して、評価
値計算部２０２の計算結果の評価値を取り出す。

【００６８】ステップ６０５）上記評価値が最大評価値
格納変数２０６に格納された値よりも大きくない場合に
は、ステップ６０７に進む。

【００６９】ステップ６０６）上記評価値を最大評価値
格納変数２０６に格納し、上記事前評価値記憶部２０３
より取り出した要素を最適要素格納変数２０７に格納す
る。ここで、以前に最大評価値格納変数２０６及び最適
要素格納変数２０７に格納されていた値は保持されな
い。

【００７０】ステップ６０７）事前評価値記憶部２０３
内に、未だ取り出されていない要素と事前評価値の組が
残っていない場合にはステップ６１２に進む。

【００７１】ステップ６０８）事前評価値記憶部２０３
から、未だ取り出されていない要素と事前評価値の組の
中で、事前評価値が最も大きい組を取り出し、取り出し
た要素と事前評価値の組には例えば取り出されたことが
識別できる印を付与して、取り出されていない要素と事
前評価値の組と区別できるようにする。

【００７２】ステップ６０９）検索要求の要素Ｅ₁ と検
索要求のパラメータＰと事前評価値記憶部２０３より取
り出した事前評価値とを上界計算部２０４に入力して、
上界計算部２０４の計算結果を上界値として得る。

【００７３】ステップ６１０）最大評価値格納変数２０
６に格納された最大評価値と上記上界値を比較し、上界
値が最大評価値よりも大きい場合には、最大評価値より
も大きい評価値を与える要素が存在する可能性があるた
め、ステップ６０４に進む。

【００７４】ステップ６１１）上界値が最大評価値より
も小さい場合には、上界関数が事前評価値の増加に対し
て単調増加するため、事前評価値記憶部２０３内に残っ
ている未だ取り出されていないすべての事前評価値に対
する上界値は最大評価値よりも小さい。これにより、事
前評価値記憶部２０３内には、最大評価値よりも大きい
評価値を与える要素が存在しない。従って、検索動作を
終了し、最適要素格納変数２０７に格納された要素を検
索結果である最適要素として出力する。

【００７５】ステップ６１２）上界値が最大評価値より
も小さくなる検索打切りの判定が成立する前に、事前評
価値記憶部２０３内のすべての要素と事前評価値の組の
取り出しを終了している場合には、事前評価値記憶部２
０３に記憶された要素以外の要素が最大の評価値を与え
る可能性があるため、全走査型探索に切り替える。尚、
本発明の一実施例においては従来技術において説明した
全走査型探索を利用する。

【００７６】上記説明の通り、あらかじめ要素を事前評
価値の大きい順に事前評価値記憶部２０３に格納し、打
切判定処理（ステップ６１０）によって検索途中におけ
る最大評価値と上界値との大小関係に基づき、最大評価
値よりも大きい評価値を与える要素が存在しないことが
保証される場合に検索を打ち切ることにより、検索対象
の要素を削減でき高速な検索が実現できる。

【００７７】尚、本発明の一実施例では、検索制御部２
０５は、最大評価値とこの最大評価値を与える要素を格
納するために最大評価値格納変数２０６と最適要素格納
変数２０７とを有しているが、これは本発明により本質
的に規定されるものではなく、検索途中における上記最
大評価値と最大評価値を与える要素を知ることができる
ならばどのような方法でも良い。例えば、事前評価値記
憶部２０３及び要素記憶部２０１に格納された要素に識
別フラグを付加し、最大評価値を与える要素の識別フラ
グだけを立てて他の要素と区別できるようにする方法も
考えられる。また、検索制御部２０５の動作も本発明の
一実施例の動作に規定されるものではなく、事前評価値
記憶部２０３から事前評価値が大きい順に要素を取り出
しながら最大評価値と最大評価値を与える要素を特定す
ることができ、上界値が最大評価値を越えない要素に対
する検索を打ち切ることができるならばどのような動作
でも良い。

【００７８】以上では、本発明の一実施例では、評価値
を最大とする要素を検索する検索装置により説明を行っ
ているが、例えば、本発明の一実施例の類似度関数Ｒの
逆数を評価関数とし、類似度関数Ｒに対応する上界関数
の逆数を下界関数とし、上界関数計算部２０４を下界関
数を計算する下界関数計算部とし、事前評価値記憶部２
０３では事前評価値の大きい順に代わり事前評価値の小
さい順に要素と事前評価値の組を格納し、検索制御部２
０５においては、最大評価値を最小評価値とし、上界値
が最大評価値よりも大きい場合ではなく、下界値が最小
評価値よりも小さい場合に検索の打ち切り判定を行うこ
とにより、本発明の第２の実施例による評価値を最小と
する要素を検索する検索装置を実現することができる。

【００７９】さらに、本発明の一実施例による検索シス
テムの構成では、要素記憶部２０１と、評価値計算部２
０２と、事前評価値記憶部２０３と、限界計算部２０４
と、検索制御部２０５とを独立したモジュールとして表
しているが、これらは物理的に独立している必要はな
い。例えば、プロセッサとメモリからなるコンピュータ
を用いて、要素記憶部２０１と、事前評価値記憶部２０
３と、最大評価値格納変数２０６と、最適要素格納変数
２０７との各機能をメモリに割り付け、評価値計算部２
０２と、上界計算部２０４と、検索制御部２０５の各機
能をプロセッサに割り付ける方法などが考えられる。

【００８０】

【発明の効果】以上説明したように、本発明により外部
から与えられた検索要求の要素と検索要求のパラメータ
に基づき、多数の要素の中から評価関数を最大とする要
素を検索する場合に、事前評価値記憶部から事前評価値
が大きい順に要素を取り出しながら最大評価値を持つ要
素を特定し、上界値を計算して、上界値が最大評価値よ
りも小さい場合には検索を打ち切ることにより、検索対
象となる要素の数を削減できるので、要素の数が多い場
合にも高速な検索が可能となる。また、上界値関数は事
前評価値の変化に対し単調であることを規定しているの
で、本発明における検索打切りの基準で検索を打ち切っ
た場合には、検索を打ち切った時点での最大評価値を与
える要素が、すべての要素のなかで最大の評価値を与え
ることが保証される。

【００８１】さらに、本発明により外部から与えられた
検索要求の要素と検索要求のパラメータに基づき、多数
の要素の中から評価関数を最小とする要素を検索する場
合に、事前評価値記憶部から事前評価値が小さい順に要
素を取り出しながら最小評価値を持つ要素を特定し、下
界値を計算して、下界値が最小評価値よりも大きい場合
には検索を打ち切ることにより、検索対象となる要素の
数を削減できるので、要素の数が多い場合にも高速な検
索が可能となる。また、下界値関数は事前評価値の変化
に対し単調であることを規定しているので、本発明にお
ける検索打切りの基準で検索を打ち切った場合には、検
索を打ち切った時点での最小評価値を与える要素が、す
べての要素のなかで最小の評価値を与えることが保証さ
れる。

【００８２】すなわち、本発明によれば、要素が多い場
合にも高速で誤差のない検索を行う検索装置が実現でき
る。

【図面の簡単な説明】

【図１】本発明の原理構成図である。

【図２】本発明の一実施例の検索装置の構成図である。

【図３】本発明の一実施例の要素記憶部の記憶形態を説
明する図である。

【図４】本発明の一実施例の事前評価値記憶部の記憶形
態を説明する図である。

【図５】本発明の一実施例の評価値と上界値の関係を説
明する図である。

【図６】本発明の一実施例の検索制御部の動作フローチ
ャートである。

【図７】従来技術の検索装置の構成図である。

【図８】従来技術の検索制御部の動作フローチャートで
ある。

【符号の説明】

１０１、２０１ 要素記憶部 １０２、２０２ 評価値計算部 １０３、２０３ 事前評価値記憶部 １０４ 有界値計算部 １０５、２０５ 検索制御部 ２０４ 上界計算部 ２０６ 最大評価値格納変数 ２０７ 最適要素格納変数 ３０１₁ 、．．．、３０１_N レコード ３０２₁ 、．．．、３０２_N 見出し ３０３₁₁、．．．、３０３_NM 重み ４０１₁₁、．．．、４０１_NL 要素 ４０２₁₁、．．．、４０２_NL、５０１₁ 、．．．、５０
１_L 事前評価値 ５０２₁ 、５０２₂ 評価値 ５０３₃ 、．．．、５０３_L 上限値

フロントページの続き (56)参考文献 特開 平４−81972（ＪＰ，Ａ) 特開 平３−123973（ＪＰ，Ａ) 特開 平５−158991（ＪＰ，Ａ) 特開 昭53−98749（ＪＰ，Ａ) 湯川高志、笠原要、松澤和光、石川 勉，アバウト推論：多観点概念ベースに おける類似概念検索の高速化，情報処理 学会学会第47回（平成５年後期）全国大 会講演論文集（３），日本，社団法人情 報処理学会，1993年 ９月27日，ＰＰ. 57−58 (58)調査した分野(Int.Cl.⁷，ＤＢ名) G06F 17/30 ＪＩＣＳＴファイル（ＪＯＩＳ)

Claims (2)

(57)【特許請求の範囲】
1. 【請求項１】 被検索情報である複数の要素を格納する
   要素記憶部と、 二つの要素とパラメータを入力されて所定の評価関数に
   従って評価値を計算する評価値計算部と、 外部より入力された検索要求の要素と検索要求のパラメ
   ータ及び該要素記憶部よりの要素を該評価値計算部に入
   力して該要素記憶部の複数の要素のうち該検索要求の要
   素と同じ要素以外のすべての要素のなかから評価値を最
   大とする要素を検索する検索動作を制御する検索制御部
   とから構成される検索装置において、 前記要素記憶部に格納された複数の要素のうち二つの要
   素の組合せに対し、該二つの要素と所定のパラメータと
   を用いて計算された評価値を事前評価値とし、該二つの
   要素のうち一方の要素毎に該二つの要素のうちの他方の
   要素と該事前評価値の組を該事前評価値の大きい順に所
   定の個数だけ格納する事前評価値記憶部と、 前記事前評価値と、前記対応する他の要素と、任意のパ
   ラメータとを入力されて、上記所定のパラメータ値にお
   ける事前評価値の増加に対して単調増加である上界関数
   に従って上界値を計算する有界値計算部とから構成さ
   れ、 前記検索制御部は、上記外部よりの検索要求の要素及び
   検索要求のパラメータを入力されて、該検索要求の要素
   に対応して前記事前評価値記憶部に格納された要素と事
   前評価値の組を前記事前評価値記憶部より順次取り出
   し、該検索要求の要素と、前記事前評価値記憶部から取
   り出された要素と、該検索要求のパラメータとを用いて
   前記評価値計算部により算出された最大の評価値を最大
   評価値とし、該事前評価値と該検索要求の要素及び該検
   索要求のパラメータとを上記有界値計算部に与えて計算
   された上界値が該最大評価値よりも小さい場合には、該
   上界値に対応する事前評価値よりも小さい上記組の前記
   事前評価値記憶部からの順次取り出しを打ち切ることを
   特徴とする、検索装置。
2. 【請求項２】 被検索情報である複数の要素を格納する
   要素記憶部と、 二つの要素とパラメータを入力されて所定の評価関数に
   従って評価値を計算する評価値計算部と、 外部より入力された検索要求の要素と検索要求のパラメ
   ータ及び該要素記憶部よりの要素を該評価値計算部に入
   力して該要素記憶部の複数の要素のうち該検索要求の要
   素と同じ要素以外のすべての要素のなかから評価値を最
   小とする要素を検索する検索動作を制御する検索制御部
   とから構成される検索装置において、 前記要素記憶部に格納された複数の要素のうち二つの要
   素の組合せに対し、該二つの要素と所定のパラメータと
   を用いて計算された評価値を事前評価値とし、該二つの
   要素のうち一方の要素毎に該二つの要素のうちの他方の
   要素と該事前評価値の組を該事前評価値の大きい順に所
   定の個数だけ格納する事前評価値記憶部と、 前記事前評価値と、前記対応する他の要素と、任意のパ
   ラメータとを入力されて、上記所定のパラメータ値にお
   ける事前評価値の減少に対して単調減少である下界関数
   に従って下界値を計算する有界値計算部とから構成さ
   れ、 前記検索制御部は、上記外部よりの検索要求の要素及び
   検索要求のパラメータを入力されて、該検索要求の要素
   に対応して前記事前評価値記憶部に格納された要素と事
   前評価値の組を前記事前評価値記憶部より順次取り出
   し、該検索要求の要素と、前記事前評価値記憶部から取
   り出された要素と、該検索要求のパラメータとを用いて
   前記評価値計算部により算出された最小の評価値を最小
   評価値とし、該事前評価値と該検索要求の要素及び該検
   索要求のパラメータとを上記有界値計算部に与えて計算
   された下界値が該最小評価値よりも大きい場合には、該
   下界値に対応する事前評価値よりも大きい上記組の前記
   事前評価値記憶部からの順次取り出しを打ち切ることを
   特徴とする、検索装置。