(57)【要約】【課題】大規模な文書集合を対象としたランキング検索を高速、低コストに行なう。【解決手段】検索処理部７は、検索語が一つの索引語のみから構成される場合には、索引語頻度が閾値Ｆ以上の文書の索引語と出現位置のリストが格納されている高頻度語転置索引４からその索引語の出現位置リストを入力し、検索語が複数の索引語の並びである場合には、各索引語の出現位置リストを高頻度語転置索引４から入力し、すべての索引語が隣接して出現する位置のリストを求め、該リストを適合度計算部６に渡し、適合文書リストを受け取る。得られた適合文書リストが、検索結果の表示に必要なＴ個以上の文書を参照しており、適合度上位Ｔ番目の文書が、高頻度語転置索引４には格納されない低頻度の文書がとり得る最大の適合度よりも大きい適合度を持つ場合それらを出力する。【選択図】    図１
2004192546.tif 000002
【特許請求の範囲】
【請求項１】
検索対象の文書から索引語を抽出し、それらと、それらの出現位置の組のリストを転置索引に格納する索引作成ステップと、
前記転置索引から、索引語頻度があらかじめ定められた閾値以上になる索引語と出現位置の組のリストを抽出し、高頻度語転置索引に格納する高頻度語抽出ステップと、
検索語の出現位置リストを受け取り、各文書における検索語の頻度と文書サイズから文書毎に適合度を計算し、適合文書リストとして出力する適合度計算ステップと、
利用者から検索語を受け取り、検索語が１つの索引語のみから構成される場合には前記高頻度語転置索引から該索引語の出現位置のリストを入力し、検索語が複数の索引語の並びである場合には、それぞれの索引語の出現位置のリストを前記高頻度語転置索引から入力し、すべての索引語が隣接して出現する位置のリストを求め、前記高頻度語転置索引から求められた出現位置のリストが、検索結果の表示に必要なＴ個（Ｔは１以上の整数）以上の文書を参照している場合には該出現位置のリストを前記適合度計算ステップに渡して、適合文書リストを受け取り、適合度上位Ｔ番目の文書が、前記高頻度語転置索引には格納されない低頻度の文書がとり得る最大の適合度よりも大きい適合度を持つ場合は、それらを出力し、前記高頻度語転置索引からＴ個以上の文書を参照する出現位置のリストが得られなかった場合、あるいは適合度上位Ｔ個の文書が正しく検索されていない可能性がある場合には、前記転置索引を用いて検索語の出現位置のリストを求め、それを前記適合度計算ステップに出力し、前記適合度計算ステップから適合文書のリストを入力し、適合文書を、適合度の降順で上位最大Ｔ個出力する検索処理ステップを有する情報検索方法。
【請求項２】
索引語と出現位置の組を格納する転置索引と、
検索対象の文書から索引語を抽出し、それら索引語と、それらの出現位置の組を前記転置索引に格納する索引作成手段と、
高頻度の索引語とその出現位置の組のみを格納する高頻度語転置索引と、
前記転置索引から、索引語頻度があらかじめ定められた閾値以上になる索引語と出現位置の組のリストを抽出し、前記高頻度語索引に格納する高頻度語抽出手段と、
検索語の出現位置リストを受け取り、各文書における検索語の頻度と文書サイズから文書毎に適合度を計算し、適合文書リストとして出力する適合度計算手段と、
利用者から検索語を受け取り、検索語が１つの索引語のみから構成される場合には前記高頻度語転置索引から該索引語の出現位置のリストを入力し、検索語が複数の索引語の並びである場合には、それぞれの索引語の出現位置のリストを前記高頻度語転置索引から入力し、すべての索引語が隣接して出現する位置のリストを求め、前記高頻度語転置索引から求められた出現位置のリストが、検索結果の表示に必要なＴ個以上（Ｔは１以上の整数）の文書を参照している場合には該出現位置のリストを前記適合度計算手段に渡して、適合文書リストを受け取り、適合度上位Ｔ番目の文書が、前記高頻度語転置索引には格納されない低頻度の文書がとり得る最大の適合度よりも大きい適合度を持つ場合は、それらを出力し、前記高頻度語転置索引からＴ個以上の文書を参照する出現位置のリストが得られなかった場合、あるいは適合度上位Ｔ個の文書が正しく検索されていない可能性がある場合には、前記転置索引を用いて検索語の出現位置のリストを求め、それを前記適合度計算手段に出力し、前記適合度計算手段から適合文書のリストを入力し、適合文書を、適合度の降順で上位最大Ｔ個出力する検索処理手段を有する情報検索装置。
【請求項３】
請求項１記載の情報検索方法をコンピュータに実行させるための情報検索プログラム。
【請求項４】
請求項３記載の情報検索プログラムを記録した、コンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、検索対象となる文書集合を索引づけし、利用者の入力した検索条件に適合する文書を検索する情報検索方法および装置に関する。
【０００２】
【従来の技術】
情報検索装置は、文書集合の中から、利用者によって与えられた検索質問に適合する文書を検索し、それらを利用者に提示する装置である。そこで、今日の情報検索装置の多くは、単に検索語を含む文書を列挙するのではなく、それぞれの文書の検索質問に対する適合度を計算し、高い適合度を得た文書のみを適合度の降順に提示する。これをランキング検索と呼ぶ。
【０００３】
適合度の計算には索引語の重みという考え方が用いられる（非特許文献３、非特許文献４）。ここで索引語とは、文書の内容を特徴づける語のことであるが、今日の全文検索装置では、基本的に文書中のすべての語を索引語とみなす。日本語などのアジア圏の言語では語の区切りが明確ではないため、形態素あるいは文字Ｎグラムを索引語とするのが一般的である。索引語の重みとは、索引語が文書の内容を表わす上でどれだけの重要度を持っているかを示す数値であり、一般に索引語ｗiの文書Ｄjにおける重みｄi,jは、局所的重みｌi,j、大域的重みｇi、文書正規化係数ｎjという３つの指標から、式（１）のように特徴づけられる（非特許文献３）。
【０００４】
【数１】
2004192546.tif 000003
【０００５】
たとえば、もっとも基本的な重み付け方法として知られるＴＦ・ＩＤＦ法では、局所的重みｌi,jとして文書内での索引語の出現回数である索引語頻度（ＴＦ：term frequency）を、大域的重みｇiとして索引語が出現する文書の割合の逆数（ＩＤＦ：inverse document frequency）を用いている。また、文書正規化係数ｎjとしては文書サイズ（索引語頻度の総和）を用いるのがもっとも単純な方法である。すなわち、ＴＦ・ＩＤＦ法による索引語の重みｄi,jは式（２）のようになる。
【０００６】
【数２】
2004192546.tif 000004
【０００７】
また、ＴＦ・ＩＤＦ法以外の方法でも、ｌi,jは索引語頻度から、ｇiは文書頻度から、ｎjは文書サイズから求めるものが多い。
【０００８】
多数の文書を対象とする情報検索装置は、検索処理を高速におこなうために、索引語と、それらの出現位置の情報を、索引と呼ばれる一種のデータベースにあらかじめ格納しておく。これを索引検索方式という（非特許文献３、非特許文献４）。索引検索の代表的な実現方式として転置索引がある（非特許文献３、非特許文献４）。転置索引とは索引語を辞書順に列挙し、それらをキーとして、索引語の出現位置リストを参照できるように構成されたデータベースである（図５）。転置索引方式では、位置情報として文書番号だけでなく文書内での位置まで格納しておくことで、複数の索引語の並びから構成される検索語の出現位置を文書自体を参照することなしに求めることができる。また、検索語の各文書での出現回数や、検索語が出現する文書数、検索語の総出現回数など、適合度の計算に必要な基本的なパラメータも同時に求められるため、転置索引はランキング検索に適した索引検索方式といえる。
【０００９】
【非特許文献１】
Michael Persin, Justin Zobel, Ron Sacks-Davis: "Filtered Document Retrieval with Frequency-Sorted Indexes", Journal of the American Society of Information Science, Vol.47, No.10, pp. 749-764, 1996.
【非特許文献２】
速水賢史、竹野浩、永瀬智哉、藤本典幸、萩原兼一「スケーラビリティのあるＷＷＷ並列全文検索システム構築法の提案と評価」、情報処理学会データベース研究会研究報告、Ｖｏｌ．１２３、Ｎｏ．７、ｐｐ．４５−５２、２００１。
【非特許文献３】
北研二、津田和彦、獅子堀正幹「情報検索アルゴリズム」、共立出版、２００２。
【非特許文献４】
徳永健伸「情報検索と言語処理」、東京大学出版会、１９９９。
【００１０】
【発明が解決しようとする課題】
転置索引を採用した情報検索装置の場合、ランキング検索の処理時間の大部分は、出現位置リストを転置索引から主記憶上に読み出す処理と、検索結果となる文書の適合度を計算する処理によって占められる。そのため、ランキング検索には、検索質問に含まれる検索語の出現回数の総和におおむね比例する時間が必要になる。
【００１１】
一般に、語句の出現回数は、検索対象となる文書集合中のテキストの量に比例して大きくなる。したがって、ＷＷＷサーチエンジンのような大規模な情報検索システムでは、従来の転置索引では検索処理に非常に時間がかかる場合がある。この問題に対処するために、文書集合を分割し、それぞれの部分文書集合を複数の計算機システムによって並列に検索し、それらの検索結果を併合するという並列検索方式が用いられることがある（非特許文献２）。しかし、多くのハードウェアが必要となるため、システムの導入や維持に要するコストが大きい。
【００１２】
本発明の目的は、大規模な文書集合を対象としたランキング検索を高速、かつ低コストにおこなうことのできる情報検索方法、装置、プログラムおよび記録媒体を提供することにある。
【００１３】
【課題を解決するための手段】
本発明の情報検索装置は索引作成手段と転置索引と高頻度語抽出手段と高頻度語転置索引と適合度計算手段と検索処理手段を有する。
【００１４】
転置索引には索引作成手段によって、索引語と出現位置の組のリストが格納されている。高頻度語転置索引には高頻度語抽出手段によって、索引語頻度があらかじめ定められた閾値以上の索引語とその出現位置の組のリストが格納されている。検索処理手段は、利用者から検索語を受け取り、検索語が１つのみの索引語から構成される場合には高頻度語転置索引から該索引語の出現位置のリストを入力し、検索語が複数の索引語の並びである場合には、それぞれの索引語の出現位置のリストを高頻度語転置索引から入力し、すべての索引語が隣接して出現する位置のリストを求め、高頻度語転置索引から求められた出現位置のリストが、検索結果の表示に必要なＴ個以上（Ｔは１以上の整数）の文書を参照している場合には該出現位置のリストを適合度計算手段に渡して、適合文書リストを受け取り、適合度上位Ｔ番目の文書が、高頻度語転置索引には格納されない低頻度の文書がとり得る最大の適合度よりも大きい適合度を持つ場合は、それらを出力し、高頻度語転置索引からＴ個以上の文書を参照する出現位置のリストが得られなかった場合、あるいは適合度上位Ｔ個の文書が正しく検索されていない可能性がある場合には、転置索引を用いて検索語の出現位置のリストを求め、それを適合度計算手段に出力し、適合度計算手段から適合文書のリストを入力し、適合文書を、適合度の降順で上位最大Ｔ個出力する。
【００１５】
本発明の情報検索装置は、通常の転置索引に加えて、索引語頻度が大きい出現位置リストのみを格納した高頻度語転置索引をあらかじめ用意することで、検索質問が一つの検索語のみから構成されている場合には、比較的小さな高頻度語転置索引のみを使って適合度の高い文書を検索し、検索質問が複数の検索語から構成される場合には、従来の検索方法を用いる。
【００１６】
【発明の実施の形態】
次に、本発明の実施の形態について図面を参照して説明する。
【００１７】
図１を参照すると、本発明の一実施形態の情報検索装置は索引作成部１と転置索引２と高頻度語抽出部３と高頻度語転置索引４と検索受付部５と適合度計算部６と検索処理部７と文書集合データベース８と文書サイズデータベース９で構成されている。
【００１８】
索引作成部１は文書集合データベース８から検索対象となる文書を入力し、該文書を特徴づける索引語を抽出し、索引語と、それら出現位置のリストを転置索引２に格納する。
【００１９】
高頻度語抽出部３は、図２に示すように、索引語と出現位置の組を転置索引２から順次読出し（ステップ１１）、索引語頻度があらかじめ決められた閾値以上になる文書に対応する出現位置を抽出し（ステップ１２）、そのような文書の数が、検索結果の上位として表示される文書数Ｔ以上（Ｔは１以上の整数）の場合には、抽出された索引語と出現位置のリストを高頻度語転置索引４に格納する（ステップ１３）。
【００２０】
検索受付部５は利用者から検索質問を受付け、検索処理部７に渡し、検索処理部７から適合文書リストを受け取り、文書集合データベース８から適合文書リスト内の文書番号に対応する文書の情報を読み出し、利用者に提示する。
【００２１】
適合度計算部６は、図３に示すように、検索処理部７から検索語の出現位置リストを受け取り（ステップ２１）、文書サイズデータベース９から文書サイズを受け取り（ステップ２２）、各文書における検索語の頻度と文書サイズから、ＴＦ・ＩＤＦ法などの計算式にしたがって文書毎に適合度を計算し（ステップ２３）、適合文書リストとして検索処理部７に出力する（ステップ２４）。検索質問が１つの検索語のみの場合（ＡＮＤ検索やＯＲ検索でない、単なる１つの言葉の検索）、文書頻度（検索語が出現する文書の数）は定数とみなせるため、適合度の計算に用いなくてもよい。すなわち、この場合「検索質問が文書とどれだけ適合するか」は「文書に含まれる索引語が文書をどれだけ強く特徴づけるか」と同じであると考えて、ＴＦ・ＩＤＦ法のような文書中の索引語の重みを計算する式で適合度を計算する。たとえば、"携帯電話"という検索語で検索し、ＴＦ・ＩＤＦ法で適合度を計算する場合、
ある文書と"携帯電話"の適合度
＝ｆi,j  ｌｏｇ（Ｎ／Ｆi）／Σiｆi,j
ここで、ｆi,jはその文書内での"携帯電話"の出現回数、Ｎは文書の総数、Ｆiは"携帯電話"が出現する文書数、Σiｆi,jはその文書における索引語頻度の総和である。
"携帯電話"という語を一定回数以上含む文書すべてについて、この適合度を計算し比較することで、どの文書がよく適合するか（"携帯電話"というトピックに強く関連した文書であるか）がわかる。Σiｆi,jはある文書ｊでのすべての索引語の索引語頻度の総和であるので、要するに文書ｊの大きさである。これは転置索引２から計算することもできるが、それでは索引全体を読み込んで集計する必要があって非効率なので、文書サイズデータベース９のように別途用意しておく。
【００２２】
図５の"検索"という語の場合、出現位置リストは（２，１００），（２，１２１），（２，２０７），（３，２４），（１９，３１）になる。つまり、"検索"という語は全体で５回出現しており、文書番号２の文書では３回、文書番号３の文書では１回、文書番号１９の文書では１回出現していることがわかる。
【００２３】
このように出現位置リストから文書ごとの索引語頻度を求めつつ、前記説明したように（ｌｏｇ（Ｎ／Ｆi）の部分は定数とみなした上で）各文書の適合度を計算する。
【００２４】
検索処理部７は、図４に示すように、まず利用者から検索受付部５を介して渡される検索語を受け取り、高頻度語転置索引４を用いて、その検索語の出現位置リストを求める（ステップ３１）。すなわち、検索語が一つの索引語のみから構成される場合には、高頻度語転置索引４からその索引語の出現位置リストを入力し、検索語が複数の索引語の並びである場合には、それぞれの索引語の出現位置リストを高頻度語転置索引４から入力し、すべての索引語が隣接して出現する位置のリストを求める。次に、高頻度語転置索引４から求められた出現位置リストが、検索結果の表示に必要なＴ個以上の文書を参照している場合には、その出現位置リストを適合度計算部６に渡し、適合文書リストを受け取る（ステップ３２，３６，３７）。そして、適合度上位Ｔ番目の文書が、高頻度語転置索引４には格納されない低頻度の文書がとり得る最大の適合度よりも大きい適合度を持つ場合は、適合度上位Ｔ個の文書が正しく検索されているので、それらを出力する（ステップ３８，３９）。たとえば、適合度の計算にＴＦ・ＩＤＦ法を用いた場合、適合度の降順でＴ番目の文書ＤTの索引語頻度がＦT、文書サイズがＳTとすると、ＦT／ＳTが（Ｆ−１）／Ｓminより大きければ、転置索引２に格納された索引語頻度（Ｆ−１）以下の文書は適合度の上位Ｔ個に入らないことが保証される。ここで、Ｓminは文書集合中で最小の文書サイズである。高頻度語転置索引４からはＴ個以上の文書を参照する出現位置リストが得られなかった場合、あるいは適合度上位Ｔ個の文書が正しく検索されていない可能性がある場合には、通常の転置索引２を用いてランキング検索処理をおこなう。すなわち、転置索引２を用いて検索語の出現位置リストを求め（ステップ３３）、それを適合度計算部６に出力し（ステップ３４）、適合度計算部６から適合文書リストを入力し（ステップ３５）、適合度の降順で上位最大Ｔ個を出力する（ステップ３９）。
【００２５】
一つ以上の検索語を用いた検索質問が与えられた場合や、適合度によるランキング検索をおこなわない場合には、通常の転置索引を使った従来通りの検索処理をおこなえばよい。本発明の方法は既存の情報検索装置に付加的に導入することが可能である。
【００２６】
日本語の文書を索引づけする場合、索引語として形態素を用いる方法、Ｎグラムを用いる方法、両者を組み合わせた方法などがあるが、本発明の方法はいずれの場合にも適用可能である。
【００２７】
本発明の方法ではあらかじめ固定された閾値Ｆを用いているが、索引語ごとに異なった閾値を設定することもできる。その場合、検索語フレーズに含まれる索引語の閾値のうち最大の値をＦmaxとすれば、ＦT／ＳTが（Ｆmax−１）／Ｓminより大きい場合に、高頻度語転置索引のみで検索できたと判断できる。
【００２８】
本発明の方法は、ＴＦ・ＩＤＦ法に限らず、索引語頻度と文書サイズを適合度計算の主要パラメータとして利用している多くの適合度計算法に適用可能である。また、適合度の計算が厳密である必要がない場合には、高頻度語転置索引でＴ個以上の文書が検索された時点で、その上位Ｔ個を検索結果としてもよい。
【００２９】
高頻度語転置索引を別途作成するかわりに、転置索引に格納する出現位置リストを索引語頻度の降順に並べておくことで、出現位置リストの先頭部分を高頻度語転置索引とみなして本発明と同様の検索処理をおこなうこともできる（非特許文献１）。ただし、そのような構成の転置索引では、本発明の方法を用いない通常の検索処理の速度が遅くなる。
【００３０】
本発明と類似した方法として、あらかじめすべての索引語でランキング検索をおこなっておき、適合文書リストの上位Ｔ個を保存しておく方法も考えられる（非特許文献２）。ただし、その方法では本発明の方法とは異なり、複数の索引語の並びであるフレーズを検索することができない。本発明の方法はこのような方法と併用することも可能である。
【００３１】
なお、本発明は専用のハードウェアにより実現されるもの以外に、その機能を実現するためのプログラムを、コンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行するものであってもよい。コンピュータ読み取り可能な記録媒体とは、フロッピーディスク、光磁気ディスク、ＣＤ−ＲＯＭ等の記録媒体、コンピュータシステムに内蔵されるハードディスク装置等の記憶装置を指す。さらに、コンピュータ読み取り可能な記録媒体は、インターネットを介してプログラムを送信する場合のように、短時間の間、動的にプログラムを保持するもの（伝送媒体もしくは伝送波）、その場合のサーバとなるコンピュータシステム内部の揮発性メモリのように、一定時間プログラムを保持しているものも含む。
【００３２】
【発明の効果】
以上説明したように、本発明によれば、単一の検索語を検索する場合に、高頻度語索引のみを使って適合度の高い文書を検索するため、従来の検索方法と比べて、データベースから主記憶上に読み出すデータ量や、適合度の計算に必要となるＣＰＵ処理時間を大幅に減らすことが可能となり、検索処理が高速化される。たとえば、ＷＷＷサーチエンジンでは検索質問の７割前後が単一の検索語のみから構成されているため、本発明による高速化の効果が大きいと期待される。
【図面の簡単な説明】
【図１】本発明の一実施形態の情報検索装置の構成を示すブロック図である。
【図２】図１の情報検索装置の高頻度語抽出部の処理を示す流れ図である。
【図３】図１の情報検索装置の適合度計算部の処理を示す流れ図である。
【図４】図１の情報検索装置の検索処理部の処理を示す流れ図である。
【図５】転置索引の一般的な構成を示す図である。
【符号の説明】
１    索引作成部
２    転置索引
３    高頻度語抽出部
４    高頻度語転置索引
５    検索受付部
６    適合度計算部
７    検索処理部
８    文書データベース
９    文書サイズデータベース
１１〜１４，２１〜２４，３１〜３９    ステップ
【図１】
2004192546.tif 000005
【図２】
2004192546.tif 000006
【図３】
2004192546.tif 000007
【図４】
2004192546.tif 000008
【図５】
2004192546.tif 000009