"プログラムを実行するプロセッサと、前記プロセッサによって実行されるプログラムを格納するメモリと、を備え、検索キーワードの入力を受け付け、文書における前記入力された検索キーワードの文書内位置を検索する文書検索システムであって、前記プロセッサが、前記文書を構成する接尾辞を辞書順に並べた接尾辞配列データを生成する接尾辞配列データ生成部と、前記プロセッサが、前記接尾辞配列データにおいて前記辞書順に並べられた接尾辞のうち一部の接尾辞の文書内位置をサンプリングするサンプリング部と、前記プロセッサが、前記文書内で前記接尾辞の前にある一文字を追加した接尾辞の前記接尾辞配列データにおける対応箇所を特定する一文字前接尾辞特定処理を実行する一文字前接尾辞特定処理実行部と、前記プロセッサが、前記サンプリング部によって前記文書内位置がサンプリングされなかった前記接尾辞に対して、前記一文字前接尾辞特定処理を繰り返し実行することによって、当該接尾辞の直近のサンプリングされた接尾辞の文書内位置に基づいて、当該接尾辞の文書内位置を特定する文書内位置特定部と、を備え、前記文書内位置特定部は、前記接尾辞配列データの任意の連続区間に含まれる接尾辞のうち、前記接尾辞の一文字前にある文字が一致するすべての接尾辞の中から最初の接尾辞及び最後の接尾辞を特定し、前記一文字前接尾辞特定処理実行部は、前記特定した最初の接尾辞及び最後の接尾辞に対して、前記一文字前接尾辞特定処理を実行し、前記文書内位置特定部は、前記最初の接尾辞及び最後の接尾辞に対する前記一文字前接尾辞特定処理の実行によって特定された二つの接尾辞に挟まれる区間を、前記接尾辞の一文字前にある文字が一致するすべての接尾辞に対する前記一文字前接尾辞特定処理の結果とすることを特徴とする文書検索システム。前記文書検索システムは、前記プロセッサが、前記接尾辞配列データに含まれる各接尾辞に対して、前記サンプリング部によって文書内位置がサンプリングされた接尾辞から前記接尾辞に到達するまでの前記一文字前接尾辞特定処理の実行回数の最小値であるサンプル距離値を含むサンプル距離データを生成するサンプル距離データ生成部を備え、前記文書内位置特定部は、前記プロセッサが、前記連続区間において前記接尾辞の一文字前にある文字が一致する接尾辞に対して前記一文字前接尾辞特定処理実行部に前記一文字前接尾辞特定処理を実行させるか否かを判定する一文字前接尾辞特定処理実行判定部を備え、前記一文字前接尾辞特定処理実行判定部は、前記区間に到達するまでの前記一文字前接尾辞特定処理を実行した回数が、前記区間に含まれる接尾辞に対する前記サンプル距離値の最大値よりも小さければ、前記一文字前接尾辞特定処理実行部に前記一文字前接尾辞特定処理を実行させる必要があると判定することを特徴とする請求項1に記載の文書検索システム。前記サンプル距離データが、前記接尾辞配列データにおける各接尾辞の位置を示す第1軸、及び、前記接尾辞配列データにおける各接尾辞の位置に対応する前記サンプル距離値を示す第2軸からなる2次元領域に、各接尾辞に対応する前記サンプル距離値を点で格納するウェーブレット木形式で記憶され、前記一文字前接尾辞特定処理実行判定部は、前記ウェーブレット木形式で記憶した前記サンプル距離データに対して、前記区間の範囲によって特定される前記第1軸上の範囲であって、かつ、前記一文字前接尾辞特定処理の実行回数に1を加えた値以上の前記第2軸上の範囲に前記サンプル距離値を示す点が存在する場合、前記一文字前接尾辞特定処理実行部に前記一文字前接尾辞特定処理を実行させる必要があると判定することを特徴とする請求項2に記載の文書検索システム。前記文書内位置データ生成部は、予め設定された文字数間隔で、前記接尾辞と当該接尾辞の文書内位置とを対応付けた前記文書内位置データを生成し、前記文字数間隔に位置しない接尾辞であっても、当該接尾辞の前記接尾辞配列データにおける位置を中心とする、ユーザが指定した大きさの範囲にある前記接尾辞の1文字前にある文字が、当該接尾辞の1文字前にある文字と一致しない場合、当該接尾辞の前記文書内位置データを生成することを特徴とする請求項1から請求項3のいずれか一つに記載の文書検索システム。前記接尾辞の文書内位置が前記文書内位置特定部によって特定された場合、前記プロセッサが、前記特定した文書内位置を表示する表示部を備え、前記表示部は、ある接尾辞の前記文書内位置を前記一文字前接尾辞特定処理実行部に前記一文字前接尾辞特定処理を実行させて特定した場合に、前記文書内位置が重複する場合、重複した文書内位置を一つの文書内位置として表示することを特徴とすることを特徴とする請求項4に記載の文書検索システム。プログラムを実行するプロセッサと、前記プロセッサによって実行されるプログラムを格納するメモリと、を備える文書検索システムにおける、検索キーワードの入力を受け付け、文書における前記入力された検索キーワードの文書内位置を検索する文書検索方法であって、前記方法は、前記プロセッサが、前記文書を構成する接尾辞を辞書順に並べた接尾辞配列データを生成する接尾辞配列データ生成ステップと、前記プロセッサが、前記接尾辞配列データにおいて前記辞書順に並べられた接尾辞のうち一部の接尾辞の文書内位置をサンプリングするサンプリングステップと、前記プロセッサが、前記文書内で前記接尾辞の前にある一文字を追加した接尾辞の前記接尾辞配列データにおける対応箇所を特定する一文字前接尾辞特定処理を実行する一文字前接尾辞特定処理実行ステップと、前記プロセッサが、前記サンプリングステップによって前記文書内位置がサンプリングされなかった前記接尾辞に対して、前記一文字前接尾辞特定処理を繰り返し実行することによって、当該接尾辞の直近のサンプリングされた接尾辞の文書内位置に基づいて、当該接尾辞の文書内位置を特定する文書内位置特定ステップと、を含み、前記文書内位置特定ステップでは、前記接尾辞配列データの任意の連続区間に含まれる接尾辞のうち、前記接尾辞の一文字前にある文字が一致するすべての接尾辞の中から最初の接尾辞及び最後の接尾辞を特定し、前記一文字前接尾辞特定処理実行ステップでは、前記特定した最初の接尾辞及び最後の接尾辞に対して、前記一文字前接尾辞特定処理を実行し、前記文書内位置特定ステップは、前記最初の接尾辞及び最後の接尾辞に対する前記一文字前接尾辞特定処理の実行によって特定された二つの接尾辞に挟まれる区間を、前記接尾辞の一文字前にある文字が一致するすべての接尾辞に対する前記一文字前接尾辞特定処理の結果とすることを特徴とする文書検索方法。前記方法は、前記プロセッサが、前記接尾辞配列データに含まれる各接尾辞に対して、前記サンプリング部によって文書内位置がサンプリングされた接尾辞から前記接尾辞に到達するまでの前記一文字前接尾辞特定処理の実行回数の最小値であるサンプル距離値を含むサンプル距離データを生成するサンプル距離データ生成ステップを含み、前記文書内位置特定ステップは、前記プロセッサが、前記連続区間において前記接尾辞の一文字前にある文字が一致する接尾辞に対して前記一文字前接尾辞特定処理実行部に前記一文字前接尾辞特定処理を実行させるか否かを判定する一文字前接尾辞特定処理実行判定ステップを含み、前記一文字前接尾辞特定処理実行判定ステップでは、前記区間に到達するまでの前記一文字前接尾辞特定処理を実行した回数が、前記区間に含まれる接尾辞に対する前記サンプル距離値の最大値よりも小さければ、前記一文字前接尾辞特定処理実行部に前記一文字前接尾辞特定処理を実行させる必要があると判定することを特徴とする請求項6に記載の文書検索方法。前記サンプル距離データは、前記接尾辞配列データにおける各接尾辞の位置を示す第1軸、及び、前記接尾辞配列データにおける各接尾辞の位置に対応する前記サンプル距離値を示す第2軸からなる2次元領域に、各接尾辞に対応する前記サンプル距離値を点で格納するウェーブレット木形式で記憶するデータであり、前記一文字前接尾辞特定処理実行判定ステップでは、前記ウェーブレット木形式で記憶した前記サンプル距離データに対して、前記区間の範囲によって特定される前記第1軸上の範囲であって、かつ、前記一文字前接尾辞特定処理の実行回数に1を加えた値以上の前記第2軸上の範囲に前記サンプル距離値を示す点が存在する場合、前記一文字前接尾辞特定処理実行部に前記一文字前接尾辞特定処理を実行させる必要があると判定することを特徴とする請求項7に記載の文書検索方法。前記文書内位置データ生成ステップは、予め設定された文字数間隔で、前記接尾辞と当該接尾辞の文書内位置とを対応付けた前記文書内位置データを生成するステップと、前記文字数間隔に位置しない接尾辞であっても、当該接尾辞の前記接尾辞配列データにおける位置を中心とする、ユーザが指定した大きさの前記接尾辞の1文字前にある文字が、当該接尾辞の1文字前にある文字と一致しない場合、当該接尾辞の前記文書内位置データを生成するステップと、を含むことを特徴とする請求項6から請求項8のいずれか一つに記載の文書検索方法。前記方法は、前記接尾辞の文書内位置が前記文書内位置特定部によって特定された場合、前記プロセッサが前記特定した文書内位置を表示する表示ステップを含み、前記表示ステップでは、ある接尾辞の前記文書内位置を前記一文字前接尾辞特定処理実行ステップに前記一文字前接尾辞特定処理を実行させて特定した場合に、前記文書内位置が重複する場合、重複した文書内位置を一つの文書内位置として表示することを特徴とすることを特徴とする請求項9に記載の文書検索方法。プログラムを実行するプロセッサと、前記プロセッサによって実行されるプログラムを格納するメモリと、を備える文書検索システムにおいて、検索キーワードの入力を受け付け、文書における前記入力された検索キーワードの文書内位置を検索する処理を前記プロセッサに実行させるプログラムにおいて、前記処理は、前記文書を構成する接尾辞を辞書順に並べた接尾辞配列データを前記プロセッサに生成させる接尾辞配列データ生成ステップと、前記接尾辞配列データにおいて前記辞書順に並べられた接尾辞のうち一部の接尾辞の文書内位置を前記プロセッサにサンプリングさせるサンプリングステップと、前記文書内で前記接尾辞の前にある一文字を追加した接尾辞の前記接尾辞配列データにおける対応個所を特定する一文字前接尾辞特定処理を前記プロセッサに実行させる一文字前接尾辞特定処理実行ステップと、前記サンプリングステップによって前記文書内位置がサンプリングされなかった前記接尾辞に対して、前記一文字前接尾辞特定処理を繰り返し実行することによって、当該接尾辞の直近のサンプリングされた接尾辞の文書内位置に基づいて、当該接尾辞の文書内位置を前記プロセッサに特定させる文書内位置特定ステップと、を含み、前記文書内位置特定ステップでは、前記接尾辞配列データの任意の連続区間に含まれる接尾辞のうち、前記接尾辞の一文字前にある文字が一致するすべての接尾辞の中から最初の接尾辞及び最後の接尾辞を特定し、前記一文字前接尾辞特定処理実行ステップでは、前記特定した最初の接尾辞及び最後の接尾辞に対して、前記一文字前接尾辞特定処理を実行し、前記文書内位置特定ステップは、前記最初の接尾辞及び最後の接尾辞に対する前記一文字前接尾辞特定処理の実行によって特定された二つの接尾辞に挟まれる区間を、前記接尾辞の一文字前にある文字が一致するすべての接尾辞に対する前記一文字前接尾辞特定処理の結果とすることを特徴とするプログラム。図23は、検索キーワード特徴が出現する文書番号及び文書内位置の算出する従来法の説明図である。検索キーワードに対応するcontext範囲301は、非特許文献2に記載されたbackwardsearchによって算出できる。しかし、このcontext範囲301には、文書番号及び文書内位置がサンプリングされている接尾辞は二つしかない。このため、他の接尾辞の文書番号及び文書内位置はLF-mapping処理を実行することによって特定する必要がある。ここで、context範囲301のすべての接尾辞の文書番号及び文書内位置が特定されるために実行されるLF-mapping処理を、図23の破線の矢印302で示した。図23では、合計7回のLF-mapping処理が必要となる。ここで、検索キーワードがで始まる接尾辞のcontextの数をn、サンプリング間隔をbとすれば、平均nb-1/2回のLFmapping処理が必要である。nはキーワードの出現回数であるので、文書中に高頻度で出現するキーワードではwが非常に大きくなり、このLF-mapping処理の実行回数が検索性能のボトルネックになる。このため、大規模な検索システムへの適用は困難であった。本発明は、検索キーワードが出現する文書内位置を計算するために必要なLF-mapping処理一文字前接尾辞特定処理の実行回数を削減する文書検索システムを提供することを目的とする。本発明の代表的な一例を示せば、プログラムを実行するプロセッサと、前記プロセッサによって実行されるプログラムを格納するメモリと、を備え、検索キーワードの入力を受け付け、文書における前記入力された検索キーワードの文書内位置を検索する文書検索システムであって、前記プロセッサが、前記文書を構成する接尾辞を辞書順に並べた接尾辞配列データを生成する接尾辞配列データ生成部と、前記プロセッサが、前記接尾辞配列データにおいて前記辞書順に並べられた接尾辞のうち一部の接尾辞の文書内位置をサンプリングするサンプリング部と、前記プロセッサが、前記文書内で前記接尾辞の前にある一文字を追加した接尾辞の前記接尾辞配列データにおける対応箇所を特定する一文字前接尾辞特定処理を実行する一文字前接尾辞特定処理実行部と、前記プロセッサが、前記サンプリング部によって前記文書内位置がサンプリングされなかった前記接尾辞に対して、前記一文字前接尾辞特定処理を繰り返し実行することによって、当該接尾辞の直近のサンプリングされた接尾辞の文書内位置に基づいて、当該接尾辞の文書内位置を特定する文書内位置特定部と、を備え、前記文書内位置特定部は、前記接尾辞配列データの任意の連続区間に含まれる接尾辞のうち、前記接尾辞の一文字前にある文字が一致するすべての接尾辞の中から最初の接尾辞及び最後の接尾辞を特定し、前記一文字前接尾辞特定処理実行部は、前記特定した最初の接尾辞及び最後の接尾辞に対して、前記一文字前接尾辞特定処理を実行し、前記文書内位置特定部は、前記最初の接尾辞及び最後の接尾辞に対する前記一文字前接尾辞特定処理の実行によって特定された二つの接尾辞に挟まれる区間を、前記接尾辞の一文字前にある文字が一致するすべての接尾辞に対する前記一文字前接尾辞特定処理の結果とすることを特徴とする。本発明によれば、検索キーワードが出現する文書内位置を計算するために必要な一文字前接尾辞特定処理の実行回数を削減する文書検索システムを提供できる。以下、本発明の実施の形態について図面を参照しつつ説明する。第1の実施形態以下、本発明の第1実施の形態について、図1~図9を用いて説明する。図1は、本発明の第1実施形態の文書検索装置1の構成の説明図である。文書検索装置1は、CPUCentralProcessingUnitプロセッサ401、主記憶装置メモリ402、補助記憶装置403、リムーバブルメディア404、及びユーザインタフェース部406を備える。この文書検索装置1は、LANLocalAreaNetwork等のネットワーク405を介して外部のネットワークに接続されている。CPU401は、主記憶装置402に格納されたプログラム接尾辞配列構築手段407、BWT構築手段408、サンプリング手段409、及び、検索手段410の機能を実現するプログラムを実行する中央演算装置である。接尾辞配列構築手段407は、文書集合データ101から接尾辞配列105図2参照を構築する。BWT構築手段408は、接尾辞配列の各接尾辞の一つ前の文字を格納した配列であるBWT107を構築する。サンプリング手段409は、接尾辞配列105の一部の接尾辞の文書内位置をサンプリングし、サンプリングされた接尾辞配列を構築する。検索手段410は、文書検索装置1に入力された検索キーワードを含む文書及び当該検索キーワードの文書内位置を検索する。主記憶装置402は、接尾辞配列構築手段407、BWT構築手段408、サンプリング手段409、及び、検索手段410の機能を実現するプログラム、当該プログラムの実行に用いるサンプリングされた接尾辞配列204、及びBWT107等を記憶するRAMRandomAccessMemory等の記憶装置である。文書集合データ101、及び接尾辞配列105も、必要があれば一時的に記憶する。補助記憶装置403は、文書集合データ101、サンプリングされた接尾辞配列204、及びBWT107等を記憶するHDD等の記憶装置である。リムーバブルメディア404は、文書集合データ101、サンプリングされた接尾辞配列204、及びBWT107等を記録したCD-ROM及びDVD等の記録媒体である。補助記憶装置403及びリムーバブルメディア404に記録された各データは、必要に応じて文書検索装置1の起動時に主記憶装置402に読み出される。ユーザインタフェース部406は、ユーザインタフェースを提供する入出力装置例えば、キーボード、マウス、及びディスプレイ等である。以上に示す装置構成において、CPU401は、主記憶装置402、補助記憶装置403、リムーバブルメディア404、又は、ネットワーク405を介した外部から、必要に応じて文書集合データ101を取得する。その後、CPU401は、取得した文書集合データ101に基づいて、接尾辞配列、BWT107、及びサンプリングされた接尾辞配列204を構築する。なお、接尾辞配列構築手段407、BWT構築手段408、サンプリング手段409、及び検索手段410は、これらのプログラムが他の計算機によって実行されることによって実現されてもよい。このため、接尾辞配列手段407、BWT構築手段408、サンプリング手段409、及び検索手段410を実現する計算機をまとめて、文書検索システムという。図2は、本発明の第1の実施形態の接尾辞配列105、BWT107及びサンプリングされた接尾辞配列204の構築処理の概要の説明図である。1接尾辞配列105の構築まず、接尾辞配列構築手段407は、文書検索装置1に入力された文書集合データ101に基づいて、接尾辞配列105を構築する。具体的には、接尾辞配列構築手段407は、文書集合データ101に含まれるすべての文書102図20参照のすべての接尾辞103を抽出する。次に、接尾辞配列構築手段407は、抽出された各接尾辞を辞書順にソートすることによって、ソート結果104図7参照を生成し、接尾辞配列105を構築する。接尾辞配列構築手段407によって構築される接尾辞配列105は、すべての接尾辞の文書番号及び文書内位置を含む。なお、接尾辞配列構築手段407は、他の方法によって接尾辞配列105を構築してもよい。接尾辞配列105を構築する他の具体的な方法は、例えば、PuglisietalAtaxonomyofsuffixarrayconstructionalgorithmsACMcomputingsurveys39Article42007に記載されている。2BWT107の構築BWT構築手段408は、接尾辞配列105の各接尾辞のBWT107を構築する。具体的には、BWT構築手段408は、接尾辞配列105において、contextiの文書番号がdで文書内位置がpであれば、文書dの位置p-1の文字をBWTのi番目の文字BWTiにセットすればよい。ただし、p=0である場合、BWTiにをセットする。なお、BWT構築手段408は、他の方法によってBWT107を構築してもよい。BWT107を構築する他の具体的な方法は、例えば、MakinenVandNavarroGDynamicentropycompressedsequencesandfulltextindexesACMTransactionsonalgorithms4Article322008に記載されている。3接尾辞配列105のサンプリングサンプリング手段409は、接尾辞配列105の文書内位置pがサンプリング間隔bで割り切れる接尾辞の文書番号及び文書内位置を抽出するサンプリングすることによってサンプリングされた接尾辞配列204を構築する。なお、サンプリング手段409による処理は、図4で詳細を説明する。図3は、本発明の第1実施形態の接尾辞配列105、BWT107、及びサンプリングされた接尾辞配列204の構築処理のデータの流れの説明図である。まず、ユーザインタフェース部406を介して文書集合データ101が文書検索装置1に入力され、CPU401は、入力された文書集合データをメモリ402に格納する。文書集合データ101は、ユーザインタフェース部406に限らず、補助記憶装置403、リムーバブルメディア404、又はネットワーク405を介して文書検索装置1に入力してもよい。次に、CPU401は、接尾辞配列構築手段407として機能するプログラムを実行し、メモリ402上に接尾辞配列105を構築する。次に、CPU401は、BWT構築手段408として機能するプログラムを実行し、接尾辞配列105の各contextに対応する文書番号及び文書内位置を参照し、メモリ402上でBWT107を構築し、構築したBWT107をウェーブレット木形式で補助記憶装置403又はネットワーク405に接続される記憶領域に格納する。次に、CPU401は、サンプリング手段409として機能するプログラムを実行し、文書内位置がサンプリング間隔で割り切れる接尾辞の文書番号及び文書内位置を抽出し、抽出した文書番号及び文書内位置をサンプリングされた接尾辞配列204として補助記憶装置403又はネットワーク405に接続される記憶領域に格納する。CPU401は、以上の処理の実行が終了すると、構築処理終了通知をユーザインタフェース部406に出力する。このため、接尾辞配列105は補助記憶装置403に格納されることはなく、サンプリングされた接尾辞配列204が補助記憶装置403に格納される。このため、検索キーワードの文書内位置を検索する場合、サンプリングされた接尾辞配列204に基づいて、文書内位置が検索される。図4は、本発明の第1実施形態のサンプリング手段409によって実行されるサンプリング処理のフローチャートである。サンプリング処理は、CPU401によって実行される。まず、CPU401は、文書番号を示す変数dに0をセットするS701。そして、CPU401は、サンプリング間隔を示す変数bにパラメータとして与えられるサンプリング間隔をセットするS702。CPU401は、すべての文書に対してサンプリング処理を実行したか否かを判定するために、変数dがすべての文書数以上であるか否かを判定するS703。S703の処理で、すべての文書に対してサンプリング処理が実行されたと判定された場合、つまり、変数dがすべての文書数以上であると判定された場合S703:YES、サンプリング処理を終了する。一方、S703の処理で、すべての文書に対してサンプリング処理が実行されていないと判定された場合、つまり、変数dがすべての文書数未満であると判定された場合S703:NO、CPU401は、文書内位置を示す変数pに文書番号を示す変数dによって特定される文書の文書長をセットし、contextを示す変数iに文書番号を示す変数dにセットされた値をセットするS704。S704の処理で、contextを示す変数iに変数dにセットされた値をセットする理由について説明する。S704では、文書内位置を示す変数pには、変数dによって特定される文書の文書長がセットされるため、変数pが示す文書内位置は、当該文書の最後の接尾辞であるとなる。この接尾辞は前述の通り、以外のすべての文字よりも辞書順が小さく、同士では文書番号によって辞書順が決まるので、当該接尾辞の接尾辞配列105におけるcontext番号は文書番号を示す変数dと同じ値となる。このため、S704の処理では、変数iに変数dにセットされた値をセットする。以降の処理で当該contextからLF-mapping処理一文字前接尾辞特定処理が繰り返し実行されるので、本サンプリング処理では、文書番号を示す変数dによって特定される文書を右から左に走査しつつサンプリングするか否かを判定していくことになる。次に、CPU401は、サンプリングの要否判定処理を実行するS705。具体的には、CPU401は、文書内位置を示す変数pがサンプリング間隔を示す変数bで割り切れる場合、サンプリングが必要と判定し、変数pが変数bで割り切れない場合、サンプリングは不要と判定する。S705の処理で、サンプリングが必要と判定された場合、CPU401は、接尾辞配列105のcontextiの文書番号を変数dの値から、文書内位置を変数pの値から抽出し、抽出した文書番号及び文書内位置をサンプリングされた接尾辞配列204に格納しS706、S707の処理に移行する。一方、S705の処理で、サンプリングが不要と判定された場合、直ちにS707の処理に移行する。CPU401は、変数dによって特定される文書のすべての文字に対してサンプリングの要否を判定したか否かを判定するS707。具体的には、CPU401は、文書内位置を示す変数pが0より大きければ、文書内位置が文書の先頭に達しておらず、変数dによって特定される文書のすべての文字に対してサンプリングの要否を判定していないとする。一方、CPU401は、文書内位置を示す変数pが0以下であれば、文書内位置が文書の先頭に達しており、変数dによって特定される文書のすべての文字に対してサンプリングの要否を判定したものとする。S707の処理で、変数dによって特定される文書に未処理の位置があると判定された場合、CPU401は、文書内位置を示す変数pから1を減じた値を変数pにセットし、contextを示す変数iにLFiをセットしS708、S705の処理に移行する。LFiは、contextiにLF-mapping処理を実行することによって、contextiが示す接尾辞の一文字左一文字前の接尾辞のcontextを示す。一方、S707の処理で、変数dによって特定される文書に未処理の位置がないと判定された場合、CPU401は、文書番号を示す変数dに1を加えた値を変数dにセットしS709、S703の処理に移行する。以上によって、サンプリング間隔の接尾辞ごとに文書番号及び文書内位置を抽出したサンプリングされた接尾辞配列204が構築される。図5は、本発明の第1実施形態の検索手段410による検索処理のデータの流れの説明図である。まずCPU401は、BWT構築手段408が構築したBWT107及びサンプリング手段409が構築したサンプリングされた接尾辞配列204を補助記憶装置403、リムーバブルメディア404又はネットワーク405を介して接続される記憶領域からメモリ402上にロードする503、504。次に、ユーザインタフェース部406を介してユーザから検索キーワードが文書検索装置1に入力される505。CPU401は、検索キーワードが入力された場合、サンプリングされた接尾辞配列204を参照し、検索キーワードから始まる接尾辞の範囲であるcontext範囲を取得する506。そして、CPU401は、BWT107を参照し、506の処理で取得したcontext範囲の各接尾辞のBWT107を取得する507。文書番号及び文書内位置はサンプリング間隔で抽出されているので、506の処理で取得したcontext範囲に属するすべてのcontextの文書番号及び文書内位置が抽出されているとは限らない。このため、CPU401は、507の処理で取得したBWT107を用いて、context範囲に属するcontextにLF-mapping処理を繰り返し実行することによって、context範囲に属するすべてのcontextの文書番号及び文書内位置を特定し508、検索キーワードが出現する文書番号及び文書内位置をユーザインタフェース部406に表示する509。なお、506~508の処理文書内位置特定処理;文書内位置特定部は、図6~図10で詳細を説明する。図6は、本発明の第1実施形態の文書内位置特定処理のフローチャートである。文書内位置特定処理は、検索手段410の機能の一部であり、CPU401によって実行される。以下、図6の処理について説明する。処理例を、図9を用いて後述する。まず、CPU401は、サンプリングされた接尾辞配列204を参照し、検索キーワードwで始まる接尾辞が出現するcontextの範囲を求めるS901。また、接尾辞103は辞書順にソートされているので、検索キーワードwで始まる接尾辞はある範囲に集まっている。このような、特定のキーワードで始まる接尾辞が出現するcontextの範囲を以下ではcontext範囲といい、当該範囲を[c1、c2]と表記する。ここに、c1はcontext範囲の最初のcontext番号開始context番号であり、c2はcontext範囲の最後のcontext番号終了context番号である。なお、検索キーワードwが検索対象文書集合101に存在しない場合は、context範囲[c1,c2]が存在せず、以降の処理は行なわない。なお、S901でcontext範囲を求める具体的な方法には、非特許文献2に記載されたbackwardsearchを用いることができる。以降の処理では、処理対象となるcontext範囲を示す処理対象集合S、並びに、検索キーワードwが出現する位置を計算した結果を格納する集合Hを使用する。なお、処理対象集合Sの個々の要素は、1処理対象となるcontext範囲の開始context番号、2終了context番号、及び3当該context範囲に至るまでに実行されたLF-mapping処理の実行回数の、3つの値からなる数値の三つ組みである。CPU401は、S901で求めたcontext範囲を処理対象集合Sにセットし、文書内位置集合Hを空集合としてセットする、初期化処理を実行するS902。具体的には、CPU401は、処理対象集合Sに、S901の処理で求めたcontext範囲の開始context番号、終了context番号、及びLF-mapping処理実行回数0の3つの数値からなる三つ組みc1、c2、0をSの最初の要素として格納する。なお、S901の処理で、複数のcontext範囲が求められていれば、処理対象集合Sには複数の要素がセットされる。次に、CPU401は、処理対象集合Sが空集合であるか否かを判定するS903。S903の処理で、処理対象集合Sが空集合であると判定された場合、全context範囲の処理が完了しているため、CPU401は、文書内位置集合Hの内容をユーザインタフェース部に出力しS909、文書内位置特定処理を終了する。一方、S903の処理で、処理対象集合Sが空集合でないと判定された場合、CPU401は、処理対象集合Sから任意の一つの要素を取り出すS904。S904の処理で取り出された要素をc1、c2、jとする。CPU401は、S904で取り出された要素を処理対象集合Sから削除する。なお、S904の処理では、CPU401が、LF-mapping実行回数jが小さい要素から取り出すようにしてもよい。次に、CPU401は、S904の処理で取り出された要素c1、c2、jに対して、LF-mapping処理を実行する必要があるか否かを判定するS905。具体的には、CPU401は、S904の処理で取り出された要素に含まれるLF-mapping実行回数jがサンプリング間隔b未満であれば、LF-mapping処理の実行が必要と判定し、S904の処理で取り出された要素に含まれるLF-mapping実行回数jがサンプリング間隔b以上であれば、LF-mapping処理の実行が不要と判定する。LF-mapping処理が必要か否かの判定に、LF-mapping実行回数jとサンプリング間隔bとを用いる理由について説明する。所定の文字からサンプリング間隔の間にある文字の文書番号及び文書内位置は必ず抽出されているので、サンプリング間隔の回数だけLF-mapping処理を実行すれば、所定の文字の直近の文字の文書番号及び文書内位置を必ず取得でき、取得した文書番号及び文書内位置から当該所定の文字の文書番号及び文書内位置を特定できる。このため、LF-mapping実行回数jがサンプリング間隔b以上であれば、処理の実行が不要と判定するようにしている。さらに、S905の処理では、CPU401は、S901の処理で求められたcontext範囲に含まれるすべての接尾辞の文書内位置が特定されているか否かを判定する処理を追加してもよい。この処理では、CPU401は、すべての接尾辞の文書内位置が特定されている場合、処理の実行が不要と判定し、すべての接尾辞の文書内位置が特定されていない場合、LF-mapping処理の実行が必要と判定する。具体的には、文書内位置集合Hに格納された文書番号及び文書内位置の個数がS901の処理で求められたcontext範囲に含まれる接尾辞の個数に達している場合、処理の実行が不要と判定し、文書内位置集合Hに格納された文書番号及び文書内位置の個数がS901の処理で求められたcontext範囲に含まれる接尾辞の個数に達していない場合、処理の実行が必要と判定してもよい。S905の処理で、LF-mapping処理の実行が不要であると判定された場合、CPU401は、S903に処理を移行する。一方、S905の処理で、LF-mapping処理によって文書番号及び文書内位置を取得する処理が必要であると判定された場合、CPU401は、S904の処理で取得された要素に含まれるcontext範囲で抽出された文書番号及び文書内位置を取得し、取得した文書番号、及び取得した文書内位置にLF-mapping処理実行回数jを加えた値を、文書内位置集合Hに格納するS906。ここで、文書内位置集合Hに値を格納する場合、文書内位置にLF-mapping処理実行回数jを加える理由について説明する。S904の処理で取得された要素に含まれるcontext範囲は、S901の処理で求められたcontext範囲つまり、検索キーワードで始まる接尾辞が出現するcontext範囲に対してLF-mapping処理がj回実行された範囲である。したがって、S904の処理で取得された要素に含まれるcontext範囲の接尾辞の文書内位置は、検索キーワードがで始まる接尾辞からj文字左の文字の位置となる。このため、S904の処理で取得された要素に含まれるcontext範囲の接尾辞の文書内位置にLF-mapping実行回数jを加えることによって、検索キーワードが出現する文書内位置を算出している。S906の処理の実行後、CPU401は、S904の処理で取得された要素に含まれるcontext範囲のBWT107の文字を取得し、取得した文字を文字集合Eに格納するS907。なお、BWT107の文字は、BWT107を格納するウェーブレット木を走査することによって取得される。この方法は、MakinenVandNavarroGRankandselectrevisitedandextendedTheoreticalComputerScience3873223472007に記載されている。本発明におけるウェーブレット木の使用方法は、図14を用いて後述する。次に、CPU401は、文字集合Eに格納された各文字aに対して、S904の処理で取得された要素に含まれるcontext範囲においてBWT107が文字aであるcontext番号が最小のcontexti1及び最大のcontexti2に対して、LF-mapping処理を実行し、これらのcontextのLF-mapping先のcontextLFi1及びLFi2を計算する。そして、数値の三つ組LF,LFi2,j1を新たな要素として処理対象集合Sに格納しS908、S903の処理に移行する。これによって、BWT107が同じ文字であるcontext範囲のLF-mapping先のcontext範囲は、当該context範囲のすべてのcontextにLF-mapping処理を実行することなく、LF,LFi2を計算することのみによって算出できる。換言すれば、あるcontext範囲の全てのLF-mappingの結果を、当該context範囲の大きさに関係なく、LF-mapping処理を2回実行するだけ算出できる。以下、この方法でよい理由について、図7及び図8を用いて説明する。図7は、本発明の第1実施形態において、BWT107が同じ文字の接尾辞のLF-mapping先が連続区間であることの、第1説明図である。図7及び図8では、検索キーワードは特徴であり、LF-mapping先のcontext範囲を算出するBWTの文字aがをである場合について説明する。図7及び図8では、contexti1に対応する接尾辞104をxとし、contexti2に対応する接尾辞104をyとする。contexti1及びi2のLF-mapping先はLFi1及びLFi2とする。contexti1のBWT107の文字はaであるので、LFi1に対応する接尾辞104は、contexti1に対応する接尾辞104であるxにaを加えたaxである。同じく、LFi2に対応する接尾辞104はayである。図7のcontexti3のLF-mapping先について検討する。contexti3は、i1<i3<i2かつBWT[i3]=aを満たすcontextである。ここで、contexti3に対応する接尾辞104をzとすると、i1<i3<i2であるので、x<z<yが成立する。そして、contexti1~i3のBWT107はすべてaであるので、LF-mapping先の接尾辞もax<az<ayとなる。このため、LF-mapping先のcontext番号も、LFi1<LFi3<LFi2となる。つまり、BWT107の文字が同一である二つのcontexti1,i2に挟まれる任意のcontexti3は、二つのcontextとBWT107の文字が同じであれば、LF-mapping先LFi3でもLFi1,LFi2に挟まれる。図8は、本発明の第1実施形態において、BWT107が同じ文字の接尾辞のLF-mapping先が連続区間であることの、第2説明図である。図8では、LFi1<i4’<LFi2を満たす任意のcontexti4’について検討する。この場合、LFi1及びLFi2の接尾辞はaで始まるため、contexti4’の接尾辞もaで始まる。このため、contexti4’の接尾辞は、ある文字列tを用いてatと表記できる。LFi1<i4’<LFi2であるのでax<at<ayであり、aは同じ文字あるのでx<w<yである。x、yは、LFi1及びLFi2にLF-mapping処理が実行される前のcontexti1及びi2に対応する接尾辞104であり、tは、i4’にLF-mapping処理が実行される前のcontexti4に対応する接尾辞104である。このため、x<t<yが成立するので、i1<i4<i2が成立する。したがって、LFi1とLFi2に挟まれるcontextへLF-Mappingされるcontextは、全てi1とi2の間にある。以上より、BWTが同じcontextの範囲[i1、i2]が、連続領域[LFi1、LFi2]にLF-mappingされることがわかる。したがって、contexti1及びcontexti2のみに対してLF-mapping処理を実行することによって、連続領域[i1,i2]の全てのcontextのLF-mapping結果を、連続領域[LFi1、LFi2]として計算できる。図9は、本発明の第1実施形態の文書内位置特定処理の説明図である。図6に示す文書内位置特定処理について、図9に示す接尾辞配列を用いて説明する。図9では、検索キーワードwを特徴とし、サンプリング間隔bは4であるとする。S901の処理で、検索キーワードwで始まる接尾辞に対応するcontext範囲として、c1~c2の範囲が求められる。S902の処理で、処理対象集合Sに要素c1、c2、0がセットされ、文書内位置集合Hは空集合としてセットされる。S903の処理では処理対象集合Sは空集合ではないと判定され、S904の処理に進み、c1、c2、0が取り出される。S905の処理では、LF-mapping実行回数は0であり、サンプリング間隔b=4より小さいので、処理が必要であると判定し、S906の処理に進む。S906の処理では、図9に示すc1~c2のcontext範囲の文書番号及び文書内位置959-8432、及び913-3380が取得され、文書内位置集合Hに格納される。この場合、LF-mapping実行回数は0であるので、取得された文書内位置がそのまま文書内位置集合Hに格納される。S907の処理では、図9に示すc1~c2のcontext範囲のBWT107を及び能が取得され、文字集合Eに格納される。S908の処理では、文字集合Eに格納されたをのcontextのLF-mapping先の範囲とLF-mapping回数、及び、文字集合Eに格納された能のcontextのLF-mapping先の範囲とLF-mapping回数が、処理対象集合Sに格納される。具体的には、文字集合Eに格納されたをについては、context番号が最小のc1のLF-mapping先がc3、context番号が最大のc2のLF-mapping先がc4であり、LF-mapping実行回数は1なので、処理対象集合Sには要素c3、c4、1が格納される。このLF-mapping処理を図9で1001として示す。また、文字集合Eに格納された能のcontextは一つであり、当該contextのLF-mapping先はc5であり、LF-mapping実行回数は1回目なので、処理対象集合Sには要素c5、c5、1が格納される。次に、S908の処理が実行された後、S903の処理に戻り、処理対象集合Sが空集合か否かが判定されるが、処理対象集合Sには、二つの要素があるので、S904の処理に進む。S904の処理では、処理対象集合Sから要素c3、c4、1が取り出されるものとする。S905の処理では、S904の処理で取り出された要素のLF-mapping実行回数は1であり、サンプリング回数未満であるので、処理が必要であると判定し、S906の処理に進む。S906の処理では、図9に示すc3~c4のcontext範囲の文書番号及び文書内位置658-8560、及び962-2172が取得され、文書内位置にLF-mapping実行回数1が加算された値658-8561、及び962-2173が文書内位置集合Hに格納される。S907の処理では、図9に示すc3~c4のcontext範囲のBWT107品、と及び能が取得され、文字集合Eに格納される。S908の処理では、文字集合Eに格納された品のcontextのLF-mapping先の範囲、文字集合Eに格納されたとのcontextのLF-mapping先の範囲、及び、文字集合Eに格納された能のcontextのLF-mapping先の範囲が、LF-mapping回数いずれも2とともに処理対象集合Sに格納される。このようにして、処理対象集合Sに格納された要素のLF-mapping実行回数がサンプリング間隔に達するまで、処理対象集合Sに格納されたcontext範囲にLF-mapping処理を実行して、文書番号及び文書内位置を取得する。上述したように、本実施形態では、あるcontext範囲のうちBWTが同じcontext範囲に対してLF-mapping処理が実行された範囲LF-mapping範囲を算出する場合、当該context範囲の中でcontext番号が最小のcontext及び最大のcontextの二つにのみLF-mapping処理を実行して算出されるLF-mapping先のcontext番号を算出し、算出したcontext番号に挟まれる範囲をLF-mapping範囲として算出する。これによって、あるLF-mapping範囲を算出するために実行するLF-mapping処理の実行回数を大幅に減少させることができ、文書検索装置1の処理負荷を軽減できる。第2実施形態以下、本発明の第2実施形態を図10~図16を用いて説明する。第1実施形態では、S905の処理で、LF-mapping実行回数がサンプリング間隔未満であれば、処理の実行が必要と判定されるまで、検索キーワードで始まる接尾辞が出現するcontext範囲のすべての接尾辞の文書番号及び文書内位置が特定されていても、LF-mapping範囲を算出してしまう。例えば、図9では、処理対象集合Sに対してLF-mapping処理を2回実行すれば、検索キーワードで始まる接尾辞が出現するcontext範囲のすべての接尾辞の文書番号及び文書内位置が特定されるが、まだ、LF-mapping実行回数がサンプリング回数に達していないので、処理対象集合Sに対して3回目のLF-mapping処理が実行されてしまう図9に示す1002。第2実施形態は、サンプル距離配列を用いて不要なLF-mapping処理が実行されないようにする実施形態である。図10は、本発明の第2実施形態の文書検索装置2の構成の説明図である。第2実施形態の文書検索装置2の構成のうち第1実施形態の文書検索装置1と同じ構成は、同じ符号を付与し、説明を省略する。文書検索装置2は、第1実施形態と同じく、CPUCentralProcessingUnit401、主記憶装置メモリ402、補助記憶装置403、リムーバブルメディア404、及びユーザインタフェース部406を備える。サンプル距離配列1101が、メモリ402、補助記憶装置403、リムーバブルメディア404、及び、ネットワーク405を介して接続された記憶領域に格納される。サンプル距離配列1101は、ある接尾辞から文書番号及び文書内位置がサンプリングされた接尾辞まで最小の文字数距離が格納された配列である。換言すれば、サンプル距離配列1101は、ある接尾辞に対して文書番号及び文書内位置が取得されるまでに実行するLF-mapping処理の回数が格納された配列ともいえる。サンプリング手段1102は、サンプル距離配列1101を生成する点が第1実施形態のサンプリング手段409と異なる。検索手段1103は、サンプル距離配列1101を参照して検索キーワードを文書から検索する点が第1実施形態の検索手段と異なる。図11は、本発明の第2実施形態の接尾辞配列105、BWT107、サンプリングされた接尾辞配列204、サンプル距離配列1101の構築処理の概要の説明図である。第2実施形態の構築処理のうち図2に示す第1実施形態の構築処理と同じ処理については、同じ符号を付与し、説明を省略する。サンプリング手段1102は、サンプリング処理に、接尾辞配列105の文書内位置pがサンプリング間隔bで割り切れる接尾辞の文書番号及び文書内位置を抽出する他に、サンプル距離配列1101を構築する。第2実施形態のサンプリング処理は、図13で詳細を説明する。図12は、本発明の第2実施形態の接尾辞配列105、BWT107、サンプリングされた接尾辞配列204、及びサンプル距離配列1101の構築処理のデータの流れの説明図である。第2実施形態の構築処理のデータの流れのうち図3に示す第1実施形態の構築処理のデータ流れと同じものについては説明を省略する。図12では、CPU401は、サンプリング手段1102として機能するプログラムを実行し、サンプル距離配列1101をメモリ402上で構築し、構築したサンプル距離配列1101をウェーブレット木化して、補助記憶装置403又はネットワーク405に接続される記憶領域に格納する。図13は、本発明の第2実施形態のサンプリング処理のフローチャートである。サンプリング処理は、サンプリング手段1102の機能の一部であり、CPU401によって実行される。第2実施形態のサンプリング処理のうち図4に示す第1実施形態のサンプリング処理と同じ処理は、同じ符号を付与し、説明を省略する。CPU401は、S701の処理で、文書番号を示す変数dに0をセットし、S702の処理で、サンプリング間隔を示す変数bにサンプリング間隔をセットし、検索対象となるすべての文書の文書長の和に等しい長さの配列Dを作成するS1401。この配列Dにサンプリング距離xが格納されることによってサンプル距離配列1101が構築される。S703の処理で、CPU401は、変数dがすべての文書数以上であるか否かを判定する。S703の処理で、変数dがすべての文書数以上であると判定された場合、CPU401は、配列Dをウェーブレット木TDに格納しS1406、サンプリング処理を終了する。S703の処理で、変数dが検索対象文書数未満であると判定された場合、S704の処理で、CPU401は、文書内位置を示す変数pに変数dによって特定される文書の文書長をセットし、contextを示す変数iに変数dにセットされた値をセットする。次に、CPU401は、文書番号及び文書内位置がサンプリングされた接尾辞までの距離サンプル距離を示す変数xに、サンプリング間隔を示す変数bにセットされた値をセットするS1402。なお、S1402の処理で変数xにセットされる値は、サンプリング間隔と同じ回数分LF-mapping処理を実行しても、サンプリングされた文書内位置に到達できないことを示すものであるので、サンプリング間隔b以上の値であれば、bの値に一致する必要はない。次に、CPU401は、第1実施形態と同様のS705の処理を実行し、サンプリングの要否を判定する。S705の処理で、サンプリングが必要と判定された場合、CPU401は、S706の処理で変数pによって特定される文書内位置の接尾辞の文書番号及び文書内位置を抽出する。そして、CPU401は、サンプル距離を示す変数xに0をセットしS1403、S1405の処理に移行する。一方、S705の処理で、サンプリングが不要と判定された場合、CPU401は、変数xにセットされた値に1を加えた値を変数xにセットしS1404、S1405の処理に移行する。CPU401は、配列Dの要素のうちi番目に対応する要素に、サンプル距離を示す変数xにセットされた値を格納しS1405、S707の処理で、変数dによって特定される文書のすべての文字に対してサンプリングの要否を判定したか否かを判定する。S1405の処理で、変数xにセットされた値がサンプリング間隔を示す変数bにセットされた値以上である場合、CPU401は、配列Dの要素のうち文書内位置を示す変数iに対応する要素に、変数bにセットされた値を格納する。そして、S707の処理で、変数dによって特定される文書の処理が完了していないと判定された場合、CPU401は、S708の処理に移行し、文書内位置を示す変数pの値から1を減じた値を変数pにセットし、contextを示す変数iにLFiをセットし、S708の処理に移行する。一方、S707の処理で、変数dによって特定される文書の処理が完了したと判定された場合、S709の処理で、CPU401は、文書番号を示す変数dの値に1を加えた値を変数dにセットし、S703の処理に移行する。図14は、本発明の第2実施形態のサンプル距離配列1101を格納するウェーブレット木のデータ構造の説明図である。ウェーブレット木というデータ構造は、MakinenVandNavarroGRankandselectrevisitedandextendedTheoreticalComputerScience3873223472007に記載されている。ウェーブレット木のデータ構造は、長方形[0x]×[0y]xyは整数の2次元領域1501上に配置された点の位置を記憶可能なデータ構造である。当該データ構造では、水平方向に必ず一つの点を設ける必要があるが、垂直方向には複数の点を設けてもよいし、点を設けなくてもよい。図14のウェーブレット木は、後述する図16に示すcontextのサンプル距離配列の例を格納したものであり、x方向第2軸はサンプル距離配列に対応し、y方向第1軸はcontextに対応する。すなわち、2次元領域内に、y方向が示す各contextに対応する接尾辞のサンプル距離をx方向の点として格納する。CPU401は、ウェーブレット木を参照することによって、任意の長方形[x1x2]×[y1y2]の領域1502の内部の点1503の総数を、効率よく計算できる。図15は、本発明の第2実施形態の検索手段1103による検索処理のデータの流れの説明図である。第2実施形態の検索処理のデータの流れのうち図5に示す第1実施形態の検索処理のデータ流れと同じものについては説明を省略する。CPU401は、504でBWTを補助記憶装置403又はネットワーク405を介して接続される記憶領域からメモリ402上にロードした後、補助記憶装置403又はネットワーク405を介して接続される記憶領域に記憶されたサンプル距離配列1101をメモリ402上にロードする1501。さらに、CPU401は、1501でメモリ402上にロードされたサンプル距離配列1101を参照しながら、文書内位置を特定する1502。次に、本発明の第2実施形態の文書内位置特定処理について説明する。第2実施形態の文書内位置特定処理は、図6に示す第1実施形態の文書内位置特定処理のS905の処理を次に述べるS905’に変更したものであり、その他の処理は同じである。S905’の処理では、CPU401は、サンプル距離配列1101を格納したウェーブレット木を参照し、S904の処理で処理対象集合Sから取り出された要素c1、c2、jの文書番号及び文書内位置がすでに取得されているか否かを判定する。CPU401は、当該要素に到達するまでに実行されたLF-mapping処理の回数jが、当該要素の範囲[c1、c2]のサンプル距離の最大値よりも小さければ、LF-mapping処理の実行が必要と判定する。具体的には、CPU401は、サンプル距離配列1101を格納したウェーブレット木において、長方形[j1,b]×[c1,c2]の内部にある点の数が0であるか否かを判定する。当該長方形内にある点の数が0でない場合、CPU401は、S904の処理で処理対象集合Sから取り出された要素c1、c2、jの文書番号及び文書内位置が未取得であり、LF-mapping処理によって文書番号及び文書内位置を取得する処理が必要であると判定し、S906の処理に移行する。一方、当該長方形内にある点の数が0である場合、CPU401は、S904の処理で処理対象集合Sから取り出された要素c1、c2、jの文書番号及び文書内位置が取得済であり、LF-mapping処理によって文書番号及び文書内位置を取得する処理が不要であると判定し、S903の処理に移行する。上記の処理が正しい理由を述べる。サンプル距離配列D1001のi番目の要素D[i]には、contextiに対応する接尾辞の位置から何文字右後の文字の文書番号及び文書内位置がサンプリングされているかが格納される。なお、文書番号及び文書内位置がサンプリングされた接尾辞のcontextiでは、D[i]=0となる。このため、S904の処理で取り出された処理対象集合Sの要素が、S901の処理で求められた検索キーワードで始まる接尾辞が出現するcontext範囲に対してj回LF-mapping処理が実行された範囲[c1、c2]である場合、c1≦i≦c2となるすべてのcontextiでD[i]≦jであれば、contextiに対応するすべての接尾辞の直近のサンプリングされた文書番号及び文書内位置をすでに特定していることになる。図16は、本発明の第2実施形態の文書内位置特定処理の説明図である。図14を参照しながら、図16について説明する。図16は、検索キーワードが特徴である場合の例となっている。特徴から始まる接尾辞の区間のうち、BWT107がをの区間にLF-mapping処理1001が実行されたを特徴から始まる区間では、BWT107がとの接尾辞の文書番号及び文書内位置は全て特定されている。このため、本来であれば、1701のLF-mapping処理の実行は不要である。しかし、CPU401が、を特徴から始まる区間に含まれる各接尾辞に対して文書番号及び文書内位置が特定済か否かを個別に判定すれば、CPU401の処理負荷が増大し、この判定処理がボトルネックとなってしまう。ここで、本実施形態では、を特徴から始まる区間にLF-mapping処理1701を実行する。そして、とを特徴から始まる接尾辞が存在する区間1702に対して、図14に示すサンプル距離配列1101を参照し、LF-mapping処理の実行の要否判定処理を実行する。具体的には、図16に示す区間1702は、図14に示す区間1702に対応している。CPU401は、図16において、当該区間1702に到達するまでに実行したLF-mapping処理の実行回数2回に1を加算した値3回からサンプリング間隔4回までの領域1703に点が存在するか否かを判定し、当該領域1703に点が存在しないので、LF-mapping処理を実行不要と判定する。これによって、CPU401は、ある区間において、一括してLF-mapping処理を実行できるので、CPU401の処理負荷を軽減しつつ、無駄なLF-mapping処理の実行しないようにすることができる。第3実施形態以下、本発明の第3実施形態を図17~図19を用いて説明する。第3実施形態では、第1、第2実施形態でサンプリングされなかったcontextであっても、当該contextを中心とする所定範囲にBWT107が一致する接尾辞がない場合、当該接尾辞の文書内位置をサンプリング追加サンプリングする。これによって、一括してLF-mappingを実行することによる高速化ができないcontextの文書番号および文書内位置がサンプリングされているので、当該contextに対して個別にLF-mapping処理を実行する必要がなくなり、高速に検索処理を実行できる。図17は、本発明の第3実施形態において追加サンプリングされたcontextの説明図である。図17のうち、第2実施形態の図16に示す構成と同じ構成は、同じ符号を付与し、説明を省略する。1801~1803の三つのcontextの接尾辞の文書番号及び文書内位置が追加サンプリングによって抽出される。例えば、1803では、当該contextのBWT107能が当該contextを中心とする所定範囲に存在しないので、当該contextの接尾辞の文書番号及び文書内位置が追加サンプリングされている。このため、図17では、第1実施形態及び第2実施形態では、1801~1803の接尾辞の文書番号及び文書内位置を特定するためにLF-mapping処理は実行されない。図18は、本発明の第3実施形態の追加サンプリング処理のフローチャートである。追加サンプリング処理は、第1実施形態のサンプリング手段409及び第2実施形態のサンプリング手段1102の機能の一部であり、CPU401によって実行される。当該追加サンプリング処理は、第1実施形態の図4に示すサンプリング処理のS705の処理、及び第2実施形態の図13に示すサンプリング処理のS705の処理を拡張して実現する。その処理の内容を、図18を用いて説明する。まず、CPU401は、文書内位置を示す変数pがサンプリング間隔を示す変数bで割り切れるか否かを判定するS1901。S1901の処理で、文書内位置を示す変数pがサンプリング間隔を示す変数bで割り切れると判定された場合S1901;YES、CPU401は、サンプリングが必要と判定し1903、追加サンプリング処理を終了する。一方、S1901の処理で、文書内位置を示す変数pがサンプリング間隔を示す変数bで割り切れないと判定された場合S1901;NO、CPU401は、変数pに対応する接尾辞のcontextを示す変数iの値を中心とした所定範囲[i-v,iv]のBWTの文字を検査する。そして、それらの文字の中に、BWT[i]と同じ文字がBWTに出現するcontextが存在するか否かを判定するS1902。換言すれば、CPU401は、i-v≦i’≦iv、i’≠i、かつBWT[i’]=BWT[i]が成立するcontexti’が存在するか否かを判定する。S1902の処理で、そのようなcontextiが存在しないと判定された場合、S1902;NO、CPU401は、S1902の処理に処理を移行し、サンプリングが必要と判定する。一方、S1902の処理で、所定範囲[i-v,iv]に、当該変数iが示すcontextのBWT107と同じ文字のcontextが存在すると判定された場合S1902;YES、CPU401は、サンプリングは不要と判定するS1904。ただし、vはBWT107に同じ文字があるかを調べる範囲を調整するためのパラメータで、ユーザが指定する。第3実施形態では、図6に示す文書内位置特定処理において、一つの接尾辞の出現位置に重複が出る場合がある。すなわち、追加サンプリングで抽出された文書番号及び文書内位置と、別の位置での追加サンプリングや第2実施形態と同様の等間隔サンプリング処理で抽出された文書番号及び文書内位置に基づいて算出される文書番号及び文書内位置とが、重複してHに格納される場合がある。この場合、図6に示す文書内位置特定処理で、文書内位置集合Hに格納された文書番号及び文書内位置が重複している場合、重複する一方の文書番号及び文書内位置を削除する。これによって、CPU401は、文書番号及び文書内位置が重複した場合であっても、重複する文書番号及び文書内位置を削除するため、一つの文書番号及び文書内位置としてユーザインタフェース部406に表示することができる。図19は、本発明の第3実施形態で2004年に出願公開された特許出願のうち2万件を検索対象文書集合101とするとき、追加サンプリングされる文字数を見積もったものである。2004年に出願公開された特許出願の2万件のデータの総文字数は2.9×108である。このデータに基づいてBWT107を構築した場合、構築したBWT107で同じ文字が続く長さの平均は2.7である。また、隣接するcontextのうち、BWT107の文字が前後のBWTの文字と異なるcontext数は6.9×107であり、総文字数のうち23を占める。このデータで、v=1として図18に示す追加サンプリング処理を実行すると、追加サンプリング処理で文書内位置がサンプリングされるcontextの数は、総文字数の23となり、約1/4の文字の文書内位置がサンプリングされ、データ量も増大する。このため、第3実施形態では、データ量を減少させるため、サンプリング間隔bを第1実施形態及び第2実施形態よりも大きくすることが望ましい。上述した実施形態では、サンプリング手段409及び1102は、文書番号及び文書内位置の両方を抽出したが、上述した図21を示す方法を用いれば文書内位置だけで文書番号及び文書内位置を特定できる。このため、サンプリング手段409及び1102は、文書番号及び文書内位置を抽出しなくても、仮想文書内における文書内位置だけ抽出すればよい。また、上述した実施形態では、横書きの文書を想定し、LF-mapping処理は、ある接尾辞の一文字左の接尾辞のcontextを特定する処理としたが、縦書きの文書の場合、LF-mapping処理は、ある接尾辞の一文字上の接尾辞のcontextを特定する処理となる。すなわち、LF-mapping処理は、ある接尾辞の一文字前の接尾辞のcontextを特定する処理である。また、BWTについても、横書きの文書を想定し、ある接尾辞の一文字左にある文字が格納されるとしたが、縦書きの文書の場合、ある接尾辞の一文字上にある文字が格納される。すなわち、BWTには、ある接尾辞の一文字上にある文字が格納される。以上、本発明の各実施形態について説明したが、上記実施形態は本発明の適用例を示したものであり、本発明の技術的範囲を上記各実施形態の具体的構成に限定する趣旨ではない。本発明の要旨を逸脱しない範囲において種々変更可能である。"