ベクトル検索装置、ベクトル検索方法、プログラムおよびプログラムを記録した記録媒体
【課題】検索キーベクトルにマッチする検索対象ベクトルを特定する場合、検索対象ベクトルの数が多くても、検索処理時間が短いベクトル検索装置を提供することを目的とする。
【解決手段】各座標毎に、特定の桁数の文字列が対応している近似値の集合である近似値集合が付随している近似値集合情報と、検索対象ベクトルを入力とし、上記検索対象ベクトルの各座標の値に対し、上記座標に対応する上記近似値集合における最も差の小さい近似値を求め、上記近似値の対応する文字列を、全座標にわたって連結することにより、上記検索対象ベクトルに対応する文字列である検索対象文字列を生成し、上記検索対象文字列をキーとして、対応する上記検索対象ベクトルとともに検索インデックスに格納する検索対象文字列生成手段とを有することを特徴とするベクトル検索装置である。
【解決手段】各座標毎に、特定の桁数の文字列が対応している近似値の集合である近似値集合が付随している近似値集合情報と、検索対象ベクトルを入力とし、上記検索対象ベクトルの各座標の値に対し、上記座標に対応する上記近似値集合における最も差の小さい近似値を求め、上記近似値の対応する文字列を、全座標にわたって連結することにより、上記検索対象ベクトルに対応する文字列である検索対象文字列を生成し、上記検索対象文字列をキーとして、対応する上記検索対象ベクトルとともに検索インデックスに格納する検索対象文字列生成手段とを有することを特徴とするベクトル検索装置である。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、検索対象と検索キーがベクトルである場合に、高速に検索対象ベクトルを検索するベクトル検索装置、ベクトル検索方法、プログラムおよびプログラムを記録した記録媒体に関する。
【背景技術】
【０００２】
ベクトル検索の手法として、ベクトルの長さを１に正規化した上で、ベクトル間の関連度をベクトルの内積として算出する方法がある（たとえば、非特許文献１参照）。
【０００３】
この他に、ベクトル間の関連度をユークリッド距離として算出することが一般的に行われている。
【０００４】
このようにして算出した関連度の大きい順に、検索結果を提示する。
【非特許文献１】熊本睦、島田茂夫、加藤恒昭著「概念ベースの情報検索への適用―概念ベースを用いた検索の特性評価―」情報処理学会研究報告、Vol.SIG-ICS 115、pp.9-16、1999.
【発明の開示】
【発明が解決しようとする課題】
【０００５】
検索キーベクトルにマッチする検索対象ベクトルを特定するにあたり、ベクトルの各座標は実数なので、上記従来手法のように、内積やユークリッド距離のような数値演算により、ベクトル間の関連度を算出している。このやり方では、全検索対象ベクトルとの関連度を算出する必要がある。
【０００６】
検索対象ベクトルの数が極めて多い場合、全検索対象ベクトルとの関連度算出は時間がかかり、検索処理時間がかかるという問題があった。
【課題を解決するための手段】
【０００７】
上記課題を解決するために、本発明におけるベクトル検索装置は、
各座標毎に、特定の桁数の文字列が対応している近似値の集合である近似値集合が付随している近似値集合情報と、
検索対象ベクトルを入力とし、上記検索対象ベクトルの各座標の値に対し、上記座標に対応する上記近似値集合における最も差の小さい近似値を求め、上記近似値の対応する文字列を、全座標にわたって連結することにより、上記検索対象ベクトルに対応する文字列である検索対象文字列を生成し、上記検索対象文字列をキーとして、対応する上記検索対象ベクトルとともに検索インデックスに格納する検索対象文字列生成手段とを有する。
【０００８】
また、検索キーベクトルを入力とし、上記検索キーベクトルの各座標の値に対し、上記座標に対応する上記近似値集合における最も差の小さい近似値を求め、上記近似値の対応する文字列を、全座標にわたって連結することにより、上記検索キーベクトルに対応する文字列である検索キー文字列を生成する検索キー文字列生成手段と、
上記検索キー文字列と、上記検索インデックス中の検索対象文字列とを文字列照合し、一致する検索対象文字列に対応付けられている検索対象ベクトルの集合を取得する文字列照合手段とをさらに併せ持つ。
【０００９】
また、上記検索キーベクトルと、上記文字列照合手段で取得した検索対象ベクトルの集合の中の各検索対象ベクトルとの関連度を計算する関連度算出手段をさらに併せ持つ。
【発明の効果】
【００１０】
検索対象ベクトルを検索対象文字列に変換し検索インデックスに格納し、検索キーベクトルを検索キー文字列に変換し、検索キー文字列と検索対象文字列とを文字列照合するので、検索キー文字列と一致する検索対象文字列に対応付けられている検索対象ベクトルの集合を即座に取得することができる。検索キーベクトルと近い検索対象ベクトルの集合を正確に取得はできず、近似的に近い検索対象ベクトルの集合を取得するが、全ての検索対象ベクトルとの関連度を計算する必要がないため、検索処理にかかる時間が問題とならなくなる。
【００１１】
また、取得した検索対象ベクトルに対して関連度を算出するので、この関連度を利用して、ある閾値以上の関連度を持つ検索対象ベクトルを表示したり、関連度の大きい順に検索対象ベクトルをランキング表示したりできる。取得した検索対象ベクトルは少数なので、大幅に短い時間で、このような検索結果を表示することが可能となる。
【発明を実施するための最良の形態】
【００１２】
発明を実施するための最良の形態は、以下の実施例である。
【実施例１】
【００１３】
以下、図面とともに本発明の実施例を説明する。
【００１４】
図１は、本発明の実施例におけるベクトル検索装置の構成例を示す。
【００１５】
ベクトル検索装置は、各座標毎に、特定の桁数の文字列が対応している近似値の集合である近似値集合が付随している近似値集合情報を持つ。
【００１６】
ここで、各座標毎の近似値集合とは、たとえば、０から０．０１の倍数だけ間隔の空いた数列
｛…，−０．０３，−０．０２，−０．０１，０．００，０．０１，０．０２，０．０３，…｝ …（１）
や、０から０．０５の倍数だけ間隔の空いた数列
｛…，−０．１５，−０．１０，−０．０５，０．００，０．０５，０．１０，０．１５，…｝ …（２）
が挙げられる。
【００１７】
各近似値には、座標毎に定まる桁数の文字列が対応し、異なる近似値には異なる文字列が対応するようにする。たとえば、数列（１）、（２）の近似値には、プラスマイナスの符号と小数点以下第一位と第二位を並べた３桁の文字列とする。これにより、数列（１）、（２）中の各近似値に対応する文字列の列は、それぞれ（１）’、（２）’のようになる。
｛…，−０３，−０２，−０１，＋００，＋０１，＋０２，＋０３，…｝ …（１）’
｛…，−１５，−１０，−０５，＋００，＋０５，＋１０，＋１５，…｝ …（２）’
もちろん、全ての座標について、同じ近似値集合をとってもよい。
【００１８】
この近似値集合情報は、それに関して定義した情報を、ファイルやメモリ、プログラムのコード中等に保持しているものとする。
【００１９】
検索対象文字列生成手段１１は、検索対象ベクトルを入力とし、上記検索対象ベクトルの各座標の値に対し、上記座標に対応する上記近似値集合における最も差の小さい近似値を求め、上記近似値の対応する文字列を、全座標にわたって連結することにより、上記検索対象ベクトルに対応する文字列である検索対象文字列を生成し、上記検索対象文字列をキーとして、対応する上記検索対象ベクトルとともに検索インデックス１５に格納する。
【００２０】
以下では、いずれの座標も、近似値とその対応文字列として（１）、（１）’をとっているものとして説明をする。
【００２１】
検索対象となるベクトルは、一定次元数の、各座標値が一般に実数のベクトルである。検索対象ベクトルは、一般に複数個ある。図２のｖ１〜ｖ６は、３次元の検索対象ベクトルの例である。
【００２２】
各検索対象ベクトルに対し、以下の処理を行う。
【００２３】
上記検索対象ベクトルの各座標の値に対し、上記座標に対応する上記近似値集合における最も差の小さい近似値を求める。たとえば、ｖ１については、座標１は０．５２３４…なので、最も差の小さい近似値は０．５２となる。このようにして、ｖ１から導出される各座標値が近似値のベクトルは、
（０．５２，−０．４０，０．８１） …（３）
となる。
【００２４】
次に、導出した各近似値の対応する文字列を、全座標にわたって連結する。（３）からは、
＋５２−４０＋８１ …（４）
という文字列が得られる。このようにして得られた文字列を上記検索対象ベクトルに対応する検索対象文字列とする。
【００２５】
各座標毎に、対応する文字列の桁数は定まっているので、各座標が、連結された文字列の何桁目から何桁目までに相当するかは一意に定まる。したがって、連結された文字列に対して、元の近似値ベクトルも一意に定まる。したがって、導出した連結文字列が同一である検索対象ベクトルや検索キーベクトルは、同一の近似値ベクトルを導出し、互いに近い関係にある。
【００２６】
検索対象文字列をキーとして、対応する検索対象ベクトルとともに検索インデックス１５に格納する。検索インデックスのキーは、たとえば、ハッシュとして実装する。この例では、（４）を検索キーとして、それに対応する検索対象ベクトルとしてｖ１を対応付ける。
【００２７】
複数の検索対象ベクトルから同一の検索対象文字列が生成された場合は、上記検索対象文字列に、生成源となった検索対象ベクトルの全てを対応付ける。図３は、図２の検索対象ベクトルをもとに生成された検索インデックスである。ｖ１、ｖ３、ｖ５から（４）が生成されたので、（４）には、ｖ１、ｖ３、ｖ５が対応付けられている。
【００２８】
検索キー文字列生成手段１２は、検索キーベクトルを入力とし、上記検索キーベクトルの各座標の値に対し、上記座標に対応する上記近似値集合における最も差の小さい近似値を求め、上記近似値の対応する文字列を、全座標にわたって連結することにより、上記検索キーベクトルに対応する文字列である検索キー文字列を生成する。
【００２９】
検索キーとなるベクトルは、検索対象ベクトルと同一次元数の、各座標値が一般に実数のベクトルである。図４のｑは、検索キーベクトルの例である。
【００３０】
検索キー文字列生成手段１２の処理は、検索対象文字列生成手段１１における文字列生成と同じである。図４のｑから導出される各座標値が近似値のベクトルは（３）となり、（３）から検索キー文字列として（４）が得られる。
【００３１】
検索キー文字列生成手段１２をなくし、検索キー文字列生成手段１２の処理を、検索対象文字列生成手段１１における文字列生成処理で行うという構成にすることも可能である。
【００３２】
文字列照合手段１３は、上記検索キー文字列と、上記検索インデックス１５中の検索対象文字列とを文字列照合し、一致する検索対象文字列に対応付けられている検索対象ベクトルの集合を取得する。
【００３３】
検索キー文字列としての（４）は、検索インデックス中の検索対象文字列の（４）と一致するので、対応する検索対象ベクトルｖ１、ｖ３、ｖ５が得られる。
【００３４】
関連度算出手段１４は、上記検索キーベクトルと、上記文字列照合手段１３で取得した検索対象ベクトルの集合の中の各検索対象ベクトルとの関連度を計算する。この関連度を利用して、ある閾値以上の関連度を持つ検索対象ベクトルを表示したり、関連度の大きい順に検索対象ベクトルをランキング表示したりすることも可能である。
【００３５】
図４のｑと、取得した検索対象ベクトルｖ１、ｖ３、ｖ５それぞれとの関連度を、たとえば、両ベクトル間のユークリッド距離として算出する。図５は、距離の小さい順に、検索対象ベクトルを対応する距離値とともに表示したものである。
【００３６】
つまり、上記実施例は、各座標毎に、特定の桁数の文字列が対応している近似値の集合である近似値集合が付随している近似値集合情報と、検索対象ベクトルを入力とし、上記検索対象ベクトルの各座標の値に対し、上記座標に対応する上記近似値集合における最も差の小さい近似値を求め、上記近似値の対応する文字列を、全座標にわたって連結することにより、上記検索対象ベクトルに対応する文字列である検索対象文字列を生成し、上記検索対象文字列をキーとして、対応する上記検索対象ベクトルとともに検索インデックスに格納する検索対象文字列生成手段とを有することを特徴とするベクトル検索装置の例である。
【００３７】
この場合、検索キーベクトルを入力とし、上記検索キーベクトルの各座標の値に対し、上記座標に対応する上記近似値集合における最も差の小さい近似値を求め、上記近似値の対応する文字列を、全座標にわたって連結することにより、上記検索キーベクトルに対応する文字列である検索キー文字列を生成する検索キー文字列生成手段と、上記検索キー文字列と、上記検索インデックス中の検索対象文字列とを文字列照合し、一致する検索対象文字列に対応付けられている検索対象ベクトルの集合を取得する文字列照合手段とを有する。
【００３８】
また、上記検索対象文字列生成手段が、検索キーベクトルを入力とし、上記検索キーベクトルの各座標の値に対し、上記座標に対応する上記近似値集合における最も差の小さい近似値を求め、上記近似値の対応する文字列を、全座標にわたって連結することにより、上記検索キーベクトルに対応する文字列である検索キー文字列を生成し、上記検索キー文字列と、上記検索インデックス中の検索対象文字列とを文字列照合し、一致する検索対象文字列に対応付けられている検索対象ベクトルの集合を取得する文字列照合手段を有する。
【００３９】
さらに、上記検索キーベクトルと、上記文字列照合手段で取得した検索対象ベクトルの集合の中の各検索対象ベクトルとの関連度を計算する関連度算出手段を有する。
【００４０】
また、上記実施例を方法の発明として把握することができる。つまり、上記実施例は、各座標毎に、特定の桁数の文字列が対応している近似値の集合である近似値集合が付随している近似値集合情報と、検索対象文字列生成手段が、検索対象ベクトルを入力とし、上記検索対象ベクトルの各座標の値に対し、上記座標に対応する上記近似値集合における最も差の小さい近似値を求め、上記近似値の対応する文字列を、全座標にわたって連結することにより、上記検索対象ベクトルに対応する文字列である検索対象文字列を生成し、上記検索対象文字列をキーとして、対応する上記検索対象ベクトルとともに検索インデックスに格納する検索対象文字列生成工程とを有することを特徴とするベクトル検索方法の例である。
【００４１】
この場合、検索キー文字列生成手段が、検索キーベクトルを入力とし、上記検索キーベクトルの各座標の値に対し、上記座標に対応する上記近似値集合における最も差の小さい近似値を求め、上記近似値の対応する文字列を、全座標にわたって連結することにより、上記検索キーベクトルに対応する文字列である検索キー文字列を生成し、記憶装置に記憶する検索キー文字列生成工程と、文字列照合手段が、上記検索キー文字列と、上記検索インデックス中の検索対象文字列とを文字列照合し、一致する検索対象文字列に対応付けられている検索対象ベクトルの集合を取得し、記憶装置に記憶する文字列照合工程とを有する。
【００４２】
また、上記検索対象文字列生成手段が、検索キーベクトルを入力とし、上記検索キーベクトルの各座標の値に対し、上記座標に対応する上記近似値集合における最も差の小さい近似値を求め、上記近似値の対応する文字列を、全座標にわたって連結することにより、上記検索キーベクトルに対応する文字列である検索キー文字列を生成し、記憶装置に記憶し、文字列照合手段が、上記検索キー文字列と、上記検索インデックス中の検索対象文字列とを文字列照合し、一致する検索対象文字列に対応付けられている検索対象ベクトルの集合を取得し、記憶装置に記憶する文字列照合工程を有する。
【００４３】
さらに、上記検索キーベクトルと、上記文字列照合手段で取得した検索対象ベクトルの集合の中の各検索対象ベクトルとの関連度を、関連度算出手段が計算し、記憶装置に記憶する関連度算出工程を有する。
【００４４】
また、上記ベクトル検索装置を構成する上記各手段としてコンピュータを機能させるプログラムを想定することができる。この場合、上記の実施の形態における処理をプログラムとして構築し、上記プログラムを通信回線または記憶媒体からインストールし、ＣＰＵ等の手段で実施することが可能である。
【００４５】
しかも、上記プログラムをコンピュータ読取可能な記録媒体に記録するようにしてもよい。この場合、ＣＤ、ＤＶＤ、ハードディスク、光ディスク、光磁気ディスク、半導体メモリ等の記録媒体に記録するようにしてもよい。
【００４６】
また、本発明は、上記実施の形態に限定されることなく、特許請求の範囲内において種々変更・応答が可能である。
【産業上の利用可能性】
【００４７】
本発明は、ベクトルを使用する文書検索技術や画像検索技術に適用可能である。
【図面の簡単な説明】
【００４８】
【図１】本発明の実施例におけるベクトル検索装置１００の構成例を示す。
【図２】３次元の検索対象ベクトルの例を示す図である。
【図３】図２の検索対象ベクトルをもとに生成された検索インデックス１５の例を示す図である。
【図４】検索キーベクトルの例を示す図である。
【図５】距離の小さい順に、検索対象ベクトルを対応する距離値とともに表示したものである。
【符号の説明】
【００４９】
１００…ベクトル検索装置、
１１…検索対象文字列生成手段、
１２…検索キー文字列生成手段、
１３…文字列照合手段、
１４…関連度算出手段、
１５…検索インデックス。
【技術分野】
【０００１】
本発明は、検索対象と検索キーがベクトルである場合に、高速に検索対象ベクトルを検索するベクトル検索装置、ベクトル検索方法、プログラムおよびプログラムを記録した記録媒体に関する。
【背景技術】
【０００２】
ベクトル検索の手法として、ベクトルの長さを１に正規化した上で、ベクトル間の関連度をベクトルの内積として算出する方法がある（たとえば、非特許文献１参照）。
【０００３】
この他に、ベクトル間の関連度をユークリッド距離として算出することが一般的に行われている。
【０００４】
このようにして算出した関連度の大きい順に、検索結果を提示する。
【非特許文献１】熊本睦、島田茂夫、加藤恒昭著「概念ベースの情報検索への適用―概念ベースを用いた検索の特性評価―」情報処理学会研究報告、Vol.SIG-ICS 115、pp.9-16、1999.
【発明の開示】
【発明が解決しようとする課題】
【０００５】
検索キーベクトルにマッチする検索対象ベクトルを特定するにあたり、ベクトルの各座標は実数なので、上記従来手法のように、内積やユークリッド距離のような数値演算により、ベクトル間の関連度を算出している。このやり方では、全検索対象ベクトルとの関連度を算出する必要がある。
【０００６】
検索対象ベクトルの数が極めて多い場合、全検索対象ベクトルとの関連度算出は時間がかかり、検索処理時間がかかるという問題があった。
【課題を解決するための手段】
【０００７】
上記課題を解決するために、本発明におけるベクトル検索装置は、
各座標毎に、特定の桁数の文字列が対応している近似値の集合である近似値集合が付随している近似値集合情報と、
検索対象ベクトルを入力とし、上記検索対象ベクトルの各座標の値に対し、上記座標に対応する上記近似値集合における最も差の小さい近似値を求め、上記近似値の対応する文字列を、全座標にわたって連結することにより、上記検索対象ベクトルに対応する文字列である検索対象文字列を生成し、上記検索対象文字列をキーとして、対応する上記検索対象ベクトルとともに検索インデックスに格納する検索対象文字列生成手段とを有する。
【０００８】
また、検索キーベクトルを入力とし、上記検索キーベクトルの各座標の値に対し、上記座標に対応する上記近似値集合における最も差の小さい近似値を求め、上記近似値の対応する文字列を、全座標にわたって連結することにより、上記検索キーベクトルに対応する文字列である検索キー文字列を生成する検索キー文字列生成手段と、
上記検索キー文字列と、上記検索インデックス中の検索対象文字列とを文字列照合し、一致する検索対象文字列に対応付けられている検索対象ベクトルの集合を取得する文字列照合手段とをさらに併せ持つ。
【０００９】
また、上記検索キーベクトルと、上記文字列照合手段で取得した検索対象ベクトルの集合の中の各検索対象ベクトルとの関連度を計算する関連度算出手段をさらに併せ持つ。
【発明の効果】
【００１０】
検索対象ベクトルを検索対象文字列に変換し検索インデックスに格納し、検索キーベクトルを検索キー文字列に変換し、検索キー文字列と検索対象文字列とを文字列照合するので、検索キー文字列と一致する検索対象文字列に対応付けられている検索対象ベクトルの集合を即座に取得することができる。検索キーベクトルと近い検索対象ベクトルの集合を正確に取得はできず、近似的に近い検索対象ベクトルの集合を取得するが、全ての検索対象ベクトルとの関連度を計算する必要がないため、検索処理にかかる時間が問題とならなくなる。
【００１１】
また、取得した検索対象ベクトルに対して関連度を算出するので、この関連度を利用して、ある閾値以上の関連度を持つ検索対象ベクトルを表示したり、関連度の大きい順に検索対象ベクトルをランキング表示したりできる。取得した検索対象ベクトルは少数なので、大幅に短い時間で、このような検索結果を表示することが可能となる。
【発明を実施するための最良の形態】
【００１２】
発明を実施するための最良の形態は、以下の実施例である。
【実施例１】
【００１３】
以下、図面とともに本発明の実施例を説明する。
【００１４】
図１は、本発明の実施例におけるベクトル検索装置の構成例を示す。
【００１５】
ベクトル検索装置は、各座標毎に、特定の桁数の文字列が対応している近似値の集合である近似値集合が付随している近似値集合情報を持つ。
【００１６】
ここで、各座標毎の近似値集合とは、たとえば、０から０．０１の倍数だけ間隔の空いた数列
｛…，−０．０３，−０．０２，−０．０１，０．００，０．０１，０．０２，０．０３，…｝ …（１）
や、０から０．０５の倍数だけ間隔の空いた数列
｛…，−０．１５，−０．１０，−０．０５，０．００，０．０５，０．１０，０．１５，…｝ …（２）
が挙げられる。
【００１７】
各近似値には、座標毎に定まる桁数の文字列が対応し、異なる近似値には異なる文字列が対応するようにする。たとえば、数列（１）、（２）の近似値には、プラスマイナスの符号と小数点以下第一位と第二位を並べた３桁の文字列とする。これにより、数列（１）、（２）中の各近似値に対応する文字列の列は、それぞれ（１）’、（２）’のようになる。
｛…，−０３，−０２，−０１，＋００，＋０１，＋０２，＋０３，…｝ …（１）’
｛…，−１５，−１０，−０５，＋００，＋０５，＋１０，＋１５，…｝ …（２）’
もちろん、全ての座標について、同じ近似値集合をとってもよい。
【００１８】
この近似値集合情報は、それに関して定義した情報を、ファイルやメモリ、プログラムのコード中等に保持しているものとする。
【００１９】
検索対象文字列生成手段１１は、検索対象ベクトルを入力とし、上記検索対象ベクトルの各座標の値に対し、上記座標に対応する上記近似値集合における最も差の小さい近似値を求め、上記近似値の対応する文字列を、全座標にわたって連結することにより、上記検索対象ベクトルに対応する文字列である検索対象文字列を生成し、上記検索対象文字列をキーとして、対応する上記検索対象ベクトルとともに検索インデックス１５に格納する。
【００２０】
以下では、いずれの座標も、近似値とその対応文字列として（１）、（１）’をとっているものとして説明をする。
【００２１】
検索対象となるベクトルは、一定次元数の、各座標値が一般に実数のベクトルである。検索対象ベクトルは、一般に複数個ある。図２のｖ１〜ｖ６は、３次元の検索対象ベクトルの例である。
【００２２】
各検索対象ベクトルに対し、以下の処理を行う。
【００２３】
上記検索対象ベクトルの各座標の値に対し、上記座標に対応する上記近似値集合における最も差の小さい近似値を求める。たとえば、ｖ１については、座標１は０．５２３４…なので、最も差の小さい近似値は０．５２となる。このようにして、ｖ１から導出される各座標値が近似値のベクトルは、
（０．５２，−０．４０，０．８１） …（３）
となる。
【００２４】
次に、導出した各近似値の対応する文字列を、全座標にわたって連結する。（３）からは、
＋５２−４０＋８１ …（４）
という文字列が得られる。このようにして得られた文字列を上記検索対象ベクトルに対応する検索対象文字列とする。
【００２５】
各座標毎に、対応する文字列の桁数は定まっているので、各座標が、連結された文字列の何桁目から何桁目までに相当するかは一意に定まる。したがって、連結された文字列に対して、元の近似値ベクトルも一意に定まる。したがって、導出した連結文字列が同一である検索対象ベクトルや検索キーベクトルは、同一の近似値ベクトルを導出し、互いに近い関係にある。
【００２６】
検索対象文字列をキーとして、対応する検索対象ベクトルとともに検索インデックス１５に格納する。検索インデックスのキーは、たとえば、ハッシュとして実装する。この例では、（４）を検索キーとして、それに対応する検索対象ベクトルとしてｖ１を対応付ける。
【００２７】
複数の検索対象ベクトルから同一の検索対象文字列が生成された場合は、上記検索対象文字列に、生成源となった検索対象ベクトルの全てを対応付ける。図３は、図２の検索対象ベクトルをもとに生成された検索インデックスである。ｖ１、ｖ３、ｖ５から（４）が生成されたので、（４）には、ｖ１、ｖ３、ｖ５が対応付けられている。
【００２８】
検索キー文字列生成手段１２は、検索キーベクトルを入力とし、上記検索キーベクトルの各座標の値に対し、上記座標に対応する上記近似値集合における最も差の小さい近似値を求め、上記近似値の対応する文字列を、全座標にわたって連結することにより、上記検索キーベクトルに対応する文字列である検索キー文字列を生成する。
【００２９】
検索キーとなるベクトルは、検索対象ベクトルと同一次元数の、各座標値が一般に実数のベクトルである。図４のｑは、検索キーベクトルの例である。
【００３０】
検索キー文字列生成手段１２の処理は、検索対象文字列生成手段１１における文字列生成と同じである。図４のｑから導出される各座標値が近似値のベクトルは（３）となり、（３）から検索キー文字列として（４）が得られる。
【００３１】
検索キー文字列生成手段１２をなくし、検索キー文字列生成手段１２の処理を、検索対象文字列生成手段１１における文字列生成処理で行うという構成にすることも可能である。
【００３２】
文字列照合手段１３は、上記検索キー文字列と、上記検索インデックス１５中の検索対象文字列とを文字列照合し、一致する検索対象文字列に対応付けられている検索対象ベクトルの集合を取得する。
【００３３】
検索キー文字列としての（４）は、検索インデックス中の検索対象文字列の（４）と一致するので、対応する検索対象ベクトルｖ１、ｖ３、ｖ５が得られる。
【００３４】
関連度算出手段１４は、上記検索キーベクトルと、上記文字列照合手段１３で取得した検索対象ベクトルの集合の中の各検索対象ベクトルとの関連度を計算する。この関連度を利用して、ある閾値以上の関連度を持つ検索対象ベクトルを表示したり、関連度の大きい順に検索対象ベクトルをランキング表示したりすることも可能である。
【００３５】
図４のｑと、取得した検索対象ベクトルｖ１、ｖ３、ｖ５それぞれとの関連度を、たとえば、両ベクトル間のユークリッド距離として算出する。図５は、距離の小さい順に、検索対象ベクトルを対応する距離値とともに表示したものである。
【００３６】
つまり、上記実施例は、各座標毎に、特定の桁数の文字列が対応している近似値の集合である近似値集合が付随している近似値集合情報と、検索対象ベクトルを入力とし、上記検索対象ベクトルの各座標の値に対し、上記座標に対応する上記近似値集合における最も差の小さい近似値を求め、上記近似値の対応する文字列を、全座標にわたって連結することにより、上記検索対象ベクトルに対応する文字列である検索対象文字列を生成し、上記検索対象文字列をキーとして、対応する上記検索対象ベクトルとともに検索インデックスに格納する検索対象文字列生成手段とを有することを特徴とするベクトル検索装置の例である。
【００３７】
この場合、検索キーベクトルを入力とし、上記検索キーベクトルの各座標の値に対し、上記座標に対応する上記近似値集合における最も差の小さい近似値を求め、上記近似値の対応する文字列を、全座標にわたって連結することにより、上記検索キーベクトルに対応する文字列である検索キー文字列を生成する検索キー文字列生成手段と、上記検索キー文字列と、上記検索インデックス中の検索対象文字列とを文字列照合し、一致する検索対象文字列に対応付けられている検索対象ベクトルの集合を取得する文字列照合手段とを有する。
【００３８】
また、上記検索対象文字列生成手段が、検索キーベクトルを入力とし、上記検索キーベクトルの各座標の値に対し、上記座標に対応する上記近似値集合における最も差の小さい近似値を求め、上記近似値の対応する文字列を、全座標にわたって連結することにより、上記検索キーベクトルに対応する文字列である検索キー文字列を生成し、上記検索キー文字列と、上記検索インデックス中の検索対象文字列とを文字列照合し、一致する検索対象文字列に対応付けられている検索対象ベクトルの集合を取得する文字列照合手段を有する。
【００３９】
さらに、上記検索キーベクトルと、上記文字列照合手段で取得した検索対象ベクトルの集合の中の各検索対象ベクトルとの関連度を計算する関連度算出手段を有する。
【００４０】
また、上記実施例を方法の発明として把握することができる。つまり、上記実施例は、各座標毎に、特定の桁数の文字列が対応している近似値の集合である近似値集合が付随している近似値集合情報と、検索対象文字列生成手段が、検索対象ベクトルを入力とし、上記検索対象ベクトルの各座標の値に対し、上記座標に対応する上記近似値集合における最も差の小さい近似値を求め、上記近似値の対応する文字列を、全座標にわたって連結することにより、上記検索対象ベクトルに対応する文字列である検索対象文字列を生成し、上記検索対象文字列をキーとして、対応する上記検索対象ベクトルとともに検索インデックスに格納する検索対象文字列生成工程とを有することを特徴とするベクトル検索方法の例である。
【００４１】
この場合、検索キー文字列生成手段が、検索キーベクトルを入力とし、上記検索キーベクトルの各座標の値に対し、上記座標に対応する上記近似値集合における最も差の小さい近似値を求め、上記近似値の対応する文字列を、全座標にわたって連結することにより、上記検索キーベクトルに対応する文字列である検索キー文字列を生成し、記憶装置に記憶する検索キー文字列生成工程と、文字列照合手段が、上記検索キー文字列と、上記検索インデックス中の検索対象文字列とを文字列照合し、一致する検索対象文字列に対応付けられている検索対象ベクトルの集合を取得し、記憶装置に記憶する文字列照合工程とを有する。
【００４２】
また、上記検索対象文字列生成手段が、検索キーベクトルを入力とし、上記検索キーベクトルの各座標の値に対し、上記座標に対応する上記近似値集合における最も差の小さい近似値を求め、上記近似値の対応する文字列を、全座標にわたって連結することにより、上記検索キーベクトルに対応する文字列である検索キー文字列を生成し、記憶装置に記憶し、文字列照合手段が、上記検索キー文字列と、上記検索インデックス中の検索対象文字列とを文字列照合し、一致する検索対象文字列に対応付けられている検索対象ベクトルの集合を取得し、記憶装置に記憶する文字列照合工程を有する。
【００４３】
さらに、上記検索キーベクトルと、上記文字列照合手段で取得した検索対象ベクトルの集合の中の各検索対象ベクトルとの関連度を、関連度算出手段が計算し、記憶装置に記憶する関連度算出工程を有する。
【００４４】
また、上記ベクトル検索装置を構成する上記各手段としてコンピュータを機能させるプログラムを想定することができる。この場合、上記の実施の形態における処理をプログラムとして構築し、上記プログラムを通信回線または記憶媒体からインストールし、ＣＰＵ等の手段で実施することが可能である。
【００４５】
しかも、上記プログラムをコンピュータ読取可能な記録媒体に記録するようにしてもよい。この場合、ＣＤ、ＤＶＤ、ハードディスク、光ディスク、光磁気ディスク、半導体メモリ等の記録媒体に記録するようにしてもよい。
【００４６】
また、本発明は、上記実施の形態に限定されることなく、特許請求の範囲内において種々変更・応答が可能である。
【産業上の利用可能性】
【００４７】
本発明は、ベクトルを使用する文書検索技術や画像検索技術に適用可能である。
【図面の簡単な説明】
【００４８】
【図１】本発明の実施例におけるベクトル検索装置１００の構成例を示す。
【図２】３次元の検索対象ベクトルの例を示す図である。
【図３】図２の検索対象ベクトルをもとに生成された検索インデックス１５の例を示す図である。
【図４】検索キーベクトルの例を示す図である。
【図５】距離の小さい順に、検索対象ベクトルを対応する距離値とともに表示したものである。
【符号の説明】
【００４９】
１００…ベクトル検索装置、
１１…検索対象文字列生成手段、
１２…検索キー文字列生成手段、
１３…文字列照合手段、
１４…関連度算出手段、
１５…検索インデックス。
【特許請求の範囲】
【請求項１】
各座標毎に、特定の桁数の文字列が対応している近似値の集合である近似値集合が付随している近似値集合情報と、
検索対象ベクトルを入力とし、上記検索対象ベクトルの各座標の値に対し、上記座標に対応する上記近似値集合における最も差の小さい近似値を求め、上記近似値の対応する文字列を、全座標にわたって連結することにより、上記検索対象ベクトルに対応する文字列である検索対象文字列を生成し、上記検索対象文字列をキーとして、対応する上記検索対象ベクトルとともに検索インデックスに格納する検索対象文字列生成手段とを有することを特徴とするベクトル検索装置。
【請求項２】
請求項１において、
検索キーベクトルを入力とし、上記検索キーベクトルの各座標の値に対し、上記座標に対応する上記近似値集合における最も差の小さい近似値を求め、上記近似値の対応する文字列を、全座標にわたって連結することにより、上記検索キーベクトルに対応する文字列である検索キー文字列を生成する検索キー文字列生成手段と、
上記検索キー文字列と、上記検索インデックス中の検索対象文字列とを文字列照合し、一致する検索対象文字列に対応付けられている検索対象ベクトルの集合を取得する文字列照合手段とを有することを特徴とするベクトル検索装置。
【請求項３】
請求項１において、
上記検索対象文字列生成手段が、検索キーベクトルを入力とし、上記検索キーベクトルの各座標の値に対し、上記座標に対応する上記近似値集合における最も差の小さい近似値を求め、上記近似値の対応する文字列を、全座標にわたって連結することにより、上記検索キーベクトルに対応する文字列である検索キー文字列を生成し、
上記検索キー文字列と、上記検索インデックス中の検索対象文字列とを文字列照合し、一致する検索対象文字列に対応付けられている検索対象ベクトルの集合を取得する文字列照合手段を有することを特徴とするベクトル検索装置。
【請求項４】
請求項２または請求項３において、
上記検索キーベクトルと、上記文字列照合手段で取得した検索対象ベクトルの集合の中の各検索対象ベクトルとの関連度を計算する関連度算出手段を有することを特徴とするベクトル検索装置。
【請求項５】
各座標毎に、特定の桁数の文字列が対応している近似値の集合である近似値集合が付随している近似値集合情報と、
検索対象文字列生成手段が、検索対象ベクトルを入力とし、上記検索対象ベクトルの各座標の値に対し、上記座標に対応する上記近似値集合における最も差の小さい近似値を求め、上記近似値の対応する文字列を、全座標にわたって連結することにより、上記検索対象ベクトルに対応する文字列である検索対象文字列を生成し、上記検索対象文字列をキーとして、対応する上記検索対象ベクトルとともに検索インデックスに格納する検索対象文字列生成工程とを有することを特徴とするベクトル検索方法。
【請求項６】
請求項５において、
検索キー文字列生成手段が、検索キーベクトルを入力とし、上記検索キーベクトルの各座標の値に対し、上記座標に対応する上記近似値集合における最も差の小さい近似値を求め、上記近似値の対応する文字列を、全座標にわたって連結することにより、上記検索キーベクトルに対応する文字列である検索キー文字列を生成し、記憶装置に記憶する検索キー文字列生成工程と、
文字列照合手段が、上記検索キー文字列と、上記検索インデックス中の検索対象文字列とを文字列照合し、一致する検索対象文字列に対応付けられている検索対象ベクトルの集合を取得し、記憶装置に記憶する文字列照合工程とを有することを特徴とするベクトル検索方法。
【請求項７】
請求項５において、
上記検索対象文字列生成手段が、検索キーベクトルを入力とし、上記検索キーベクトルの各座標の値に対し、上記座標に対応する上記近似値集合における最も差の小さい近似値を求め、上記近似値の対応する文字列を、全座標にわたって連結することにより、上記検索キーベクトルに対応する文字列である検索キー文字列を生成し、記憶装置に記憶し、
文字列照合手段が、上記検索キー文字列と、上記検索インデックス中の検索対象文字列とを文字列照合し、一致する検索対象文字列に対応付けられている検索対象ベクトルの集合を取得し、記憶装置に記憶する文字列照合工程を有することを特徴とするベクトル検索方法。
【請求項８】
請求項６または請求項７において、
上記検索キーベクトルと、上記文字列照合手段で取得した検索対象ベクトルの集合の中の各検索対象ベクトルとの関連度を、関連度算出手段が計算し、記憶装置に記憶する関連度算出工程を有することを特徴とするベクトル検索方法。
【請求項９】
請求項１〜請求項４のいずれか１項に記載のベクトル検索装置を構成する各手段としてコンピュータを機能させるプログラム。
【請求項１０】
請求項９記載のプログラムを記録したコンピュータ読取可能な記録媒体。
【請求項１】
各座標毎に、特定の桁数の文字列が対応している近似値の集合である近似値集合が付随している近似値集合情報と、
検索対象ベクトルを入力とし、上記検索対象ベクトルの各座標の値に対し、上記座標に対応する上記近似値集合における最も差の小さい近似値を求め、上記近似値の対応する文字列を、全座標にわたって連結することにより、上記検索対象ベクトルに対応する文字列である検索対象文字列を生成し、上記検索対象文字列をキーとして、対応する上記検索対象ベクトルとともに検索インデックスに格納する検索対象文字列生成手段とを有することを特徴とするベクトル検索装置。
【請求項２】
請求項１において、
検索キーベクトルを入力とし、上記検索キーベクトルの各座標の値に対し、上記座標に対応する上記近似値集合における最も差の小さい近似値を求め、上記近似値の対応する文字列を、全座標にわたって連結することにより、上記検索キーベクトルに対応する文字列である検索キー文字列を生成する検索キー文字列生成手段と、
上記検索キー文字列と、上記検索インデックス中の検索対象文字列とを文字列照合し、一致する検索対象文字列に対応付けられている検索対象ベクトルの集合を取得する文字列照合手段とを有することを特徴とするベクトル検索装置。
【請求項３】
請求項１において、
上記検索対象文字列生成手段が、検索キーベクトルを入力とし、上記検索キーベクトルの各座標の値に対し、上記座標に対応する上記近似値集合における最も差の小さい近似値を求め、上記近似値の対応する文字列を、全座標にわたって連結することにより、上記検索キーベクトルに対応する文字列である検索キー文字列を生成し、
上記検索キー文字列と、上記検索インデックス中の検索対象文字列とを文字列照合し、一致する検索対象文字列に対応付けられている検索対象ベクトルの集合を取得する文字列照合手段を有することを特徴とするベクトル検索装置。
【請求項４】
請求項２または請求項３において、
上記検索キーベクトルと、上記文字列照合手段で取得した検索対象ベクトルの集合の中の各検索対象ベクトルとの関連度を計算する関連度算出手段を有することを特徴とするベクトル検索装置。
【請求項５】
各座標毎に、特定の桁数の文字列が対応している近似値の集合である近似値集合が付随している近似値集合情報と、
検索対象文字列生成手段が、検索対象ベクトルを入力とし、上記検索対象ベクトルの各座標の値に対し、上記座標に対応する上記近似値集合における最も差の小さい近似値を求め、上記近似値の対応する文字列を、全座標にわたって連結することにより、上記検索対象ベクトルに対応する文字列である検索対象文字列を生成し、上記検索対象文字列をキーとして、対応する上記検索対象ベクトルとともに検索インデックスに格納する検索対象文字列生成工程とを有することを特徴とするベクトル検索方法。
【請求項６】
請求項５において、
検索キー文字列生成手段が、検索キーベクトルを入力とし、上記検索キーベクトルの各座標の値に対し、上記座標に対応する上記近似値集合における最も差の小さい近似値を求め、上記近似値の対応する文字列を、全座標にわたって連結することにより、上記検索キーベクトルに対応する文字列である検索キー文字列を生成し、記憶装置に記憶する検索キー文字列生成工程と、
文字列照合手段が、上記検索キー文字列と、上記検索インデックス中の検索対象文字列とを文字列照合し、一致する検索対象文字列に対応付けられている検索対象ベクトルの集合を取得し、記憶装置に記憶する文字列照合工程とを有することを特徴とするベクトル検索方法。
【請求項７】
請求項５において、
上記検索対象文字列生成手段が、検索キーベクトルを入力とし、上記検索キーベクトルの各座標の値に対し、上記座標に対応する上記近似値集合における最も差の小さい近似値を求め、上記近似値の対応する文字列を、全座標にわたって連結することにより、上記検索キーベクトルに対応する文字列である検索キー文字列を生成し、記憶装置に記憶し、
文字列照合手段が、上記検索キー文字列と、上記検索インデックス中の検索対象文字列とを文字列照合し、一致する検索対象文字列に対応付けられている検索対象ベクトルの集合を取得し、記憶装置に記憶する文字列照合工程を有することを特徴とするベクトル検索方法。
【請求項８】
請求項６または請求項７において、
上記検索キーベクトルと、上記文字列照合手段で取得した検索対象ベクトルの集合の中の各検索対象ベクトルとの関連度を、関連度算出手段が計算し、記憶装置に記憶する関連度算出工程を有することを特徴とするベクトル検索方法。
【請求項９】
請求項１〜請求項４のいずれか１項に記載のベクトル検索装置を構成する各手段としてコンピュータを機能させるプログラム。
【請求項１０】
請求項９記載のプログラムを記録したコンピュータ読取可能な記録媒体。
【図１】
【図２】
【図３】
【図４】
【図５】
【図２】
【図３】
【図４】
【図５】
【公開番号】特開２００９−１１６５９２（Ｐ２００９−１１６５９２Ａ）
【公開日】平成２１年５月２８日（２００９．５．２８）
【国際特許分類】
【出願番号】特願２００７−２８８６５２（Ｐ２００７−２８８６５２）
【出願日】平成１９年１１月６日（２００７．１１．６）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２１年５月２８日（２００９．５．２８）
【国際特許分類】
【出願日】平成１９年１１月６日（２００７．１１．６）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]