(57)【要約】【課題】限られたリソースで検索精度を向上させる。【解決手段】検索条件の入力を受け付けて、検索対象の文書集合から文書を検索する文書検索システムであって、入力された検索条件に基づいて、検索語を論理式によって組み合わせた検索式を作成する検索処理制御部と、作成された検索式に基づいて、事前に作成された検索用文字列に対応する文書を検索するインデクス検索部と、作成された検索式に基づいて、文書の全文を検索するスキャン検索部と、インデクス検索部及びスキャン検索部による検索の少なくとも一方の検索の中間結果に関する統計情報を含む実行プロファイルを作成する実行プロファイル取得部とを備える。【選択図】図２
2009064221.tif 000002
【特許請求の範囲】
【請求項１】
検索条件の入力を受け付けて、検索対象の文書集合から文書を検索する文書検索システムであって、
前記入力された検索条件に基づいて、検索語を論理式によって組み合わせた検索式を作成する検索処理制御部と、
前記作成された検索式に基づいて、事前に作成された検索用文字列に対応する文書を検索するインデクス検索部と、
前記作成された検索式に基づいて、前記文書の全文を検索するスキャン検索部と、
前記インデクス検索部及び前記スキャン検索部による検索の少なくとも一方の検索の中間結果に関する統計情報を含む実行プロファイルを作成する実行プロファイル取得部と、を備えることを特徴とする文書検索システム。
【請求項２】
前記検索用文字列が格納されるインデクス検索構造体と、
前記実行プロファイルに基づいて、前記インデクス検索構造体に含まれる検索用文字列を更新する実行プロファイル反映部と、をさらに備えることを特徴とする請求項１に記載の文書検索システム。
【請求項３】
前記実行プロファイルは、前記インデクス検索構造体に含まれる検索用文字列ごとに、前記インデクス検索部による検索の実行前の検索対象の文書数の累計と、前記インデクス検索部による検索によって絞り込まれた文書数の累計とを含むことを特徴とする請求項２に記載の文書検索システム。
【請求項４】
前記実行プロファイルは、前記検索式に含まれる検索語ごとに、前記スキャン検索部による検索の実行前の検索対象の文書数の累計と、前記スキャン検索部による検索によって絞り込まれた文書数の累計とを含むことを特徴とする請求項２に記載の文書検索システム。
【請求項５】
前記インデクス検索構造体は、前記検索用文字列と、前記検索用文字列を含む文書の識別子との対応を含むことを特徴とする請求項２に記載の文書検索システム。
【請求項６】
前記インデクス検索部は、前記検索式に含まれる検索語と前記検索用文字列とを比較することによって、前記検索用文字列に対応する文書を取得することを特徴とする請求項５に記載の文書検索システム。
【請求項７】
前記実行プロファイル取得部は、前記実行プロファイルに基づいて、前記検索用文字列ごとに、前記インデクス検索部による検索の効果を示す値を算出することを特徴とする請求項２に記載の文書検索システム。
【請求項８】
前記実行プロファイル取得部は、前記実行プロファイルに基づいて、前記インデクス検索構造体の構成を変更した場合に、前記インデクス検索部による検索の実行効率の変化を提示することを特徴とする請求項２に記載の文書検索システム。
【請求項９】
前記実行プロファイル反映部は、前記実行プロファイル取得部が前記インデクス検索部による検索の実行効率の変化を提示した後に、前記インデクス検索構造体の構成を変更する指示を受け付け、前記インデクス検索構造体の構成を変更することを特徴とする請求項８に記載の文書検索システム。
【請求項１０】
検索条件の入力を受け付けて、検索対象の文書集合から文書を検索する文書検索システムにおける文書検索方法であって、
前記入力された検索条件に基づいて、検索語を論理式によって組み合わせた検索式を作成し、
前記作成された検索式に基づいて、事前に作成された検索用文字列に対応する文書を検索するインデクス検索を実行し、
前記作成された検索式に基づいて、前記文書の全文を検索するスキャン検索を実行し、
前記インデクス検索及び前記スキャン検索の少なくとも一方の検索の中間結果に関する統計情報を含む実行プロファイルを作成することを特徴とする文書検索方法。
【請求項１１】
前記文書検索システムは、前記検索用文字列が格納されるインデクス検索構造体を含み、
前記文書検索方法は、前記実行プロファイルに基づいて、前記インデクス検索構造体に含まれる検索用文字列を更新することを特徴とする請求項１０に記載の文書検索方法。
【請求項１２】
前記実行プロファイルは、前記インデクス検索構造体に含まれる検索用文字列ごとに、前記インデクス検索の実行前の検索対象の文書数の累計と、前記インデクス検索によって絞り込まれた文書数の累計とを含むことを特徴とする請求項１１に記載の文書検索方法。
【請求項１３】
前記実行プロファイルは、前記検索式に含まれる検索語ごとに、前記スキャン検索の実行前の検索対象の文書数の累計と、前記スキャン検索によって絞り込まれた文書数の累計とを含むことを特徴とする請求項１１に記載の文書検索方法。
【請求項１４】
前記インデクス検索構造体は、前記検索用文字列と、前記検索用文字列を含む文書の識別子との対応を含むことを特徴とする請求項１１に記載の文書検索方法。
【請求項１５】
前記インデクス検索は、前記検索式に含まれる検索語と前記検索用文字列とを比較することによって、前記検索用文字列に対応する文書を取得することを特徴とする請求項１４に記載の文書検索方法。
【請求項１６】
前記文書検索方法は、前記実行プロファイルに基づいて、前記検索用文字列ごとに、前記インデクス検索の効果を示す値を算出することを特徴とする請求項１１に記載の文書検索方法。
【請求項１７】
前記文書検索方法は、前記実行プロファイルに基づいて、前記インデクス検索構造体の構成を変更した場合に、前記インデクス検索の実行効率の変化を提示することを特徴とする請求項１１に記載の文書検索方法。
【請求項１８】
前記文書検索方法は、
前記実行プロファイル取得部が前記インデクス検索部による検索の実行効率の変化が提示された後に、前記インデクス検索構造体の構成を変更するか否かの指示を受け付け、
前記インデクス検索構造体の構成を変更することを特徴とする請求項１７に記載の文書検索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、文書集合から文書を検索する技術に関し、特に、インデクス検索で使用されるインデクスを再構成する技術に関する。
【背景技術】
【０００２】
文書検索は、検索対象となる文書集合から、特定の検索式を満たす部分集合を特定し、当該文書集合に対応する文書番号のリストを取得することを目的とする。文書検索方式には、主としてインデクス型とスキャン型の検索方式が存在する。スキャン型検索方式は、全文検索方式とも呼ばれる。
【０００３】
インデクス型の検索方式では、あらかじめ定められた検索文字列の集合について、各検索文字列を含む文書に対応する文書番号リスト（インデクス）を作成しておく。検索時には、入力された検索式に含まれる検索文字列に対応する文書番号リストを組合せて評価し、最終的な文書番号リストを特定する（非特許文献１）。
【０００４】
一方、スキャン型の検索方式では、入力された検索式にしたがって、個々の文書が検索式を満たすか否かを判定する判定プログラム（オートマトン）を作成し、検索式を満たす文書の文書番号リストを作成する。判定プログラムは、検索式で指定された個々の検索語が検索対象文書に出現するか否かを判定し、さらに、出現した検索後の組合せが検索式を満たすか否かを判定する（非特許文献２、非特許文献３）。
【０００５】
インデクス型検索では、事前に作成したインデクスを参照して対象文書を絞込むため、大量の文書を高速に絞り込むことが可能である。しかし、検索式を検索文字列に分解してから判定するため、複雑な検索語又は検索式に対しては検索時間が増大する。また、検索を高速に実行するため、インデクスサイズをメモリに格納可能な範囲に限定し、検索文字列の出現位置情報を持たないインデクスを用いた場合には、検索結果に本来の検索結果以外の検索ノイズ（本来の検索結果には含まれない文書、例えば、検索語を構成する検索文字列をバラバラに含む文書など）を含むことがある。
【０００６】
一方、スキャン型検索では、判定プログラムを用いて検索対象文書に対して１件ずつ判定するため、検索対象文書数が多い場合には多くの検索時間を必要とする。しかし、検索式が複雑な場合でも検索時間は増大せず、検索結果に検索ノイズを含むことない。
【０００７】
以上のように、両検索方式は、それぞれ検索処理における特性が異なるため、まず、インデクス型検索を用いて検索対象文書を大幅に絞り込んだ後、絞り込んだ結果の文書に対してスキャン型検索を適用するなど、両タイプの検索処理間で処理を分担させるハイブリッド型の検索を実行することにより、高速かつ検索ノイズの無い検索処理を実現することができる。従来知られている階層型検索方式も、前段のインデクスとして文字成分表を用いたハイブリッド型検索として分類することができる。
【非特許文献１】「情報検索アルゴリズム」, 共立出版, 2002年出版, 北 研二，津田 和彦，獅子堀 正幹著, pp.160-179.
【非特許文献２】Aho, A. V. and Corasick, M. J., “Efficent string matching: an aid to bibliographic search”, CACM, 18(6), pp.333-340, 1975.
【非特許文献３】Commentz-Walter, B., “A string matching algorithm fast on the average”, In Proceedings of the 6th International Colloquium on Automata, Languages and Programming. LNCS71, pp.118-132, 1979.
【発明の開示】
【発明が解決しようとする課題】
【０００８】
ハイブリッド型検索の前段にあたるインデクス検索においては、インデクスを構成する検索文字列の範囲を拡大することによって、より多くの検索式を利用して文書を効率的に絞込むことができる一方、インデクス保持のために使用されるメモリ量が増大する。限られたリソース内でより効率的な検索処理を実現するためには、インデクスサイズ（検索文字列と対応する文書番号リストを保持する構造体のサイズ）をメモリに格納可能な範囲に限定しながら、入力された検索式集合に対して、効率良く検索対象文書を絞り込むことができる最適なインデクスを構成する文字列の集合を決定することが重要である。
【０００９】
また、検索対象文書又は検索式の事前解析結果に基づいてインデクスを構成する検索文字列の集合を決定した場合には、検索対象文書の追加又は削除、あるいは新たな検索語の登場及び利用者のニーズの変化などによって、検索対象文書又は検索式の特性が当初の前提から外れてきた場合には、検索効率維持のために適当なタイミングでインデクスを再構成するための手間が必要であるという課題が存在する。
【課題を解決するための手段】
【００１０】
本発明の代表的な一形態では、検索条件の入力を受け付けて、検索対象の文書集合から文書を検索する文書検索システムであって、前記入力された検索条件に基づいて、検索語を論理式によって組み合わせた検索式を作成する検索処理制御部と、前記作成された検索式に基づいて、事前に作成された検索用文字列に対応する文書を検索するインデクス検索部と、前記作成された検索式に基づいて、前記文書の全文を検索するスキャン検索部と、前記インデクス検索部及び前記スキャン検索部による検索の少なくとも一方の検索の中間結果に関する統計情報を含む実行プロファイルを作成する実行プロファイル取得部とを備える。
【発明の効果】
【００１１】
本発明の一形態によれば、実行プロファイルを利用することによって、インデクス検索の精度を向上させることができる。例えば、実行プロファイルに基づいて、インデクスの構成を更新することによって、インデクス検索の精度を向上させることができる。
【発明を実施するための最良の形態】
【００１２】
以下に図面を参照しながら本発明の実施の形態を説明する。
【００１３】
図１Ａは、本発明の実施の形態の文書検索システムのシステム構成を示す図である。
【００１４】
文書検索システム１０１は、検索サーバ１０及び入出力装置１２を含む。検索サーバ１０及び入出力装置１２は、ネットワーク１１を介して接続される。
【００１５】
検索サーバ１０は、入出力装置１２から入力された検索条件に基づいて、要求された文書を検索する。入出力装置１２は、利用者から入力された検索条件を検索サーバ１０に送信し、検索結果を表示する。
【００１６】
検索サーバ１０は、ＣＰＵ１３及びメモリ１４を含む。ＣＰＵ１３は、メモリ１４に記憶されたプログラムを処理することによって、各種処理を実行する。メモリ１４は、各種処理を実行するプログラムと、当該プログラムの実行に必要なデータを記憶する。
【００１７】
検索サーバ１０は、インデクス検索構造体１２３、実行プロファイル情報１４２、検索対象文書格納位置情報１６２を格納する。
【００１８】
インデクス検索構造体１２３は、検索対象の文書に対応するインデクス検索用の文字列と文書の識別子との対応を含む。インデクス検索構造体１２３の詳細については、図３にて後述する。
【００１９】
実行プロファイル情報１４２は、インデクス検索又はスキャン検索の中間結果を格納する。実行プロファイル情報１４２の詳細については、図６Ａ及び図６Ｂにて後述する。
【００２０】
検索対象文書格納位置情報１６２は、検索対象の文書が格納されている領域が記録される。検索対象文書格納位置情報１６２の詳細については、図４にて後述する。
【００２１】
検索サーバ１０は、さらに、検索処理制御部１１０、インデクス検索部１２０、スキャン検索部１３０、実行プロファイル取得部１４０、実行プロファイル反映部１５０、検索対象文書管理部１６０及び検索対象文書格納部１７０を格納する。
【００２２】
検索処理制御部１１０、インデクス検索部１２０、スキャン検索部１３０、実行プロファイル取得部１４０、実行プロファイル反映部１５０及び検索対象文書管理部１６０は、ＣＰＵ１３によって実行されるプログラムである。
【００２３】
検索処理制御部１１０は、入出力装置１２に入力された検索式を受信し、検索処理を実行する。また、検索処理制御部１１０は、検索結果を入出力装置１２に送信する。
【００２４】
インデクス検索部１２０は、インデクス検索を実行する。スキャン検索部１３０は、スキャン検索を実行する。
【００２５】
実行プロファイル取得部１４０は、インデクス検索及びスキャン検索の中間結果を記録する実行プロファイルを作成し、実行プロファイル情報１４２に格納する。実行プロファイル反映部１５０は、実行プロファイル情報１４２に格納された実行プロファイルに基づいて、インデクス検索構造体１２３を更新する。
【００２６】
検索対象文書管理部１６０は、検索対象文書群１０２から格納位置を取得し、検索対象文書格納位置情報１６２に記録する。
【００２７】
検索対象文書格納部１７０は、検索対象文書が記憶される領域である。検索対象文書格納部１７０は、メモリ１４に割り当てられた記憶領域である。
【００２８】
図１Ｂは、本発明の実施の形態の処理の流れを含むシステム構成図である。
【００２９】
本発明の実施の形態の文書検索システム１０１は、図１Ａに示したように、検索処理制御部１１０、インデクス検索部１２０、スキャン検索部１３０、実行プロファイル取得部１４０、実行プロファイル反映部１５０、検索対象文書管理部１６０及び検索対象文書格納部１７０を含む。なお、太線で囲われた部分は、本発明の特徴的な処理を実行する部分を示している。
【００３０】
検索処理制御部１１０は、検索式分配手段１１１及び検索結果変換手段１１２を備える。検索式分配手段１１１は、利用者から入力された検索式１００を、それぞれインデクス型検索及びスキャン型検索に適した検索式に変換し、インデクス検索部１２０及びスキャン検索部１３０に送信する。また、文書検索システム全体の処理タイミングを調整する。検索結果変換手段１１２は、スキャン検索部１３０から受信した検索結果を利用者が理解可能な形式に変換して検索結果１０３として出力する。
【００３１】
インデクス検索部１２０は、インデクス作成手段１２１及びインデクス検索手段１２２を備える。インデクス作成手段１２１は、検索対象文書群１０２を参照して、インデクス検索構造体１２３を作成する。さらに、インデクス検索手段１２２は、検索式分配手段１１１から送信されたインデクス検索用検索式に基づいて、インデクス検索構造体１２３を参照してインデクス検索を実行し、インデクス検索結果文書番号集合を生成する。
【００３２】
スキャン検索部１３０は、スキャン検索手段１３１を備える。スキャン検索手段１３１は、検索式分配手段１１１から送信されたスキャン検索用検索式に基づいて、検索対象文書管理部１６０から受信した文書本体にスキャン検索を実行し、検索結果を検索結果変換手段１１２に送信する。
【００３３】
実行プロファイル取得部１４０は、実行プロファイル取得手段１４１及び実行プロファイル情報１４２を備える。実行プロファイル取得手段１４１は、検索実行時にインデクス検索手段１２２及びスキャン検索手段１３１から検索処理の実行情報を収集し、実行プロファイル情報１４２として保存する。
【００３４】
実行プロファイル反映部１５０は、実行プロファイル反映手段１５１を備える。実行プロファイル反映手段１５１は、実行プロファイル情報１４２に基づいて、インデクス検索構造体１２３を更新する。
【００３５】
検索対象文書管理部１６０は、検索対象文書格納手段１６１、検索対象文書格納位置情報１６２、検索対象文書格納位置管理手段１６３、及び検索対象文書取得手段１６４を備える。
【００３６】
検索対象文書格納手段１６１は、検索対象文書群１０２を参照し、検索対象文書格納部１７０に格納するとともに、個々の文書番号と格納位置情報の対を検索対象文書格納位置情報１６２として保存する。
【００３７】
検索対象文書格納位置管理手段１６３は、検索対象文書格納位置情報１６２を参照し、インデクス検索手段１２２が生成したインデクス検索結果文書番号集合に含まれる個々の文書番号から文書格納位置情報を取得し、検索対象文書取得手段１６４に送信する。
【００３８】
検索対象文書取得手段１６４は、検索対象文書格納位置管理手段１６３から受信した文書格納位置情報に基づいて、検索対象文書格納部１７０から文書本体を取得し、スキャン検索手段１３１に送信する。
【００３９】
図２は、本発明の実施の形態の文書検索システムにおける検索処理の手順を示すフローチャートである。なお、太線で囲われた処理は、本発明の特徴的な処理を示している。
【００４０】
本発明の実施の形態の文書検索システム１０１では、システムの起動に先立って、検索サーバ１０のＣＰＵ１３が、初期インデクス検索構造体を作成し（ステップ２０１）、さらに、検索対象文書格納位置情報１６２を作成する（ステップ２０２）。
【００４１】
図３は、本発明の実施の形態のインデクス検索構造体１２３を示す図である。
【００４２】
インデクス検索構造体１２３は、インデクス検索文字列３０１、文書出現回数３０２及び文書番号リスト３０３を含む。
【００４３】
インデクス検索文字列３０１は、インデクス検索に用いられる最小の単位の文字列である。インデクス検索文字列３０１は、事前に指定され、検索対象の文書に出現するすべての２文字の組合せ（2gram）を抽出して利用してもよいし、検索応用向けに作成された文字列辞書（形態素）をそのまま用いてもよい。
【００４４】
本発明の実施の形態では、初期インデクス検索構造体として、検索対象の文書に出現するすべての２文字の組合せ（2gram）をインデクス検索文字列として利用する。そして、ステップ２０１の処理において、検索サーバ１０のＣＰＵ１３がインデクス作成手段１２１を実行することによって、初期のインデクス検索構造体１２３を作成する。
【００４５】
文書出現回数３０２は、ＤＦ値とも呼ばれ、インデクス検索文字列３０１を含む文書の個数である。文書番号リスト３０３は、対応するインデクス検索文字列を含む文書の文書番号の一覧が文書番号順にソートされたリストである。
【００４６】
図４は、本発明の実施の形態の検索対象文書格納位置情報１６２の一例を示す図である。
【００４７】
検索対象文書格納位置情報１６２は、文書番号４０１及び格納位置情報４０２を含む。文書番号４０１は、検索対象の文書を識別する識別子である。格納位置情報４０２は、｛格納開始位置、文書サイズ｝のペアを含む。
【００４８】
本発明の実施の形態では、検索対象文書格納部１７０は、メモリ１４に格納される。そこで、検索サーバ１０のＣＰＵ１３は、ステップ２０２の処理において、検索対象文書格納手段１６１を実行することによって、検索対象文書群を順次メモリに配置しながら、格納開始位置と文書サイズとを対にして検索対象文書格納位置情報１６２に登録する。
【００４９】
ここで、図２のフローチャートの説明に戻る。
【００５０】
検索サーバ１０のＣＰＵ１３は、利用者からの各種要求入力を受け付ける（ステップ２０３）。本発明の実施の形態では、１）指定した検索式に従った検索処理の実施を指示する検索要求、２）インデクスの再構成を指示するインデクス構成変更要求、３）システム全体の終了を指示する終了要求の３種類の要求が入力される。検索サーバ１０のＣＰＵ１３は、入力された要求に基づいて処理を分岐させる（ステップ２０４）。
【００５１】
まず、検索要求が入力された場合について説明する（ステップ２０４の結果が「検索要求」）。本発明の実施の形態では、検索要求が入力された場合には、さらに、検索式の入力を受け付ける。入力される検索式は、検索語をＡＮＤ（＊）、ＯＲ（｜）、括弧（‘(’，‘)’）などの論理式によって組合せたものである。
【００５２】
図５Ａは、本発明の実施の形態の文書検索システムに検索式を入力する画面の一例を示す図である。
【００５３】
図５Ａに示す画面は、検索式を入力するための画面である。検索文字列入力欄５１１に検索文字列が入力され、検索実行ボタン５１２が操作されると、検索処理が実行される。検索文字列の入力を中止する場合には、ボタン５１３を操作することによって、処理を中止する。処理が中止されると、検索サーバ１０のＣＰＵ１３は、ステップ２０３の処理を実行し、利用者からの要求を受け付ける。
【００５４】
図５Ａに示す画面の検索文字列入力欄５１１には、検索式‘液体窒素’｜‘固体窒素’が入力されている。入力された検索式は、検索対象文書中に‘液体窒素’又は‘固体窒素’という検索語を含む文書集合を検索することを意味している。
【００５５】
ここで、図２のフローチャートの説明に戻る。
【００５６】
検索サーバ１０のＣＰＵ１３は、検索式分配処理によって、入力された検索式をインデクス検索用検索式とスキャン検索用検索式に変換する（ステップ２０５）。
【００５７】
図５Ｂは、本発明の実施の形態の検索式分配処理の手順を示すフローチャートである。本処理は、図２のステップ２０５の処理に対応する。
【００５８】
検索サーバ１０のＣＰＵ１３は、検索式分配手段１１１を実行し、検索式の入力を受け付ける（ステップ５０２）。
【００５９】
検索サーバ１０のＣＰＵ１３は、インデクス検索構造体を構成するインデクス検索文字列を参照し、入力された検索式を分解し、インデクス検索文字列の組合せに関する論理式に変換する（ステップ５０３）。
【００６０】
例えば、図３に示したように、インデクス検索文字列として2gramを採用したインデクス検索構造体を用いると、図５Ａに示した検索式‘液体窒素’｜‘固体窒素’を変換する場合、変換後のインデクス検索用検索式は、（（‘液体’＊‘体窒’＊‘窒素’）｜（‘固体’＊‘体窒’＊‘窒素’））となる。
【００６１】
また、スキャン検索用検索式に変換する場合には、ステップ５０２の処理で入力された検索式を大きく変更する必要はない（ステップ５０５）。例えば、入力された検索式が‘液体窒素’｜‘固体窒素’の場合には、そのままスキャン検索用検索式として用いることができる。
【００６２】
ここで、図２のフローチャートの説明に戻る。
【００６３】
検索サーバ１０のＣＰＵ１３は、インデクス検索手段１２２を実行し、検索式分配処理によって変換されたインデクス検索用検索式に基づいて、インデクス検索処理を実行する（ステップ２０６）。インデクス検索処理では、インデクス検索用検索式に含まれるすべてのインデクス検索文字列について、対応する文書番号リストを取得する。
【００６４】
続いて、検索サーバ１０のＣＰＵ１３は、取得された文書リストを最も若い文書番号から順に参照する。さらに、インデクス検索用検索式に含まれる各インデクス検索文字列に対応する文書番号リストに参照された文書番号が含まれる場合には、当該インデクス検索文字列を‘Ｔ’（真）に変換し、含まれない場合には‘Ｆ’に変換する。そして、変換の結果得られた論理式の評価結果が‘Ｔ’になった場合には、当該文書番号をインデクス検索結果文書番号集合に追加し、‘Ｆ’（偽）になった場合は追加しない。さらに詳細な検索手順については、非特許文献１に詳しく記述されている。
【００６５】
さらに、インデクス検索処理について、図５Ｃを参照しながら具体的に説明する。
【００６６】
図５Ｃは、本発明の実施の形態のインデクス検索処理の概要を説明する図である。
【００６７】
前述のように、検索式‘液体窒素’｜‘固体窒素’を変換する場合に、インデクス検索文字列３０１は‘液体’、‘体窒’、‘窒素’及び‘固体’となる。そして、変換後のインデクス検索用検索式は、（（‘液体’＊‘体窒’＊‘窒素’）｜（‘固体’＊‘体窒’＊‘窒素’））となる。
【００６８】
図５Ｃに示すように、インデクス検索文字列３０１を横に並べ、対応するインデクス検索文字列３０１を含む文書の文書番号リスト３０３を縦に並べる。そして、変換後のインデクス検索用検索式の結果が‘Ｔ’（真）となる文書番号をインデクス検索結果文書番号集合３０４に追加する。
【００６９】
図３を参照すると、文書番号１の文書には、‘液体’、‘体窒’及び‘窒素’が含まれ、‘固体’は含まれていない。そこで、変換後の検索式（（‘液体’＊‘体窒’＊‘窒素’）｜（‘固体’＊‘体窒’＊‘窒素’））の検索文字列を変換すると、変換後のインデクス検索用論理式は（（‘Ｔ’＊‘Ｔ’＊‘Ｔ’）｜（‘Ｆ’＊‘Ｔ’＊‘Ｔ’））となる。したがって、変換後の論理式の評価結果は‘Ｔ’（真）となり、インデクス検索結果文書番号集合３０４に加えられる。さらに、文書番号４について同様に検討すると、変換後のインデクス検索用論理式は、（（‘Ｆ’＊‘Ｆ’＊‘Ｆ’）｜（‘Ｔ’＊‘Ｆ’＊‘Ｆ’））となり、変換後の論理式の評価結果は‘Ｆ’（偽）となるので、インデクス検索結果文書番号集合３０４には加えられない。
【００７０】
以上のように、検索対象のすべての文書に対して、変換後の論理式を評価することによって、文書を検索する。
【００７１】
ここで、図２のフローチャートの説明に戻る。
【００７２】
検索サーバ１０のＣＰＵ１３は、インデクス検索処理の検索内容に基づいて、インデクス検索処理の実行プロファイルを更新する（ステップ２０７）。インデクス検索処理の実行プロファイルの更新処理について、図６Ａを参照しながら説明する。
【００７３】
図６Ａは、本発明の実施の形態のインデクス検索の実行プロファイル情報の一例を示す図である。
【００７４】
インデクス検索の実行プロファイル情報は、インデクス検索文字列６０１、文書出現回数６０２、絞込み前累計文書数６０３、絞込み後累計文書数６０４及び使用リソースサイズ６０５を含む。インデクス検索の実行プロファイル情報の各エントリは、インデクス検索文字列ごとに作成される。
【００７５】
インデクス検索文字列６０１は、インデクス検索文字列が格納される。
【００７６】
文書出現回数６０２は、当該インデクス検索文字列が検索対象文書中に出現する総数である。文書出現回数６０２は、インデクス検索構造体において当該インデクス検索文字列に対応する文書リストの大きさを利用して設定する。
【００７７】
絞込み前累計文書数６０３は、当該インデクス検索文字列の文書番号リストが存在しない場合のインデクス検索中間結果累計件数である。
【００７８】
絞込み前累計文書数６０３は、インデクス検索用検索式を作成する場合に、検索式が複数のインデクス検索文字列に分割される場合には、分割後の各インデクス検索文字列に対応する文書番号リストの和集合に含まれる文書の個数が加算される。また、検索式がインデクス検索用検索式において単一のインデクス検索文字列に変換される場合には、検索対象文書の総数が加算される。
【００７９】
絞込み後累計文書数６０４は、当該インデクス検索文字列の文書番号リストが存在した場合のインデクス検索中間結果累計件数である。すなわち、絞込み後累計文書数６０４は、当該インデクス検索文字列によって検索された文書の個数をインデクス検索が実行されるたびに加算された値である。
【００８０】
絞込み前累計文書数６０３及び絞込み後累計文書数６０４は、インデクス検索を実行するたびにそれぞれ増加する。
【００８１】
使用リソースサイズ６０５は、当該インデクス検索文字列に対応する文書番号リストをメモリ上に保持するために必要なサイズである。
【００８２】
さらに、インデクス検索の実行プロファイル情報について詳細に説明する。総検索対象文書数を１００件とし、単語‘液体窒素’、‘固体窒素’を含む文書がそれぞれ３０件、２０件存在し、両方の単語を含む文書が１０件存在する。他の文書は関連する単語をまったく含まないものとする。
【００８３】
そして、入力される検索式を‘液体’、‘固体’、‘窒素’、‘液体窒素’、‘固体窒素’とする検索をそれぞれ１０回、１５回、５回、３０回、２０回実行する。このとき、インデクス検索文字列‘液体’、‘固体’、‘窒素’、‘体窒’について、絞込み前累計文書数６０３は、それぞれ２２００、２３００、２５００、２０００となる。また、絞込み後累計文書数６０４は、それぞれ１２００、７００、２２００、２０００となる。
【００８４】
具体的な計算過程を説明すると、インデクス検索文字列‘液体’に注目した場合、検索式‘液体窒素’が指定された検索では（検索回数３０回）、インデクス検索用検索式は‘液体’＊‘体窒’＊‘窒素’と変換される。そして、インデクス検索文字列‘液体’、‘体窒’、‘窒素’のいずれかを含む文書数４０件が絞り込み前文書数とされ、論理式の評価結果として得られる文書数３０件が絞込み後文書数とされる。
【００８５】
また、検索式‘液体’（検索回数１０回）が指定された検索では、インデクス検索用検索式は、単体のインデクス検索文字列に変換されるため、全検索対象文書数が絞り込み前文書数とみなされ、論理式を評価した結果、得られる文書３０件が絞り込み後文書数とみなされる。以上より、絞込み前累計文書数については、４０件×３０回＋１００件×１０回＝２２００、絞込み後累計文書数については、３０件×３０回＋３０件×１０回＝１２００という値を得られる。
【００８６】
ここで、図２のフローチャートの説明に戻る。
【００８７】
検索サーバ１０のＣＰＵ１３は、インデクス検索結果文書番号集合に対応する各文書に対してスキャン検索を実行する（ステップ２０８）。スキャン検索処理では、まず、変換されたスキャン用検索式に基づいて、オートマトンを生成する。次に、生成されたオートマトンを使用して対象文書をスキャンし、オートマトンが受理するか否かを判定する。スキャン検索処理のさらに詳細な検索手順については、非特許文献２及び非特許文献３に詳しく記述されている。
【００８８】
検索サーバ１０のＣＰＵ１３は、スキャン検索においてもインデクス検索と同様に、スキャン検索処理の実行プロファイルを更新する（ステップ２０９）。スキャン検索処理の実行プロファイルの更新処理について、図６Ｂを参照しながら説明する。
【００８９】
図６Ｂは、本発明の実施の形態のスキャン検索の実行プロファイル情報の一例を示す図である。
【００９０】
スキャン検索の実行プロファイル情報は、検索文字列７０１、絞込み前累計文書数７０２及び絞り込み後累積文書数７０３を含む。スキャン検索の実行プロファイル情報の各エントリは、検索文字列ごとに作成される。
【００９１】
検索文字列７０１は、スキャン検索文字列が格納される。
【００９２】
絞込み前累計文書数７０２は、スキャン検索において検索対象となった累計文書数である。絞込み前累計文書数７０２は、検索式がインデクス検索用検索式において複数のインデクス検索文字列に分割される場合には、スキャン検索の前に実行されたインデクス検索において分割後の各インデクス検索文字列に対応する文書番号リストの和集合に含まれる文書の個数をスキャン検索実行ごとに累計した値を設定する。また、検索式がインデクス検索用検索式において単一のインデクス検索文字列に変換される場合には、検索対象文書の総数をスキャン検索実行ごとに累計した値を設定する。
【００９３】
絞込み後累計文書数７０３は、スキャン検索によって絞り込まれた結果の累計文書数である。絞込み後累計文書数７０３は、スキャン検索結果文書件数をスキャン検索実行ごとに累計した値を設定する。なお、絞込み前累計文書数７０２及び絞込み後累計文書数７０３は、スキャン検索を実行するたびに増加する。
【００９４】
例えば、前述したインデクス検索が実行された場合に、検索語‘液体窒素’、‘固体窒素’の絞込み前累計文書数は、それぞれ１２００、８００、絞込み後累計文書数は９００、４００となる。
【００９５】
具体的には、検索語を‘液体窒素’として検索した場合、検索式‘液体窒素’（検索回数３０回）が指定された検索では、インデクス検索用検索式は‘液体’＊‘体窒’＊‘窒素’と変換される。そして、インデクス検索文字列‘液体’、‘体窒’、‘窒素’のいずれかを含む文書４０件が絞り込み前文書数とされ、スキャン検索後の評価結果として得られる文書３０件が絞込み後文書数とされる。そのため、絞込み前累計文書数は、４０件×３０回＝１２００、絞込み後累計文書数については、３０件×３０回＝９００という数値が得られる。
【００９６】
検索サーバ１０のＣＰＵ１３は、インデクス検索及びスキャン検索によって絞り込まれた文書について、当該文書番号を結果文書番号集合に追加する。すべての文書番号について判定した後、得られた結果文書番号集合を、対応する各文書に付随する諸情報とともに最終的な検索結果として出力する（ステップ２１０）。検索結果の出力画面の例は、図７にて後述する。
【００９７】
検索サーバ１０のＣＰＵ１３は、検索終了後、次に入力される検索式を受け付ける（ステップ２０４）。
【００９８】
図７は、本発明の実施の形態の文書検索システムの検索結果を出力する画面の一例を示す図である。
【００９９】
図７に示す出力画面には、一例として、公開特許公報の一覧が表示されている。具体的には、検索結果として、文書番号、文書名及び文書タイトルが表示され、さらに、検索された文書の件数が表示されている。
【０１００】
続いて、インデクスの構成を変更する場合について説明する。
【０１０１】
検索サーバ１０のＣＰＵ１３は、検索式入力受付処理において、利用者からインデクス構成の変更要求が入力された場合には（ステップ２０４の結果が「インデクス構成変更要求」）、実行プロファイルを参照し、各インデクス検索文字列及びスキャン検索文字列の貢献度を算出するとともに、インデクス利用効率を算出する（ステップ２１１）。本発明の実施の形態では、以下の計算式に従って貢献度と利用効率を算出する。
【０１０２】
貢献度 ＝（絞込み前累計文書数−絞込み後累計文書数）／ 使用リソース量
利用効率 ＝ インデクス検索文字列の貢献度の総和 ／ 再構成後のインデクス検索文字列の貢献度の総和
貢献度は、絞込み前累計文書数と絞込み後累計文書数との差を、検索処理に使用されたリソース量で割った値と定義する。すなわち、絞込み前累計文書数と絞込み後累計文書数との差が大きければ、効率的に文書を絞り込めたことになる。また、使用リソース量が小さいということは、検索時間及びメモリ使用量などのリソースの消費が少ないことになる。例えば、2gramを採用した場合に検索文字列が短ければ、検索回数が少なくなるため、使用リソースが少なくなる。貢献度は、各インデクス検索文字列をインデクスとした場合のインデクス検索の効果を示す値である。
【０１０３】
インデクス検索文字列の貢献度の総和は、インデクス検索の有効性を示す実行効率である。利用効率は、インデクス検索文字列の貢献度の総和を再構成後のインデクス検索文字列の貢献度の総和で割った値であり、再構築したインデクスの貢献度が大きくなれば、利用効率の値が小さくなる。すなわち、利用効率は、インデクスの再構成前後における実行効率の変化を示している。
【０１０４】
以下、インデクスの構成を変更する手順について説明する。
【０１０５】
図９は、本発明の実施の形態のインデクス検索処理に使用されるインデクスを再構成する手順を示すフローチャートである。
【０１０６】
検索サーバ１０のＣＰＵ１３は、まず、インデクス検索実行プロファイルを参照し、インデクス検索文字列の貢献度を算出する（ステップ９０２）。
【０１０７】
次に、検索サーバ１０のＣＰＵ１３は、スキャン検索実行プロファイルを参照し、スキャン検索文字列の貢献度を算出する（ステップ９０３）。このとき、スキャン検索文字列の使用リソース量については、当該スキャン検索文字列を指定して実行された検索の検索結果件数からの比例計算により算出することが可能である。
【０１０８】
検索サーバ１０のＣＰＵ１３は、各検索処理における貢献度の算出した後、それぞれの検索文字列の貢献度の算出結果をマージした再構成検索文字列集合を、貢献度の大きい順に検索文字列をソートする（ステップ９０４）。このとき、累積使用リソース量を０にリセットする。
【０１０９】
検索サーバ１０のＣＰＵ１３は、再構成検索文字列集合に検索文字列が含まれるか否かを判定する（ステップ９０５）。
【０１１０】
検索サーバ１０のＣＰＵ１３は、再構成検索文字列集合に検索文字列が含まれている場合には（ステップ９０５の結果が「Ｙ」）、ソートされた検索文字列を貢献度順に参照し、最も貢献度の高い検索文字列を一つ選択する（ステップ９０６）。
【０１１１】
検索サーバ１０のＣＰＵ１３は、累積使用リソース量に選択された検索文字列の使用リソース量を加算し、あらかじめ定められた上限リソース量を超えるか否かを判定する（ステップ９０７）。
【０１１２】
検索サーバ１０のＣＰＵ１３は、累積使用リソース量が上限リソース量を超えない場合には（ステップ９０７結果が「Ｎ」）、選択した検索文字列を新しいインデクスを構成する検索文字列として新規検索文字列集合に登録する（ステップ９０８）。さらに、新規検索文字列集合に登録された検索文字列を再構成検索文字列集合から除外して、ステップ９０５の処理を実行する。
【０１１３】
検索サーバ１０のＣＰＵ１３は、再構成検索文字列集合に検索文字列含まれない場合（ステップ９０５の結果が「Ｙ」）、又は累積使用リソース量が上限を超えた場合には（ステップ９０７の結果が「Ｙ」）は、新規検索文字列集合を出力する（ステップ９０９）。その後、本処理を終了する。
【０１１４】
ここで、インデクスの構成を変更する例を具体的に示す。図８Ａ及び図８Ｂに検索文字列絞り込み情報の一例を示す。検索文字列絞り込み情報は、検索文字列８０１、貢献度８０２及び使用リソース量８０３を含む。
【０１１５】
図８Ａは、本発明の実施の形態のインデクス検索文字列絞り込み情報を示す図である。インデクス検索文字列絞り込み情報は、図９のステップ９０２の処理の実行時に作成される。
【０１１６】
図８Ｂは、本発明の実施の形態のスキャン検索文字列絞り込み情報を示す図である。スキャン検索文字列絞り込み情報は、図９のステップ９０３の処理の実行時に作成される。
【０１１７】
検索サーバ１０のＣＰＵ１３は、図９のステップ９０４の処理で図８Ａ及び図８Ｂに示された検索文字列絞込み情報をマージし、再構成検索文字列集合を作成する。そして、再構成検索文字列集合に含まれる各エントリを貢献度８０２の大きい順にソートすると、‘固体’、‘液体’、‘固体窒素’、‘液体窒素’、‘窒素’、‘体窒’の順に格納された再構成検索文字列集合を得る。
【０１１８】
ここで、本発明の実施の形態では、累積使用リソース量が上限を１５０とすると、貢献度の大きい検索文字列を順番に選択し、新規検索文字列集合には、‘固体’、‘液体’、‘固体窒素’、‘液体窒素’、‘窒素’が含まれることとなる。
【０１１９】
以上より、図８Ａ及び図８Ｂを参照すると、インデクス検索文字列‘液体’、‘固体’、‘窒素’、‘体窒’の貢献度は、それぞれ３３．３、８０、７．５、０．０であるため、インデクス利用効率は、１２０．８／１５０．８＝０．８０という結果が得られる。
【０１２０】
ここで、図２のフローチャートの説明に戻る。
【０１２１】
検索サーバ１０のＣＰＵ１３は、貢献度及び利用効率を算出した後、インデクス利用効率を利用者に対して出力するともに、引き続いてインデクスを再構成するか否かの判定を利用者から受け付ける（ステップ２１３）。
【０１２２】
検索サーバ１０のＣＰＵ１３は、インデクスを再構成する場合には（ステップ２１３の結果が「Ｙ」）、新しい検索文字列集合に基づいてインデクス検索構造体１２３を再構成する（ステップ２１４）。インデクスを再構成しない場合（ステップ２１３の結果が「Ｎ」）、インデクスの再構成が終了すると、入力受付処理を実行する（ステップ２０３）。
【０１２３】
最後に、検索サーバ１０のＣＰＵ１３は、入力受付処理において、終了要求を受け付けた場合には（ステップ２０４の結果が「終了要求」）、文書検索システムを終了する。
【０１２４】
本発明の実施の形態によれば、検索処理の実行プロファイルに基づいて、インデクス検索に使用されるインデクス検索構造体を更新することによって、インデクス検索の精度を向上させることができる。
【０１２５】
本発明の実施の形態によれば、インデクスを再構成する場合に、貢献度の高い検索用文字列を優先してインデクス検索構造体に追加し、累積使用リソース量に上限を設けることによって、限られたリソース量で効率的な検索を実行することができる。
【０１２６】
本発明の実施の形態によれば、インデクス検索構造体を再構成する場合に、検索精度の変化を示す指標を提示することができるため、提示された指標に基づいて、利用者がインデクスを再構成するか否かを判断することができる。
【０１２７】
本発明の実施の形態によれば、定期的にインデクスを再構成することによって、検索対象文書の追加又は削除、あるいは、新たな検索語の登場及び利用者のニーズの変化などによって、検索対象文書又は検索式の特性が当初の前提から外れてきた場合であっても検索性能を維持することができる。
【図面の簡単な説明】
【０１２８】
【図１Ａ】本発明の実施の形態の文書検索システムのシステム構成を示す図である。
【図１Ｂ】本発明の実施の形態の処理の流れを含むシステム構成図である。
【図２】本発明の実施の形態の文書検索システムにおける検索処理の手順を示すフローチャートである。
【図３】本発明の実施の形態のインデクス検索構造体を示す図である。
【図４】本発明の実施の形態の検索対象文書格納位置情報の一例を示す図である。
【図５Ａ】本発明の実施の形態の文書検索システムに検索式を入力する画面の一例を示す図である。
【図５Ｂ】本発明の実施の形態の検索式分配処理の手順を示すフローチャートである。
【図５Ｃ】本発明の実施の形態のインデクス検索処理の概要を説明する図である。
【図６Ａ】本発明の実施の形態のインデクス検索の実行プロファイル情報の一例を示す図である。
【図６Ｂ】本発明の実施の形態のスキャン検索の実行プロファイル情報の一例を示す図である。
【図７】本発明の実施の形態の文書検索システムの検索結果を出力する画面の一例を示す図である。
【図８Ａ】本発明の実施の形態のインデクス検索文字列絞り込み情報を示す図である。
【図８Ｂ】本発明の実施の形態のスキャン検索文字列絞り込み情報を示す図である。
【図９】本発明の実施の形態のインデクス検索処理に使用されるインデクスを再構成する手順を示すフローチャートである。
【符号の説明】
【０１２９】
１０    検索サーバ
１１    ネットワーク
１２    入出力装置
１３    ＣＰＵ
１４    メモリ
１００    検索式
１０１    文書検索システム
１０２    検索対象文書群
１０３    検索結果
１１０    検索処理制御部
１１１    検索式分配手段
１１２    検索結果変換手段
１２０    インデクス検索部
１２１    インデクス作成手段
１２２    インデクス検索手段
１２３    インデクス検索構造体
１３０    スキャン検索部
１３１    スキャン検索手段
１４０    実行プロファイル取得部
１４１    実行プロファイル取得手段
１４２    実行プロファイル情報
１５０    実行プロファイル反映部
１５１    実行プロファイル反映手段
１６０    検索対象文書管理部
１６１    検索対象文書格納手段
１６２    検索対象文書格納位置情報
１６３    検索対象文書格納位置管理手段
１６４    検索対象文書取得手段
１７０    検索対象文書格納部
【図１Ａ】
2009064221.tif 000003
【図１Ｂ】
2009064221.tif 000004
【図２】
2009064221.tif 000005
【図３】
2009064221.tif 000006
【図４】
2009064221.tif 000007
【図５Ａ】
2009064221.tif 000008
【図５Ｂ】
2009064221.tif 000009
【図５Ｃ】
2009064221.tif 000010
【図６Ａ】
2009064221.tif 000011
【図６Ｂ】
2009064221.tif 000012
【図７】
2009064221.tif 000013
【図８Ａ】
2009064221.tif 000014
【図８Ｂ】
2009064221.tif 000015
【図９】
2009064221.tif 000016