(57)【要約】【課題】N-gramインデックスと圧縮全文索引のハイブリッドインデックスを提案する。【解決手段】文書検索装置の検索サーバが、文書検索処理手段として、検索式の各検索タームに対応するインデックスタームについてN-gramインデックス型検索を実行し、N-gramインデックスＤＢの当該インデックスタームの情報を用いて圧縮全文索引での当該検索タームの処理時間の予測値を計算し、予測値に基づいて圧縮全文索引での当該検索タームの処理順序を変更した圧縮全文索引型検索式を構築し、構築した検索式に含まれる検索タームの圧縮全文索引での検索が不要である場合に検索をスキップし、当該検索タームを構成するインデックスタームの情報をN-gramインデックスＤＢから取得して圧縮全文索引での文字の照合回数を削減し、圧縮全文索引型検索式を用いて圧縮全文索引ＤＢに対して圧縮全文索引型検索を実行する。【選択図】図１
2015056089.tif 000002
【特許請求の範囲】
【請求項１】
検索対象の文書を格納した文書データＤＢと、
前記検索対象の文書に含まれるインデックスタームと当該インデックスタームを含む文書数と当該インデックスタームで開始する接尾辞が存在する圧縮全文索引でのヒット区間と前記検索対象の文書を区別する文書番号による文書番号リストと前記検索対象の文書における当該インデックスタームの文字位置による文字位置リストとを格納したN-gramインデックスＤＢと、
前記文書データＤＢに格納された前記検索対象の文書の集合から作成された圧縮全文索引を格納した圧縮全文索引ＤＢと、を備えた検索サーバを有する文書検索装置であって、前記検索サーバが、
検索タームを論理式で組み合わせた検索式の入力を受けて当該検索タームを含む文書を検索する文書検索処理手段を備え、前記文書検索処理手段は、
入力された検索式に含まれる各検索タームについて、当該検索タームに対応するインデックスタームの情報を前記N-gramインデックスＤＢから取得して、N-gramインデックス型検索を実行する手段と、
前記検索式に含まれる各検索ターム毎に、当該検索タームを構成するインデックスタームについて前記N-gramインデックスＤＢに格納されている当該インデックスタームの情報を用いることにより、圧縮全文索引での当該検索タームの処理時間の予測値を計算する手段と、
前記検索式に含まれる各検索タームの前記予測値に基づいて、圧縮全文索引での当該検索タームの処理順序を変更した圧縮全文索引型検索式を構築する手段と、
前記圧縮全文索引型検索式に含まれる各検索タームについて、当該検索タームの前記圧縮全文索引での検索が不要である場合に、前記圧縮全文索引での検索をスキップする手段と、
前記当該検索タームを構成するインデックスタームの情報を前記N-gramインデックスＤＢから取得して、圧縮全文索引での当該検索タームの文字の照合回数を削減する手段と、
前記圧縮全文索引型検索式を用いて、前記圧縮全文索引ＤＢに対して圧縮全文索引型検索を実行する手段と、を含むことを特徴とする
文書検索装置。
【請求項２】
前記検索サーバが、登録指示された文書データを前記文書データＤＢに記憶し、当該文書データから前記インデックスタームを抽出し、当該文書データの文書番号と当該インデックスタームの当該文書データにおける文字位置を当該インデックスタームと組み合わせて前記N-gramインデックスＤＢに記憶する文書登録処理手段を備え、前記文書登録処理手段は、インデックスタームを含む文書の文書番号と文字位置を分割して登録する手段を含むことを特徴とする請求項１に記載の文書検索装置。
【請求項３】
前記検索サーバが、前記文書データＤＢから圧縮全文索引を作成して前記圧縮全文索引ＤＢに記憶する圧縮全文索引構築処理手段を備え、前記圧縮全文索引構築処理手段は、前記文書データＤＢに登録されている文書集合から圧縮全文索引を作成し、前記N-gramインデックスＤＢに格納されている辞書の更新と文字位置リストの削除を実行する手段を含むことを特徴とする請求項１又は２に記載の文書検索装置。
【請求項４】
前記インデックスタームにおいて、頻繁に検索されるタームである特定のタームを指定できることを特徴とする請求項１〜３のいずれかに記載の文書検索装置。
【請求項５】
前記検索式に含まれる各検索タームであって、当該検索タームを構成するインデックスタームのN-gramインデックスＤＢに格納されている情報を用いて、前記圧縮全文索引での予想ヒット数と予想文書数を算出し、当該予想ヒット数と当該予想文書数から前記予測値を計算することを特徴とする請求項１〜４のいずれかに記載の文書検索装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、N-gramインデックスと圧縮全文索引をハイブリッドしたインデックスを持つ文書検索装置に関する。
【背景技術】
【０００２】
現代社会では、膨大な量の電子文書データがオフィスなどにおいて日々作成されている。希望の情報を含む電子文書データを膨大な量の電子文書データから短時間で検索し、検索結果を出力する文書検索技術は、電子文書データの活用のために必須である。
【０００３】
文書検索を実現するインデックスとしては、従来からN-gramインデックスが使われることが多い。N-gramインデックスとは、”日本語文書用高速全文検索の一手法”（非特許文献１)に記載されているようなインデックスのことである。文字種に応じて１文字または連接２文字をインデックスターム(以下、N-gramインデックスのインデックスタームをN-gramタームと呼ぶ)とし、それらの出現する文書番号と出現位置を利用して、検索ターム中の位置関係とN-gramインデックス中の位置関係が等しいかどうかを判定(以下、隣接判定と呼ぶ)する方式が開示されている。N-gramインデックスは、多くの場合、文書集合に対して数倍のデータサイズになる。検索を行う時は、検索式に指定されたタームをN-gramタームに分割して、N-gramタームごとの文書番号と文字位置を読み込んで隣接判定を行う。
【０００４】
近年、N-gramインデックスとは別の検索技術として、文書を圧縮したまま検索を実行できる”圧縮全文索引”と呼ばれる技術がある。圧縮全文索引には、“高速文字列解析の世界”(非特許文献２)に示されるようなCSAやFM-Indexなどがある。圧縮全文索引の特徴として、圧縮しているということもあり、インデックスサイズが小さいということがある。実装の仕方にも依存するが、多くの場合、文書サイズよりも小さくなる。文書集合を扱う場合は、それぞれの文書を連結した文字列を作成し、その文字列から圧縮全文索引を作成する。また、文書を追加する場合は、圧縮全文索引を再作成する必要がある。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】日本語文書用高速全文検索の一手法, 電子情報通信学会論文誌 D-1 Vol.J75-D-1 No.9, 1992.
【非特許文献２】高速文字列解析の世界, 岡野原 大輔, 岩波書店, 2012.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
N-gramインデックスは、登録する文書のサイズに対して、インデックスサイズが大きいという問題がある。これは、N-gramインデックスが保持している文字位置のデータサイズが大きいためである。多くの場合、インデックスサイズが、登録する文書のサイズの数倍となる。これに対して、圧縮全文索引は、文字位置を保持していないため、登録する文書のサイズよりも小さいサイズとなる。このため、インデックスサイズが重要な場合、N-gramインデックスを圧縮全文索引に置き換えることが考えられる。しかし、N-gramインデックスを圧縮全文索引に置き換える場合、以下のような問題がある。
【０００７】
検索の問題としては、１文字の検索のようにヒット数が多い検索の場合の文書番号を取得するのに時間がかかる点と、検索式に複数の検索タームが指定された場合に無駄な照合が発生することがある点である。
【０００８】
文書の追加処理の問題としては、圧縮全文索引に文書を追加する場合は、再作成が必要であるため、文書を追加する処理に時間がかかる点である。
【０００９】
本発明の目的は、上記の課題を解決するために、N-gramインデックスと圧縮全文索引のハイブリッドインデックスを提案することにある。
【課題を解決するための手段】
【００１０】
上記目的を達成するため、本発明は、以下の構成を提供する。
本発明の態様は、検索対象の文書を格納した文書データＤＢと、
前記検索対象の文書に含まれるインデックスタームと当該インデックスタームを含む文書数と当該インデックスタームで開始する接尾辞が存在する圧縮全文索引でのヒット区間と前記検索対象の文書を区別する文書番号による文書番号リストと前記検索対象の文書における当該インデックスタームの文字位置による文字位置リストとを格納したN-gramインデックスＤＢと、
前記文書データＤＢに格納された前記検索対象の文書の集合から作成された圧縮全文索引を格納した圧縮全文索引ＤＢと、を備えた検索サーバを有する文書検索装置であって、前記検索サーバが、
検索タームを論理式で組み合わせた検索式の入力を受けて当該検索タームを含む文書を検索する文書検索処理手段を備え、前記文書検索処理手段は、
入力された検索式に含まれる各検索タームについて、当該検索タームに対応するインデックスタームの情報を前記N-gramインデックスＤＢから取得して、N-gramインデックス型検索を実行する手段と、
前記検索式に含まれる各検索ターム毎に、当該検索タームを構成するインデックスタームについて前記N-gramインデックスＤＢに格納されている当該インデックスタームの情報を用いることにより、圧縮全文索引での当該検索タームの処理時間の予測値を計算する手段と、
前記検索式に含まれる各検索タームの前記予測値に基づいて、圧縮全文索引での当該検索タームの処理順序を変更した圧縮全文索引型検索式を構築する手段と、
前記圧縮全文索引型検索式に含まれる各検索タームについて、当該検索タームの前記圧縮全文索引での検索が不要である場合に、前記圧縮全文索引での検索をスキップする手段と、
前記当該検索タームを構成するインデックスタームの情報を前記N-gramインデックスＤＢから取得して、圧縮全文索引での当該検索タームの文字の照合回数を削減する手段と、
前記圧縮全文索引型検索式を用いて、前記圧縮全文索引ＤＢに対して圧縮全文索引型検索を実行する手段と、を含むことを特徴とする。
【００１１】
一態様においては、前記検索サーバが、登録指示された文書データを前記文書データＤＢに記憶し、当該文書データから前記インデックスタームを抽出し、当該文書データの文書番号と当該インデックスタームの当該文書データにおける文字位置を当該インデックスタームと組み合わせて前記N-gramインデックスＤＢに記憶する文書登録処理手段を備え、前記文書登録処理手段は、インデックスタームを含む文書の文書番号と文字位置を分割して登録する手段を含むことを特徴とする。
【００１２】
一態様においては、前記検索サーバが、前記文書データＤＢから圧縮全文索引を作成して前記圧縮全文索引ＤＢに記憶する圧縮全文索引構築処理手段を備え、前記圧縮全文索引構築処理手段は、前記文書データＤＢに登録されている文書集合から圧縮全文索引を作成し、前記N-gramインデックスＤＢに格納されている辞書の更新と文字位置リストの削除を実行する手段を含むことを特徴とする請求項１又は２に記載の文書検索装置。
【００１３】
一態様においては、前記インデックスタームにおいて、頻繁に検索されるタームである特定のタームを指定できる。
【００１４】
一態様においては、前記検索式に含まれる各検索タームであって、当該検索タームを構成するインデックスタームのN-gramインデックスＤＢに格納されている情報を用いて、前記圧縮全文索引での予想ヒット数と予想文書数を算出し、当該予想ヒット数と当該予想文書数から前記予測値を計算する。
【発明の効果】
【００１５】
本発明の文書検索装置によれば、以下のような効果がある。
インデックスサイズの効果として、N-gramインデックスの文字位置を保持する代わりに、圧縮全文索引を保持することにより、全文検索を実現しつつ、N-gramインデックスよりインデックスサイズを削減することができる。
【００１６】
検索の効果として、圧縮全文索引は、検索タームのヒット数が多い場合に、文書番号を取得する処理を苦手としているが、N-gramインデックスに、該当する検索タームを登録しておくことにより、文書番号リストを利用でき、高速に文書番号を取得することができる。また、検索式内の複数のタームを圧縮全文索引で検索する場合は、N-gramインデックスに保持しているヒット数と文書数を利用して、各タームの処理時間を見積もり、圧縮全文索引での検索順序を変更することにより、無駄な照合を減らすことができる。
【００１７】
文書の追加処理の効果として、追加する文書の文字位置をN-gramインデックスに登録することにより、圧縮全文索引を変更することなく、文書を追加することができる。この処理により、全文検索を実現しつつ、インデックスサイズの増加も抑えることができる。追加した文字位置は、一定期間経過後、圧縮全文索引を再作成することで、削除することができる。
【図面の簡単な説明】
【００１８】
【図１】本発明による文書検索装置全体のブロック図である。
【図２】本発明の実施例の検索サーバで実行される処理フロー図である。
【図３】N-gramインデックスＤＢに含まれる辞書の一例である。
【図４】N-gramインデックスＤＢに含まれる文書番号リストの一例である。
【図５】本発明の実施例のN-gramインデックスに対する検索処理のフローチャートである。
【図６】圧縮全文索引ＤＢに含まれる圧縮全文索引の一例である。
【図７】本発明の実施例の圧縮全文索引検索用検索式の構築処理のフローチャートである。
【図８】本発明の実施例の文書の登録処理のフローチャートである。
【図９】N-gramインデックスＤＢに含まれる文字位置リストの一例である。
【図１０】本発明の実施例の文字位置のあるN-gramインデックスに対する検索処理のフローチャートである。
【発明を実施するための形態】
【００１９】
以下、本発明の実施の形態を、一例を示した図面に基づいて説明する。
図１は、本発明の文書検索装置のシステム構成例を示す図である。文書検索装置は、検索クライアント10とネットワーク11と検索サーバ12とを備える。
【００２０】
検索サーバ12は、ＣＰＵ121、メモリ122、文書データＤＢ123、N-gramインデックスＤＢ124、圧縮全文索引ＤＢ125を備える。
【００２１】
N-gramインデックスＤＢ124は、辞書1241、文書番号リスト1242、文字位置リスト1243を備える。
【００２２】
検索サーバ12は、N-gramインデックス検索部127、圧縮全文索引検索式構築部128、圧縮全文索引検索部129、N-gramインデックス登録部130、圧縮全文索引構築部131を構成するプログラム、及びデータ通信部126を格納している。
【００２３】
ＣＰＵ121は、N-gramインデックス検索部127、圧縮全文索引検索式構築部128、圧縮全文索引検索部129、N-gramインデックス登録部130、圧縮全文索引構築部131を構成する各種プログラムを実行することによって各処理を実行する。メモリ122は、ＣＰＵ121が実行するプログラムを実行するために必要なデータを一時的に記憶する。
【００２４】
データ通信部126は、ネットワーク11を介してデータ通信をするインターフェースである。検索サーバ12は、データ通信部126を介してネットワーク11に接続された検索クライアント10と通信する。検索クライアント10は、利用者からの検索式を受け付けて、ネットワーク11を介して検索結果を受け取り、利用者に提示する。検索クライアント10の内部構成については説明を省略する。
【００２５】
図２は、文書検索装置で実行される検索処理のフロー全体を示す図である。以下、図２に基づいて、N-gramインデックス検索部127、圧縮全文索引検索式構築部128、圧縮全文索引検索部129によって実行される処理の概要を説明する。
【００２６】
検索クライアント10から送られた検索式201が、
Q={ (京都 + 大阪) * 市役所 }
だったとする。この検索式は、検索タームを論理式で組み合わせており、”京都”または”大阪”を含みかつ”市役所”を含む文書を見つけるための検索式である。つまり、”*”が論理積(AND)を表現し、”+”が論理和(OR)を表現する。
【００２７】
まず、N-gramインデックス型検索202を行う。N-gramインデックスＤＢ124に対する検索処理の詳細な説明は後述する。なお、検索式によっては、N-gramインデックスＤＢ124のみで検索を完了できるので、その場合は、検索処理を終了する(ステップ203)。
【００２８】
次に、N-gramインデックスＤＢ124の情報を参照して、圧縮全文索引型検索式構築204により検索式を構築する。圧縮全文索引型検索式205の構築が終了したら、圧縮全文索引ＤＢ125に対して、圧縮全文索引型検索206を行う。また、圧縮全文索引の検索時にもN-gramインデックスＤＢ124の情報を利用する。圧縮全文索引に対する検索処理の詳細な説明は後述する。
【００２９】
最終的に、N-gramインデックスの検索結果と圧縮全文索引の検索結果を統合して、検索式を満たす検索結果として文書番号集合207を作成する。
【００３０】
以下では、N-gramインデックス型検索202について詳細に説明する。図５は、N-gramインデックス型検索202で実行される検索処理のフローチャートを示す図である。
【００３１】
最初に、検索式201の検索タームから辞書1241を利用して、N-gramタームを取得する(S501)。図３は、辞書1241に格納されるテーブルの構成の一例を示す図である。辞書1241は、文書番号リスト1242を取得するために、N-gramターム301をターム番号302に変換するテーブルである。また、変換時には、圧縮全文索引での検索に利用するヒット区間303とN-gramタームを含む文書数304も取得できる。本実施例では、文字2-gramをN-gramタームとして用いることとする。例えば、”京都”と”大阪”は、２文字なので、テーブルを参照し、ターム番号１とターム番号２を取得することができる。また、”市役所”は、３文字以上であることから、テーブルに該当する項目がないため、検索を行わない。
【００３２】
一般的な文字位置を持つN-gramインデックスであれば、”市役所”を”市役”と”役所”に分割して、文字位置の隣接照合により検索を実行する。しかし、本実施例において、３文字以上のタームの検索は、圧縮全文索引を利用して実行するので、３文字以上のタームをN-gramタームに分割して検索しない。ただし、登録時は、”市役所”を”市役”と”役所”に分割して登録する。これは、”市役”や”役所”が検索式の検索タームに用いられた場合に、２文字の検索を実現するためである。
【００３３】
なお、ここでは、一例として、文字2-gramをN-gramタームとして用いたが、その他にも、文字1-gramや文字3-gramなどをN-gramタームとして用いることも可能である。また、文字1-gramと文字2-gramを併用することも可能である。例えば、”市役所”を”市役”と”所”という2-gramと1-gramに分割して登録しても良い。また、検索ログなどからよく検索されるタームを抽出し、登録しておいても良い。例えば、”市役所”をN-gramタームとして登録しておけば、”市役所”を検索する時に、N-gramインデックスのみで検索を完了することができる。
【００３４】
次に、文書番号リスト1242を利用して、ターム番号から文書番号リストを取得する(S503)。図４は、ターム番号に対応する文書番号リストが記録されているテーブルの構成の一例を示す図である。文書番号リストは、内部的には、配列などで実装する。例えば、”京都”のターム番号は1であるので、対応する文書番号リストとして、{1,5,11,25,39,...}を取得することができる。N-gramタームが残っていない場合は、次に進む(S502)。
【００３５】
最後に、検索式にしたがって、文書番号リストを照合する(S504)。この例の場合、”京都”と”大阪”のOR検索を行う。この結果と圧縮全文索引で”市役所”を検索した結果でAND検索を行い、検索結果として文書番号集合207を作成する。
【００３６】
以下では、圧縮全文索引の検索処理について説明する。本実施例では、圧縮全文索引ＤＢ125に格納する圧縮全文索引として、FM-Indexを用いる。まず、図６を用いて、圧縮全文索引ＤＢ125に格納するFM-Indexについて説明した後、圧縮全文索引型検索式構築204と圧縮全文索引型検索206について説明する。FM-Indexの詳細は、非特許文献２を参照されたい。
【００３７】
文書集合データ601に、文書データ602と文書データ603があり、これらを連結した文字列データ604がある。文字列データ604の文字数をnとし、文字位置を0からn−1で表現する。例えば、文字列データ604において、文字数は12であり、位置7の文字は”阪”であり、最後の文字位置は11である。それぞれの文書データの境界には、”$”が存在する。”$”は、辞書順で他のすべての文字よりも小さい文字とする。
【００３８】
文字列データ604のすべての接尾辞を取り出し、辞書順でソートした結果が接尾辞ソート結果605である。また、接尾辞ソート結果605の各接尾辞の文字列データ604での位置を記録した配列が接尾辞配列データ606である。ここで、接尾辞配列データ606内での位置と文字列データ604での位置との混同を防ぐために、context番号611をiとして、接尾辞配列データ606でi番目の値を、SA[i]で表記する。例えば、SA[5]は、2となる。
【００３９】
BWT607は、文字列604に対して、BW変換(Burrows-Wheeler変換)を適用した結果の文字列である。SA[i]と同様に、context番号611をiとして、BWT607でi番目の値をBWT[i]で表記する。BW変換は、接尾辞配列データ606が存在する場合は、SA[i]の一つ前の位置の文字列データ604の文字を出力すれば良い。つまり、BWT[i]は、文字列604のSA[i]−1の位置の文字となる。ただし、SA[i]が0の場合は、最後の文字位置の文字となる。例えば、SA[5]が2なので、SA[5]−1の位置の文字は、”都”となる。SA[2]が0なので、BWT[2]は、最後の文字である”$”となる。FM-Indexでは、BWT607を圧縮しつつ、高速にアクセスするために、ウェーブレット木に変換するのが一般的である。
【００４０】
FM-Indexで検索を実行するためには、LF-Mapping処理を実行する必要がある。LF-Mapping処理とは、context番号としてiが与えられた時に、SA[i]の一つ前の位置であるSA[i]−1の接尾辞配列データ606におけるcontext番号を特定する処理である。そのcontext番号を以下では、LF(i)と表記する。例えば、LF(10)は、SA[10]−1の接尾辞配列データ606におけるcontext番号である2となる。
【００４１】
FM-Indexでの検索は、接尾辞配列データ606において、検索タームで始まる接尾辞が存在する区間を特定することと等しい。検索タームの後ろから1文字ずつ取り出し、接尾辞が存在する区間を特定する。例えば、”市役所”を検索する場合、まず、”所”を検索し、context番号が8から9の区間に存在することを特定する。次に、”所”の区間から”役”を検索し、”役所”という接尾辞が存在する区間を特定して、context番号の6から7の区間を得る。最後に、”役所”の区間から”市”を検索し、”市役所”という接尾辞が、context番号の4から5の区間に存在することを特定する。タームがヒットしている区間をヒット区間612とする。また、検索時間は、タームの長さに比例する。詳細は、非特許文献２を参照されたい。
【００４２】
FM-Indexでは、接尾辞配列データ606を保持していないため、ヒット区間がわかっても文字列604での位置がわからない。位置を取得するために、接尾辞配列データ606を一定間隔でサンプリングしたサンプリング接尾辞配列データ610とcontext番号をマークした位置マーク配列608を保持する。サンプリング接尾辞配列データ610は、左から右に要素が格納され、先頭の要素番号は0とする。また、サンプリング間隔を4としている。例えば、SA[3]を取得する場合、位置マーク配列608から、サンプリングされていないことがわかるので、LF(3)=1とし、次にチェックするcontext番号を1に更新する。context番号が1の場合、位置マーク配列608からサンプリングされていないことがわかるので、LF(1)=9とし、次にチェックするcontext番号を9に更新する。context番号が9の場合、位置マーク配列608からサンプリングされていることがわかるので、位置マーク配列608の先頭からcontext番号の9まで1の数を数えると、2が得られる。この結果から、サンプリング接尾辞配列データ610の2番目の要素である4を取得する。最終的に、2回のLF-Mappingを行ったので、SA[3]は、4の位置から2文字進めた6の位置となる。このような処理で文字位置を取得する処理を、以下では、文字位置取得処理と呼ぶ。
【００４３】
タームがヒットした位置の文書番号を取得するには、文書の区切りをマークした文書マーク配列609を利用する。文字列604で、文書の区切り文字である”$”が存在する位置をマークしている。この文書マーク配列609と文字位置取得処理を用いて、文書番号を取得する。例えば、context番号が3の文字位置であるSA[3]は、文字位置取得処理によって、6であることがわかり、文書マーク配列609において、6の位置までに存在する1の数は1つであるため、SA[3]の接尾辞は、文書1の接尾辞であることがわかる。また、同一の接尾辞が存在する区間で、各接尾辞の文書番号は、昇順に並んでいるというわけではなく、ランダムに並んでいる。例えば、”市役所”というタームの検索結果として、4と5というヒット区間が得られたとする。この場合、SA[4]は8なので、文書番号として1が得られ、SA[5]は2なので、文書番号として0が得られる。このような処理で文書番号を取得する処理を、以下では、文書番号取得処理と呼ぶ。
【００４４】
以下では、圧縮全文索引検索式構築部128で実行される圧縮全文索引型検索式構築204について詳細に説明する。図 7に、検索式構築のフローチャートを示す。
まず、検索式から検索タームを取り出す(S701)。例えば、
Q={(京都 + 大阪) + (東京都庁 * 京都市役所 * 大阪市役所)}
という検索式の場合、”京都”と”大阪”は、N-gramインデックスを利用して検索できるため、これらの検索タームを取り出さない。これに対して、”東京都庁”と”京都市役所”と”大阪市役所”は、N-gramインデックスを利用して検索できないため、これらの検索タームを取り出す。取り出した検索タームは、
Qw={“東京都庁”, “京都市役所”, “大阪市役所”}
とする。
【００４５】
次に、Qw内の検索タームをN-gramタームに分割する(S703)。Qwを2-gramに分割すると、
Qb={
“東京 * 京都 * 都庁”,
“京都 * 都市 * 市役 * 役所”,
“大阪 * 阪市 * 市役 * 役所”
}
となる。
【００４６】
N-gramタームに分割したQbとN-gramインデックスを利用して、予想ヒット数を計算する(S704)。辞書30には、ヒット区間303が付与されており、辞書に登録されているN-gramタームのFM-Indexにおけるヒット区間を取得できる。例えば、N-gramターム301の”大阪”のヒット区間303は、開始位置が1015であり、終了位置が1191である。このとき、ヒット数は、1191 ? 1015 = 176なので、”大阪”で開始する接尾辞が176個ヒットする。このN-gramタームのヒット数を利用して、検索タームのヒット数を見積もる。例えば、”京都市役所”というタームの2-gramのヒット数が以下のようになったとする。
“京都”→519
“都市”→731
“市役”→153
“役所”→321
【００４７】
このとき、”京都市役所”という検索タームのヒット数は、分割した2-gramの最小ヒット数よりも大きくならない。上記の例の場合、”市役”の153よりも大きくならないため、”京都市役所”の予想ヒット数は、153となる。また、N-gramタームが、辞書に存在しない場合は、予想ヒット件数が0件となるが、その場合は、Qwから該当する検索タームを取り除く。
【００４８】
N-gramタームに分割したQbとN-gramインデックスを利用して、予想文書数を計算する(S705)。この処理は、文書数に基づいて計算すること以外は、予想ヒット数の計算(S704)と同じであるため、詳細については記述しない。
検索タームが残っていない場合は、次に進む(S702)。
【００４９】
予想ヒット数と予想文書数を利用して、圧縮全文索引での検索タームの処理順序を変更する(S706)。例えば、
Qand={ 東京都庁 * 京都市役所 * 大阪市役所 }
というAND検索の検索式の場合、予想ヒット数が、以下のようになったとする。
“東京都庁”→1517
“京都市役所”→115
“大阪市役所”→75
【００５０】
このとき、AND検索を”東京都庁→京都市役所→大阪市役所”の順序で行わず、予想ヒット数が少ない”大阪市役所→京都市役所→東京都庁”の順序で行う。また、予想ヒット数が同一だった場合は、同一だった検索ターム内で予想文書数が小さい順に並べ替える。
【００５１】
AND検索において、検索タームを並べ替えた結果を利用することで、AND検索が成立しない場合に、圧縮全文索引での検索を途中で終了しやすくなる(圧縮全文索引型検索206)。このことにより、文書番号取得処理の実行回数を削減できる。具体的には、処理順序の並び替えを実行しない場合、”東京都庁”と”京都市役所”をAND検索するために、”東京都庁”の予想ヒット数の1517と”京都市役所”の予想ヒット数の115の合計である1632回の文書番号取得処理を実行する可能性がある。これに対して、”大阪市役所”の予想ヒット数は75であり、”京都市役所”の予想ヒット数との合計は、190となる。この場合、”京都市役所”と”大阪市役所”のANDが成立しなければ、190回しか文書番号取得処理を実行する可能性がないため、文書番号の取得にかかる処理時間は短くなる。
【００５２】
OR検索の場合は、まず、予想文書数が多い順に検索タームを並べ替える。予想文書数が同一だった場合は、同一だった検索ターム内で予想ヒット数が大きい順に並べ替える。
【００５３】
OR検索において、検索タームを並び替えた結果を利用することで、検索タームの圧縮全文索引での検索をスキップすることができる(圧縮全文索引型検索206)。まず、圧縮全文索引から、予想文書数の最も多い検索タームがヒットする文書番号をすべて取得し、OR基準文書番号集合とする。残りの検索タームは、圧縮全文索引から文書番号を取得する前に、検索タームを構成するN-gramタームの文書番号リストをAND照合した予想文書番号集合を作成する。OR基準文書番号集合が予想文書番号集合をすべて含んでいれば、該当する検索タームの圧縮全文索引での検索をスキップすることができる。そうでない場合は、圧縮全文索引から該当する検索タームの文書番号をすべて取得し、OR基準文書番号集合に含まれていない文書番号をOR基準文書番号集合に追加する。残りの検索タームも同様に処理する。例えば、
Qor={ 大阪市役所 + 京都市役所 + 東京都庁 }
というOR検索の検索式の場合、予想文書数が、以下のようになったとする。
“大阪市役所” → 1
“京都市役所” → 3
“東京都庁” → 5
【００５４】
このとき、OR検索は、”東京都庁→京都市役所→大阪市役所”の順序で行われる。まず、圧縮全文索引から”東京都庁”の文書番号を取得し、OR基準文書番号集合が{ 1, 2, 3, 4, 5 }となったとする。次に、”京都市役所”をN-gramタームに分割して、各N-gramタームの文書番号リストをAND照合した予想文書番号集合が{ 1, 3, 6 }になったとする。この場合、OR基準文書番号集合が予想文書番号集合をすべて含んでいないため、”京都市役所”の正確な文書番号を圧縮全文索引から取得し、OR基準文書番号集合を更新する。その結果、OR基準文書番号集合が{ 1, 2, 3, 4, 5, 6 }になったとする。最後に、”大阪市役所”の予想文書番号集合が{ 1 }になったとする。この場合、OR基準文書番号集合が予想文書番号集合をすべて含んでいるため、”大阪市役所”の正確な文書番号を圧縮全文索引から取得する処理をスキップすることができる。
【００５５】
次に、圧縮全文索引型検索206について詳細に説明する。圧縮全文索引としてFM-Indexを利用した場合、検索タームの後ろの文字から1文字ずつ検索するが、辞書1241を利用して、検索タームの終端のN-gramタームの検索を省略する。例えば、”京都市役所”というタームの終端の2-gramタームである”役所”が辞書に存在する場合、辞書からヒット区間がわかるため、”所”と”役”の検索を省略することができる。残りの文字列である”京都市”は、辞書から求めた”役所”のヒット区間の続きから”市”、”都”、”京”の順に通常の照合を行う。タームの照合後のヒット区間に対して、文書番号取得処理を実行して、文書番号リストを作成する。
【００５６】
最終的に、圧縮全文索引に対する検索で得られた文書番号リストとN-gramインデックスに対する検索で得られた文書番号リストとを照合して、検索式を満たす検索結果として文書番号集合207を取得する。
【００５７】
図８は、文書の登録処理の処理手順を表すフローチャートである。文書の登録処理は、N-gramインデックス登録部130で実行される。
【００５８】
文書の登録処理は、検索クライアントから検索サーバに登録処理の要求と登録する文書集合を送信する事で開始する。
【００５９】
検索サーバは、検索クライアントから送られてきた登録文書の文字列を、N-gramタームにすべて分割する(S801)。分割する時は、該当するN-gramタームの登録文書上での文字位置の数とすべての文字位置のリストをセットで記録する。
【００６０】
次に、N-gramタームと文字位置集合を、N-gramタームごとに分類する(S802)。分類したN-gramタームごとに、辞書テーブル30に存在するかチェックする(S806)。存在しなければ登録する(S803)。
【００６１】
次に、ターム番号302ごとに、文字位置リスト902の末尾に、記憶してある文字位置の数と文字位置のリストをセットで追加する(S804)。この時、文字位置は昇順で追加する。図９は、ターム番号302に対応する文字位置リストが記録されているテーブルの構成の一例である。
【００６２】
次に、ターム番号302ごとに、文書番号リスト1242の末尾に、文書番号を追加する(S805)。この時、文書番号は、検索サーバの内部で採番した番号を使用して、文書番号リストの中で文書番号が必ず昇順に並ぶようにする。
【００６３】
図５の検索処理に、追加文書がある場合の検索処理を追加したフローチャートを図１０に示す。図５と同一処理の部分については、説明しない。
【００６４】
まず、圧縮全文索引で処理するタームが存在するかどうかをチェックする(S1005)。存在しない場合、N-gramインデックスだけで検索を完了することができる。存在する場合、該当するタームをN-gramタームに分割する(S1006)。その後、N-gramタームに対応する文書番号リストを取得する(S1008)。N-gramタームが残っていない場合は、次に進む(S1007)。
【００６５】
取得した文書番号リストに、隣接判定が必要な文書番号が存在する場合は、N-gramタームに対応する文字位置リストを読み込み、隣接判定を行う(S1009)。
【００６６】
圧縮全文索引は、文書データＤＢ123から文書集合を取り出し、各文書を連結した文字列から構築され、圧縮全文索引ＤＢ125に格納される。また、一定期間経過後に、文書データＤＢ123の文書データを使って、圧縮全文索引ＤＢ125を作り直し、辞書1241を更新することで、N-gramインデックスの文字位置リスト1243を削除することができる。圧縮全文索引の構築処理は、圧縮全文索引構築部131で実行される。
【００６７】
また、N-gramタームにおいて、頻繁に検索されるタームである特定のタームを指定できる。
【符号の説明】
【００６８】
10  検索クライアント
11  ネットワーク
12  検索サーバ
121  ＣＰＵ
122  メモリ
123  文書データＤＢ
124  N-gramインデックスＤＢ
1241  辞書
1242  文書番号リスト
1243  文字位置リスト
125  圧縮全文索引ＤＢ
126  データ通信部
127  N-gramインデックス検索部
128  圧縮全文索引検索式構築部
129  圧縮全文索引検索部
130   N-gramインデックス登録部
131  圧縮全文索引構築部
【図１】
2015056089.tif 000003
【図２】
2015056089.tif 000004
【図３】
2015056089.tif 000005
【図４】
2015056089.tif 000006
【図５】
2015056089.tif 000007
【図６】
2015056089.tif 000008
【図７】
2015056089.tif 000009
【図８】
2015056089.tif 000010
【図９】
2015056089.tif 000011
【図１０】
2015056089.tif 000012