特許

J-GLOBAL ID：200903075037446578

検索装置

発明者： 湯川 高志
出願人/特許権者： 日本電信電話株式会社
代理人 (1件)： 伊東 忠彦
公報種別：公開公報
出願番号（国際出願番号）：特願平5-227408
公開番号（公開出願番号）：特開平7-085068
出願日： 1993年09月13日
公開日（公表日）： 1995年03月31日
要約：

【要約】【目的】 本発明の目的は、検索対象の要素数が多いときにも高速に検索を行う検索装置を提供することである。【構成】 本発明の検索装置は、複数の要素を格納する要素記憶部101と、二つの要素とパラメータから評価値を計算する評価値計算部102と、要素と事前評価値の組を事前評価値の大きい順に所定の個数だけ格納する事前評価値記憶部103と、上界値を計算する有界値計算部104と、上界値が最大評価値よりも小さい場合には、上界値に対応する事前評価値よりも小さい上記組の事前評価値記憶部103からの順次取り出しを打ち切り、評価値を最大とする要素を検索する検索動作を制御する検索制御部105とにより構成される。

請求項（抜粋）：

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