文書ランキングスコアの動的更新のための方法および装置
【課題】文書が追加および削除される動的ウェブ環境で文書の文書ランキングスコアを算出する方法および装置が提供される。
【解決手段】第１文書と第２文書との間の共通キーワードに対する前記第１文書の第１単語関連度スコアに基づいて前記第２文書の文書ランキングスコアを算出するステップと、前記第１単語関連度スコアを第２単語関連度スコアに動的に変更するステップと、前記第２単語関連度スコアに基づいて前記第２文書の文書ランキングスコアを更新するステップと、を含み、前記第１文書は前記第２文書へのリンクを含むことを特徴とする文書ランキング決定方法。
【解決手段】第１文書と第２文書との間の共通キーワードに対する前記第１文書の第１単語関連度スコアに基づいて前記第２文書の文書ランキングスコアを算出するステップと、前記第１単語関連度スコアを第２単語関連度スコアに動的に変更するステップと、前記第２単語関連度スコアに基づいて前記第２文書の文書ランキングスコアを更新するステップと、を含み、前記第１文書は前記第２文書へのリンクを含むことを特徴とする文書ランキング決定方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は文書ランキングスコアを算出するための方法および装置に関する。
【０００２】
本発明において、文書が追加および削除される動的ウェブ環境において文書の文書ランキングスコアを算出する方法および装置が開示される。
【背景技術】
【０００３】
ウェブ（ｗｅｂ）に存在する文書を対象に検索サービスを提供するシステム（以下、「ウェブ検索システム」と称する）は文書を収集し、文書の内容およびリンク情報などを反映して収集された文書のスコアを算出する。ウェブ検索システムは、ユーザによってクエリが入力されると、クエリと最も関連度の高い文書（または、このような文書のリスト、すなわちリンク）をユーザに提供する。
【０００４】
ウェブには数十億個以上の文書が存在し、このようなウェブ文書のうち一部は内容が変更または削除されてもよく、新しい文書が生成されたり文書そのものが削除されたりする場合もある。すなわち、ウェブ文書の状態は持続的に変化する。
【０００５】
したがって、ユーザに良好なウェブ検索サービスを提供するために、ウェブ検索システムは持続的にウェブの変化を反映してクエリに対する文書のスコアを算出し、算出の結果を短い時間内に検索結果へ反映する必要がある。
【０００６】
一般に、ウェブ検索システムは、一定の時間間隔で収集、索引、リンク情報分析、およびサービス反映などの作業を繰り返す。このような繰り返しの時間間隔は検索サービス業者ごとに異なるが、一般的には少なくとも１週間ないし２週間以内の間隔である。
【０００７】
もし、ウェブ検索システムの変更された文書が発見されるたびに文書の変更状態を検索サービスに反映してクエリとの関連度の高い文書をユーザに提供することができれば、検索サービスに対するユーザの満足度は大きく向上されるであろう。
【０００８】
検索サービスにおいて、文書のスコアは、文書の内容ベースのスコアおよびリンクベースのスコアの組合せに基づいて算出されてもよい。したがって、変更された文書が発見されるたびに短い時間内で検索結果に反映するためには文書の内容ベースのスコアおよびリンクベースのスコアを迅速に更新しなければならない。
【０００９】
文書＜ｐ＞の単語ｔに対する内容ベースのスコアは、一般的に単語頻度（Ｔｅｒｍ Ｆｒｅｑｕｅｎｃｙ；ＴＦ）および逆文書頻度（Ｉｎｖｅｒｓｅ Ｄｏｃｕｍｅｎｔ Ｆｒｅｑｕｅｎｃｙ；ＩＤＦ）値に基づいて算出される。ＴＦは文書＜ｐ＞における単語ｔの発生頻度数である。ＩＤＦは文書全体の集合で単語ｔを含む文書数の逆数である。
【００１０】
ＴＦは、文書内で単語ｔの使用頻度数を測定することによって算出される。したがって、特定文書のＴＦについては、文書全体の集合における他の文書に状態変化があっても再び算出される必要がない。
【００１１】
文書全体の集合における文書のうち１つの文書で単語ｔが追加または削除されるとＩＤＦが変更される。このような場合、単語ｔを含む全ての文書に対して内容ベースのスコアが再び算出されなければならない。
【００１２】
ウェブ検索システムは、ＩＤＦの変更による影響を最小化しながら漸次に文書の内容ベースのスコアを算出する必要がある。
【００１３】
例えば、ウェブ検索システムは与えられた単語ｔに対して、単語ｔを含む文書およびその文書数を格納した後、内容の変更された文書について単語ｔが新しく追加または削除されたかを把握することで単語ｔのＩＤＦ値を再算出してもよい。
【００１４】
単語ｔに対する従来のＩＤＦ値および新規ＩＤＦ値の差が予め設定された値以下であれば、ウェブ検索システムは従来のＩＤＦ値を用いて文書の内容ベースのスコアを算出してもよい。もし、前記値の差が予め設定された値よりも大きければ、ウェブ検索システムは単語ｔのＩＤＦ値を変更して単語ｔを含む文書の単語ｔに対する内容ベースのスコアを再算出してもよい。
【００１５】
また、ウェブ検索システムは、単語のＩＤＦ値は変化しないという仮定下でリンクベースのスコアを動的更新してもよい。
【発明の概要】
【発明が解決しようとする課題】
【００１６】
本発明の目的は、文書の内容が変更されたり文書が追加または削除されたりする場合、変更、追加、または削除された文書に関連する一部文書のみを対象に文書ランキングスコアを再算出する部分更新方法および装置を提供することである。
【００１７】
また、本発明の他の目的は、文書ランキングスコアを算出している間に文書の内容が変更されたり文書が追加または削除されたりする場合、文書の変更、追加、または削除が反映された文書ランキングスコアを算出する動的更新方法および装置を提供することである。
【課題を解決するための手段】
【００１８】
本発明の一実施形態に係る文書ランキング決定方法において、第１文書と第２文書との共通キーワードに対する第１文書の第１単語関連度スコアに基づいて第２文書の文書ランキングスコアを算出するステップと、第１単語関連度スコアを第２単語関連度スコアに動的に変更するステップと、第２単語関連度スコアに基づいて第２文書の文書ランキングスコアを更新するステップとを含み、第１文書は第２文書へのリンクを含むことを特徴とする文書ランキング決定方法が提供される。
【００１９】
第１文書と第２文書との共通キーワードに対する第１単語関連度スコアに基づいて第２文書の文書ランキングスコアを算出するステップは、共通キーワードに対する第１寄与係数および第１単語関連度スコアに基づいて第１寄与スコアを算出するステップと、第１寄与スコアを第２文書の共通キーワードに対する文書ランキングスコアに反映するステップとを含んでもよい。
【００２０】
第２単語関連度スコアに基づいて第２文書の文書ランキングスコアを更新するステップは、共通キーワードに対する第２寄与係数を算出するステップと、第１寄与係数、第１単語関連度スコア、第２寄与係数、および第２単語関連度スコアに基づいて第２寄与スコアを算出するステップと、第２寄与スコアを第２文書の文書ランキングスコアに反映するステップとを含んでもよい。
【００２１】
第１単語関連度スコアを第２単語関連度スコアに動的に変更するステップは、第１文書の内容が変更されるステップを含んでもよく、第１単語関連度スコアは、第１文書の内容が変更される前の第１文書の内容の共通キーワードに対する単語関連度スコアであり、第２単語関連度スコアは第１文書の内容が変更された後の第１文書の内容の共通キーワードに対する単語関連度スコアであってもよい。
【００２２】
第１単語関連度スコアを第２単語関連度スコアに動的に変更するステップは、第１文書の内容が生成されるステップを含んでもよく、第２単語関連度スコアは、生成された内容における共通キーワードに対する単語関連度スコアであってもよい。
【００２３】
第１単語関連度スコアを第２単語関連度スコアに動的に変更するステップは、第１文書の内容が削除されるステップを含んでもよく、第１単語関連度スコアは、第１文書の内容が削除された後の共通キーワードに対する単語関連度スコアであってもよい。
【００２４】
第１単語関連度スコアを第２単語関連度スコアに動的に変更するステップは、リンクが生成されるステップを含んでもよく、第２単語関連度スコアは、第１文書の内容の共通キーワードに対する単語関連度スコアであり、第１単語関連度スコアが第２単語関連度スコアに変更されるとみなすことによってリンクの生成を反映してもよい。
【００２５】
第１単語関連度スコアを第２単語関連度スコアに動的に変更するステップは、リンクが削除されるステップを含んでもよく、第１単語関連度スコアは、第１文書の内容の共通キーワードに対する単語関連度スコアであり、第１単語関連度スコアが第２単語関連度スコアに変更されるとみなすことによってリンクの削除を反映してもよい。
【００２６】
第１単語関連度スコアおよび第２単語関連度スコアは、第１文書の内容と共通キーワードとの間の関連性に基づいて算出されてもよい。
【００２７】
第１寄与係数および第２寄与係数は、共通キーワードにおいて第２文書が第１文書の内容に寄与する係数であってもよい。
【００２８】
文書ランキング決定方法は、第１文書が含む各単語について、第１文書の単語に対する単語関連度スコアを算出するステップと、第１文書のキーワードおよび第２文書のキーワードを抽出するステップと、第１文書と第２文書との間の共通キーワードを抽出するステップとをさらに含んでもよい。
【００２９】
文書ランキング決定方法は、第１文書への経路の開始文書である第３文書に対する、経路を通じた第１文書の寄与スコアおよび第１寄与係数に基づいて第３寄与スコアを算出するステップをさらに含んでもよい。
【００３０】
第２文書の文書ランキングスコアは、共通キーワードに対する第２文書の単語関連度スコア、第１寄与スコア、第２寄与スコア、および第３寄与スコアに基づいて決定されてもよい。
【００３１】
文書ランキング決定方法は、文書ランキングスコアに基づいて第２文書の文書ランキングを決定するステップをさらに含んでもよい。
【００３２】
また、本発明の一実施形態に係る文書ランキング決定装置において、第１文書と第２文書との間の共通キーワードに対する第１文書の第１単語関連度スコアおよび共通キーワードに対する第１文書の第２単語関連度スコアを算出する単語関連度スコア算出部と、第１単語関連度スコアを第２単語関連度スコアに変更する単語関連度スコア変更部と、第１単語関連度スコアに基づいて第２文書の文書ランキングスコアを算出し、第２単語関連度スコアに基づいて第２文書の文書ランキングスコアを更新する文書ランキングスコア算出部とを備え、第１文書は第２文書へのリンクを含むことを特徴とする文書ランキング決定装置が提供される。
【００３３】
文書ランキング決定装置は、共通キーワードに対する第１寄与係数および第２寄与係数を算出する寄与係数算出部と、第１寄与係数および第１単語関連度スコアに基づいて第１寄与スコアを算出し、第１寄与係数、第１単語関連度スコア、第２寄与係数、および第２単語関連度スコアに基づいて第２寄与スコアを算出する寄与スコア算出部とをさらに備えてもよく、文書ランキングスコア算出部は、第１寄与スコアを第２文書の共通キーワードに対する文書ランキングスコアに反映することによって第１単語関連度スコアに基づいて第２文書の文書ランキングスコアを算出し、第２寄与スコアを第２文書の文書ランキングスコアに反映することによって第２単語関連度スコアに基づいて第２文書の文書ランキングスコアを更新してもよい。
【００３４】
単語関連度スコア変更部は、第１文書の内容が変更される場合に第１単語関連度スコアを第２単語関連度スコアに変更してもよく、第１単語関連度スコアは、第１文書の内容が変更される前の第１文書の内容の共通キーワードに対する単語関連度スコアであり、第２単語関連度スコアは、第１文書の内容が変更された後の第１文書の内容の共通キーワードに対する単語関連度スコアであってもよい。
【００３５】
単語関連度スコア変更部は、第１文書の内容が生成される場合に第１単語関連度スコアを第２単語関連度スコアに変更してもよく、第２単語関連度スコアは、生成された第１文書の内容の共通キーワードに対する単語関連度スコアであってもよい。
【００３６】
単語関連度スコア変更部は、第１文書の内容が削除される場合に第１単語関連度スコアを第２単語関連度スコアに変更してもよく、第１単語関連度スコアは、第１文書の内容が削除された後の共通キーワードに対する単語関連度スコアであってもよい。
【００３７】
単語関連度スコア変更部は、リンクが生成される場合に第１単語関連度スコアが第２単語関連度スコアに変更されたものとみなすことによってリンクの生成を反映してもよく、第２単語関連度スコアは、第１文書の内容の共通キーワードに対する単語関連度スコアであってもよい。
【００３８】
単語関連度スコア変更部は、リンクが削除される場合に第１単語関連度スコアが第２単語関連度スコアに変更されたものとみなすことによってリンクの削除を反映してもよく、第１単語関連度スコアは、第１文書の内容の共通キーワードに対する単語関連度スコアであってもよい。
【００３９】
文書ランキング決定装置は、第１文書のキーワードおよび第２文書のキーワードを抽出し、第１文書と第２文書との間の共通キーワードを抽出する共通キーワード抽出部をさらに備えてもよく、単語関連度スコア算出部は、第１文書が含む各単語に対して第１文書の単語に対する単語関連度スコアを算出してもよい。
【００４０】
寄与スコア算出部は、第１文書への経路の開始文書である第３文書に対する、経路を通じた第１文書の寄与スコアおよび第１寄与係数に基づいて第３寄与スコアを算出してもよく、文書ランキングスコア算出部は、第３寄与スコアを第２文書の文書ランキングスコアに反映してもよい。
【００４１】
文書ランキングスコア算出部は、共通キーワードに対する第２文書の単語関連度スコア、第１寄与スコア、第２寄与スコア、および第３寄与スコアに基づいて第２文書の文書ランキングスコアを決定してもよい。
【００４２】
文書ランキングスコアに基づいて第２文書の文書ランキングを決定する文書ランキング決定部をさらに備えてもよい。
【発明の効果】
【００４３】
本発明の一実施形態によれば、文書の内容が変更されたり文書が追加または削除されたりする場合、変更、追加、または削除された文書に関連する一部文書のみを対象に文書ランキングスコアを再算出する部分更新方法および装置を提供することができる。
【００４４】
本発明の一実施形態によると、文書ランキングスコアを算出している間に文書の内容が変更されたり文書が追加または削除されたりする場合、文書の変更、追加、または削除が反映された文書ランキングスコアを算出する動的更新方法および装置を提供することができる。
【図面の簡単な説明】
【００４５】
【図１】本発明の一実施形態に係る文書スコア算出方法を説明するための図である。
【図２】本発明の一実施形態に係る共通キーワードに対する文書の寄与係数を算出する方法を説明するための図である。
【図３】本発明の一実施形態に係る文書ランキング決定方法を示すフローチャートである。
【図４】本発明の一実施形態に係る単語関連度スコア変更を説明するための図である。
【図５】本発明の一実施形態に係る寄与スコアの分割伝達の特性を説明するための図である。
【図６】本発明の一実施形態に係るＣ−Ｒａｎｋスコア更新の対象となる文書を説明するための図である。
【図７】本発明の一実施形態に係る動的文書ランキングの決定方法を示すフローチャートである。
【図８】本発明の一実施形態に係る文書ランキング決定装置の構造図である。
【発明を実施するための形態】
【００４６】
以下、本発明の一実施形態を添付する図面を参照しながら詳説する。本発明は実施形態によって制限されたり限定されたりすることはない。各図面に提示された同じ参照符号は同じ部材を示す。本発明の一実施形態に係る文書ランキング決定方法は文書ランキング決定システムの各構成によって行われてもよい。
【００４７】
Ｃ−Ｒａｎｋベースの文書ランキング決定方法は、各文書について単語ごとに単語関連度スコアおよび寄与スコアを算出し、算出された単語関連度スコアおよび寄与スコアの組合せに基づいて文書のランキングを決定する方法である。
【００４８】
単語関連度スコアは、単語に対する文書の内容に基づいて決定される情報である。寄与スコアは、単語に対する文書のリンク情報に基づいて決定される情報である。すなわち、上記方法はリンクに接続された文書間の関係を考慮してリンクに基づいた寄与スコアを算出する特徴を有する。
【００４９】
各文書は各単語に対するＣ−Ｒａｎｋスコアを有する。単語ｔに対する文書＜ｐ＞のＣ−Ｒａｎｋスコアは、文書＜ｐ＞の単語ｔに対する単語関連度スコアおよび寄与スコアを組合せることによって算出される。
【００５０】
Ｃ−Ｒａｎｋベースの文書ランキング決定方法は、ユーザによってクエリが入力される前に各文書に対して文書に含まれる単語に対するＣ−Ｒａｎｋスコアを算出する。クエリが１つ以上の単語で構成された場合、本方法においては文書の単語それぞれに対するＣ−Ｒａｎｋスコアを合算することによってクエリに対する文書のスコアを算出してもよい。
【００５１】
図１は、本発明の一実施形態に係る文書スコア算出方法を説明するための図である。
【００５２】
図１に示すように、文書＜Ｘ＞１００とリンクに接続された文書＜Ｙ１＞１１０、文書＜Ｚ１＞１２０、文書＜Ｙ２＞１３０および文書＜Ｚ２＞１４０が示された。ここで、文書＜Ｘ＞１００、文書＜Ｙ１＞１１０および文書＜Ｚ１＞１２０は単語Ａ１５０を含み、文書＜Ｘ＞１００、文書＜Ｙ２＞１３０および文書＜Ｚ２＞１４０は単語Ｂ１６０を含む。
【００５３】
単語Ａ１５０は文書＜Ｘ＞１００、文書＜Ｙ１＞１１０および文書＜Ｚ１＞１２０に共通に含まれた共通キーワードであり、単語Ｂ１６０は文書＜Ｘ＞１００、文書＜Ｙ２＞１３０および文書＜Ｚ２＞１４０に共通に含まれた共通キーワードである。すなわち、共通キーワードはリンクに接続された文書に共通して含まれたキーワードである。各文書は１つ以上の共通キーワードを含んでもよい。
【００５４】
単語Ａ１５０および単語Ｂ１６０はユーザが入力したクエリに含まれた単語であってもよい。
【００５５】
本発明の一実施形態に係る文書ランキング決定方法は、単語それぞれに対する文書のランキングを決定してもよい。文書ランキング決定方法は、文書内容およびリンク情報を組合せて単語に対する文書のランキングを決定してもよい。
【００５６】
具体的に、文書ランキング決定方法は、文書に含まれた少なくとも１つの単語それぞれに対する文書の単語関連度スコアと単語を共通に含む他の文書の活用度を示す寄与スコアとを組合せて文書ランキングを決定してもよい。
【００５７】
一実施形態として、文書のランキングを決定する場合に次のような基本概念を予め定義してもよい。
【００５８】
（１）重要文書の基準
文書が生成される場合、ユーザに提供しようとする主要情報で本文を構成してもよい。また、文書の本文に対する詳細説明や本文に関連する追加情報は他の文書をリンクに接続する方式により提供されてもよい。ここで、リンクに接続された文書（例えば、文書＜Ｙ１＞１１０および文書＜Ｙ２＞１３０）とはリンクを含む文書（例えば、文書＜Ｘ＞１００）のような主要情報について説明している文書であってもよく、または他の文書における主要情報に関する細部事項を補完説明する文書であってもよく、または単語（例えば、単語Ａ１５０および単語Ｂ１６０）の詳細説明の文書であってもよい。または場合に応じて、リンクに接続された文書はリンクを含む文書と全く関係のない文書（例えば、文書の内容と関係のない広告）であってもよい。
【００５９】
文書の内容は文書の品質を評価するときの重要な要素であってもよい。ユーザは所望する内容を含む高品質の文書が検索結果として示されることを期待してもよい。また、文書ランキング決定方法または装置は文書の本文の品質に寄与する重要文書をリンクとして接続してもよい。
【００６０】
本発明の一実施形態に係る文書ランキング決定システムは、次のような条件を満たす文書を重要文書であると規定してもよい。１）与えられた単語に対する単語関連度スコアが高い文書、２）与えられた単語に対する単語関連度スコアが高い文書とリンクにより接続された文書、３）リンクによって自身の情報を多く活用する文書に接続された文書。
【００６１】
（２）リンクに接続された文書の寄与スコア
リンクに接続された文書（例えば、文書＜Ｙ１＞１１０、文書＜Ｙ２＞１３０）がリンクを含む文書（例えば、文書＜Ｘ＞１００）に対する寄与スコアは与えられたクエリに対する２つの文書の単語関連度スコアに基づいて決定されてもよい。
【００６２】
与えられたクエリに対する２つの文書の関連度が高いほど、リンクに接続された文書はリンクを含む文書の品質に大きく寄与する。ただし、リンクを含む文書は検索クエリに対して高い関連度を有するもののリンクに接続された文書は検索クエリに対して低い関連度を有する場合、リンクに接続された文書はリンクを含む文書の品質に寄与しない場合がある。
【００６３】
（３）ランキングに応じたユーザの関心度
検索結果においては、文書の相対的なランキングが重要であり、ユーザは自身が所望する情報が検索結果を表示するページの１ページ目に表示されることを所望する。例えば、文書ランキング決定システムが上位１０位までに該当する文書を１ページ目に表示する場合、ユーザはそれら表示される文書に対して敏感であるが、ランキングが２００位から３００位までの間に位置する文書については、それらの文書をいずれも重要ではないものとして、その間のランキングの差に関心を示さないことが考えられる。
【００６４】
したがって、本発明の一実施形態に係る文書ランキング決定システムは、予め設定したランキング上において上位に該当する文書の相対的なランキングをランキング上において下位に該当する文書よりもさらに正確に決定することができる。ランキング上、上位に該当する文書について、相対的なランキングを正確に決定すればユーザは検索結果に満足することができ、それ以上に多くの文書に対して正確なランキングを決定する必要がないため、検索結果を導き出すために要求されるリソースを節約することができる。
【００６５】
このような基本概念に基づいて、本発明の一実施形態に係る文書ランキング決定方法または装置は、単語Ａ１５０に対して文書＜Ｘ＞１００、文書＜Ｙ１＞１１０および文書＜Ｚ１＞１２０の単語関連度スコアおよび寄与スコアを算出し、算出された単語関連度スコアおよび寄与スコアを組合せることによって、単語Ａ１５０に対する文書間の文書ランキングを決定するためのＣ−Ｒａｎｋスコアを算出してもよい。
【００６６】
また、本発明の一実施形態に係る文書ランキング決定方法またはシステムは、単語Ｂ１６０に対して文書＜Ｘ＞１００、文書＜Ｙ２＞１３０および文書＜Ｚ２＞１４０の単語関連度スコアおよび寄与スコアを算出し、算出された単語関連度スコアおよび寄与スコアを組合せることによって単語Ｂ１６０に対する文書間の文書ランキングを決定するためのＣ−Ｒａｎｋスコアを決定してもよい。最終的に、決定された文書ランキングは、文書および単語の対に対して決定された文書ランキングスコアを昇順または降順に配列することによって決定されてもよい。（例えば、ＣＡ（Ｘ）など）
【００６７】
【数１】
【００６８】
【００６９】
【００７０】
【００７１】
図２は、本発明の一実施形態に係る共通キーワードに対する文書の寄与係数を算出する方法を説明するための図である。
【００７２】
本実施形態において、寄与係数は第２文書が第１文書の内容に寄与する係数を意味する。第１文書および第２文書の共通キーワードに対して第１文書の第２文書に対する寄与係数が決定される。
【００７３】
【００７４】
【数２】
【００７５】
【００７６】
ｔ２５０は単語を意味する。
【００７７】
【００７８】
【００７９】
【００８０】
数２から分かるように、第１文書＜ｐ＞２４０の第２文書＜ｑ＞２１０に対する寄与係数に第２文書＜ｑ＞２１０の内容スコアを適用することによって第１文書＜ｐ＞２４０の寄与スコアが算出されてもよい。
【００８１】
図２に示すように、第２文書（文書＜ｑ＞２１０）から第１文書（文書＜ｐ＞２４０）に達する複数のステップのリンクを含むリンク経路が存在する場合、リンク経路に対応する文書（文書＜ｒ１＞２２０〜文書＜ｒｄ−１＞２３０）の寄与係数を用いることによって第１文書の第２文書に対する寄与係数を決定してもよい。
【００８２】
寄与係数は下記の数３によって決定されてもよい。
【数３】
【００８３】
【００８４】
また、リンク経路に対応する文書の寄与係数は、リンク経路上で隣接する文書間の寄与係数（例えば、ｒ１→ｒ２のリンクでｒ２のｒ１に対する寄与係数）を用いて決定されてもよい。
【００８５】
本発明の一実施形態によると、第１文書および第２文書が１つのリンクに接続される場合、第１文書の内容スコア、第２文書の内容スコア、および第２文書のアウトリンクに対応する第３文書の内容スコアを用いることによって第１文書の第２文書に対する寄与係数を決定してもよい。
【００８６】
第１文書および第２文書が１つのリンクに接続される場合、第１文書の第２文書に対する寄与係数は下記の数４によって決定されてもよい。
【数４】
【００８７】
【００８８】
【００８９】
【００９０】
【００９１】
例えば、文書＜ｐ＞、文書＜ｑ＞および文書＜ｒ＞がｒ→ｑ→ｐのようにリンクに接続された場合、このようなリンクに対して図２の説明を適用すると次の通りである。
【００９２】
【００９３】
【００９４】
図３は、本発明の一実施形態に係る文書ランキング決定方法を示すフローチャートである。
【００９５】
本実施形態の文書ランキング算出方法は、初期化ステップＳ３１０ないしステップＳ３３０およびスコア伝達ステップＳ３４０ないしステップＳ３８０に分類されてもよい。
【００９６】
【００９７】
【００９８】
ステップＳ３２０において、各文書＜ｐ＞について、文書＜ｐ＞のキーワードが抽出される。
【００９９】
ステップＳ３２２において、各文書＜ｐ＞について、文書＜ｐ＞および文書＜ｐ＞がリンクに示す各文書＜ｑ＞間の共通キーワードが抽出される。
【０１００】
【０１０１】
【０１０２】
【０１０３】
【０１０４】
【０１０５】
【０１０６】
【０１０７】
【０１０８】
【０１０９】
【０１１０】
ステップＳ３８０において、全ての文書に伝達した寄与スコアが０であれば（または伝達された全ての寄与スコアが０であれば）手続きを終了し、そうでなければステップＳ３５０が繰り返される。
【０１１１】
図４は、本発明の一実施形態に係る単語関連度スコア変更を説明するための図である。
【０１１２】
【０１１３】
図１から図３を参照して前述した文書ランキング算出方法は静的な算出方法であり、動的な算出方法においては、静的な算出方法で用いられた記号や式に時点Ｔが追加されてもよい。Ｔは０以上の整数である。
【０１１４】
【０１１５】
【０１１６】
【０１１７】
【０１１８】
【０１１９】
【０１２０】
【０１２１】
【０１２２】
単語関連度スコアの変更によるＣ−Ｒａｎｋスコアの更新は２種類に区分されてもよい。
【０１２３】
（１）部分更新はＣ−Ｒａｎｋスコアが完全に算出された後、単語関連度スコアが変更される場合に行われるものである。
【０１２４】
文書間のリンク構造は変更されないものと仮定する。
【０１２５】
【０１２６】
【０１２７】
（２）動的更新はＣ−Ｒａｎｋスコアを算出している際に、単語関連度スコアが変更される場合に行われるものである。
【０１２８】
文書間のリンク構造は変更されないものと仮定する。
【０１２９】
【０１３０】
【０１３１】
下記では、時点Ｔ、Ｃ−Ｒａｎｋスコアおよび寄与スコア間の関係について説明する。
【０１３２】
数１によると、単語ｔに対する文書＜ｐ＞のＣ−Ｒａｎｋスコアは、単語ｔに対する文書＜ｐ＞の単語関連度スコアおよび文書＜ｐ＞の他の文書に対する寄与スコアの加重和である。
【０１３３】
時点Ｔである場合、文書＜ｐ＞の単語関連度スコア、寄与スコア、およびＣ−Ｒａｎｋスコアが算出されていると仮定する。これによって、時点がＴ＋１である場合に単語ｔに対する文書＜ｐ＞のＣ−Ｒａｎｋスコアは下記の数５のように表してもよい。
【数５】
【０１３４】
【０１３５】
前述の部分更新および動的更新は文書の内容が変更されたり文書が削除または追加されたりする場合に変更、削除、または追加された文書によってＣ−Ｒａｎｋスコアが影響の受けた文書のみを対象にＣ−Ｒａｎｋスコアの更新を行う。
【０１３６】
したがって、部分更新および動的更新により、動的に変化するウェブ環境をＣ−Ｒａｎｋスコアへと素早く反映することができる。
【０１３７】
また、ウェブなど文書ランキング決定を要する環境においては、持続的に文書が追加および削除されるため、部分更新および動的更新方法に基づいて算出されたＣ−Ｒａｎｋスコアは静的算出方法に基づいて算出されたＣ−Ｒａｎｋスコアよりも、より実際のウェブ環境をさらに効率よく反映することができる。
【０１３８】
図５は、本発明の一実施形態に係る寄与スコアの分割伝達の特性を説明するための図である。
【０１３９】
【０１４０】
前述したように、各文書は自身の単語関連度スコアにアウトリンクの寄与係数を乗算することによって寄与スコアを生成し、生成された寄与スコアをアウトリンクが示す文書に伝達する。
【０１４１】
寄与スコアを伝達された文書は、伝達された寄与スコアにアウトリンクの寄与係数を乗算してアウトリンクが示す文書に伝達される。すなわち、寄与スコアは、経路の寄与係数に寄与スコアを付与する文書の単語関連度スコアを乗算することによって生成される。
【０１４２】
このような寄与スコアの生成および伝達過程は、伝達する寄与スコアが一定の値以下になるか、あるいは寄与スコアの伝達回数が一定の回数に達するまで繰り返されてもよい。
【０１４３】
【０１４４】
まず、文書＜ｐ＞５１０は、算出された寄与スコアの半分５５０を第１反復ステップ（例えば、スコア伝達ステップＳ３４０ないしＳ３８０の最初の実行ステップ）で文書＜ｑ＞５２０に伝達し、残りの半分５６０を第２反復ステップに追加伝達する場合について説明する。
【０１４５】
【０１４６】
結果的に、文書＜ｐ＞５１０が寄与スコアを分割して伝達しても、反復算出の過程が完了したときの文書＜ｑ＞５２０の文書＜ｐ＞５１０に対する寄与スコアは一定である。
【０１４７】
したがって、静的な算出の過程において文書＜ｐ＞の寄与スコア（文書＜ｐ＞の単語関連度スコアによって生成された寄与スコアまたは文書＜ｐ＞に伝達された寄与スコア）が分割され（分割された寄与スコアの総和は本来の寄与スコアと同一である）、分割された寄与スコアが数回に分割してアウトリンクが示す文書に伝達されても、静的な算出方法が完了したときに文書それぞれに伝達された寄与スコアは変わらない。
【０１４８】
次に、文書＜ｐ＞５１０は、算出された寄与スコアの２倍の値を示す値５７０を第１反復ステップにおいて文書＜ｑ＞５２０に伝達し、算出された寄与スコアに−１を乗算した値５８０を第２反復ステップに伝達する場合について説明する。
【０１４９】
【０１５０】
【０１５１】
すなわち、文書＜ｐ＞５１０が多すぎる寄与スコアを文書＜ｑ＞５２０に伝達した後、これを相殺する程の負の寄与スコアを文書＜ｑ＞５２０に伝達しても、反復算出の過程が完了したときに文書＜ｑ＞５２０の文書＜ｐ＞５１０に対する寄与スコアは一定である。
【０１５２】
また、ｏ→ｐ→ｑのリンク構造において、文書＜ｐ＞が文書＜ｏ＞から伝達された寄与スコアを分割して文書＜ｑ＞に伝達しても、最終的な文書＜ｑ＞の文書＜ｏ＞に対する寄与スコアは同じ値を有する。
【０１５３】
前述したように、寄与スコアが正の数及び負の数に分割されて伝達されても、分割されて伝達された寄与スコアの総和が本来の分割される前の寄与スコアと同一であれば、本来の寄与スコアが伝達されたものと同じ結果となる。このような寄与スコアの特性を分割伝達の特性と称する。
【０１５４】
分割伝達の特性を活用すると、前述した部分更新および動的更新は静的な算出の中間過程であると解釈してもよい。
【０１５５】
【０１５６】
【０１５７】
【０１５８】
【０１５９】
【数６】
【０１６０】
【０１６１】
【０１６２】
【０１６３】
【０１６４】
（１）スコア伝達反復作業を中断する。
（２）各リンクの寄与係数を更新する。
（３）各文書は数６によって算出された追加寄与スコアを伝達する。
（４）スコア伝達反復作業を再開する。
【０１６５】
図６は、本発明の一実施形態に係るＣ−Ｒａｎｋスコア更新の対象となる文書を説明するための図である。
【０１６６】
文書＜ｐ＞６１０の単語関連度スコアが更新されるときに、寄与係数が変更されるリンクは文書＜ｐ＞６１０のアウトリンク６５０および文書＜ｐ＞６１０を示す文書６２０、６３０のアウトリンク６６０、６７０である。
【０１６７】
数６によると、単語関連度スコアが変更されることなくアウトリンクの寄与係数が変わらない文書は、追加伝達する寄与スコアがない。したがって、寄与スコアを追加伝達する文書は、単語関連度スコアが変更された文書および単語関連度スコアが変更された文書をリンクで示す文書に制限される。このような文書を追加寄与スコア伝達文書と称する。
【０１６８】
文書の内容が変更されながら時点Ｔ＋１に新しいリンクｐ→ｑ６８０が追加された場合について説明する。
【０１６９】
【０１７０】
文書の内容が変更されながら時点Ｔ＋１に既存リンクｐ→ｑ６８０が削除された場合について説明する。
【０１７１】
【０１７２】
したがって、リンクの追加および削除によるＣ−Ｒａｎｋスコアの部分更新および動的更新は、前述の文書の単語関連度スコア変更による動的更新と同じ方法に基づいて処理されてもよい。
【０１７３】
新しい文書が追加されるのは、既に生成されていたが、本文の内容がなかったため全ての単語関連度スコアが０であった文書に本文が追加されることで単語関連度スコアが変更された場合である。
【０１７４】
従来の文書が削除されるのは、文書の本文が削除されて全ての単語関連度スコアが０になった場合である。
【０１７５】
したがって、文書の追加および削除による動的更新は、文書の単語関連度スコア変更による動的更新と同じ方法に基づいて処理されてもよい。
【０１７６】
図７は、本発明の一実施形態に係る動的文書ランキングの決定方法を示すフローチャートである。
【０１７７】
本実施形態における動的文書ランキングの決定方法は、前処理ステップＳ７００ないしＳ７４４、反復作業ステップＳ７５０ないしＳ７９２、および文書ランキング算出ステップＳ７９４に区分してもよい。
【０１７８】
図７に示される本実施形態の動的文書ランキングの決定方法および図３を参照して前述した文書ランキング決定方法との差異について説明すると、本実施形態に係る動的文書ランキングの決定方法は、文書の追加または削除が発生したり、文書の内容が変更されたりすることによる変更された寄与スコアを算出する方法、およびこのような寄与スコアを文書ランキングスコアに反映する方法が追加された点で図３を参照して前述した文書ランキングの決定方法と異なる。
【０１７９】
まず、前処理ステップＳ７００ないしステップＳ７４４について説明する。
【０１８０】
ステップＳ７００において、時点Ｔが０に初期化される。
【０１８１】
ステップＳ７１０において、各文書＜ｐ＞が含んでいる各単語ｔに対する文書の単語関連度スコアが算出される。以下、本ステップＳ７１０で算出された文書の単語関連度スコアを第１単語関連度スコアと称する。例えば、第１文書が第１単語を含むと、第１文書の第１単語に対する第１単語関連度スコアが算出される。
【０１８２】
ステップＳ７２０において、各文書＜ｐ＞の各単語ｔに対する初期Ｃ−Ｒａｎｋスコアが指定（すなわち、算出および設定）される。初期Ｃ−Ｒａｎｋスコアは、ステップＳ７１０で算出された単語関連度スコアに加重値λを乗算した値である。
【０１８３】
ステップＳ７３０において、各文書＜ｐ＞からキーワードが抽出される。キーワードは、例えば、第１文書が含む第１単語のように各文書＜ｐ＞が含む各単語ｔのうちの一部である。
【０１８４】
ステップＳ７３２において、各リンクｌに対してリンクｌに接続された２つの文書間の共通キーワードが抽出される。例えば、第１文書が第１リンクを含み、第１リンクは第１文書から第２文書へのリンクであれば、第１文書および第２文書の共通キーワードが抽出される。
【０１８５】
ステップＳ７４０において、リンクに接続された２つの文書間の各共通キーワードに対して２つの文書間の寄与係数が算出される。算出された寄与係数は２つの文書を接続するリンクのキーワードに対する寄与係数であってもよい。以下、本ステップＳ７４０で算出された寄与係数を第１寄与係数と称する。例えば、リンクに接続された第１文書および第２文書の共通キーワードがあれば、第１文書と第２文書との間の共通キーワードに対する第１寄与係数が算出される。
【０１８６】
【０１８７】
【０１８８】
次に、反復作業ステップＳ７５０ないしＳ７９２について説明する。反復作業ステップＳ７５０ないしＳ７９２において、寄与スコアを伝達するためのステップＳ７５０ないしＳ７５２、および追加伝達寄与スコアを伝達するためのステップＳ７６０ないしＳ７６８が行われ、これらステップが行われた後に寄与スコアを算出するためのステップＳ７７０ないしＳ７９２が行われる。
【０１８９】
寄与スコアを伝達するためのステップＳ７５０ないしＳ７５２について説明する。
【０１９０】
【０１９１】
【０１９２】
【０１９３】
【０１９４】
次に、追加伝達寄与スコアを伝達するためのステップＳ７６０ないしＳ７６８を説明する。
【０１９５】
追加伝達寄与スコアを伝達するためのステップは、１つ以上の文書で追加伝達寄与スコアが発生する場合に実行されるステップである。文書の単語関連度が変更されると、既に伝達された寄与スコアは、変更された単語関連度および変更された寄与係数を正しく反映することができない。したがって、変更に応じて発生した寄与スコアの差を補正するために追加伝達寄与スコアが伝達される。
【０１９６】
ステップＳ７６０において、単語関連度が変更された文書が存在するか否かが検出される。もし、単語関連度が変更された文書がなければ、ステップＳ７７０を実行する。
【０１９７】
文書の単語関連度は下記の（１）〜（５）のような場合に変更されてもよい。
【０１９８】
（１）文書の内容が変更される場合に、文書の単語関連度が変更されてもよい。ここで、変更前の文書の単語関連度スコアは、ステップＳ７１０で算出された第１単語関連度スコアであってもよい。変更された内容に応じて文書の単語関連度スコアが変更される。
【０１９９】
（２）文書または文書の内容が生成される場合に、文書の単語関連度が変更されてもよい。ここで、変更前の文書の単語関連度スコアは０であってもよい。生成された文書の内容または生成された内容に応じて文書の単語関連度スコアが変更される。
【０２００】
（３）文書または文書の内容が削除される場合に、文書の単語関連度が変更されてもよい。ここで、変更前の文書の単語関連度スコアは、ステップＳ７１０で算出された第１単語関連度スコアであってもよい。文書または文書の内容が削除されることによって文書の単語関連度スコアは０に変更されてもよい。
【０２０１】
（４）両文書間のリンクが生成される場合に、文書の単語関連度が変更されたとみなしてもよい。
【０２０２】
第１文書から第２文書へのリンクが新しく生成されると、寄与スコアが伝達されていない第２文書へと新たに寄与スコアを伝達しなければならない。第１文書の単語関連度が変更されたものとみなすことによって、単語関連度の変更に応じて生成された追加伝達寄与スコアを第２文書に伝達してもよい（文書の単語関連度は文書に関連するリンクとは関係ない）。ここで、ステップＳ７１０で算出された第１単語関連度スコアは０であってもよい。また、変更された単語関連度スコアは第１文書の内容の単語に対する単語関連度スコアであるとみなしてもよい。
【０２０３】
（５）両文書間のリンクが削除される場合に、文書の単語関連度が変更されたとみなしてもよい。
【０２０４】
第１文書から第２文書へのリンクが削除されると、既に第２文書に伝達された寄与スコアは、消滅することとなる。第１文書の単語関連度が変更されたものとみなすことによって、単語関連度の変更に応じて生成された負の追加伝達寄与スコアを第２文書に伝達してもよい（文書の単語関連度は文書に関連するリンクとは関係ない）。ここで、ステップＳ７１０で算出された第１単語関連度スコアは、第１文書の内容の単語に対する単語関連度スコアであるとみなしてもよい。また、変更された単語関連度スコアは０であるとみなしてもよい。
【０２０５】
以下、変更された文書の単語関連度スコアを第２単語関連度スコアと称する。
【０２０６】
単語関連度が変更された文書＜ｐ＞に対して下記のステップＳ７６２ないしステップＳ７６８を実行する。
【０２０７】
【０２０８】
【０２０９】
【０２１０】
【０２１１】
すなわち、ステップＳ７６６およびステップＳ７６８において、単語関連度スコアの変更された第１文書の追加寄与スコアが第１文書およびリンクに接続された第２文書に伝達され、伝達された第１文書の追加寄与スコアが第２文書の累積スコアに加えられる。
【０２１２】
寄与スコアを算出するためのステップＳ７７０ないしステップＳ７９２について説明する。
【０２１３】
【０２１４】
【０２１５】
【０２１６】
第３寄与スコアは次のように実行される時点Ｔが１大きい反復作業ステップＳ７５０ないしＳ７９２で文書＜ｑ＞に伝達される。
【０２１７】
すなわち、第３文書および第１文書が第３文書から第１文書へのリンクに接続されたとき、すなわち、第３文書は第１文書を表す経路の開始文書であるとき、第３文書の寄与スコアは今回の反復作業ステップＳ７５０ないしＳ７９２で第１文書に伝達され、伝達された第３文書の寄与スコアに基づいて生成された第３寄与スコアが次の反復作業ステップＳ７５０ないしＳ７９２で第１文書と接続された第２文書に伝達される。したがって、第３文書に対する、前述した経路を介する第１文書の寄与スコアおよび第１寄与係数に基づいて第３寄与スコアが算出される。
【０２１８】
ステップＳ７９２において、全ての文書が伝達する寄与スコアが０であるか否かが検出される。
【０２１９】
伝達される全ての寄与スコアのうち０でないものがあれば、反復作業ステップＳ７５０ないしＳ７９２を再び繰り返す。すなわち、ステップＳ７５０およびステップＳ７６０が再び実行される。
【０２２０】
伝達される全ての寄与スコアが０であれば、これ以上反復作業ステップＳ７５０ないしＳ７９２を繰り返す必要がない。したがって、ステップＳ７９４が実行される。
【０２２１】
【０２２２】
【０２２３】
図８は、本発明の一実施形態に係る文書ランキング決定装置の構造図である。
【０２２４】
文書ランキング決定装置８００は、寄与係数算出部８１０、単語関連度スコア算出部８２０、寄与スコア算出部８３０、単語関連度スコア変更部８４０、および文書ランキングスコア算出部８５０を備える。文書ランキング決定装置８００は、共通キーワード抽出部８６０、文書ランキング決定部８７０、および格納部８８０をさらに備えてもよい。
【０２２５】
寄与係数算出部８１０は前述の寄与係数を算出する。例えば、寄与係数算出部は、ステップＳ７４０の第１寄与係数およびステップＳ７６２の第２寄与係数を算出してもよい。
【０２２６】
単語関連度スコア算出部８２０は前述の単語関連度を算出する。例えば、単語関連度算出部８２０は、ステップＳ７１０の第１単語関連度スコアおよびステップＳ７６０の第２単語関連度スコアを算出してもよい。
【０２２７】
寄与スコア算出部８３０は前述の寄与スコアを算出する。例えば、寄与スコア算出部８３０は、ステップＳ７４４の第１寄与スコア、ステップＳ７６２の第２寄与スコア、およびステップＳ７９０の第３寄与スコアを算出してもよい。
【０２２８】
単語関連度スコア変更部８４０は、文書の単語に対する単語関連度スコアを変更する。例えば、単語関連度スコア変更部８４０は、ステップＳ７６０で説明された単語関連度の変更原因（１）〜（５）が発生した文書の単語関連度スコアをステップＳ７１０の第１単語関連度スコアからステップＳ７６０の第２単語関連度スコアに変更してもよい。
【０２２９】
単語関連度スコア変更部８４０は、単語関連度スコアが変更された文書の単語関連度スコアを再算出することを単語関連度スコア算出部８２０に要求してもよい。
【０２３０】
文書ランキングスコア算出部８５０は前述の文書ランキングスコアを算出する。
【０２３１】
文書ランキングスコア算出部８５０は、第１単語関連度スコアに基づいて第２文書の文書ランキングスコアを算出してもよく、第２単語関連度スコアに基づいて第２文書の文書ランキングスコアを更新してもよい。
【０２３２】
文書ランキングスコア算出部８５０は、ステップＳ７４４の第１寄与スコアを第２文書の共通キーワードに対する文書ランキングスコアに反映することによって第１単語関連度スコアに基づいて第２文書の文書ランキングスコアを算出してもよく、ステップＳ７６２の第２寄与スコアを第２文書の文書ランキングスコアに反映することによって第２単語関連度スコアに基づいて第２文書の文書ランキングスコアを更新してもよい。
【０２３３】
例えば、文書ランキングスコア算出部８５０は、ステップＳ７４４の第１寄与スコア、ステップＳ７６２の第２寄与スコア、およびステップＳ７９０の第３寄与スコアに基づいてステップＳ７７０の文書ランキングスコアを算出してもよい。
【０２３４】
文書ランキングスコア算出部８５０は、文書の単語に対するステップＳ７１０の第１文書関連度スコア、ステップＳ７４４の第１寄与スコア、ステップＳ７６２の第２寄与スコア、およびステップＳ７９０の第３寄与スコアに基づいて文書の単語に対する文書ランキングスコアを決定してもよい。
【０２３５】
共通キーワード抽出部８６０は、リンクに接続された２つの文書間の共通キーワードを抽出する。例えば、共通キーワード抽出部はステップＳ７３２の共通キーワードを抽出してもよい。
【０２３６】
文書ランキング決定部８７０は、文書ランキングスコア算出部８５０によって算出された文書の単語に対する文書ランキングスコアに基づいて文書の単語に対する文書ランキングを決定してもよい。
【０２３７】
格納部８８０は、前述した文書ランキング決定装置８００の他の構成要素８１０ないし８７０の動作に必要なデータを格納および提供する。例えば、格納部８８０は、文書、リンク、寄与係数、寄与スコア、単語関連度スコア、文書ランキングスコア、および文書ランキングなどを管理するために必要なデータ構造を格納する。
【０２３８】
上記の図１ないし図７を参照して説明された本発明の一実施形態に係る技術的内容が本実施形態にもそのまま適用されてもよい。したがって、本詳細な説明は以下では省略することにする。
【０２３９】
文書ランキング決定装置８００の構成要素８１０ないし８８０の機能の一部または全部は単一な制御部（図示せず）で行われてもよい。制御部は単一または複数のプロセッサであってもよく、ネットワークによって接続された分散処理システムであってもよい。構成要素８１０ないし８８０は制御部で行われるサービス、プロセス、スレッド、モジュール、ライブラリ、および関数を表してもよい。
【０２４０】
本発明の一実施形態に係る方法は多様なコンピュータ手段を介して様々な処理を実行することができるプログラム命令の形態で実現され、コンピュータ読取可能な記録媒体に記録されてもよい。コンピュータ読取可能な媒体は、プログラム命令、データファイル、データ構造などのうちの１つまたはその組合せを含んでもよい。媒体に記録されるプログラム命令は、本発明の目的のために特別に設計されて構成されたものでもよく、コンピュータソフトウェア分野の技術を有する当業者にとって公知のものであり、使用可能なものであってもよい。コンピュータ読取可能な記録媒体の例としては、ハードディスク、フロッピー（登録商標）ディスク及び磁気テープのような磁気媒体、ＣＤ−ＲＯＭ、ＤＶＤのような光記録媒体、光ディスクのような光磁気媒体、及びＲＯＭ、ＲＡＭ、フラッシュメモリなどのようなプログラム命令を保存して実行するように特別に構成されたハードウェア装置が含まれてもよい。プログラム命令の例としては、コンパイラによって生成されるような機械語コード（ｍａｃｈｉｎｅ ｃｏｄｅ）だけでなく、インタプリタなどを用いてコンピュータによって実行され得る高級言語コード（ｈｉｇｈｅｒ ｌｅｖｅｌ ｃｏｄｅ）を含む。上述したハードウェア装置は、本発明の動作を行うために１つ以上のソフトウェアのレイヤで動作するように構成されてもよい。
【０２４１】
上述したように、本発明を限定された実施形態と図面によって説明したが、本発明は、上記の実施形態に限定されることなく、本発明が属する分野における通常の知識を有する者であれば、このような実施形態から多様な修正及び変形が可能である。
【０２４２】
したがって、本発明の範囲は、開示された実施形態に限定されるものではなく、特許請求の範囲だけではなく特許請求の範囲と均等なものなどによって定められるものである。
【符号の説明】
【０２４３】
８００ 文書ランキング決定装置
８１０ 寄与係数算出部
８２０ 単語関連度スコア算出部
８３０ 寄与スコア算出部
８４０ 単語関連度スコア変更部
８５０ 文書ランキングスコア算出部
【技術分野】
【０００１】
本発明は文書ランキングスコアを算出するための方法および装置に関する。
【０００２】
本発明において、文書が追加および削除される動的ウェブ環境において文書の文書ランキングスコアを算出する方法および装置が開示される。
【背景技術】
【０００３】
ウェブ（ｗｅｂ）に存在する文書を対象に検索サービスを提供するシステム（以下、「ウェブ検索システム」と称する）は文書を収集し、文書の内容およびリンク情報などを反映して収集された文書のスコアを算出する。ウェブ検索システムは、ユーザによってクエリが入力されると、クエリと最も関連度の高い文書（または、このような文書のリスト、すなわちリンク）をユーザに提供する。
【０００４】
ウェブには数十億個以上の文書が存在し、このようなウェブ文書のうち一部は内容が変更または削除されてもよく、新しい文書が生成されたり文書そのものが削除されたりする場合もある。すなわち、ウェブ文書の状態は持続的に変化する。
【０００５】
したがって、ユーザに良好なウェブ検索サービスを提供するために、ウェブ検索システムは持続的にウェブの変化を反映してクエリに対する文書のスコアを算出し、算出の結果を短い時間内に検索結果へ反映する必要がある。
【０００６】
一般に、ウェブ検索システムは、一定の時間間隔で収集、索引、リンク情報分析、およびサービス反映などの作業を繰り返す。このような繰り返しの時間間隔は検索サービス業者ごとに異なるが、一般的には少なくとも１週間ないし２週間以内の間隔である。
【０００７】
もし、ウェブ検索システムの変更された文書が発見されるたびに文書の変更状態を検索サービスに反映してクエリとの関連度の高い文書をユーザに提供することができれば、検索サービスに対するユーザの満足度は大きく向上されるであろう。
【０００８】
検索サービスにおいて、文書のスコアは、文書の内容ベースのスコアおよびリンクベースのスコアの組合せに基づいて算出されてもよい。したがって、変更された文書が発見されるたびに短い時間内で検索結果に反映するためには文書の内容ベースのスコアおよびリンクベースのスコアを迅速に更新しなければならない。
【０００９】
文書＜ｐ＞の単語ｔに対する内容ベースのスコアは、一般的に単語頻度（Ｔｅｒｍ Ｆｒｅｑｕｅｎｃｙ；ＴＦ）および逆文書頻度（Ｉｎｖｅｒｓｅ Ｄｏｃｕｍｅｎｔ Ｆｒｅｑｕｅｎｃｙ；ＩＤＦ）値に基づいて算出される。ＴＦは文書＜ｐ＞における単語ｔの発生頻度数である。ＩＤＦは文書全体の集合で単語ｔを含む文書数の逆数である。
【００１０】
ＴＦは、文書内で単語ｔの使用頻度数を測定することによって算出される。したがって、特定文書のＴＦについては、文書全体の集合における他の文書に状態変化があっても再び算出される必要がない。
【００１１】
文書全体の集合における文書のうち１つの文書で単語ｔが追加または削除されるとＩＤＦが変更される。このような場合、単語ｔを含む全ての文書に対して内容ベースのスコアが再び算出されなければならない。
【００１２】
ウェブ検索システムは、ＩＤＦの変更による影響を最小化しながら漸次に文書の内容ベースのスコアを算出する必要がある。
【００１３】
例えば、ウェブ検索システムは与えられた単語ｔに対して、単語ｔを含む文書およびその文書数を格納した後、内容の変更された文書について単語ｔが新しく追加または削除されたかを把握することで単語ｔのＩＤＦ値を再算出してもよい。
【００１４】
単語ｔに対する従来のＩＤＦ値および新規ＩＤＦ値の差が予め設定された値以下であれば、ウェブ検索システムは従来のＩＤＦ値を用いて文書の内容ベースのスコアを算出してもよい。もし、前記値の差が予め設定された値よりも大きければ、ウェブ検索システムは単語ｔのＩＤＦ値を変更して単語ｔを含む文書の単語ｔに対する内容ベースのスコアを再算出してもよい。
【００１５】
また、ウェブ検索システムは、単語のＩＤＦ値は変化しないという仮定下でリンクベースのスコアを動的更新してもよい。
【発明の概要】
【発明が解決しようとする課題】
【００１６】
本発明の目的は、文書の内容が変更されたり文書が追加または削除されたりする場合、変更、追加、または削除された文書に関連する一部文書のみを対象に文書ランキングスコアを再算出する部分更新方法および装置を提供することである。
【００１７】
また、本発明の他の目的は、文書ランキングスコアを算出している間に文書の内容が変更されたり文書が追加または削除されたりする場合、文書の変更、追加、または削除が反映された文書ランキングスコアを算出する動的更新方法および装置を提供することである。
【課題を解決するための手段】
【００１８】
本発明の一実施形態に係る文書ランキング決定方法において、第１文書と第２文書との共通キーワードに対する第１文書の第１単語関連度スコアに基づいて第２文書の文書ランキングスコアを算出するステップと、第１単語関連度スコアを第２単語関連度スコアに動的に変更するステップと、第２単語関連度スコアに基づいて第２文書の文書ランキングスコアを更新するステップとを含み、第１文書は第２文書へのリンクを含むことを特徴とする文書ランキング決定方法が提供される。
【００１９】
第１文書と第２文書との共通キーワードに対する第１単語関連度スコアに基づいて第２文書の文書ランキングスコアを算出するステップは、共通キーワードに対する第１寄与係数および第１単語関連度スコアに基づいて第１寄与スコアを算出するステップと、第１寄与スコアを第２文書の共通キーワードに対する文書ランキングスコアに反映するステップとを含んでもよい。
【００２０】
第２単語関連度スコアに基づいて第２文書の文書ランキングスコアを更新するステップは、共通キーワードに対する第２寄与係数を算出するステップと、第１寄与係数、第１単語関連度スコア、第２寄与係数、および第２単語関連度スコアに基づいて第２寄与スコアを算出するステップと、第２寄与スコアを第２文書の文書ランキングスコアに反映するステップとを含んでもよい。
【００２１】
第１単語関連度スコアを第２単語関連度スコアに動的に変更するステップは、第１文書の内容が変更されるステップを含んでもよく、第１単語関連度スコアは、第１文書の内容が変更される前の第１文書の内容の共通キーワードに対する単語関連度スコアであり、第２単語関連度スコアは第１文書の内容が変更された後の第１文書の内容の共通キーワードに対する単語関連度スコアであってもよい。
【００２２】
第１単語関連度スコアを第２単語関連度スコアに動的に変更するステップは、第１文書の内容が生成されるステップを含んでもよく、第２単語関連度スコアは、生成された内容における共通キーワードに対する単語関連度スコアであってもよい。
【００２３】
第１単語関連度スコアを第２単語関連度スコアに動的に変更するステップは、第１文書の内容が削除されるステップを含んでもよく、第１単語関連度スコアは、第１文書の内容が削除された後の共通キーワードに対する単語関連度スコアであってもよい。
【００２４】
第１単語関連度スコアを第２単語関連度スコアに動的に変更するステップは、リンクが生成されるステップを含んでもよく、第２単語関連度スコアは、第１文書の内容の共通キーワードに対する単語関連度スコアであり、第１単語関連度スコアが第２単語関連度スコアに変更されるとみなすことによってリンクの生成を反映してもよい。
【００２５】
第１単語関連度スコアを第２単語関連度スコアに動的に変更するステップは、リンクが削除されるステップを含んでもよく、第１単語関連度スコアは、第１文書の内容の共通キーワードに対する単語関連度スコアであり、第１単語関連度スコアが第２単語関連度スコアに変更されるとみなすことによってリンクの削除を反映してもよい。
【００２６】
第１単語関連度スコアおよび第２単語関連度スコアは、第１文書の内容と共通キーワードとの間の関連性に基づいて算出されてもよい。
【００２７】
第１寄与係数および第２寄与係数は、共通キーワードにおいて第２文書が第１文書の内容に寄与する係数であってもよい。
【００２８】
文書ランキング決定方法は、第１文書が含む各単語について、第１文書の単語に対する単語関連度スコアを算出するステップと、第１文書のキーワードおよび第２文書のキーワードを抽出するステップと、第１文書と第２文書との間の共通キーワードを抽出するステップとをさらに含んでもよい。
【００２９】
文書ランキング決定方法は、第１文書への経路の開始文書である第３文書に対する、経路を通じた第１文書の寄与スコアおよび第１寄与係数に基づいて第３寄与スコアを算出するステップをさらに含んでもよい。
【００３０】
第２文書の文書ランキングスコアは、共通キーワードに対する第２文書の単語関連度スコア、第１寄与スコア、第２寄与スコア、および第３寄与スコアに基づいて決定されてもよい。
【００３１】
文書ランキング決定方法は、文書ランキングスコアに基づいて第２文書の文書ランキングを決定するステップをさらに含んでもよい。
【００３２】
また、本発明の一実施形態に係る文書ランキング決定装置において、第１文書と第２文書との間の共通キーワードに対する第１文書の第１単語関連度スコアおよび共通キーワードに対する第１文書の第２単語関連度スコアを算出する単語関連度スコア算出部と、第１単語関連度スコアを第２単語関連度スコアに変更する単語関連度スコア変更部と、第１単語関連度スコアに基づいて第２文書の文書ランキングスコアを算出し、第２単語関連度スコアに基づいて第２文書の文書ランキングスコアを更新する文書ランキングスコア算出部とを備え、第１文書は第２文書へのリンクを含むことを特徴とする文書ランキング決定装置が提供される。
【００３３】
文書ランキング決定装置は、共通キーワードに対する第１寄与係数および第２寄与係数を算出する寄与係数算出部と、第１寄与係数および第１単語関連度スコアに基づいて第１寄与スコアを算出し、第１寄与係数、第１単語関連度スコア、第２寄与係数、および第２単語関連度スコアに基づいて第２寄与スコアを算出する寄与スコア算出部とをさらに備えてもよく、文書ランキングスコア算出部は、第１寄与スコアを第２文書の共通キーワードに対する文書ランキングスコアに反映することによって第１単語関連度スコアに基づいて第２文書の文書ランキングスコアを算出し、第２寄与スコアを第２文書の文書ランキングスコアに反映することによって第２単語関連度スコアに基づいて第２文書の文書ランキングスコアを更新してもよい。
【００３４】
単語関連度スコア変更部は、第１文書の内容が変更される場合に第１単語関連度スコアを第２単語関連度スコアに変更してもよく、第１単語関連度スコアは、第１文書の内容が変更される前の第１文書の内容の共通キーワードに対する単語関連度スコアであり、第２単語関連度スコアは、第１文書の内容が変更された後の第１文書の内容の共通キーワードに対する単語関連度スコアであってもよい。
【００３５】
単語関連度スコア変更部は、第１文書の内容が生成される場合に第１単語関連度スコアを第２単語関連度スコアに変更してもよく、第２単語関連度スコアは、生成された第１文書の内容の共通キーワードに対する単語関連度スコアであってもよい。
【００３６】
単語関連度スコア変更部は、第１文書の内容が削除される場合に第１単語関連度スコアを第２単語関連度スコアに変更してもよく、第１単語関連度スコアは、第１文書の内容が削除された後の共通キーワードに対する単語関連度スコアであってもよい。
【００３７】
単語関連度スコア変更部は、リンクが生成される場合に第１単語関連度スコアが第２単語関連度スコアに変更されたものとみなすことによってリンクの生成を反映してもよく、第２単語関連度スコアは、第１文書の内容の共通キーワードに対する単語関連度スコアであってもよい。
【００３８】
単語関連度スコア変更部は、リンクが削除される場合に第１単語関連度スコアが第２単語関連度スコアに変更されたものとみなすことによってリンクの削除を反映してもよく、第１単語関連度スコアは、第１文書の内容の共通キーワードに対する単語関連度スコアであってもよい。
【００３９】
文書ランキング決定装置は、第１文書のキーワードおよび第２文書のキーワードを抽出し、第１文書と第２文書との間の共通キーワードを抽出する共通キーワード抽出部をさらに備えてもよく、単語関連度スコア算出部は、第１文書が含む各単語に対して第１文書の単語に対する単語関連度スコアを算出してもよい。
【００４０】
寄与スコア算出部は、第１文書への経路の開始文書である第３文書に対する、経路を通じた第１文書の寄与スコアおよび第１寄与係数に基づいて第３寄与スコアを算出してもよく、文書ランキングスコア算出部は、第３寄与スコアを第２文書の文書ランキングスコアに反映してもよい。
【００４１】
文書ランキングスコア算出部は、共通キーワードに対する第２文書の単語関連度スコア、第１寄与スコア、第２寄与スコア、および第３寄与スコアに基づいて第２文書の文書ランキングスコアを決定してもよい。
【００４２】
文書ランキングスコアに基づいて第２文書の文書ランキングを決定する文書ランキング決定部をさらに備えてもよい。
【発明の効果】
【００４３】
本発明の一実施形態によれば、文書の内容が変更されたり文書が追加または削除されたりする場合、変更、追加、または削除された文書に関連する一部文書のみを対象に文書ランキングスコアを再算出する部分更新方法および装置を提供することができる。
【００４４】
本発明の一実施形態によると、文書ランキングスコアを算出している間に文書の内容が変更されたり文書が追加または削除されたりする場合、文書の変更、追加、または削除が反映された文書ランキングスコアを算出する動的更新方法および装置を提供することができる。
【図面の簡単な説明】
【００４５】
【図１】本発明の一実施形態に係る文書スコア算出方法を説明するための図である。
【図２】本発明の一実施形態に係る共通キーワードに対する文書の寄与係数を算出する方法を説明するための図である。
【図３】本発明の一実施形態に係る文書ランキング決定方法を示すフローチャートである。
【図４】本発明の一実施形態に係る単語関連度スコア変更を説明するための図である。
【図５】本発明の一実施形態に係る寄与スコアの分割伝達の特性を説明するための図である。
【図６】本発明の一実施形態に係るＣ−Ｒａｎｋスコア更新の対象となる文書を説明するための図である。
【図７】本発明の一実施形態に係る動的文書ランキングの決定方法を示すフローチャートである。
【図８】本発明の一実施形態に係る文書ランキング決定装置の構造図である。
【発明を実施するための形態】
【００４６】
以下、本発明の一実施形態を添付する図面を参照しながら詳説する。本発明は実施形態によって制限されたり限定されたりすることはない。各図面に提示された同じ参照符号は同じ部材を示す。本発明の一実施形態に係る文書ランキング決定方法は文書ランキング決定システムの各構成によって行われてもよい。
【００４７】
Ｃ−Ｒａｎｋベースの文書ランキング決定方法は、各文書について単語ごとに単語関連度スコアおよび寄与スコアを算出し、算出された単語関連度スコアおよび寄与スコアの組合せに基づいて文書のランキングを決定する方法である。
【００４８】
単語関連度スコアは、単語に対する文書の内容に基づいて決定される情報である。寄与スコアは、単語に対する文書のリンク情報に基づいて決定される情報である。すなわち、上記方法はリンクに接続された文書間の関係を考慮してリンクに基づいた寄与スコアを算出する特徴を有する。
【００４９】
各文書は各単語に対するＣ−Ｒａｎｋスコアを有する。単語ｔに対する文書＜ｐ＞のＣ−Ｒａｎｋスコアは、文書＜ｐ＞の単語ｔに対する単語関連度スコアおよび寄与スコアを組合せることによって算出される。
【００５０】
Ｃ−Ｒａｎｋベースの文書ランキング決定方法は、ユーザによってクエリが入力される前に各文書に対して文書に含まれる単語に対するＣ−Ｒａｎｋスコアを算出する。クエリが１つ以上の単語で構成された場合、本方法においては文書の単語それぞれに対するＣ−Ｒａｎｋスコアを合算することによってクエリに対する文書のスコアを算出してもよい。
【００５１】
図１は、本発明の一実施形態に係る文書スコア算出方法を説明するための図である。
【００５２】
図１に示すように、文書＜Ｘ＞１００とリンクに接続された文書＜Ｙ１＞１１０、文書＜Ｚ１＞１２０、文書＜Ｙ２＞１３０および文書＜Ｚ２＞１４０が示された。ここで、文書＜Ｘ＞１００、文書＜Ｙ１＞１１０および文書＜Ｚ１＞１２０は単語Ａ１５０を含み、文書＜Ｘ＞１００、文書＜Ｙ２＞１３０および文書＜Ｚ２＞１４０は単語Ｂ１６０を含む。
【００５３】
単語Ａ１５０は文書＜Ｘ＞１００、文書＜Ｙ１＞１１０および文書＜Ｚ１＞１２０に共通に含まれた共通キーワードであり、単語Ｂ１６０は文書＜Ｘ＞１００、文書＜Ｙ２＞１３０および文書＜Ｚ２＞１４０に共通に含まれた共通キーワードである。すなわち、共通キーワードはリンクに接続された文書に共通して含まれたキーワードである。各文書は１つ以上の共通キーワードを含んでもよい。
【００５４】
単語Ａ１５０および単語Ｂ１６０はユーザが入力したクエリに含まれた単語であってもよい。
【００５５】
本発明の一実施形態に係る文書ランキング決定方法は、単語それぞれに対する文書のランキングを決定してもよい。文書ランキング決定方法は、文書内容およびリンク情報を組合せて単語に対する文書のランキングを決定してもよい。
【００５６】
具体的に、文書ランキング決定方法は、文書に含まれた少なくとも１つの単語それぞれに対する文書の単語関連度スコアと単語を共通に含む他の文書の活用度を示す寄与スコアとを組合せて文書ランキングを決定してもよい。
【００５７】
一実施形態として、文書のランキングを決定する場合に次のような基本概念を予め定義してもよい。
【００５８】
（１）重要文書の基準
文書が生成される場合、ユーザに提供しようとする主要情報で本文を構成してもよい。また、文書の本文に対する詳細説明や本文に関連する追加情報は他の文書をリンクに接続する方式により提供されてもよい。ここで、リンクに接続された文書（例えば、文書＜Ｙ１＞１１０および文書＜Ｙ２＞１３０）とはリンクを含む文書（例えば、文書＜Ｘ＞１００）のような主要情報について説明している文書であってもよく、または他の文書における主要情報に関する細部事項を補完説明する文書であってもよく、または単語（例えば、単語Ａ１５０および単語Ｂ１６０）の詳細説明の文書であってもよい。または場合に応じて、リンクに接続された文書はリンクを含む文書と全く関係のない文書（例えば、文書の内容と関係のない広告）であってもよい。
【００５９】
文書の内容は文書の品質を評価するときの重要な要素であってもよい。ユーザは所望する内容を含む高品質の文書が検索結果として示されることを期待してもよい。また、文書ランキング決定方法または装置は文書の本文の品質に寄与する重要文書をリンクとして接続してもよい。
【００６０】
本発明の一実施形態に係る文書ランキング決定システムは、次のような条件を満たす文書を重要文書であると規定してもよい。１）与えられた単語に対する単語関連度スコアが高い文書、２）与えられた単語に対する単語関連度スコアが高い文書とリンクにより接続された文書、３）リンクによって自身の情報を多く活用する文書に接続された文書。
【００６１】
（２）リンクに接続された文書の寄与スコア
リンクに接続された文書（例えば、文書＜Ｙ１＞１１０、文書＜Ｙ２＞１３０）がリンクを含む文書（例えば、文書＜Ｘ＞１００）に対する寄与スコアは与えられたクエリに対する２つの文書の単語関連度スコアに基づいて決定されてもよい。
【００６２】
与えられたクエリに対する２つの文書の関連度が高いほど、リンクに接続された文書はリンクを含む文書の品質に大きく寄与する。ただし、リンクを含む文書は検索クエリに対して高い関連度を有するもののリンクに接続された文書は検索クエリに対して低い関連度を有する場合、リンクに接続された文書はリンクを含む文書の品質に寄与しない場合がある。
【００６３】
（３）ランキングに応じたユーザの関心度
検索結果においては、文書の相対的なランキングが重要であり、ユーザは自身が所望する情報が検索結果を表示するページの１ページ目に表示されることを所望する。例えば、文書ランキング決定システムが上位１０位までに該当する文書を１ページ目に表示する場合、ユーザはそれら表示される文書に対して敏感であるが、ランキングが２００位から３００位までの間に位置する文書については、それらの文書をいずれも重要ではないものとして、その間のランキングの差に関心を示さないことが考えられる。
【００６４】
したがって、本発明の一実施形態に係る文書ランキング決定システムは、予め設定したランキング上において上位に該当する文書の相対的なランキングをランキング上において下位に該当する文書よりもさらに正確に決定することができる。ランキング上、上位に該当する文書について、相対的なランキングを正確に決定すればユーザは検索結果に満足することができ、それ以上に多くの文書に対して正確なランキングを決定する必要がないため、検索結果を導き出すために要求されるリソースを節約することができる。
【００６５】
このような基本概念に基づいて、本発明の一実施形態に係る文書ランキング決定方法または装置は、単語Ａ１５０に対して文書＜Ｘ＞１００、文書＜Ｙ１＞１１０および文書＜Ｚ１＞１２０の単語関連度スコアおよび寄与スコアを算出し、算出された単語関連度スコアおよび寄与スコアを組合せることによって、単語Ａ１５０に対する文書間の文書ランキングを決定するためのＣ−Ｒａｎｋスコアを算出してもよい。
【００６６】
また、本発明の一実施形態に係る文書ランキング決定方法またはシステムは、単語Ｂ１６０に対して文書＜Ｘ＞１００、文書＜Ｙ２＞１３０および文書＜Ｚ２＞１４０の単語関連度スコアおよび寄与スコアを算出し、算出された単語関連度スコアおよび寄与スコアを組合せることによって単語Ｂ１６０に対する文書間の文書ランキングを決定するためのＣ−Ｒａｎｋスコアを決定してもよい。最終的に、決定された文書ランキングは、文書および単語の対に対して決定された文書ランキングスコアを昇順または降順に配列することによって決定されてもよい。（例えば、ＣＡ（Ｘ）など）
【００６７】
【数１】
【００６８】
【００６９】
【００７０】
【００７１】
図２は、本発明の一実施形態に係る共通キーワードに対する文書の寄与係数を算出する方法を説明するための図である。
【００７２】
本実施形態において、寄与係数は第２文書が第１文書の内容に寄与する係数を意味する。第１文書および第２文書の共通キーワードに対して第１文書の第２文書に対する寄与係数が決定される。
【００７３】
【００７４】
【数２】
【００７５】
【００７６】
ｔ２５０は単語を意味する。
【００７７】
【００７８】
【００７９】
【００８０】
数２から分かるように、第１文書＜ｐ＞２４０の第２文書＜ｑ＞２１０に対する寄与係数に第２文書＜ｑ＞２１０の内容スコアを適用することによって第１文書＜ｐ＞２４０の寄与スコアが算出されてもよい。
【００８１】
図２に示すように、第２文書（文書＜ｑ＞２１０）から第１文書（文書＜ｐ＞２４０）に達する複数のステップのリンクを含むリンク経路が存在する場合、リンク経路に対応する文書（文書＜ｒ１＞２２０〜文書＜ｒｄ−１＞２３０）の寄与係数を用いることによって第１文書の第２文書に対する寄与係数を決定してもよい。
【００８２】
寄与係数は下記の数３によって決定されてもよい。
【数３】
【００８３】
【００８４】
また、リンク経路に対応する文書の寄与係数は、リンク経路上で隣接する文書間の寄与係数（例えば、ｒ１→ｒ２のリンクでｒ２のｒ１に対する寄与係数）を用いて決定されてもよい。
【００８５】
本発明の一実施形態によると、第１文書および第２文書が１つのリンクに接続される場合、第１文書の内容スコア、第２文書の内容スコア、および第２文書のアウトリンクに対応する第３文書の内容スコアを用いることによって第１文書の第２文書に対する寄与係数を決定してもよい。
【００８６】
第１文書および第２文書が１つのリンクに接続される場合、第１文書の第２文書に対する寄与係数は下記の数４によって決定されてもよい。
【数４】
【００８７】
【００８８】
【００８９】
【００９０】
【００９１】
例えば、文書＜ｐ＞、文書＜ｑ＞および文書＜ｒ＞がｒ→ｑ→ｐのようにリンクに接続された場合、このようなリンクに対して図２の説明を適用すると次の通りである。
【００９２】
【００９３】
【００９４】
図３は、本発明の一実施形態に係る文書ランキング決定方法を示すフローチャートである。
【００９５】
本実施形態の文書ランキング算出方法は、初期化ステップＳ３１０ないしステップＳ３３０およびスコア伝達ステップＳ３４０ないしステップＳ３８０に分類されてもよい。
【００９６】
【００９７】
【００９８】
ステップＳ３２０において、各文書＜ｐ＞について、文書＜ｐ＞のキーワードが抽出される。
【００９９】
ステップＳ３２２において、各文書＜ｐ＞について、文書＜ｐ＞および文書＜ｐ＞がリンクに示す各文書＜ｑ＞間の共通キーワードが抽出される。
【０１００】
【０１０１】
【０１０２】
【０１０３】
【０１０４】
【０１０５】
【０１０６】
【０１０７】
【０１０８】
【０１０９】
【０１１０】
ステップＳ３８０において、全ての文書に伝達した寄与スコアが０であれば（または伝達された全ての寄与スコアが０であれば）手続きを終了し、そうでなければステップＳ３５０が繰り返される。
【０１１１】
図４は、本発明の一実施形態に係る単語関連度スコア変更を説明するための図である。
【０１１２】
【０１１３】
図１から図３を参照して前述した文書ランキング算出方法は静的な算出方法であり、動的な算出方法においては、静的な算出方法で用いられた記号や式に時点Ｔが追加されてもよい。Ｔは０以上の整数である。
【０１１４】
【０１１５】
【０１１６】
【０１１７】
【０１１８】
【０１１９】
【０１２０】
【０１２１】
【０１２２】
単語関連度スコアの変更によるＣ−Ｒａｎｋスコアの更新は２種類に区分されてもよい。
【０１２３】
（１）部分更新はＣ−Ｒａｎｋスコアが完全に算出された後、単語関連度スコアが変更される場合に行われるものである。
【０１２４】
文書間のリンク構造は変更されないものと仮定する。
【０１２５】
【０１２６】
【０１２７】
（２）動的更新はＣ−Ｒａｎｋスコアを算出している際に、単語関連度スコアが変更される場合に行われるものである。
【０１２８】
文書間のリンク構造は変更されないものと仮定する。
【０１２９】
【０１３０】
【０１３１】
下記では、時点Ｔ、Ｃ−Ｒａｎｋスコアおよび寄与スコア間の関係について説明する。
【０１３２】
数１によると、単語ｔに対する文書＜ｐ＞のＣ−Ｒａｎｋスコアは、単語ｔに対する文書＜ｐ＞の単語関連度スコアおよび文書＜ｐ＞の他の文書に対する寄与スコアの加重和である。
【０１３３】
時点Ｔである場合、文書＜ｐ＞の単語関連度スコア、寄与スコア、およびＣ−Ｒａｎｋスコアが算出されていると仮定する。これによって、時点がＴ＋１である場合に単語ｔに対する文書＜ｐ＞のＣ−Ｒａｎｋスコアは下記の数５のように表してもよい。
【数５】
【０１３４】
【０１３５】
前述の部分更新および動的更新は文書の内容が変更されたり文書が削除または追加されたりする場合に変更、削除、または追加された文書によってＣ−Ｒａｎｋスコアが影響の受けた文書のみを対象にＣ−Ｒａｎｋスコアの更新を行う。
【０１３６】
したがって、部分更新および動的更新により、動的に変化するウェブ環境をＣ−Ｒａｎｋスコアへと素早く反映することができる。
【０１３７】
また、ウェブなど文書ランキング決定を要する環境においては、持続的に文書が追加および削除されるため、部分更新および動的更新方法に基づいて算出されたＣ−Ｒａｎｋスコアは静的算出方法に基づいて算出されたＣ−Ｒａｎｋスコアよりも、より実際のウェブ環境をさらに効率よく反映することができる。
【０１３８】
図５は、本発明の一実施形態に係る寄与スコアの分割伝達の特性を説明するための図である。
【０１３９】
【０１４０】
前述したように、各文書は自身の単語関連度スコアにアウトリンクの寄与係数を乗算することによって寄与スコアを生成し、生成された寄与スコアをアウトリンクが示す文書に伝達する。
【０１４１】
寄与スコアを伝達された文書は、伝達された寄与スコアにアウトリンクの寄与係数を乗算してアウトリンクが示す文書に伝達される。すなわち、寄与スコアは、経路の寄与係数に寄与スコアを付与する文書の単語関連度スコアを乗算することによって生成される。
【０１４２】
このような寄与スコアの生成および伝達過程は、伝達する寄与スコアが一定の値以下になるか、あるいは寄与スコアの伝達回数が一定の回数に達するまで繰り返されてもよい。
【０１４３】
【０１４４】
まず、文書＜ｐ＞５１０は、算出された寄与スコアの半分５５０を第１反復ステップ（例えば、スコア伝達ステップＳ３４０ないしＳ３８０の最初の実行ステップ）で文書＜ｑ＞５２０に伝達し、残りの半分５６０を第２反復ステップに追加伝達する場合について説明する。
【０１４５】
【０１４６】
結果的に、文書＜ｐ＞５１０が寄与スコアを分割して伝達しても、反復算出の過程が完了したときの文書＜ｑ＞５２０の文書＜ｐ＞５１０に対する寄与スコアは一定である。
【０１４７】
したがって、静的な算出の過程において文書＜ｐ＞の寄与スコア（文書＜ｐ＞の単語関連度スコアによって生成された寄与スコアまたは文書＜ｐ＞に伝達された寄与スコア）が分割され（分割された寄与スコアの総和は本来の寄与スコアと同一である）、分割された寄与スコアが数回に分割してアウトリンクが示す文書に伝達されても、静的な算出方法が完了したときに文書それぞれに伝達された寄与スコアは変わらない。
【０１４８】
次に、文書＜ｐ＞５１０は、算出された寄与スコアの２倍の値を示す値５７０を第１反復ステップにおいて文書＜ｑ＞５２０に伝達し、算出された寄与スコアに−１を乗算した値５８０を第２反復ステップに伝達する場合について説明する。
【０１４９】
【０１５０】
【０１５１】
すなわち、文書＜ｐ＞５１０が多すぎる寄与スコアを文書＜ｑ＞５２０に伝達した後、これを相殺する程の負の寄与スコアを文書＜ｑ＞５２０に伝達しても、反復算出の過程が完了したときに文書＜ｑ＞５２０の文書＜ｐ＞５１０に対する寄与スコアは一定である。
【０１５２】
また、ｏ→ｐ→ｑのリンク構造において、文書＜ｐ＞が文書＜ｏ＞から伝達された寄与スコアを分割して文書＜ｑ＞に伝達しても、最終的な文書＜ｑ＞の文書＜ｏ＞に対する寄与スコアは同じ値を有する。
【０１５３】
前述したように、寄与スコアが正の数及び負の数に分割されて伝達されても、分割されて伝達された寄与スコアの総和が本来の分割される前の寄与スコアと同一であれば、本来の寄与スコアが伝達されたものと同じ結果となる。このような寄与スコアの特性を分割伝達の特性と称する。
【０１５４】
分割伝達の特性を活用すると、前述した部分更新および動的更新は静的な算出の中間過程であると解釈してもよい。
【０１５５】
【０１５６】
【０１５７】
【０１５８】
【０１５９】
【数６】
【０１６０】
【０１６１】
【０１６２】
【０１６３】
【０１６４】
（１）スコア伝達反復作業を中断する。
（２）各リンクの寄与係数を更新する。
（３）各文書は数６によって算出された追加寄与スコアを伝達する。
（４）スコア伝達反復作業を再開する。
【０１６５】
図６は、本発明の一実施形態に係るＣ−Ｒａｎｋスコア更新の対象となる文書を説明するための図である。
【０１６６】
文書＜ｐ＞６１０の単語関連度スコアが更新されるときに、寄与係数が変更されるリンクは文書＜ｐ＞６１０のアウトリンク６５０および文書＜ｐ＞６１０を示す文書６２０、６３０のアウトリンク６６０、６７０である。
【０１６７】
数６によると、単語関連度スコアが変更されることなくアウトリンクの寄与係数が変わらない文書は、追加伝達する寄与スコアがない。したがって、寄与スコアを追加伝達する文書は、単語関連度スコアが変更された文書および単語関連度スコアが変更された文書をリンクで示す文書に制限される。このような文書を追加寄与スコア伝達文書と称する。
【０１６８】
文書の内容が変更されながら時点Ｔ＋１に新しいリンクｐ→ｑ６８０が追加された場合について説明する。
【０１６９】
【０１７０】
文書の内容が変更されながら時点Ｔ＋１に既存リンクｐ→ｑ６８０が削除された場合について説明する。
【０１７１】
【０１７２】
したがって、リンクの追加および削除によるＣ−Ｒａｎｋスコアの部分更新および動的更新は、前述の文書の単語関連度スコア変更による動的更新と同じ方法に基づいて処理されてもよい。
【０１７３】
新しい文書が追加されるのは、既に生成されていたが、本文の内容がなかったため全ての単語関連度スコアが０であった文書に本文が追加されることで単語関連度スコアが変更された場合である。
【０１７４】
従来の文書が削除されるのは、文書の本文が削除されて全ての単語関連度スコアが０になった場合である。
【０１７５】
したがって、文書の追加および削除による動的更新は、文書の単語関連度スコア変更による動的更新と同じ方法に基づいて処理されてもよい。
【０１７６】
図７は、本発明の一実施形態に係る動的文書ランキングの決定方法を示すフローチャートである。
【０１７７】
本実施形態における動的文書ランキングの決定方法は、前処理ステップＳ７００ないしＳ７４４、反復作業ステップＳ７５０ないしＳ７９２、および文書ランキング算出ステップＳ７９４に区分してもよい。
【０１７８】
図７に示される本実施形態の動的文書ランキングの決定方法および図３を参照して前述した文書ランキング決定方法との差異について説明すると、本実施形態に係る動的文書ランキングの決定方法は、文書の追加または削除が発生したり、文書の内容が変更されたりすることによる変更された寄与スコアを算出する方法、およびこのような寄与スコアを文書ランキングスコアに反映する方法が追加された点で図３を参照して前述した文書ランキングの決定方法と異なる。
【０１７９】
まず、前処理ステップＳ７００ないしステップＳ７４４について説明する。
【０１８０】
ステップＳ７００において、時点Ｔが０に初期化される。
【０１８１】
ステップＳ７１０において、各文書＜ｐ＞が含んでいる各単語ｔに対する文書の単語関連度スコアが算出される。以下、本ステップＳ７１０で算出された文書の単語関連度スコアを第１単語関連度スコアと称する。例えば、第１文書が第１単語を含むと、第１文書の第１単語に対する第１単語関連度スコアが算出される。
【０１８２】
ステップＳ７２０において、各文書＜ｐ＞の各単語ｔに対する初期Ｃ−Ｒａｎｋスコアが指定（すなわち、算出および設定）される。初期Ｃ−Ｒａｎｋスコアは、ステップＳ７１０で算出された単語関連度スコアに加重値λを乗算した値である。
【０１８３】
ステップＳ７３０において、各文書＜ｐ＞からキーワードが抽出される。キーワードは、例えば、第１文書が含む第１単語のように各文書＜ｐ＞が含む各単語ｔのうちの一部である。
【０１８４】
ステップＳ７３２において、各リンクｌに対してリンクｌに接続された２つの文書間の共通キーワードが抽出される。例えば、第１文書が第１リンクを含み、第１リンクは第１文書から第２文書へのリンクであれば、第１文書および第２文書の共通キーワードが抽出される。
【０１８５】
ステップＳ７４０において、リンクに接続された２つの文書間の各共通キーワードに対して２つの文書間の寄与係数が算出される。算出された寄与係数は２つの文書を接続するリンクのキーワードに対する寄与係数であってもよい。以下、本ステップＳ７４０で算出された寄与係数を第１寄与係数と称する。例えば、リンクに接続された第１文書および第２文書の共通キーワードがあれば、第１文書と第２文書との間の共通キーワードに対する第１寄与係数が算出される。
【０１８６】
【０１８７】
【０１８８】
次に、反復作業ステップＳ７５０ないしＳ７９２について説明する。反復作業ステップＳ７５０ないしＳ７９２において、寄与スコアを伝達するためのステップＳ７５０ないしＳ７５２、および追加伝達寄与スコアを伝達するためのステップＳ７６０ないしＳ７６８が行われ、これらステップが行われた後に寄与スコアを算出するためのステップＳ７７０ないしＳ７９２が行われる。
【０１８９】
寄与スコアを伝達するためのステップＳ７５０ないしＳ７５２について説明する。
【０１９０】
【０１９１】
【０１９２】
【０１９３】
【０１９４】
次に、追加伝達寄与スコアを伝達するためのステップＳ７６０ないしＳ７６８を説明する。
【０１９５】
追加伝達寄与スコアを伝達するためのステップは、１つ以上の文書で追加伝達寄与スコアが発生する場合に実行されるステップである。文書の単語関連度が変更されると、既に伝達された寄与スコアは、変更された単語関連度および変更された寄与係数を正しく反映することができない。したがって、変更に応じて発生した寄与スコアの差を補正するために追加伝達寄与スコアが伝達される。
【０１９６】
ステップＳ７６０において、単語関連度が変更された文書が存在するか否かが検出される。もし、単語関連度が変更された文書がなければ、ステップＳ７７０を実行する。
【０１９７】
文書の単語関連度は下記の（１）〜（５）のような場合に変更されてもよい。
【０１９８】
（１）文書の内容が変更される場合に、文書の単語関連度が変更されてもよい。ここで、変更前の文書の単語関連度スコアは、ステップＳ７１０で算出された第１単語関連度スコアであってもよい。変更された内容に応じて文書の単語関連度スコアが変更される。
【０１９９】
（２）文書または文書の内容が生成される場合に、文書の単語関連度が変更されてもよい。ここで、変更前の文書の単語関連度スコアは０であってもよい。生成された文書の内容または生成された内容に応じて文書の単語関連度スコアが変更される。
【０２００】
（３）文書または文書の内容が削除される場合に、文書の単語関連度が変更されてもよい。ここで、変更前の文書の単語関連度スコアは、ステップＳ７１０で算出された第１単語関連度スコアであってもよい。文書または文書の内容が削除されることによって文書の単語関連度スコアは０に変更されてもよい。
【０２０１】
（４）両文書間のリンクが生成される場合に、文書の単語関連度が変更されたとみなしてもよい。
【０２０２】
第１文書から第２文書へのリンクが新しく生成されると、寄与スコアが伝達されていない第２文書へと新たに寄与スコアを伝達しなければならない。第１文書の単語関連度が変更されたものとみなすことによって、単語関連度の変更に応じて生成された追加伝達寄与スコアを第２文書に伝達してもよい（文書の単語関連度は文書に関連するリンクとは関係ない）。ここで、ステップＳ７１０で算出された第１単語関連度スコアは０であってもよい。また、変更された単語関連度スコアは第１文書の内容の単語に対する単語関連度スコアであるとみなしてもよい。
【０２０３】
（５）両文書間のリンクが削除される場合に、文書の単語関連度が変更されたとみなしてもよい。
【０２０４】
第１文書から第２文書へのリンクが削除されると、既に第２文書に伝達された寄与スコアは、消滅することとなる。第１文書の単語関連度が変更されたものとみなすことによって、単語関連度の変更に応じて生成された負の追加伝達寄与スコアを第２文書に伝達してもよい（文書の単語関連度は文書に関連するリンクとは関係ない）。ここで、ステップＳ７１０で算出された第１単語関連度スコアは、第１文書の内容の単語に対する単語関連度スコアであるとみなしてもよい。また、変更された単語関連度スコアは０であるとみなしてもよい。
【０２０５】
以下、変更された文書の単語関連度スコアを第２単語関連度スコアと称する。
【０２０６】
単語関連度が変更された文書＜ｐ＞に対して下記のステップＳ７６２ないしステップＳ７６８を実行する。
【０２０７】
【０２０８】
【０２０９】
【０２１０】
【０２１１】
すなわち、ステップＳ７６６およびステップＳ７６８において、単語関連度スコアの変更された第１文書の追加寄与スコアが第１文書およびリンクに接続された第２文書に伝達され、伝達された第１文書の追加寄与スコアが第２文書の累積スコアに加えられる。
【０２１２】
寄与スコアを算出するためのステップＳ７７０ないしステップＳ７９２について説明する。
【０２１３】
【０２１４】
【０２１５】
【０２１６】
第３寄与スコアは次のように実行される時点Ｔが１大きい反復作業ステップＳ７５０ないしＳ７９２で文書＜ｑ＞に伝達される。
【０２１７】
すなわち、第３文書および第１文書が第３文書から第１文書へのリンクに接続されたとき、すなわち、第３文書は第１文書を表す経路の開始文書であるとき、第３文書の寄与スコアは今回の反復作業ステップＳ７５０ないしＳ７９２で第１文書に伝達され、伝達された第３文書の寄与スコアに基づいて生成された第３寄与スコアが次の反復作業ステップＳ７５０ないしＳ７９２で第１文書と接続された第２文書に伝達される。したがって、第３文書に対する、前述した経路を介する第１文書の寄与スコアおよび第１寄与係数に基づいて第３寄与スコアが算出される。
【０２１８】
ステップＳ７９２において、全ての文書が伝達する寄与スコアが０であるか否かが検出される。
【０２１９】
伝達される全ての寄与スコアのうち０でないものがあれば、反復作業ステップＳ７５０ないしＳ７９２を再び繰り返す。すなわち、ステップＳ７５０およびステップＳ７６０が再び実行される。
【０２２０】
伝達される全ての寄与スコアが０であれば、これ以上反復作業ステップＳ７５０ないしＳ７９２を繰り返す必要がない。したがって、ステップＳ７９４が実行される。
【０２２１】
【０２２２】
【０２２３】
図８は、本発明の一実施形態に係る文書ランキング決定装置の構造図である。
【０２２４】
文書ランキング決定装置８００は、寄与係数算出部８１０、単語関連度スコア算出部８２０、寄与スコア算出部８３０、単語関連度スコア変更部８４０、および文書ランキングスコア算出部８５０を備える。文書ランキング決定装置８００は、共通キーワード抽出部８６０、文書ランキング決定部８７０、および格納部８８０をさらに備えてもよい。
【０２２５】
寄与係数算出部８１０は前述の寄与係数を算出する。例えば、寄与係数算出部は、ステップＳ７４０の第１寄与係数およびステップＳ７６２の第２寄与係数を算出してもよい。
【０２２６】
単語関連度スコア算出部８２０は前述の単語関連度を算出する。例えば、単語関連度算出部８２０は、ステップＳ７１０の第１単語関連度スコアおよびステップＳ７６０の第２単語関連度スコアを算出してもよい。
【０２２７】
寄与スコア算出部８３０は前述の寄与スコアを算出する。例えば、寄与スコア算出部８３０は、ステップＳ７４４の第１寄与スコア、ステップＳ７６２の第２寄与スコア、およびステップＳ７９０の第３寄与スコアを算出してもよい。
【０２２８】
単語関連度スコア変更部８４０は、文書の単語に対する単語関連度スコアを変更する。例えば、単語関連度スコア変更部８４０は、ステップＳ７６０で説明された単語関連度の変更原因（１）〜（５）が発生した文書の単語関連度スコアをステップＳ７１０の第１単語関連度スコアからステップＳ７６０の第２単語関連度スコアに変更してもよい。
【０２２９】
単語関連度スコア変更部８４０は、単語関連度スコアが変更された文書の単語関連度スコアを再算出することを単語関連度スコア算出部８２０に要求してもよい。
【０２３０】
文書ランキングスコア算出部８５０は前述の文書ランキングスコアを算出する。
【０２３１】
文書ランキングスコア算出部８５０は、第１単語関連度スコアに基づいて第２文書の文書ランキングスコアを算出してもよく、第２単語関連度スコアに基づいて第２文書の文書ランキングスコアを更新してもよい。
【０２３２】
文書ランキングスコア算出部８５０は、ステップＳ７４４の第１寄与スコアを第２文書の共通キーワードに対する文書ランキングスコアに反映することによって第１単語関連度スコアに基づいて第２文書の文書ランキングスコアを算出してもよく、ステップＳ７６２の第２寄与スコアを第２文書の文書ランキングスコアに反映することによって第２単語関連度スコアに基づいて第２文書の文書ランキングスコアを更新してもよい。
【０２３３】
例えば、文書ランキングスコア算出部８５０は、ステップＳ７４４の第１寄与スコア、ステップＳ７６２の第２寄与スコア、およびステップＳ７９０の第３寄与スコアに基づいてステップＳ７７０の文書ランキングスコアを算出してもよい。
【０２３４】
文書ランキングスコア算出部８５０は、文書の単語に対するステップＳ７１０の第１文書関連度スコア、ステップＳ７４４の第１寄与スコア、ステップＳ７６２の第２寄与スコア、およびステップＳ７９０の第３寄与スコアに基づいて文書の単語に対する文書ランキングスコアを決定してもよい。
【０２３５】
共通キーワード抽出部８６０は、リンクに接続された２つの文書間の共通キーワードを抽出する。例えば、共通キーワード抽出部はステップＳ７３２の共通キーワードを抽出してもよい。
【０２３６】
文書ランキング決定部８７０は、文書ランキングスコア算出部８５０によって算出された文書の単語に対する文書ランキングスコアに基づいて文書の単語に対する文書ランキングを決定してもよい。
【０２３７】
格納部８８０は、前述した文書ランキング決定装置８００の他の構成要素８１０ないし８７０の動作に必要なデータを格納および提供する。例えば、格納部８８０は、文書、リンク、寄与係数、寄与スコア、単語関連度スコア、文書ランキングスコア、および文書ランキングなどを管理するために必要なデータ構造を格納する。
【０２３８】
上記の図１ないし図７を参照して説明された本発明の一実施形態に係る技術的内容が本実施形態にもそのまま適用されてもよい。したがって、本詳細な説明は以下では省略することにする。
【０２３９】
文書ランキング決定装置８００の構成要素８１０ないし８８０の機能の一部または全部は単一な制御部（図示せず）で行われてもよい。制御部は単一または複数のプロセッサであってもよく、ネットワークによって接続された分散処理システムであってもよい。構成要素８１０ないし８８０は制御部で行われるサービス、プロセス、スレッド、モジュール、ライブラリ、および関数を表してもよい。
【０２４０】
本発明の一実施形態に係る方法は多様なコンピュータ手段を介して様々な処理を実行することができるプログラム命令の形態で実現され、コンピュータ読取可能な記録媒体に記録されてもよい。コンピュータ読取可能な媒体は、プログラム命令、データファイル、データ構造などのうちの１つまたはその組合せを含んでもよい。媒体に記録されるプログラム命令は、本発明の目的のために特別に設計されて構成されたものでもよく、コンピュータソフトウェア分野の技術を有する当業者にとって公知のものであり、使用可能なものであってもよい。コンピュータ読取可能な記録媒体の例としては、ハードディスク、フロッピー（登録商標）ディスク及び磁気テープのような磁気媒体、ＣＤ−ＲＯＭ、ＤＶＤのような光記録媒体、光ディスクのような光磁気媒体、及びＲＯＭ、ＲＡＭ、フラッシュメモリなどのようなプログラム命令を保存して実行するように特別に構成されたハードウェア装置が含まれてもよい。プログラム命令の例としては、コンパイラによって生成されるような機械語コード（ｍａｃｈｉｎｅ ｃｏｄｅ）だけでなく、インタプリタなどを用いてコンピュータによって実行され得る高級言語コード（ｈｉｇｈｅｒ ｌｅｖｅｌ ｃｏｄｅ）を含む。上述したハードウェア装置は、本発明の動作を行うために１つ以上のソフトウェアのレイヤで動作するように構成されてもよい。
【０２４１】
上述したように、本発明を限定された実施形態と図面によって説明したが、本発明は、上記の実施形態に限定されることなく、本発明が属する分野における通常の知識を有する者であれば、このような実施形態から多様な修正及び変形が可能である。
【０２４２】
したがって、本発明の範囲は、開示された実施形態に限定されるものではなく、特許請求の範囲だけではなく特許請求の範囲と均等なものなどによって定められるものである。
【符号の説明】
【０２４３】
８００ 文書ランキング決定装置
８１０ 寄与係数算出部
８２０ 単語関連度スコア算出部
８３０ 寄与スコア算出部
８４０ 単語関連度スコア変更部
８５０ 文書ランキングスコア算出部
【特許請求の範囲】
【請求項１】
第１文書と第２文書との間の共通キーワードに対する前記第１文書の第１単語関連度スコアに基づいて前記第２文書の文書ランキングスコアを算出するステップと、
前記第１単語関連度スコアを第２単語関連度スコアに動的に変更するステップと、
前記第２単語関連度スコアに基づいて前記第２文書の文書ランキングスコアを更新するステップと、
を含み、
前記第１文書は前記第２文書へのリンクを含むことを特徴とする文書ランキング決定方法。
【請求項２】
第１文書と第２文書との共通キーワードに対する第１単語関連度スコアに基づいて第２文書の文書ランキングスコアを算出するステップは、
前記共通キーワードに対する第１寄与係数および前記第１単語関連度スコアに基づいて第１寄与スコアを算出するステップと、
前記第１寄与スコアを第２文書の前記共通キーワードに対する文書ランキングスコアに反映するステップと、
を含み、
前記第２単語関連度スコアに基づいて第２文書の文書ランキングスコアを更新するステップは、
前記共通キーワードに対する第２寄与係数を算出するステップと、
前記第１寄与係数、前記第１単語関連度スコア、前記第２寄与係数、および前記第２単語関連度スコアに基づいて第２寄与スコアを算出するステップと、
前記第２寄与スコアを前記第２文書の前記文書ランキングスコアに反映するステップと、
を含むことを特徴とする請求項１に記載の文書ランキング決定方法。
【請求項３】
前記第１単語関連度スコアを第２単語関連度スコアに動的に変更するステップは、前記第１文書の内容が変更されるステップを含み、
前記第１単語関連度スコアは、前記第１文書の内容が変更される前の前記第１文書の内容の前記共通キーワードに対する単語関連度スコアであり、前記第２単語関連度スコアは前記第１文書の内容が変更された後の前記第１文書の内容の前記共通キーワードに対する単語関連度スコアであることを特徴とする請求項１または２に記載の文書ランキング決定方法。
【請求項４】
前記第１単語関連度スコアを第２単語関連度スコアに動的に変更するステップは、前記第１文書の内容が生成されるステップを含み、
前記第２単語関連度スコアは、前記生成された内容における前記共通キーワードに対する単語関連度スコアであることを特徴とする請求項１から３のいずれかに記載の文書ランキング決定方法。
【請求項５】
前記第１単語関連度スコアを第２単語関連度スコアに動的に変更するステップは、前記第１文書の内容が削除されるステップを含み、
前記第１単語関連度スコアは、前記第１文書の内容が削除された後の前記共通キーワードに対する単語関連度スコアであることを特徴とする請求項１から４のいずれかに記載の文書ランキング決定方法。
【請求項６】
前記第１単語関連度スコアを第２単語関連度スコアに動的に変更するステップは、前記リンクが生成されるステップを含み、
前記第２単語関連度スコアは、前記第１文書の内容の前記共通キーワードに対する単語関連度スコアであり、前記第１単語関連度スコアが前記第２単語関連度スコアに変更されるとみなすことによって前記リンクの生成を反映することを特徴とする請求項１から５のいずれかに記載の文書ランキング決定方法。
【請求項７】
前記第１単語関連度スコアを第２単語関連度スコアに動的に変更するステップは、前記リンクが削除されるステップを含み、
前記第１単語関連度スコアは、前記第１文書の内容の前記共通キーワードに対する単語関連度スコアであり、前記第１単語関連度スコアが前記第２単語関連度スコアに変更されるとみなすことによって前記リンクの削除を反映することを特徴とする請求項１から６のいずれかに記載の文書ランキング決定方法。
【請求項８】
前記第１単語関連度スコアおよび前記第２単語関連度スコアは、前記第１文書の内容と前記共通キーワードとの間の関連性に基づいて算出されることを特徴とする請求項１から７のいずれかに記載の文書ランキング決定方法。
【請求項９】
前記第１寄与係数および前記第２寄与係数は、前記共通キーワードにおいて前記第２文書が前記第１文書の内容に寄与する係数であることを特徴とする請求項２から８のいずれかに記載の文書ランキング決定方法。
【請求項１０】
前記第１文書が含む各単語について、前記第１文書の前記単語に対する単語関連度スコアを算出するステップと、
前記第１文書のキーワードおよび前記第２文書のキーワードを抽出するステップと、
前記第１文書と前記第２文書との間の前記共通キーワードを抽出するステップと
をさらに含むことを特徴とする請求項１から９のいずれかに記載の文書ランキング決定方法。
【請求項１１】
前記第１文書への経路の開始文書である第３文書に対する、前記経路を通じた前記第１文書の寄与スコアおよび前記第１寄与係数に基づいて第３寄与スコアを算出するステップをさらに含むことを特徴とする請求項２から１０のいずれかに記載の文書ランキング決定方法。
【請求項１２】
前記第２文書の文書ランキングスコアは、前記共通キーワードに対する前記第２文書の単語関連度スコア、前記第１寄与スコア、前記第２寄与スコア、および前記第３寄与スコアに基づいて決定されることを特徴とする請求項１１に記載の文書ランキング決定方法。
【請求項１３】
前記文書ランキングスコアに基づいて前記第２文書の文書ランキングを決定するステップをさらに含むことを特徴とする請求項１から１２のいずれかに記載の文書ランキング決定方法。
【請求項１４】
請求項１から１３のいずれかに記載の方法を実行するためのプログラムが記録されたコンピュータで読み出し可能な記録媒体。
【請求項１５】
第１文書と第２文書との間の共通キーワードに対する前記第１文書の第１単語関連度スコアおよび前記共通キーワードに対する前記第１文書の第２単語関連度スコアを算出する単語関連度スコア算出部と、
前記第１単語関連度スコアを前記第２単語関連度スコアに変更する単語関連度スコア変更部と、
第１単語関連度スコアに基づいて前記第２文書の文書ランキングスコアを算出し、前記第２単語関連度スコアに基づいて前記第２文書の文書ランキングスコアを更新する文書ランキングスコア算出部と
を備え、
前記第１文書は前記第２文書へのリンクを含むことを特徴とする文書ランキング決定装置。
【請求項１６】
前記共通キーワードに対する第１寄与係数および第２寄与係数を算出する寄与係数算出部と、
前記第１寄与係数および前記第１単語関連度スコアに基づいて第１寄与スコアを算出し、前記第１寄与係数、前記第１単語関連度スコア、第２寄与係数、および前記第２単語関連度スコアに基づいて第２寄与スコアを算出する寄与スコア算出部と
をさらに備え、
前記文書ランキングスコア算出部は、前記第１寄与スコアを前記第２文書の前記共通キーワードに対する文書ランキングスコアに反映することによって前記第１単語関連度スコアに基づいて前記第２文書の文書ランキングスコアを算出し、前記第２寄与スコアを前記第２文書の前記文書ランキングスコアに反映することによって前記第２単語関連度スコアに基づいて前記第２文書の文書ランキングスコアを更新することを特徴とする請求項１５に記載の文書ランキング決定装置。
【請求項１７】
前記単語関連度スコア変更部は、前記第１文書の内容が変更される場合に前記第１単語関連度スコアを前記第２単語関連度スコアに変更し、
前記第１単語関連度スコアは、前記第１文書の内容が変更される前の前記第１文書の内容の前記共通キーワードに対する単語関連度スコアであり、前記第２単語関連度スコアは、前記第１文書の内容が変更された後の前記第１文書の内容の前記共通キーワードに対する単語関連度スコアであることを特徴とする請求項１５または１６に記載の文書ランキング決定装置。
【請求項１８】
前記単語関連度スコア変更部は、前記第１文書の内容が生成される場合に前記第１単語関連度スコアを前記第２単語関連度スコアに変更し、
前記第２単語関連度スコアは、前記生成された第１文書の内容の前記共通キーワードに対する単語関連度スコアであることを特徴とする請求項１５から１７のいずれかに記載の文書ランキング決定装置。
【請求項１９】
前記単語関連度スコア変更部は、前記第１文書の内容が削除される場合に前記第１単語関連度スコアを前記第２単語関連度スコアに変更し、
前記第１単語関連度スコアは、前記第１文書の内容が削除された後の前記共通キーワードに対する単語関連度スコアであることを特徴とする請求項１５から１８のいずれかに記載の文書ランキング決定装置。
【請求項２０】
前記単語関連度スコア変更部は、前記リンクが生成される場合に前記第１単語関連度スコアが前記第２単語関連度スコアに変更されたものとみなすことによって前記リンクの生成を反映し、
前記第２単語関連度スコアは、前記第１文書の内容の前記共通キーワードに対する単語関連度スコアであることを特徴とする請求項１５から１９のいずれかに記載の文書ランキング決定装置。
【請求項２１】
前記単語関連度スコア変更部は、前記リンクが削除される場合に前記第１単語関連度スコアが前記第２単語関連度スコアに変更されたものとみなすことによって前記リンクの削除を反映し、
前記第１単語関連度スコアは、前記第１文書の内容の前記共通キーワードに対する単語関連度スコアであることを特徴とする請求項１５から２０のいずれかに記載の文書ランキング決定装置。
【請求項２２】
前記第１文書のキーワードおよび前記第２文書のキーワードを抽出し、前記第１文書と前記第２文書との間の前記共通キーワードを抽出する共通キーワード抽出部をさらに備え、
前記単語関連度スコア算出部は、前記第１文書が含む各単語に対して前記第１文書の前記単語に対する単語関連度スコアを算出することを特徴とする請求項１５から２１のいずれかに記載の文書ランキング決定装置。
【請求項２３】
前記寄与スコア算出部は、前記第１文書への経路の開始文書である第３文書に対する、前記経路を通じた前記第１文書の寄与スコアおよび前記第１寄与係数に基づいて第３寄与スコアを算出し、
前記文書ランキングスコア算出部は、前記第３寄与スコアを前記第２文書の前記文書ランキングスコアに反映することを特徴とする請求項１６から２２のいずれかに記載の文書ランキング決定装置。
【請求項２４】
前記文書ランキングスコア算出部は、前記共通キーワードに対する前記第２文書の単語関連度スコア、前記第１寄与スコア、前記第２寄与スコア、および前記第３寄与スコアに基づいて前記第２文書の文書ランキングスコアを決定することを特徴とする請求項２３に記載の文書ランキング決定装置。
【請求項２５】
前記文書ランキングスコアに基づいて前記第２文書の文書ランキングを決定する文書ランキング決定部をさらに備えることを特徴とする請求項１５から２４のいずれかに記載の文書ランキング決定装置。
【請求項１】
第１文書と第２文書との間の共通キーワードに対する前記第１文書の第１単語関連度スコアに基づいて前記第２文書の文書ランキングスコアを算出するステップと、
前記第１単語関連度スコアを第２単語関連度スコアに動的に変更するステップと、
前記第２単語関連度スコアに基づいて前記第２文書の文書ランキングスコアを更新するステップと、
を含み、
前記第１文書は前記第２文書へのリンクを含むことを特徴とする文書ランキング決定方法。
【請求項２】
第１文書と第２文書との共通キーワードに対する第１単語関連度スコアに基づいて第２文書の文書ランキングスコアを算出するステップは、
前記共通キーワードに対する第１寄与係数および前記第１単語関連度スコアに基づいて第１寄与スコアを算出するステップと、
前記第１寄与スコアを第２文書の前記共通キーワードに対する文書ランキングスコアに反映するステップと、
を含み、
前記第２単語関連度スコアに基づいて第２文書の文書ランキングスコアを更新するステップは、
前記共通キーワードに対する第２寄与係数を算出するステップと、
前記第１寄与係数、前記第１単語関連度スコア、前記第２寄与係数、および前記第２単語関連度スコアに基づいて第２寄与スコアを算出するステップと、
前記第２寄与スコアを前記第２文書の前記文書ランキングスコアに反映するステップと、
を含むことを特徴とする請求項１に記載の文書ランキング決定方法。
【請求項３】
前記第１単語関連度スコアを第２単語関連度スコアに動的に変更するステップは、前記第１文書の内容が変更されるステップを含み、
前記第１単語関連度スコアは、前記第１文書の内容が変更される前の前記第１文書の内容の前記共通キーワードに対する単語関連度スコアであり、前記第２単語関連度スコアは前記第１文書の内容が変更された後の前記第１文書の内容の前記共通キーワードに対する単語関連度スコアであることを特徴とする請求項１または２に記載の文書ランキング決定方法。
【請求項４】
前記第１単語関連度スコアを第２単語関連度スコアに動的に変更するステップは、前記第１文書の内容が生成されるステップを含み、
前記第２単語関連度スコアは、前記生成された内容における前記共通キーワードに対する単語関連度スコアであることを特徴とする請求項１から３のいずれかに記載の文書ランキング決定方法。
【請求項５】
前記第１単語関連度スコアを第２単語関連度スコアに動的に変更するステップは、前記第１文書の内容が削除されるステップを含み、
前記第１単語関連度スコアは、前記第１文書の内容が削除された後の前記共通キーワードに対する単語関連度スコアであることを特徴とする請求項１から４のいずれかに記載の文書ランキング決定方法。
【請求項６】
前記第１単語関連度スコアを第２単語関連度スコアに動的に変更するステップは、前記リンクが生成されるステップを含み、
前記第２単語関連度スコアは、前記第１文書の内容の前記共通キーワードに対する単語関連度スコアであり、前記第１単語関連度スコアが前記第２単語関連度スコアに変更されるとみなすことによって前記リンクの生成を反映することを特徴とする請求項１から５のいずれかに記載の文書ランキング決定方法。
【請求項７】
前記第１単語関連度スコアを第２単語関連度スコアに動的に変更するステップは、前記リンクが削除されるステップを含み、
前記第１単語関連度スコアは、前記第１文書の内容の前記共通キーワードに対する単語関連度スコアであり、前記第１単語関連度スコアが前記第２単語関連度スコアに変更されるとみなすことによって前記リンクの削除を反映することを特徴とする請求項１から６のいずれかに記載の文書ランキング決定方法。
【請求項８】
前記第１単語関連度スコアおよび前記第２単語関連度スコアは、前記第１文書の内容と前記共通キーワードとの間の関連性に基づいて算出されることを特徴とする請求項１から７のいずれかに記載の文書ランキング決定方法。
【請求項９】
前記第１寄与係数および前記第２寄与係数は、前記共通キーワードにおいて前記第２文書が前記第１文書の内容に寄与する係数であることを特徴とする請求項２から８のいずれかに記載の文書ランキング決定方法。
【請求項１０】
前記第１文書が含む各単語について、前記第１文書の前記単語に対する単語関連度スコアを算出するステップと、
前記第１文書のキーワードおよび前記第２文書のキーワードを抽出するステップと、
前記第１文書と前記第２文書との間の前記共通キーワードを抽出するステップと
をさらに含むことを特徴とする請求項１から９のいずれかに記載の文書ランキング決定方法。
【請求項１１】
前記第１文書への経路の開始文書である第３文書に対する、前記経路を通じた前記第１文書の寄与スコアおよび前記第１寄与係数に基づいて第３寄与スコアを算出するステップをさらに含むことを特徴とする請求項２から１０のいずれかに記載の文書ランキング決定方法。
【請求項１２】
前記第２文書の文書ランキングスコアは、前記共通キーワードに対する前記第２文書の単語関連度スコア、前記第１寄与スコア、前記第２寄与スコア、および前記第３寄与スコアに基づいて決定されることを特徴とする請求項１１に記載の文書ランキング決定方法。
【請求項１３】
前記文書ランキングスコアに基づいて前記第２文書の文書ランキングを決定するステップをさらに含むことを特徴とする請求項１から１２のいずれかに記載の文書ランキング決定方法。
【請求項１４】
請求項１から１３のいずれかに記載の方法を実行するためのプログラムが記録されたコンピュータで読み出し可能な記録媒体。
【請求項１５】
第１文書と第２文書との間の共通キーワードに対する前記第１文書の第１単語関連度スコアおよび前記共通キーワードに対する前記第１文書の第２単語関連度スコアを算出する単語関連度スコア算出部と、
前記第１単語関連度スコアを前記第２単語関連度スコアに変更する単語関連度スコア変更部と、
第１単語関連度スコアに基づいて前記第２文書の文書ランキングスコアを算出し、前記第２単語関連度スコアに基づいて前記第２文書の文書ランキングスコアを更新する文書ランキングスコア算出部と
を備え、
前記第１文書は前記第２文書へのリンクを含むことを特徴とする文書ランキング決定装置。
【請求項１６】
前記共通キーワードに対する第１寄与係数および第２寄与係数を算出する寄与係数算出部と、
前記第１寄与係数および前記第１単語関連度スコアに基づいて第１寄与スコアを算出し、前記第１寄与係数、前記第１単語関連度スコア、第２寄与係数、および前記第２単語関連度スコアに基づいて第２寄与スコアを算出する寄与スコア算出部と
をさらに備え、
前記文書ランキングスコア算出部は、前記第１寄与スコアを前記第２文書の前記共通キーワードに対する文書ランキングスコアに反映することによって前記第１単語関連度スコアに基づいて前記第２文書の文書ランキングスコアを算出し、前記第２寄与スコアを前記第２文書の前記文書ランキングスコアに反映することによって前記第２単語関連度スコアに基づいて前記第２文書の文書ランキングスコアを更新することを特徴とする請求項１５に記載の文書ランキング決定装置。
【請求項１７】
前記単語関連度スコア変更部は、前記第１文書の内容が変更される場合に前記第１単語関連度スコアを前記第２単語関連度スコアに変更し、
前記第１単語関連度スコアは、前記第１文書の内容が変更される前の前記第１文書の内容の前記共通キーワードに対する単語関連度スコアであり、前記第２単語関連度スコアは、前記第１文書の内容が変更された後の前記第１文書の内容の前記共通キーワードに対する単語関連度スコアであることを特徴とする請求項１５または１６に記載の文書ランキング決定装置。
【請求項１８】
前記単語関連度スコア変更部は、前記第１文書の内容が生成される場合に前記第１単語関連度スコアを前記第２単語関連度スコアに変更し、
前記第２単語関連度スコアは、前記生成された第１文書の内容の前記共通キーワードに対する単語関連度スコアであることを特徴とする請求項１５から１７のいずれかに記載の文書ランキング決定装置。
【請求項１９】
前記単語関連度スコア変更部は、前記第１文書の内容が削除される場合に前記第１単語関連度スコアを前記第２単語関連度スコアに変更し、
前記第１単語関連度スコアは、前記第１文書の内容が削除された後の前記共通キーワードに対する単語関連度スコアであることを特徴とする請求項１５から１８のいずれかに記載の文書ランキング決定装置。
【請求項２０】
前記単語関連度スコア変更部は、前記リンクが生成される場合に前記第１単語関連度スコアが前記第２単語関連度スコアに変更されたものとみなすことによって前記リンクの生成を反映し、
前記第２単語関連度スコアは、前記第１文書の内容の前記共通キーワードに対する単語関連度スコアであることを特徴とする請求項１５から１９のいずれかに記載の文書ランキング決定装置。
【請求項２１】
前記単語関連度スコア変更部は、前記リンクが削除される場合に前記第１単語関連度スコアが前記第２単語関連度スコアに変更されたものとみなすことによって前記リンクの削除を反映し、
前記第１単語関連度スコアは、前記第１文書の内容の前記共通キーワードに対する単語関連度スコアであることを特徴とする請求項１５から２０のいずれかに記載の文書ランキング決定装置。
【請求項２２】
前記第１文書のキーワードおよび前記第２文書のキーワードを抽出し、前記第１文書と前記第２文書との間の前記共通キーワードを抽出する共通キーワード抽出部をさらに備え、
前記単語関連度スコア算出部は、前記第１文書が含む各単語に対して前記第１文書の前記単語に対する単語関連度スコアを算出することを特徴とする請求項１５から２１のいずれかに記載の文書ランキング決定装置。
【請求項２３】
前記寄与スコア算出部は、前記第１文書への経路の開始文書である第３文書に対する、前記経路を通じた前記第１文書の寄与スコアおよび前記第１寄与係数に基づいて第３寄与スコアを算出し、
前記文書ランキングスコア算出部は、前記第３寄与スコアを前記第２文書の前記文書ランキングスコアに反映することを特徴とする請求項１６から２２のいずれかに記載の文書ランキング決定装置。
【請求項２４】
前記文書ランキングスコア算出部は、前記共通キーワードに対する前記第２文書の単語関連度スコア、前記第１寄与スコア、前記第２寄与スコア、および前記第３寄与スコアに基づいて前記第２文書の文書ランキングスコアを決定することを特徴とする請求項２３に記載の文書ランキング決定装置。
【請求項２５】
前記文書ランキングスコアに基づいて前記第２文書の文書ランキングを決定する文書ランキング決定部をさらに備えることを特徴とする請求項１５から２４のいずれかに記載の文書ランキング決定装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２０１２−７４０３４（Ｐ２０１２−７４０３４Ａ）
【公開日】平成２４年４月１２日（２０１２．４．１２）
【国際特許分類】
【出願番号】特願２０１１−２０８６１１（Ｐ２０１１−２０８６１１）
【出願日】平成２３年９月２６日（２０１１．９．２６）
【出願人】（５０５２０５８１２）エヌエイチエヌ コーポレーション (408)
【公開日】平成２４年４月１２日（２０１２．４．１２）
【国際特許分類】
【出願日】平成２３年９月２６日（２０１１．９．２６）
【出願人】（５０５２０５８１２）エヌエイチエヌ コーポレーション (408)
[ Back to top ]