(57)【特許請求の範囲】
【請求項１】
検索文字列に含まれる（ｎ−１）（ｎ≧２）の文字数の第１の文字列について、先頭の文字に第１の記号を加え、最後尾の文字に第２の記号を加え、前記先頭の文字と前記第１の記号の組み合わせと前記最後尾の文字と前記第２の記号の組み合わせとのそれぞれに一致する圧縮符号を、予め用意された第２の文字列の先頭に前記第２の記号を付加し、後尾に前記第１の記号を付加した第３の文字列を用いて作成されたｎグラムのインデックスに前記インデックスそれぞれに対応する圧縮符号が関連づけられたインデックスファイルから検索する検索部と、
前記先頭の文字と前記第１の記号の組み合わせの検索結果と、前記最後尾の文字と前記第２の記号の組み合わせの検索結果それぞれの組み合わせを、前記第１の文字列の順番に並べた検索用情報を作成する作成部と、
を有することを特徴とする文字列検索装置。
【請求項２】
前記作成部により作成された前記検索用情報に示される圧縮符号の組み合わせを備える圧縮文書の該圧縮符号の組み合わせに対応する部位を特定し、特定した部位を他の部位と区別し得る態様で出力する出力部をさらに有することを特徴とする請求項１記載の文字列検索装置。
【請求項３】
前記インデックスには、さらに、圧縮符号における前記第３の文字列の含まれる位置を示す文字位置情報が関連づけられており、
前記検索部は、前記先頭の文字と前記第１の記号の組み合わせと前記最後尾の文字と前記第２の記号の組み合わせとのそれぞれに一致する圧縮符号と該圧縮符号における前記第３の文字列の含まれる位置を示す文字位置情報を、前記インデックスファイルから検索し、
前記作成部は、前記検索結果それぞれの圧縮符号と前記文字位置情報の組み合わせを作成することを特徴とする請求項１記載の文字列検索装置。
【請求項４】
前記作成部により作成された前記検索用情報に示される圧縮符号と前記文字位置情報の組み合わせを用いて、該圧縮符号を備える圧縮文書の該圧縮符号に対応する部位を特定し、特定した部位を他の部位と区別し得る態様で出力する出力部をさらに有することを特徴とする請求項３記載の文字列検索装置。
【請求項５】
前記第２の文字列と前記第２の文字列に対応する圧縮符号とが関連づけられた圧縮辞書の該各文字列の先頭および後尾に前記第１の記号および前記第２の記号を付加して前記インデックスファイルの前記インデックスを作成するインデックスファイル作成部をさらに有することを特徴とする請求項１記載の文字列検索装置。
【請求項６】
コンピュータが、
検索文字列に含まれる（ｎ−１）（ｎ≧２）の文字数の第１の文字列について、先頭の文字に第１の記号を加え、最後尾の文字に第２の記号を加え、前記先頭の文字と前記第１の記号の組み合わせと前記最後尾の文字と前記第２の記号の組み合わせとのそれぞれに一致する圧縮符号を、予め用意された第２の文字列の先頭に前記第２の記号を付加し、後尾に前記第１の記号を付加した第３の文字列を用いて作成されたｎグラムのインデックスに前記インデックスそれぞれに対応する圧縮符号が関連づけられたインデックスファイルから検索し、
前記先頭の文字と前記第１の記号の組み合わせの検索結果と、前記最後尾の文字と前記第２の記号の組み合わせの検索結果それぞれの組み合わせを、前記第１の文字列の順番に並べた検索用情報を作成する、
ことを特徴とする文字列検索方法。
【請求項７】
コンピュータに、
検索文字列に含まれる（ｎ−１）（ｎ≧２）の文字数の第１の文字列について、先頭の文字に第１の記号を加え、最後尾の文字に第２の記号を加え、前記先頭の文字と前記第１の記号の組み合わせと前記最後尾の文字と前記第２の記号の組み合わせとのそれぞれに一致する圧縮符号を、予め用意された第２の文字列の先頭に前記第２の記号を付加し、後尾に前記第１の記号を付加した第３の文字列を用いて作成されたｎグラムのインデックスに前記インデックスそれぞれに対応する圧縮符号が関連づけられたインデックスファイルから検索する検索手順、
前記先頭の文字と前記第１の記号の組み合わせの検索結果と、前記最後尾の文字と前記第２の記号の組み合わせの検索結果それぞれの組み合わせを、前記第１の文字列の順番に並べた検索用情報を作成する作成手順、
を実行させることを特徴とする文字列検索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は文字列検索装置、文字列検索方法および文字列検索プログラムに関する。
【背景技術】
【０００２】
コンピュータシステムにおいて、テキストデータを処理対象とした情報処理を行う場合がある。例えば、テキストデータを対象とした情報検索が行われる。
近年、情報通信技術の用途の拡大に伴い、処理されるテキストデータの量が増加傾向にある。そこで、テキストデータを処理対象とした情報処理を効率化するためのさまざまな技術が考えられている。例えば、小容量のメモリを用いて、高速にデータソート処理を行うデータソート処理方法が考えられている。また、指定された項目に沿ったデータ集合の分割を効率よく行うことができるデータ集合分割方法も考えられている。
【０００３】
ところで、テキストデータを検索する場合、蓄積されたテキストデータの中から、検索文字列（検索キーワード）に合致する文字列を効率よく検出することで、処理の高速化が図れる。例えば、圧縮パターン照合技術が知られている。
【０００４】
圧縮パターン照合では、テキストデータを圧縮したまま検索できるように、入力されたテキストの中に含まれる部分文字列を、その部分文字列を一意に特定可能な符号に符号化する。テキストデータに含まれる部分文字列を符号化することで、元のテキストデータよりもデータ量を減少させることができる。
【０００５】
圧縮パターン照合技術の１つに、固定された圧縮辞書（静的辞書）を使用して、テキストの可変長な部分文字列に対して固定長の符号（ＶＦ：Variable-to-Fixed-length）を割り当てることで圧縮を行う静的辞書式ＶＦ符号化技術が知られている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２０００−２３１５６３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
圧縮されたテキストを解凍せずに検索するためには、検索文字列が圧縮テキスト上でどのような符号列で存在するかを知る必要がある。
しかしながら、単純にｎ（ｎ≧２）文字単位で文字列を切り出した（ｎ−ｇｒａｍの）インデックスを用いて、検索文字列に対応する符号列を調べようとすると、対応する符号列の検出漏れや、処理時間がかかるという問題があった。
【０００８】
本発明はこのような点に鑑みてなされたものであり、文字列の検索を高速に行う文字列検索装置、文字列検索方法および文字列検索プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記目的を達成するために、開示の文字列検索装置が提供される。この文字列検索装置は、検索部と作成部とを有している。
検索部は、検索文字列に含まれる（ｎ−１）（ｎ≧２）の文字数の文字列について、先頭の文字に文字列の先頭であることを示す先頭記号を加え、最後尾の文字に文字列の最後尾であることを示す後尾記号を加え、文字列と先頭記号の組み合わせと文字列と後尾記号の組み合わせとのそれぞれに一致する圧縮符号を、予め用意された任意の文字列の先頭に先頭記号を付加し、後尾に後尾記号を付加した文字列を用いて作成されたｎグラムのインデックスにインデックスそれぞれに対応する圧縮符号が関連づけられたインデックスファイルから検索する。
【００１０】
作成部は、検索部の検索により得られた先頭の文字と先頭記号の組み合わせの検索結果と最後尾の文字と後尾記号の組み合わせの検索結果それぞれの組み合わせを、文字列の順番に並べた検索用情報を作成する。
【発明の効果】
【００１１】
文字列の検索を高速に行うことができる。
【図面の簡単な説明】
【００１２】
【図１】第１の実施の形態の文字列検索装置の概要を示す図である。
【図２】第２の実施の形態の文字列検索装置のハードウェアの一構成例を示す図である。
【図３】文字列検索装置の機能を示すブロック図である。
【図４】インデックスファイル作成部の動作を示す図である。
【図５】文字列検索装置の処理の概要を示すフローチャートである。
【図６】検索処理を説明するフローチャートである。
【図７】検索処理の具体例を説明する図である。
【図８】検索処理の具体例を説明する図である。
【図９】検索処理の具体例を説明する図である。
【図１０】検索処理の具体例を説明する図である。
【図１１】検索処理の具体例を説明する図である。
【図１２】検索結果出力部の処理の具体例を説明する図である。
【図１３】比較例を説明する図である。
【図１４】他の比較例を説明する図である。
【発明を実施するための形態】
【００１３】
以下、実施の形態を、図面を参照して詳細に説明する。
まず、実施の形態の文字列検索装置について説明し、その後、実施の形態をより具体的に説明する。
【００１４】
＜第１の実施の形態＞
図１は、第１の実施の形態の文字列検索装置の概要を示す図である。
実施の形態の文字列検索装置（コンピュータ）１は、圧縮符号（ＡＤＢ・・・）を有する圧縮文書２に対し、検索文字列（本実施の形態では「ｔｈ」）が含まれているか否か、いくつ含まれているか、どこに含まれているか等を検索するときに用いる検索用情報を作成する装置である。
【００１５】
ここで、圧縮符号は、ある文字列が圧縮符号化されたことを識別する符号である。例えば、圧縮符号「Ａ」は、文字列「ｔｈｅ」を圧縮したことを識別する符号である。圧縮符号「Ａ」を解凍すると、文字列「ｔｈｅ」を取り出すことができる。
【００１６】
文字列検索装置１は、検索部１ａと、作成部１ｂとを有している。
検索部１ａは、インデックスファイル３を用いて、入力された検索文字列に含まれる任意の文字列について、対応する圧縮符号と文字位置情報の組み合わせを検索する。
【００１７】
インデックスファイル３には、バイグラム（bi-Gram）のインデックスに、インデックスそれぞれに対応する圧縮符号と文字位置情報の組み合わせ（以下、「文字位置情報付き圧縮符号」と言う）が関連づけられている。
【００１８】
なお、本実施の形態では、バイグラム（ｎ＝２）のインデックスを作成したが、これに限らずｎ＝３以上のｎグラムのインデックスを作成してもよい。
ここで、文字位置情報は、圧縮符号における文字列の含まれる位置を示す情報である。例えば、インデックスファイル３の１行目の文字位置情報付き圧縮符号Ａ［１：２］は、圧縮符号「Ａ」の「１バイト目と２バイト目」にインデックスの欄に記載された文字列「ｔｈ」が含まれていることを示している。
【００１９】
本実施の形態では、検索部１ａは、検索文字列の任意の文字列「ｔｈ」について、先頭の文字「ｔ」の語尾に文字の先頭であることを示す先頭記号「＄」を加え、後尾の文字「ｈ」の語頭に文字の最後尾であることを示す後尾記号「＾」を加える。なお、先頭記号および後尾記号は、識別情報としての役割を果たすものであり、加える記号の種別や、記号の位置は、図示のものに限定されない。また、先頭記号および後尾記号は、それぞれ後述する圧縮辞書４ａに加えた記号と同じ記号である。
【００２０】
そして、検索部１ａは、先頭の文字と先頭記号の組み合わせ（以下、「文字記号」と言う）「ｔ＄」と文字記号「＾ｈ」のそれぞれに一致する文字位置情報付き圧縮符号を、インデックスファイル３から検索する。
【００２１】
検索の結果、検索部１ａは、文字列「ｔｈ」に関連づけられた文字位置情報付き圧縮符号Ａ［１：２］、文字記号「ｔ＄」に関連づけられた文字位置情報付き圧縮符号Ｂ［２：３］，Ｇ［３：４］、および文字記号「＾ｈ」に関連づけられた文字位置情報付き圧縮符号Ｅ［０：１］，Ｆ［０：１］，Ｇ［０：１］を見つける。
【００２２】
ところで、インデックスファイル３は、任意のテキスト（文字または文字列）と、テキストに対応する圧縮符号とが関連づけられた圧縮辞書４から作成することができる。
本実施の形態の文字列検索装置１は、圧縮辞書４からインデックスファイル３を作成するインデックスファイル作成部１ｃを、さらに有している。
【００２３】
インデックスファイル作成部１ｃは、圧縮辞書４を加工して圧縮辞書４ａを作成する。具体的には、インデックスファイル作成部１ｃは、圧縮辞書４の各テキストに、検索部１ａが加えた先頭記号と同じ先頭記号「＄」を加える。また、インデックスファイル作成部１ｃは、圧縮辞書４の各テキストに、検索部１ａが加えた後尾記号と同じ後尾記号「＾」を加える。
【００２４】
そして、インデックスファイル作成部１ｃは、圧縮辞書４ａからバイグラムのインデックスを作成する。そして、インデックスファイル作成部１ｃは、作成したインデックスに圧縮符号の文字位置情報を関連づける。これにより、インデックスファイル３を作成することができる。
【００２５】
作成部１ｂは、検索部１ａの検索により得られた文字記号「ｔ＄」に関連づけられた文字位置情報付き圧縮符号Ｂ［２：３］，Ｇ［３：４］と文字記号「＾ｈ」に関連づけられた文字位置情報付き圧縮符号Ｅ［０：１］，Ｆ［０：１］，Ｇ［０：１］それぞれの文字位置情報付き圧縮符号を文字列「ｔｈ」の順番に並列に並べた組み合わせを作成する。ここで、文字列「ｔｈ」の順番に並べるとは、文字記号「ｔ＄」に関連づけられた文字位置情報付き圧縮符号の後に、文字記号「＾ｈ」に関連づけられた文字位置情報付き圧縮符号を並べることを意味する。図１では、並べ方に２×３＝６通りの組み合わせが存在する。従って、文字列「ｔｈ」の検索により得られた検索結果Ａ［１：２］と合わせると、合計７通りの文字位置情報付き圧縮符号の組み合わせが作成される。以下、この組み合わせを「検索用情報」と言う。この検索用情報における圧縮符号の列（圧縮符号列）は、検索文字列「ｔｈ」の圧縮パターン照合時に用いる符号列となる。例えば、検索用情報Ｂ［２：３］Ｅ［０：１］の圧縮符号列「ＢＥ」が、検索対象の圧縮文書２に含まれていれば、検索文字列「ｔｈ」を見つけたことになる。また、検索用情報における文字位置情報は、圧縮文書を解凍したときに、検索文字列「ｔｈ」が含まれている箇所を特定する情報となる。
【００２６】
また、本実施の形態の文字列検索装置１は、結果作成部１ｄをさらに有している。結果作成部１ｄは、検索用情報から文字位置情報を削除することにより、複数の圧縮符号列５を作成する。そして、結果作成部１ｄは、各圧縮符号列５に一致するテキストを圧縮文書２から検索する。図１では、検索により、圧縮符号列「ＢＥ」と圧縮符号列「ＧＥ」が見つかる。
【００２７】
結果作成部１ｄは、圧縮文書２を解凍する。そして、検索用情報が有する文字位置情報を参照し、見つかった圧縮符号列「ＢＥ」と圧縮符号列「ＧＥ」の、文字位置情報によって特定される検索文字列を他の文字と区別し得る態様（図１では、太字と下線）で、明記して出力する。なお、図１では、圧縮符号列が見つからなかった行についても解凍し、出力しているが、圧縮符号列が見つからなかった行については、出力対象から除外するようにしてもよい。
【００２８】
次に、文字列検索装置１の処理の流れを簡単に説明する。
まず、インデックスファイル作成部１ｃが、圧縮辞書４から圧縮辞書４ａを作成する。そして、インデックスファイル作成部１ｃが、圧縮辞書４ａに基づいて、インデックスファイル３を作成する。
【００２９】
検索部１ａは、検索文字列を読み込むと、インデックスファイル３を参照し、検索文字列の任意の文字列に一致するインデックスと文字位置情報の組み合わせを検索する。
作成部１ｂは、検索部１ａの検索結果に基づいて、検索用情報を作成する。
【００３０】
結果作成部１ｄは、作成部１ｂが作成した検索用情報から圧縮符号列５を生成する。そして、結果作成部１ｄは、圧縮符号列５に一致する圧縮文書２の箇所を検索する。そして、結果作成部１ｄは、圧縮文書を解凍し、一致した圧縮文書２の箇所を明示して出力する。
【００３１】
実施の形態の文字列検索装置１によれば、作成部１ｂが、検索用情報を作成することにより、符号のつなぎ部分（図１では、符号Ｂに関連づけられたテキスト「ｉｔ」の「ｔ」と、符号Ｅに関連づけられたテキスト「ｈｅ」の「ｈ」、符号Ｆに関連づけられたテキスト「ｈｅｒ」の「ｈ」および符号Ｇに関連づけられたテキスト「ｈｉｔ」の「ｈ」）を確実に検出することができる。従って、予め符号のつなぎ部分を含めたインデックスファイルに比べ、サイズ（容量）が小さいインデックスファイル３を用いて検索部１ａが検索を行うことにより、処理の高速化を図ることができる。
【００３２】
なお、本実施の形態では、文字列検索装置１がインデックスファイル作成部１ｃを有し、インデックスファイル３を作成する構成とした。しかし、この構成に限らず、文字列検索装置１からインデックスファイル作成部１ｃを省略した構成とし、検索部１ａは、文字列検索装置１以外の装置によって作成されたインデックスファイルを検索する構成にしてもよい。また、本実施の形態では、文字列検索装置１が結果作成部１ｄを有し、解凍した圧縮文書を出力する構成とした。しかし、この構成に限らず、文字列検索装置１から結果作成部１ｄを省略した構成とし、他の装置が、作成部１ｂが作成した圧縮符号列を用いて解凍した圧縮文書を出力する構成にしてもよい。
【００３３】
なお、圧縮辞書４ａやインデックスファイル３は、文字列検索装置１が有するデータ記憶領域に記憶しておくことができる。このデータ記憶領域は、例えば、文字列検索装置１が有するＲＡＭ（Random Access Memory）やハードディスクドライブ（ＨＤＤ:Hard Disk Drive）等により実現することができる。また、検索部１ａ、作成部１ｂ、インデックスファイル作成部１ｃおよび結果作成部１ｄは、文字列検索装置１が有するＣＰＵ（Central Processing Unit）が備える機能により実現することができる。
【００３４】
なお、本実施の形態では、検索文字列としてアルファベットを使用しているが、文字列の種類は、アルファベットに限らず、ひらがな、カタカナ、漢字等を用いることもできる。例えばひらがなの文字列を検索する場合は、ひらがなの圧縮辞書からひらがなのインデックスと文字位置情報付き圧縮符号とが関連づけられたインデックスファイルを作成しておき、作成されたインデックスファイルに基づいて、文字列検索装置１が前述した処理を行うことで、ひらがなの文字列を検索することができる。
【００３５】
以下、実施の形態をより具体的に説明する。
＜第２の実施の形態＞
図２は、第２の実施の形態の文字列検索装置のハードウェアの一構成例を示す図である。
【００３６】
文字列検索装置１０は、ＣＰＵ１０１によって装置全体が制御されている。ＣＰＵ１０１には、バス１０８を介してＲＡＭ１０２と複数の周辺機器が接続されている。
ＲＡＭ１０２は、文字列検索装置１０の主記憶装置として使用される。ＲＡＭ１０２には、ＣＰＵ１０１に実行させるＯＳ（Operating System）のプログラムやアプリケーションプログラムの少なくとも一部が一時的に格納される。また、ＲＡＭ１０２には、ＣＰＵ１０１による処理に必要な各種データが格納される。
【００３７】
バス１０８に接続されている周辺機器としては、ハードディスクドライブ１０３、グラフィック処理装置１０４、入力インタフェース１０５、光学ドライブ装置１０６、および通信インタフェース１０７がある。
【００３８】
ＨＤＤ１０３は、内蔵したディスクに対して、磁気的にデータの書き込みおよび読み出しを行う。ＨＤＤ１０３は、文字列検索装置１０の二次記憶装置として使用される。ＨＤＤ１０３には、ＯＳのプログラム、アプリケーションプログラム、および各種データが格納される。なお、二次記憶装置としては、フラッシュメモリなどの半導体記憶装置を使用することもできる。
【００３９】
グラフィック処理装置１０４には、モニタ１０４ａが接続されている。グラフィック処理装置１０４は、ＣＰＵ１０１からの命令に従って、画像をモニタ１０４ａの画面に表示させる。モニタ１０４ａとしては、ＣＲＴ（Cathode Ray Tube）を用いた表示装置や液晶表示装置等が挙げられる。
【００４０】
入力インタフェース１０５には、キーボード１０５ａとマウス１０５ｂとが接続されている。入力インタフェース１０５は、キーボード１０５ａやマウス１０５ｂから送られてくる信号をＣＰＵ１０１に送信する。なお、マウス１０５ｂは、ポインティングデバイスの一例であり、他のポインティングデバイスを使用することもできる。他のポインティングデバイスとしては、タッチパネル、タブレット、タッチパッド、トラックボール等が挙げられる。
【００４１】
光学ドライブ装置１０６は、レーザ光などを利用して、光ディスク２００に記録されたデータの読み取りを行う。光ディスク２００は、光の反射によって読み取り可能なようにデータが記録された可搬型の記録媒体である。光ディスク２００には、Ｂｌｕ−Ｒａｙ（登録商標）、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等が挙げられる。
【００４２】
通信インタフェース１０７は、ネットワーク５０に接続されている。通信インタフェース１０７は、ネットワーク５０を介して、他のコンピュータまたは通信機器との間でデータの送受信を行う。
【００４３】
以上のようなハードウェア構成によって、本実施の形態の処理機能を実現することができる。
このようなハードウェア構成の文字列検索装置１０内には、以下のような機能が設けられる。
【００４４】
図３は、文字列検索装置の機能を示すブロック図である。
文字列検索装置１０は、入力される検索文字列に基づいて、この検索文字列を検索する検索用情報を作成する。そして、文字列検索装置１０は、作成した検索用情報を用いて、圧縮文書格納部２２に格納されている圧縮文書に、検索文字列が含まれているか否かを検索する。検索文字列が含まれている場合、文字列検索装置１０は、圧縮文書の検索文字列が含まれている部分を解凍した解凍文書を出力する。
【００４５】
この文字列検索装置１０は、インデックスファイル作成部１１と、インデックスファイル格納部１２と、検索用情報作成部１３と、検索結果出力部１４とを有している。
インデックスファイル作成部１１は、圧縮辞書格納部２１に格納されている固定された圧縮辞書（静的辞書）に基づいて、インデックスファイルを作成する。具体的には、インデックスファイル作成部１１は、圧縮辞書格納部２１に格納された圧縮辞書の各エントリのテキスト（文字または文字列）の先頭に、テキストの先頭であることを示す先頭記号を付加し、後尾にテキストの最後尾であることを示す後尾記号を付加する。
【００４６】
そして、インデックスファイル作成部１１は、ある文字列の中で、Ｎ個の文字列または単語の組み合わせが、どの程度出現するかを示すＮ−Ｇｒａｍのインデックスファイルを作成する。そして、インデックスファイル作成部１１は、作成したインデックスファイルをインデックスファイル格納部１２に格納する。
【００４７】
図４は、インデックスファイル作成部の動作を示す図である。
圧縮辞書２１ａの各エントリには、圧縮対象のテキストに、圧縮符号が関連づけられている。
【００４８】
インデックスファイル作成部１１は、圧縮辞書２１ａの各エントリのテキストの先頭に記号「＾」を付加し、テキストの後尾に記号「＄」を付加した圧縮辞書２１ｂを作成する。例えば、テキストが「ｔｈｅ」である場合、テキスト「ｔｈｅ」の先頭に、先頭記号「＾」を付加し、最後尾に、後尾記号「＄」を付加する。この結果、テキストは「＾ｔｈｅ＄」となる。なお、記号の種別は任意であり、実施の形態のものには限定されない。
【００４９】
そして、インデックスファイル作成部１１は、作成した圧縮辞書２１ｂに基づいて、先頭記号および後尾記号を文字に含め、２文字単位でテキストを切り出したバイグラムのインデックスを作成する。
【００５０】
そして、作成したインデックスに、文字位置情報付き圧縮符号を関連づけて、インデックスファイル１２ａを作成する。
例えば、インデックスファイル１２ａの１行目のレコード「＾ａ：Ｆ［０：１］」は、インデックス「＾ａ」に文字位置情報付き圧縮符号「Ｆ［０：１］」が関連づけられていることを示している。そして、圧縮符号Ｆの０バイト目と１バイト目に文字列「＾ａ」が含まれていることを示している。
【００５１】
再び図３に戻って説明する。
検索用情報作成部１３は、入力される検索文字列と、インデックスファイル格納部１２に格納されているインデックスファイル１２ａとに基づいて、検索文字列を検索可能な検索用情報を作成する。
【００５２】
具体的には、検索用情報作成部１３は、検索部１３１と作成部１３２とを有している。
検索部１３１は、検索文字列を、次の３種類のパターンに分けてインデックスファイル１２ａを検索する。（１）検索文字列を２文字ずつ分割したもの。（２）検索文字列を１文字ずつ分割し、各文字の前に、先頭記号を加えたもの。（３）検索文字列を１文字ずつ分割し、各文字の後ろに後尾記号を加えたもの。
【００５３】
上記（１）〜（３）のうち、（１）を用いて検索することにより、１つのテキストに含まれる検索文字列を検索することができる。また、（２）、（３）を用いて検索することにより、２つのテキストに跨った（符号のつなぎ部分）に含まれる検索文字列を検索することができる。
【００５４】
作成部１３２は、検索部１３１の検索の結果見つかった文字位置情報付き圧縮符号のうち、後尾記号と先頭記号を結合することにより、２つのテキストに跨った検索文字列を検索可能な検索用情報を作成することができる。
【００５５】
検索用情報作成部１３は、作成した検索用情報や、検索用情報を作成する課程で一時的に作成される情報を記憶するメモリ（以下、「内部メモリ」と言う）を有している。
作成部１３２は、作成した検索用情報を内部メモリに記憶する。
【００５６】
検索用情報作成部１３は、検索文字列が２文字を超える場合は、前述した処理を隣接する２文字について繰り返し行って検索用情報を作成する。なお、検索用情報の作成方法については、後に詳述する。
【００５７】
検索結果出力部１４は、検索用情報作成部１３が作成した検索用情報に基づいて、圧縮文書格納部２２に格納されている圧縮文書を検索する。そして、検索結果出力部１４は、圧縮文書の検索文字列が含まれている部分（例えば、検索文字列が含まれている行等）を解凍した解凍文書を出力する。このとき、検索結果出力部１４は、解凍文書に含まれる検索文字列を明示して出力することができる。
【００５８】
なお、圧縮文書は、予め用意されたものを読み込んでもよいし、ユーザが作成した文書でもよい。
次に、文字列検索装置１０の処理を、フローチャートを用いて説明する。
【００５９】
図５は、文字列検索装置の処理の概要を示すフローチャートである。
［ステップＳ１］  インデックスファイル作成部１１が、圧縮辞書２１ａの各エントリ文字列を細工し、圧縮辞書２１ｂを作成する。具体的には、インデックスファイル作成部１１は、圧縮辞書内の各エントリ文字列に先頭記号および後尾記号を入れる。その後、ステップＳ２に遷移する。
【００６０】
［ステップＳ２］  インデックスファイル作成部１１が、圧縮辞書２１ｂに基づいて、バイグラムのインデックスファイル１２ａを作成する。そして、インデックスファイル作成部１１は、作成したインデックスファイル１２ａをインデックスファイル格納部１２に格納する。その後、ステップＳ３に遷移する。
【００６１】
［ステップＳ３］  検索用情報作成部１３が、検索処理を行って、検索文字列に対応する検索用情報を出力する。その後、ステップＳ４に遷移する。なお、検索処理については後述する。
【００６２】
［ステップＳ４］  検索結果出力部１４が、ステップＳ３で出力された検索用情報を用いて圧縮文書に記載されている圧縮文書を検索する。その後、ステップＳ５に遷移する。
［ステップＳ５］  検索結果出力部１４が、圧縮文書の検索文字列が含まれている部分を解凍した解凍文書を出力する。その後、処理を終了する。
【００６３】
以上で、図５の処理の説明を終了する。
次に、ステップＳ３の検索処理を説明する。
図６は、検索処理を説明するフローチャートである。
【００６４】
［ステップＳ３ａ］  検索部１３１は、検索文字列の先頭の文字を処理対象の文字に設定する。その後、ステップＳ３ｂに遷移する。
［ステップＳ３ｂ］  検索部１３１は、処理対象の文字に、処理対象の文字の次の文字を加えた文字列（第１の文字列）で、ステップＳ２にて作成されたインデックスファイル１２ａを検索する。そして、作成部１３２は、検索した結果見つかった文字位置情報付き圧縮符号を検索用情報の現候補（以下、単に「現候補」と言う）とする。作成部１３２は、現候補を内部メモリに一時的に記憶する。その後、ステップＳ３ｃに遷移する。
【００６５】
［ステップＳ３ｃ］  検索部１３１は、第１の文字列および、先頭記号に先頭記号の次の文字を加えた文字列（第２の文字列）で、ステップＳ２にて作成されたインデックスファイル１２ａを検索する。その後、ステップＳ３ｄに遷移する。
【００６６】
［ステップＳ３ｄ］  作成部１３２は、第１の文字列の検索の結果および第２の文字列の検索の結果得られた文字位置情報付き圧縮符号を、ステップＳ３ｂにて得られた現候補に追加する。その後、ステップＳ３ｅに遷移する。
【００６７】
［ステップＳ３ｅ］  検索部１３１は、処理対象の文字以降の検索文字列の文字数（残りの文字数）が２文字以上か否かを判断する。残りの文字数が２文字以上であると判断した場合（ステップＳ３ｅのＹｅｓ）、ステップＳ３ｆに遷移する。残りの文字数が２文字未満であると判断した場合（ステップＳ３ｅのＮｏ）、ステップＳ３ｐに遷移する。
【００６８】
［ステップＳ３ｆ］  検索部１３１は、現在の処理対象の文字の次の文字を処理対象の文字に設定する。その後、ステップＳ３ｇに遷移する。
［ステップＳ３ｇ］  検索部１３１は、処理対象の文字に、処理対象の文字の次の文字を加えた文字列で、ステップＳ２にて作成されたインデックスファイル１２ａを検索する。その後、ステップＳ３ｈに遷移する。
【００６９】
［ステップＳ３ｈ］  作成部１３２は、ステップＳ３ｄの現候補に含まれる文字位置情報付き圧縮符号の最後尾の符号と、ステップＳ３ｇの検索の結果得られた文字位置情報付き圧縮符号の符号とが同一、かつ、文字位置情報が隣同士となる組み合わせを検索用情報の次候補とし、内部メモリに記憶する。その後、ステップＳ３ｉに遷移する。
【００７０】
［ステップＳ３ｉ］  検索部１３１は、処理対象の文字に後尾記号を加えた文字列で、ステップＳ２にて作成されたインデックスファイル１２ａを検索する。その後、ステップＳ３ｊに遷移する。
【００７１】
［ステップＳ３ｊ］  作成部１３２は、ステップＳ３ｄの現候補に含まれる文字位置情報付き圧縮符号の最後尾の符号と、ステップＳ３ｉの検索の結果得られた文字位置情報付き圧縮符号の符号とが同一、かつ、文字位置情報が隣同士となる組み合わせを検索用情報の仮候補とする。その後、ステップＳ３ｋに遷移する。
【００７２】
［ステップＳ３ｋ］  検索部１３１は、先頭記号に次の文字を加えた文字列で、ステップＳ２にて作成されたインデックスファイル１２ａを検索する。その後、ステップＳ３ｍに遷移する。
【００７３】
［ステップＳ３ｍ］  作成部１３２は、ステップＳ３ｊの検索用情報の仮候補に含まれる文字位置情報付き圧縮符号の最後尾の符号と、ステップＳ３ｍの検索の結果得られた文字位置情報付き圧縮符号の符号とが同一、かつ、文字位置情報が隣同士となる組み合わせをステップＳ３ｈの検索用情報の次候補に追加する。その後、ステップＳ３ｎに遷移する。
【００７４】
［ステップＳ３ｎ］  作成部１３２は、ステップＳ３ｍの次候補を現候補に上書きする。また、作成部１３２は、仮候補を消去（クリア）する。その後、ステップＳ３ｅに遷移する。
【００７５】
［ステップＳ３ｐ］  作成部１３２は、検索用情報の現候補を出力する。その後、検索処理を終了する。
以上で検索処理の説明を終了する。
【００７６】
次に、検索処理の具体例を説明する。
図７〜図１１は、検索処理の具体例を説明する図である。
なお、図７〜図１１中、右側から左側に向かう矢印は、矢印の基端側の文字列を検索文字としてインデックスファイル１２ａを検索することを示している。また、左側から右側に向かう矢印は、検索の結果、矢印の先端側のインデックスと文字位置情報付き圧縮符号の組み合わせが得られたことを示している。
【００７７】
また、図７〜図１１では、検索用情報作成部１３が有する内部メモリ１０２ａへの情報の出し入れの様子も併せて表記し、明細書中では、その説明を省略している。
また、具体例のインデックスファイル１２ａには説明の便宜上、行番号を表記している。
【００７８】
本具体例の検索文字列は「ｔｈｅｍ」とする。まず、検索部１３１は、文字列「ｔｈｅｍ」の先頭の文字「ｔ」を処理対象の文字に設定する。
そして、検索部１３１は、設定した処理対象の文字「ｔ」に次の文字「ｈ」を加えた文字列「ｔｈ」を検索文字としてインデックスファイル１２ａを検索する。検索の結果、検索部１３１は、１５行目のレコード「ｔｈ：Ａ［１：２］，Ｆ［２：３］」を見つける。
【００７９】
作成部１３２は、見つけたレコードに含まれる文字位置情報付き圧縮符号Ａ：［１：２］と、文字位置情報付き圧縮符号Ｆ［２：３］とを検索用情報の現候補とする。
なお、以下の説明では、説明の便宜上、文字位置情報付き圧縮符号の列（以下、文字位置情報付き圧縮符号列と言う）を句読点で結び、括弧（「」）で囲んで表記する。
【００８０】
例えば、検索用情報が、文字位置情報付き圧縮符号Ａ：［１：２］と、文字位置情報付き圧縮符号Ｆ［２：３］を有していれば、文字位置情報付き圧縮符号列「Ａ：［１：２］、Ｆ［２：３］」と表記する。
【００８１】
次に、検索部１３１は、「ｔ＄」および「＾ｈ」を検索文字としてインデックスファイル１２ａを検索する。
検索の結果、検索部１３１は、１８行目のレコード「ｔ＄：Ｂ［２：３］」、および３行目のレコード「＾ｈ：Ｅ［０：１］，Ｇ［０：１］」を見つける。作成部１３２は、見つかったレコードに含まれる文字位置情報付き圧縮符号を組み合わせることにより得られる文字位置情報付き圧縮符号Ｂ［２：３］Ｅ［０：１］と、文字位置情報付き圧縮符号Ｂ［２：３］Ｇ［０：１］を、検索用情報の現候補に追加する。この結果、現候補は、文字位置情報付き圧縮符号列「Ａ［１：２］、Ｆ［２：３］、Ｂ［２：３］Ｅ［０：１］、Ｂ［２：３］Ｇ［０：１］」を有する。
【００８２】
検索部１３１は、文字列「ｔｈｅｍ」の文字「ｔ」を除いた残り文字数が２文字以上か否かを判断すると、「ｈｅｍ」の３文字であるため、２文字以上であると判断する。
次に、検索部１３１は、文字列「ｔｈｅｍ」の「ｔ」の次の文字を検索すると、次の文字「ｈ」を見つけるので、見つかった文字「ｈ」を処理対象の文字に設定する（図８参照）。
【００８３】
そして、検索部１３１は、設定した処理対象の文字「ｈ」に次の文字「ｅ」を加えた文字列「ｈｅ」を検索文字としてインデックスファイル１２ａを検索する。検索の結果、検索部１３１は、９行目のレコード「ｈｅ：Ａ［２：３］，Ｅ［１：２］」を見つける。
【００８４】
作成部１３２は、現候補に含まれる文字位置情報付き圧縮符号列「Ａ［１：２］、Ｆ［２：３］、Ｂ［２：３］Ｅ［０：１］、Ｂ［２：３］Ｇ［０：１］」の各文字位置情報付き圧縮符号の最後尾の符号と、見つかったレコードに含まれる文字位置情報付き圧縮符号「Ａ［２：３］、Ｅ［１：２］」の各符号が同一、かつ、文字位置情報が隣同士となる組み合わせを列挙する。
【００８５】
見つかったレコードに含まれる文字位置情報付き圧縮符号Ａ［２：３］については、符号が同じで文字位置情報が隣同士となる文字位置情報付き圧縮符号は、Ａ［１：２］である。作成部１３２は、文字位置情報付き圧縮符号Ａ［１：２］を最後尾に含む文字位置情報付き圧縮符号を現候補の文字位置情報付き圧縮符号列から探すと、文字位置情報付き圧縮符号Ａ［１：２］を見つける。従って、作成部１３２は、文字位置情報付き圧縮符号Ａ［１：２］と文字位置情報付き圧縮符号Ａ［２：３］を組み合わせる。
【００８６】
見つかったレコードに含まれる文字位置情報付き圧縮符号Ｅ［１：２］については、符号が同じで隣同士となる文字位置情報付き圧縮符号は、Ｅ［０：１］である。作成部１３２は、Ｅ［０：１］を最後尾に含む文字位置情報付き圧縮符号を現候補の文文字位置情報付き圧縮符号列から探すと、文字位置情報付き圧縮符号Ｂ［２：３］Ｅ［０：１］を見つける。従って、作成部１３２は、文字位置情報付き圧縮符号Ｂ［２：３］Ｅ［０：１］と文字位置情報付き圧縮符号Ｅ［１：２］を組み合わせる。
【００８７】
そして、作成部１３２は、組み合わせた文字位置情報付き圧縮符号列「Ａ［１：２］Ａ［２：３］、Ｂ［２：３］Ｅ［０：１］Ｅ［１：２］」を検索用情報の次候補とする。
なお、本具体例では、検索により見つかった文字位置情報付き圧縮符号から現候補の文字位置情報付き圧縮符号列との組み合わせを探したが、現候補の文字位置情報付き圧縮符号列から検索により見つかった文字位置情報付き圧縮符号との組み合わせを探してもよい。
【００８８】
次に、検索部１３１は、「ｈ＄」を検索文字としてインデックスファイル１２ａを検索する（図９参照）。検索の結果、１７行目のレコード「ｈ＄：Ｆ［３：４］」を見つける。
【００８９】
作成部１３２は、現候補に含まれる文字位置情報付き圧縮符号列「Ａ［１：２］、Ｆ［２：３］、Ｂ［２：３］Ｅ［０：１］、Ｂ［２：３］Ｇ［０：１］」の各文字位置情報付き圧縮符号の最後尾の符号と、見つかったレコードに含まれる文字位置情報付き圧縮符号Ｆ［３：４］の符号が同一、かつ、文字位置情報が隣同士となる組み合わせを列挙する。
【００９０】
見つかったレコードに含まれる文字位置情報付き圧縮符号がＦ［３：４］であるため、符号が同じで隣同士となる文字位置情報付き圧縮符号は、Ｆ［２：３］である。作成部１３２は、Ｆ［２：３］を最後尾に含む文字位置情報付き圧縮符号を、現候補に含まれる文字位置情報付き圧縮符号列から探すと、文字位置情報付き圧縮符号Ｆ［２：３］を見つける。従って、作成部１３２は、文字位置情報付き圧縮符号Ｆ［２：３］と文字位置情報付き圧縮符号Ｆ［３：４］を組み合わせる。
【００９１】
そして、作成部１３２は、組み合わせた文字位置情報付き圧縮符号Ｆ［２：３］Ｆ［３：４］を検索用情報の仮候補とする。
次に、検索部１３１は、「＾ｅ」を検索文字としてインデックスファイル１２ａを検索する。検索の結果、２行目のレコード「＾ｅ：Ｃ［０：１］」を見つける。
【００９２】
作成部１３２は、見つかったレコードに含まれる文字位置情報付き圧縮符号Ｃ［０：１］を、仮候補の文字位置情報付き圧縮符号Ｆ［２：３］Ｆ［３：４］の最後尾に組み合わせた文字位置情報付き圧縮符号Ｆ［２：３］Ｆ［３：４］Ｃ［０：１］を作成する。そして、作成した文字位置情報付き圧縮符号Ｆ［２：３］Ｆ［３：４］Ｃ［０：１］を次候補に追加する。
【００９３】
この結果、次候補は、文字位置情報付き圧縮符号列「Ａ［１：２］Ａ［２：３］、Ｂ［２：３］Ｅ［０：１］Ｅ［１：２］、Ｆ［２：３］Ｆ［３：４］Ｃ［０：１］」を有する。
【００９４】
次に、作成部１３２は、次候補の文字位置情報付き圧縮符号列「Ａ［１：２］Ａ［２：３］、Ｂ［２：３］Ｅ［０：１］Ｅ［１：２］、Ｆ［２：３］Ｆ［３：４］Ｃ［０：１］」を現候補の文字位置情報付き圧縮符号列に置換する（図１０参照）。置換後、次候補の文字位置情報付き圧縮符号列をクリア（消去）する。
【００９５】
検索部１３１は、文字列「ｔｈｅｍ」の文字「ｔｈ」を除いた残り文字数が２文字以上か否かを判断すると、「ｅｍ」の２文字であるため、２文字以上であると判断する。
次の文字が存在するので、検索部１３１は、文字列「ｔｈｅｍ」の「ｔｈ」の次の文字を検索する。検索の結果、次の文字「ｅ」を見つけるので、検索部１３１は、見つかった文字「ｅ」を処理対象の文字に設定する。
【００９６】
そして、検索部１３１は、設定した処理対象の文字「ｅ」に次の文字「ｍ」を加えた文字列「ｅｍ」を検索文字としてインデックスファイル１２ａを検索する。検索の結果、検索部１３１は、８行目のレコード「ｅｍ：Ｃ［１：２］」を見つける。
【００９７】
作成部１３２は、現候補に含まれる文字位置情報付き圧縮符号列「Ａ［１：２］Ａ［２：３］、Ｂ［２：３］Ｅ［０：１］Ｅ［１：２］、Ｆ［２：３］Ｆ［３：４］Ｃ［０：１］」の各文字位置情報付き圧縮符号の最後尾の符号と、見つかったレコードに含まれる文字位置情報付き圧縮符号Ｃ［１：２］の符号が同一、かつ、文字位置情報が隣同士となる組み合わせを列挙する。
【００９８】
見つかった文字位置情報付き圧縮符号がＣ［１：２］であるため、符号が同じで隣同士となる文字位置情報付き圧縮符号は、Ｃ［０：１］である。作成部１３２は、文字位置情報付き圧縮符号Ｃ［０：１］を最後尾に含む文字位置情報付き圧縮符号を、現候補の文字位置情報付き圧縮符号列から探すと、文字位置情報付き圧縮符号Ｆ［２：３］［３：４］Ｃ［０：１］を見つける。従って、作成部１３２は、文字位置情報付き圧縮符号Ｃ［１：２］と文字位置情報付き圧縮符号Ｆ［２：３］Ｆ［３：４］Ｃ［０：１］を組み合わせる。
【００９９】
そして、作成部１３２は、組み合わせた圧縮符号Ｆ［２：３］Ｆ［３：４］Ｃ［０：１］Ｃ［１：２］を検索用情報の次候補とする。
次に、検索部１３１は、「ｅ＄」を検索文字としてインデックスファイル１２ａを検索する（図１１参照）。検索の結果、検索部１３１は、１６行目のレコード「ｅ＄：Ａ［３：４］，Ｅ［２：３］，Ｇ［３：４］」を見つける。
【０１００】
作成部１３２は、現候補の文字位置情報付き圧縮符号列「Ａ［１：２］Ａ［２：３］、Ｂ［２：３］Ｅ［０：１］Ｅ［１：２］、Ｆ［２：３］Ｆ［３：４］Ｃ［０：１］」の各文字位置情報付き圧縮符号の最後尾の符号と、見つかったレコードに含まれる文字位置情報付き圧縮符号「Ａ［３：４］，Ｅ［２：３］，Ｇ［３：４］」の各符号が同一、かつ、文字位置情報が隣同士となる組み合わせを列挙する。
【０１０１】
見つけた文字位置情報付き圧縮符号がＡ［３：４］，Ｅ［２：３］，Ｇ［３：４］であるため、作成部１３２は、まず、Ａ［３：４］について処理を行う。見つかったレコードに含まれる文字位置情報付き圧縮符号Ａ［３：４］については、符号が同じで文字位置情報が隣同士となる文字位置情報付き圧縮符号は、Ａ［２：３］である。
【０１０２】
作成部１３２は、Ａ［２：３］を最後尾に含む圧縮符号列を現候補の圧縮符号列から探すと、圧縮符号列Ａ［１：２］Ａ［２：３］を見つける。従って、作成部１３２は、圧縮符号列Ａ［１：２］Ａ［２：３］と文字位置情報付き圧縮符号Ａ［３：４］を組み合わせる。
【０１０３】
次に、作成部１３２は、Ｅ［２：３］について処理を行う。見つかったレコードに含まれる文字位置情報付き圧縮符号Ｅ［２：３］については、符号が同じで文字位置情報が隣同士となる文字位置情報付き圧縮符号は、Ｅ［１：２］である。
【０１０４】
作成部１３２は、Ｅ［１：２］を最後尾に含む圧縮符号列を現候補の圧縮符号列から探すと、圧縮符号列Ｂ［２：３］Ｅ［０：１］Ｅ［１：２］を見つける。従って、作成部１３２は、圧縮符号列Ｂ［２：３］Ｅ［０：１］Ｅ［１：２］と文字位置情報付き圧縮符号Ｅ［２：３］を組み合わせる。
【０１０５】
次に、作成部１３２は、Ｇ［３：４］について処理を行う。見つかったレコードに含まれる文字位置情報付き圧縮符号Ｇ［３：４］については、符号が同じで文字位置情報が隣同士となる文字位置情報付き圧縮符号は、Ｇ［２：３］である。
【０１０６】
作成部１３２は、Ｇ［２：３］を最後尾に含む圧縮符号列を現候補の圧縮符号列から探すと、見つからない。
この結果、作成部１３２は、組み合わせた文字位置情報付き圧縮符号Ａ［１：２］Ａ［２：３］Ａ［３：４］と文字位置情報付き圧縮符号Ｂ［２：３］Ｅ［０：１］Ｅ［１：２］Ｅ［２：３］を検索用情報の仮候補とする。
【０１０７】
次に、検索部１３１は、「＾ｍ」を検索文字としてインデックスファイル１２ａを検索する。検索の結果、５行目のレコード「＾ｍ：Ｄ［０：１］」を見つける。
作成部１３２は、見つかったＤ［０：１］を、仮候補の文字位置情報付き圧縮符号列「Ａ［１：２］Ａ［２：３］Ａ［３：４］、Ｂ［２：３］Ｅ［０：１］Ｅ［１：２］Ｅ［２：３］」それぞれの最後尾に組み合わせた文字位置情報付き圧縮符号列「Ａ［１：２］Ａ［２：３］Ａ［３：４］Ｄ［０：１］、Ｂ［２：３］Ｅ［０：１］Ｅ［１：２］Ｅ［２：３］Ｄ［０：１］」を作成する。そして、作成部１３２は、作成した文字位置情報付き圧縮符号列「Ａ［１：２］Ａ［２：３］Ａ［３：４］Ｄ［０：１］、Ｂ［２：３］Ｅ［０：１］Ｅ［１：２］Ｅ［２：３］Ｄ［０：１］」を次候補に追加する。
【０１０８】
この結果、次候補は、文字位置情報付き圧縮符号列「Ｆ［２：３］Ｆ［３：４］Ｃ［０：１］Ｃ［１：２］、Ａ［１：２］Ａ［２：３］Ａ［３：４］Ｄ［０：１］、Ｂ［２：３］Ｅ［０：１］Ｅ［１：２］Ｅ［２：３］Ｄ［０：１］」を有する。
【０１０９】
次に、作成部１３２は、次候補を現候補に置換する。置換後、仮候補をクリアする。
検索部１３１は、文字列「ｔｈｅｍ」の文字「ｔｈｅ」を除いた残り文字数が２文字以上か否かを判断すると、「ｍ」の１文字であるため、２文字未満であると判断する。
【０１１０】
検索用情報作成部１３は、現候補の文字位置情報付き圧縮符号列「Ｆ［２：３］Ｆ［３：４］Ｃ［０：１］Ｃ［１：２］、Ａ［１：２］Ａ［２：３］Ａ［３：４］Ｄ［０：１］、Ｂ［２：３］Ｅ［０：１］Ｅ［１：２］Ｅ［２：３］Ｄ［０：１］」を検索用情報として出力して処理を終了する。
【０１１１】
次に、ステップＳ４の検索結果出力部１４の処理の具体例を説明する。
図１２は、検索結果出力部の処理の具体例を説明する図である。
検索結果出力部１４は、検索用情報作成部１３が出力した検索用情報を構成する文字位置情報付き圧縮符号列「Ｆ［２：３］Ｆ［３：４］Ｃ［０：１］Ｃ［１：２］、Ａ［１：２］Ａ［２：３］Ａ［３：４］Ｄ［０：１］、Ｂ［２：３］Ｅ［０：１］Ｅ［１：２］Ｅ［２：３］Ｄ［０：１］」から文字位置情報を削除し、圧縮符号列「ＦＣ、ＡＤ、ＢＥＤ」を作成する。
【０１１２】
次に、検索結果出力部１４は、作成した圧縮符号列「ＦＣ、ＡＤ、ＢＥＤ」で圧縮文書２３ａを検索する。なお、具体例の圧縮文書２３ａには説明の便宜上、行番号を表記している。
【０１１３】
圧縮文書２３ａを行単位で検索した結果、検索結果出力部１４は、１行目の「ＡＤＢＣＢＣ」、６行目の「ＢＥＤＢＥＤ」、７行目の「ＦＡＤＡＣＢ」を見つける。なお、図１２では、見つけた行の、圧縮符号列に対応する部位をアンダーラインで示している。
【０１１４】
検索結果出力部１４は、見つかった１行目、６行目、７行目の文書を解凍する。そして、検索結果出力部１４は、文字位置情報付き圧縮符号列の文字位置情報を使ってハイライト（図１２では、アンダーライン部分）出力する。
【０１１５】
具体的には、検索結果出力部１４は、圧縮符号ＡＤについては、文字位置情報付き圧縮符号列Ａ［１：２］Ａ［２：３］Ａ［３：４］Ｄ［０：１］のＡ［１：２］Ａ［２：３］Ａ［３：４］に対応する「ｔｈｅ」、およびＤ［０：１］に対応する「ｍ」をハイライト出力する。
【０１１６】
また、検索結果出力部１４は、圧縮符号ＢＥＤについては、文字位置情報付き圧縮符号列Ｂ［２：３］Ｅ［０：１］Ｅ［１：２］Ｅ［２：３］Ｄ［０：１］のＢ［２：３］に対応する「ｔ」、Ｅ［０：１］Ｅ［１：２］Ｅ［２：３］に対応する「ｈｅ」、およびＤ［０：１］に対応する「ｍ」をハイライト出力する。
【０１１７】
また、検索結果出力部１４は、圧縮符号ＦＣについては、文字位置情報付き圧縮符号列Ｆ［２：３］Ｆ［３：４］Ｃ［０：１］Ｃ［１：２］のＦ［２：３］Ｆ［３：４］に対応する「ｔｈ」、およびＣ［０：１］Ｃ［１：２］に対応する「ｅｍ」をハイライト出力する。
【０１１８】
以上述べたように、文字列検索装置１０によれば、インデックスファイル１２ａを作成し、検索用情報を作成することで、ある文字列の後尾と他の文字列の先頭に跨る文字列の検索が可能となる。従って、正確に文字列を検索することができる。
【０１１９】
また、インデックスのサイズ（エントリ数とエントリ長）が抑えられるため、インデックスファイル１２ａの容量が抑えられる。これにより、高速に検索を終了することができる。
【０１２０】
次に、正確な検索ができること、およびインデックスファイル１２ａの容量が抑えられることを、比較例を挙げて説明する。
＜比較例＞
図１３は、比較例を説明する図である。
【０１２１】
図１３に示す比較例は、圧縮辞書２１ａから圧縮辞書２１ｂを作成することなく単純にバイグラムのインデックスファイル９１を作成している。そして作成されたインデックスファイル９１に基づいて、文字列「ｔｈｅｍ」を検索し、検索により得られた文字位置情報付き圧縮符号列を列挙している。図１３に示す比較例の場合、最後の文字と最初の文字のつなぎ部分の符号列が見つからない。従って、検索漏れが発生する可能性がある。
【０１２２】
図１４は、他の比較例を説明する図である。
図１４に示す比較例は、圧縮辞書２１ａのテキストの文字のつなぎ部分を全て登録したインデックスファイル９２を作成している。例えば、インデックスファイル９２の１４行目には、圧縮辞書２１ａの１行目のテキスト「ｔｈｅ」の最後の文字「ｅ」と、２行目のテキスト「ｉｔ」の最初の文字「ｉ」とをつないだ文字列「ｅｉ」をインデックスとし、このインデックスに対応する文字位置情報付き圧縮符号が関連づけられている。また、１９行目には、圧縮辞書２１ａの１行目のテキスト「ｉｔ」の最後の文字「ｔ」と、２行目のテキスト「ｅｍ」の最初の文字「ｅ」とをつないだ文字列「ｔｅ」をインデックスとし、このインデックスに対応する文字位置情報付き圧縮符号が関連づけられている。
【０１２３】
インデックスファイル９２を用いると、最後の文字と最初の文字のつなぎ部分の文字位置情報付き圧縮符号を見つけることは可能となるが、インデックスファイル９２の容量が、インデックスファイル１２ａよりも大きくなる。具体的には圧縮辞書２１ａのエントリ数の２乗の容量になる。このため、処理数が多く、処理に時間がかかってしまう。
【０１２４】
これに対し、本実施の形態のインデックスファイル１２ａであれば、バイグラムの場合、辞書のエントリ数をＮ、平均エントリ長をＭとすると、インデックスのサイズをＮ×Ｎ＋Ｎ×ＭからＮ×Ｍに削減できる。通常、ＭはＮに比べてとても小さいので、Ｍをほとんど無視できることを考えると、インデックスファイルの容量をＮ／Ｍ倍に圧縮できるということになる。
【０１２５】
以上、本発明の文字列検索装置、文字列検索方法および文字列検索プログラムを、図示の実施の形態に基づいて説明したが、本発明はこれに限定されるものではなく、各部の構成は、同様の機能を有する任意の構成のものに置換することができる。また、本発明に、他の任意の構成物や工程が付加されていてもよい。
【０１２６】
また、本発明は、前述した各実施の形態のうちの、任意の２以上の構成（特徴）を組み合わせたものであってもよい。
なお、文字列検索装置１０が行った処理が、複数の装置によって分散処理されるようにしてもよい。例えば、１つの装置が、インデックス作成処理までを行ってインデックスを生成しておき、他の装置が、そのインデックスを用いて検索用情報を作成するようにしてもよい。
【０１２７】
なお、上記の処理機能は、コンピュータによって実現することができる。その場合、文字列検索装置１、１０が有すべき機能の処理内容を記述したプログラムが提供される。そのプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、磁気記憶装置、光ディスク、光磁気記録媒体、半導体メモリ等が挙げられる。磁気記憶装置には、ハードディスク装置（ＨＤＤ）、フレキシブルディスク（ＦＤ）、磁気テープ等が挙げられる。光ディスクには、ＤＶＤ、ＤＶＤ−ＲＡＭ、ＣＤ−ＲＯＭ／ＲＷ等が挙げられる。光磁気記録媒体には、ＭＯ（Magneto-Optical disk）等が挙げられる。
【０１２８】
プログラムを流通させる場合には、例えば、そのプログラムが記録されたＤＶＤ、ＣＤ−ＲＯＭなどの可搬型記録媒体が販売される。また、プログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することもできる。
【０１２９】
プログラムを実行するコンピュータは、例えば、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、自己の記憶装置に格納する。そして、コンピュータは、自己の記憶装置からプログラムを読み取り、プログラムに従った処理を実行する。なお、コンピュータは、可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することもできる。また、コンピュータは、ネットワークを介して接続されたサーバコンピュータからプログラムが転送されるごとに、逐次、受け取ったプログラムに従った処理を実行することもできる。
【０１３０】
また、上記の処理機能の少なくとも一部を、ＤＳＰ（Digital Signal Processor）、ＡＳＩＣ（Application Specific Integrated Circuit）、ＰＬＤ（Programmable Logic Device）などの電子回路で実現することもできる。
【０１３１】
以上の第１〜第２の実施の形態に関し、さらに以下の付記を開示する。
（付記１）  検索文字列に含まれる（ｎ−１）（ｎ≧２）の文字数の文字列について、先頭の文字に前記文字列の先頭であることを示す先頭記号を加え、最後尾の文字に前記文字列の最後尾であることを示す後尾記号を加え、前記文字列と前記先頭記号の組み合わせと前記文字列と前記後尾記号の組み合わせとのそれぞれに一致する圧縮符号を、予め用意された任意の文字列の先頭に前記先頭記号を付加し、後尾に前記後尾記号を付加した文字列を用いて作成されたｎグラムのインデックスに前記インデックスそれぞれに対応する前記圧縮符号が関連づけられたインデックスファイルから検索する検索部と、
前記検索部の検索により得られた前記先頭の文字と前記先頭記号の組み合わせの検索結果と前記最後尾の文字と前記後尾記号の組み合わせの検索結果それぞれの組み合わせを、前記文字列の順番に並べた検索用情報を作成する作成部と、
を有することを特徴とする文字列検索装置。
【０１３２】
（付記２）  前記作成部により作成された前記圧縮符号の組み合わせの前記圧縮符号を用いて、前記圧縮符号を備える圧縮文書の前記圧縮符号に対応する部位を特定し、特定した部位を他の部位と区別し得る態様で出力する出力部をさらに有することを特徴とする付記１記載の文字列検索装置。
【０１３３】
（付記３）  前記インデックスには、さらに、前記圧縮符号における前記文字列の含まれる位置を示す文字位置情報が関連づけられており、
前記検索部は、前記先頭の文字と前記先頭記号の組み合わせと前記最後尾の文字と前記後尾記号の組み合わせとのそれぞれに一致する圧縮符号と前記圧縮符号における前記文字列の含まれる位置を示す文字位置情報を、前記インデックスファイルから検索し、
前記作成部は、前記検索結果それぞれの前記圧縮符号と前記文字位置情報の組み合わせを作成することを特徴とする付記１記載の文字列検索装置。
【０１３４】
（付記４）  前記作成部により作成された前記圧縮符号と前記文字位置情報の組み合わせに含まれる前記圧縮符号を用いて、前記圧縮符号を備える圧縮文書の前記圧縮符号に対応する部位を特定し、特定した部位を他の部位と区別し得る態様で出力する出力部をさらに有することを特徴とする付記３記載の文字列検索装置。
【０１３５】
（付記５）  前記出力部は、前記特定した部位に対し、前記文字位置情報に対応する部位のみを他の部位と区別し得る態様で出力することを特徴とする付記４記載の文字列検索装置。
【０１３６】
（付記６）  任意の文字列と前記文字列に対応する前記圧縮符号とが関連づけられた圧縮辞書の前記各文字列の先頭および後尾に前記先頭記号および前記後尾記号を付加して前記インデックスファイルの前記インデックスを作成するインデックスファイル作成部をさらに有することを特徴とする付記１記載の文字列検索装置。
【０１３７】
（付記７）  コンピュータが、
検索文字列に含まれる（ｎ−１）（ｎ≧２）の文字数の文字列について、先頭の文字に前記文字列の先頭であることを示す先頭記号を加え、最後尾の文字に前記文字列の最後尾であることを示す後尾記号を加え、前記文字列と前記先頭記号の組み合わせと前記文字列と前記後尾記号の組み合わせとのそれぞれに一致する圧縮符号を、予め用意された任意の文字列の先頭に前記先頭記号を付加し、後尾に前記後尾記号を付加した文字列を用いて作成されたｎグラムのインデックスに前記インデックスそれぞれに対応する前記圧縮符号が関連づけられたインデックスファイルから検索し、
検索により得られた前記先頭の文字と前記先頭記号の組み合わせの検索結果と前記最後尾の文字と前記後尾記号の組み合わせの検索結果それぞれの組み合わせを、前記文字列の順番に並べた検索用情報を作成する、
ことを特徴とする文字列検索方法。
【０１３８】
（付記８）  作成された前記圧縮符号の組み合わせの前記圧縮符号を用いて、前記圧縮符号を備える圧縮文書の前記圧縮符号に対応する部位を特定し、特定した部位を他の部位と区別し得る態様で出力することを特徴とする付記７記載の文字列検索方法。
【０１３９】
（付記９）  前記インデックスには、さらに、前記圧縮符号における前記文字列の含まれる位置を示す文字位置情報が関連づけられており、
前記検索では、前記先頭の文字と前記先頭記号の組み合わせと前記最後尾の文字と前記後尾記号の組み合わせとのそれぞれに一致する圧縮符号と前記圧縮符号における前記文字列の含まれる位置を示す文字位置情報を、前記インデックスファイルから検索し、
前記作成では、前記検索結果それぞれの前記圧縮符号と前記文字位置情報の組み合わせを作成することを特徴とする付記７記載の文字列検索方法。
【０１４０】
（付記１０）  作成された前記圧縮符号と前記文字位置情報の組み合わせに含まれる前記圧縮符号を用いて、前記圧縮符号を備える圧縮文書の前記圧縮符号に対応する部位を特定し、特定した部位を他の部位と区別し得る態様で出力することを特徴とする付記９記載の文字列検索方法。
【０１４１】
（付記１１）  前記出力では、前記特定した部位に対し、前記文字位置情報に対応する部位のみを他の部位と区別し得る態様で出力することを特徴とする付記１０記載の文字列検索方法。
【０１４２】
（付記１２）  任意の文字列と前記文字列に対応する前記圧縮符号とが関連づけられた圧縮辞書の前記各文字列の先頭および後尾に前記先頭記号および前記後尾記号を付加して前記インデックスファイルの前記インデックスを作成することを特徴とする付記７記載の文字列検索方法。
【０１４３】
（付記１３）  コンピュータに、
検索文字列に含まれる（ｎ−１）（ｎ≧２）の文字数の文字列について、先頭の文字に前記文字列の先頭であることを示す先頭記号を加え、最後尾の文字に前記文字列の最後尾であることを示す後尾記号を加え、前記文字列と前記先頭記号の組み合わせと前記文字列と前記後尾記号の組み合わせとのそれぞれに一致する圧縮符号を、予め用意された任意の文字列の先頭に前記先頭記号を付加し、後尾に前記後尾記号を付加した文字列を用いて作成されたｎグラムのインデックスに前記インデックスそれぞれに対応する前記圧縮符号が関連づけられたインデックスファイルから検索する検索手順、
前記検索手順の検索により得られた前記先頭の文字と前記先頭記号の組み合わせの検索結果と前記最後尾の文字と前記後尾記号の組み合わせの検索結果それぞれの組み合わせを、前記文字列の順番に並べた検索用情報を作成する作成手順、
を実行させることを特徴とする文字列検索プログラム。
【０１４４】
（付記１４）  前記コンピュータに、前記作成手順により作成された前記圧縮符号の組み合わせの前記圧縮符号を用いて、前記圧縮符号を備える圧縮文書の前記圧縮符号に対応する部位を特定し、特定した部位を他の部位と区別し得る態様で出力する出力手順をさらに実行させることを特徴とする付記１３記載の文字列検索プログラム。
【０１４５】
（付記１５）  前記インデックスには、さらに、前記圧縮符号における前記文字列の含まれる位置を示す文字位置情報が関連づけられており、
前記検索手順では、前記先頭の文字と前記先頭記号の組み合わせと前記最後尾の文字と前記後尾記号の組み合わせとのそれぞれに一致する圧縮符号と前記圧縮符号における前記文字列の含まれる位置を示す文字位置情報を、前記インデックスファイルから検索し、
前記作成手順では、前記検索結果それぞれの前記圧縮符号と前記文字位置情報の組み合わせを作成することを特徴とする付記１３記載の文字列検索プログラム。
【０１４６】
（付記１６）  前記コンピュータに、前記作成手順により作成された前記圧縮符号と前記文字位置情報の組み合わせに含まれる前記圧縮符号を用いて、前記圧縮符号を備える圧縮文書の前記圧縮符号に対応する部位を特定し、特定した部位を他の部位と区別し得る態様で出力する出力手順をさらに実行させることを特徴とする付記１５記載の文字列検索プログラム。
【０１４７】
（付記１７）  前記出力手順では、前記特定した部位に対し、前記文字位置情報に対応する部位のみを他の部位と区別し得る態様で出力することを特徴とする付記１６記載の文字列検索装置。
【０１４８】
（付記１８）  前記コンピュータに、任意の文字列と前記文字列に対応する前記圧縮符号とが関連づけられた圧縮辞書の前記各文字列の先頭および後尾に前記先頭記号および前記後尾記号を付加して前記インデックスファイルの前記インデックスを作成するインデックスファイル作成手順をさらに実行させることを特徴とする付記１３記載の文字列検索プログラム。
【符号の説明】
【０１４９】
１、１０  文字列検索装置
１ａ、１３１  検索部
１ｂ、１３２  作成部
１ｃ、１１  インデックスファイル作成部
１ｄ  結果作成部
２、２３ａ  圧縮文書
３、１２ａ  インデックスファイル
４、４ａ、２１ａ、２１ｂ  圧縮辞書
５  圧縮符号列
１２  インデックスファイル格納部
１３  検索用情報作成部
１４  検索結果出力部
２１  圧縮辞書格納部
２２  圧縮文書格納部
【図１】
0005648360.tif 000002
【図２】
0005648360.tif 000003
【図３】
0005648360.tif 000004
【図４】
0005648360.tif 000005
【図５】
0005648360.tif 000006
【図６】
0005648360.tif 000007
【図７】
0005648360.tif 000008
【図８】
0005648360.tif 000009
【図９】
0005648360.tif 000010
【図１０】
0005648360.tif 000011
【図１１】
0005648360.tif 000012
【図１２】
0005648360.tif 000013
【図１３】
0005648360.tif 000014
【図１４】
0005648360.tif 000015