(57)【要約】  クライアントからの文字列を取得する文字列入力手段と、該文字列が含まれる情報をインデックスＤＢから取得する文字列情報検索手段と、該文字列と検索された情報との類似度を算出する類似度算出手段と、類似度の高い順に検索された情報を出力する出力手段と、を有する情報検索装置が提供される。当該情報検索装置において、前記文字列情報検索手段は、入力された前記文字列が複数の単語からなる場合に、各単語に基づいて、単語及び該単語の出現位置情報を格納したインデックスＤＢを検索し、該単語の出現位置間の距離を求める手段を含み、前記類似度算出手段は、前記単語の出現位置間の距離に基づいて類似度を算出する手段を含む。
2009066501.tif 000002
【特許請求の範囲】
【請求項１】
クライアントからの文字列を取得する文字列入力手段と、該文字列が含まれる情報をインデックスＤＢから取得する文字列情報検索手段と、該文字列と検索された情報との類似度を算出する類似度算出手段と、類似度の高い順に検索された情報を出力する出力手段と、を有する情報検索装置であって、
前記文字列情報検索手段は、
入力された前記文字列が複数の単語からなる場合に、各単語に基づいて、単語及び該単語の出現位置情報を格納したインデックスＤＢを検索し、該単語の出現位置間の距離を求める手段を含み、
前記類似度算出手段は、前記単語の出現位置間の距離に基づいて類似度を算出する手段を含むことを特徴とする情報検索装置。
【請求項２】
前記インデックスＤＢは、単語と、該単語の文書中における文単位での出現位置情報を保持することを特徴とする請求項１に記載の情報検索装置。
【請求項３】
前記インデックスＤＢは、
単語と、該単語の文書中における文単位での出現位置情報を保持し、
前記出現位置情報をビット列で表現し、
前記文字列情報検索手段は、
前記インデックスＤＢを検索し、前記ビット列による単語の出現位置を取得する手段を含み、
前記類似度算出手段は、
前記インデックスＤＢの前記出現位置情報のビット列を用いてビットの論理演算により類似度を求める手段を含む請求項１記載の情報検索装置。
【請求項４】
前記入力された前記文字列が複数の単語からなる場合に、該単語に基づいて、近接を考慮しない単語が登録されている近接未考慮単語リスト記憶手段を参照して、該単語が該近接未考慮単語リスト記憶手段に存在する場合は近接を考慮しない単語と判断する文字列選択手段を更に有し、
前記文字列情報検索手段は、
前記文字列選択手段において、近接を考慮しない単語であると判断された単語については、全ての文に該単語が存在することとして前記インデックスＤＢを検索する手段を含む請求項１記載の情報検索装置。
【請求項５】
前記文字列情報検索手段は、
前記インデックスＤＢに、各単語の文単位での出現位置情報が格納されている場合には、前記入力された文字列から得られた複数の単語に基づいて、該インデックスＤＢを検索し、当該複数の単語が存在する文のＩＤを検出し、文書保存ＤＢから当該ＩＤに対応する文を検索し、当該文に該入力された文字列が存在している場合のみ検索結果を前記類似度算出手段に出力する連接確認手段を更に有する請求項１記載の情報検索装置。
【請求項６】
クライアントからの文字列を取得する文字列入力手段と、該文字列が含まれる文書に関する情報を、単語毎に文書における文単位の単語出現位置情報を格納したインデックスＤＢから取得する文字列情報検索手段と、該文字列と文書との類似度を算出する類似度算出手段と、類似度の高い順に検索された文書の情報を出力する出力手段と、を有する情報検索装置であって、
前記文字列情報検索手段は、
入力された前記文字列が複数の単語からなる場合に、各単語に基づいて、前記インデックスＤＢを検索することにより、各単語の文単位の出現位置情報を文書毎に取得する手段を含み、
前記類似度算出手段は、各文書における前記複数の単語の文単位での共起の度合いに基づいて、各文書と前記文字列との類似度を算出する手段を含むことを特徴とする情報検索装置。
【請求項７】
前記類似度算出手段は、ある文書において、前記複数の単語が共起する文の数を、当該文書における前記共起の度合いとして求める請求項６に記載の情報検索装置。
【請求項８】
クライアントからの文字列を取得し、該文字列が含まれる情報をインデックスＤＢから取得し、該文字列と検索された情報との類似度を算出し、類似度の高い順に検索された情報を出力する装置における情報検索方法であって、
文字列情報検索手段が、入力された前記文字列が複数の単語からなる場合に、各単語に基づいて、単語及び該単語の出現位置情報を格納したインデックスＤＢを検索し、該単語の出現位置間の距離を求める文字列情報検索ステップと、
類似度算出手段が、前記単語の出現位置間の距離に基づいて類似度を算出するステップと、を有することを特徴とする情報検索方法。
【請求項９】
前記インデックスＤＢが、単語と、該単語の文書中における文単位での出現位置情報を保持することを特徴とする請求項８に記載の情報検索方法。
【請求項１０】
前記インデックスＤＢが、単語と、該単語の文書中における文単位での出現位置情報を保持し、該出現位置情報がビット列で表現されている場合に、
前記文字列情報検索ステップにおいて、
前記文字列情報検索手段は、前記インデックスＤＢを検索し、前記ビット列による単語の出現位置情報を取得し、
前記類似度算出ステップにおいて、
前記類似度算出手段は、前記インデックスＤＢの前記出現位置情報のビット列を用いてビットの論理演算により類似度を求める請求項８記載の情報検索方法。
【請求項１１】
前記入力された前記文字列が複数の単語からなる場合に、該単語に基づいて、近接を考慮しない単語が登録されている近接未考慮単語リスト記憶手段を参照して、該単語が該近接未考慮単語リスト記憶手段に存在する場合は近接を考慮しない単語と判断する文字列選択ステップを更に有し、
前記文字列情報検索ステップにおいて、
前記文字列情報検索手段は、前記文字列選択ステップにおいて、近接を考慮しない単語であると判断された単語については、全ての文に該単語が存在することとして前記インデックスＤＢを検索する請求項８記載の情報検索方法。
【請求項１２】
前記文字列情報検索ステップにおいて、
前記文字列情報検索手段は、前記インデックスＤＢに各単語の文単位での出現位置情報が格納されている場合には、前記入力された文字列から得られた複数の単語に基づいて、該インデックスＤＢを検索し、当該複数の単語が存在する文のＩＤを検出し、文書保存ＤＢから当該ＩＤに対応する文を検索し、当該文に該入力された文字列が存在している場合のみ検索結果を前記類似度算出手段に出力する請求項８記載の情報検索方法。
【請求項１３】
クライアントからの文字列を取得する文字列入力手段と、該文字列が含まれる文書に関する情報を、単語毎に文書における文単位の単語出現位置情報を格納したインデックスＤＢから取得する文字列情報検索手段と、該文字列と文書との類似度を算出する類似度算出手段と、類似度の高い順に検索された文書の情報を出力する出力手段と、を有する情報検索装置が実行する情報検索方法であって、
前記文字列情報検索手段が、入力された前記文字列が複数の単語からなる場合に、各単語に基づいて、前記インデックスＤＢを検索することにより、各単語の文単位の出現位置情報を文書毎に取得する文字列情報検索ステップと、
前記類似度算出手段が、各文書における前記複数の単語の文単位での共起の度合いに基づいて、各文書と前記文字列との類似度を算出する類似度算出ステップとを有することを特徴とする情報検索方法。
【請求項１４】
前記類似度算出手段は、ある文書において、前記複数の単語が共起する文の数を、当該文書における前記共起の度合いとして求める請求項１３に記載の情報検索方法。
【請求項１５】
請求項１乃至７のいずれか１項に記載の情報検索装置を構成する各手段としてコンピュータを機能させる情報検索プログラム。
【請求項１６】
請求項１５記載の情報検索プログラムを格納したコンピュータ読取可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報検索方法及び装置及びプログラム及びコンピュータ読取可能な記録媒体に係り、大量の文書から文字列によって検索を行うための、全文検索のインデックスを構築するための情報検索方法及び装置及びプログラム及びコンピュータ読取可能な記録媒体に関する。詳しくは、検索条件の文字列が２単語（形態素）以上で構成される場合の情報検索方法及び装置及びプログラム及びコンピュータ読取可能な記録媒体に関する。
【背景技術】
【０００２】
大量の文書の中から、検索条件として入力された文字列を含む文書を検索して提示するシステムが実現されている。情報検索装置は、一般的に、情報検索装置の文字列ＤＢに保存される文書情報の中から、検索条件として入力された文字列を含む文書を特定する処理（ルックアップと呼ばれる）と、当該文字列と、当該文字列を含む各文書との類似度（スコアとも呼ばれる）を算出する処理（ランキングと呼ばれる）を行う。そして、情報検索装置は、検索結果として、この類似度が高い順に文書（文書ＩＤでもよい）を表示する。なお、本明細書において、"文書"とは、ある単位の文の集合であり、"文"とは、句点で区切られた単位の文字列である。例えば、１つの文書ファイルは、１つの文書と考えることができる。以下、従来の技術の例をより詳細に説明する。【０００３】
図１は、従来の情報検索装置１０の構成例を示す。図１において、情報検索装置１０、クライアント２０、及びネットワーク３０が、情報検索システムを構成している。図中の、文字列インデックスDB３は、検索対象となる文書群（本明細書において、"文書"を"文書群"の意味で使用する場合がある）の情報を検索しやすいデータ構造で格納したものであり、本例では、転置インデックスを格納する。従来の転置インデックスは、単語毎に、その単語が出現する文書ＩＤと、その文書の中での当該単語の単語単位での出現位置を有する。また、当該単語の当該文書内での出現頻度を転置インデックスに含めてもよい。【０００４】
同図に示す情報検索装置１０において、クライアント２０から転送された文字列がクライアント入力受付部１より入力される。入力された文字列は文字列情報検索部２において単語毎に分割される。そして、文字列情報検索部２は、その分割された単語毎に、当該単語が含まれる文書の文書ＩＤとその文書内での単語の出現位置を文字列インデックスDB３から取得する。【０００５】
さて、検索条件を構成する単語の中には、「東京」と「都」のように、「東京都」という複合語を分割した複数の単語（形態素）が含まれる場合がある。このような複合語では、２つの単語が隣り合って１つの意味を持つものであるから、ルックアップの処理において、２つの単語が検索対象文書の中で隣り合っているかどうかを確認する処理を行うのが一般的である。これを連接処理と呼ぶ。情報検索装置１０における連接処理の具体例は以下のとおりである。【０００６】
入力された文字列が「東京都」である場合、情報検索装置１０における文字列情報検索部２は、「東京都」を「東京」と「都」に分割する。そして、文字列情報検索部２は、分割して取得された各単語が存在する文書ＩＤと、その出現位置を文字列インデックスDB３から取得する。図２に、取得した情報の例を示す。図２において、「東京」が、文書ID１３３、１４４、１７０の文書に含まれることが示されている。また、文書ID１３３の文書では、「東京」の出現頻度が２で、当該文書中の５番目と２２番目に出現し、文書ID１４４の文書では、出現頻度が３で、文書中の１番目、１１番目、１８番目に出現していることが示されている。「都」についても同様に、出現文書、出現頻度、単語単位の出現位置が示されている。【０００７】
そして、文字列情報検索部２は、「東京」の次に「都」が出現している文書の有無をチェックし、文書ID１４４の文書において「東京」の次に「都」が出現していることを確認する。これにより、文字列情報検索部２は、「東京都」という複合語が含まれる文書として文書ID１４４を出力することができる。【０００８】
分割された複数の単語において、どれが複合語を構成する単語であるかは最初は不明であるから、文字列情報検索部２は、検索条件に含まれる単語のいずれかを持つ全ての文書に対して連接処理を行うことになり、大きな処理コストがかかるという問題がある。また、単語単位で位置情報を有する文字列インデックスでは、位置情報が多くのリソースを利用してしまうという問題もある。【０００９】
上記のようにしてルックアップ処理が終わった後、類似度算出部４は、文字列インデックスDB３から取得から得られた情報を用いて、入力された文字列と、当該文字列が出現する各文書との類似度を算出し、その類似度が高い文書順にその結果をクライアント出力部５に転送する。【００１０】
文字列と文書との類似度は、例えば、TFIDF(Term Frequency Inverse Document Frequency)を利用して算出される（非特許文献１）。この場合の類似度算出部４を詳細に示すと図３のようになる。図３に示すように、類似度算出部４は、単語重要度（ｉｄｆ）を利用して類似度を算出する単語重要度類似度算出部４１と、単語頻度（ｔｆ）を利用して類似度を算出する単語頻度類似度算出部４２より構成され、この二つの値を乗算した値が文書と単語との類似度になる。検索条件である文字列と、文書との類似度は、当該文字列を構成する全ての単語に関して上記の類似度を算出し、これら類似度の和を求めることにより得られる。【００１１】
【数１】
2009066501.tif 000003
上記の式がその計算方法を示す。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.
【発明の開示】
【発明が解決しようとする課題】
【００１５】
上述したように、単語単位で位置情報を有する文字列インデックス（転置インデックス）では、位置情報の量が多いとともに、連接処理に大きな処理コストがかかるという問題がある。【００１６】
また、非特許文献１及び非特許文献２に記載されている類似度算出方法では、入力された文字列が複数単語（もしくは形態素）で構成されたとしても、入力された文字列が出現する位置とは無関係に類似度算出を行うため、情報検索装置の精度が低いという問題があった。【００１７】
また、非特許文献３に記載された類似度算出方法では、入力された単語が複数の場合に、その複数の単語が近傍に出現すること（近接）を考慮した類似度の算出を提案しているが、一つの単語が複数の形態素で構成されていることは想定されていない。【００１８】
本発明は、上記の点に鑑みなされたもので、従来の問題を解消するための文字列インデックスを提供するとともに、近接している情報を利用した類似度の算出を文書全体に対して行うことで、検索精度を高め、また、計算コスト削減が実現可能な情報検索方法及び装置及びプログラム及びコンピュータ読取可能な記録媒体を提供することを目的とする。
【課題を解決するための手段】
【００１９】
上記の課題を解決するために、本発明は、クライアントからの文字列を取得する文字列入力手段と、該文字列が含まれる情報をインデックスＤＢから取得する文字列情報検索手段と、該文字列と検索された情報との類似度を算出する類似度算出手段と、類似度の高い順に検索された情報を出力する出力手段と、を有する情報検索装置であって、前記文字列情報検索手段は、入力された前記文字列が複数の単語からなる場合に、各単語に基づいて、単語及び該単語の出現位置情報を格納したインデックスＤＢを検索し、該単語の出現位置間の距離を求める手段を含み、前記類似度算出手段は、前記単語の出現位置間の距離に基づいて類似度を算出する手段を含むことを特徴とする情報検索装置として構成される。【００２０】
また、本発明は、クライアントからの文字列を取得する文字列入力手段と、該文字列が含まれる文書に関する情報を、単語毎に文書における文単位の単語出現位置情報を格納したインデックスＤＢから取得する文字列情報検索手段と、該文字列と文書との類似度を算出する類似度算出手段と、類似度の高い順に検索された文書の情報を出力する出力手段と、を有する情報検索装置であって、前記文字列情報検索手段は、入力された前記文字列が複数の単語からなる場合に、各単語に基づいて、前記インデックスＤＢを検索することにより、各単語の文単位の出現位置情報を文書毎に取得する手段を含み、前記類似度算出手段は、各文書における前記複数の単語の文単位での共起の度合いに基づいて、各文書と前記文字列との類似度を算出する手段を含むことを特徴とする情報検索装置として構成することもできる。【００２１】
上記の情報検索装置において、前記類似度算出手段は、ある文書において、前記複数の単語が共起する文の数を、当該文書における前記共起の度合いとして求めることとしてもよい。【００２２】
また、本発明は、上記情報検索装置が実行する処理方法としての情報検索方法としても構成できる。更に、本発明は、上記情報検索装置を構成する各手段としてコンピュータを機能させる情報検索プログラム、及び、当該情報検索プログラムを格納したコンピュータ読取可能な記録媒体として構成することもできる。
【発明の効果】
【００２３】
上記のように本発明によれば、２単語以上（もしくは２形態素以上で構成される１単語）を検索条件として検索を要求された場合に、単語の出現位置情報を用いることにより、その２単語が近傍に出現すること、あるいは、その２単語が文中で共起することを考慮した類似度を算出できる。これにより、検索精度を向上させる可能性がある。また、その出現位置をビットで格納し、ビット演算のみで実現することにより低コストで類似度を算出することができる。【００２４】
また、連接処理を行わずに、単語の近接の度合い（距離）あるいは単語の共起の度合いにより類似度を算出することにより、処理コストが連接処理を行う従来技術より低減する。また、再現率が従来技術に比べて向上する。更に、区切られた区間として、単語単位の位置情報ではなく、文単位の位置情報を用いて文字列インデックスを構成することにより、単語単位の位置情報を用いている従来の文字列インデックスに比べて情報量を削減できる。
【図面の簡単な説明】
【００２５】
【図１】情報検索システムの構成図である。
【図２】従来の文字列インデックスDBから取得した情報の例を示す図である。
【図３】類似度算出部４を示す図である。
【図４】本発明の実施の形態に係る情報検索装置の概要構成例を示す図である。
【図５】本発明の実施の形態に係る情報検索方法の概要を説明するための図である。
【図６】本発明の実施の形態に係るシステム構成図である。
【図７】本発明の第１の実施の形態における類似度算出部４'の構成図である。
【図８】本発明の第１の実施の形態における情報処理装置１０の一連の動作のフローチャートである。
【図９】本発明の第１の実施の形態における位置近接情報を利用した類似度算出処理のフローチャートである。
【図１０】本発明の第１の実施の形態における文字列インデックスＤＢ３'に格納されるデータの構造例を示す図である。
【図１１】本発明の第１の実施の形態における文字列インデックスＤＢ３'のビット列による位置情報の格納例である。
【図１２】ビットマップを利用した位置情報を用いる場合の近接計算を説明するための図である。
【図１３】文内共起回数を説明するための図である。
【図１４】本発明の第２の実施の形態における情報検索装置１０の構成図である。
【図１５】本発明の第２の実施の形態における近接を考慮しない単語が入力された場合を示す図である。
【図１６】本発明の第３の実施の形態における情報検索装置１０の構成図である。
【図１７】本発明の第３の実施の形態における文単位で位置情報を持った場合の連接実現方法を説明するための図である。
【符号の説明】
【００２６】
１  クライアント入力受付部、文字列入力手段
２  文字列情報検索部、文字列情報検索手段
３，３'  文字列インデックスＤＢ
４，４'  類似度算出部、類似度算出手段
５  クライアント出力部、出力手段
６  文字列選択部
１０  情報検索装置
１２  近接未考慮単語リスト記憶部
１４  文書保存ＤＢ
２０  クライアント
３０  ネットワーク
４１  単語重要度類似度算出部
４２  単語頻度類似度算出部
４３  単語位置類似度算出部
【発明を実施するための最良の形態】
【００２７】
以下、図面と共に本発明の実施の形態を説明する。まず、本発明の実施の形態の概要例を図４、図５を参照して説明する。【００２８】
図４は、本実施の形態に係る情報検索装置の概要構成例を示す図である。図４に示すように、この情報検索装置は、クライアントからの文字列を取得する文字列入力手段１と、該文字列が含まれる情報をＤＢから取得する文字列情報検索手段２と、該文字列と検索された情報との類似度を算出する類似度算出手段４と、類似度の高い順に検索された情報を出力する出力手段５と、を有する情報検索装置であって、文字列情報検索手段２は、入力された文字列が複数の単語からなる場合に、各単語に基づいて、単語及び該単語の出現位置情報を格納したインデックスＤＢ３'を検索し、該単語の出現位置間の距離を求める手段を含み、類似度算出手段４は、単語の出現位置間の距離に基づいて類似度を算出する手段を含む。【００２９】
また、インデックスＤＢ３'が、単語と該単語の文中の出現位置情報を文単位で集約した情報を保持し、出現位置情報をビット列で表現し、文字情報検索手段２において、インデックスＤＢ３を検索し、ビット列による単語の出現位置情報を取得する手段を含み、類似度算出手段４において、インデックスＤＢ３'の出現位置情報のビット列を用いてビットの論理演算により類似度を求める手段を含むこととしてもよい。【００３０】
また、前記情報検索装置において、入力された前記文字列が複数の単語からなる場合に、該単語に基づいて、近接を考慮しない単語が登録されている近接未考慮単語リスト記憶手段を参照して、該単語が該近接未考慮単語リスト記憶手段に存在する場合は近接を考慮しない単語と判断する文字列選択手段を更に有し、文字列情報検索手段２において、文字列選択手段において、近接を考慮しない単語であると判断された単語については、全ての文に該単語が存在することとしてインデックスＤＢ３を検索する手段を含むこととしてもよい。【００３１】
また、前記情報検索装置において、文字列情報検索手段２が、インデックスＤＢ３に文単位で文番号及び出現位置情報が格納されている場合には、入力された文字列から得られた単語に基づいて、該インデックスＤＢ３を検索し、得られた文番号を、文書が保存されている文書保存ＤＢから検索し、該入力された文字列が存在している場合のみ検索結果を前記類似度算出手段に出力する連接確認手段を更に有することとしてもよい。【００３２】
図５は、本発明の実施の形態に係る情報検索方法の概要を説明するための図である。当該情報検索方法は、クライアントからの文字列を取得し、該文字列が含まれる情報をＤＢから取得し、該文字列と検索された情報との類似度を算出し、類似度の高い順に検索された情報を出力する（ステップ３）装置における情報検索方法であって、文字列情報検索手段が、入力された文字列が複数の単語からなる場合に、各単語に基づいて、単語及び該単語の出現位置情報を格納したインデックスＤＢを検索し、該単語の出現位置間の距離を求める文字列情報検索ステップ（ステップ１）と、類似度算出手段が、単語の出現位置間の距離に基づいて類似度を算出するステップ（ステップ２）と、有する。【００３３】
また、前記情報検索方法において、インデックスＤＢが、単語と該単語の文中の出現位置情報を文単位で集約した情報を保持し、該出現位置情報をビット列で表現されている場合に、文字列情報検索ステップにおいて、インデックスＤＢを検索し、ビット列による単語の出現位置情報を取得し、類似度算出ステップにおいて、インデックスＤＢの出現位置情報のビット列を用いてビットの論理演算により類似度を求めることとしてもよい。【００３４】
また、前記情報検索方法において、入力された前記文字列が複数の単語からなる場合に、該単語に基づいて、近接を考慮しない単語が登録されている近接未考慮単語リスト記憶手段を参照して、該単語が該近接未考慮単語リスト記憶手段に存在する場合は近接を考慮しない単語と判断する文字列選択ステップを更に行い、文字列情報検索ステップにおいて、文字列選択ステップで近接を考慮しない単語であると判断された単語については、全ての文に該単語が存在することとして前記インデックスＤＢを検索することとしてもよい。【００３５】
また、前記情報検索方法における文字列情報検索ステップにおいて、インデックスＤＢに文単位で文番号及び出現位置情報が格納されている場合には、入力された文字列から得られた単語に基づいて、該インデックスＤＢを検索し、得られた文番号を、文書が保存されている文書保存ＤＢから検索し、該入力された文字列が存在している場合のみ検索結果を前記類似度算出手段に出力することとしてもよい。【００３６】
本実施の形態において、情報検索装置を構成する各手段としてコンピュータを機能させる情報検索プログラムを提供することができる。また、この情報検索プログラムを格納したコンピュータ読取可能な記録媒体を提供することもできる。【００３７】
以下、本発明の各実施の形態を詳細に説明する。【００３８】
本発明の実施の形態では、インターネットのＷｅｂサーバ上で動作する情報検索プログラムが、ハードディスクなどの記録媒体に保存され、当該Ｗｅｂサーバ上で実行させることを想定している。よって、クライアント側はネットワークを介してＷｅｂブラウザ等を利用し、当該情報検索装置にアクセスし、クライアント入力受付部、及び出力部を通して情報を検索する。この方法は、スタンドアロンの形態のシステムにも適用することが可能である。【００３９】
本発明の実施の形態に係るシステム構成を図６に示す。図６に示すとおり、本発明の実施の形態のシステムは、クライアント２０、ネットワーク３０、及び情報検索装置１０を有する。情報検索装置１０は、クライアント入力受付部１、文字列情報検索部２、文字列インデックスＤＢ３'、類似度算出部４'、クライアント出力部５から構成される。その構成は、前述の図１とほぼ同様であるが、文字列インデックスＤＢ３'及び類似度算出部４'の構成は、図１に示した文字列インデックスＤＢ３及び類似度算出部４と異なる。【００４０】
図６の構成において、情報検索装置１０には、クライアント２０からネットワーク３０を介してクライアント入力受付部１に文字列が入力される。クライアント入力受付部１から文字列が文字列情報検索部２に転送されると、文字列は単語毎に分割される。文字列情報検索部２は、その分割された各単語が含まれる文書とその文書内の単語の出現位置を文字列インデックスＤＢ３'から取得し、それらを類似度算出部４'に転送する。類似度算出部４'は、取得された単語と単語の出現位置に基づいて、文字列と各文書との類似度を計算する。なお、図６に示す構成における機能分担は、以下に説明するものに限られるわけではない。例えば、文字列情報検索部２が、類似度算出部４'における処理の一部（近接の度合いの計算、共起の度合いの計算等）を行うこととしてもよい。【００４１】
類似度算出部４'は、転送された文字列が単一の単語の場合は、その単語と、その単語が出現する文書との類似度を例えば、前述の非特許文献１の方法で算出し、その類似度が高い文書順に文書ＩＤを出力する。なお、文書ＩＤから、別のデータベースを検索して、文書そのものを出力してもよい。その単語が複数の単語で構成されている場合は、類似度算出部４'は、その複数の単語がどの程度近接しているのかを考慮して、文字列と文書との類似度を算出し、その結果として、類似度が高い文書順に文書ＩＤ等をクライアント出力部５に転送する。【００４２】
図７は、本発明の第１の実施の形態における類似度算出部４'の構成を示す。【００４３】
同図に示す類似度算出部４'は、従来技術と比較して、単語重要度類似度算出部４１、単語頻度類似度算出部４２に加え、単語位置類似度算出部４３が追加されている。この単語位置類似度算出部４３は、近接情報又は共起情報を利用した類似度を算出する。【００４４】
次に、本発明の実施の形態に係る一連の処理について説明する。【００４５】
図８は、本発明の第１の実施の形態における情報処理装置１０の一連の動作のフローチャートである。【００４６】
ステップ１０１）  クライアント入力受付部１より文字列が入力されると、文字列情報検索部２は、入力された文字列を単語毎に分割する。例えば、"東京都"という文字列が入力されると、形態素解析処理を利用して単語毎に分割する。単語毎に分割すると、一般的に"東京"及び"都"という文字列に分割される。【００４７】
ステップ１０２）  文字列情報検索部２は、文字列が２単語以上で構成されるかをチェックする。２単語以上である場合はステップ１０３に移行し、単一単語である場合は、ステップ１０５に移行する。【００４８】
ステップ１０３）  文字列情報検索部２は、文字列インデックスＤＢ３'を検索して、分割された単語毎に、分割された単語を持つ文書と単語出現位置を取得する。【００４９】
ステップ１０４）  類似度算出部４'は、近接情報を利用して類似度を算出し、ステップ１０７に移行する。なお、近接情報を利用した類似度の算出方法については後述する。【００５０】
ステップ１０５）  類似度算出部４'は、文字列インデックスＤＢ３'から入力文字列である単一の単語を持つ文書と単語出現頻度を取得する。【００５１】
ステップ１０６）  類似度算出部４'は、１単語の場合の単語の重要度は全ての文書で共通であるので、単語頻度類似度算出部４２において単語の頻度のみで、当該単語と、当該単語が出現する各文書との類似度を算出する。【００５２】
ステップ１０７）  上記のステップ１０２において、入力文字列が２単語以上である場合は、類似度算出部４'は、近接情報を利用した検索結果（例えば、文書ＩＤ）を類似度順（例えば類似度の高い順）に並べ、クライアント出力部５に転送する。ステップ１０２において、入力文字列が単一単語の場合には、類似度算出部４'は、単語頻度情報を用いて算出された類似度順に検索結果をソートしてクライアント出力部５に転送する。これにより、クライアント出力部５は、検索結果をクライアント２０に提示する。【００５３】
次に、上記のステップ１０４における位置近接情報を利用した類似度算出方法について説明する。【００５４】
図９は、本発明の第１の実施の形態における位置近接情報を利用した類似度算出処理のフローチャートである。【００５５】
ステップ２０１）  類似度算出部４'の単語位置類似度算出部４３において、文字列から分割して得られた各単語を含む文書の文書ＩＤとその文書ＩＤでの各単語の出現位置を取得する。その情報は、文字列情報検索部２が文字列インデックスDB3'から取得した情報から取得できる。【００５６】
ここで、本実施の形態における文字列インデックスＤＢ３'に格納されるデータの構造例を図１０に示す。図１０の例では、単語毎に、単語とその単語が出現する文書ＩＤが保存され、更に、文書ＩＤ毎に、当該単語の出現位置データが保存されている。また、本実施の形態における単語の出現位置は、文単位の出現位置である。【００５７】
例えば、word１が"東京"という文字列である場合、"東京"はｉｄ１という文書に存在し、その出現位置は、ｉｄ１という文書の中の１文目、３文目、４文目、及び８文目であることを示している。また、その構造をbitmapで持たせた例を図１１に示す。図１０では文単位の出現位置が数値で示されていたのに対し、図１１ではbitmapで表現されている。例えば、word１のｉｄ１の文書に関する"００１０"は、３文目に単語word１が存在することを示している。本発明の実施の形態では、単語の位置情報を文単位としたが、必ずしもこれに限定されることはなく、ある区切られた区間毎の単位であればよい。例えば、この位置情報を単語単位の出現位置や、段落単位の出現位置などに変更しても同様の近接に基づく類似度算出処理が可能である。【００５８】
入力された文字列を分割して得られた単語が「東京」と「都」であった場合、ステップ２０１の処理において、単語位置類似度算出部４３は、「東京」と「都」の両方を含む文書の文書ＩＤと、その文書内での「東京」の文単位での出現位置、及び、その文書内での「都」の文単位での出現位置を取得することになる。例えば、図１０の例において、ｗｏｒｄ１が「東京」であり、ｗｏｒｄ２が「都」であるとすれば、ステップ２０１において、単語位置類似度算出部４３は、「東京」に対して、文書ＩＤ１と、その中の出現位置（１文目、３文目、４文目、８文目）、及び、「都」に対して、文書ＩＤ１と、その中の出現位置（１文目、５文目、６文目、８文目）を取得することになる。【００５９】
この例において、以下では、単語位置類似度算出部４３は、文書ＩＤ１の文書内で、「東京」の文単位での出現位置と「都」の文単位での出現位置とがどの程度近接しているかを示すスコアを算出し、そのスコアを、入力文字列（「東京都」）と文書ＩＤ１の文書との類似度とする処理を行う。【００６０】
ステップ２０２）  単語位置類似度算出部４３は、カウンタｋ＝０、及び、ｎをセットする。ｎとは、前後何文までの近接を見るかを指定するための数値である。例えば、ｎ＝１だとすると、隣り合う文のみに着目して近接類似度を求めることになる。逆にある文書がｍ文で構成され、そのｍをｎにセットすると文書全体での近接類似度を算出することができる。【００６１】
ステップ２０３）  単語位置類似度算出部４３は、ｋの値がｎ以下かどうかをチェックする。ｎ以下の場合は、ステップ２０４に移行し、ｎより大きい場合はステップ２０７に移行する。【００６２】
ステップ２０４〜２０５）  単語位置類似度算出部４３は、ステップ２０１で得られた出現位置群のペアのうちの一方の出現位置を文単位でｋだけずらし（例えば、減算し）て得られた出現位置と、他方の出現位置との一致度  score(Q,d,k)  を算出する。一致度score(Q,d,k)は例えば、下記に示される式で算出される。【００６３】
【数２】
2009066501.tif 000004
上記の式において、Ｑはクエリ集合（文字列を分割して得た単語の集合）、ｄは文書、Ｐｏｓｄ（ｑｉ）は、文書ｄ中のｑｉ（単語、例えば上記の例の「東京」）の出現位置を示し、Ｐｏｓｄｋ（ｑｊ）は文書ｄ中のｑｊ（単語、例えば上記の例の「都」）の出現位置からｋ減算した列を表す。例えば、図１０のｗｏｒｄ２が「都」である例において、ｋが０の場合、Ｐｏｓｄｋ（ｑｊ）は（１、５、６、８）である。また、この例において、ｋが１の場合、Ｐｏｓｄｋ（ｑｊ）は（０、４、５、７）である。【００６４】
Count(Pos,Pos)は、２つのポジションデータが与えられた時に、その一致度を返す関数で、例えば、入力がｋ＝０だった場合は、同一文に単語ｑｉとｑｉ以外の単語であるｑｊが出現する回数の合計を出力する。また、ｋ＝１の場合、Count(Pos,Pos)は、隣り合う文に単語ｑｉと単語ｑｊが出現する回数の合計を出力する。【００６５】
例えば、単語ｑｉが上記の例の「東京」であり、ｑｉ以外の単語ｑｊが上記の例の「都」であるとすると、ｋ＝０の場合において、Ｐｏｓｄ（ｑｉ）は（１、３、４、８）であり、Ｐｏｓｄｋ（ｑｊ）は、（１、５、６、８）であるから、Countは２を返す。つまり、これは、対象の文書において、「東京」と「都」が同一文に出現する回数が２回（文１と文８）であることを示す。【００６６】
αは係数であり、例えば１である。１／(αｋ＋１）によってより近い位置の文に各単語が存在する場合に大きなスコアが算出される。【００６７】
ステップ２０６）  単語位置類似度算出部４３は、ｋの値を１インクリメントし、ステップ２０３に戻る。【００６８】
ステップ２０７）  単語位置類似度算出部４３は、各ｋの値で算出されたscoreの値の合計値を入力文字列と文書との類似度として出力する。これが単語の位置情報を考慮した類似度となる。より詳細には、これは近接の度合いを考慮した類似度である。これは、以下の式で算出される。【００６９】
【数３】
2009066501.tif 000005
図１１に示すビットマップを利用した位置情報を用いる場合は、ＰｏｓｄとＰｏｓｄｋをｋビットシフトした情報で論理積をとり、その論理積をとった結果のビットから１の数をカウントするだけでcountを計算することができる。図１２は、ビットマップを利用した位置情報を用いる場合の近接計算を説明するための図であり、Ｑ（word_2,word_1），ｄ＝１，ｋ＝１が入力になったときのスコアの算出例を示している。まず、文字列情報検索部２は、word1とword2の位置情報を文字列インデックスDB3'（図１１に示す構成）から取得する。類似度算出部４'は、その取得した位置情報からword_1の位置情報を１ビットシフトし、word_2の位置情報と論理積をとる。その論理積の結果のビット位置が隣の１文にword1とword2が存在した位置である。この例の場合、立っているビットが２ビット目の一つだけなので、scoreは"１"である。このビット列から１の数を数える方法としては、例えば、Intel CPUのSSE4命令POPCNTで高速に求める方法がある。【００７０】
検索条件である文字列と、文書との類似度の算出方法の他の例を次に説明する。この例では、下記の数式を用いて類似度（スコア）を算出する。【００７１】
【数４】
2009066501.tif 000006
上記の式（１）は、文字列（クエリ）ｑの集合Qと文書ｄとの類似度ｓｃｏｒｅが、クエリ毎の類似度ｗｄ（ｑ）の和であることを示し、式（２）は、クエリｑが、形態素ｔの集合Ｔｑから構成されることを示す。式（３）は、類似度ｗｄ（ｑ）が、形態素毎の類似度ｗｄ（ｔ）の和であることを示す。類似度ｗｄ（ｔ）は、式（４）により求められる。【００７２】
この式（４）は、非特許文献２に示されているＢＭ２５で用いられる下記の式【００７３】
【数５】
2009066501.tif 000007
における、ｔｆ（ｔ，ｄ）（形態素ｔの文書ｄにおける出現頻度）を、ｃｏｏｃｃ（Ｔｑ，ｄ）に置き換えたものに相当する。それ以外のパラメータについては、ＢＭ２５におけるパラメータと同様である。Ｎは全文書数を示す。ｄｆ（ｔ）は、ｔを含む文書数であり、ｋ１は係数である。Ｋは、ｋ１と文書長等から求められる値である。【００７４】
ｃｏｏｃｃ（Ｔｑ，ｄ）は、Ｔｑの文書ｄにおける文内共起回数である。例えば、Ｔｑが、「東京」と「都」である場合において、類似度算出にあたり、類似度算出部４'は、ぞれぞれの単語についての文書ＩＤ、出現頻度、文単位位置情報として、図１３に示す情報を、文字列インデックスＤＢ３'から、又は、文字列情報検索部２から取得する。この例では、文字列インデックスＤＢ３'は、文書ＩＤと、文単位の単語出現位置情報とともに、単語の出現頻度を有する。この出現頻度は、ある文に該当の単語が存在すれば、それが２回以上同じ文に出現する場合でも、１加算されるものである。【００７５】
図１３に示す情報を取得した類似度算出部４'は、文単位の位置情報に基づき、文１、文３４、文５２において、「東京」と「都」が共起していることを検知し、ｃｏｏｃｃ（Ｔｑ，ｄ）（この場合、Ｔｑは「東京」と「都」、ｄは１３３）を３とする。そして、上記の式（４）、式（３）を用いて、文書１３３についての、"東京都"に対する類似度を求めることができる。【００７６】
なお、上記の例では、ＢＭ２５の式の一部を文内共起回数ｃｏｏｃｃ（Ｔｑ，ｄ）に置き換えた式を用いて類似度を算出しているが、ＢＭ２５の式に基づくことは必ずしも必須ではない。文内共起回数ｃｏｏｃｃ（Ｔｑ，ｄ）を用いるのであれば、他の式を用いてもよい。また、例えば、文内共起回数ｃｏｏｃｃ（Ｔｑ，ｄ）そのものを類似度とすることも考えられる。【００７７】
上記のように、本実施の形態では、連接処理を行わずに、区切られた区間（上記の例では文）単位での単語の近接の度合いあるいは単語の共起の度合いにより類似度を算出しているため、処理コストが連接処理を行う従来技術より低減する。また、再現率が従来技術に比べて向上する。更に、区切られた区間として、単語単位の位置情報ではなく、文単位の位置情報を用いて文字列インデックスＤＢ３'を構成することにより、単語単位の位置情報を用いている従来の文字列インデックスＤＢに比べて情報量を削減できる。【００７８】
［第２の実施の形態］
上記で入力された文字列が２単語（形態素）以上であった時に、近接していることを利用した類似度の算出方法を説明した。しかしながら、必ずしも近接していることが精度向上に繋がるとは言えない。例えば、"レストラン名  電話番号"という文字列が検索条件として入力された場合、"レストラン名  電話番号"を探しているわけではなく、あるレストランのページで「電話番号」という文字列が存在しているページを提示するだけでよい可能性がある。そこで、本実施の形態では、その検索条件として入力された単語が、近接を考慮するか否かを判断する。【００７９】
図１４は、本発明の第２の実施の形態における情報検索装置１０の構成を示す。同図において、図６と同一構成部分については同一符号を付し、その説明を省略する。【００８０】
同図に示す情報検索装置１０は、図６の情報検索装置１０に文字列選択部６と、近接未考慮単語リスト記憶部１２が付加された構成である。近接未考慮単語リスト記憶部１２は、近接を考慮しない単語が登録されている。【００８１】
文字列選択部６は、検索条件として入力された単語に基づいて、近接未考慮単語リスト記憶部１２を参照して、当該単語が近接未考慮単語リスト記憶部１２に存在する場合には、近接を考慮しない単語であると判定する。文字列情報検索部２は、文字列選択部６において近接を考慮しない単語であると判断された場合には、全ての位置にその単語が存在することとして近接処理を行う。図１５は、本発明の第２の実施の形態における近接を考慮しない単語が入力された場合を示す。同図に示すword_1が近接を考慮しない単語の例で、その出現位置は"００１０"である。本実施の形態では、当該単語の出現位置を全ての文に存在する"１１１１"に変換し、類似度算出部４'による類似度算出処理を行う。類似度算出部４'による処理は、前述の第１の実施の形態での処理と同様である。【００８２】
近接未考慮単語の出現位置を"１１１１"に変換することにより、当該単語の出現位置は類似度のスコアに寄与しなくなる。【００８３】
［第３の実施の形態］
入力された文字列が２単語で構成される場合に、文単位の単語出現位置情報のみを用いた近接処理では、複合語を判別できないので、検索精度が低下する恐れがある。そこで、本実施の形態では、２単語で構成される語の連接処理を単語出現位置情報が文単位で保存されている場合に実現する方法を説明する。【００８４】
図１６は、本発明の第３の実施の形態における情報検索装置１０の構成を示す。【００８５】
同図に示す情報検索装置は、図６の構成に文書保存ＤＢ１４が追加された構成である。また、文字列インデックスＤＢ３'は、単語に対して、単語単位ではなく、文書ＩＤと文単位の位置情報を保持している。【００８６】
図１７は、本発明の第３の実施の形態における文単位で位置情報を持った場合の、連接実現方法を説明するための図である。【００８７】
同図に示すように、文字列インデックスＤＢ３'には、単語毎に、当該単語が存在する文書ＩＤ（ＤＯＣ＿ＩＤ）とビットで表された文単位の単語出現位置情報が格納されている。これにより、文字列情報検索部２は、入力された文字列を形態素解析し、当該文字列が２単語以上である場合には、文字列インデックスＤＢ３'から当該単語を持つ文書ＩＤと、単語の出現位置を取得し、位置情報の論理積をとることにより文内共起の有無を調べる。【００８８】
そして、該当の単語が文内共起している文がある場合に、文字列情報検索部２は、文書ＩＤ及び文番号に基づいて文書保存ＤＢ１４を検索し、対応する文を取得し、その文の中に、上記複数単語が連接した複合語があるかどうかを調べる。そして、複合語があれば、その複合語を含む文書を検索結果として出力できる。【００８９】
また、本例でも、類似度算出部４の単語位置類似度算出部４３は、第１の実施の形態と同様にして、文字列情報検索部２から取得した２つの単語に対応する文書の近接情報（位置情報）に基づいて、類似度を算出してよいが、上記のように複合語が検知された文書にスコアを加算することとしてもよい。また、単語位置類似度算出部４３は、複合語が検知された文書のみについて類似度を算出し、類似度の高い順に検索結果をクライアント出力部５に出力することとしてもよい。【００９０】
例えば、検索クエリとして"東京都"という文字列が入力された場合、まず、"東京"と"都"が存在する文が特定される。これは、今までの文単位での位置情報による近接処理と同等である。図１７の例では、文書１における２番目の文、及び、文書２における１番目の文が、それぞれ"東京"と"都"を含む。特定された文書ＩＤと文番号を文書保存ＤＢ１４から参照し、"東京都"という文字列が存在するか否かが調査される。この処理は文の前方から全てスキャンすることにより行うことができる。この結果、文字列情報検索部２は、当該文字列が存在した文書のみ（連接語が存在している文書のみ）を類似度算出部４'に出力し、類似度算出部４'は類似度を算出し、クライアント出力部より検索結果を提示することができる。【００９１】
また、上記の実施の形態における情報検索装置の構成要素の各動作をプログラムとして構築し、情報検索装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。【００９２】
さらに、構築されたプログラムをハードディスクや、フレキシブルディスク・ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールする、または、配布することが可能である。【００９３】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【産業上の利用可能性】
【００９４】
本発明は、データベース等の大量の文書から入力された文字列を用いて所望の情報を取得する情報検索に適用可能である。【００９５】
本国際出願は、２００７年１１月１９日に出願された日本国特許出願第２００７−２９９７８４号に基づく優先権を主張するものであり、その全内容を本国際出願に援用する。
【図１】
2009066501.tif 000008
【図２】
2009066501.tif 000009
【図３】
2009066501.tif 000010
【図４】
2009066501.tif 000011
【図５】
2009066501.tif 000012
【図６】
2009066501.tif 000013
【図７】
2009066501.tif 000014
【図８】
2009066501.tif 000015
【図９】
2009066501.tif 000016
【図１０】
2009066501.tif 000017
【図１１】
2009066501.tif 000018
【図１２】
2009066501.tif 000019
【図１３】
2009066501.tif 000020
【図１４】
2009066501.tif 000021
【図１５】
2009066501.tif 000022
【図１６】
2009066501.tif 000023
【図１７】
2009066501.tif 000024
【国際調査報告】
2009066501.tif 000025
2009066501.tif 000026
2009066501.tif 000027
2009066501.tif 000028