(57)【要約】【課題】本開示の一側面においては、同じファイルに含まれる他の文字情報の存在により、ある文字情報を含まないにも関わらず、ある文字情報の検索対象と判断されることの抑制を目的とする。【解決手段】  コンピュータが、第１の文字情報および第１のファイルの識別情報により示される記憶領域であって、前記第１のファイルと異なる第２のファイルが第２の文字情報を含むか否かを示す情報を記憶する記憶領域に、前記第１のファイルが前記第１の文字情報を含むことまたは前記第２ファイルが第２の文字情報を含むことのいずれかを満たすか否かを示す存否情報を記憶する。
2013175537.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータに、
第１の文字情報および第１のファイルの識別情報により示される記憶領域であって、前記第１のファイルと異なる第２のファイルが第２の文字情報を含むか否かを示す情報を記憶する記憶領域に、前記第１のファイルが前記第１の文字情報を含むことまたは前記第２ファイルが第２の文字情報を含むことのいずれかを満たすか否かを示す存否情報を記憶する、
処理を実行させることを特徴とする記憶プログラム。
【請求項２】
前記第２の文字情報は、前記第１の文字情報と異なる、
ことを特徴とする付記１に記載の記憶プログラム。
【請求項３】
前記第１のファイルは、前記第２のファイルよりもファイルサイズが大きい、
ことを特徴とする付記１または付記２に記載の記憶プログラム。
【請求項４】
前記コンピュータに、さらに、
前記第１の文字情報および前記第１のファイルの識別情報により示され、前記第１のファイル及び前記第２のファイルと異なる第３のファイルが第３の文字情報を含むか否かを示す情報を記憶する、他の記憶領域に、前記第１のファイルが前記第１の文字情報を含むことまたは前記第２のファイルが第２の文字情報を含むことのいずれかを満たすか否かを示す他の存否情報を記憶する、
処理を実行させることを特徴とする付記１〜３のいずれか１項に記載の記憶プログラム。
【請求項５】
前記記憶領域は、前記第１の文字情報および前記識別情報に基づき算出される第１の数値により示され、
前記コンピュータに、さらに、
前記第１のファイルと異なる第４のファイルの識別情報及び前記第１の文字情報に基づき算出され、且つ前記第１の数値の次の数値である、第２の数値に示される別の記憶領域に、前記第４のファイルに前記第１の文字情報が含まれるか否かを示す別の存否情報を記憶する、
処理を実行させることを特徴とする付記１〜４のいずれか１項に記載の記憶プログラム。
【請求項６】
前記第２の数値は前記第１の数値よりも１大きい、
ことを特徴とする付記５に記載の記憶プログラム。
【請求項７】
前記記憶領域は、前記第１の文字情報及び前記識別情報を変換して得られる引数を所定の関数に代入して得られる数値に示される領域である、
ことを特徴とする付記１〜３のいずれか１項に記載の記憶プログラム。
【請求項８】
前記引数は、前記第１の文字情報に所定の変換を行なって得られる情報と、前記識別情報との和により得られ、
前記所定の関数は、前記和を所定数で割った剰余を算出する関数である、
ことを特徴とする付記７に記載の記憶プログラム。
【請求項９】
コンピュータに、
第１の文字情報および第１のファイルの識別情報により示される記憶領域であって、前記第１のファイルと異なる第２のファイルが第２の文字情報を含むか否かを示す情報を記憶する記憶領域に、前記第１のファイルが前記第１の文字情報を含むことまたは前記第２ファイルが第２の文字情報を含むことのいずれかを満たすか否かを示す存否情報を記憶する、
ことを実行させることを特徴とする記憶方法。
【請求項１０】
記憶部と、
第１の文字情報および第１のファイルの識別情報により示される前記記憶部内の記憶領域であって、前記第１のファイルと異なる第２のファイルが第２の文字情報を含むか否かを示す情報を記憶する記憶領域に、前記第１のファイルが前記第１の文字情報を含むことまたは前記第２ファイルが第２の文字情報を含むことのいずれかを満たすか否かを示す存否情報を記憶させる制御を行なう制御部、
を含むことを特徴とする記憶装置。
【請求項１１】
メモリと、
第１の文字情報および第１のファイルの識別情報により示される前記メモリ内の記憶領域であって、前記第１のファイルと異なる第２のファイルが第２の文字情報を含むか否かを示す情報を記憶する記憶領域に、前記第１のファイルが前記第１の文字情報を含むことまたは前記第２ファイルが第２の文字情報を含むことのいずれかを満たすか否かを示す存否情報を記憶させる、
処理を実行するプロセッサと、
を含む記憶装置。
【請求項１２】
コンピュータに、
第１の文字情報を含む検索要求を受けた場合に、前記第１の文字情報および第１のファイルの識別情報により示される記憶領域から、前記第１のファイルが前記第１の文字情報を含むこと、または前記第１のファイルと異なる第２のファイルが第２の文字情報を含むことのいずれかの条件を満たすか否かを示す存否情報を読み出し、
読み出した前記存否情報が前記いずれかの条件を満たす旨を示す場合に、前記第１のファイルを、前記第１の文字情報について文字列検索を行なう、
処理を実行させることを特徴とする検索プログラム。
【請求項１３】
コンピュータに、
第１の文字情報を含む検索要求を受けた場合に、前記第１の文字情報および第１のファイルの識別情報により示される記憶領域から、前記第１のファイルが前記第１の文字情報を含むこと、または前記第１のファイルと異なる第２のファイルが第２の文字情報を含むことのいずれかの条件を満たすか否かを示す存否情報を読み出し、
読み出した前記存否情報が前記いずれかの条件を満たす旨を示す場合に、前記第１のファイルを、前記第１の文字情報について文字列検索を行なう、
ことを実行させることを特徴とする検索方法。
【請求項１４】
記憶部と、
第１の文字情報を含む検索要求を受けた場合に、前記第１の文字情報および第１のファイルの識別情報により示される前記記憶部内の記憶領域から、前記第１のファイルが前記第１の文字情報を含むこと、または前記第１のファイルと異なる第２のファイルが第２の文字情報を含むことのいずれかの条件を満たすか否かを示す存否情報を読み出す読出し部と、
読み出した前記存否情報が前記いずれかの条件を満たす旨を示す場合に、前記第１のファイルを、前記第１の文字情報に基づく文字列検索の対象と判断する判断部と、
を含むことを特徴とする検索装置。
【請求項１５】
第１の文字情報および第１のファイルの識別情報により示される記憶領域に、前記第１のファイルが前記第１の文字情報を含むこと、または前記第１のファイルと異なる第２のファイルが第２の文字情報を含むことのいずれかの条件を満たすか否かを示す存否情報を記憶するメモリと、
前記第１の文字情報を含む検索要求を受けた場合に、前記存否情報を読出し、
読み出した前記存否情報が前記いずれかの条件を満たす旨を示す場合に、前記第１のファイルを、前記第１の文字情報に基づく文字列検索の対象と判断する、
処理を実行するプロセッサと、
を含む検索装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、検索技術に関する。
【背景技術】
【０００２】
全文検索において、検索文字列内の文字情報がファイル群のうちのいずれのファイルに含まれているかの対応関係を示すインデックス情報を用いて、検索対象ファイルを絞り込む技術がある。例えば、検索文字列にある文字情報Ｃが含まれる場合に、予め生成されたインデックス情報に文字情報Ｃを含むことが示されるファイルが、検索文字列に基づく文字列検索の検索対象となる。その一方で、前述の文字情報Ｃを含まないことがインデックス情報に示されているファイルには、文字列検索が行なわれなくとも、そのファイルが検索文字列を含まないことは明らかである。そのため、インデックス情報に文字情報Ｃを含むことが示されないファイルは、文字列検索の対象から除かれる。【０００３】
各ファイルに対してビットを割り当て、割り当てられた各ビットの値により、文字情報がファイル群のうちのいずれのファイルに含まれているかを示すインデックス情報がある。そのインデックス情報では、ビットがファイル番号順に並んだビット列が各文字情報に対応する。ビット列中で値が「１」であるビットに対応するファイル番号のファイルには、そのビット列に対応する文字情報が存在する。一方、値が「０」であるビットに対応するファイル番号の対象ファイルには、そのビット列に対応する文字情報は存在しない。 【０００４】
文字情報ごとにビット列が対応するため、インデックス情報が対象とする文字情報の種類が多くなると、インデックス情報のデータサイズも大きくなる。それに対し、複数種類の文字情報を、１つのビット列と対応付けたインデックス情報を用いる技術がある。この場合、ビットの値が「１」であるファイル番号のファイルは、そのビットを含むビット列に対応する複数種類の文字情報のうちの少なくとも１つを含む。また、ビットの値が「０」であるファイル番号のファイルは、そのビットを含むビット列に対応する複数種類の文字情報のいずれも含まない。各ビット列には値（アドレス）が割り当てられており、文字情報に対応するビット列を示すアドレスは、文字情報をハッシュ関数に代入して得られる。そのため、ハッシュ関数に代入すると同じ値が得られる文字情報同士は、同じビット列と対応づけられる。【０００５】
複数の文字情報を１つのビット列と対応させたインデックス情報を用いると、ファイルの絞り込みにおいて、ノイズが発生しうる。検索文字列に含まれる文字情報ＣＡに対応するビット列においてビットの値が「１」であったとしても、ビットの値が「１」であるファイル番号のファイルは、文字情報ＣＡは含まず、異なる別の文字情報ＣＢを含むことがあるためである（文字情報ＣＢは、ハッシュ関数に代入すると、文字情報ＣＡをハッシュ関数に代入して得られる値と同じ値が得られる文字情報とする）。この場合、文字情報ＣＡを含まないにも関わらず、ビットの値が「１」であるファイル番号のファイルまでも、文字列検索の対象となる。【０００６】
それに対して、インデックス情報を複数種類用いる技術がある。複数種類のインデックス情報では、互いに異なるハッシュ関数を用いて、文字情報とビット列とが対応付けられる。すると、文字情報ＣＡと文字情報ＣＢは、先述の例では同じビット列に対応付けられていたが、別のハッシュ関数を用いた結果、互いに異なるビット列に対応付けられ得る。複数種類のインデックス情報を用いたファイルの絞り込みは、双方のインデックス情報に含まれる文字情報ＣＡに対応するビット列の論理積（ＡＮＤ）演算により得られるビット列に基づいて行なわれる。文字情報ＣＡに対応し、あるファイル番号に対応するビットの値が、一方のインデックス情報において「１」であり、他方のインデックス情報において「０」であったとすると、論理積演算により得られるビットは「０」である。そのため、そのビットに対応するファイル番号のファイルは、文字情報ＣＡを含まないことが示される。このように、一方のインデックス情報では、同じビット列に対応づけられる文字情報ＣＢの存在により、文字情報ＣＡを含まないと判断できない場合にも、他方のインデックス情報により、文字情報ＣＡを含まないと判断できることがある (例えば、特許文献１及び特許文献２など)。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２０１１−１３８２３０号公報
【特許文献２】特開平３−１２５２６３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、複数種類のインデックス情報を用いても、絞り込みノイズは発生しうる。前述の例における他方のインデックス情報においても、文字情報ＣＡと同じビット列に対応付けられる文字情報ＣＣが存在しうる。文字情報ＣＡを含まず、文字情報ＣＣを含むファイルが存在する場合には、他方のインデックス情報において、そのファイルと文字情報ＣＡと対応するビットは「１」となる。双方のインデックス情報において文字情報ＣＡに対応するビットの値が「１」であると、その論理積（ＡＮＤ）も「１」となる。この例のように、文字情報ＣＡを含まなくとも、文字情報ＣＢと文字情報ＣＣとを含むファイルについては、双方のインデックス情報内のビットの論理積（ＡＮＤ）のビットも「１」となる。そのため、文字情報ＣＡについてのファイル絞り込みにおいて、文字情報ＣＡを含まないファイルも文字列検索の対象ファイルになり得る。すなわち、絞り込みのノイズが発生しうる。このように、複数の文字情報を１つのビット列に対応付けると、同じファイルに含まれる他の文字情報の存在により絞り込みノイズが生じる。【０００９】
ファイル群に含まれる各ファイルが、どの程度多くの種類の文字情報を含むかはファイル次第である。例えば、学術書における索引部分などは文字情報の種類が多くなりがちである。その一方で、本文部分のファイルには、索引部分のファイルと比較してファイルに含まれる文字情報の種類が少ないファイルがある。ファイルに含まれる文字情報の種類が少ないと、ある文字情報と同じビット列に対応付ける他の文字情報がファイル内に存在することにより、ある文字情報がファイル内に存在しないことがインデックス情報に示されなくなる事態は生じにくい。そういったファイルよりも文字情報の種類が多いファイルは、文字情報の種類が少ないファイルに比べて、同じファイル内の他の文字情報の存在により、絞り込みノイズが発生しやすくなる。【００１０】
本開示の一側面においては、同じファイルに含まれる他の文字情報の存在により、検索文字列中の文字情報を含まないにも関わらず、検索文字列による文字列検索の対象と判断されることの抑制を目的とする。
【課題を解決するための手段】
【００１１】
一態様として、開示の記憶プログラムは、コンピュータに、第１の文字情報および第１のファイルの識別情報により示される記憶領域であって、前記第１のファイルと異なる第２のファイルが第２の文字情報を含むか否かを示す情報を記憶する記憶領域に、前記第１のファイルが前記第１の文字情報を含むことまたは前記第２ファイルが第２の文字情報を含むことのいずれかを満たすか否かを示す存否情報を記憶する、処理を実行させる。【００１２】
一態様として、開示の記憶方法においては、コンピュータに、第１の文字情報および第１のファイルの識別情報により示される記憶領域であって、前記第１のファイルと異なる第２のファイルが第２の文字情報を含むか否かを示す情報を記憶する記憶領域に、前記第１のファイルが前記第１の文字情報を含むことまたは前記第２ファイルが第２の文字情報を含むことのいずれかを満たすか否かを示す存否情報を記憶する、ことを実行させる。【００１３】
一態様として、開示の記憶装置は、記憶部と、第１の文字情報および第１のファイルの識別情報により示される記憶部内の記憶領域であって、前記第１のファイルと異なる第２のファイルが第２の文字情報を含むか否かを示す情報を記憶する記憶領域に、前記第１のファイルが前記第１の文字情報を含むことまたは前記第２ファイルが第２の文字情報を含むことのいずれかを満たすか否かを示す存否情報を記憶させる制御を行なう制御部、を含む。【００１４】
一態様として、開示の検索プログラムは、コンピュータに、第１の文字情報を含む検索要求を受けた場合に、前記第１の文字情報および第１のファイルの識別情報により示される記憶領域から、前記第１のファイルが前記第１の文字情報を含むこと、または前記第１のファイルと異なる第２のファイルが第２の文字情報を含むことのいずれかの条件を満たすか否かを示す存否情報を読み出し、読み出した前記存否情報が前記いずれかの条件を満たす旨を示す場合に、前記第１のファイルを、前記第１の文字情報について文字列検索を行なう、処理を実行させる。【００１５】
一態様として、開示の検索方法においては、コンピュータに、第１の文字情報を含む検索要求を受けた場合に、前記第１の文字情報および第１のファイルの識別情報により示される記憶領域から、前記第１のファイルが前記第１の文字情報を含むこと、または前記第１のファイルと異なる第２のファイルが第２の文字情報を含むことのいずれかの条件を満たすか否かを示す存否情報を読み出し、読み出した前記存否情報が前記いずれかの条件を満たす旨を示す場合に、前記第１のファイルを、前記第１の文字情報について文字列検索を行なう、ことを実行させる。【００１６】
一態様として、開示の検索装置は、記憶部と、第１の文字情報を含む検索要求を受けた場合に、前記第１の文字情報および第１のファイルの識別情報により示される前記記憶部内の記憶領域から、前記第１のファイルが前記第１の文字情報を含むこと、または前記第１のファイルと異なる第２のファイルが第２の文字情報を含むことのいずれかの条件を満たすか否かを示す存否情報を読み出す読出し部と、読み出した前記存否情報が前記いずれかの条件を満たす旨を示す場合に、前記第１のファイルを、前記第１の文字情報の文字列検索の対象と判断する判断部と、を含む。
【発明の効果】
【００１７】
本発明の一側面においては、同じファイルに含まれる他の文字情報の存在により、検索文字列中の文字情報を含まないにも関わらず、検索文字列による文字列検索の対象と判断されることを抑制する。
【図面の簡単な説明】
【００１８】
【図１Ａ−Ｂ】図１Ａ及びＢは、インデックス情報と、インデックス情報内のビット列同士の論理積演算との例を示す。
【図２】図２は、複数のインデックス情報を用いたファイル絞り込み処理を示す。
【図３Ａ−Ｂ】図３Ａ及びＢは、関数ｆに代入される引数と、インデックス情報との例を示す。
【図４】図４は、コンピュータ１の機能ブロックの例を示す。
【図５】図５は、生成部１３の機能ブロックの例を示す。
【図６】図６は、絞込部１５の機能ブロックの例を示す。
【図７】図７は、コンピュータ１のハードウェア構成例を示す。
【図８】図８は、コンピュータ１で動作するソフトウェア構成例を示す。
【図９】図９は、インデックス生成の処理手順例を示す。
【図１０】図１０は、全文検索の処理手順例を示す。
【図１１】図１１は、インデックス情報の参照処理手順例を示す。
【図１２】図１２は、ファイル番号とファイルパスとの対応関係を示す。
【図１３】図１３は、検索文字列との一致箇所を記憶するテーブルＴ２を示す。
【図１４Ａ−Ｄ】図１４Ａ−Ｄは、文字情報とアドレスとの対応関係を示す。
【図１５】図１５は、２種類のインデックス情報の関係を示す。
【図１６】図１６は、アドレスが重複する文字情報同士の存否情報の関係を示す。
【発明を実施するための形態】
【００１９】
まず、インデックス情報を用いた検索対象ファイルの絞り込みついて、説明する。
【００２０】
図１Ａは、検索対象のファイル群Ｆ１〜Ｆｎに基づくインデックス情報Ｉ１を示す。図１Ａに示すインデックス情報Ｉ１中、最上行がファイル番号を示す。ファイル番号は、検索対象のファイル群Ｆ１〜Ｆｎそれぞれに対応する番号である。インデックス情報において、文字情報群Ｃ１〜Ｃｍのそれぞれが、ファイル群Ｆ１〜Ｆｎにおける存否に関するビット列と対応付けられる。
【００２１】
文字情報群Ｃ１〜Ｃｍに含まれる文字情報Ｃｊは、例えば、１文字もしくは複数の文字の組み合わせによる文字列である。もしくは、文字情報Ｃｊは、文字情報に対応するバイナリコードの一部分でもよい。文字情報群Ｃ１〜Ｃｍは、使用が想定される文字（たとえばＪＩＳコードが割り当てられている文字）の全通りの組み合わせでもよい。例えば、ファイル群Ｆ１〜ＦｎのうちのあるファイルＦｉ（ファイル番号はｉ）が、「人生はクローズアップで見れば悲劇  ロングショットで見れば喜劇」という文字列を含むファイルであるとする。その場合、ファイルＦｉは、「人」、「生」、「は」、・・・、「劇」という文字情報を含むファイルであり、「人生」、「生は」、「はク」、・・・、「喜劇」という文字情報を含むファイルでもある。本実施形態においては、文字情報群Ｃ１〜Ｃｍのそれぞれは２文字の文字情報である場合を例示する。
【００２２】
文字情報Ｃｊがファイル群Ｆ１〜Ｆｎのいずれに含まれるかは、１〜ｎのそれぞれの数ｉについて、文字情報ＣｊとファイルＦｉとに対応する記憶領域に、文字情報ＣｊがファイルＦｉに含まれるか否かに関する情報が記憶されることで示される。例えば、インデックス情報Ｉ１において、ファイルＦｉに文字情報Ｃｊが含まれるか否かに関する存否情報の格納先は、文字情報Ｃｊに対応するバイナリコードをハッシュ関数に代入して得られるアドレスＰｊと、ファイル番号ｉにより示される。文字情報に対応するバイナリコードとは、例えば、文字情報「喜劇」に対応するバイナリコード（ＪＩＳに基づく文字コード）であれば、０ｘ３４６Ｅ３７６０（０ｘは１６進数表記を意味する）である。
【００２３】
１つの文字情報Ｃｊに対して１つのアドレスＰｊが割り当てられる場合には、文字情報Ｃｊの存否情報は、ファイルＦｉに文字情報Ｃｊが存在すれば 「１」の値のビットで示され、ファイルＦｉに文字情報Ｃｊが存在しなければ、「０」の値のビットで示される。一方、複数の文字情報（例えば、文字情報Ｃｊと文字情報Ｃｋ）が１つのアドレスＰｊに割り当てられている場合もある。その場合には、存否情報は、ファイルＦｉに文字情報Ｃｊ及び文字情報Ｃｋのうちの少なくとも１つが存在すれば「１」の値のビットで示され、ファイルＦｉに文字情報Ｃｊ及び文字情報Ｃｋのいずれも存在しなければ、「０」の値のビットで示される。ちなみに、存否情報がどのように示されるかは適宜変更されてよく、値が「１」で不存在が示され、値が「０」で存在が示されてもよい。さらには、複数ビットにより存否が示されてもよい。図１Ａに示すインデックス情報においては、文字情報を含む旨は「１」の値のビットで示されている。
【００２４】
例えば、アドレスＰｊに対応する文字情報が「喜劇」のみである場合には、インデックス情報Ｉ１のアドレスＰｊに示されるビット列により、「喜劇」がファイル番号２，３，ｉのファイルそれぞれに含まれることが明らかになる。また、例えば、１つのアドレスＰｋに「劇王」と「見れ」との双方が対応する場合には、インデックス情報Ｉ１のアドレスＰｋに示されるビット列は、ファイル群Ｆ１〜Ｆｎのそれぞれについて、「劇王」と「見れ」との少なくとも一方を含むか、「劇王」と「見れ」とのいずれも含まないか、のいずれかを示す。例えば、ファイル番号ｉ，ｎ−１のファイルは、「劇王」と「見れ」の少なくとも一方を含むことが示され、ファイル番号１，２，３、ｊ、ｋなどのファイルは、「劇王」と「見れ」とのいずれも含まないことが示される。
【００２５】
図１Ａに示すように、ファイルＦｉは、「喜劇」以外の文字情報も含むため、「喜劇」だけでなく、「人生」、「生は」、・・・など、他の文字情報に対応する位置のビットも「１」の値を示す。また、図１Ａでは省略されているが、ファイル群Ｆ１〜Ｆｎのそれぞれについても、各ファイルに含まれる文字情報に対応する位置のビットが「１」の値を示す。
【００２６】
ファイル群Ｆ１〜Ｆｎに対して検索を行なう場合に、図１Ａに示すインデックス情報Ｉ１を用いて文字列検索対象のファイルの絞り込みが行なわれる。例えば「喜劇王」という検索文字列を含む検索要求を受け付けたとする。検索文字列の「喜劇王」には、「喜劇」という文字情報と「劇王」という文字情報とが含まれている。この場合、文字列検索対象となるファイルは、例えば、「喜劇」に基づき算出されるアドレス（図１ＡではＰｊ）に示されるビット列と、「劇王」に基づき算出されるアドレス（図１ＡではＰｋ）に示されるビット列とにより絞り込まれる。例えば、アドレスＰｊに対応するビット列と、アドレスＰｋに対応するビット列との論理積演算結果であるビット列Ａ１は、図１Ｂに示す通りとなる。
【００２７】
図１Ｂに示すビット列Ａ１において、「１」となるビットに対応するファイル（図１Ｂにおいては、ファイル番号ｉのファイル）が、文字列検索対象のファイルとなる。図１Ａの例においては、アドレスＰｋに複数の文字情報（例えば、「見れ」及び「劇王」）が対応する。ファイルＦｉは、「劇王」は含まないが、「見れ」を含む。そのため、「見れ」及び「劇王」に対応するポインタＰｋに対応するビット列における、ファイルＦｉのビットも「１」となってしまう。そのようなインデックス情報Ｉ１を用いて、文字情報「喜劇」および「劇王」で検索対象のファイルを絞り込むと、ファイルＦｉに「劇王」が含まれないにも関わらず、「喜劇」と「劇王」の双方を含むファイルと判断され、検索対象のファイルとなる。
【００２８】
図２は、複数のインデックス情報Ｉ１，Ｉ２を用いたファイル絞り込みの説明図である。図１Ａに示す通り、インデックス情報Ｉ１においては、文字情報「劇王」及び「見れ」は、アドレスＰｋと対応する（図２の説明においてはＰｋ２とする）。これは、文字情報「劇王」及び「見れ」のそれぞれを、ハッシュ関数（図２においてはＨａｓｈ１とする）に代入して得られる値がアドレスＰｋ１であるためである。例えば、ハッシュ関数Ｈａｓｈ１と異なるハッシュ関数Ｈａｓｈ２を用いると、インデックス情報Ｉ２が生成されるとする。インデックス情報Ｉ２では、文字情報「劇王」は、アドレスＰｋ１に対応する。また、文字情報「見れ」は、アドレスＰｋ２とは異なるアドレスと対応する。
【００２９】
検索文字列「喜劇王」についての検索を行う場合に、インデックス情報Ｉ１とインデックス情報Ｉ２との双方の「劇王」に関する存否情報に基づいて、文字列検索対象のファイルが絞り込まれる。例えば、アドレスＰｋ１のビット列とＡ２−１、アドレスＰｋ２のビット列Ａ２−２が抽出され、抽出されたビット列同士の論理積演算で得られるビット列Ａ２−３に基づいてファイル絞り込みが行われる。しかしながら、インデックス情報Ｉ２においても、アドレスＰｋ２に文字情報「劇王」以外の文字情報が対応することがある。図２に示すインデックス情報Ｉ２においても、ファイルＦＩが文字情報「劇王」を含まないにも関わらず、ビットの値が「１」となっている。ファイルＦｉが文字情報「劇王」以外のアドレスＰｋ２に対応する文字情報を含む場合には、やはり、ファイルＦｉが文字情報「劇王」を含まない旨がインデックス情報Ｉ２に示されなくなる。そのため、インデックス情報Ｉ１とインデックス情報Ｉ２とに基づくビット列Ａ２−３にも、ファイルＦｉに「劇王」が含まれない旨が示されない。そのため、ファイルＦｉは文字情報「劇王」を含まないにも関わらず、検索文字列「喜劇王」の文字列検索の対象に絞り込まれる。
【００３０】
半角文字を用いた場合も同様である。例えば、ファイルＦｉが「Ｌｉｆｅ  ｉｓ  ａ  ｔｒａｇｅｄｙ  ｗｈｅｎ  ｓｅｅｎ  ｉｎ  ｃｌｏｓｅ−ｕｐ，  ｂｕｔ  ａ  ｃｏｍｅｄｙ  ｉｎ  ｌｏｎｇ−ｓｈｏｔ．」という文字列を含むとする。すると、例えば、インデックス情報において、文字情報「ｃｏｍｅ」に基づき算出されたアドレスＰｊと、ファイル番号ｉに示される位置のビットが「１」を示す。また、例えば、文字情報「ｍｅｄｙ」に基づき算出されたアドレスＰｋと、ファイル番号ｉに示される位置のビットが「１」を示す。検索文字列が「ｃｏｍｅｄｉａｎ」であると、例えば、検索対象のファイルが、インデックス情報に基づいて、「ｃｏｍｅ」および「ｄｉａｎ」の双方を含むファイルに絞り込まれるとする。その際に、たまたま文字情報「ｄｉａｎ」に基づき算出したアドレスが、文字情報「ｍｅｄｙ」に基づいて算出したアドレスＰｋと同じであると、ファイルＦｉは「ｄｉａｎ」を含まないにも関わらず、「ｃｏｍｅｄｉａｎ」の検索対象のファイルとなる。
【００３１】
また、アドレスと文字情報を対応付ける複数のハッシュ関数Ｈａｓｈ１，Ｈａｓｈ２を用いて、複数のインデックス情報Ｉ１，Ｉ２を生成する方法もある。すると、インデックス情報Ｉ１でたまたま同じアドレスと対応する文字情報「ｍｅｄｙ」と「ｄｉａｎ」が、インデックス情報Ｉ２では、インデックス情報Ｉ１とは異なるハッシュ関数Ｈａｓｈ２を用いることにより、互いに異なるアドレスに対応付けられる。インデックス情報Ｉ２を参照することにより、「ｄｉａｎ」を含まないにも関わらず、「ｍｅｄｙ」を含むために、文字列検索の対象に絞り込まれることは抑制される。しかしながら、インデックス情報Ｉ２において、「ｄｉａｎ」と同じアドレスに対応する他の文字情報があり、その文字情報を含むファイルについては、結果的に、「ｄｉａｎ」を含まないにも関わらず、文字列検索の対象に絞り込まれる。
【００３２】
上述のように、異なる複数の文字情報に対応するアドレスが重複することにより、ファイル絞り込みにノイズが生じうる。これは、ファイルＦｉに含まれない文字情報（「劇王」、「ｄｉａｎ」など）と、ファイルＦｉに含まれる文字情報（「見れ」、「ｍｅｄｙ」など）とで、存否情報の格納位置を示すポインタが重複しているためである。ファイルＦｉに含まれる文字情報（「見れ」、「ｍｅｄｙ」など）の存在により、ビットが「１」の状態になるため、ファイルＦｉに含まれない文字情報（「劇王」、「ｄｉａｎ」など）が存在しないことがインデックス情報に示されなくなってしまう。ちなみに、対応するポインタが重複する複数の文字情報の双方を含まない場合には、ビットが「０」の状態になるため、インデックス情報、複数の文字情報のどちらに対しても不存在が明らかとなる。
【００３３】
つまり、ファイル内に含まれる文字情報のポインタと、ファイル内に含まれない文字情報のポインタとが重複しやすいファイルほど、絞込みノイズを生じやすい。学術書などの電子書籍を例にあげると、本編のファイルよりも、索引や目次などのファイルの方が、多くの文字種類を含みやすく、同じ電子書籍内のファイルであっても、ファイルに含まれる文字情報の種類数には、差があることがある。ファイル内に含まれる文字情報の種類の数が異なるファイル同士では、一方のファイルの方が、アドレスの重複により、文字情報の不存在が示されなくなる事態が、他方のファイルに比べて発生しやすくなる。
【００３４】
上述の理由により、ファイル群Ｆ１〜Ｆｎのインデックス情報が全体的に疎な行列になる場合には、文字情報を多く含むファイルに、文字情報同士のポインタ重複による絞り込みノイズが発生しやすくなる。また、多くの文字種類を含むファイルの一例として、ファイルサイズが他のファイルよりも大きいファイルが挙げられる。ファイルサイズが大きいファイルが絞り込みノイズになると、他のファイルよりも無駄な文字列検索の処理量が大きくなる。
［第１の実施形態］
第１の実施形態を説明する。第１の実施形態においては、インデックス情報におけるアドレスを、文字情報ＣｊとファイルＦｉのファイル番号ｉとの双方に基づき求められる数値を引数とする関数ｆの演算により算出する。算出されたアドレスＰｉｊには、ファイルＦｉにおける文字情報Ｃｊの存否情報が格納される。この関数ｆは、所定範囲内の数値を返す関数である。
【００３５】
図３Ａは、関数ｆに代入される引数の例を示す。図３Ａの例では、引数は、文字情報Ｃｊのバイナリコードを所定数αだけビットシフトさせたバイナリコードと、ファイルＦｉのファイル番号ｉのバイナリコードとの和である。文字情報Ｃｊ、ファイル番号ｉおよび引数について、バイナリコードを例示する。例えば、文字情報Ｃｊが「喜劇」だとすると、そのバイナリコードは、「０ｘ３４６Ｅ３７６０」である（文字コードにＪＩＳコードを用いた場合）。ファイル番号が「５２（１０進数表記）」であるとすると、「０ｘ３４」となる。図３Ａに例示するように、例えば、所定数αを１６として、文字情報Ｃｊを１６ビットシフトさせた場合の引数は、「０ｘ３４６Ｅ３７６０００３４」となる。
【００３６】
図３Ｂは、インデックス情報Ｉ３を示す。例えば、図３Ａに示す引数を関数ｆに代入して得られる値は、ファイルＦｉにおける文字情報Ｃｊの存否情報の格納場所を示し、すなわち、インデックス情報Ｉ３内のアドレスとなる。関数ｆが、例えば、ある除数Ｄで引数を除算した際の剰余を求める関数であるとする。関数ｆが他の関数の場合については後述する。例えば、除数Ｄを「１００００７（１０進数表記）」とすると、得られる値は０〜１００００６の間のいずれかの数となり、インデックス情報Ｉ３は、１００００７ビットの記憶領域内に収まる。ちなみに、引数が上述のように「０ｘ３４６Ｅ３７６０００３４（１６進数表記）」であり、「１００００７」で除算した場合の剰余は「９１５０（１０進数表記）」となるので、「９１５０」に対応する記憶領域に、ファイル番号「５２」のファイルＦ５２における「喜劇」の存否情報が格納される。図３Ｂにおいては、文字情報「喜劇」とファイル番号ｉに基づいて算出されるアドレスをＨａｓｈ（“喜劇”，１）と表記している。同様に、「見れ」のバイナリコードは、「０ｘ３８２Ｂ２４６Ｃ」であり、そのアドレスは「５０６４（１０進数）」となる。図３Ｂに示す通り、Ｈａｓｈ（“喜劇”，１）とＨａｓｈ（“見れ”，４０８６）とが同値であり、その値に示される記憶領域には、ファイルＦ１における「喜劇」の存否情報と、ファイルＦ４０８６における「見れ」の存否情報とが重複して記憶される。具体的には、双方において存否を示すビットの値の論理和が格納される。
【００３７】
さらに、例えば、ファイル番号が「５２」よりも１大きい「５３」であるファイルＦ５３における「喜劇」の存否情報は、ファイルＦ５２における「喜劇」の存否情報を格納するアドレス「９１５０」よりも１大きい「９１５１」となる。図３Ａの引数は、ファイル番号についてビットのシフトをしていないので、剰余によりアドレス求めると、同じ「喜劇」に関する存否情報を格納するアドレスは連続する。例えば、ファイル番号０として、文字情報「喜劇」の存否情報の格納先アドレスを算出すると、「９０９８」となる。すると、ファイル番号１〜ｎに対応するファイル群Ｆ１〜Ｆｎのそれぞれにおける「喜劇」の存否情報を格納するアドレスは、「９０９８＋１」〜「９０９８＋ｎ」という連続する値をとる。ファイル群Ｆ１〜Ｆｎのそれぞれにおける「喜劇」の存否を示すビット列Ａ３−２は、図３Ｂに示す通り、インデックス情報Ｉ３の対応する位置のビットに反映される。ファイル群Ｆ１〜Ｆｎのそれぞれにおける「見れ」の存否を示すビット列Ａ３−１も、図３Ｂに示す通り、インデックス情報Ｉ３の対応する位置のビットに反映される。ビット列Ａ３−１とビット列Ａ３−２とで、インデックス情報Ｉ３の反映する部分が重なるが、上述の通り、双方のビット列の論理和が格納される。
【００３８】
半角文字についても同様の方法で存否情報のアドレスが決められる。例えば、「ｃｏｍｅ」という文字情報のバイナリコードは「０ｘ６３６ｄ６ｂ６５」である。例えば、ファイルＦ５２における「ｃｏｍｅ」の存否情報を格納する場合には、そのアドレスの算出に用いられる引数は、「０ｘ６３６ｄ６ｂ６５００３４」となる。さらに、「０ｘ６３６ｄ６ｂ６５００３４」を「１００００７」で除算した場合の剰余は「８９７２７（１０進数）」となるので、「８９７２７」に対応する記憶領域に、ファイルＦ５２における「ｃｏｍｅ」の存否情報が格納される。
【００３９】
第１の実施形態においては、上述の方法で定められるインデックス情報内のアドレスを用いて、インデックス情報の生成と、文字列検索対象のファイルの絞り込みとが行なわれる。第１の実施形態のインデックス情報の生成と文字列検索対象のファイルの絞り込みとについて、さらに詳細に説明する。
【００４０】
図４は、第１の実施形態におけるコンピュータ１の機能ブロックの例を示す。コンピュータ１は、処理部１１および記憶部１２を含む。処理部１１は、インデックス情報を生成し、生成したインデックス情報を用いた検索を行なう。記憶部１２は、処理部１１の処理に用いられる情報（例えば、検索対象となるファイル群Ｆ１〜Ｆｎやインデックス情報など）を記憶する。
【００４１】
処理部１１は、生成部１３を含む。生成部１３は、インデックス情報を生成し、記憶部１２に記憶する。
【００４２】
図６は、生成部１３の機能ブロックの例を示す。生成部１３は、制御部１３１、読出し部１３２および判定部１３３を含む。制御部１３１は、ファイルＦ１からファイルＦｎを順に指定し、指定したファイルについて、読出し部１３２と判定部１３３とにそれぞれの処理を実行させる。読出し部１３２は、ファイル群Ｆ１〜Ｆｎのうち、制御部１３１により指定されたファイルＦｉを記憶部１２から読み出す。判定部１３３は、ファイルＦｉに、設定された文字情報群Ｃ１〜Ｃｍのうちの各文字情報Ｃｊについて、Ｃｊを含むか否かを判定する。判定部１３３の判定結果が、文字情報Ｃｊを含む旨を示す場合に、制御部１３１は、文字情報Ｃｊ及びファイルＦｉのファイル番号ｉに基づいてアドレスを算出し、算出したアドレスに示される記憶場所に、文字情報Ｃｊを含む旨を示す情報を格納する。図１２は、ファイル番号とファイルパスと対応関係を格納するテーブルＴ１の例を示す。読出し部１３２は、制御部１３１にファイル番号を指定された場合に、指定されたファイル番号とテーブルＴ１において対応するファイルパスで読み出し対象のファイルを特定する。
【００４３】
図４に示す通り、処理部１１は、さらに、検索制御部１４、絞込部１５および文字列検索部１６を含む。検索制御部１４は、絞込部１５と文字列検索部１６との制御により、検索要求に応じた検索処理を行なう。絞込部１５は、図３Ｂに示すインデックス情報を用いて、検索対象ファイルの絞り込みを行なう。例えば、検索制御部１４が、受け付けた検索要求に含まれる検索文字列から文字情報Ｃａを抽出して、抽出された文字情報Ｃａを絞込部１５に通知する。絞込部１５は、ファイル群Ｆ１〜Ｆｎのうち、検索制御部１４に通知された文字情報Ｃａを含まないファイルを除いたファイルのファイル番号を検索制御部１４に通知する。文字列検索部１６は、絞込部１５により絞り込まれたファイルについて、検索制御部１４が受け付けた検索要求に基づく文字列検索を行なう。
【００４４】
図５は、絞込部１５の機能ブロックの例を示す。絞込部１５は、参照部１５１および判定部１５２を含む。参照部１５１は、記憶部１２に記憶されたインデックス情報のうち、検索制御部１４から通知された文字情報Ｃａに対応する部分を読み出す。文字情報Ｃａに対応する部分を示すアドレスは、図３Ｂに示す通り、文字情報Ｃａとファイル番号に応じて算出される。図３Ｂのインデックス情報のように、文字情報Ｃａの存否に関する存否情報のアドレスがファイル群Ｆ１〜Ｆｎで連続する場合には、例えば、参照部１５１は、ファイル番号を「１」としてアドレスを算出し、そのアドレスからｎビット連続するビット列を読み出す。判定部１５２は、参照部１５１が読み出したビット列に基づいて、文字情報Ｃａを含まないファイルを判定し、ファイル群Ｆ１〜Ｆｎのなかで文字情報Ｃａを含まないファイルを除いてファイル番号を文字列検索部１６に通知する。
【００４５】
検索制御部１４は、検索文字列から複数の文字情報（例えば文字情報Ｃａ、文字情報Ｃｂ）を抽出してもよい。すると、参照部１５１は、複数の文字情報Ｃａ，Ｃｂのそれぞれについて、インデックス情報の対応する部分を読み出す。また、判定部１５２は、文字情報Ｃａに対応するビット列に含まれる存否情報と、文字情報Ｃｂに対応するビット列に含まれる存否情報との論理積（ＡＮＤ）を算出し、その算出結果に基づいて各ファイルにおける文字情報Ｃａ，Ｃｂの存否を判定する。文字情報Ｃａ，Ｃｂのいずれかが含まれないと判断されたファイルのファイル番号は、文字列検索部１６に通知しない。
【００４６】
図７は、コンピュータ１のハードウェア構成例を示す。図４〜６に示す各機能ブロックは、例えば、図７に示すハードウェア構成により実現される。コンピュータ１は、例えば、プロセッサ３０１、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）３０２、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）３０３、ドライブ装置３０４、記録媒体３０５、入力インターフェース（Ｉ／Ｆ）３０６、入力デバイス３０７、出力インターフェース（Ｉ／Ｆ）３０８、出力デバイス３０９、通信インターフェース（Ｉ／Ｆ）３１０などを含む。それぞれのハードウェアはバス３１１を介して接続されている。通信Ｉ／Ｆ３１０はネットワーク４を介した通信の制御を行なう。入力インターフェース３０６は、入力デバイス３０７と接続されており、入力デバイス３０７から受信した入力信号をプロセッサ３０１に伝達する。出力インターフェース３０８は、出力デバイス３０９と接続されており、出力デバイス３０９に、プロセッサ３０１の指示に応じた出力を実行させる。
【００４７】
ＲＡＭ３０２は読み書き可能なメモリ装置であって、例えば、ＳＲＡＭ（Ｓｔａｔｉｃ  ＲＡＭ）やＤＲＡＭ（Ｄｙｎａｍｉｃ  ＲＡＭ）などの半導体メモリ、またはＲＡＭでなくてもフラッシュメモリなどが用いられる。ＲＯＭ３０３は、ＰＲＯＭ（Ｐｒｏｇｒａｍｍａｂｌｅ  ＲＯＭ）なども含む。ドライブ装置３０４は、記録媒体３０５に記録された情報の読み出しか書き込みかの少なくともいずれか一方を行なう装置である。記録媒体３０５は、ドライブ装置３０４によって書き込まれた情報を記憶する。記録媒体３０５は、例えば、ハードディスク、ＣＤ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ）、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｃ）、ブルーレイディスクなどの記録媒体である。また、例えば、コンピュータ１は、複数種類の記録媒体それぞれについて、ドライブ装置３０４及び記録媒体３０５を設ける。
【００４８】
入力デバイス３０７は、操作に応じて入力信号を送信する装置である。入力信号は、例えば、キーボードやコンピュータ１の本体に取り付けられたボタンなどのキー装置や、マウスやタッチパネルなどのポインティングデバイスである。出力デバイス３０９は、コンピュータ１の制御に応じて情報を出力する装置である。出力デバイス３０９は、例えば、ディスプレイなどの画像出力装置（表示デバイス）や、スピーカーなどの音声出力装置などである。また、例えば、タッチスクリーンなどの入出力装置が、入力デバイス３０７及び出力デバイス３０９として用いられる。
【００４９】
プロセッサ３０１は、ＲＯＭ３０３や記録媒体３０５に記憶されたプログラムをＲＡＭ３０２に読み出し、読み出されたプログラムの手順に従って処理部１１の処理を行なう。その際にＲＡＭ３０２はプロセッサ３０１のワークエリアとして用いられる。記憶部１２の機能は、ＲＯＭ３０３および記憶媒体３０５がプログラムやファイル群Ｆ１〜Ｆｎを記憶し、ＲＡＭ３０２がプロセッサ３０１のワークエリアとして用いられることによって実現される。プロセッサ３０１が読み出すプログラムについては、図８を用いて説明する。
【００５０】
図８は、コンピュータ１で動作するソフトウェアの構成例を示す。コンピュータ１において、図７に示すハードウェア群２１の制御を行なうＯＳ２２（オペレーションシステム）が動作する。ＯＳ２２に従った手順でプロセッサ３０１が動作して、ハードウェア２１の制御・管理が行なわれることにより、アプリケーションプログラムやミドルウェアによる処理がハードウェア２１により実行される。さらに、コンピュータ１において、例えば、インデックス生成プログラム２３ａや検索処理プログラム２３ｂなどが、ＲＡＭ３０２に読み出されてプロセッサ３０１により実行される。また、プロセッサ３０１がインデックス生成プログラム２３ａに基づく処理を行なうことにより、（それらの処理をＯＳ２２に基づいてハードウェア２１を制御して）インデックス生成部１３の機能が実現される。さらに、プロセッサ３０１が検索処理プログラム２３ｂに基づく処理を行なうことにより、（それらの処理をＯＳ２２に基づいてハードウェア２１を制御して）検索制御部１４、ファイル絞込部１５および文字列検索部１６の機能が実現される。図８にはインデックス生成プログラム２３ａと検索処理プログラム２３ｂとが別のプログラムとして示されているが、両プログラムを併せて１つのプログラムとしてもよい。
【００５１】
図４〜８に示すコンピュータ１の構成は、後述の第２の実施形態、第３の実施形態においても同様である。
【００５２】
図９は、インデックス生成の処理手順例を示す。インデックス生成プログラム２３ａが起動される（Ｓ１００）と、制御部１３１は、前処理を行なう（Ｓ１０１）。Ｓ１０１の前処理は、例えば、図１２に示すテーブルＴ１や文字情報群Ｃ１〜Ｃｍの読み出しなどである。制御部１３１は、インデックス情報の生成が要求されるか否かを判断し（Ｓ１０２）、インデックス情報の生成が要求されるまで繰り返し判断を行なう（Ｓ１０２：ＮＯ）。インデックス情報の生成が要求される（Ｓ１０２：ＹＥＳ）と、制御部１３１は、インデックス情報を記憶する記憶領域を確保する（Ｓ１０３）。例えば、Ｓ１０３において確保された記憶領域内の各ビットは「０」にセットしておく。
【００５３】
制御部１３１は、図１２に示すテーブルＴ１から、ファイル番号ｉを選択し、選択したファイル番号ｉのファイルＦｉを読出し部１３２に読み出させる（Ｓ１０４）。例えば、Ｓ１０４において、制御部１３１は、テーブルＴ１内のレコードを順に選択する。次に、判定部１３３は、文字情報Ｃ１〜Ｃｍのうちの１つの文字情報Ｃｊを選択する（Ｓ１０５）。例えば、Ｓ１０５において、判定部１３３が、文字情報Ｃ１〜Ｃｍのリストを保持して、リスト内の文字情報を順に選択してもよいし、所定の数値範囲内で文字コードをインクリメントしつつ順に選択してもよい。判定部１３３は、ファイルＦｉが文字情報Ｃｊを含むか否か判定する（Ｓ１０６）。ファイルＦｉが文字情報Ｃｊを含むと判定した場合（Ｓ１０６：ＹＥＳ）は、制御部１３１は、ファイル番号ｉと文字情報Ｃｊに基づいてアドレスを算出する。制御部１３１は、算出したアドレスに対応する位置のビットを「１」に更新する。すなわち、制御部１３１は、算出したアドレスに対応する位置のビットと、「１」との論理和（ＯＲ）演算の結果を、算出したアドレスに対応する位置に格納する。制御部１３１によりビットの更新が行なわれると、判定部１３３はＳ１０８の処理を行なう。判定部１３３によりファイルＦｉが文字情報Ｃｊを含まないと判定された場合（Ｓ１０６：ＮＯ）は、判定部１３３は、Ｓ１０８の処理を行なう。次の文字情報についての処理を行なう。文字情報Ｃ１〜Ｃｍのなかで、未選択の文字情報が存在する場合には、判定部１３３は、再度Ｓ１０５の処理を行なう（Ｓ１０８）。文字情報Ｃ１〜Ｃｍのなかで未選択の文字情報が存在しない場合には、Ｓ１０９の処理が行なわれる。Ｓ１０９では、ファイル群Ｆ１〜Ｆｎのなかで未選択のファイルがあれば、読出し部１３２がＳ１０４の処理を再度行なう。また、ファイル群Ｆ１〜Ｆｎのなかで未選択のファイルがなければ、Ｓ１１０の処理が行なわれる。
【００５４】
制御部１３１は、ファイル群Ｆ１〜Ｆｎのインデックス情報の生成処理が完了した旨の通知を行なう（Ｓ１１０）。Ｓ１１０において、制御部１３１は、さらに、Ｓ１０３で確保した領域内の情報をインデックスファイルとして保存する。Ｓ１１０の処理後、終了指示を受けていたか否か判定する（Ｓ１１１）。終了指示を受けていた場合（Ｓ１１１：ＹＥＳ）は、処理部１１は、インデックス生成プログラムを終了する。終了指示を受けていない場合（Ｓ１１１：ＮＯ）には、Ｓ１０２の処理を再度行なう。
【００５５】
図１０は、全文検索の処理手順例を示す。検索処理プログラム２３が起動される（Ｓ２００）と、検索制御部１４は、前処理を行なう（Ｓ２０１）。Ｓ２０１の前処理は、図１２に示すテーブルＴ１の読出しや、インデックス情報の読出しである。検索制御部１４は、検索要求を受けたか否かを判断し（Ｓ２０２）、検索要求を受けるまでＳ２０２の判断を繰り返す（Ｓ２０２：ＮＯ）。検索要求を受けた場合（Ｓ２０２：ＹＥＳ）には、インデックス参照処理が実行される（Ｓ２０３）。
【００５６】
図１１は、インデックス情報の参照処理手順の例を示す。Ｓ２０３が実行される（Ｓ３００）と、検索制御部１４は、検索要求に含まれる検索文字列を取り出し、文字情報Ｃ１〜Ｃｍのうちの検索文字列に含まれる文字情報Ｃａ，Ｃｂ，・・・を抽出する（Ｓ３０１）。
【００５７】
ファイル絞込部１５は、検索制御部１４が文字情報Ｃａ，Ｃｂ，・・・を抽出すると、ファイル群Ｆ１〜Ｆｎのそれぞれについて、抽出された文字情報Ｃａ，Ｃｂ，・・・のいずれか１つでも含まないファイルであるかどうかを判断する。具体的には、まず、抽出された文字情報のうちの１つを選択する（Ｓ３０２）。参照部１５１は、選択された文字情報に基づいてアドレスを算出し、算出されたアドレスに示される位置に格納された情報を読み出す（Ｓ３０３）。Ｓ３０３において、参照部１５１は、Ｓ１０７と同様の演算によりアドレスを算出する。その際に、例えば、参照部１５１は、ファイル番号を「１」としてアドレスを算出し、算出したアドレスからｎビット連続するビット列を読み出す。ファイル絞込部１５は、抽出された文字情報Ｃａ，Ｃｂ，・・・のなかに未選択の文字情報がある場合には、Ｓ３０２の処理を再度行ない、抽出された文字情報Ｃａ，Ｃｂ，・・・に未選択の文字情報がない場合には、インデックス参照処理を終了する（Ｓ３０４，Ｓ３０５）。
【００５８】
インデックス参照処理が終了すると、ファイル絞込部１５は、検索対象のファイルのファイル番号を抽出する（Ｓ２０４）。Ｓ２０４において、例えば、判定部１５２は、文字情報Ｃａ，Ｃｂ，・・・のそれぞれについて参照部１５１により読み出されたビット列同士の論理積（ＡＮＤ）を算出する。判定部１５２は、算出されたビット列において「１」であるビットが何番目であるかを示す番号を生成する。例えば、判定部１５２は、算出されたビット列において、ｘ番目のビットとｙ番目のビットが「１」であれば、ｘ，ｙを生成する。
【００５９】
検索制御部１４は、判定部１５２により生成された番号ｘ，ｙ，・・・のいずれかである番号ｉを選択する（Ｓ２０５）。文字列検索部１６は、選択された番号ｉがファイル番号であるファイルＦｉを読み出す（Ｓ２０６）。文字列検索部１６は、図１２に示すテーブルＴ１においてファイル番号ｉと対応づけられた格納場所からファイルを読み出す。文字列検索部１６は、読み出したファイルＦｉを検索文字列で検索する（Ｓ２０７）。例えば、文字列検索部１６は、ファイルＦｉ内に検索文字列と一致する文字列を検出した場合には、一致した文字列のファイルＦｉ内の位置を示す情報を生成し、ファイルＦｉのファイル番号ｉと関連付けて記憶部１２に記憶する（図１２参照）。例えば、検索文字列と照合を行なったデータの量をカウントするカウンタを予め設けておき、文字列の一致を検出した際のカウンタの値を、ファイル内の位置を示す情報とする。
【００６０】
Ｓ２０７の処理後、検索制御部１４は、判定部１５２により生成された番号ｘ，ｙ，・・・のなかで未選択の番号があればＳ２０５の処理を行なう。検索制御部１４は、判定部１５２により生成された番号ｘ，ｙ，・・・のなかに未選択の番号がない場合には、Ｓ２１０の処理を行なう。
【００６１】
検索制御部１４は、検索結果の出力処理を行なう（Ｓ２０９）。例えば、Ｓ２０７の処理で図１３に示すテーブルＴ２に格納された情報に示される位置の近傍の文字列を抽出して、抽出した文字列を、ファイル番号に対応するファイル名などと併せて表示デバイスに表示させるなどの処理を行なう。
【００６２】
Ｓ２１０処理後に、処理部１１は、終了の指示があったか否かを判断する（Ｓ２１１）。終了の指示がない場合（Ｓ２１１：ＮＯ）には、検索制御部１４はＳ２０２の処理を行なう。終了の指示があった場合には、処理部１１は、検索処理プログラム２２ｂを終了させる（Ｓ２１１）。
【００６３】
以下に、ファイル番号ｉと文字情報Ｃｊに基づいて存否情報を格納するアドレスを算出する方法について、さらに詳細に説明する。まず、αビットシフトさせた文字情報Ｃｊとファイル番号との和を、除数Ｄで除算した剰余をアドレスとする方法について、さらに説明する。
【００６４】
図１４Ａ−Ｄは、シフトさせるビット数αと除数Ｄとの関係を示す図である。図１４Ａに示す０〜６の各数値に文字情報（Ｃ０〜Ｃ６）が対応するとする。図１４Ａはあくまで例示であり、０〜６の数値が８ビットや１６ビットで表現される文字情報のバイナリコードに相当する。図１４Ｂは、文字情報Ｃ０〜Ｃ６のバイナリコードをそれぞれ２ビットシフトした数値であり、それぞれ０，４，８，１２，１６，２０，２４となる。図１４Ｂに示す数値は、もしファイル番号が「０」である場合に引数となる数値である。図１４Ｃは、除数Ｄを１３として図１４Ｂに示す各数値を除算した場合の剰余および商を示す。剰余の値はそれぞれ０，４，８，１２，３，７となる。図１４Ｄは、図１４Ｃの剰余をまとめて表示した図である。図１４に示す各数値は、もしファイル番号が「０」であった場合のアドレスを示す。各数値は、０，４，８，１２，３，７であり、同じ値になっていない。ファイル番号「０」のファイルにおける文字情報Ｃ０〜Ｃ６の各存否情報の格納先アドレスは、互いに異なる。例えば、ファイル番号がｉの場合にも、ｉに応じてアドレスがずれるのみなので、ファイルＦｉにおける文字情報Ｃ０〜Ｃ６の各存否情報の格納先アドレスは異なる。
【００６５】
例えば、「１３」対応する文字情報Ｃ１３があるとすると、引数１３×４を「１３」で除算した剰余は０となるため、アドレスがＣ０と同じになる。Ｃ０〜Ｃ１２までの文字情報については、それぞれ別のアドレスが割り当てられている。
【００６６】
同じファイルについての存否情報の格納先アドレスの種類は、２のα乗と除数Ｄとの最小公倍数Ｘによって決まる。最小公倍数Ｘを２のα乗で除算した値Ｙが、とり得るアドレスの種類の数である。２のα乗と除数Ｄとが互いに素であれば、除数Ｄがとり得るアドレスの種類の数である。２のα乗と互いに素な数として、奇数を除数Ｄにすればよい。
【００６７】
上述した例において、除数Ｄが１２であるとすると、２のα乗（＝４）と除数Ｄとの最小公倍数Ｘは１２となり、最小公倍数Ｘを２のα乗で除算した値Ｙは３となる。
文字情報Ｃ０〜Ｃ６のバイナリコードをそれぞれ２ビットシフトした数値０，４，８，１２，１６，２０，２４を１２で除算した場合の剰余は、０，４，８，０，４，８，０・・・となり、アドレスは３種類となる。
【００６８】
インデックス情報のサイズは、（ハッシュ演算によりとり得る値の数ｋ）×（ファイル数ｎ）ビットであった。この場合、同じファイルについての存否情報は、ｋ種類のアドレスのいずれかによって示される位置に格納される。除数Ｄをｋ×ｎと同程度の数で、２のα乗と互いに素であるとすると、同じファイルについての存否情報は、ｋ×ｎ程度の種類のアドレスのいずれかに示される位置に格納される。従来と同程度のサイズのインデックス情報でありながら、ほぼｎ倍の種類のアドレスから同一のファイルの存否情報の格納アドレスが決まるため、互いに重複した位置に格納されにくくなる。
【００６９】
しかしながら、図１４の例では、Ｃ０〜Ｃ６に対応する文字情報が存在するが、所定範囲内の全ての整数値に対応する文字情報が存在するわけではないので、実際にどの程度重なるかは使用する文字コード系におけるバイナリコードの分布に応じて異なる。
除数Ｄによりインデックス情報のサイズが決まるので、例えば、除数Ｄはインデックス情報のサイズに近い素数に設定される。文字コードが所定ビット数αシフトされるのであれば、奇数は２のα乗と互いに素であるため、インデックス情報のサイズに近い奇数などが除数Ｄに設定される。
【００７０】
引数を生成する際に文字情報のバイナリコードをシフトさせるビット数αについて、追加説明する。上述の説明においては、αを１６としたが、例えば、αを４としてもよい。ただし、ファイル番号が４ビットで表現できる数以上になると、引数の重複が発生する。例えば、文字情報Ｃｊのファイル番号１７についての引数と、バイナリコードで文字情報Ｃｊと１違いの文字情報Ｃｋ（Ｃｋ＝Ｃｊ＋１）のファイル番号１についての引数は同じになる。また、α＝０として、文字情報Ｃｊのバイナリコードとファイル番号との和を用いても良い。文字情報Ｃｊのファイル番号１についての引数と、文字情報Ｃｋ（Ｃｋ＝Ｃｊ＋１）のファイル番号１についての引数とは、１違いになる。
【００７１】
また、第１の実施形態において、上述の説明では、文字情報のバイナリコードのシフトにより引数を生成し、引数を代入する関数ｆに剰余を算出する関数を用いた。いずれについても他の方法に変更可能である。例えば、引数の生成においては、文字情報ではなく、逆にファイル番号をシフトしてもよい。また、文字情報のバイナリコードの一部のみをファイル番号を組併せてもよい。また、例えば、関数ｆには、剰余を算出する関数でなくても、所定範囲内の値の出力が得られる関数が用いられる。例えば、引数を所定数の桁ごとに分割し、分割して得られた数値同士の和を算出する関数を用いてもよい。ただし、上述の変形例においては、図１０に示すＳ２０３の処理において存否情報を読みだす際に、参照部１５１は、各ファイルについてアドレスを算出して、１ビットずつ存否情報を読みだす。
［第２の実施形態］
第２の実施形態を説明する。第２の実施形態においては、複数のインデックス情報が用いられる。複数のインデックス情報それぞれから、検索文字列に含まれる文字情報Ｃｊに対応するビット列（ビット長：ｎ）が抽出され、抽出されたビット列同士の論理積（ＡＮＤ）演算結果に基づいて、文字列検索対象のファイルが絞り込まれる。
【００７２】
異なる関数ｆにより得られるアドレスに基づいて生成されるインデックス情報を用いた場合には、同じアドレスに対応する組み合わせ（ファイルＦｉ及び文字情報Ｃｊの組み合わせ）が異なる。関数ｆ１及び関数ｆ２に剰余を算出する関数を用いる場合には、関数ｆ１に用いられる除数Ｄ１と、関数ｆ２に用いられる除数Ｄ２は互いに異なる数とする。例えば、Ｄ１とＤ２に互いに素な整数を用いる。
【００７３】
図１５は、異なる関数ｆ１，ｆ２を用いたインデックス情報の関係を示す。図１５Ａは、図３Ｂに示したビット列Ａ３−1，Ａ３−２，Ａ３−３とインデックス情報の数値範囲との関係を示す。また、図１５は、図１５Ａに示すインデックス情報に用いられる関数ｆ１とは異なる関数ｆ２に基づいて作成されたインデックス情報におけるビット列Ａ３−１、Ａ３−２，Ａ３−３，Ａ３−４と、インデックス情報の数値範囲との関係を示す。図１５Ａに示す通り、ビット列Ａ３−１とビット列Ａ３−２とで、存否情報をインデックス情報に反映させる範囲が一部重複している。上述の通り、重複する部分においては、例えば、ファイルＦ４０８６における文字情報「見れ」の存否情報と、ファイルＦ１における文字情報「喜劇」の存否情報とが重複した位置に反映されていた。一方、図１５Ｂに示すインデックス情報においては、ビット列Ａ３−１を反映させる範囲と、ビット列Ａ３−２を反映させる範囲とが重複しない。そのため、文字情報「喜劇」の存否情報と文字情報「見れ」の存否情報とは、インデックス情報内の異なる部分に反映される。一方で、ビット列Ａ３−１とビット列Ａ３−４とで、反映させる範囲が一部重複している。ビット列Ａ３−４は、文字情報「喜劇」、「見れ」、「劇王」以外の文字情報のファイル群Ｆ１〜Ｆｎにおける存否情報を示すビット列である。この場合、図１５Ｂに示すインデックス情報内で、ファイルＦ４０８６における文字情報「見れ」の存否情報と重複して反映される存否情報は、図１５Ａにおける重複箇所のように、ファイル１とは限らない。むしろその他のファイルのことの方が多い。すると、極めて文字情報の種類が多いファイルが存在する場合にも、そのファイルと反映する箇所が重複することにより、文字情報を含まないことがインデックス情報内に存在することが抑制される。
［第３の実施形態］
第３の実施形態について説明する。第３の実施形態のインデックス情報は、文字情報Ｃｊに基づいて文字情報Ｃｊに対応するビット列が定められ、文字情報Ｃｊとファイル番号との双方に基づいて存否情報を格納するビット列内の位置が定められる。
【００７４】
例えば、文字情報Ｃｊに対応するビット列は、関数ｆに文字情報Ｃｊのバイナリコードを代入して得られるアドレスＹにより示される。数式では、Ｙ＝ｆ（Ｃｊ）となる。関数ｆは、上述の実施例と同様に、例えば、ｆ（Ｃｊ）＝ｍｏｄ（Ｃｊ，Ｄ）などの除数Ｄで除算した際の剰余を求める関数である。
【００７５】
存否情報を格納するビット列内の位置は、例えば、ファイル番号ｉと、文字情報Ｃｊのバイナリコードを除数Ｄで除算した場合の整数商との和とする。数式では、ビット列内での位置Ｘを、Ｘ＝ｉ＋ＱＵＯＴＩＥＮＴ（Ｃｊ／Ｄ）などと示す。ＱＵＯＴＩＥＮＴは除算結果の整数部分をとり出す演算子を示す。
【００７６】
図１６は、第３の実施形態におけるインデックス情報内のビット列の例を示す。ビット列Ａ４−１は、文字情報「劇王」に対応する存否情報の例を示す。アドレスＹ１は、ハッシュ関数に文字情報「劇王」に対応するバイナリコードを代入して得られる。ｑ１＝ＱＵＯＴＩＥＮＴ（“劇王”／Ｄ）とすると、ビット列Ａ４−１は、ファイル群Ｆ１〜Ｆｎのそれぞれについての存否情報がｑ１ビットシフトされたビット列となる。ビット列Ａ４−２は、文字情報「見れ」に対応する存否情報の例を示す。アドレスＹ２は、ハッシュ関数に文字情報「見れ」に対応するバイナリコードを代入して得られる。ｑ２＝ＱＵＯＴＩＥＮＴ（“見れ”／Ｄ）とすると、ビット列Ａ４−２は、ファイル群Ｆ１〜Ｆｎのそれぞれについての存否情報がｑ２ビットシフトされたビット列となる。図  の例のように、「劇王」のアドレスと「見れ」のアドレスとが一致する場合（Ｙ１＝Ｙ２）には、インデックス情報内のＹ１（もしくはＹ２）のビット列は、ビット列Ａ４−1とビット列Ａ４−２との論理和（ＯＲ）であるビット列Ａ４−３となる。
【００７７】
文字情報ごとに除数Ｄの整数商でシフトされるため、アドレスＹが同値となる文字情報同士であっても、それぞれの文字情報についての存否情報をシフトさせる数が異なる。そのため、シフトさせる数の差がファイル数ｎの倍数でなければ、同一のファイルについての存否情報は、ビット列内で異なる位置に格納される。図１６の例によれば、文字情報「劇王」のファイルｉにおける存否情報と、文字情報「見れ」のファイルｉにおける存否情報とは、ビット列中の異なる位置に格納されている。そのため、ファイルｉに文字情報「劇王」が含まれないにも関わらず、文字情報「見れ」が含まれることにより、インデックス情報に文字情報「劇王」の不存在が示されないことが抑制される。
【符号の説明】
【００７８】
１      コンピュータ
１１    処理部
１２    記憶部
１３    生成部
１４    検索制御部
１５    絞込部
１６    文字列検索部
【図１Ａ−Ｂ】
2013175537.tif 000003
【図２】
2013175537.tif 000004
【図３Ａ−Ｂ】
2013175537.tif 000005
【図４】
2013175537.tif 000006
【図５】
2013175537.tif 000007
【図６】
2013175537.tif 000008
【図７】
2013175537.tif 000009
【図８】
2013175537.tif 000010
【図９】
2013175537.tif 000011
【図１０】
2013175537.tif 000012
【図１１】
2013175537.tif 000013
【図１２】
2013175537.tif 000014
【図１３】
2013175537.tif 000015
【図１４Ａ−Ｄ】
2013175537.tif 000016
【図１５】
2013175537.tif 000017
【図１６】
2013175537.tif 000018
【手続補正書】
【提出日】平成27年2月6日(2015.2.6)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
コンピュータに、
第１の文字情報および第１のファイルの識別情報により示される記憶領域であって、前記第１のファイルと異なる第２のファイルが第２の文字情報を含むか否かを示す情報を記憶する記憶領域に、前記第１のファイルが前記第１の文字情報を含むことまたは前記第２ファイルが第２の文字情報を含むことのいずれかを満たすか否かを示す存否情報を記憶する、
処理を実行させることを特徴とする記憶プログラム。
【請求項２】
前記第２の文字情報は、前記第１の文字情報と異なる、
ことを特徴とする請求項１に記載の記憶プログラム。
【請求項３】
前記第１のファイルは、前記第２のファイルよりもファイルサイズが大きい、
ことを特徴とする請求項１または請求項２に記載の記憶プログラム。
【請求項４】
前記コンピュータに、さらに、
前記第１の文字情報および前記第１のファイルの識別情報により示され、前記第１のファイル及び前記第２のファイルと異なる第３のファイルが第３の文字情報を含むか否かを示す情報を記憶する、他の記憶領域に、前記第１のファイルが前記第１の文字情報を含むことまたは前記第２のファイルが第２の文字情報を含むことのいずれかを満たすか否かを示す他の存否情報を記憶する、
処理を実行させることを特徴とする請求項１〜３のいずれか１項に記載の記憶プログラム。
【請求項５】
前記記憶領域は、前記第１の文字情報および前記識別情報に基づき算出される第１の数値により示され、
前記コンピュータに、さらに、
前記第１のファイルと異なる第４のファイルの識別情報及び前記第１の文字情報に基づき算出され、且つ前記第１の数値の次の数値である、第２の数値に示される別の記憶領域に、前記第４のファイルに前記第１の文字情報が含まれるか否かを示す別の存否情報を記憶する、
処理を実行させることを特徴とする請求項１〜４のいずれか１項に記載の記憶プログラム。
【請求項６】
前記第２の数値は前記第１の数値よりも１大きい、
ことを特徴とする請求項５に記載の記憶プログラム。
【請求項７】
前記記憶領域は、前記第１の文字情報及び前記識別情報を変換して得られる引数を所定の関数に代入して得られる数値により示される領域である、
ことを特徴とする請求項１〜３のいずれか１項に記載の記憶プログラム。
【請求項８】
前記引数は、前記第１の文字情報に所定の変換を行なって得られる情報と、前記識別情報との和により得られ、
前記所定の関数は、前記和を所定数で割った剰余を算出する関数である、
ことを特徴とする請求項７に記載の記憶プログラム。
【請求項９】
コンピュータに、
第１の文字情報および第１のファイルの識別情報により示される記憶領域であって、前記第１のファイルと異なる第２のファイルが第２の文字情報を含むか否かを示す情報を記憶する記憶領域に、前記第１のファイルが前記第１の文字情報を含むことまたは前記第２ファイルが第２の文字情報を含むことのいずれかを満たすか否かを示す存否情報を記憶する、
ことを実行させることを特徴とする記憶方法。
【請求項１０】
記憶部と、
第１の文字情報および第１のファイルの識別情報により示される前記記憶部内の記憶領域であって、前記第１のファイルと異なる第２のファイルが第２の文字情報を含むか否かを示す情報を記憶する記憶領域に、前記第１のファイルが前記第１の文字情報を含むことまたは前記第２ファイルが第２の文字情報を含むことのいずれかを満たすか否かを示す存否情報を記憶させる制御を行なう制御部、
を含むことを特徴とする記憶装置。
【請求項１１】
メモリと、
第１の文字情報および第１のファイルの識別情報により示される前記メモリ内の記憶領域であって、前記第１のファイルと異なる第２のファイルが第２の文字情報を含むか否かを示す情報を記憶する記憶領域に、前記第１のファイルが前記第１の文字情報を含むことまたは前記第２ファイルが第２の文字情報を含むことのいずれかを満たすか否かを示す存否情報を記憶させる、
処理を実行するプロセッサと、
を含む記憶装置。
【請求項１２】
コンピュータに、
第１の文字情報を含む検索要求を受けた場合に、前記第１の文字情報および第１のファイルの識別情報により示される記憶領域から、前記第１のファイルが前記第１の文字情報を含むこと、または前記第１のファイルと異なる第２のファイルが第２の文字情報を含むことのいずれかの条件を満たすか否かを示す存否情報を読み出し、
読み出した前記存否情報が前記いずれかの条件を満たす旨を示す場合に、前記第１のファイルを、前記第１の文字情報について文字列検索を行なう、
処理を実行させることを特徴とする検索プログラム。
【請求項１３】
コンピュータに、
第１の文字情報を含む検索要求を受けた場合に、前記第１の文字情報および第１のファイルの識別情報により示される記憶領域から、前記第１のファイルが前記第１の文字情報を含むこと、または前記第１のファイルと異なる第２のファイルが第２の文字情報を含むことのいずれかの条件を満たすか否かを示す存否情報を読み出し、
読み出した前記存否情報が前記いずれかの条件を満たす旨を示す場合に、前記第１のファイルを、前記第１の文字情報について文字列検索を行なう、
ことを実行させることを特徴とする検索方法。
【請求項１４】
記憶部と、
第１の文字情報を含む検索要求を受けた場合に、前記第１の文字情報および第１のファイルの識別情報により示される前記記憶部内の記憶領域から、前記第１のファイルが前記第１の文字情報を含むこと、または前記第１のファイルと異なる第２のファイルが第２の文字情報を含むことのいずれかの条件を満たすか否かを示す存否情報を読み出す読出し部と、
読み出した前記存否情報が前記いずれかの条件を満たす旨を示す場合に、前記第１のファイルを、前記第１の文字情報に基づく文字列検索の対象と判断する判断部と、
を含むことを特徴とする検索装置。
【請求項１５】
第１の文字情報および第１のファイルの識別情報により示される記憶領域に、前記第１のファイルが前記第１の文字情報を含むこと、または前記第１のファイルと異なる第２のファイルが第２の文字情報を含むことのいずれかの条件を満たすか否かを示す存否情報を記憶するメモリと、
前記第１の文字情報を含む検索要求を受けた場合に、前記存否情報を読出し、
読み出した前記存否情報が前記いずれかの条件を満たす旨を示す場合に、前記第１のファイルを、前記第１の文字情報に基づく文字列検索の対象と判断する、
処理を実行するプロセッサと、
を含む検索装置。 
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００２７
【補正方法】変更
【補正の内容】
【００２７】
図１Ｂに示すビット列Ａ１において、「１」となるビットに対応するファイル（図１Ｂにおいては、ファイル番号ｉのファイル）が、文字列検索対象のファイルとなる。図１Ａの例においては、アドレスＰｋに複数の文字情報（例えば、「見れ」及び「劇王」）が対応する。ファイルＦｉは、「劇王」は含まないが、「見れ」を含む。そのため、「見れ」及び「劇王」に対応するアドレスＰｋに対応するビット列における、ファイルＦｉのビットも「１」となってしまう。そのようなインデックス情報Ｉ１を用いて、文字情報「喜劇」および「劇王」で検索対象のファイルを絞り込むと、ファイルＦｉに「劇王」が含まれないにも関わらず、「喜劇」と「劇王」の双方を含むファイルと判断され、検索対象のファイルとなる。 
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００３７
【補正方法】変更
【補正の内容】
【００３７】
さらに、例えば、ファイル番号が「５２」よりも１大きい「５３」であるファイルＦ５３における「喜劇」の存否情報は、ファイルＦ５２における「喜劇」の存否情報を格納するアドレス「９１５０」よりも１大きい「９１５１」となる。図３Ａの引数は、ファイル番号についてビットのシフトをしていないので、剰余によりアドレスを求めると、同じ「喜劇」に関する存否情報を格納するアドレスは連続する。例えば、ファイル番号０として、文字情報「喜劇」の存否情報の格納先アドレスを算出すると、「９０９８」となる。すると、ファイル番号１〜ｎに対応するファイル群Ｆ１〜Ｆｎのそれぞれにおける「喜劇」の存否情報を格納するアドレスは、「９０９８＋１」〜「９０９８＋ｎ」という連続する値をとる。ファイル群Ｆ１〜Ｆｎのそれぞれにおける「喜劇」の存否を示すビット列Ａ３−２は、図３Ｂに示す通り、インデックス情報Ｉ３の対応する位置のビットに反映される。ファイル群Ｆ１〜Ｆｎのそれぞれにおける「見れ」の存否を示すビット列Ａ３−１も、図３Ｂに示す通り、インデックス情報Ｉ３の対応する位置のビットに反映される。ビット列Ａ３−１とビット列Ａ３−２とで、インデックス情報Ｉ３の反映する部分が重なるが、上述の通り、双方のビット列の論理和が格納される。 
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００４８
【補正方法】変更
【補正の内容】
【００４８】
入力デバイス３０７は、操作に応じて入力信号を送信する装置である。入力デバイス３０７は、例えば、キーボードやコンピュータ１の本体に取り付けられたボタンなどのキー装置や、マウスやタッチパネルなどのポインティングデバイスである。出力デバイス３０９は、コンピュータ１の制御に応じて情報を出力する装置である。出力デバイス３０９は、例えば、ディスプレイなどの画像出力装置（表示デバイス）や、スピーカーなどの音声出力装置などである。また、例えば、タッチスクリーンなどの入出力装置が、入力デバイス３０７及び出力デバイス３０９として用いられる。 
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００５０
【補正方法】変更
【補正の内容】
【００５０】
図８は、コンピュータ１で動作するソフトウェアの構成例を示す。コンピュータ１において、図７に示すハードウェア群２１の制御を行なうＯＳ２２（オペレーティングシステム）が動作する。ＯＳ２２に従った手順でプロセッサ３０１が動作して、ハードウェア２１の制御・管理が行なわれることにより、アプリケーションプログラムやミドルウェアによる処理がハードウェア２１により実行される。さらに、コンピュータ１において、例えば、インデックス生成プログラム２３ａや検索処理プログラム２３ｂなどが、ＲＡＭ３０２に読み出されてプロセッサ３０１により実行される。また、プロセッサ３０１がインデックス生成プログラム２３ａに基づく処理を行なうことにより、（それらの処理をＯＳ２２に基づいてハードウェア２１を制御して）インデックス生成部１３の機能が実現される。さらに、プロセッサ３０１が検索処理プログラム２３ｂに基づく処理を行なうことにより、（それらの処理をＯＳ２２に基づいてハードウェア２１を制御して）検索制御部１４、ファイル絞込部１５および文字列検索部１６の機能が実現される。図８にはインデックス生成プログラム２３ａと検索処理プログラム２３ｂとが別のプログラムとして示されているが、両プログラムを併せて１つのプログラムとしてもよい。 
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００５５
【補正方法】変更
【補正の内容】
【００５５】
図１０は、全文検索の処理手順例を示す。検索処理プログラム２３ｂが起動される（Ｓ２００）と、検索制御部１４は、前処理を行なう（Ｓ２０１）。Ｓ２０１の前処理は、図１２に示すテーブルＴ１の読出しや、インデックス情報の読出しである。検索制御部１４は、検索要求を受けたか否かを判断し（Ｓ２０２）、検索要求を受けるまでＳ２０２の判断を繰り返す（Ｓ２０２：ＮＯ）。検索要求を受けた場合（Ｓ２０２：ＹＥＳ）には、インデックス参照処理が実行される（Ｓ２０３）。 
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００６２
【補正方法】変更
【補正の内容】
【００６２】
Ｓ２０９処理後に、処理部１１は、終了の指示があったか否かを判断する（Ｓ２１０）。終了の指示がない場合（Ｓ２１０：ＮＯ）には、検索制御部１４はＳ２０２の処理を行なう。終了の指示があった場合には（Ｓ２１０：ＹＥＳ）、処理部１１は、検索処理プログラム２３ｂを終了させる（Ｓ２１１）。 
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００６５
【補正方法】変更
【補正の内容】
【００６５】
例えば、「１３」に対応する文字情報Ｃ１３があるとすると、引数１３×４を「１３」で除算した剰余は０となるため、アドレスがＣ０と同じになる。Ｃ０〜Ｃ１２までの文字情報については、それぞれ別のアドレスが割り当てられている。 
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】００６６
【補正方法】変更
【補正の内容】
【００６６】
同じファイルについての存否情報の格納先アドレスの種類の数は、２のα乗と除数Ｄとの最小公倍数Ｘによって決まる。最小公倍数Ｘを２のα乗で除算した値Ｙが、とり得るアドレスの種類の数である。２のα乗と除数Ｄとが互いに素であれば、除数Ｄがとり得るアドレスの種類の数である。２のα乗と互いに素な数として、奇数を除数Ｄにすればよい。
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】００７３
【補正方法】変更
【補正の内容】
【００７３】
図１５は、異なる関数ｆ１，ｆ２を用いたインデックス情報の関係を示す。図１５Ａは、図３Ｂに示したビット列Ａ３−1，Ａ３−２，Ａ３−３とインデックス情報の数値範囲との関係を示す。また、図１５Ｂは、図１５Ａに示すインデックス情報に用いられる関数ｆ１とは異なる関数ｆ２に基づいて作成されたインデックス情報におけるビット列Ａ３−１、Ａ３−２，Ａ３−３，Ａ３−４と、インデックス情報の数値範囲との関係を示す。図１５Ａに示す通り、ビット列Ａ３−１とビット列Ａ３−２とで、存否情報をインデックス情報に反映させる範囲が一部重複している。上述の通り、重複する部分においては、例えば、ファイルＦ４０８６における文字情報「見れ」の存否情報と、ファイルＦ１における文字情報「喜劇」の存否情報とが重複した位置に反映されていた。一方、図１５Ｂに示すインデックス情報においては、ビット列Ａ３−１を反映させる範囲と、ビット列Ａ３−２を反映させる範囲とが重複しない。そのため、文字情報「喜劇」の存否情報と文字情報「見れ」の存否情報とは、インデックス情報内の異なる部分に反映される。一方で、ビット列Ａ３−１とビット列Ａ３−４とで、反映させる範囲が一部重複している。ビット列Ａ３−４は、文字情報「喜劇」、「見れ」、「劇王」以外の文字情報のファイル群Ｆ１〜Ｆｎにおける存否情報を示すビット列である。この場合、図１５Ｂに示すインデックス情報内で、ファイルＦ４０８６における文字情報「見れ」の存否情報と重複して反映される存否情報は、図１５Ａにおける重複箇所のように、ファイル１とは限らない。むしろその他のファイルのことの方が多い。すると、極めて文字情報の種類が多いファイルが存在する場合にも、そのファイルと反映する箇所が重複することにより、文字情報を含まないことがインデックス情報内に存在することが抑制される。
［第３の実施形態］
第３の実施形態について説明する。第３の実施形態のインデックス情報は、文字情報Ｃｊに基づいて文字情報Ｃｊに対応するビット列が定められ、文字情報Ｃｊとファイル番号との双方に基づいて存否情報を格納するビット列内の位置が定められる。 
【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】００７６
【補正方法】変更
【補正の内容】
【００７６】
図１６は、第３の実施形態におけるインデックス情報内のビット列の例を示す。ビット列Ａ４−１は、文字情報「劇王」に対応する存否情報の例を示す。アドレスＹ１は、ハッシュ関数に文字情報「劇王」に対応するバイナリコードを代入して得られる。ｑ１＝ＱＵＯＴＩＥＮＴ（“劇王”／Ｄ）とすると、ビット列Ａ４−１は、ファイル群Ｆ１〜Ｆｎのそれぞれについての存否情報がｑ１ビットシフトされたビット列となる。ビット列Ａ４−２は、文字情報「見れ」に対応する存否情報の例を示す。アドレスＹ２は、ハッシュ関数に文字情報「見れ」に対応するバイナリコードを代入して得られる。ｑ２＝ＱＵＯＴＩＥＮＴ（“見れ”／Ｄ）とすると、ビット列Ａ４−２は、ファイル群Ｆ１〜Ｆｎのそれぞれについての存否情報がｑ２ビットシフトされたビット列となる。図１６の例のように、「劇王」のアドレスと「見れ」のアドレスとが一致する場合（Ｙ１＝Ｙ２）には、インデックス情報内のＹ１（もしくはＹ２）のビット列は、ビット列Ａ４−1とビット列Ａ４−２との論理和（ＯＲ）であるビット列Ａ４−３となる。
【国際調査報告】
2013175537.tif 000019
2013175537.tif 000020