(57)【要約】【課題】大量のリソースを消費せずに検索処理を高速に実行できる情報検索装置を提供する。【解決手段】情報検索装置１は、検索条件を獲得する検索条件獲得手段１０と、ビットマップ表を縮退または圧縮して階層的に形成されたビットマップ表を多段状に積層したインデックスから検索条件に基づいて最上段から最下段まで順にビットマップ表を獲得するインデックス獲得手段１３と、ビットマップ表が圧縮されている場合にそのデータを解凍する解凍手段１４と、解凍されたビットマップ表において最下段まで順にビットマップ表の中から検索条件に対応したビットマップ列を抽出してビットワイズ演算を行うことでビットマップを算出するビットマップ算出手段１５と、最下段で算出されたビットマップにおいてビットが割り当てられた位置に対応するドキュメントを複数のドキュメントの中から抽出するビットマップ対応情報抽出手段１２とを備える。【選択図】図１
2009048352.tif 000002
【特許請求の範囲】
【請求項１】
利用者によって入力された検索条件に基づいて、複数の検索対象情報の中から、前記入力された検索条件に対応した検索対象情報を、前記利用者の所望する検索対象情報として検索する情報検索装置であって、
前記検索条件として、前記利用者の所望する検索対象情報についての予め定められた複数の検索条件を獲得する検索条件獲得手段と、
予め作成されたビットマップ表に格納された所定のビットデータを縮退または圧縮する処理を施して加工した複数のビットマップ表を多段状に順次積み上げて構成したインデックスの中から、前記検索条件獲得手段で獲得された複数の検索条件に基づいて、データの包含関係が最大のものから最小のものまで順にビットマップ表を獲得するインデックス獲得手段と、
前記インデックス獲得手段で獲得されたビットマップ表に格納された所定のデータが圧縮されている場合に前記圧縮されているデータを解凍したビットマップ表を生成する解凍手段と、
前記インデックス獲得手段で獲得され、所定のデータが圧縮されている場合には前記圧縮されているデータが解凍された、ビットマップ表において、前記データの包含関係が最大のものから最小のものまで順に、前記ビットマップ表の中から、前記検索条件獲得手段で獲得された複数の検索条件に対応した複数のビットマップ列を抽出し、前記抽出した複数のビットマップ列のそれぞれ対応する位置に割り当てられたビットについて、ビットワイズ演算を行うことでビットマップを算出するビットマップ算出手段と、
前記データの包含関係が最小のビットマップ表について算出されたビットマップに対応する情報として、前記複数の検索対象情報の中から、前記最小のビットマップ表について算出されたビットマップにおいて前記一方のビットが割り当てられたビット位置に対応する検索対象情報を抽出するビットマップ対応情報抽出手段とを備え、
前記予め作成されたビットマップ表は、前記複数の検索対象情報の識別情報と、前記予め定められた複数の検索条件とが２値のいずれか一方のビットに対応付けられており、
前記インデックスは、前記処理前のビットマップ表に格納された所定のデータが前記処理後のビットマップ表に包含されるように階層的に形成されていることを特徴とする情報検索装置。
【請求項２】
前記インデックスは、
前記複数の検索対象情報を複数のグループに分けたときに前記グループを単位として、前記予め作成されたビットマップ表に格納された所定のデータを縮退または圧縮する処理を順次施して多段状に構成されたものであり、
前記インデックスの各段を示すビットマップ表は、ビットワイズ演算によるジョイン処理が可能であることを特徴とする請求項１に記載の情報検索装置。
【請求項３】
前記インデックスは、
前記複数の検索対象情報を内容の類似度に基づいて複数のグループに分けたときに前記グループを単位として、前記予め作成されたビットマップ表に格納された所定のデータを縮退または圧縮する処理を順次施して多段状に構成されたものであり、
前記インデックスの各段を示すビットマップ表は、ビットワイズ演算によるジョイン処理が可能であることを特徴とする請求項１に記載の情報検索装置。
【請求項４】
前記インデックスは、
前記予め定められた複数の検索条件を複数のグループに分けたときに前記グループを単位として、前記予め作成されたビットマップ表に格納された所定のデータを縮退または圧縮する処理を順次施して多段状に構成されたものであり、
前記インデックスの各段を示すビットマップ表は、ビットワイズ演算によるジョイン処理が可能であることを特徴とする請求項１ないし請求項３のいずれか一項に記載の情報検索装置。
【請求項５】
前記インデックスは、
前記予め定められた複数の検索条件を内容の類似度に基づいて複数のグループに分けたときに前記グループを単位として、前記予め作成されたビットマップ表に格納された所定のデータを縮退または圧縮する処理を順次施して多段状に構成されたものであり、
前記インデックスの各段を示すビットマップ表は、ビットワイズ演算によるジョイン処理が可能であることを特徴とする請求項１ないし請求項３のいずれか一項に記載の情報検索装置。
【請求項６】
前記インデックスにおいて前記予め定められた複数の検索条件は、所定の連続値を区切って構成される複数の区間であって、
前記複数の検索対象情報に関連する情報をそれぞれ数値化した情報は、前記複数の区間のいずれかに含まれ、
前記インデックスは、
前記区間を単位として、前記予め作成されたビットマップ表に格納された所定のデータを縮退または圧縮する処理を順次施して多段状に構成されたものであることを特徴とする請求項１ないし請求項５のいずれか一項に記載の情報検索装置。
【請求項７】
利用者によって入力された検索条件に基づいて、複数の検索対象情報の中から、前記入力された検索条件に対応した検索対象情報を、前記利用者の所望する検索対象情報として検索する情報検索装置の情報検索方法であって、
前記情報検索装置は、
前記検索条件として、前記利用者の所望する検索対象情報についての予め定められた複数の検索条件を獲得する検索条件獲得ステップと、
予め作成されたビットマップ表に格納された所定のビットデータを縮退または圧縮する処理を施して加工した複数のビットマップ表を多段状に順次積み上げて構成したインデックスの中から、前記検索条件獲得ステップで獲得された複数の検索条件に基づいて、データの包含関係が最大のものから最小のものまで順にビットマップ表を獲得するインデックス獲得ステップと、
前記インデックス獲得ステップで獲得されたビットマップ表に格納された所定のデータが圧縮されている場合に前記圧縮されているデータを解凍したビットマップ表を生成する解凍ステップと、
前記インデックス獲得ステップで獲得され、所定のデータが圧縮されている場合には前記圧縮されているデータが解凍された、ビットマップ表において、前記データの包含関係が最大のものから最小のものまで順に、前記ビットマップ表の中から、前記検索条件獲得ステップで獲得された複数の検索条件に対応した複数のビットマップ列を抽出し、前記抽出した複数のビットマップ列のそれぞれ対応する位置に割り当てられたビットについて、ビットワイズ演算を行うことでビットマップを算出するビットマップ算出ステップと、
前記データの包含関係が最小のビットマップ表について算出されたビットマップに対応する情報として、前記複数の検索対象情報の中から、前記最小のビットマップ表について算出されたビットマップにおいて前記一方のビットが割り当てられたビット位置に対応する検索対象情報を抽出するビットマップ対応情報抽出ステップとを実行し、
前記予め作成されたビットマップ表は、前記複数の検索対象情報の識別情報と、前記予め定められた複数の検索条件とが２値のいずれか一方のビットに対応付けられており、
前記インデックスは、前記処理前のビットマップ表に格納された所定のデータが前記処理後のビットマップ表に包含されるように階層的に形成されていることを特徴とする情報検索方法。
【請求項８】
前記インデックスは、
前記複数の検索対象情報を内容の類似度に基づいて複数のグループに分けたときに前記グループを単位として、前記予め作成されたビットマップ表に格納された所定のデータを縮退または圧縮する処理を順次施して多段状に構成されたものであり、
前記インデックスの各段を示すビットマップ表は、ビットワイズ演算によるジョイン処理が可能であることを特徴とする請求項７に記載の情報検索方法。
【請求項９】
前記インデックスは、
前記予め定められた複数の検索条件を内容の類似度に基づいて複数のグループに分けたときに前記グループを単位として、前記予め作成されたビットマップ表に格納された所定のデータを縮退または圧縮する処理を順次施して多段状に構成されたものであり、
前記インデックスの各段を示すビットマップ表は、ビットワイズ演算によるジョイン処理が可能であることを特徴とする請求項７または請求項８に記載の情報検索方法。
【請求項１０】
請求項１ないし請求項６のいずれか一項に記載の情報検索装置の機能をコンピュータで実現するための情報検索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、多数のドキュメントファイル等の大量の検索対象情報から、検索対象情報に含まれる語や検索対象情報の属性情報を検索条件として、利用者の所望する検索対象情報を検索する情報検索装置、情報検索方法および情報検索プログラムに関する。
【背景技術】
【０００２】
従来、例えば、多数のドキュメントファイル等の大量の検索対象情報（テキスト情報）から、検索条件の情報として、「検索対象情報に含まれる語」や「検索対象情報の属性情報」を用いて、検索対象情報を検索する方法として以下の２通りの方法が知られている（例えば、非特許文献１および非特許文献２参照）。なお、検索対象情報の属性情報とは、例えば、検索対象情報がドキュメントファイルであれば、ファイル作成日時、作成者、構成文字数、閲覧可否情報、有効期限等を指す。
【０００３】
従来の第１の検索方法は、非特許文献１に開示された方法に関連して、複数の検索条件（検索対象情報に含まれる語や検索対象情報の属性情報）を個々の検索条件に切り離して、大量の検索対象情報に対して、切り離した各々の検索条件を独立に用いて検索処理を行い、検索条件毎に一次的な検索結果セットを獲得するものである。具体的には、従来の情報検索装置に、検索条件として、例えば、「検索対象に含まれる語」と、「検索対象情報の１つの属性情報」とが入力された場合に、情報検索装置は、まず、第１段階として、入力された「検索対象に含まれる語」を含むすべての検索対象情報を、大量の検索対象情報の中から検索し、一次的な検索結果である複数の検索対象情報を検索結果セットとして作成、保持する。次に、第２段階として、情報検索装置は、一次的な検索結果セットに含まれる１つ１つの検索対象情報について、検索条件として入力された「検索対象情報の１つの属性情報」を満たすテキスト情報を抽出して、最終的な検索結果として利用者に提示する。これにより、利用者は、入力した「検索対象に含まれる語」と、「検索対象情報の１つの属性情報」に応じた所望のテキスト情報を取得することができる。
【０００４】
また、従来の第２の検索方法は、非特許文献１および非特許文献２に開示された方法に関連して、大量の検索対象情報について、問い合わせの可能性がある全ての検索条件に対応して予め作成されたビットマップインデックスを用意しておくものである。この方法では、情報検索装置に複数の検索条件が入力された場合に、予め作成されたビットマップインデックスに基づいて各検索条件に対応したビットマップ列間の論理積をとり、論理積結果のビットの立った箇所に対応する情報を、利用者の欲する情報として提示する。
【非特許文献１】J. Zobel and A. Moffat, Inverted Files Text Search Engines, ACM Computing Surveys, Vo1.38, No. 2, Article 6, July, 2006
【非特許文献２】C. Y. Chan and Y. E. Ioannidis, Bitmap Index Design and Evaluation, Proceedings of the 1998 ACM SIGMOD international Conference on Management of data, pages:355-366, 1998．
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、従来の第１の検索方法では、入力された複数の検索条件を、個別の検索条件に切り離して、入力された複数の検索条件のうちの１つのだけを用いて、他の検索条件を用いずに、一次的な検索結果セットを獲得する。そのため、この検索結果セットに含まれる検索対象が大量となってしまう可能性がある。この場合に、検索結果セットを保管するため大量のリソース（主としてメモリまたはディスク）が消費されることとなる。また、従来の第１の検索方法は、個別の検索条件に切り離された１つ１つの検索条件に対応した一次的な検索結果セットを獲得する個別の段階と、利用者に提示する最終的な検索結果を求める段階とを有するため、検索処理に時間がかかるという問題がある。
【０００６】
また、従来の第２の検索方法では、大量の検索対象情報として、例えば1000万以上のドキュメントファイルを扱うような場合に、問い合わせの可能性がある全ての検索条件に対応したビットマップインデックスのサイズが巨大になってしまい、その保持のために、多くのリソース（主としてメモリまたはディスク）を必要とする。さらに、ビットワイズ演算時には、巨大なサイズのビットマップインデックスを基準とした巨大なビット列を扱わねばならず、多くのリソース（主としてＣＰＵキャッシュとメモリ）を消費することとなり、演算性能も劣化してしまうという問題がある。
【０００７】
そこで、本発明では、前記した問題を解決し、大量のリソースを消費することなく、検索処理を高速に実行することのできる情報検索装置、情報検索方法および情報検索プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
前記課題を解決するため、請求項１に記載の情報検索装置は、利用者によって入力された検索条件に基づいて、複数の検索対象情報の中から、前記入力された検索条件に対応した検索対象情報を、前記利用者の所望する検索対象情報として検索する情報検索装置であって、前記検索条件として、前記利用者の所望する検索対象情報についての予め定められた複数の検索条件を獲得する検索条件獲得手段と、予め作成されたビットマップ表に格納された所定のビットデータを縮退または圧縮する処理を施して加工した複数のビットマップ表を多段状に順次積み上げて構成したインデックスの中から、前記検索条件獲得手段で獲得された複数の検索条件に基づいて、データの包含関係が最大のものから最小のものまで順にビットマップ表を獲得するインデックス獲得手段と、前記インデックス獲得手段で獲得されたビットマップ表に格納された所定のデータが圧縮されている場合に前記圧縮されているデータを解凍したビットマップ表を生成する解凍手段と、前記インデックス獲得手段で獲得され、所定のデータが圧縮されている場合には前記圧縮されているデータが解凍された、ビットマップ表において、前記データの包含関係が最大のものから最小のものまで順に、前記ビットマップ表の中から、前記検索条件獲得手段で獲得された複数の検索条件に対応した複数のビットマップ列を抽出し、前記抽出した複数のビットマップ列のそれぞれ対応する位置に割り当てられたビットについて、ビットワイズ演算を行うことでビットマップを算出するビットマップ算出手段と、前記データの包含関係が最小のビットマップ表について算出されたビットマップに対応する情報として、前記複数の検索対象情報の中から、前記最小のビットマップ表について算出されたビットマップにおいて前記一方のビットが割り当てられたビット位置に対応する検索対象情報を抽出するビットマップ対応情報抽出手段とを備え、前記予め作成されたビットマップ表が、前記複数の検索対象情報の識別情報と、前記予め定められた複数の検索条件とが２値のいずれか一方のビットに対応付けられており、前記インデックスが、前記処理前のビットマップ表に格納された所定のデータが前記処理後のビットマップ表に包含されるように階層的に形成されていることを特徴とする。
【０００９】
かかる構成によれば、情報検索装置は、予め作成されたビットマップ表を元として階層的に形成された複数のビットマップ表を積み上げて多段状に構成されたインデックスの中から、検索条件に対応した複数のビットマップ表を上位階層から順次獲得する。ここで、ビットマップ表において、複数の検索対象情報の識別情報と対応付けられた予め定められた複数の検索条件は、例えば、所望の検索対象情報に含まれて入力される検索条件となりうる語や、所望の検索対象情報の属性情報である。そして、情報検索装置は、獲得した複数のビットマップ表に圧縮データがあれば解凍してから、複数のビットマップ表を上位階層から順次処理対象として、対象とするビットマップ表の中から、検索条件に対応した複数のビットマップ列を抽出して、ビットワイズ演算を行うことでビットマップを算出する。この順次処理の過程で算出されたビットマップにおいて、ビットが立てられた位置を指標として、次に処理すべき下層の階層のビットマップから計算に必要なデータを抽出することができる。そして、最終的には、最下層のビットマップ表から算出したビットマップにおいて、ビットが立てられた位置に対応する検索対象情報の識別情報が利用者に提示すべき検索対象情報として抽出される。したがって、検索処理装置は、利用者から入力された検索条件に対応した検索結果情報として、この抽出された検索対象情報を出力することができる。
【００１０】
これにより、情報検索装置は、大量の検索対象情報について問い合わせの可能性がある全ての検索条件に対応したビットマップインデックスを予め用意する必要がないので、従来に比べて大量のリソース（ＣＰＵキャッシュ、メモリ、ディスク）を消費することがない。また、情報検索装置は、複数の検索条件を、個別に切り離して処理するのではなく、まとめて扱うことを可能にし、検索候補の絞込みを高速に実施することができる。したがって、従来の装置に比べてリソース（ディスク、メモリ、ＣＰＵ）の消費を低減し、かつ、検索処理を高速に実行することができる。
【００１１】
また、請求項２に記載の情報検索装置は、請求項１に記載の情報検索装置において、前記インデックスが、前記複数の検索対象情報を複数のグループに分けたときに前記グループを単位として、前記予め作成されたビットマップ表に格納された所定のデータを縮退または圧縮する処理を順次施して多段状に構成されたものであり、前記インデックスの各段を示すビットマップ表が、ビットワイズ演算によるジョイン処理が可能であることを特徴とする。
【００１２】
かかる構成によれば、情報検索装置は、インデックス中で検索対象情報のグループ毎にビットが割当てられたビットマップ表に基づいて複数のビットマップ列を獲得する。これによれば、情報検索装置は、処理対象とするビットマップ表から、入力された検索条件に応じた検索対象情報のグループに関するビットマップ列のみを検索することとなる。ここで、検索対象情報のグループは、階層的に設けることができる。
【００１３】
また、各段においてビットワイズ演算によるジョイン処理を可能にしたインデックスを用いるため、以下の効果を奏する。まず、インデックスにおける各段において圧縮データがある場合に必要部分のみを部分解凍すればよいため、高速な検索が可能となる。また、検索処理中において、中間データサイズを小さくすることができる。さらに、１回の計算におけるビットマップサイズを小さくすることができ、その結果、ＣＰＵキャッシュの効率的利用が可能となる。したがって、かかる構成の情報検索装置は、従来の装置に比べてリソースの消費を低減し、かつ、検索処理を高速に実行することができる。
【００１４】
また、請求項３に記載の情報検索装置は、請求項１に記載の情報検索装置において、前記インデックスが、前記複数の検索対象情報を内容の類似度に基づいて複数のグループに分けたときに前記グループを単位として、前記予め作成されたビットマップ表に格納された所定のデータを縮退または圧縮する処理を順次施して多段状に構成されたものであり、前記インデックスの各段を示すビットマップ表が、ビットワイズ演算によるジョイン処理が可能であることを特徴とする。
【００１５】
かかる構成によれば、情報検索装置は、インデックス中で検索対象情報について内容が類似したグループ毎にビットが割当てられたビットマップ表に基づいて複数のビットマップ列を獲得する。ここで、検索対象情報について内容が類似したグループは、階層的に設けることができる。また、類似度は、検索対象情報に応じて適宜定めることができる。例えば、検索対象情報がドキュメントであれば、ドキュメントのタイトルやジャンルで定めてもよいし、ドキュメントに含まれるキーワードやその個数で定めてもよい。また、かかる構成の情報検索装置によれば、検索対象情報について内容が類似したグループに分けることで、以下の作用効果を奏する。すなわち、インデックス中においてビットの立つ箇所が密集するので、圧縮効率が向上する。また、縮退後にビットの立つ箇所の数が削減される。その結果、ビットマップ演算結果における、ビットの立つ箇所の数が削減されるそのため、リソース（メモリ、ディスク）の消費を抑えることができる。
【００１６】
また、請求項４に記載の情報検索装置は、請求項１ないし請求項３のいずれか一項に記載の情報検索装置において、前記インデックスが、前記予め定められた複数の検索条件を複数のグループに分けたときに前記グループを単位として、前記予め作成されたビットマップ表に格納された所定のデータを縮退または圧縮する処理を順次施して多段状に構成されたものであり、前記インデックスの各段を示すビットマップ表が、ビットワイズ演算によるジョイン処理が可能であることを特徴とする。
【００１７】
かかる構成によれば、情報検索装置は、インデックス中で検索条件のグループ毎にビットが割当てられたビットマップ表に基づいて複数のビットマップ列を獲得する。ここで、検索条件のグループは、階層的に設けることができる。これによれば、情報検索装置は、処理対象とするビットマップ表から、入力された検索条件に応じて、ビットマップ表中の検索条件のグループに関するビットマップ列のみを検索することとなる。したがって、従来の装置に比べてリソースの消費を低減し、かつ、検索処理を高速に実行することができる。
【００１８】
また、請求項５に記載の情報検索装置は、請求項１ないし請求項３のいずれか一項に記載の情報検索装置において、前記インデックスが、前記予め定められた複数の検索条件を内容の類似度に基づいて複数のグループに分けたときに前記グループを単位として、前記予め作成されたビットマップ表に格納された所定のデータを縮退または圧縮する処理を順次施して多段状に構成されたものであり、前記インデックスの各段を示すビットマップ表が、ビットワイズ演算によるジョイン処理が可能であることを特徴とする。
【００１９】
かかる構成によれば、情報検索装置は、インデックス中で検索条件について内容が類似したグループ毎にビットが割当てられたビットマップ表に基づいて複数のビットマップ列を獲得する。ここで、検索条件について内容が類似したグループは、階層的に設けることができる。また、類似度は、検索条件に応じて適宜定めることができる。例えば、検索条件がドキュメントに含まれるキーワードであれば、そのキーワードが食べ物に関するものか場所に関するものかという上位概念の分類で定めてもよい。また、検索条件がドキュメントの作成日時であれば年月日で定めてもよい。また、かかる構成の情報検索装置によれば、インデックス中の検索条件について内容が類似したグループに分けることで、以下の作用効果を奏する。すなわち、インデックス中においてビットの立つ箇所が密集するので、圧縮効率が向上する。また、縮退後にビットの立つ箇所の数が削減される。その結果、ビットマップ演算結果における、ビットの立つ箇所の数が削減されるため、リソース（メモリ、ディスク）の消費を抑えることができる。
【００２０】
また、請求項６に記載の情報検索装置は、請求項１ないし請求項５のいずれか一項に記載の情報検索装置において、前記インデックスにおいて前記予め定められた複数の検索条件が、所定の連続値を区切って構成される複数の区間であって、前記複数の検索対象情報に関連する情報をそれぞれ数値化した情報が、前記複数の区間のいずれかに含まれ、前記インデックスが、前記区間を単位として、前記予め作成されたビットマップ表に格納された所定のデータを縮退または圧縮する処理を順次施して多段状に構成されたものであることを特徴とする。
【００２１】
かかる構成によれば、情報検索装置は、インデックス中で区間毎にビットが割当てられたビットマップ表に基づいて複数のビットマップ列を獲得する。ここで、検索対象情報に関連する情報をそれぞれ数値化した情報としては、例えば、検索対象情報の価格、文字数やページ数等である。これによれば、情報検索装置は、処理対象とするビットマップ表から、入力された検索条件としての検索対象情報に関連する情報をそれぞれ数値化した情報（例えば価格）に応じて、該当する区間に関するビットマップ列のみを検索することとなる。したがって、従来の装置に比べてリソースの消費を低減し、かつ、検索処理を高速に実行することができる。
【００２２】
また、前記課題を解決するため、請求項７に記載の情報検索方法は、利用者によって入力された検索条件に基づいて、複数の検索対象情報の中から、前記入力された検索条件に対応した検索対象情報を、前記利用者の所望する検索対象情報として検索する情報検索装置の情報検索方法であって、前記情報検索装置が、前記検索条件として、前記利用者の所望する検索対象情報についての予め定められた複数の検索条件を獲得する検索条件獲得ステップと、予め作成されたビットマップ表に格納された所定のビットデータを縮退または圧縮する処理を施して加工した複数のビットマップ表を多段状に順次積み上げて構成したインデックスの中から、前記検索条件獲得ステップで獲得された複数の検索条件に基づいて、データの包含関係が最大のものから最小のものまで順にビットマップ表を獲得するインデックス獲得ステップと、前記インデックス獲得ステップで獲得されたビットマップ表に格納された所定のデータが圧縮されている場合に前記圧縮されているデータを解凍したビットマップ表を生成する解凍ステップと、前記インデックス獲得ステップで獲得され、所定のデータが圧縮されている場合には前記圧縮されているデータが解凍された、ビットマップ表において、前記データの包含関係が最大のものから最小のものまで順に、前記ビットマップ表の中から、前記検索条件獲得ステップで獲得された複数の検索条件に対応した複数のビットマップ列を抽出し、前記抽出した複数のビットマップ列のそれぞれ対応する位置に割り当てられたビットについて、ビットワイズ演算を行うことでビットマップを算出するビットマップ算出ステップと、前記データの包含関係が最小のビットマップ表について算出されたビットマップに対応する情報として、前記複数の検索対象情報の中から、前記最小のビットマップ表について算出されたビットマップにおいて前記一方のビットが割り当てられたビット位置に対応する検索対象情報を抽出するビットマップ対応情報抽出ステップとを実行し、前記予め作成されたビットマップ表が、前記複数の検索対象情報の識別情報と、前記予め定められた複数の検索条件とが２値のいずれか一方のビットに対応付けられており、前記インデックスが、前記処理前のビットマップ表に格納された所定のデータが前記処理後のビットマップ表に包含されるように階層的に形成されていることを特徴とする。
【００２３】
かかる手順によれば、情報検索装置は、予め作成されたビットマップ表を元として階層的に形成された複数のビットマップ表を積み上げて多段状に構成されたインデックスの中から、検索条件に対応した複数のビットマップ表を上位階層から順次獲得する。そして、情報検索装置は、獲得した複数のビットマップ表に圧縮データがあれば解凍してから、複数のビットマップ表を上位階層から順次処理対象として、対象とするビットマップ表の中から、検索条件に対応した複数のビットマップ列を抽出して、ビットワイズ演算を行うことでビットマップを算出する。そして、検索処理装置は、最終的には、最下層のビットマップ表から算出したビットマップにおいて、ビットが立てられた位置に対応する検索対象情報の識別情報を、利用者に提示すべき検索対象情報として抽出する。
【００２４】
また、請求項８に記載の情報検索方法は、請求項７に記載の情報検索方法において、前記インデックスが、前記複数の検索対象情報を内容の類似度に基づいて複数のグループに分けたときに前記グループを単位として、前記予め作成されたビットマップ表に格納された所定のデータを縮退または圧縮する処理を順次施して多段状に構成されたものであり、前記インデックスの各段を示すビットマップ表が、ビットワイズ演算によるジョイン処理が可能であることを特徴とする。
【００２５】
かかる手順によれば、情報検索装置は、インデックス中で検索対象情報について内容が類似したグループ毎にビットが割当てられたビットマップ表に基づいて複数のビットマップ列を獲得する。ここで、類似度は、検索対象情報に応じて適宜定めることができる。
【００２６】
また、請求項９に記載の情報検索方法は、請求項７または請求項８に記載の情報検索方法において、前記インデックスが、前記予め定められた複数の検索条件を内容の類似度に基づいて複数のグループに分けたときに前記グループを単位として、前記予め作成されたビットマップ表に格納された所定のデータを縮退または圧縮する処理を順次施して多段状に構成されたものであり、前記インデックスの各段を示すビットマップ表が、ビットワイズ演算によるジョイン処理が可能であることを特徴とする。
【００２７】
かかる手順によれば、情報検索装置は、インデックス中で検索条件について内容が類似したグループ毎にビットが割当てられたビットマップ表に基づいて複数のビットマップ列を獲得する。ここで、類似度は、検索条件に応じて適宜定めることができる。
【００２８】
また、請求項１０に記載の情報検索プログラムは、請求項１ないし請求項６のいずれか一項に記載の情報検索装置の機能をコンピュータで実現するための情報検索プログラムとした。このように構成されることにより、このプログラムをインストールされたコンピュータは、このプログラムに基づいた各機能を実現することができる。
【発明の効果】
【００２９】
本発明によれば、大量の検索対象情報について問い合わせの可能性がある全ての検索条件に対応したビットマップインデックスを予め用意する必要がなく、また、複数の検索条件を個別に切り離すことなくまとめて処理するので、大量のリソースを消費することなく、検索処理を高速に実行することができる。
【発明を実施するための最良の形態】
【００３０】
以下、図面を参照して本発明の情報検索装置および情報検索方法を実施するための最良の形態（以下「実施形態」という）について詳細に説明する。
【００３１】
［情報検索装置の構成］
図１は、本発明の実施形態に係る情報検索装置を模式的に示す構成図である。情報検索装置１は、利用者によって入力された検索条件に基づいて、複数の検索対象情報の中から、入力された検索条件に対応した検索対象情報を、利用者の所望する検索対象情報として検索するものである。情報検索装置１は、例えば、ＣＰＵ（Central Processing Unit）、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、ＨＤＤ（Hard Disk Drive）、入出力インタフェース等から構成される。この情報検索装置１は、図１に示すように、入力手段２と、記憶手段３と、制御手段４と、出力手段５とを備えている。
【００３２】
＜入力手段＞
入力手段２は、所定の通信インタフェースや入力インタフェースから構成される。この入力手段２は、例えば、インターネット等の通信ネットワークを介して受信した利用者の検索条件を制御手段４に入力するものである。なお、入力手段２は、利用者の使用する情報検索装置１にケーブルで接続されたマウスやキーボード等の入力装置Ｍから入力される検索条件を制御手段４に入力することも可能である。
【００３３】
＜記憶手段＞
記憶手段３は、所定のプログラム等を格納するＲＯＭと、制御手段４による演算処理等に利用されるＲＡＭと、ＨＤＤとを備えている。この記憶手段３は、図１に示すように、インデックス格納部６と、情報格納部７と、プログラム格納部８とを備えている。
【００３４】
≪インデックス格納部≫
インデックス格納部６は、予め作成されたインデックスを格納するものであり、例えば、一般的なＨＤＤ等から構成される。インデックスは、複数の検索対象情報の識別情報と、予め定められた複数の検索条件とが２値のいずれか一方のビット（１か０）に対応付けられて予め作成されたビットマップ表から予め作成されたものである。このインデックスは、予め作成されたビットマップ表に格納された所定のビットデータを縮退または圧縮する処理を施して加工した複数のビットマップ表を多段状に順次積み上げて構成したものである。そして、インデックスは、縮退または圧縮による処理前のビットマップ表に格納された所定のデータが処理後のビットマップ表に包含されるように階層的に形成されている。なお、本実施形態では、インデックスは、予め定められた複数の検索条件等が「１」のビットに対応付けられている。また、多段状の構成とは、上段のビットマップ表のビットの立った箇所から、下段の対応するビットマップ、または、ビットマップを圧縮したデータヘアクセスする方法を提供可能な構成である。
【００３５】
本実施形態では、ビットマップ表は、複数のドキュメント（検索対象情報）のうちの各ドキュメントに含まれる語やドキュメント自身の属性情報が「１」のビットに対応付けられているものとする。また、本実施形態では、インデックスは、複数の検索対象情報を複数のグループに分けたときにそのグループを単位とし、かつ、予め定められた複数の検索条件を複数のグループに分けたときにそのグループを単位として、予め作成されたビットマップ表に格納された所定のデータを縮退または圧縮する処理を順次施して多段状に構成されたものであり、インデックスの各段を示すビットマップ表は、ビットワイズ演算によるジョイン処理が可能であるものとする。ここで、各グループは、内容が類似しているものから構成されることが好ましい。なお、インデックスは、複数の検索対象情報と予め定められた複数の検索条件とのうちの一方だけ複数のグループに分けてもよいし、グループ分けをしなくても構わない。
【００３６】
ここで、インデックスを構築する方法の一例について図２ないし図７を参照（適宜図１参照）して説明する。図２は、インデックスを構築する方法の一例を示すフローチャートである。この方法は、例えば、インデックスを構築するためのプログラムを格納された図示しない所定の情報処理装置が実行するものである。なお、情報検索装置１がこのプログラムをさらに実行することで同等の機能を果たしてもよい。
【００３７】
まず、この情報処理装置は、情報検索装置１の情報格納部７（図１参照）に格納される全ての情報（ドキュメント）と、入力されうる全ての検索条件（ドキュメントに含まれる語や属性情報）とを対応づけた巨大なビットマップ表を作成する（ステップＳ１）。この巨大なビットマップ表の一例を図３に示す。図３は、インデックスを構築する元となるビットマップ表の一例を示す図である。図３に示したビットマップ表３０は、「ドキュメントに含まれる語」として、「遠足」、「卵焼き」等を含んでいる。また、ビットマップ表３０は、「ドキュメント自身の属性情報」として、「有効期限」、「閲覧可否」等を含んでいる。図３において、「１」のビットが立っている箇所は、該当するドキュメントが、その検索条件を満たすことを示す。図３から、例えば、「登山へ行こう」というタイトルのドキュメントは、「東京」、「テント」、「ランプ」という語をドキュメント中に含むと共に、「有効期限内ではない」ものであり、「閲覧を許可されていない」ものであることが分かる。
【００３８】
図２のフローチャートにおいて、ステップＳ１に続いて、情報処理装置は、情報格納部７（図１参照）に格納される全ての情報（ドキュメント）について、内容的に類似したグループに分け（ステップＳ２）、入力されうる全ての検索条件について、内容的に類似したグループに分ける（ステップＳ３）。内容が類似したグループに分けて並べ替えた（改変した）ビットマップ表の一例を図４に示す。図４は、図３に示したビットマップ表をグルーピングにより改変したビットマップ表の一例を示す図である。図４に示す改変ビットマップ表４０は、検索条件の類似グループ４１として、「アウトドア」、「食べ物」等を含んでいる。また、改変ビットマップ表４０は、ドキュメントの類似グループ４２として、「旅行」、「レシピ」等を含んでいる。さらに、改変ビットマップ表４０では、ドキュメントを識別するために、全てのドキュメントにユニークな識別情報（Doc id）を付与した。この改変ビットマップ表４０は、図３に示したビットマップ表３０と比較すると、「１」のビットの立った箇所が、部分的に密集していることが分かる。
【００３９】
図２のフローチャートにおいて、ステップＳ３に続いて、情報処理装置は、改変ビットマップ表をドキュメントおよび検索条件の各グループ単位で縮退または圧縮する（ステップＳ４）。改変ビットマップ表を縮退したビットマップ表の一例を図５に示す。図５は、図４に示した改変ビットマップ表を縮退したビットマップ表の一例を示す図である。図５に示す縮退ビットマップ表５０において「１」のビットは、図４に示した改変ビットマップ表４０の対応する部分内で、１箇所でも「１」のビットが立っていたならば、「１」のビットを立てるという縮退ルールを適用したものである。つまり、図４に示した改変ビットマップ表４０の対応する部分内のビットが全て「０」でない限り、縮退ビットマップ表５０は、「０」のビットにはならない。図４に示した改変ビットマップ表４０において、ビットの立つ箇所を部分的に密集させておいたため、縮退ビットマップ表５０では、「１」のビットの立つ箇所の数が削減されている。
【００４０】
さらに詳細にいうと、縮退ビットマップ表５０は、検索条件の類似グループ５１として、「条件グループ１」、「条件グループ２」等を含んでいる。なお、「条件グループ１」は、図４に示した類似グループ「アウトドア」と同様なものである。また、縮退ビットマップ表５０は、ドキュメントについてのDocグループ５２として、「Docグループ１」、「Docグループ２」等を含んでいる。なお、「Docグループ１」は、図４に示した類似グループ「旅行」と同様なものである。図５において、「１」のビットが立っている箇所は、該当するDocグループに含まれるドキュメントの少なくとも一つが、検索条件の類似グループ（検索条件グループ）に含まれる検索条件の少なくとも一つを満たしていることを示す。例えば、符号５３で示す「１」のビットに着目すると、「Docグループ１」に含まれるドキュメント（Doc idが「ｌ」、「２」、「３」、「４」のドキュメント）のいずれかが、「条件グループ１」に含まれる検索条件のいずれか（「遠足」、「テント」、「ランプ」のいずれかの語を含むという条件）を満たしていることが分かる。また、例えば、符号５４で示す「０」のビットに着目すると、「Docグループ１」に含まれるドキュメントはいずれも「条件グループ１」に含まれる検索条件を満たしていないことが分かる。
【００４１】
次に、改変ビットマップ表を圧縮したビットマップ表の一例を図６に示す。図６は、図４に示した改変ビットマップ表を圧縮したビットマップ表の一例を示す図である。圧縮ビットマップ表６０は、検索条件の条件グループ名６１として、「条件グループ１」、「条件グループ２」等を含んでいる。なお、「条件グループ１」は、図４に示した類似グループ「アウトドア」と同様なものである。また、圧縮ビットマップ表６０は、ドキュメントについてのDocグループ名６２として、「Docグループ１」、「Docグループ２」等を含んでいる。なお、「Docグループ１」は、図４に示した類似グループ「旅行」と同様なものである。
【００４２】
さらに詳細にいうと、圧縮ビットマップ表６０において、例えば、符号６３で示す圧縮データ１−１は、図４に示した改変ビットマップ表４０における、類似グループ「旅行」に含まれるドキュメント（Doc idが「ｌ」、「２」、「３」、「４」のドキュメント）と、「アウトドア」に含まれる検索条件（「遠足」、「テント」、「ランプ」のいずれかの語を含むという条件）とを両方満たすビットマップ部分を圧縮したものである。図４に示した改変ビットマップ表４０において、ビットの立つ箇所を部分的に密集させたために、圧縮ビットマップ表６０は、圧縮効率が上がっている。これにより、リソース消費（メモリ、ディスク）が軽減される。なお、例えば、符号６４で示す圧縮データ１−２は、図４に示した改変ビットマップ表４０において対応する部分の全てのビットが「０」であるため、圧縮作業さえ不必要であるといえる。
【００４３】
ステップＳ４で実施する縮退または圧縮の方法は、縮退または圧縮の対象であるビットマップの持つboolean属性（０，１のいずれか）を保持した、縮退または圧縮の方法である。つまり、この方法は、ビットワイズ演算によるジョイン処理が可能な縮退または圧縮の方法である。これにより、インデックスの各段におけるビットワイズ演算によるジョイン処理が可能となる。なお、前記した例では、ビットマップの持つboolean属性を保持した縮退を行い、ビットマップの持つboolean属性を保持しない圧縮を行っているが、場合により、縮退は行わず、ビットマップの持つboolean属性を保持した圧縮を行うことも可能である。
【００４４】
図２のフローチャートにおいて、ステップＳ４に続いて、情報処理装置は、縮退または圧縮したビットマップ表を多段状に構成する（ステップＳ５）。一例として２段構成のインデックスを図７に示す。図７は、図６に示した圧縮ビットマップ表の上に、図５に示した縮退ビットマップ表を積み上げた多段（２段）のインデックスの一例を示す図である。図７に示すように、インデックスの１段目７１において符号７１ａで示す「１」のビットは、インデックスの２段目（最下段）７２における「圧縮データ２−１」に対応している。同様に、符号７１ｂで示す「１」のビットは「圧縮データ２−２」に対応し、符号７１ｃで示す「１」のビットは「圧縮データ２−Ｍ」に対応している。
【００４５】
図２のフローチャートにおいて、ステップＳ５に続いて、情報処理装置は、段数は最適か否か判別し（ステップＳ６）、最適な段数となるまで、ステップＳ２〜ステップＳ５の処理を繰り返す。これにより、インデックス格納部６（図１参照）に格納されるインデックスが構築される。ここで、最適とは、インデックスの全体の大きさと、各段のビットマップ表のビットマップや圧縮データとが、扱うのに最適な大きさかどうかを示すものであり、予め所定の基準が定められる。この所定の基準はドキュメント（検索対象情報）を扱う環境により異なるものでありそれぞれ適宜定められる。また、図５および図６に示したように、１通りのグルーピングで縮退と圧縮の両方を行うことができるので、ステップＳ２〜ステップＳ５の処理を繰り返すときに、必ずしもグループの変更を行うとは限らない。また、所定のビットマップ表に格納された所定のデータを圧縮する処理を階層的に繰り返す場合にはグループの変更を伴うこととなる。
【００４６】
図１に戻って、情報検索装置１の構成の説明を続ける。
≪情報格納部≫
情報格納部７は、検索対象の複数のテキスト情報（検索対象情報）を格納するものであり、例えば、一般的なＨＤＤ等から構成される。本実施形態では、情報格納部７に格納されたテキスト情報の１つ１つをドキュメントとする。これらドキュメントには、ドキュメントを識別する識別情報（ドキュメントＩＤ：Doc id）と、ドキュメントタイトルとが付与されている。
【００４７】
≪プログラム格納部≫
プログラム格納部８は、制御手段４が実行する各種プログラム等を格納するものであり、例えば、一般的メモリやＨＤＤ等から構成される。なお、インデックス格納部６や情報格納部７は、１以上の外部記憶装置で構成することもできる。
【００４８】
＜制御手段＞
制御手段４は、例えば、ＣＰＵ等から構成され、検索条件獲得手段１０と、ビットマップ情報算出手段１１と、ビットマップ対応情報抽出手段１２とを備えている。なお、これら検索条件獲得手段１０、ビットマップ情報算出手段１１およびビットマップ対応情報抽出手段１２は、ＣＰＵが記憶手段３のプログラム格納部８に格納された所定のプログラムをＲＡＭに展開して実行することにより実現されるものである。
【００４９】
≪検索条件獲得手段≫
検索条件獲得手段１０は、検索条件として、利用者の所望するドキュメント（検索対象情報）についての予め定められた複数の検索条件を獲得するものである。本実施形態では、検索条件獲得手段１０は、検索条件として、ドキュメントに含まれる複数の単語と、当該ドキュメント自身の属性情報とを獲得するものとする。
【００５０】
≪ビットマップ情報算出手段≫
ビットマップ情報算出手段１１は、インデックス獲得手段１３と、解凍手段１４と、ビットマップ算出手段１５と、インデックス取得制御手段１６とを備えている。
インデックス獲得手段１３は、予め作成されたインデックスの中から、検索条件獲得手段１０で獲得された複数の検索条件に基づいて、データの包含関係が最大のものから最小のものまで順にビットマップ表を獲得するものである。本実施形態では、インデックス獲得手段１３は、インデックス取得制御手段１６の制御の下、インデックス格納部６から、インデックスの１段目（最上段）、２段目、…、最下段の順にインデックスのｋ（ｋ＝１，２，…）段目のビットマップ表を獲得する。
【００５１】
≪解凍手段≫
解凍手段１４は、インデックス獲得手段１３で獲得されたビットマップ表に格納された所定のデータが圧縮されている場合に圧縮されているデータを解凍したビットマップ表を生成するものである。本実施形態では、解凍手段１４は、インデックス取得制御手段１６の制御の下、インデックスのｋ段目のビットマップ表に格納されたデータが圧縮されている場合にそのデータを解凍する。
【００５２】
≪ビットマップ算出手段≫
ビットマップ算出手段１５は、インデックス獲得手段１３で獲得され、所定のデータが圧縮されている場合には圧縮されているデータが解凍された、ビットマップ表において、データの包含関係が最大のものから最小のものまで順に、ビットマップ表の中から、検索条件獲得手段１０で獲得された複数の検索条件に対応した複数のビットマップ列を抽出し、抽出した複数のビットマップ列のそれぞれ対応する位置に割り当てられたビットについて、ビットワイズ演算を行うことでビットマップを算出するものである。本実施形態では、ビットマップ算出手段１５は、インデックス取得制御手段１６の制御の下、処理対象とするインデックスｋ段目のビットマップ表（圧縮されていた場合には解凍後）より抽出した複数のビットマップ列について、ビットワイズ演算を実行する。ここで、ビットワイズ演算とは、入力された検索条件が「ＡＮＤ検索」の場合には論理積をとることを指し、一方、入力された検索条件が「ＯＲ検索」の場合には、論理和をとることを指す。
【００５３】
インデックス取得制御手段１６は、前記したインデックス獲得手段１３、解凍手段１４およびビットマップ算出手段１５を統括制御するものである。本実施形態では、インデックス取得制御手段１６は、インデックス獲得手段１３で獲得されたインデックスのｋ段目のビットマップ表に格納されたデータが圧縮されているか否かを判別し、圧縮されている場合には解凍手段１４に解凍させてから、ビットマップ算出手段１５に出力し、一方、そうでない場合には、そのままビットマップ算出手段１５に出力する。また、インデックス取得制御手段１６は、インデックス獲得手段１３で獲得されたインデックスのｋ段目のビットマップ表の次に（下に）さらにビットマップ表が存在するか否かを判別し、次に（下に）さらにビットマップ表が存在する場合に、インデックス獲得手段１３に対して同様の処理を繰り返させ、一方、次に（下に）さらにビットマップ表が存在しない場合に、その時点においてビットマップ算出手段１５で算出されているビットマップを後段のビットマップ対応情報抽出手段１２に出力させる。
【００５４】
≪ビットマップ対応情報抽出手段≫
ビットマップ対応情報抽出手段１２は、ビットマップ算出手段１５においてデータの包含関係が最小のビットマップ表について算出されたビットマップに対応する情報（以下、ビットマップ対応情報という）として、複数のドキュメント（検索対象情報）の中から、データの包含関係が最小のビットマップ表について算出されたビットマップにおいていずれか一方のビット（１または０）が割り当てられたビット位置に対応する複数のドキュメント（検索対象情報）を抽出するものである。本実施形態では、ビットマップ対応情報抽出手段１２は、インデックス取得制御手段１６でｋ段目のビットマップ表の次に（下に）さらにビットマップ表が存在しないと判別された場合に、情報格納部７に格納された大量のドキュメントの中から、ビットマップ算出手段１５で算出されたビットマップにおいて「１」のビットが割り当てられたビット位置に対応するドキュメントを抽出する。
【００５５】
＜出力手段＞
出力手段５は、所定の通信インタフェースや出力インタフェースから構成される。この出力手段５は、ビットマップ対応情報抽出手段１２で抽出したドキュメント（検索対象情報）を、例えば、インターネット等の通信ネットワークを介して利用者の使用するＰＣに送信するものである。なお、出力手段５は、ビットマップ対応情報抽出手段１２で抽出したドキュメント（検索対象情報）を、情報検索装置１にケーブルで接続された液晶ディスプレイ等の出力装置Ｄに出力することも可能である。
【００５６】
なお、情報検索装置１は、一般的なコンピュータを、前記した検索条件獲得手段１０、ビットマップ対応情報抽出手段１２、インデックス獲得手段１３、解凍手段１４、ビットマップ算出手段１５およびインデックス取得制御手段１６として機能させる情報検索プログラムを実行することで実現することもできる。これらのプログラムは、通信回線を介して配布することも可能であるし、ＣＤ−ＲＯＭ等の記録媒体に書き込んで配布することも可能である。
【００５７】
［情報検索装置の動作］
図１に示した情報検索装置１の動作について図８を参照（適宜図１参照）して説明する。図８は、図１に示した情報検索装置の動作を示すフローチャートである。まず、情報検索装置１は、検索条件獲得手段１０によって、入力装置Ｍから入力手段２を介して、利用者の欲する情報に関する複数の検索条件を獲得する（ステップＳ１１：検索条件獲得ステップ）。そして、情報検索装置１は、インデックス取得制御手段１６によって、獲得すべきインデックスの段数ｋを初期化してｋ＝１とする（ステップＳ１２）。次に、情報検索装置１は、インデックス獲得手段１３によって、ステップＳ１１で獲得した複数の検索条件に対応するインデックスのｋ段目のビットマップ表を獲得する（ステップＳ１３：インデックス獲得ステップ）。そして、情報検索装置１は、インデックス取得制御手段１６によって、ステップＳ１３で獲得したｋ段目のビットマップ表に格納されたデータが圧縮されているか否かを判別する（ステップＳ１４）。圧縮されていた場合（ステップＳ１４：Ｙｅｓ）、情報検索装置１は、解凍手段１４によって、圧縮されたデータを解凍する（ステップＳ１５：解凍ステップ）。次に、情報検索装置１は、ビットマップ算出手段１５によって、獲得されたｋ段目のビットマップ表から抽出した複数のビットマップ列についてビットワイズ演算を行うことでビットマップを算出する（ステップＳ１６：ビットマップ算出ステップ）。
【００５８】
一方、ステップＳ１４において、ｋ段目のビットマップ表に格納されたデータが圧縮されていなかった場合（ステップＳ１４：Ｎｏ）、情報検索装置１は、ステップＳ１５をスキップして、ステップＳ１６に進む。続いて、情報検索装置１は、インデックス取得制御手段１６によって、現在のインデックスの段数ｋの値に「１」を加算して（ｋ＝ｋ＋１）、新たなｋを取得し（ステップＳ１７）、インデックスのｋ段目のビットマップ表が存在するか否かを判別する（ステップＳ１８）。インデックスのｋ段目のビットマップ表が存在する場合には、ステップＳ１３に戻る。ここで、情報検索装置１は、戻ったときに、前記したステップＳ１６で算出されたビットマップにおいて「１」のビットの立った箇所から、インデックスのｋ段目のビットマップ表の該当するデータを獲得する。
【００５９】
一方、ステップＳ１８において、インデックスのｋ段目のビットマップ表が存在しない場合（ステップＳ１８：Ｎｏ）、情報検索装置１は、ビットマップ対応情報抽出手段１２によって、直前のステップＳ１６で算出されたビットマップ（インデックスの最下段から算出されたビットマップ）に対応したビットマップ対応情報（ドキュメント）を情報格納部７から抽出する（ステップＳ１９：ビットマップ対応情報抽出ステップ）。そして、情報検索装置１は、ステップＳ１９で抽出されたビットマップ対応情報（ドキュメント）を検索結果情報として出力手段５を介して出力装置Ｄに出力する（ステップＳ２０）。
【００６０】
〔具体例〕
次に、具体例を用いて情報検索装置１の検索処理動作の概略を説明する。ここでは、一例として、図４に示したビットマップ表（改変ビットマップ表４０）を元に予め作成されたインデックス（図７に示すインデックスの１段目７１およびインデックスの２段目（最下段）７２）がインデックス格納部６（図１参照）に格納されているものとする。また、改変ビットマップ表４０に対応付けられた各ドキュメントを含む大量のドキュメントが情報格納部７（図１参照）に格納されているものとする。さらに、利用者が入力する検索条件が、図９に示すように、「遠足」と「卵焼き」という２つの語を含み、かつ、「有効期限内」であるドキュメントを検索する場合（ＡＮＤ検索）を想定する。
【００６１】
まず、情報検索装置１の検索条件獲得手段１０は、図９に示す３つの検索条件を獲得する。続いて、インデックス獲得手段１３は、図７に示すインデックスの１段目７１すなわち縮退ビットマップ表５０から、図９に示す３つの検索条件のうちの「遠足」を包含した「条件グループ１」のビットマップ列と、「卵焼き」を包含した「条件グループ２」のビットマップ列と、「有効期限」を包含した「条件グループＭ」のビットマップ列とを獲得する。獲得したビットマップ列を図１０に示す。ここで、図７に示すインデックスの１段目７１すなわち縮退ビットマップ表５０は、データが圧縮されたものではないため、インデックス取得制御手段１６は、解凍手段１４を用いない。そして、ビットマップ算出手段１５では、インデックス獲得手段１３で獲得されたビットマップ列すなわち図１０で示したビットマップ列について論理積演算を実施する。ことのきに算出されたビットマップ（論理積結果）を図１１に示す。
【００６２】
図４に示した改変ビットマップ表４０において「１」のビットの立つ箇所を部分的に密集させたため、縮退ビットマップ表５０（図７に示すインデックスの１段目７１）の「１」のビットの立つ箇所の数が削減されているため、ビットワイズ演算のコストが軽量化（ＣＰＵキャッシュの有効活用）される。さらに、図１１に示すように、ビットマップ演算後も「１」のビットの立つ箇所の数が削減されている。
【００６３】
次に、インデックス取得制御手段１６は、図７に示すインデックスの１段目７１の処理の後で、インデックスの最下段には未だ達していないと判別し、インデックス獲得手段１３に対して、次段のビットマップ表の獲得を指示する。このとき、インデックス取得制御手段１６は、図１１に示したビットマップから、「１」のビットの立った箇所は、「Docグループ２」に対応していることを認識し、インデックス獲得手段１３に対して、次段のビットマップ表の該当データの取得を指示する。
【００６４】
次に、インデックス獲得手段１３は、図７に示すインデックスの２段目（最下段）７２すなわち圧縮ビットマップ表６０において、「Docグループ２」に対応している行のデータを取得する。取得したビットマップの一例を図１２に示す。ここで、「圧縮データ２−１」、「圧縮データ２−２」、「圧縮データ２−Ｍ」は、それぞれが複数の検索条件を包含している。そこで、インデックス取得制御手段１６は、解凍手段１４を用いて「圧縮データ２−１」、「圧縮データ２−２」、「圧縮データ２−Ｍ」を解凍させる。解凍されたビットマップを図１３に示す。ビットマップ算出手段１５は、図１３に示すビットマップから、図９に示した３つの検索条件に対応するビットマップ列を抽出し、論理積演算を実施する。このとき抽出される３つのビットマップ列と、算出されるビットマップ（論理積結果）とを図１４に示す。
【００６５】
次に、インデックス取得制御手段１６は、図７に示すインデックスの２段目７２の処理の後で、インデックスの最下段に達したと判別し、図１４に示すビットマップ（論理積結果）をビットマップ対応情報抽出手段１２に出力する。そして、ビットマップ対応情報抽出手段１２は、図１４に示すビットマップ（論理積結果）において「１」のビットの立った箇所から、全ての検索条件を満たすドキュメントとして、Doc idが「６」であるドキュメント（ドキュメントタイトル＝「お弁当レシピ」：図４参照）を情報格納部７から獲得する。これにより、情報検索装置１は、抽出されたドキュメントを、検索結果情報として出力する。
【００６６】
本実施形態によれば、情報検索装置１は、格納された大量のドキュメント（検索対象情報）と、入力されうる全ての検索条件とを対応づけたビットマップ表から予め作成されたインデックスを用いる。また、インデックスの元になるビットマップ表において、「１」のビットの立つ箇所をグループ単位に密集させたので、圧縮効率を上げると共に、部分解凍をも可能とし、また、縮退後に「１」のビットの立つ箇所の数を削減することができる。ここで、「１」のビットの立つ箇所は、利用者の望む検索対象である可能性が高く、その個数は検索候補を含む検索候補グループの数に相当する。この数を削減すると、ビットマップ演算において「１」のビットの立つ箇所の数が削減される。その結果、少ないリソース（ＣＰＵキャッシュ、メモリ、ディスク）消費でありながら、複数の検索条件を個別に切り離して処理することなくまとめて扱うことを可能にし、検索候補の絞込みを高速に実施することを可能とする。
【００６７】
以上、本発明の実施形態について説明したが、本発明はこれに限定されるものではなく、その趣旨を変えない範囲で実施することができる。例えば、本実施形態では、インデックスの段数を２段としたが、３段以上であってもよい。例えば、図５に示した縮退ビットマップ表５０をさらに縮退させると図１５に示すように、縮退ビットマップ表１５０を構築することができる。縮退ビットマップ表１５０は、項目として、条件グループ１５１と、Docグループ１５２とを備えている。条件グループ１５１の「条件グループ１」は、図５に示した縮退ビットマップ表５０の「条件グループ１」と「条件グループ２」とを「人物」という上位概念で縮退した新たなグループである。また、Docグループ１５２の「Docグループ１」は、図５に示した縮退ビットマップ表５０の「Docグループ１」と「Docグループ２」とを合わせた上位概念（例えば、“趣味”）で縮退した新たなグループである。つまり、符号１５３で示す「１」のビットは、図５に示した縮退ビットマップ表５０の該当する領域のビット（１，０，１，１）に対応している。このように縮退または圧縮を繰り返して３段以上の多段のインデックスを用いることで、複数の検索条件に基づいて、例えば、1000万以上の大量のドキュメントから所望のドキュメントを低消費リソースかつ高速に検索することができる。
【００６８】
また、本実施形態では、インデックスの元にしたビットマップ表において検索条件およびドキュメントをそれぞれ類似したものでグループ化したが、グループ化の基準はこれに限定されるものではない。また、機械的に部分集合あるいはクラスに分類（クラス分け、クラスタリング）する手法としては、一般的に多くの手法があり、その手法にも限定されるものではない。格納される検索対象情報の集合と検索条件の集合との少なくとも一方をクラスタリングすることによりビットマップ上のビットの配置に偏りを出すことができればよい。特に、クラスタリングによって作成される「格納される検索対象情報の集合」のビットの偏りの特徴と、クラスタリングによって作成される「検索条件の集合」のビットの偏りの特徴とが同様になるように両方をクラスタリングすることが好ましい。これは、例えば、ドキュメント側の類似グループ名と、検索条件側の類似グループ名とが、同じグループ名となるようなクラスタリングを実施することで実現できる。
【００６９】
また、本実施形態では、縮退または圧縮する処理を順次施して多段状に構成されたインデックスが、複数のドキュメント（検索対象情報）を内容の類似度に基づいて複数のグループに分け、かつ、複数の検索条件を内容の類似度に基づいて複数のグループに分けたものとしたが、本発明はこれに限定されるものではない。例えば、インデックスにおいて複数の検索条件は、所定の連続値を区切って構成される複数の区間であってもよく、このとき、複数の検索対象情報に関連する情報をそれぞれ数値化した情報が、複数の区間のいずれかに含まれるようにしてもよい。この場合のビットマップ表の一例を図１６に示す。図１６は、価格を検索条件としたビットマップ表の一例を示す図である。ここでは、検索対象情報に関連する情報として、ドキュメントの属性情報としての価格（整数値）を想定している。また、１円から１０万円までの複数のドキュメントがあるものとする。そして、１円から１０万円までの５００円単位の区間が検索条件の１つになっている。これによれば、価格等の数値化した情報のような連続量に対する検索条件であっても、ビットマップインデックスによる検索が可能となる。
【００７０】
また、その他の設計変形例として、情報格納部７（図１参照）に、利用者の欲するドキュメント（検索対象情報）の他、例えば、そのドキュメントに関連する情報や、そのドキュメントへアクセスするためのアドレス（ＵＲＩ：Uniform Resource Identifier）等を格納するようにしてもよい。この場合には、ビットマップ対応情報抽出手段１２（図１参照）は、論理積演算により算出されたビットマップに対応する情報（ビットマップ対応情報）として、利用者の所望するドキュメントの他に、そのドキュメントに関連する情報や、そのドキュメントへアクセスするためのアドレスを獲得する。これにより、情報検索装置１は、ドキュメントと共に、そのドキュメントに関連する情報や、そのドキュメントへアクセスするためのアドレスをも利用者に提示することができる。
【図面の簡単な説明】
【００７１】
【図１】本発明の実施形態に係る情報検索装置を模式的に示す構成図である。
【図２】インデックスを構築する方法の一例を示すフローチャートである。
【図３】インデックスを構築する元となるビットマップ表の一例を示す図である。
【図４】図３に示したビットマップ表をグルーピングにより改変したビットマップ表の一例を示す図である。
【図５】図４に示した改変ビットマップ表を縮退したビットマップ表の一例を示す図である。
【図６】図４に示した改変ビットマップ表を圧縮したビットマップ表の一例を示す図である。
【図７】図６に示した圧縮ビットマップ表の上に図５に示した縮退ビットマップ表を積み上げた多段（２段）のインデックスの一例を示す図である。
【図８】図１に示した情報検索装置の動作を示すフローチャートである。
【図９】２つの単語とドキュメント自身の情報とを含む検索条件の一例を示す図である。
【図１０】図７に示したインデックスの１段目から抽出されたビットマップ列の一例を示す図である。
【図１１】図１０に示したビットマップ列を用いた論理積結果を示す図である。
【図１２】図７に示したインデックスの２段目から抽出されたビットマップ列の一例を示す図である。
【図１３】図１２に示した圧縮データを解凍したデータを示す図である。
【図１４】図１３に示したビットマップ列と獲得された検索条件とを用いた論理積結果を示す図である。
【図１５】図５に示した縮退ビットマップ表をさらに縮退した縮退ビットマップ表の一例を示す図である。
【図１６】価格を検索条件としたビットマップ表の一例を示す図である。
【符号の説明】
【００７２】
１      情報検索装置
２      入力手段
３      記憶手段
４      制御手段
５      出力手段
６      インデックス格納部
７      情報格納部
８      プログラム格納部
１０    検索条件獲得手段
１１    ビットマップ情報算出手段
１２    ビットマップ対応情報抽出手段
１３    インデックス獲得手段
１４    解凍手段
１５    ビットマップ算出手段
１６    インデックス取得制御手段
Ｍ      入力装置
Ｄ      出力装置
【図１】
2009048352.tif 000003
【図２】
2009048352.tif 000004
【図３】
2009048352.tif 000005
【図４】
2009048352.tif 000006
【図５】
2009048352.tif 000007
【図６】
2009048352.tif 000008
【図７】
2009048352.tif 000009
【図８】
2009048352.tif 000010
【図９】
2009048352.tif 000011
【図１０】
2009048352.tif 000012
【図１１】
2009048352.tif 000013
【図１２】
2009048352.tif 000014
【図１３】
2009048352.tif 000015
【図１４】
2009048352.tif 000016
【図１５】
2009048352.tif 000017
【図１６】
2009048352.tif 000018