(57)【要約】【課題】  新規ページが追加されたときページ群のスコア計算の反復回数を減少させる技術を提供する。【解決手段】  文書検索装置１のクローラ２は、コンテンツサーバ群Ｓから電子文書群を収集して文書データベース３に格納する。スコア算出手段４は、文書データベース３に格納された各電子文書のスコアを重要度に基いて算出し、スコア情報データベース５に格納する。クラスタ生成手段７は、コンテンツサーバ群Ｓに新規追加された電子文書を追加ページデータベース６から取得し、ＵＲＬから一意に決定されるクラスタに分類する。スコア推定手段８は、前記クラスタと同一クラスタに属する電子文書のスコアの平均値を算出し、追加文書のスコアの推定値として推定値データベース９に格納する。スコア算出手段４は、スコアの推定値を用いて電子文書の追加に応じた電子文書群のスコアを再計算する。【選択図】  図１
2010211486.tif 000002
【特許請求の範囲】
【請求項１】
検索キーワードに基づき電子文書群を検索し、各電子文書について算出されたスコアを検索ランキングの一指標とする文書検索装置であって、
前記電子文書群に新規に追加された電子文書を、ＵＲＬから一意に決定されるクラスタに分類するクラスタ生成手段と、
前記電子文書群の既存文書のうち、前記クラスタと同一クラスタに属する電子文書のスコアの平均値を算出し、該平均値を前記追加文書のスコアの推定値とするスコア推定手段と、を備え、
前記電子文書の追加に伴い電子文書群のスコアに変動が生じたときに、前記推定値を利用して変動後の各電子文書のスコアを再計算する
ことを特徴とする文書検索装置。
【請求項２】
前記クラスタ生成手段は、前記追加文書を格納するデータベースを参照して前記追加文書を前記クラスタに分類し、
前記スコア算出手段は、前記推定値を格納するデータベースを参照して前記再計算を行う
ことを特徴とする請求項１記載の文書検索装置。
【請求項３】
前記スコア推定手段は、前記クラスタと同一クラスタに属する既存文書が存在しないときに、あらかじめ設定した初期値を前記スコアの推定値とする
ことを特徴とする請求項１または２のいずれか１項に記載の文書検索装置。
【請求項４】
検索キーワードに基づき電子文書群を検索し、各電子文書について算出されたスコアを検索ランキングの一指標とする文書検索方法であって、
クラスタ生成手段が、前記電子文書群に新規に追加された電子文書を、ＵＲＬから一意に決定されるクラスタに分類する第１ステップと、
スコア推定手段が、前記電子文書群の既存文書のうち前記クラスタと同一クラスタに属する電子文書のスコアの平均値を算出し、該平均値を前記追加文書のスコアの推定値とする第２ステップと、
スコア算出手段が、前記電子文書の追加に伴い電子文書群のスコアに変動が生じたときに、前記推定値を利用して変動後の各電子文書のスコアを再計算する第３ステップと、
を有することを特徴とする文書検索方法。
【請求項５】
前記第１ステップは、前記追加文書を格納するデータベースを参照して前記追加文書を前記クラスタに分類し、
前記第３ステップは、前記推定値を格納するデータベースを参照して前記再計算を行う
ことを特徴とする請求項４記載の文書検索方法。
【請求項６】
前記スコア推定手段が、前記クラスタと同一クラスタに属する既存文書が存在しないときに、あらかじめ設定した初期値を前記スコアの推定値とするステップをさらに有する
ことを特徴とする請求項４または５のいずれか１項に記載の文書検索方法。
【請求項７】
請求項１〜３のいずれか１項に記載の文書検索装置としてコンピュータを機能させることを特徴とする文書検索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電子文書群中から任意のクエリに対応する電子文書を検索する文書検索装置に関し、特に検索結果のランキングに使用される文書重要度の算出時間を削減する技術に関する。
【背景技術】
【０００２】
大量の電子文書（Ｗｅｂページ：以下ページと略する。）群を検索する文書検索システムにおいて、ページ間のリンク構造に基づく各ページの重要度（以下、スコアとする。）を算出して検索結果のランキングに利用する手法が知られている。
【０００３】
このようなページへの重要度付与手法の一例として「ページランク」が挙げられる。「ページランク」は、有益な文書から閲覧（リンク）される文書はより有益であるという考え方に基づき、リンク構造を基にＷｅｂページをスコア付けする方法である。
【０００４】
「ページランク」の算出では、ＵＲＬ（Ｕｎｉｆｏｒｍ  Ｒｅｓｏｕｒｃｅ  Ｌｏｃａｔｏｒ）を持つＷｅｂページのリンク構造を行列として保持し、大規模な反復計算を行い、収束した値をＷｅｂページの重要度として用いるため、計算コストが膨大となる。特に、新規のページが追加されてリンク構造が変化した際には、初めからページランクの再計算を行う必要があり、その都度処理時間がかかる。
【０００５】
そこで、例えば非特許文献１のようなページランクの推定方法が提案されている。この推定方法では、ページランクの再計算の際にページ全体のリンク構造ではなく、再計算を行う対象ページの近傍の部分リンク構造に着目してページランクに基づく再計算を行い、近似値を算出している。
【先行技術文献】
【特許文献】
【０００６】
【非特許文献１】Ｚｉｖ  Ｂａｒ−Ｙｏｓｓｅｆ  ａｎｄ  Ｌｉ−Ｔａｌ  Ｍａｓｈｉａｃｈ．“Ｌｏｃａｌ  Ａｐｐｒｏｘｉｍａｔｉｏｎ  ｏｆ  ＰａｇｅＲａｎｋ  ａｎｄ  Ｒｅｖｅｒｓｅ  ＰａｇｅＲａｎｋ”  Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  １７th  ＡＣＭ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  ａｎｄ  Ｋｎｏｗｌｅｄｇｅ  Ｍａｎａｇｅｍｅｎｔ（ＣＩＫＭ２００８），ｐｐ．２７９−２８８，２００８．
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、上述のような従来の手法では、追加ページの近傍の部分リンク構造を取得してスコア計算手法の反復計算を行うため、適切な近似値計算ができるとは限らないばかりか、処理コストがかかるおそれがある。
【０００８】
本発明は、このような問題を解決するためになされたものであり、新規ページが追加されたときページ群のスコア再計算の反復回数を減少させる技術を提供することを解決課題としている。
【課題を解決するための手段】
【０００９】
そこで本発明は、前記課題を解決するため、新規追加されたページをサイトやディレクトリなどの単位をクラスタとし、該追加ページの重要度を同一クラスタに属する電子文書群の平均値と推定したうえで、該推定値を用いてページ群全体のスコアを再計算する。
【００１０】
本発明の一態様は、検索キーワードに基づき電子文書群を検索し、各電子文書について算出されたスコアを検索ランキングの一指標とする文書検索装置であって、前記電子文書群に新規に追加された電子文書を、ＵＲＬから一意に決定されるクラスタに分類するクラスタ生成手段と、前記電子文書群の既存文書のうち、前記クラスタと同一クラスタに属する電子文書のスコアの平均値を算出し、該平均値を前記追加文書のスコアの推定値とするスコア推定手段と、を備え、前記電子文書の追加に伴い電子文書群のスコアに変動が生じたときに、前記推定値を利用して変動後の各電子文書のスコアを再計算する。
【００１１】
本発明の他の態様は、検索キーワードに基づき電子文書群を検索し、各電子文書について算出されたスコアを検索ランキングの一指標とする文書検索方法であって、クラスタ生成手段が、前記電子文書群に新規に追加された電子文書を、ＵＲＬから一意に決定されるクラスタに分類する第１ステップと、スコア推定手段が、前記電子文書群の既存文書のうち前記クラスタと同一クラスタに属する電子文書のスコアの平均値を算出し、該平均値を前記追加文書の推定値とする第２ステップと、スコア算出手段が、前記電子文書の追加に伴い電子文書群のスコアに変動が生じたときに、前記推定値を利用して変動後の各電子文書のスコアを再計算する第３ステップと、を有する。
【００１２】
なお、本発明は、前記文書検索装置としてコンピュータを機能させるプログラムの態様として提供してもよい。
【発明の効果】
【００１３】
本発明によれば、新規ページが追加されたときにスコア計算の反復回数が減少するため、スコア計算処理全体を高速に行うことができる。
【図面の簡単な説明】
【００１４】
【図１】本発明の実施形態に係る文書検索装置の構成図。
【図２】同  追加ページのスコア推定値算出の処理フロー。
【図３】同  追加ページのスコア推定値の算出例。
【発明を実施するための形態】
【００１５】
以下、本発明の実施形態を説明する。ここでは以前から保持しているページ集合に関してはスコアの算出が終わっているとし、新しく追加されたページのスコア、および該ページの追加によってスコアが変化する他ページのスコアをより短時間で算出しなければならない状況を想定している。
【００１６】
追加ページのスコアは、同じホストや同じディレクトリに含まれる他のページと近い値を持つと仮定する。即ち、ページを分類するクラスタの単位としてホスト、ディレクトリ、およびサイトを想定し、追加ページのスコアの推定値は、該追加ページが含まれるクラスタに既に存在する他のページのスコアの平均値とする。ここでは追加ページの推定値を少ない処理時間で推測し、スコア算出処理の反復回数を減らすことにより、スコア算出アルゴリズム全体の処理時間を削減可能としている。
【００１７】
以下、図面に基づき本発明の実施形態に係る文書検索装置を具体的に説明する。図１に示すように、文書検索装置１は、検索語（クエリ）を指示するユーザ端末Ｔおよびページ群が格納されているコンテンツサーバ群Ｓと通信可能にネットワーク接続されている。
【００１８】
前記ユーザ端末Ｔは、前記文書検索装置１と通信可能で、ユーザとのインタフェースとしてのブラウザを備えていればよく、パーソナルコンピュータ（ＰＣ）や携帯電話などのモバイル端末であってもよい。なお、図１中は省略されているが、通常は前記文書検索装置１には複数の前記ユーザ端末Ｔが接続される。
【００１９】
前記文書検索装置１は、前記コンテンツサーバ群Ｓに存在するページ群を検索するいわゆる検索エンジンとして機能し、通常のコンピュータのハードウェア資源、即ちＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｏｒ  Ｕｎｉｔ）、メモリ（ＲＡＭ）、ハードディスクドライブ装置、通信インタフェースなどを備えている。このハードウェア資源とソフトウェアとの協働の結果、前記文書検索装置１は、文書収集手段であるクローラ２，文書データベース３，スコア算出手段４，スコア情報データベース５，追加ページデータベース６，クラスタ生成手段７，スコア推定手段８，推定値データベース９を実装する。ここでは前記各データベース３．５．６．９は、ハードディスクドライブ装置上に構築されている。
【００２０】
前記クローラ２は、前記通信インタフェースを通じて前記コンテンツサーバ群Ｓにアクセスし、検索対象となるページ群を収集して前記文書データベース３に格納する。この収集処理は通常、一定期間ごとに行われる。
【００２１】
前記スコア算出手段４は、スコア計算アルゴリズムに基づいて前記文書データベース３に格納された各ページのスコアを算出する。ここでは算出したスコアと各ページの識別子であるＵＲＬとを対応づけて、前記スコア情報データベース５に格納する。なお、前記スコア情報データベース５の格納データ例を表１に示す。
【００２２】
【表１】
2010211486.tif 000003
【００２３】
前記追加ページデータベース６には、前記コンテンツサーバ群Ｓに新たに追加されたスコア未算出のページのＵＲＬが格納される。この追加ページは、前記クローラ２によってページ群が収集されたときに選別され、前記追加データベース６に格納される。なお、前記追加ページデータベース６の格納データ例を表２に示す。
【００２４】
【表２】
2010211486.tif 000004
【００２５】
前記クラスタ生成手段７は、前記追加ページデータベース６に格納された追加ページを、サイトやディレクトリなどのクラスタに分類する。
【００２６】
前記スコア推定手段８は、前記スコア情報データベース５の格納情報を基に、前記クラスタに分類された追加ページのスコアの推定値を算出し、該推定値を各追加ページのＵＲＬと対応づけて前記推定値データベース９に格納する。なお、前記推定値データベース９の格納データ例を表３に示す。
【００２７】
【表３】
2010211486.tif 000005
【００２８】
また、前記スコア算出手段４は、前記推定値データベース９に格納されたスコアの推定値を用いて、スコア計算アルゴリズムに基づく反復計算を行い、ページ群のスコアを再計算して前記スコア情報データベース５に格納する。ここで再計算されたページ群のスコアは、図示省略の検索実行手段の検索に反映される。
【００２９】
即ち、前記ユーザ端末Ｔから投入されたクエリ（検索キーワード）に基づきページ群を検索し、前記ユーザ端末Ｔに応答する検索結果のランキング（並べ替える）の一指標として各ページのスコアが利用される。以下、前記クラスタ生成手段７およびスコア推定手段８の実行するスコア推定値の算出処理を図２のフローチャートに基づき説明する。
【００３０】
Ｓ０１：まず、前記クラスタ生成手段７は、前記追加ページデータベース６から全てのレコード（追加ページ群）を読み込み、各ページを同一クラスタにまとめる。
【００３１】
クラスタの単位は、ＵＲＬによって一意に決定されるものであれば本手法を適用可能である。例えばホスト（ドメイン）、サイト、ディレクトリなどでよい。
【００３２】
ここでサイトとは、インターネットサービスを提供しているプロバイダ（ＩＳＰ）のホームページサービスやブログなどのＵＲＬの一部が一定の規則性を持つ、サービス利用者が自由に作成できるようなＷＥＢ文書群をまとめる単位である。
【００３３】
クラスタを生成する具体的な方法としては、例えば文字列検索技術のひとつであるパターンマッチングにより追加ページのＵＲＬを解析して、クラスタの単位に該当する文字列を含むページを同一クラスタにまとめればよい。なお、クラスタとしてどの単位を用いるかは、仕様に応じて予めプログラムに設定しておけばよい。
【００３４】
Ｓ０２：前記スコア推定手段８は、Ｓ０１で生成されたクラスタ群から任意のクラスタＣiを選択し、該クラスタＣiに含まれる追加ページｋを取得する。追加ページｋは単数であっても複数であってもよい。
【００３５】
Ｓ０３：前記スコア推定手段８は、前記スコア情報データベース５を参照し、クラスタＣiと同一クラスタに含まれるスコア算出済みのページが存在するか否かを確認する。存在する場合はＳ０４の処理を行い、存在しない場合はＳ０５に進む。
【００３６】
Ｓ０４：前記スコア推定手段８は、前記スコア情報データベース５からクラスタＣiと同一クラスタに含まれるページ群およびそのスコアを取得し、該取得したページ群のスコアの平均値を算出する。この平均値の算出方法は、以下の式（１）で表される。この式（１）はプログラムに定義されているものとする。
【００３７】
【数１】
2010211486.tif 000006
【００３８】
式（１）において、Ｃiはクラスタ、ｐjはクラスタＣiに含まれるページ、ｓｃｏｒｅ（ｐj）はｐjのスコアを表す。また、｜Ｃi｜はクラスタＣiに含まれるスコア計算済みページの数であり、追加ページｋの数は含まない。
【００３９】
算出したスコアの平均値ｓｃｏｒｅ（Ｃi）を、クラスタＣiに追加されたページｋのスコア推定値とする。追加ページｋが複数ある場合は、それぞれに同じ値を付与する。
【００４０】
なお、サイトをクラスタとした場合の追加ページのスコア推定例を図３に示す。ここではサイトＡに既に存在するページｍのスコア「０．４」およびページｎのスコア「０．２」から平均値「０．３」を求め、サイトＡに新たに追加されたページｋのスコア推定値としている。
【００４１】
Ｓ０５：ここではクラスタＣiと同一クラスタに含まれるページが前記スコア情報データベース５に存在しない場合、即ちクラスタＣiが新規クラスタの場合の処理を示している。
【００４２】
この場合には、前記スコア推定手段８はクラスタＣiのスコア平均値ｓｃｏｒｅ（Ｃi）として初期値ｄを付与し、該初期値ｄを追加ページｋのスコア推定値とする。追加ページｋが複数ある場合は、それぞれに同じ値ｄを付与する。
【００４３】
これにより追加ページｋが新規クラスタに分類され、推定値の基準となるスコアがない場合に対応することができる。なお、初期値ｄは、固定値としてプログラムに設定しておけばよい。
【００４４】
Ｓ０６：前記スコア推定手段８は、クラスタＣiの各追加ページｋについて算出したスコア推定値を、各ページのＵＲＬと対応付けて前記推定値データベース９に格納する。
【００４５】
Ｓ０７：前記スコア推定手段８は、スコア平均値の算出処理が終了していないクラスタＣiが残っているか否かを確認する。未処理のクラスタが残っている場合はＳ０２に戻り、全てのクラスタＣiについて処理が終了するまでＳ０２〜Ｓ０６を繰り返す。
【００４６】
このように、全てのクラスタＣiについて追加ページｋのスコア推定値を算出した後、前記スコア算出手段４は、ページｋの追加により変化したリンク構造に基づいて、追加ページｋおよび以前から前記スコア情報データベース５に保持しているページ群のスコアの再計算を行う。
【００４７】
このとき追加ページｋに対して算出されているスコア推定値をデータベース９から取得する。このスコア推定値を利用してページ群のスコアを再計算することで、再計算の過程における反復計算回数を低減させることができる。
【００４８】
これによりスコア再計算処理が高速化し、検索結果に最新のスコアを迅速に反映させることができる。再計算によりスコアが決定された追加ページｋのデータは、前記スコア情報データベース５に格納し、前記推定値データベース９から削除してもよい。
【００４９】
なお、本発明は、上記実施形態に限定されるものではなく、各請求項に記載した範囲内で適宜変形することができる。例えば、前記クラスタ生成手段７、前記スコア推定手段８、前記追加ページデータベース６、前記推定値データベース９は、必ずしも前記文書検索装置１に実装される必要はなく、前記文書検索装置１にネットワークを介して接続された図外のサーバ内にそれぞれ実装した構成であってもよい。
【００５０】
この場合には、前記スコア算出手段４は、前記通信インタフェースを介して前記スコア情報データベース５および前記推定値データベース９にアクセスして、ページ群のスコアを再計算する。
【００５１】
本発明は、前記文書検索装置１の各手段２〜９の一部もしくは全部としてコンピュータを機能させるプログラムに構成することもできる。この場合には、前記実施形態の処理ステップ（Ｓ０１〜Ｓ０７など）の全てあるいは一部をコンピュータに実行させる。
【００５２】
このプログラムは、Ｗｅｂサイトや電子メールなどネットワークを通じて提供することができる。また、前記プログラムは、ＣＤ−ＲＯＭ，ＤＶＤ−ＲＯＭ，ＣＤ−Ｒ，ＣＤ−ＲＷ，ＤＶＤ−Ｒ，ＤＶＤ−ＲＷ，ＭＯ，ＨＤＤ，Ｂｌｕ−ｒａｙ  Ｄｉｓｋ（登録商標）などの記録媒体に格納して、保存・配布することも可能である。この記録媒体は、記録媒体駆動装置（光学ドライブ装置など）を利用して読み出され、そのプログラムコード自体が前記実施形態の処理を実現するので、該記録媒体も本発明を構成する。
【符号の説明】
【００５３】
１…文書検索装置
２…クローラ
３…文書データベース
４…スコア算出手段
５…スコア情報データベース
６…追加ページデータベース
７…クラスタ生成手段
８…スコア推定手段
９…推定値データベース
Ｓ…コンテンツサーバ群
Ｔ…ユーザ端末
【図１】
2010211486.tif 000007
【図２】
2010211486.tif 000008
【図３】
2010211486.tif 000009