JP5116775B2 - 情報検索方法及び装置及びプログラム及びコンピュータ読取可能な記録媒体 - Google Patents

Description

本発明は、情報検索方法及び装置及びプログラム及びコンピュータ読取可能な記録媒体に係り、大量の文書から文字列によって検索を行うための、全文検索のインデックスを構築するための情報検索方法及び装置及びプログラム及びコンピュータ読取可能な記録媒体に関する。詳しくは、検索条件の文字列が２単語（形態素）以上で構成される場合の情報検索方法及び装置及びプログラム及びコンピュータ読取可能な記録媒体に関する。

大量の文書の中から、検索条件として入力された文字列を含む文書を検索して提示するシステムが実現されている。情報検索装置は、一般的に、情報検索装置の文字列ＤＢに保存される文書情報の中から、検索条件として入力された文字列を含む文書を特定する処理（ルックアップと呼ばれる）と、当該文字列と、当該文字列を含む各文書との類似度（スコアとも呼ばれる）を算出する処理（ランキングと呼ばれる）を行う。そして、情報検索装置は、検索結果として、この類似度が高い順に文書（文書ＩＤでもよい）を表示する。なお、本明細書において、"文書"とは、ある単位の文の集合であり、"文"とは、句点で区切られた単位の文字列である。例えば、１つの文書ファイルは、１つの文書と考えることができる。以下、従来の技術の例をより詳細に説明する。

図１は、従来の情報検索装置１０の構成例を示す。図１において、情報検索装置１０、クライアント２０、及びネットワーク３０が、情報検索システムを構成している。図中の、文字列インデックスDB３は、検索対象となる文書群（本明細書において、"文書"を"文書群"の意味で使用する場合がある）の情報を検索しやすいデータ構造で格納したものであり、本例では、転置インデックスを格納する。従来の転置インデックスは、単語毎に、その単語が出現する文書ＩＤと、その文書の中での当該単語の単語単位での出現位置を有する。また、当該単語の当該文書内での出現頻度を転置インデックスに含めてもよい。

同図に示す情報検索装置１０において、クライアント２０から転送された文字列がクライアント入力受付部１より入力される。入力された文字列は文字列情報検索部２において単語毎に分割される。そして、文字列情報検索部２は、その分割された単語毎に、当該単語が含まれる文書の文書ＩＤとその文書内での単語の出現位置を文字列インデックスDB３から取得する。

さて、検索条件を構成する単語の中には、「東京」と「都」のように、「東京都」という複合語を分割した複数の単語（形態素）が含まれる場合がある。このような複合語では、２つの単語が隣り合って１つの意味を持つものであるから、ルックアップの処理において、２つの単語が検索対象文書の中で隣り合っているかどうかを確認する処理を行うのが一般的である。これを連接処理と呼ぶ。情報検索装置１０における連接処理の具体例は以下のとおりである。

入力された文字列が「東京都」である場合、情報検索装置１０における文字列情報検索部２は、「東京都」を「東京」と「都」に分割する。そして、文字列情報検索部２は、分割して取得された各単語が存在する文書ＩＤと、その出現位置を文字列インデックスDB３から取得する。図２に、取得した情報の例を示す。図２において、「東京」が、文書ID１３３、１４４、１７０の文書に含まれることが示されている。また、文書ID１３３の文書では、「東京」の出現頻度が２で、当該文書中の５番目と２２番目に出現し、文書ID１４４の文書では、出現頻度が３で、文書中の１番目、１１番目、１８番目に出現していることが示されている。「都」についても同様に、出現文書、出現頻度、単語単位の出現位置が示されている。

そして、文字列情報検索部２は、「東京」の次に「都」が出現している文書の有無をチェックし、文書ID１４４の文書において「東京」の次に「都」が出現していることを確認する。これにより、文字列情報検索部２は、「東京都」という複合語が含まれる文書として文書ID１４４を出力することができる。

分割された複数の単語において、どれが複合語を構成する単語であるかは最初は不明であるから、文字列情報検索部２は、検索条件に含まれる単語のいずれかを持つ全ての文書に対して連接処理を行うことになり、大きな処理コストがかかるという問題がある。また、単語単位で位置情報を有する文字列インデックスでは、位置情報が多くのリソースを利用してしまうという問題もある。

上記のようにしてルックアップ処理が終わった後、類似度算出部４は、文字列インデックスDB３から取得から得られた情報を用いて、入力された文字列と、当該文字列が出現する各文書との類似度を算出し、その類似度が高い文書順にその結果をクライアント出力部５に転送する。

文字列と文書との類似度は、例えば、TFIDF(Term Frequency Inverse Document Frequency)を利用して算出される（非特許文献１）。この場合の類似度算出部４を詳細に示すと図３のようになる。図３に示すように、類似度算出部４は、単語重要度（ｉｄｆ）を利用して類似度を算出する単語重要度類似度算出部４１と、単語頻度（ｔｆ）を利用して類似度を算出する単語頻度類似度算出部４２より構成され、この二つの値を乗算した値が文書と単語との類似度になる。検索条件である文字列と、文書との類似度は、当該文字列を構成する全ての単語に関して上記の類似度を算出し、これら類似度の和を求めることにより得られる。

上記の式がその計算方法を示す。sim（Ｑ，ｄ）が検索条件Ｑと文書ｄの類似度を表す関数であり、ｗ_ｄｉが検索条件Ｑを構成する単語ｗのスコアで、そのスコアは単語ｗのｔｆ（単語ｗの文書ｄ上の出現回数）とｉｄｆ（ｗが出現する文書数／全文書数）から算出される。ここでは、単語の位置情報を利用することなく、類似度を算出している。

また、連接をみて類似度を算出する場合は、例えば、「東京都」というｑ１"東京"とｑ２"都"という２単語から構成される複合語が入力となった場合、２つの類似度算出方法がある。そのまま、ｑ１、ｑ２をｗ１、ｗ２とみなしてＴＦＩＤＦを計算する方法と、ｑ１とｑ２が連接している複合語を１つの単語ｗと見做して、類似度を計算する方法する方法がある。前者は、位置情報を無視し、後者は連接している場合をスコア１、連接していない場合をスコア０として、位置情報を利用しているだけである。また、従来技術では、複数の単語が入力となった場合でも、その単語の出現位置情報を考慮しない。

文字列と文書との類似度算出方法としては、BM２５と呼ばれる方法もある（非特許文献２）。しかし、この方法でもＴＦＩＤＦと同様に、文字列が複数の単語を含む場合に、各単語の文中での出現位置情報を考慮せずに類似度を算出している。

また、英語を対象として、入力された語が複数の場合に、その複数の単語が近傍に出現すること（以下、近接）を考慮して類似度を算出する方法もある（例えば、非特許文献３参照）。
Gerard Salton and Chris Buckley, Term Weighting Approaches in Automatic Text Retrieval, Information Processing and Management: an International Journal, Pages: 513-523 Vol.24, Issue 5, 1988. Stephen E. Robertson, Steve Walker, Micheline Hancock-Beaulieu, Asrron Gull, and Marianna Lau. Okapi at TREC3. In text Retrieval Conference, pages 21-30, 1992. Tao Tao and ChengXiang Zhai. An exploration of proximity measures in information retrieval. In SIGIR '07: Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, pp.295-302. New York, NY, USA, 2007. ACM Press.

上述したように、単語単位で位置情報を有する文字列インデックス（転置インデックス）では、位置情報の量が多いとともに、連接処理に大きな処理コストがかかるという問題がある。

また、非特許文献１及び非特許文献２に記載されている類似度算出方法では、入力された文字列が複数単語（もしくは形態素）で構成されたとしても、入力された文字列が出現する位置とは無関係に類似度算出を行うため、情報検索装置の精度が低いという問題があった。

また、非特許文献３に記載された類似度算出方法では、入力された単語が複数の場合に、その複数の単語が近傍に出現すること（近接）を考慮した類似度の算出を提案しているが、一つの単語が複数の形態素で構成されていることは想定されていない。

本発明は、上記の点に鑑みなされたもので、従来の問題を解消するための文字列インデックスを提供するとともに、近接している情報を利用した類似度の算出を文書全体に対して行うことで、検索精度を高め、また、計算コスト削減が実現可能な情報検索方法及び装置及びプログラム及びコンピュータ読取可能な記録媒体を提供することを目的とする。

上記の課題を解決するために、本発明は、クライアントからの文字列を取得する文字列入力手段と、該文字列が含まれる情報をインデックスＤＢから取得する文字列情報検索手段と、該文字列と検索された情報との類似度を算出する類似度算出手段と、類似度の高い順に検索された情報を出力する出力手段と、を有する情報検索装置であって、前記文字列情報検索手段は、入力された前記文字列が複数の単語からなる場合に、各単語に基づいて、単語及び該単語の文書中における文単位での出現位置を格納したインデックスＤＢを検索し、各単語を含む文書ｄと当該文書ｄでの各単語の出現位置を取得し、
文字列を分割して得た単語の集合をＱとし、Ｐｏｓ _ｄ （ｑ _ｉ ）を文書ｄ中の単語ｑ _ｉ の出現位置とし、Ｐｏｓ _ｄｋ （ｑ _ｊ ）を文書ｄ中の単語ｑ _ｊ の出現位置からｋ減算した値とし、ｋを所定のカウンタ値とし、αを所定の係数とし、Count(Pos,Pos)を、２つの位置データが与えられた時に、その一致度を返す関数とした場合に、
前記類似度算出手段は、単語の出現位置間の一致度score(Q,d,k)を

により算出し、当該一致度score(Q,d,k)に基づいて類似度を算出することを特徴とする情報検索装置として構成される。

また、本発明は、クライアントからの文字列を取得する文字列入力手段と、該文字列が含まれる文書に関する情報を、単語毎に文書における文単位の単語出現位置情報を格納したインデックスＤＢから取得する文字列情報検索手段と、該文字列と文書との類似度を算出する類似度算出手段と、類似度の高い順に検索された文書の情報を出力する出力手段と、を有する情報検索装置であって、前記文字列情報検索手段は、入力された前記文字列が複数の単語からなる場合に、各単語に基づいて、前記インデックスＤＢを検索することにより、各単語の文単位の出現位置情報を文書毎に取得する手段を含み、前記類似度算出手段は、各文書における前記複数の単語の文単位での共起の度合いに基づいて、各文書と前記文字列との類似度を算出する手段を含むことを特徴とする情報検索装置として構成することもできる。

上記の情報検索装置において、前記類似度算出手段は、ある文書において、前記複数の単語が共起する文の数を、当該文書における前記共起の度合いとして求めることとしてもよい。

また、本発明は、上記情報検索装置が実行する処理方法としての情報検索方法としても構成できる。更に、本発明は、上記情報検索装置を構成する各手段としてコンピュータを機能させる情報検索プログラム、及び、当該情報検索プログラムを格納したコンピュータ読取可能な記録媒体として構成することもできる。

上記のように本発明によれば、２単語以上（もしくは２形態素以上で構成される１単語）を検索条件として検索を要求された場合に、単語の出現位置情報を用いることにより、その２単語が近傍に出現すること、あるいは、その２単語が文中で共起することを考慮した類似度を算出できる。これにより、検索精度を向上させる可能性がある。また、その出現位置をビットで格納し、ビット演算のみで実現することにより低コストで類似度を算出することができる。

また、連接処理を行わずに、単語の近接の度合い（距離）あるいは単語の共起の度合いにより類似度を算出することにより、処理コストが連接処理を行う従来技術より低減する。また、再現率が従来技術に比べて向上する。更に、区切られた区間として、単語単位の位置情報ではなく、文単位の位置情報を用いて文字列インデックスを構成することにより、単語単位の位置情報を用いている従来の文字列インデックスに比べて情報量を削減できる。

情報検索システムの構成図である。 従来の文字列インデックスDBから取得した情報の例を示す図である。 類似度算出部４を示す図である。 本発明の実施の形態に係る情報検索装置の概要構成例を示す図である。 本発明の実施の形態に係る情報検索方法の概要を説明するための図である。 本発明の実施の形態に係るシステム構成図である。 本発明の第１の実施の形態における類似度算出部４'の構成図である。 本発明の第１の実施の形態における情報処理装置１０の一連の動作のフローチャートである。 本発明の第１の実施の形態における位置近接情報を利用した類似度算出処理のフローチャートである。 本発明の第１の実施の形態における文字列インデックスＤＢ３'に格納されるデータの構造例を示す図である。 本発明の第１の実施の形態における文字列インデックスＤＢ３'のビット列による位置情報の格納例である。 ビットマップを利用した位置情報を用いる場合の近接計算を説明するための図である。 文内共起回数を説明するための図である。 本発明の第２の実施の形態における情報検索装置１０の構成図である。 本発明の第２の実施の形態における近接を考慮しない単語が入力された場合を示す図である。 本発明の第３の実施の形態における情報検索装置１０の構成図である。 本発明の第３の実施の形態における文単位で位置情報を持った場合の連接実現方法を説明するための図である。

符号の説明

１ クライアント入力受付部、文字列入力手段
２ 文字列情報検索部、文字列情報検索手段
３，３' 文字列インデックスＤＢ
４，４' 類似度算出部、類似度算出手段
５ クライアント出力部、出力手段
６ 文字列選択部
１０ 情報検索装置
１２ 近接未考慮単語リスト記憶部
１４ 文書保存ＤＢ
２０ クライアント
３０ ネットワーク
４１ 単語重要度類似度算出部
４２ 単語頻度類似度算出部
４３ 単語位置類似度算出部

以下、図面と共に本発明の実施の形態を説明する。まず、本発明の実施の形態の概要例を図４、図５を参照して説明する。

図４は、本実施の形態に係る情報検索装置の概要構成例を示す図である。図４に示すように、この情報検索装置は、クライアントからの文字列を取得する文字列入力手段１と、該文字列が含まれる情報をＤＢから取得する文字列情報検索手段２と、該文字列と検索された情報との類似度を算出する類似度算出手段４と、類似度の高い順に検索された情報を出力する出力手段５と、を有する情報検索装置であって、文字列情報検索手段２は、入力された文字列が複数の単語からなる場合に、各単語に基づいて、単語及び該単語の出現位置情報を格納したインデックスＤＢ３'を検索し、該単語の出現位置間の距離を求める手段を含み、類似度算出手段４は、単語の出現位置間の距離に基づいて類似度を算出する手段を含む。

また、インデックスＤＢ３'が、単語と該単語の文中の出現位置情報を文単位で集約した情報を保持し、出現位置情報をビット列で表現し、文字情報検索手段２において、インデックスＤＢ３を検索し、ビット列による単語の出現位置情報を取得する手段を含み、類似度算出手段４において、インデックスＤＢ３'の出現位置情報のビット列を用いてビットの論理演算により類似度を求める手段を含むこととしてもよい。

また、前記情報検索装置において、入力された前記文字列が複数の単語からなる場合に、該単語に基づいて、近接を考慮しない単語が登録されている近接未考慮単語リスト記憶手段を参照して、該単語が該近接未考慮単語リスト記憶手段に存在する場合は近接を考慮しない単語と判断する文字列選択手段を更に有し、文字列情報検索手段２において、文字列選択手段において、近接を考慮しない単語であると判断された単語については、全ての文に該単語が存在することとしてインデックスＤＢ３を検索する手段を含むこととしてもよい。

また、前記情報検索装置において、文字列情報検索手段２が、インデックスＤＢ３に文単位で文番号及び出現位置情報が格納されている場合には、入力された文字列から得られた単語に基づいて、該インデックスＤＢ３を検索し、得られた文番号を、文書が保存されている文書保存ＤＢから検索し、該入力された文字列が存在している場合のみ検索結果を前記類似度算出手段に出力する連接確認手段を更に有することとしてもよい。

図５は、本発明の実施の形態に係る情報検索方法の概要を説明するための図である。当該情報検索方法は、クライアントからの文字列を取得し、該文字列が含まれる情報をＤＢから取得し、該文字列と検索された情報との類似度を算出し、類似度の高い順に検索された情報を出力する（ステップ３）装置における情報検索方法であって、文字列情報検索手段が、入力された文字列が複数の単語からなる場合に、各単語に基づいて、単語及び該単語の出現位置情報を格納したインデックスＤＢを検索し、該単語の出現位置間の距離を求める文字列情報検索ステップ（ステップ１）と、類似度算出手段が、単語の出現位置間の距離に基づいて類似度を算出するステップ（ステップ２）と、有する。

また、前記情報検索方法において、インデックスＤＢが、単語と該単語の文中の出現位置情報を文単位で集約した情報を保持し、該出現位置情報をビット列で表現されている場合に、文字列情報検索ステップにおいて、インデックスＤＢを検索し、ビット列による単語の出現位置情報を取得し、類似度算出ステップにおいて、インデックスＤＢの出現位置情報のビット列を用いてビットの論理演算により類似度を求めることとしてもよい。

また、前記情報検索方法において、入力された前記文字列が複数の単語からなる場合に、該単語に基づいて、近接を考慮しない単語が登録されている近接未考慮単語リスト記憶手段を参照して、該単語が該近接未考慮単語リスト記憶手段に存在する場合は近接を考慮しない単語と判断する文字列選択ステップを更に行い、文字列情報検索ステップにおいて、文字列選択ステップで近接を考慮しない単語であると判断された単語については、全ての文に該単語が存在することとして前記インデックスＤＢを検索することとしてもよい。

また、前記情報検索方法における文字列情報検索ステップにおいて、インデックスＤＢに文単位で文番号及び出現位置情報が格納されている場合には、入力された文字列から得られた単語に基づいて、該インデックスＤＢを検索し、得られた文番号を、文書が保存されている文書保存ＤＢから検索し、該入力された文字列が存在している場合のみ検索結果を前記類似度算出手段に出力することとしてもよい。

本実施の形態において、情報検索装置を構成する各手段としてコンピュータを機能させる情報検索プログラムを提供することができる。また、この情報検索プログラムを格納したコンピュータ読取可能な記録媒体を提供することもできる。

以下、本発明の各実施の形態を詳細に説明する。

本発明の実施の形態では、インターネットのＷｅｂサーバ上で動作する情報検索プログラムが、ハードディスクなどの記録媒体に保存され、当該Ｗｅｂサーバ上で実行させることを想定している。よって、クライアント側はネットワークを介してＷｅｂブラウザ等を利用し、当該情報検索装置にアクセスし、クライアント入力受付部、及び出力部を通して情報を検索する。この方法は、スタンドアロンの形態のシステムにも適用することが可能である。

本発明の実施の形態に係るシステム構成を図６に示す。図６に示すとおり、本発明の実施の形態のシステムは、クライアント２０、ネットワーク３０、及び情報検索装置１０を有する。情報検索装置１０は、クライアント入力受付部１、文字列情報検索部２、文字列インデックスＤＢ３'、類似度算出部４'、クライアント出力部５から構成される。その構成は、前述の図１とほぼ同様であるが、文字列インデックスＤＢ３'及び類似度算出部４'の構成は、図１に示した文字列インデックスＤＢ３及び類似度算出部４と異なる。

図６の構成において、情報検索装置１０には、クライアント２０からネットワーク３０を介してクライアント入力受付部１に文字列が入力される。クライアント入力受付部１から文字列が文字列情報検索部２に転送されると、文字列は単語毎に分割される。文字列情報検索部２は、その分割された各単語が含まれる文書とその文書内の単語の出現位置を文字列インデックスＤＢ３'から取得し、それらを類似度算出部４'に転送する。類似度算出部４'は、取得された単語と単語の出現位置に基づいて、文字列と各文書との類似度を計算する。なお、図６に示す構成における機能分担は、以下に説明するものに限られるわけではない。例えば、文字列情報検索部２が、類似度算出部４'における処理の一部（近接の度合いの計算、共起の度合いの計算等）を行うこととしてもよい。

類似度算出部４'は、転送された文字列が単一の単語の場合は、その単語と、その単語が出現する文書との類似度を例えば、前述の非特許文献１の方法で算出し、その類似度が高い文書順に文書ＩＤを出力する。なお、文書ＩＤから、別のデータベースを検索して、文書そのものを出力してもよい。その単語が複数の単語で構成されている場合は、類似度算出部４'は、その複数の単語がどの程度近接しているのかを考慮して、文字列と文書との類似度を算出し、その結果として、類似度が高い文書順に文書ＩＤ等をクライアント出力部５に転送する。

図７は、本発明の第１の実施の形態における類似度算出部４'の構成を示す。

同図に示す類似度算出部４'は、従来技術と比較して、単語重要度類似度算出部４１、単語頻度類似度算出部４２に加え、単語位置類似度算出部４３が追加されている。この単語位置類似度算出部４３は、近接情報又は共起情報を利用した類似度を算出する。

次に、本発明の実施の形態に係る一連の処理について説明する。

図８は、本発明の第１の実施の形態における情報処理装置１０の一連の動作のフローチャートである。

ステップ１０１） クライアント入力受付部１より文字列が入力されると、文字列情報検索部２は、入力された文字列を単語毎に分割する。例えば、"東京都"という文字列が入力されると、形態素解析処理を利用して単語毎に分割する。単語毎に分割すると、一般的に"東京"及び"都"という文字列に分割される。

ステップ１０２） 文字列情報検索部２は、文字列が２単語以上で構成されるかをチェックする。２単語以上である場合はステップ１０３に移行し、単一単語である場合は、ステップ１０５に移行する。

ステップ１０３） 文字列情報検索部２は、文字列インデックスＤＢ３'を検索して、分割された単語毎に、分割された単語を持つ文書と単語出現位置を取得する。

ステップ１０４） 類似度算出部４'は、近接情報を利用して類似度を算出し、ステップ１０７に移行する。なお、近接情報を利用した類似度の算出方法については後述する。

ステップ１０５） 類似度算出部４'は、文字列インデックスＤＢ３'から入力文字列である単一の単語を持つ文書と単語出現頻度を取得する。

ステップ１０６） 類似度算出部４'は、１単語の場合の単語の重要度は全ての文書で共通であるので、単語頻度類似度算出部４２において単語の頻度のみで、当該単語と、当該単語が出現する各文書との類似度を算出する。

ステップ１０７） 上記のステップ１０２において、入力文字列が２単語以上である場合は、類似度算出部４'は、近接情報を利用した検索結果（例えば、文書ＩＤ）を類似度順（例えば類似度の高い順）に並べ、クライアント出力部５に転送する。ステップ１０２において、入力文字列が単一単語の場合には、類似度算出部４'は、単語頻度情報を用いて算出された類似度順に検索結果をソートしてクライアント出力部５に転送する。これにより、クライアント出力部５は、検索結果をクライアント２０に提示する。

次に、上記のステップ１０４における位置近接情報を利用した類似度算出方法について説明する。

図９は、本発明の第１の実施の形態における位置近接情報を利用した類似度算出処理のフローチャートである。

ステップ２０１） 類似度算出部４'の単語位置類似度算出部４３において、文字列から分割して得られた各単語を含む文書の文書ＩＤとその文書ＩＤでの各単語の出現位置を取得する。その情報は、文字列情報検索部２が文字列インデックスDB3'から取得した情報から取得できる。

ここで、本実施の形態における文字列インデックスＤＢ３'に格納されるデータの構造例を図１０に示す。図１０の例では、単語毎に、単語とその単語が出現する文書ＩＤが保存され、更に、文書ＩＤ毎に、当該単語の出現位置データが保存されている。また、本実施の形態における単語の出現位置は、文単位の出現位置である。

例えば、word１が"東京"という文字列である場合、"東京"はｉｄ１という文書に存在し、その出現位置は、ｉｄ１という文書の中の１文目、３文目、４文目、及び８文目であることを示している。また、その構造をbitmapで持たせた例を図１１に示す。図１０では文単位の出現位置が数値で示されていたのに対し、図１１ではbitmapで表現されている。例えば、word１のｉｄ１の文書に関する"００１０"は、３文目に単語word１が存在することを示している。本発明の実施の形態では、単語の位置情報を文単位としたが、必ずしもこれに限定されることはなく、ある区切られた区間毎の単位であればよい。例えば、この位置情報を単語単位の出現位置や、段落単位の出現位置などに変更しても同様の近接に基づく類似度算出処理が可能である。

入力された文字列を分割して得られた単語が「東京」と「都」であった場合、ステップ２０１の処理において、単語位置類似度算出部４３は、「東京」と「都」の両方を含む文書の文書ＩＤと、その文書内での「東京」の文単位での出現位置、及び、その文書内での「都」の文単位での出現位置を取得することになる。例えば、図１０の例において、ｗｏｒｄ１が「東京」であり、ｗｏｒｄ２が「都」であるとすれば、ステップ２０１において、単語位置類似度算出部４３は、「東京」に対して、文書ＩＤ１と、その中の出現位置（１文目、３文目、４文目、８文目）、及び、「都」に対して、文書ＩＤ１と、その中の出現位置（１文目、５文目、６文目、８文目）を取得することになる。

この例において、以下では、単語位置類似度算出部４３は、文書ＩＤ１の文書内で、「東京」の文単位での出現位置と「都」の文単位での出現位置とがどの程度近接しているかを示すスコアを算出し、そのスコアを、入力文字列（「東京都」）と文書ＩＤ１の文書との類似度とする処理を行う。

ステップ２０２） 単語位置類似度算出部４３は、カウンタｋ＝０、及び、ｎをセットする。ｎとは、前後何文までの近接を見るかを指定するための数値である。例えば、ｎ＝１だとすると、隣り合う文のみに着目して近接類似度を求めることになる。逆にある文書がｍ文で構成され、そのｍをｎにセットすると文書全体での近接類似度を算出することができる。

ステップ２０３） 単語位置類似度算出部４３は、ｋの値がｎ以下かどうかをチェックする。ｎ以下の場合は、ステップ２０４に移行し、ｎより大きい場合はステップ２０７に移行する。

ステップ２０４〜２０５） 単語位置類似度算出部４３は、ステップ２０１で得られた出現位置群のペアのうちの一方の出現位置を文単位でｋだけずらし（例えば、減算し）て得られた出現位置と、他方の出現位置との一致度 score(Q,d,k) を算出する。一致度score(Q,d,k)は例えば、下記に示される式で算出される。

上記の式において、Ｑはクエリ集合（文字列を分割して得た単語の集合）、ｄは文書、Ｐｏｓ_ｄ（ｑ_ｉ）は、文書ｄ中のｑ_ｉ（単語、例えば上記の例の「東京」）の出現位置を示し、Ｐｏｓ_ｄｋ（ｑ_ｊ）は文書ｄ中のｑ_ｊ（単語、例えば上記の例の「都」）の出現位置からｋ減算した列を表す。例えば、図１０のｗｏｒｄ２が「都」である例において、ｋが０の場合、Ｐｏｓ_ｄｋ（ｑ_ｊ）は（１、５、６、８）である。また、この例において、ｋが１の場合、Ｐｏｓ_ｄｋ（ｑ_ｊ）は（０、４、５、７）である。

Count(Pos,Pos)は、２つのポジションデータが与えられた時に、その一致度を返す関数で、例えば、入力がｋ＝０だった場合は、同一文に単語ｑ_ｉとｑ_ｉ以外の単語であるｑ_ｊが出現する回数の合計を出力する。また、ｋ＝１の場合、Count(Pos,Pos)は、隣り合う文に単語ｑ_ｉと単語ｑ_ｊが出現する回数の合計を出力する。

例えば、単語ｑ_ｉが上記の例の「東京」であり、ｑ_ｉ以外の単語ｑ_ｊが上記の例の「都」であるとすると、ｋ＝０の場合において、Ｐｏｓ_ｄ（ｑ_ｉ）は（１、３、４、８）であり、Ｐｏｓ_ｄｋ（ｑ_ｊ）は、（１、５、６、８）であるから、Countは２を返す。つまり、これは、対象の文書において、「東京」と「都」が同一文に出現する回数が２回（文１と文８）であることを示す。

αは係数であり、例えば１である。１／(αｋ＋１）によってより近い位置の文に各単語が存在する場合に大きなスコアが算出される。

ステップ２０６） 単語位置類似度算出部４３は、ｋの値を１インクリメントし、ステップ２０３に戻る。

ステップ２０７） 単語位置類似度算出部４３は、各ｋの値で算出されたscoreの値の合計値を入力文字列と文書との類似度として出力する。これが単語の位置情報を考慮した類似度となる。より詳細には、これは近接の度合いを考慮した類似度である。これは、以下の式で算出される。

図１１に示すビットマップを利用した位置情報を用いる場合は、Ｐｏｓ_ｄとＰｏｓ_ｄｋをｋビットシフトした情報で論理積をとり、その論理積をとった結果のビットから１の数をカウントするだけでcountを計算することができる。図１２は、ビットマップを利用した位置情報を用いる場合の近接計算を説明するための図であり、Ｑ（word_2,word_1），ｄ＝１，ｋ＝１が入力になったときのスコアの算出例を示している。まず、文字列情報検索部２は、word1とword2の位置情報を文字列インデックスDB3'（図１１に示す構成）から取得する。類似度算出部４'は、その取得した位置情報からword_1の位置情報を１ビットシフトし、word_2の位置情報と論理積をとる。その論理積の結果のビット位置が隣の１文にword1とword2が存在した位置である。この例の場合、立っているビットが２ビット目の一つだけなので、scoreは"１"である。このビット列から１の数を数える方法としては、例えば、Intel CPUのSSE4命令POPCNTで高速に求める方法がある。

検索条件である文字列と、文書との類似度の算出方法の他の例を次に説明する。この例では、下記の数式を用いて類似度（スコア）を算出する。

上記の式（１）は、文字列（クエリ）ｑの集合Qと文書ｄとの類似度ｓｃｏｒｅが、クエリ毎の類似度ｗ_ｄ（ｑ）の和であることを示し、式（２）は、クエリｑが、形態素ｔの集合Ｔ_ｑから構成されることを示す。式（３）は、類似度ｗ_ｄ（ｑ）が、形態素毎の類似度ｗ_ｄ（ｔ）の和であることを示す。類似度ｗ_ｄ（ｔ）は、式（４）により求められる。

この式（４）は、非特許文献２に示されているＢＭ２５で用いられる下記の式

における、ｔｆ（ｔ，ｄ）（形態素ｔの文書ｄにおける出現頻度）を、ｃｏｏｃｃ（Ｔ_ｑ，ｄ）に置き換えたものに相当する。それ以外のパラメータについては、ＢＭ２５におけるパラメータと同様である。Ｎは全文書数を示す。ｄｆ（ｔ）は、ｔを含む文書数であり、ｋ_１は係数である。Ｋは、ｋ_１と文書長等から求められる値である。

ｃｏｏｃｃ（Ｔ_ｑ，ｄ）は、Ｔ_ｑの文書ｄにおける文内共起回数である。例えば、Ｔ_ｑが、「東京」と「都」である場合において、類似度算出にあたり、類似度算出部４'は、ぞれぞれの単語についての文書ＩＤ、出現頻度、文単位位置情報として、図１３に示す情報を、文字列インデックスＤＢ３'から、又は、文字列情報検索部２から取得する。この例では、文字列インデックスＤＢ３'は、文書ＩＤと、文単位の単語出現位置情報とともに、単語の出現頻度を有する。この出現頻度は、ある文に該当の単語が存在すれば、それが２回以上同じ文に出現する場合でも、１加算されるものである。

図１３に示す情報を取得した類似度算出部４'は、文単位の位置情報に基づき、文１、文３４、文５２において、「東京」と「都」が共起していることを検知し、ｃｏｏｃｃ（Ｔ_ｑ，ｄ）（この場合、Ｔ_ｑは「東京」と「都」、ｄは１３３）を３とする。そして、上記の式（４）、式（３）を用いて、文書１３３についての、"東京都"に対する類似度を求めることができる。

なお、上記の例では、ＢＭ２５の式の一部を文内共起回数ｃｏｏｃｃ（Ｔ_ｑ，ｄ）に置き換えた式を用いて類似度を算出しているが、ＢＭ２５の式に基づくことは必ずしも必須ではない。文内共起回数ｃｏｏｃｃ（Ｔ_ｑ，ｄ）を用いるのであれば、他の式を用いてもよい。また、例えば、文内共起回数ｃｏｏｃｃ（Ｔ_ｑ，ｄ）そのものを類似度とすることも考えられる。

上記のように、本実施の形態では、連接処理を行わずに、区切られた区間（上記の例では文）単位での単語の近接の度合いあるいは単語の共起の度合いにより類似度を算出しているため、処理コストが連接処理を行う従来技術より低減する。また、再現率が従来技術に比べて向上する。更に、区切られた区間として、単語単位の位置情報ではなく、文単位の位置情報を用いて文字列インデックスＤＢ３'を構成することにより、単語単位の位置情報を用いている従来の文字列インデックスＤＢに比べて情報量を削減できる。

［第２の実施の形態］
上記で入力された文字列が２単語（形態素）以上であった時に、近接していることを利用した類似度の算出方法を説明した。しかしながら、必ずしも近接していることが精度向上に繋がるとは言えない。例えば、"レストラン名 電話番号"という文字列が検索条件として入力された場合、"レストラン名 電話番号"を探しているわけではなく、あるレストランのページで「電話番号」という文字列が存在しているページを提示するだけでよい可能性がある。そこで、本実施の形態では、その検索条件として入力された単語が、近接を考慮するか否かを判断する。

図１４は、本発明の第２の実施の形態における情報検索装置１０の構成を示す。同図において、図６と同一構成部分については同一符号を付し、その説明を省略する。

同図に示す情報検索装置１０は、図６の情報検索装置１０に文字列選択部６と、近接未考慮単語リスト記憶部１２が付加された構成である。近接未考慮単語リスト記憶部１２は、近接を考慮しない単語が登録されている。

文字列選択部６は、検索条件として入力された単語に基づいて、近接未考慮単語リスト記憶部１２を参照して、当該単語が近接未考慮単語リスト記憶部１２に存在する場合には、近接を考慮しない単語であると判定する。文字列情報検索部２は、文字列選択部６において近接を考慮しない単語であると判断された場合には、全ての位置にその単語が存在することとして近接処理を行う。図１５は、本発明の第２の実施の形態における近接を考慮しない単語が入力された場合を示す。同図に示すword_1が近接を考慮しない単語の例で、その出現位置は"００１０"である。本実施の形態では、当該単語の出現位置を全ての文に存在する"１１１１"に変換し、類似度算出部４'による類似度算出処理を行う。類似度算出部４'による処理は、前述の第１の実施の形態での処理と同様である。

近接未考慮単語の出現位置を"１１１１"に変換することにより、当該単語の出現位置は類似度のスコアに寄与しなくなる。

［第３の実施の形態］
入力された文字列が２単語で構成される場合に、文単位の単語出現位置情報のみを用いた近接処理では、複合語を判別できないので、検索精度が低下する恐れがある。そこで、本実施の形態では、２単語で構成される語の連接処理を単語出現位置情報が文単位で保存されている場合に実現する方法を説明する。

図１６は、本発明の第３の実施の形態における情報検索装置１０の構成を示す。

同図に示す情報検索装置は、図６の構成に文書保存ＤＢ１４が追加された構成である。また、文字列インデックスＤＢ３'は、単語に対して、単語単位ではなく、文書ＩＤと文単位の位置情報を保持している。

図１７は、本発明の第３の実施の形態における文単位で位置情報を持った場合の、連接実現方法を説明するための図である。

同図に示すように、文字列インデックスＤＢ３'には、単語毎に、当該単語が存在する文書ＩＤ（ＤＯＣ＿ＩＤ）とビットで表された文単位の単語出現位置情報が格納されている。これにより、文字列情報検索部２は、入力された文字列を形態素解析し、当該文字列が２単語以上である場合には、文字列インデックスＤＢ３'から当該単語を持つ文書ＩＤと、単語の出現位置を取得し、位置情報の論理積をとることにより文内共起の有無を調べる。

そして、該当の単語が文内共起している文がある場合に、文字列情報検索部２は、文書ＩＤ及び文番号に基づいて文書保存ＤＢ１４を検索し、対応する文を取得し、その文の中に、上記複数単語が連接した複合語があるかどうかを調べる。そして、複合語があれば、その複合語を含む文書を検索結果として出力できる。

また、本例でも、類似度算出部４の単語位置類似度算出部４３は、第１の実施の形態と同様にして、文字列情報検索部２から取得した２つの単語に対応する文書の近接情報（位置情報）に基づいて、類似度を算出してよいが、上記のように複合語が検知された文書にスコアを加算することとしてもよい。また、単語位置類似度算出部４３は、複合語が検知された文書のみについて類似度を算出し、類似度の高い順に検索結果をクライアント出力部５に出力することとしてもよい。

例えば、検索クエリとして"東京都"という文字列が入力された場合、まず、"東京"と"都"が存在する文が特定される。これは、今までの文単位での位置情報による近接処理と同等である。図１７の例では、文書１における２番目の文、及び、文書２における１番目の文が、それぞれ"東京"と"都"を含む。特定された文書ＩＤと文番号を文書保存ＤＢ１４から参照し、"東京都"という文字列が存在するか否かが調査される。この処理は文の前方から全てスキャンすることにより行うことができる。この結果、文字列情報検索部２は、当該文字列が存在した文書のみ（連接語が存在している文書のみ）を類似度算出部４'に出力し、類似度算出部４'は類似度を算出し、クライアント出力部より検索結果を提示することができる。

また、上記の実施の形態における情報検索装置の構成要素の各動作をプログラムとして構築し、情報検索装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。

さらに、構築されたプログラムをハードディスクや、フレキシブルディスク・ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールする、または、配布することが可能である。

なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。

本発明は、データベース等の大量の文書から入力された文字列を用いて所望の情報を取得する情報検索に適用可能である。

本国際出願は、２００７年１１月１９日に出願された日本国特許出願第２００７−２９９７８４号に基づく優先権を主張するものであり、その全内容を本国際出願に援用する。

Claims (12)

1. クライアントからの文字列を取得する文字列入力手段と、該文字列が含まれる情報をインデックスＤＢから取得する文字列情報検索手段と、該文字列と検索された情報との類似度を算出する類似度算出手段と、類似度の高い順に検索された情報を出力する出力手段と、を有する情報検索装置であって、
   前記文字列情報検索手段は、
   入力された前記文字列が複数の単語からなる場合に、各単語に基づいて、単語及び該単語の文書中における文単位での出現位置を格納したインデックスＤＢを検索し、各単語を含む文書ｄと当該文書ｄでの各単語の出現位置を取得し、
   文字列を分割して得た単語の集合をＱとし、Ｐｏｓ _ｄ （ｑ _ｉ ）を文書ｄ中の単語ｑ _ｉ の出現位置とし、Ｐｏｓ _ｄｋ （ｑ _ｊ ）を文書ｄ中の単語ｑ _ｊ の出現位置からｋ減算した値とし、ｋを所定のカウンタ値とし、αを所定の係数とし、Count(Pos,Pos)を、２つの位置データが与えられた時に、その一致度を返す関数とした場合に、
   前記類似度算出手段は、
   単語の出現位置間の一致度score(Q,d,k)を
   

   

   により算出し、当該一致度score(Q,d,k)に基づいて類似度を算出することを特徴とする情報検索装置。
2. ｎを０以上の定数としたときに、前記類似度算出手段は、
   

   

   により、前記文字列と文書ｄとの類似度ｓｉｍ（Ｑ，ｄ）を算出する
   ことを特徴とする請求項１に記載の情報検索装置。
3. 前記インデックスＤＢは、
   各単語の出現位置をビット列で表現し、
   前記文字列情報検索手段は、
   前記インデックスＤＢを検索し、前記ビット列による単語の出現位置を取得する手段を含み、
   前記類似度算出手段は、
   前記インデックスＤＢの前記出現位置のビット列を用いてビットの論理演算により類似度を求める手段を含む請求項１又は２に記載の情報検索装置。
4. 前記入力された前記文字列が複数の単語からなる場合に、該単語に基づいて、近接を考慮しない単語が登録されている近接未考慮単語リスト記憶手段を参照して、該単語が該近接未考慮単語リスト記憶手段に存在する場合は近接を考慮しない単語と判断する文字列選択手段を更に有し、
   前記文字列情報検索手段は、
   前記文字列選択手段において、近接を考慮しない単語であると判断された単語については、全ての文に該単語が存在することとして前記インデックスＤＢを検索する手段を含む請求項１又は２に記載の情報検索装置。
5. 前記文字列情報検索手段は、
   前記入力された文字列から得られた複数の単語に基づいて、前記インデックスＤＢを検索し、当該複数の単語が存在する文のＩＤを検出し、文書保存ＤＢから当該ＩＤに対応する文を検索し、当該文に該入力された文字列が存在している場合のみ検索結果を前記類似度算出手段に出力する連接確認手段を更に有する請求項１又は２に記載の情報検索装置。
6. クライアントからの文字列を取得し、該文字列が含まれる情報をインデックスＤＢから取得し、該文字列と検索された情報との類似度を算出し、類似度の高い順に検索された情報を出力する装置における情報検索方法であって、
   文字列情報検索手段が、入力された前記文字列が複数の単語からなる場合に、各単語に基づいて、単語及び該単語の文書中における文単位での出現位置を格納したインデックスＤＢを検索し、各単語を含む文書ｄと当該文書ｄでの各単語の出現位置を取得する文字列情報検索ステップと、
   文字列を分割して得た単語の集合をＱとし、Ｐｏｓ _ｄ （ｑ _ｉ ）を文書ｄ中の単語ｑ _ｉ の出現位置とし、Ｐｏｓ _ｄｋ （ｑ _ｊ ）を文書ｄ中の単語ｑ _ｊ の出現位置からｋ減算した値とし、ｋを所定のカウンタ値とし、αを所定の係数とし、Count(Pos,Pos)を、２つの位置データが与えられた時に、その一致度を返す関数とした場合に、類似度算出手段が、単語の出現位置間の一致度score(Q,d,k)を
   

   

   により算出し、当該一致度score(Q,d,k)に基づいて類似度を算出する類似度算出ステップと、
   を有することを特徴とする情報検索方法。
7. ｎを０以上の定数としたときに、前記類似度算出手段は、
   

   

   により、前記文字列と文書ｄとの類似度ｓｉｍ（Ｑ，ｄ）を算出する
   ことを特徴とする請求項６に記載の情報検索方法。
8. 前記インデックスＤＢは、
   各単語の出現位置をビット列で表現し、
   前記文字列情報検索ステップにおいて、
   前記文字列情報検索手段は、前記インデックスＤＢを検索し、前記ビット列による単語の出現位置を取得し、
   前記類似度算出ステップにおいて、
   前記類似度算出手段は、前記インデックスＤＢの前記出現位置のビット列を用いてビットの論理演算により類似度を求める請求項６又は７に記載の情報検索方法。
9. 前記入力された前記文字列が複数の単語からなる場合に、該単語に基づいて、近接を考慮しない単語が登録されている近接未考慮単語リスト記憶手段を参照して、該単語が該近接未考慮単語リスト記憶手段に存在する場合は近接を考慮しない単語と判断する文字列選択ステップを更に有し、
   前記文字列情報検索ステップにおいて、
   前記文字列情報検索手段は、前記文字列選択ステップにおいて、近接を考慮しない単語であると判断された単語については、全ての文に該単語が存在することとして前記インデックスＤＢを検索する請求項６又は７に記載の情報検索方法。
10. 前記文字列情報検索ステップにおいて、
    前記文字列情報検索手段は、前記入力された文字列から得られた複数の単語に基づいて、前記インデックスＤＢを検索し、当該複数の単語が存在する文のＩＤを検出し、文書保存ＤＢから当該ＩＤに対応する文を検索し、当該文に該入力された文字列が存在している場合のみ検索結果を前記類似度算出手段に出力する請求項６又は７に記載の情報検索方法。
11. 請求項１乃至５のいずれか１項に記載の情報検索装置を構成する各手段としてコンピュータを機能させる情報検索プログラム。
12. 請求項１１に記載の情報検索プログラムを格納したコンピュータ読取可能な記録媒体。

Images