(57)【特許請求の範囲】
【請求項１】
属性名と属性値からなる属性情報を１つ以上含む登録情報を記憶する記憶手段と、
前記登録情報に含まれる属性情報の組み合わせを示す情報である組み合わせ選択情報を作成し、記憶する組み合わせ管理手段と、
前記属性名と前記属性値からなる前記属性情報を１つ以上含み、情報検索の対象である検索情報を取得する取得手段と、
前記組み合わせ選択情報を取得し、前記検索情報に基づいて前記組み合わせ選択情報に対応する組み合わせの新たな検索情報を生成する生成手段と、
前記新たな検索情報と一致する前記登録情報を前記記憶手段から検索する検索手段と、
を備えることを特徴とする情報検索システム。
【請求項２】
前記組み合わせ選択情報は、前記登録情報に含まれる属性情報の属性名の組み合わせを示す情報であって、
前記生成手段は、前記組み合わせ選択情報を取得し、前記検索情報の属性情報の中から、前記組み合わせ選択情報に含まれる属性名の組み合わせの新たな検索情報を生成することを特徴とする請求項１に記載の情報検索システム。
【請求項３】
前記登録情報および前記新たな検索情報に含まれる１つ以上の属性値を所定の条件に従って並べ替え、連結した連結属性値を作成する連結手段と、
前記連結属性値をハッシュ変換してハッシュ値を生成するハッシュ生成手段と、を備え、
前記記憶手段は、前記登録情報に対応する前記ハッシュ値をキーとし前記登録情報を値とするハッシュテーブルを記憶しており、
前記検索手段は、前記ハッシュテーブルから前記新たな検索情報に対応するハッシュ値と一致するキーを検索し、その値である登録情報を取得することを特徴とする請求項１または２に記載の情報検索システム。
【請求項４】
前記登録情報および前記検索情報について、前記属性名および前記属性値の組を一意に識別する属性値に変換して、変換後登録情報および変換後検索情報を生成する変換手段をさらに備え、
前記記憶手段は、前記変換後登録情報を記憶し、
前記生成手段は、前記変換後検索情報に基づいて前記新たな検索情報を生成し、
前記検索手段は、前記新たな検索情報と一致する前記変換後登録情報を前記記憶手段から検索することを特徴とする請求項１ないし３のいずれか１項に記載の情報検索システム。
【請求項５】
前記変換手段は、前記属性値を属性名と属性値を連結した文字列に変換することを特徴とする請求項４に記載の情報検索システム。
【請求項６】
前記変換手段は、前記属性値を属性値に識別文字列を付与した文字列に変換することを特徴とする請求項４に記載の情報検索システム。
【請求項７】
情報検索システムが実行する情報検索方法であって、
属性名と属性値からなる属性情報を１つ以上含む登録情報に含まれる属性情報の組み合わせを示す情報である組み合わせ選択情報を作成し、記憶する組み合わせ管理ステップと、
前記属性名と前記属性値からなる前記属性情報を１つ以上含み、情報検索の対象である検索情報を取得する取得ステップと、
前記組み合わせ選択情報を取得し、前記検索情報に基づいて前記組み合わせ選択情報に対応する組み合わせの新たな検索情報を生成する生成ステップと、
前記登録情報を記憶する記憶手段から、前記新たな検索情報と一致する前記登録情報を検索する検索ステップと、
を備えることを特徴とする情報検索方法。
【請求項８】
前記組み合わせ選択情報は、前記登録情報に含まれる属性情報の属性名の組み合わせを示す情報であって、
前記生成ステップでは、前記組み合わせ選択情報を取得し、前記検索情報の属性情報の中から、前記組み合わせ選択情報に含まれる属性名の組み合わせの新たな検索情報を生成することを特徴とする請求項７に記載の情報検索方法。
【請求項９】
前記登録情報および前記新たな検索情報に含まれる１つ以上の属性値を所定の条件に従って並べ替え、連結した連結属性値を作成する連結ステップと、
前記連結属性値をハッシュ変換してハッシュ値を生成するハッシュ生成ステップと、を備え、
前記検索ステップでは、前記記憶手段が記憶する前記登録情報に対応する前記ハッシュ値をキーとし前記登録情報を値とするハッシュテーブルから、前記新たな検索情報に対応するハッシュ値と一致するキーを検索し、その値である登録情報を取得することを特徴とする請求項７または８に記載の情報検索方法。
【請求項１０】
コンピュータを、
属性名と属性値からなる属性情報を１つ以上含む登録情報を記憶する記憶手段、
前記登録情報に含まれる属性情報の組み合わせを示す情報である組み合わせ選択情報を作成し、記憶する組み合わせ管理手段、
前記属性名と前記属性値からなる前記属性情報を１つ以上含み、情報検索の対象である検索情報を取得する取得手段、
前記組み合わせ選択情報を取得し、前記検索情報に基づいて前記組み合わせ選択情報に対応する組み合わせの新たな検索情報を生成する生成手段、
前記新たな検索情報と一致する前記登録情報を前記記憶手段から検索する検索手段、
として機能させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報検索システム、情報検索方法およびプログラムに関する。
【背景技術】
【０００２】
ワイルドカードを含んだ登録情報の登録と、検索情報にマッチする登録情報の検索が可能なハッシュテーブルを用いた検索システムの一例が非特許文献１に記載されている。非特許文献１の検索システムにおける登録情報であるグルーピング条件および評価対象情報であるコンテキストは、属性名と属性値の組からなる属性情報を複数含んだ情報である。ワイルドカードを含んだ登録情報とは、システムで扱う属性名をすべては含んでいない登録情報である。たとえば、システムで扱う属性名が「場所」、「年齢」、「性別」の３種類であったとき、「(性別、男)」や「(場所、東京)、(年齢、２０)」のように３種類すべては含んでいない登録情報のことを、ワイルドカードを含んだ登録情報と呼ぶ。このワイルドカードを含んだ登録情報に対しては、登録情報に含まれるすべての属性情報が、評価対象情報（本発明では検索情報という）と一致すればマッチしたと判断される。たとえば、「(性別、男)」という登録情報に対しては、「(性別、男)」、「(性別、男)、(場所、東京)」、「(性別、男)、(場所、東京)、(年齢、３０)」のように(性別、男)を含む評価対象情報であれば何れもマッチする。
【０００３】
非特許文献１の検索システムの情報登録フローでは、登録情報に含まれるすべての属性値を決められた順番で連結し、連続属性値を得る。属性値のうち値がワイルドカードのものについては連結を行わない。そして、連結した連結属性値をキーとし、登録情報を含む情報を値とするエントリをハッシュテーブルに登録する。非特許文献１の検索システムの評価動作フローでは、まず評価対象情報に含まれるすべての属性値を要素とする集合のべき集合を作成し、べき集合の要素となる集合の各要素を決められた順番で連結し、複数の連結属性値を得る。たとえば、「(性別、Ｍ)、(年齢、２０)」という評価対象情報に含まれる「Ｍ」、「２０」という属性値を要素とする集合「Ｍ、２０」のべき集合Ｐ「Ｍ、２０」=｛「Ｍ」、「２０」、「Ｍ、２０」｝を作成し、べき集合の要素となる集合「Ｍ」、「２０」、「Ｍ、２０」の各要素を決められた順番で連結し、「Ｍ」、「２０」、「２０Ｍ」という連結属性値を得る。そして、連結した連結属性値をキーとするエントリをハッシュテーブルから取得することによりワイルドカードを含んだ登録情報の検索を実現している。ワイルドカードを含んだ登録情報の検索が実現できるのは、複数の連結属性値が評価対象情報にマッチするすべてのエントリのキーとなっているためである。
【０００４】
特許文献１には、従来技術で処理すると途中で対象の数が増加し処理しきれないようなデータも高速に処理する事が可能なデータ解析方式が開示されている。特許文献１のデータ解析方式は、条件にあうすべての組み合わせの中から、キャッシュアルゴリズムを利用して処理対象を選択することで処理の高速化を図るものである。
【０００５】
特許文献２には、膨大なデータリストの中から所望のデータを抽出する検索処理の高速化を実現する検索装置が開示されている。特許文献２の検索装置は、検索キーのハッシュ値を算出し、インデックス領域における当該ハッシュ値に対応する場所を参照して原データの格納場所を示す情報を抽出し、次いで前記原データ領域におけるその情報で示される場所を参照して所要の原データを抽出することにより、複数のデータファイルに対してファイル操作及び入出力を行わずに済むことから、検索の一層の効率化、高速化が図られる。
【０００６】
特許文献３には、絞り込みに対して有効度の高い特徴項目を検索者に報知することで、効率的な検索を可能とする検索システムが開示されている。特許文献３の検索システムは、複数の検索キーを要素とするべき集合を作成し、検索によって絞り込まれる要素数のバラツキの程度を算出して、絞り込みに対する有効度の評価結果を検索者に報知することで検索の効率化を測るものである。
【０００７】
特許文献４には、ディレクトリ情報ベースに対する検索速度を向上させる情報処理装置が開示されている。特許文献４の情報処理装置は、エントリを検索するために相対識別名（ＲＤＮ）の比較を行なうときに、属性値の比較で一致したものだけに属性型を比較することで、属性型から比較する場合より、全体の比較回数を減らすことができ、検索速度を向上させることができる。また、属性値に固定長のハッシュ値をもたせることで、ハッシュ値を持たせない場合よりも全体としての検索速度を向上させることができる。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２００５−２８５０４８号公報
【特許文献２】特開２００７−２４１３７８号公報
【特許文献３】特開２００９−２０５７８号公報
【特許文献４】特開平７−２３４８７９号公報
【非特許文献】
【０００９】
【非特許文献１】山崎健太郎ほか、「コンテキストのべき集合を用いた高速な動的グルーピング」、電子情報通信学会2009年ソサエティ大会講演論文集、B-7-15
【発明の概要】
【発明が解決しようとする課題】
【００１０】
非特許文献１の検索システムでは、評価対象情報に含まれるすべての属性値を要素とする集合のべき集合を作成し、べき集合の要素となる集合の各要素を決められた順番で連結することで検索キーとなる連結属性値を得ている。べき集合の要素数は属性情報数ｎに対して２ｎ−１となる。これは評価フローの計算量が属性情報数に対して指数オーダーとなることを意味している。そのため、属性情報数ｎが多い場合には検索キーの数が増大し、処理時間が大幅に増加してしまうことがある。
【００１１】
特許文献１および３に記載の技術は、検索キーに含まれる複数の要素のべき集合を生成しないことで検索処理の高速化を図るものではない。
【００１２】
特許文献２および４に記載の技術は、ワイルドカードを含んだ登録情報の検索をするものではない。
【００１３】
本発明は、上述のような事情に鑑みてなされたもので、検索対象に含まれる要素の数が増加した場合にも、処理時間の増加を防いで短時間での処理を実現する情報検索システム、情報検索方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１４】
本発明の第１の観点に係る情報検索システムは、
属性名と属性値からなる属性情報を１つ以上含む登録情報を記憶する記憶手段と、
前記登録情報に含まれる属性情報の組み合わせを示す情報である組み合わせ選択情報を作成し、記憶する組み合わせ管理手段と、
前記属性名と前記属性値からなる前記属性情報を１つ以上含み、情報検索の対象である検索情報を取得する取得手段と、
前記組み合わせ選択情報を取得し、前記検索情報に基づいて前記組み合わせ選択情報に対応する組み合わせの新たな検索情報を生成する生成手段と、
前記新たな検索情報と一致する前記登録情報を前記記憶手段から検索する検索手段と、
を備えることを特徴とする。
【００１５】
本発明の第２の観点に係る情報検索方法は、
情報検索システムが実行する情報検索方法であって、
属性名と属性値からなる属性情報を１つ以上含む登録情報に含まれる属性情報の組み合わせを示す情報である組み合わせ選択情報を作成し、記憶する組み合わせ管理ステップと、
前記属性名と前記属性値からなる前記属性情報を１つ以上含み、情報検索の対象である検索情報を取得する取得ステップと、
前記組み合わせ選択情報を取得し、前記検索情報に基づいて前記組み合わせ選択情報に対応する組み合わせの新たな検索情報を生成する生成ステップと、
前記登録情報を記憶する記憶手段から、前記新たな検索情報と一致する前記登録情報を検索する検索ステップと、
を備えることを特徴とする。
【００１６】
本発明の第３の観点に係るプログラムは、コンピュータを、
属性名と属性値からなる属性情報を１つ以上含む登録情報を記憶する記憶手段、
前記登録情報に含まれる属性情報の組み合わせを示す情報である組み合わせ選択情報を作成し、記憶する組み合わせ管理手段、
前記属性名と前記属性値からなる前記属性情報を１つ以上含み、情報検索の対象である検索情報を取得する取得手段、
前記組み合わせ選択情報を取得し、前記検索情報に基づいて前記組み合わせ選択情報に対応する組み合わせの新たな検索情報を生成する生成手段、
前記新たな検索情報と一致する前記登録情報を前記記憶手段から検索する検索手段、
として機能させることを特徴とする。
【発明の効果】
【００１７】
本発明の情報検索システム、情報検索方法およびプログラムによれば、検索対象に含まれる要素の数が増加した場合でも処理時間の増加を防ぐことができ、要素のべき集合や部分集合を生成して検索する方法よりも短時間での処理を実現することができる。
【図面の簡単な説明】
【００１８】
【図１】本発明の実施の形態１に係る情報検索システムの構成例を示すブロック図である。
【図２】実施の形態１における登録情報に対応するハッシュ値の生成の例を示す図である。
【図３】実施の形態１における検索情報に対応するハッシュ値の生成の例を示す図である。
【図４】実施の形態１に係る情報登録の動作の一例を示すフローチャートである。
【図５】実施の形態１に係る情報検索の動作の一例を示すフローチャートである。
【図６】実施の形態２に係る情報検索システムの構成例を示すブロック図である。
【図７】実施の形態２に係る情報登録の動作の一例を示すフローチャートである。
【図８】実施の形態２に係る情報検索の動作の一例を示すフローチャートである。
【図９】本発明の実施の形態に係る情報検索システムを構成する情報検索装置のハードウェア構成の一例を示すブロック図である。
【発明を実施するための形態】
【００１９】
本発明において、登録情報とは、属性名と属性値からなる属性情報を１つ以上含む情報であって、検索される対象を示す情報である。また、検索情報とは、属性名と属性値からなる属性情報を１つ以上含む情報であって、検索する対象を示す情報である。
【００２０】
以下、本発明を実施するための形態について図を参照して詳細に説明する。なお図中、同一または同等の部分には同一の符号を付す。
【００２１】
（実施の形態１）
図１は、本発明の実施の形態１に係る情報検索システムの構成例を示すブロック図である。情報検索システム１０１は、情報登録部１１、属性情報ソート連結部１２、ハッシュ生成部１３、登録情報管理部１４、検索情報処理部１５、組み合わせ生成部１６および組み合わせ管理部１７を備える。情報検索システム１０１は、前述の各部を備える情報検索装置のみで構成されることとしてもよいし、前述の各部を備える情報検索装置と、検索情報の入力を受け付けて情報検索装置に送信し、情報検索装置から検索結果を受信して出力する１つ以上のユーザ端末とで構成されることとしてもよい。後者の場合、ユーザ端末は情報検索装置の附属の装置であってもよいし、情報検索装置とネットワークで接続されることとしてもよい。
【００２２】
情報登録部１１は、登録情報を受信し、受信した登録情報に含まれる属性名を組み合わせ管理部１７に送信する。なお、属性情報の種類が年齢、性別、場所、・・・のＮ種類である場合でも、登録情報は必ずしもＮ種類すべての属性情報を含まなくてよい。たとえば、年齢、性別、場所の３種類の属性情報しか含まない登録情報でもよい。属性情報をＮ種類すべては含まない登録情報が受信されたとき、前述のワイルドカードを含んだ登録情報として取り扱う。また、情報登録部１１は、登録情報を属性情報ソート連結部１２に送信する。そして、情報登録部１１は、当該登録情報に対応するハッシュ値をハッシュ生成部１３から受信する。情報登録部１１は、登録情報と当該登録情報に対応するハッシュ値とを含む情報登録要求を生成し、登録情報管理部１４に送信する。
【００２３】
属性情報ソート連結部１２は、情報登録部１１から登録情報を受信し、組み合わせ生成部１６から新たな検索情報を受信する。属性情報ソート連結部１２は、登録情報および新たな検索情報の属性情報を、属性名に基づいて決められた順序にしたがって並び替え、属性値の連結を行う。属性情報ソート連結部１２は、連結した属性値である連結属性値をハッシュ生成部１３に送信する。なお、並び替えの順序は、属性名に対して定められたものでよいし属性名が英語で表記される場合はアルファベット順でもよい。また、属性名が日本語で表記される場合は五十音順でもよいし、属性名が数値で表記される場合は数値の昇順・降順でもよい。
【００２４】
ハッシュ生成部１３は、属性情報ソート連結部１２から登録情報に基づいて生成された連結属性値と、新たな検索情報に基づいて生成された連結属性値とを受信し、これらの連結属性値をハッシュ変換し、ハッシュ値を生成する。ハッシュ生成部１３は、登録情報に対応するハッシュ値を情報登録部１１に、新たな検索情報に対応するハッシュ値を検索情報処理部１５に送信する。なお、ハッシュ変換はＭＤ５やＳＨＡに代表されるような一般的なハッシュ関数を用いてよい。
【００２５】
登録情報管理部１４は、登録情報と当該登録情報に対応するハッシュ値とを含む情報登録要求を受信する。登録情報管理部１４は、ハッシュテーブルを記憶しており、受信した情報登録要求に含まれるハッシュ値をキーとし、登録情報を値とするエントリを作成し、ハッシュテーブルに登録する。なお、ハッシュテーブルへのエントリの登録を行う際に、すでに同一のハッシュ値をキーとして持つエントリが存在していたならば、登録情報を当該エントリの値に追加する。また、登録情報管理部１４は、検索情報に対応するハッシュ値を含む情報検索要求を受信する。登録情報管理部１４は、受信した情報検索要求に含まれるハッシュ値をキーとするエントリをハッシュテーブルより取得し、当該エントリまたは当該エントリの値である登録情報を検索結果として検索情報処理部１５に送信する。
【００２６】
検索情報処理部１５は、検索情報を受信する。また、検索情報処理部１５は、組み合わせ管理部１７に組み合わせ選択情報を要求し、取得する。なお、検索情報処理部１５は検索情報に含まれる属性名を含めて組み合わせ選択情報を要求してもよい。検索情報処理部１５は、組み合わせ生成部１６に、検索情報と組み合わせ管理部１７から取得した組み合わせ選択情報とを送信する。そして、検索情報処理部１５は、ハッシュ生成部１３から当該検索情報に対応するハッシュ値を受信する。さらに、検索情報処理部１５は、ハッシュ生成部１３から受信したハッシュ値を含む情報検索要求を登録情報管理部１４に送信し、検索結果を受信する。検索結果は、登録情報管理部１４に記憶されるハッシュテーブルのエントリのうち、情報検索要求に含まれるハッシュ値をキーとするエントリ、またはエントリの値である登録情報である。
【００２７】
組み合わせ生成部１６は、検索情報と生成すべき組み合わせを示した情報である組み合わせ選択情報を受信する。組み合わせ生成部１６は、受信した検索情報から属性情報を取得し、受信した組み合わせ選択情報が示す組み合わせの属性情報を含む新たな検索情報を生成し、属性情報ソート連結部１２へ送信する。
【００２８】
組み合わせ管理部１７は、情報登録部１１より登録情報に含まれる属性名を受信し、受信した属性名の組み合わせを組み合わせ選択情報として記憶する。ただし、組み合わせ管理部１７が作成した組み合わせ選択情報と同一の情報が既に記憶されている場合には当該組み合わせ選択情報の記憶は行わない。たとえば、組み合わせ管理部１７は、年齢および性別という属性名を受信した場合、「(年齢)、(性別)」という組み合わせ選択情報を生成し、記憶する。この後さらに、年齢および性別という属性名を受信した場合、組み合わせ選択情報「(年齢)、(性別)」が生成されるが、すでに同一の情報が記憶されているので、前記組み合わせ選択情報の記憶は行わない。また、組み合わせ管理部１７は、検索情報処理部１５からの要求に応じて、記憶している組み合わせ選択情報を呼び出して検索情報処理部１５に返す。このとき、組み合わせ管理部１７は、検索情報処理部１５からの要求に対し、記憶する組み合わせ選択情報をすべて検索情報処理部１５に送信する。なお、検索情報処理部１５からの要求に属性名が含まれる場合は、組み合わせ管理部１７は当該属性名を含む組み合わせ選択情報のみを検索情報処理部１５に送信する。
【００２９】
図２は、本発明の実施の形態１における登録情報に対応するハッシュ値の生成の例を示す図である。図２（ａ）は登録情報の例である。登録情報は属性名と属性値からなる属性情報を１つ以上含む。図２（ａ）の例では、登録情報は、「属性名：性別、属性値：Ｍ」の属性情報と、「属性名：年齢、属性値：２０」の属性情報と、「属性名：場所、属性値：東京」の属性情報とを有する。
【００３０】
図２（ｂ）は組み合わせ選択情報の例である。組み合わせ管理部１７は、図２（ａ）に示す登録情報の属性名：性別、属性名：年齢、属性名：場所を受信すると、組み合わせ選択情報として（性別、年齢、場所）を記憶する。
【００３１】
図２（ｃ）は、連結属性値とそのハッシュ変換の例である。属性情報ソート連結部１２は、情報登録部１１から図２（ａ）に示す登録情報を受信すると、当該登録情報に含まれる属性情報「属性名：性別、属性値：Ｍ」、「属性名：年齢、属性値：２０」および「属性名：場所、属性値：東京」を抽出し、これを属性名に基づいてあらかじめ決められた順序にしたがって並び替え、属性情報に含まれる属性値を連結した連結属性値を生成する。図２（ｃ）の例では、属性名に基づいて五十音順にソートし、属性値を連結しており、連結属性値は「Ｍ２０東京」となる。ハッシュ生成部１３は、連結属性値「Ｍ２０東京」をハッシュ変換し、ハッシュ値1dd20cb93584263cf087ed20f6fed68bを生成する。
【００３２】
図３は、本発明の実施の形態１における検索情報に対応するハッシュ値の生成の例を示す図である。図３（ａ）は検索情報の例である。検索情報は、属性名と属性値からなる属性情報を１つ以上含む。図３（ａ）の例では、検索情報は、「属性名：年齢、属性値：２０」の属性情報と、「属性名：性別、属性値：Ｆ」の属性情報と、「属性名：場所、属性値：東京」とを有する。
【００３３】
図３（ｂ）は新たな検索情報およびそれに対応する連結属性値の例である。組み合わせ生成部１６は、検索情報処理部１５から図３に示す検索情報と、(年齢、性別)・(年齢)・(性別、場所)という組み合わせ選択情報とを受信したとすると、組み合わせ選択情報 (年齢、性別)に対して「(年齢、２０)、(性別、Ｆ)」、(年齢)に対して「(年齢、２０)」、(性別、場所)に対して「(性別、Ｆ)、(場所、東京)」という新たな検索情報を作成する。属性情報ソート連結部１２は、組み合わせ生成部１６から新たな検索情報を受信すると、当該新たな検索情報に含まれるそれぞれの属性情報を属性名に基づいてあらかじめ決められた順序にしたがって並び替え、属性情報に含まれる属性値を連結した連結属性値を生成する。図３（ｂ）の例では、属性名に基づいて五十音順にソートし、属性値を連結しており、連結属性値はそれぞれ「Ｆ２０」、「２０」、「Ｆ東京」となる。
【００３４】
図３（ｃ）は、連結属性値とそのハッシュ変換の例である。ハッシュ生成部１３は、図３（ｂ）に示す連結属性値Ｆ「Ｆ２０」、「２０」、「Ｆ東京」をハッシュ変換し、それぞれハッシュ値fc335adb3d69d3d8270769e1923ea4dc、98f13708210194c475687be6106a3b84、d1fcc8d97797635e8a3462f21fdb6862を生成する。
【００３５】
図４は、実施の形態１に係る情報登録の動作の一例を示すフローチャートである。まず、情報登録部１１は登録情報を受信する（ステップＳ１１）。情報登録部１１は、受信した登録情報に含まれる属性名を組み合わせ管理部１７に送信し、登録情報を属性情報ソート連結部１２に送信する。組み合わせ管理部１７は、受信した１つ以上の属性名を組にした組み合わせ選択情報を生成し（ステップＳ１２）、記憶する。
【００３６】
一方、属性情報ソート連結部１２は、受信した登録情報の属性情報を属性名に基づいて決められた順序にしたがって並び替え、属性情報に含まれる属性値を連結した連結属性値を生成する（ステップＳ１３）。属性情報ソート連結部１２は、生成した連結属性値をハッシュ生成部１３に送信する。
【００３７】
ハッシュ生成部１３は、受信した連結属性値をハッシュ変換し、ハッシュ値を生成する（ステップＳ１４）。ハッシュ生成部１３は、生成したハッシュ値を情報登録部１１に送信する。情報登録部１１は、受信したハッシュ値および登録情報登録要求を生成し（ステップＳ１５）、登録情報管理部１４に送信する。登録情報管理部１４は、受信した情報登録要求に含まれるハッシュ値をキーとし登録情報を値とするエントリを生成し、ハッシュテーブルに登録し（ステップＳ１６）、処理を終了する。
【００３８】
図５は、実施の形態１に係る情報検索の動作の一例を示すフローチャートである。まず、検索情報処理部１５は、検索情報を受信する（ステップＳ２１）。検索情報処理部１５は、組み合わせ管理部１７に組み合わせ選択情報を要求し、取得する（ステップＳ２２）。
【００３９】
検索情報処理部１５は、組み合わせ生成部１６に検索情報および組み合わせ選択情報を送信する。組み合わせ生成部１６は、受信した検索情報から属性情報を抽出し、抽出した属性情報に基づいて組み合わせ選択情報で示される属性名の組からなる新たな検索情報を生成する（ステップＳ２３）。組み合わせ生成部１６は、生成した新たな検索情報を属性情報ソート連結部１２へ送信する。属性情報ソート連結部１２は、受信した新たな検索情報の属性情報を属性名に基づいて決められた順序にしたがって並び替え、属性情報に含まれる属性値を連結した連結属性値を生成する（ステップＳ２４）。属性情報ソート連結部１２は、生成した連結属性値をハッシュ生成部１３に送信する。組み合わせ生成部１６は、次の検索情報があるか否かを判定する（ステップＳ２５）。次の検索情報がある場合（ステップＳ２５；ＹＥＳ）、ステップＳ２３に戻り、ステップＳ２３〜ステップＳ２５の処理を繰り返す。
【００４０】
一方、次の検索情報がない場合（ステップＳ２５；ＮＯ）、ハッシュ生成部１３は、受信した連結属性値をハッシュ変換し、ハッシュ値を生成する（ステップＳ２６）。ハッシュ生成部１３は、生成したハッシュ値を検索情報処理部１５に送信する。ハッシュ生成部１３は、次の連結属性値があるか否かを判定する（ステップＳ２７）。次の連結属性値がある場合（ステップＳ２７；ＹＥＳ）、ステップＳ２６に戻り、ステップＳ２６およびステップＳ２７の処理を繰り返す。
【００４１】
一方、次の連結属性値がない場合（ステップＳ２７；ＮＯ）、検索情報処理部１５は、受信したハッシュ値を含む情報検索要求生成し（ステップＳ２８）、登録情報管理部１４に送信する。登録情報管理部１４は、受信した情報検索要求に含まれるハッシュ値をキーとするエントリをハッシュテーブルから検索し（ステップＳ２９）、検索結果を検索情報処理部１５に送信する。登録情報管理部１４は、次のハッシュ値があるか否かを判定する（ステップＳ３０）。次の連結属性値がある場合（ステップＳ３０；ＹＥＳ）、ステップＳ２８に戻り、ステップＳ２８〜ステップＳ３０の処理を繰り返す。次の連結属性値がない場合（ステップＳ３０；ＮＯ）、処理を終了する。
【００４２】
以上説明したように、実施の形態１の情報検索システム１０１によれば、検索対象に含まれる要素の数が増加した場合でも処理時間の増加を防ぐことができ、要素のべき集合や部分集合を生成して検索する方法よりも短時間での処理を実現することができる。
【００４３】
（実施の形態２）
図６は、実施の形態２に係る情報検索システムの構成例を示すブロック図である。情報検索システム１０２は、実施の形態１に係る情報検索システム１０１に属性値変換部１８が追加されている。
【００４４】
実施の形態２では、属性値変換部１８は、情報登録部１１から登録情報を受信し、検索情報処理部１５から検索情報を受信する。属性値変換部１８は、受信した登録情報および検索情報に含まれる属性値を属性名と属性値の組毎に異なる値となるように変換し、変換後登録情報および変換後検索情報を生成する。属性値変換部１８は、変換後登録情報を情報登録部１１に、変換後検索情報を検索情報処理部１５に送信する。また、属性値変換部１８は、属性値をキーとして属性名を値とする属性値テーブルを記憶している。
【００４５】
情報登録部１１は、属性値変換部１８から受け取った変換後登録情報を属性情報ソート連結部１２に送信する。また、情報登録部１１は、変換後登録情報に含まれる属性名を組み合わせ管理部１７に送信する。検索情報処理部１５は、属性値変換部１８から受け取った変換後検索情報を組み合わせ生成部１６に送信する。各部のその他の働きは、実施の形態１と同様である。
【００４６】
図７は、実施の形態２に係る情報登録の動作の一例を示すフローチャートである。まず、情報登録部１１は登録情報を受信する（ステップＳ７１）。情報登録部１１は、受信した登録情報を属性値変換部１８に送信する。属性値変換部１８は、属性値変換処理を行い（ステップＳ７２）、変換後登録情報を情報登録部１１に送信する。情報登録部１１は、受信した変換後登録情報に含まれる属性名を組み合わせ管理部１７に送信し、変換後登録情報を属性情報ソート連結部１２に送信する。組み合わせ管理部１７は、受信した１つ以上の属性名を組にした組み合わせ選択情報を生成し（ステップＳ７３）、記憶する。
【００４７】
一方、属性情報ソート連結部１２は、受信した変換後登録情報の属性情報を属性名に基づいて決められた順序にしたがって並び替え、属性情報に含まれる属性値を連結した連結属性値を生成する（ステップＳ７４）。属性情報ソート連結部１２は、生成した連結属性値をハッシュ生成部１３に送信する。
【００４８】
ハッシュ生成部１３は、受信した連結属性値をハッシュ変換し、ハッシュ値を生成する（ステップＳ７５）。ハッシュ生成部１３は、生成したハッシュ値を情報登録部１１に送信する。情報登録部１１は、受信したハッシュ値および変換後登録情報登録要求を生成し（ステップＳ７６）、登録情報管理部１４に送信する。登録情報管理部１４は、受信した情報登録要求に含まれるハッシュ値をキーとし変換後登録情報を値とするエントリを生成し、ハッシュテーブルに登録し（ステップＳ７７）、処理を終了する。
【００４９】
図８は、実施の形態２に係る情報検索の動作の一例を示すフローチャートである。まず、検索情報処理部１５は、検索情報を受信する（ステップＳ８１）。検索情報処理部１５は、受信した検索情報を属性値変換部１８に送信する。属性値変換部１８は、属性値変換処理を行い（ステップＳ８２）、変換後検索情報を検索情報処理部１５に送信する。また、検索情報処理部１５は、組み合わせ管理部１７に組み合わせ選択情報を要求し、取得する（ステップＳ８３）。
【００５０】
検索情報処理部１５は、組み合わせ生成部１６に変換後検索情報および組み合わせ選択情報を送信する。組み合わせ生成部１６は、受信した変換後検索情報から属性情報を抽出し、抽出した属性情報に基づいて組み合わせ選択情報で示される属性名の組からなる新たな検索情報を生成する（ステップＳ８４）。組み合わせ生成部１６は、生成した新たな検索情報を属性情報ソート連結部１２へ送信する。属性情報ソート連結部１２は、受信した新たな検索情報の属性情報を属性名に基づいて決められた順序にしたがって並び替え、属性情報に含まれる属性値を連結した連結属性値を生成する（ステップＳ８５）。属性情報ソート連結部１２は、生成した連結属性値をハッシュ生成部１３に送信する。組み合わせ生成部１６は、次の変換後検索情報があるか否かを判定する（ステップＳ８６）。次の変換後検索情報がある場合（ステップＳ８６；ＹＥＳ）、ステップＳ８４に戻り、ステップＳ８４〜ステップＳ８６の処理を繰り返す。
【００５１】
一方、次の変換後検索情報がない場合（ステップＳ８６；ＮＯ）、ハッシュ生成部１３は、受信した連結属性値をハッシュ変換し、ハッシュ値を生成する（ステップＳ８７）。ハッシュ生成部１３は、生成したハッシュ値を検索情報処理部１５に送信する。ハッシュ生成部１３は、次の連結属性値があるか否かを判定する（ステップＳ８８）。次の連結属性値がある場合（ステップＳ８８；ＹＥＳ）、ステップＳ８７に戻り、ステップＳ８７およびステップＳ８８の処理を繰り返す。
【００５２】
一方、次の連結属性値がない場合（ステップＳ８８；ＮＯ）、検索情報処理部１５は、受信したハッシュ値を含む情報検索要求生成し（ステップＳ８９）、登録情報管理部１４に送信する。登録情報管理部１４は、受信した情報検索要求に含まれるハッシュ値をキーとするエントリをハッシュテーブルから検索し（ステップＳ９０）、検索結果を検索情報処理部１５に送信する。登録情報管理部１４は、次のハッシュ値があるか否かを判定する（ステップＳ９１）。次の連結属性値がある場合（ステップＳ９１；ＹＥＳ）、ステップＳ８８に戻り、ステップＳ８９〜ステップＳ９１の処理を繰り返す。次の連結属性値がない場合（ステップＳ９１；ＮＯ）、処理を終了する。
【００５３】
以上説明したように、実施の形態２の情報検索システム１０２によれば、検索対象に含まれる要素の数が増加した場合にも、処理時間の増加を防いで短時間での処理を実現することができ、かつ、属性名は異なるが属性値が同一である２つの属性情報が情報検索システムに入力された場合に、検索結果から本来マッチすべきではない登録情報が含まれることを防止することができる。
【００５４】
図９は、本発明の実施の形態に係る情報検索システムを構成する情報検索装置のハードウェア構成の一例を示すブロック図である。情報検索システム１０１および１０２を構成する情報検索装置は、図９に示すように、制御部２１、主記憶部２２、外部記憶部２３、操作部２４、表示部２５、入出力部２６および送受信部２７を備える。主記憶部２２、外部記憶部２３、操作部２４、表示部２５、入出力部２６および送受信部２７はいずれも内部バス２０を介して制御部２１に接続されている。
【００５５】
制御部２１はＣＰＵ（Central Processing Unit）等から構成され、外部記憶部２３に記憶されている制御プログラム３０に従って、情報検索装置の情報登録部１１、属性情報ソート連結部１２、ハッシュ生成部１３、登録情報管理部１４、検索情報処理部１５、組み合わせ生成部１６、組み合わせ管理部１７および属性変換部１８の各処理を実行する。
【００５６】
主記憶部２２はＲＡＭ（Random-Access Memory）等から構成され、外部記憶部２３に記憶されている制御プログラム３０をロードし、制御部２１の作業領域として用いられる。
【００５７】
外部記憶部２３は、フラッシュメモリ、ハードディスク、ＤＶＤ−ＲＡＭ（Digital Versatile Disc Random-Access Memory）、ＤＶＤ−ＲＷ（Digital Versatile Disc ReWritable）等の不揮発性メモリから構成され、情報検索システム１０１および１０２の処理を制御部２１に行わせるためのプログラムをあらかじめ記憶し、また、制御部２１の指示に従って、このプログラムが記憶するデータを制御部２１に供給し、制御部２１から供給されたデータを記憶する。登録情報管理部１４、組み合わせ管理部１７および属性変換部１８の記憶領域は、外部記憶部２３に構成される。
【００５８】
操作部２４はキーボードおよびマウスなどのポインティングデバイス等と、キーボードおよびポインティングデバイス等を内部バス２０に接続するインタフェース装置から構成されている。連結属性値を生成する際の並び替えの順序などを設定する場合や、ユーザが情報検索装置に直接検索情報を入力する場合は、操作部２４を介して、指示が制御部２１に供給される。
【００５９】
表示部２５は、ＣＲＴ（Cathode Ray Tube）またはＬＣＤ（Liquid Crystal Display）などから構成され、連結属性値を生成する際の並び替えの順序などを設定する場合や、ユーザが情報検索装置に直接検索情報を入力する場合は、操作画面を表示する。また、表示部２５は、検索結果を表示することとしてもよい。
【００６０】
入出力部２６は、シリアルインタフェースまたはパラレルインタフェースから構成されている。入出力部２６は、ユーザ端末が情報検索装置の附属の装置である場合は、それに接続する。
【００６１】
送受信部２７は、ネットワークに接続する網終端装置または無線通信装置、およびそれらと接続するシリアルインタフェースまたはＬＡＮ（Local Area Network）インタフェースから構成されている。送受信部２７は、情報検索装置とユーザ端末がネットワーク接続される場合は、ネットワークを介してそれに接続する。
【００６２】
図１に示す情報検索システム１０１および１０２の情報登録部１１、属性情報ソート連結部１２、ハッシュ生成部１３、登録情報管理部１４、検索情報処理部１５、組み合わせ生成部１６、組み合わせ管理部１７および属性変換部１８の処理は、制御プログラム３０が、制御部２１、主記憶部２２、外部記憶部２３、操作部２４、表示部２５、入出力部２６および送受信部２７などを資源として用いて処理することによって実行する。
【００６３】
その他、前記のハードウエア構成やフローチャートは一例であり、任意に変更および修正が可能である。
【００６４】
制御部２１、主記憶部２２、外部記憶部２３、操作部２４、内部バス２０などから構成される情報検索処理を行う中心となる部分は、専用のシステムによらず、通常のコンピュータシステムを用いて実現可能である。たとえば、前記の動作を実行するためのコンピュータプログラムを、コンピュータが読み取り可能な記録媒体（フレキシブルディスク、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ等）に格納して配布し、当該コンピュータプログラムをコンピュータにインストールすることにより、前記の処理を実行する情報検索システム１０１および１０２を構成してもよい。また、インターネット等の通信ネットワーク上のサーバ装置が有する記憶装置に当該コンピュータプログラムを格納しておき、通常のコンピュータシステムがダウンロード等することで情報検索システム１０１および１０２を構成してもよい。
【００６５】
また、情報検索システム１０１および１０２の機能を、ＯＳ（オペレーティングシステム）とアプリケーションプログラムの分担、またはＯＳとアプリケーションプログラムとの協働により実現する場合などには、アプリケーションプログラム部分のみを記録媒体や記憶装置に格納してもよい。
【００６６】
また、搬送波にコンピュータプログラムを重畳し、通信ネットワークを介して配信することも可能である。たとえば、通信ネットワーク上の掲示板(BBS, Bulletin Board System)に前記コンピュータプログラムを掲示し、ネットワークを介して前記コンピュータプログラムを配信してもよい。そして、このコンピュータプログラムを起動し、ＯＳの制御下で、他のアプリケーションプログラムと同様に実行することにより、前記の処理を実行できるように構成してもよい。
【００６７】
上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
【００６８】
（付記１）
属性名と属性値からなる属性情報を１つ以上含む登録情報を記憶する記憶手段と、
前記登録情報に含まれる属性情報の組み合わせを示す情報である組み合わせ選択情報を作成し、記憶する組み合わせ管理手段と、
前記属性名と前記属性値からなる前記属性情報を１つ以上含み、情報検索の対象である検索情報を取得する取得手段と、
前記組み合わせ選択情報を取得し、前記検索情報に基づいて前記組み合わせ選択情報に対応する組み合わせの新たな検索情報を生成する生成手段と、
前記新たな検索情報と一致する前記登録情報を前記記憶手段から検索する検索手段と、
を備えることを特徴とする情報検索システム。
【００６９】
（付記２）
前記組み合わせ選択情報は、前記登録情報に含まれる属性情報の属性名の組み合わせを示す情報であって、
前記生成手段は、前記組み合わせ選択情報を取得し、前記検索情報の属性情報の中から、前記組み合わせ選択情報に含まれる属性名の組み合わせの新たな検索情報を生成することを特徴とする付記１に記載の情報検索システム。
【００７０】
（付記３）
前記登録情報および前記新たな検索情報に含まれる１つ以上の属性値を所定の条件に従って並べ替え、連結した連結属性値を作成する連結手段と、
前記連結属性値をハッシュ変換してハッシュ値を生成するハッシュ生成手段と、を備え、
前記記憶手段は、前記登録情報に対応する前記ハッシュ値をキーとし前記登録情報を値とするハッシュテーブルを記憶しており、
前記検索手段は、前記ハッシュテーブルから前記新たな検索情報に対応するハッシュ値と一致するキーを検索し、その値である登録情報を取得することを特徴とする付記１または２に記載の情報検索システム。
【００７１】
（付記４）
前記登録情報および前記検索情報について、前記属性名および前記属性値の組を一意に識別する属性値に変換して、変換後登録情報および変換後検索情報を生成する変換手段をさらに備え、
前記記憶手段は、前記変換後登録情報を記憶し、
前記生成手段は、前記変換後検索情報に基づいて前記新たな検索情報を生成し、
前記検索手段は、前記新たな検索情報と一致する前記変換後登録情報を前記記憶手段から検索することを特徴とする付記１ないし３のいずれか１項に記載の情報検索システム。
【００７２】
（付記５）
前記変換手段は、前記属性値を属性名と属性値を連結した文字列に変換することを特徴とする付記４に記載の情報検索システム。
【００７３】
（付記６）
前記変換手段は、前記属性値を属性値に識別文字列を付与した文字列に変換することを特徴とする付記４に記載の情報検索システム。
【００７４】
（付記７）
情報検索システムが実行する情報検索方法であって、
属性名と属性値からなる属性情報を１つ以上含む登録情報に含まれる属性情報の組み合わせを示す情報である組み合わせ選択情報を作成し、記憶する組み合わせ管理ステップと、
前記属性名と前記属性値からなる前記属性情報を１つ以上含み、情報検索の対象である検索情報を取得する取得ステップと、
前記組み合わせ選択情報を取得し、前記検索情報に基づいて前記組み合わせ選択情報に対応する組み合わせの新たな検索情報を生成する生成ステップと、
前記登録情報を記憶する記憶手段から、前記新たな検索情報と一致する前記登録情報を検索する検索ステップと、
を備えることを特徴とする情報検索方法。
【００７５】
（付記８）
前記組み合わせ選択情報は、前記登録情報に含まれる属性情報の属性名の組み合わせを示す情報であって、
前記生成ステップでは、前記組み合わせ選択情報を取得し、前記検索情報の属性情報の中から、前記組み合わせ選択情報に含まれる属性名の組み合わせの新たな検索情報を生成することを特徴とする付記７に記載の情報検索方法。
【００７６】
（付記９）
前記登録情報および前記新たな検索情報に含まれる１つ以上の属性値を所定の条件に従って並べ替え、連結した連結属性値を作成する連結ステップと、
前記連結属性値をハッシュ変換してハッシュ値を生成するハッシュ生成ステップと、を備え、
前記検索ステップでは、前記記憶手段が記憶する前記登録情報に対応する前記ハッシュ値をキーとし前記登録情報を値とするハッシュテーブルから、前記新たな検索情報に対応するハッシュ値と一致するキーを検索し、その値である登録情報を取得することを特徴とする付記７または８に記載の情報検索方法。
【００７７】
（付記１０）
前記登録情報および前記検索情報について、前記属性名および前記属性値の組を一意に識別する属性値に変換して、変換後登録情報および変換後検索情報を生成する変換ステップをさらに備え、
前記生成ステップでは、前記変換後検索情報に基づいて前記新たな検索情報を生成し、
前記検索ステップでは、前記新たな検索情報と一致する前記変換後登録情報を、前記変換後登録情報を記憶する前記記憶手段から検索することを特徴とする付記７ないし９のいずれか１項に記載の情報検索方法。
【００７８】
（付記１１）
前記変換ステップでは、前記属性値を属性名と属性値を連結した文字列に変換することを特徴とする付記１０に記載の情報検索方法。
【００７９】
（付記１２）
前記変換ステップでは、前記属性値を属性値に識別文字列を付与した文字列に変換することを特徴とする付記１０に記載の情報検索方法。
【００８０】
（付記１３）
コンピュータを、
属性名と属性値からなる属性情報を１つ以上含む登録情報を記憶する記憶手段、
前記登録情報に含まれる属性情報の組み合わせを示す情報である組み合わせ選択情報を作成し、記憶する組み合わせ管理手段、
前記属性名と前記属性値からなる前記属性情報を１つ以上含み、情報検索の対象である検索情報を取得する取得手段、
前記組み合わせ選択情報を取得し、前記検索情報に基づいて前記組み合わせ選択情報に対応する組み合わせの新たな検索情報を生成する生成手段、
前記新たな検索情報と一致する前記登録情報を前記記憶手段から検索する検索手段、
として機能させることを特徴とするプログラム。
【符号の説明】
【００８１】
１１  情報登録部
１２  属性情報ソート連結部
１３  ハッシュ生成部
１４  登録情報管理部
１５  検索情報処理部
１６  組み合わせ生成部
１７  組み合わせ管理部
１８  属性値変換部
２１  制御部
２２  主記憶部
２３  外部記憶部
２４  操作部
２５  表示部
２６  入出力部
２７  送受信部
３０  制御プログラム
１０１  情報検索システム
１０２  情報検索システム
【図１】
0005477139.tif 000002
【図２】
0005477139.tif 000003
【図３】
0005477139.tif 000004
【図４】
0005477139.tif 000005
【図５】
0005477139.tif 000006
【図６】
0005477139.tif 000007
【図７】
0005477139.tif 000008
【図８】
0005477139.tif 000009
【図９】
0005477139.tif 000010