対話形サーチクエリーを改良するためシステム及び方法
【課題】ユーザの好みにより近いサーチ結果をもたらすために、サーチクエリーをより絞り込んで定義されたクエリーに改良する際にユーザへの支援を提供する。
【解決手段】受信クエリーは、該受信クエリーに対応するランク付けされた文書の初期グループを作成するように処理される。ランク付けされた文書の初期グループ内の文書の全部又は一部の各文書は、ランク付けされた候補用語のそれぞれのセットの各候補用語が文書内に組み込まれるように、ランク付けされた候補用語のそれぞれのセットに関連付けられる。ランク付けされた候補用語の各それぞれのセットは、受信クエリーの処理の前の時点で識別される。選択関数に従って、候補用語のそれぞれのセットの１つ又はそれ以上内の候補用語のサブセットが選択される。受信クエリーに応答して、ランク付けされた文書の初期グループと候補用語のサブセットとが提示される。
【解決手段】受信クエリーは、該受信クエリーに対応するランク付けされた文書の初期グループを作成するように処理される。ランク付けされた文書の初期グループ内の文書の全部又は一部の各文書は、ランク付けされた候補用語のそれぞれのセットの各候補用語が文書内に組み込まれるように、ランク付けされた候補用語のそれぞれのセットに関連付けられる。ランク付けされた候補用語の各それぞれのセットは、受信クエリーの処理の前の時点で識別される。選択関数に従って、候補用語のそれぞれのセットの１つ又はそれ以上内の候補用語のサブセットが選択される。受信クエリーに応答して、ランク付けされた文書の初期グループと候補用語のサブセットとが提示される。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、２００３年３月２１日に出願した代理人整理番号１０１３０−０４４−８８８の名称が「対話形サーチクエリー改良のためのシステム及び方法」の米国特許出願番号第６０／４５６，９０５号に対する優先権を主張し、その全体が引用により本明細書に組み込まれる。本発明は、データベース内の文書、或いはインターネット又はイントラネットに結合されたサーバ上に格納された文書を探し出すためのサーチエンジンなどのサーチエンジン分野に関し、詳細には、本発明は、ユーザにとって関心のある文書を探し出すためにそのサーチクエリーを改良する際にサーチエンジンのユーザを支援するためのシステム及び方法に関する。
【背景技術】
【０００２】
ユーザの情報のニーズを伝え、該ニーズが目標文書の語彙内で表現される方法と一致する検索式を作ることは、テキストサーチエンジンのユーザにとって困難な認知タスクとして長い間認識されてきた。サーチエンジンユーザの大多数は、１つ又は２つの語だけのクエリーを用いて文書のサーチを始め、次いで、サーチエンジンによって得られた最初の１０位の結果の中にユーザが求める文書又は複数の文書が見つからないと失望する。少なくとも幾つかのサーチでは、結果をランク付けする方法を改善することによってユーザの満足度を向上させることができるが、極めて広範なサーチクエリーでは、多くの様々なサーチエンジンユーザのより具体的な情報要求を満たすことはできない。ユーザがクエリー式を改良するのを助ける１つの方法は、丁度司書が情報を探している人と対面した会話で行うように、用語の提案を提供することである。しかしながら、システムでは、概念的にクエリーに関係する可能性のある何百の中から、サーチを行っているユーザに最も関係がありそうな用語がどれであるかを「推測」しなければならないので、これを自動的に行うことは全く別のことである。関連する用語を選択するための一般的な方法には、オンラインシソーラス又は以前のログに記録されたクエリーのデータベース（現在のクエリー内の１つ又はそれ以上の語を含む以前のクエリーを見つけるためにサーチすることができる）に照会することが含まれる。このような方法の欠点は、このようにして得られた関連用語が文書自体のコーパス内で使用される内容又は語彙を実際に反映している保証がないことである。この理由により、関連用語をクエリーの実際の結果から動的に収集しようと試みる代替方法が多くの関心を集めている。
【０００３】
改良提案を生成するためにサーチ結果セットを使用する幾つかの従来方法には、用語関連性フィードバック（例えば、「Ｆａｓｔ ａｎｄ Ｅｆｆｅｃｔｉｖｅ Ｑｕｅｒｙ Ｒｅｆｉｎｅｍｅｎｔ」， Ｖｅｌｅｚ他， ＳＩＧＩＲ’９７会報 ｐ６−ｐ１５）、ハイパーインデックス（「Ｑｕｅｒｙ Ｒｅｆｏｒｍｕｌａｔｉｏｎ ｏｎ ｔｈｅ Ｉｎｔｅｒｎｅｔ：Ｅｍｐｉｒｉｃａｌ Ｄａｔａ ａｎｄ ｔｈｅ Ｈｙｐｅｒｉｎｄｅｘ Ｓｅａｒｃｈ Ｅｎｇｉｎｅ」， Ｂｒｕｚａ及びＤｅｎｎｉｓ， ＲＩＡＯ’９７会報 ｐ５００−ｐ５０９）、パラフレーズ（「Ｔｈｅ Ｐａｒａｐｈｒａｓｅ Ｓｅａｒｃｈ Ａｓｓｉｓｔａｎｔ：Ｔｅｒｍｉｎｏｌｏｇｉｃａｌ Ｆｅｅｄｂａｃｋ ｆｏｒ Ｉｔｅｒａｔｉｖｅ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｅｅｋｉｎｇ」， Ａｎｉｃｋ及びＴｉｐｉｒｎｅｎｉ，ＳＩＧＩＲ’９９会報、ｐ１５３−ｐ１５９）、及びクラスタリング（「Ｗｅｂ Ｄｏｃｕｍｅｎｔ Ｃｌｕｓｔｅｒｉｎｇ：Ａ Ｆｅａｓｉｂｉｌｉｔｙ Ｄｅｍｏｎｓｔｒａｔｉｏｎ」， Ｚａｍｉｒ及びＥｔｚｉｏｎｉ， ＳＩＧＩＲ’９８会報 ｐ４６−ｐ５４）がある。ほとんどの関連性フィードバック法は、部分一致サーチエンジン用に設計されており、通常、ユーザによって関連するもの或いは関連しないものとして明示的にタグ付けされた検索文書のサブセット全体にわたる計算から得られた複数の重み付けされた用語を付加することによって、クエリー式を展開することを伴う。ハイパーインデックスは、サーチエンジンによって返された断片の全体にわたり構文解析器を作動させて、クエリー用語を包含する名詞句を抽出する。パラフレーズは、結果として得られたセット文書から名詞句を抽出し、語句拡散に基づいて表示するためのフィードバック用語を選択する。クラスタリング法は、結果のセット断片をクラスタ化し、それぞれのクラスタ内に出現してくる用語から代表的なクエリー用語を得ようとするものである。これらの方法の多くは機能的であるが、生成されたフィードバック用語のランタイム性能又は関連性のいずれかの原因により、巨大なウェブサーチエンジンでも多少不十分である。サーチを向上させるための関連のサーチ用語の識別において、ユーザを支援する効率的な方法に対する当該技術分野における必要性がある。
【０００４】
従来技術の限界をよく理解するためには、「Ｆａｓｔ ａｎｄ Ｅｆｆｅｃｔｉｖｅ Ｑｕｅｒｙ Ｒｅｆｉｎｅｍｅｎｔ」， Ｖｅｌｅｚ他， ＳＩＧＩＲ’９７会報 ｐ６−ｐ１５を綿密に調べることで保証される。Ｖｅｌｅｚ他は、初期クエリーを改良するために、自動的な提案からの用語を初期クエリーに付加するクエリー改良のシステム及び方法を提供する。Ｖｅｌｅｚ他の文献では、一般的なクエリー改良プログラムＤＭをベースに構成されている。Ｖｅｌｅｚ他文献で示されるように、ＤＭは以下のステップを有する：
Ｃ＝文書コーパス
ｑ＝ユーザクエリー
ｒ＝検討するマッチング文書の数
Ｗfcn（Ｓ）＝アルゴリズム特定重み用語セットＳ
とすると、
１．クエリーｑにマッチする文書のセットＤ（ｑ）∈Ｃを計算する。
２．文書にマッチするトップｒのサブセットＤr（ｑ）を選択する。
３．ｄが文書、ｔが用語である場合に、Ｔ（ｑ）＝｛ｔ｜∃ｄ∈Ｄr（ｑ）：ｔ∈ｄ｝であるような文書Ｄr（ｑ）から用語のセットＴ（ｑ）を計算する。
４．最も高い重みＷfcn（Ｓ）でＴ（ｑ）からｎ個の用語のサブセットＳを計算する。
５．Ｓを用語提案のセットとしてユーザに提示する。
Ｖｅｌｅｚ他文献で示されるように、この方法は、高コストのランタイム技法であるので満足できるものではない。言い換えると、文書データベース（コーパス）が大きい場合において、ＤＭを使用して用語提案のセットＳを計算するために不満足な時間量を取ることになる。
【０００５】
Ｖｅｌｅｚ他は、ＤＭによって動的に実行される作業のかなりの量を事前計算することによってＤＭの速度を向上させようとしている。この事前計算段階では、Ｖｅｌｅｚ他は、コーパスの各単語の用語ｔを、単一の用語クエリーｔを所与としてＤＭアルゴリズムが提案する用語のそれぞれのセットｍにマップするデータ構造を作成する。次に、ランタイムにおいて、ユーザから任意のクエリーが受信される。クエリーは通常、用語のセットを含む。クエリーに応答して、Ｖｅｌｅｚ他は、クエリーの用語の各々に対応する用語のそれぞれのセットｍを収集し、これらのセットの各々を単一のセットにマージし、次いで、これが改良されたサーチのための提案としてユーザに戻される。例えば、ユーザがクエリー「スペースシャトル」を入力する場合を考える。この事例では、Ｖｅｌｅｚ他は、語「スペース」に対して事前計算されている用語のセットｍと、語「シャトル」に対して事前計算されている用語のセットｍとを取得することができ、これらを一緒にマージしてクエリー「スペースシャトル」に対して提案される用語のセットを得るようにする。
【０００６】
この方法は、オフラインで用語の関連性のサブセットを事前計算することによってランタイム性能を向上させるが、Ｖｅｌｅｚ他の方法には欠点がある。第１に、文脈の問題がある。Ｖｅｌｅｚ他の方法は、用語ｔがそれ自体で或いは複数用語クエリーの一部として現れるかどうかに関わらず、所与の用語ｔに関連する用語のセットｍが同じであるという仮定に依存する。しかしながら、この仮定は常に真であるとは限らない。複数用語句内に現れる用語は、ある事例においては、それ自体が現れている用語に対して完全に異なる意味を表すことがある。Ｖｅｌｅｚ他でのベースとなる仮定により、この方法は幾つかの事例では不適切なサーチ用語提案を潜在的にもたらす可能性があり、或いは、クエリー全体の文脈内でより関連性があるはずの他の提案を見逃す可能性がある。第２に、コーパス（文書データベース）が変わると、Ｖｅｌｅｚ他の方法は、用語の各セットｍが、場合によってはコーパスに最近加えられたファイルを含むコーパスの複数のファイルのコンテンツに依存するので、コーパスの用語ｔにそれぞれ関連する用語のセットｍを再計算することが必要となる。
【０００７】
Ｘｕ及びＣｒｏｆｔ，ＳＩＧＩＲ’９７、ｐ４−ｐ１１は、幾つかの概念（サーチ用語）を含むことができるサーチクエリーが受け取られる前に、所与の概念に関係する用語のセットが事前計算される別の方法を説明している。Ｖｅｌｅｚ他の方法と同様に、Ｘｕ及びＣｒｏｆｔの方法は、コーパスが時間につれて変化するときに概念に関連する用語の広範な再計算を必要とする、静的クロス文書データ構造及び統計の構成に依存する。従って、Ｘｕ及びＣｒｏｆｔの計算要求は、極めて大きな動的文書データベースにとっては不満足なものである。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】米国特許出願番号第６０／４５６，９０５号公報
【非特許文献】
【０００９】
【非特許文献１】「Ｆａｓｔ ａｎｄ Ｅｆｆｅｃｔｉｖｅ Ｑｕｅｒｙ Ｒｅｆｉｎｅｍｅｎｔ」， Ｖｅｌｅｚ他， ＳＩＧＩＲ’９７会報 ｐ６−ｐ１５
【非特許文献２】「Ｑｕｅｒｙ Ｒｅｆｏｒｍｕｌａｔｉｏｎ ｏｎ ｔｈｅ Ｉｎｔｅｒｎｅｔ：Ｅｍｐｉｒｉｃａｌ Ｄａｔａ ａｎｄ ｔｈｅ Ｈｙｐｅｒｉｎｄｅｘ Ｓｅａｒｃｈ Ｅｎｇｉｎｅ」， Ｂｒｕｚａ及びＤｅｎｎｉｓ， ＲＩＡＯ’９７会報 ｐ５００−ｐ５０９
【非特許文献３】「Ｔｈｅ Ｐａｒａｐｈｒａｓｅ Ｓｅａｒｃｈ Ａｓｓｉｓｔａｎｔ：Ｔｅｒｍｉｎｏｌｏｇｉｃａｌ Ｆｅｅｄｂａｃｋ ｆｏｒ Ｉｔｅｒａｔｉｖｅ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｅｅｋｉｎｇ」， Ａｎｉｃｋ及びＴｉｐｉｒｎｅｎｉ，ＳＩＧＩＲ’９９会報、ｐ１５３−ｐ１５９
【非特許文献４】「Ｗｅｂ Ｄｏｃｕｍｅｎｔ Ｃｌｕｓｔｅｒｉｎｇ：Ａ Ｆｅａｓｉｂｉｌｉｔｙ Ｄｅｍｏｎｓｔｒａｔｉｏｎ」， Ｚａｍｉｒ及びＥｔｚｉｏｎｉ， ＳＩＧＩＲ’９８会報 ｐ４６−ｐ５４
【発明の概要】
【００１０】
上記従来技術から、ユーザの好みにより近いサーチ結果をもたらすために、サーチクエリーをより絞り込んで定義されたクエリーに改良する際にユーザへの支援を提供することが望まれる。
本発明は、文書インデックスから文書を検索するよう設計されたサーチクエリーを改良するための改善された方法を提供する。本発明は、コーパスが更新される度に再計算しなければならないクロス文書データ構造又はグローバル統計に依存しないので有利である。更に本発明は、句のミックス、単語用語、及び特殊化（クエリー用語を含む句）を含む関連のある提案の短いリストを作成するために、周知の方法に比べてランタイムでフェッチする必要のある結果が少ないので、クエリー時（ランタイム）にＩ／Ｏ資源を必要とすることが著しく少ない。本発明において、文書インデックスでの各文書は、例えば文書インデックスの作成中にクエリーに先立つある時間に処理される。この処理では、文書インデックスでの各文書は、文書がその文書に対するランク付けされた候補用語のセット内に含むのに何らかの適切な用語を含むかどうかを判定するために調べられる。文書がこのような用語を含む場合、文書への文書インデックスの入力は、文書と関連付けられた用語のセットを含むよう構成される。この用語のセットは、ランク付けされた候補用語のセットと呼ばれる。
【００１１】
クエリーが受け取られると、文書の初期グループが文書インデックスから検索される。文書の初期グループは、クエリーに対する関連性によってランク付けされる。文書の「初期グループ」は、クエリーに対して潜在的に関係があるものとして識別された文書のフルセットのうちのセブセットとすることができる。１つの実施形態において、初期グループでの文書の数は、クエリーに潜在的に関係があるものとして識別された全文書より少なく、パラメータ値は通常２０と２００の間（例えば５０）である。次に、重み付け関数は、ランク付けされた文書の初期グループでの文書に関連するランク付けされた候補用語のいずれかのセットに現れる各候補用語に加えられる。トップスコアリング候補用語は、クエリーに応答してランク付けされた文書の初期グループと共に提示される。提示された候補用語の１つをユーザが選択することにより、オリジナルのサーチクエリーへ用語を付加することになる。
【００１２】
本発明の１つの態様は、受信クエリーを改良する方法を提供する。受信クエリーは、受信クエリーに対応するランク付けされた文書の初期グループを作成するように処理される。ランク付けされた文書の初期グループでの文書の全部又は一部の各文書は、ランク付けされた候補用語のそれぞれのセットに関連付けられる。候補用語の種々のそれぞれのセットにおける各候補用語は、ランク付けされた文書の初期グループの文書内に組み込まれる。各候補用語は、語又は句とすることができる。更に、好ましい実施形態において、候補用語の種々のそれぞれのセットは受信クエリーを処理する前の時点で構成される。この方法は、続いて、ランク付けされた候補用語の種々のそれぞれのセットの１つまたはそれ以上内にある候補用語のサブセットを選択する。選択関数は、この候補用語のサブセットを選択するのに使用される。次に受信クエリーに応答して、ランク付けされた文書の初期グループと候補用語のサブセットとが提示される。幾つかの実施形態において、処理、選択、及び提示が、オリジナルの受信クエリーと候補用語のサブセットからの候補用語とを含む変更されたクエリーを使用して繰り返される。
【００１３】
幾つかの実施形態において、文書と関連付けられた候補用語のセットは、文書の用語を候補用語のマスターリストと比較することによって構成される。用語が候補用語のマスターリストに存在する場合、その用語は、候補用語として文書と関連付けられた候補用語のセットに加えられる。幾つかの実施形態において、候補用語のマスターリストは、１０，０００，０００より多い候補用語を含む。この比較は、文書内の用語の最大数が検討されるか或いは固有の用語の閾値数が検討されるまで繰り返される。次に重み付け及び／又は選択関数が、ランク付けされた候補用語のセットを作成するために候補用語のセットに加えられる。一般的に、この重み付け及び／又は選択関数は、候補用語をランク付けし、次いで、高くランク付けされた用語だけが保持されるカットオフを適用する。幾つかの実施形態において、候補用語のマスターリストは、特定の言語（例えば、英語、スペイン語、フランス語、ドイツ語、ポルトガル語、イタリア語、ロシア語、中国語、又は日本語）について最適化される。幾つかの実施形態において、ランク付けされた文書の初期グループにおける文書の全部又は一部の各文書は、候補用語のマスターリストが最適化された言語と同じ言語である。
【００１４】
幾つかの実施形態において、文書インデックスの各文書は、クエリープロセスの前（例えば初期文書インデックス中）の時点で分類される。幾つかの実施形態において、２つの可能なクラス、すなわち第１の家族向けクラスと第２の非家族向けクラスがある。文書の分類の指定は、文書インデックスに含まれる。
【００１５】
幾つかの実施形態において、実際には、ランク付けされた候補用語のセットのより複雑な用語のサブセット（サブストリング）であるランク付けされた候補用語のセット内の単語候補用語が廃棄される。更に、より複雑な用語は、ランク付けされた候補用語のセットに関連する文書の全部或いは上位部分において単純な用語が現れた事例の回数に対してクレジットが与えられる。この廃棄及びクレジットは、ランク付けされた候補用語のセットにおけるより複雑な候補用語のサブセットである単語候補用語が無くなるまで繰り返される。更に、同じ手順をより複雑な用語のサブセットである複数語候補用語に適用できる。
【００１６】
幾つかの実施形態において、ランク付けされた候補用語のセット内の第２用語の正字の異形又は屈折異形であるランク付けされた候補用語のセットにおける候補用語が廃棄される。更に、第２用語は、ランク付けされた候補用語のセットに関連する文書の全部又は上位部分において正字の異形又は屈折異形用語が現れた事例の回数に対してクレジットが与えられる。この廃棄及びクレジットは、ランク付けされた候補用語のセット内の別の用語の正字の異形又は屈折異形である用語が無くなるまで繰り返される。幾つかの事例では、第２用語は、両方の（例えば複数の）正字の異形又は屈折異形を含む結合用語として候補セット内に上書きされ、関連する文書の全部或いは上位部分に最も現れた異形が結合用語に最初に現れる。幾つかの実施形態において、結合用語が提示された候補用語のサブセットに含めるために選択される場合、結合用語の第１部分のみがユーザに提示される。
【００１７】
本発明の幾つかの実施形態は、クエリーに応答して提示されることになる候補用語のサブセットを選択するのに使用される種々の選択関数を提供する。幾つかの実施形態において、この選択関数は、ランク付けされた文書の初期グループ内のトップランクの文書と関連付けられた候補用語のセットにおいて見つけられた情報を利用する。この情報は、ランキングの２つの形式を含む。最初に、文書がランク付けされる。次に、ランク付けされた文書の初期グループ内の文書と関連するランク付けされた候補用語の各セット内の各候補用語がランク付けされる。
【００１８】
１つの実施形態において、選択関数は、（ｉ）ランク付けされた文書の初期グループ内のトップランクの文書に関連するランク付けされた候補用語の各それぞれのセット内の各候補用語に対して重み付け関数を適用することを含む。本明細書で使用されるランク付けされた文書の初期グループの各トップランクの文書は、ある閾値ランキングよりも数値的に小さいランク（例えば５０、すなわちトップランクの文書がクエリーに戻されたランク付けされた文書の初期グループのトップ５０の文書内にある）を有する文書である。例えば、ランク付けされた文書の初期グループが１００の文書を含み、閾値ランキングが５０である場合を考える。このとき、最初の５０の文書はトップランクの文書とみなすことになる。最も高い重みを受け取っているこれらの候補用語は、クエリー結果と共に提示される候補用語のサブセット内に含まれる。幾つかの実施形態において、重み付け関数によって候補用語に加えられる重みは、候補用語が現れるトップランクの文書と関連付けられた候補用語のセットの数に応じて、ランク付けされた候補用語の各こうしたセット内の候補用語の平均位置に応じて、受信クエリーの用語が候補用語内に存在するかどうかによって、候補用語内の文字数によって、或いは候補用語の関連するセット内に用語を含むトップランクの文書の平均ランク位置によって決定される。幾つかの実施形態において、重み付け関数によって候補用語に加えられる重みは、ＴｅｒｍＣｏｕｎｔ、ＴｅｒｍＰｏｓｉｔｉｏｎ、ＲｅｓｕｌｔＰｏｓｉｔｉｏｎ、ＴｅｒｍＬｅｎｇｔｈ、及びＱｕｅｒｙＩｎｃｌｕｓｉｏｎのいずれかの組合せ又はいずれかの重み付けサブセットに応じて決定され、ここで、
ＴｅｒｍＣｏｕｎｔは、（ｉ）候補用語を含み、且つ（ｉｉ）トップランクの文書にそれぞれ関連するランク付けされた候補用語のセットの数であり、
ＴｅｒｍＰｏｓｉｔｉｏｎは、（ｉ）候補用語を含み、且つ（ｉｉ）トップランクの文書にそれぞれ関連するランク付けされた候補用語のこれらのセットにおける候補用語の位置の関数（例えば平均）であり、
ＲｅｓｕｌｔＰｏｓｉｔｉｏｎは、候補用語を含むランク付けされた候補用語のセットに関連付けられるこれらのトップランクの文書のランクの関数（例えば平均）であり、
ＴｅｒｍＬｅｎｇｔｈは、候補用語の文字の数（候補用語の複雑性）であり、
ＱｕｅｒｙＩｎｃｌｕｓｉｏｎは、受信クエリーの用語が候補用語内に存在するかどうかを示す値である。
幾つかの実施形態において、重み付け関数によって候補用語に加えられる重みは、次式に応じて決定される。
ＴｅｒｍＣｏｕｎｔ＋ＴｅｒｍＰｏｓｉｔｉｏｎ＋ＲｅｓｕｌｔＰｏｓｉｔｉｏｎ＋ＴｅｒｍＬｅｎｇｔｈ＋ＱｕｅｒｙＩｎｃｌｕｓｉｏｎ
【００１９】
幾つかの実施形態において、ＴｅｒｍＣｏｕｎｔ、ＴｅｒｍＰｏｓｉｔｉｏｎ、ＲｅｓｕｌｔＰｏｓｉｔｉｏｎ、ＴｅｒｍＬｅｎｇｔｈ、及びＱｕｅｒｙＩｎｃｌｕｓｉｏｎは各々、別々に重み付けされる。幾つかの実施形態において、重み付け関数によって候補用語に加えられる重みは、次式に応じて決定される。
（ＴｅｒｍＣｏｕｎｔ*ｗ1）＋
（ＴｅｒｍＰｏｓｉｔｉｏｎ*（ｗ2＋（ＲｅｆｉｎｅｍｅｎｔＤｅｐｔｈ*ｗ2´）））＋
（ＲｅｓｕｌｔＰｏｓｉｔｉｏｎ*ｗ3）＋
（ＴｅｒｍＬｅｎｇｔｈ*（ｗ4＋（ＲｅｆｉｎｅｍｅｎｔＤｅｐｔｈ*ｗ4´）））＋
（ＱｕｅｒｙＩｎｃｌｕｓｉｏｎ*（ｗ5＋（ＲｅｆｉｎｅｍｅｎｔＤｅｐｔｈ*ｗ5´）））
ここで、ｗ1、ｗ2、ｗ3、ｗ4、ｗ5、ｗ2´、ｗ4´、及びｗ5´は別々の重みであり、ＲｅｆｉｎｅｍｅｎｔＤｅｐｔｈは受信クエリーに対して処理が行われた回数である。
【００２０】
幾つかの実施形態において、選択関数は、ランク付けされた文書の初期グループ内の各文書について文書の分類を決定する段階を含む。次いで、文書のセットの閾値パーセンテージが第１分類（例えば、家族向けカテゴリー）に属する場合には、第２分類（例えば、非家族向けカテゴリー）のメンバーである文書に属するランク付けされた候補用語の全セットは、候補用語のサブセットを形成するのには使用されない。
【００２１】
本発明の別の態様は、コンピュータシステムと共に使用するコンピュータプログラム製品を提供する。コンピュータプログラム製品は、コンピュータ可読記憶媒体とこれに組み込まれたコンピュータプログラム機構とを含む。コンピュータプログラム機構は、受信クエリーを改良するためのクエリー改良提案エンジンを含む。このエンジンは、受信クエリーに対応するランク付けされた文書の初期グループを作成するように受信クエリーを処理する命令を含む。ランク付けされた文書の初期グループ内の文書の全部又は一部の各文書は、ランク付けされた候補用語のそれぞれのセットの各候補用語が文書内に組み込まれるように、ランク付けされた候補用語のそれぞれのセットに関連付けられる。ランク付けされた候補用語の各それぞれのセットは、受信クエリーの処理の前の時点で識別される。エンジンは更に、選択関数に従って、候補用語のそれぞれのセットの１つ又はそれ以上内にある候補用語のサブセットを選択する命令を含む。更に、エンジンは、受信クエリーに応答して、ランク付けされた文書の初期グループと候補用語のサブセットとを提示する命令を含む。
【００２２】
本発明の更に別の態様は、複数のユニフォームリソースロケータ（ＵＲＬ）から構成される文書インデックスデータ構造を提供する。各ＵＲＬはそれぞれの文書を指定する。複数のＵＲＬによって指定されたそれぞれの文書の全部又は一部の各文書は、ランク付けされた候補用語のそれぞれのセットに関連付けられる。ランク付けされた候補用語のそれぞれのセットの各候補用語は、ランク付けされた候補用語のセットに関連する文書に組み込まれる候補用語を含む。更に、これらの候補用語は、重み付け関数によってランク付けされる。幾つかの実施形態において、ランク付けされた候補用語のそれぞれのセットは、
（Ａ）ランク付けされた候補用語のそれぞれのセットに関連する文書内の用語を候補用語のマスターリストと比較し、ここで、その用語が候補用語のマスターリスト内に存在する場合には、その用語をランク付けされた候補用語のそれぞれのセットに候補用語として加え、
（Ｂ）文書内の用語の最大数が検討されるまで比較を繰り返し、
（Ｃ）重み付け関数に従って候補用語をランク付けし、これによりランク付けされた候補用語を形成する、
ことによって生成される。
【図面の簡単な説明】
【００２３】
【図１】サーチエンジンにクエリーを依頼しているクライアントコンピュータを示す図である。
【図２】本発明の実施形態に従って作り出される、クエリー改良提案を含むサーチ結果ページを示す図である。
【図３】サーチエンジンサーバのブロック図である。
【図４】サーチエンジンインデックスのブロック図である。
【図５】文書インデックス方法のフローチャートである。
【図６】ユーザによって提出されたクエリーを処理するための手順のフローチャートである。
【発明を実施するための形態】
【００２４】
本発明の上述の特徴及び利点、並びに本発明の付加的な特徴及び利点は、図面を併用しながら本発明の好ましい実施形態の詳細な説明の結果として以下でより明確に理解されるであろう。
同じ参照符号は、幾つかの図面全体を通して対応する要素を示す。
【００２５】
典型的な実施形態において、本発明は、効率的な方法でユーザのクエリーに潜在的により高度に関連し、且つ目標文書の語彙を反映するクエリー改良提案（候補用語のサブセット）の小さなセット（１０−２０）を作成する。
【００２６】
図１に示されるように、サーチクエリーは、クライアントコンピュータ１００によってサーチエンジンサーバ１１０に提出される。サーチエンジンサーバ１１０は、サーチクエリーを受信すると、該サーチクエリーに関連する文書インデックス１２０において文書を識別する。更に、サーチエンジンサーバ１１０は、例えば他のランキング要因のうちでサーチクエリーに対するこれらの関連性によって関連する文書をランク付けする。次いで、このランク付けされた文書のグループの記述（サーチ結果）は、ランク付けされた文書のグループとしてクライアントコンピュータ１００に戻される。本発明においては、候補用語のサブセットの形式（サーチ改良提案）での付加的な情報は、ランク付けされた文書の初期グループと共にクライアントコンピュータに戻される。
【００２７】
サーバ１１０が候補用語のサブセットを作成する方法の詳細に移る前に、本発明の利点をより良く理解できるように、サーチエンジンサーバ１１０の実施形態によって戻されたサーチ結果及びサーチ改良提案のスクリーンショットが図２に提供されている。図２で、ユーザは初期クエリー（受信クエリー）１３２を提供する。検索ボタン１３４が押されると、クエリー１３２がクライアントコンピュータ１００からサーチエンジンサーバ１１０に送られる。クエリー１３２が受信されると、サーチエンジンサーバ１１０は、受信クエリー１３２を処理し、サーチ結果及びサーチ改良提案をランク付けされた文書の初期グループ及び候補用語のサブセットの形式でクライアントコンピュータ１００に送り返す。候補用語のサブセットは、インターフェース１８０のパネル１４０に表示される。具体的には、候補用語のサブセットの各用語１３６が、タグ１３８と共に領域１４０内に表示される。同時に、サーチ結果のリスティング（ランク付けされた文書の初期リストのトップランクの文書）がパネル１４２に表示される。本発明のシステム及び方法は、オリジナルのクエリー１３２を絞り込み、変更し、又は改善することができる用語１３６を識別することに関する。ユーザがタグ１３８を押すと、タグ１３８に対応する用語１３６が初期クエリー１３２に付加され、新しいクエリーに関してプロセス全体が繰り返される。ユーザが別のタグ１３９を押すと、タグ１３８に対応する用語１３６は初期クエリー１３２を更新し、サーチエンジンサーバは、当該用語１３６を新しいクエリーとして処理する。図示されていない実施形態において、各用語１３６に対応する１つ又はそれ以上の付加的なタグは、パネル１４０に追加することができる。１つの実施例では、対応する用語１３６を例外リストに付加するのに使用されるタグが存在する。例えば、オリジナルクエリーを「Ａ」とし、ユーザが用語「Ｂ」の排他タグを押すと、新しいクエリーが「Ａ」になり「Ｂ」ではなくなる。パネル１４０に表示された用語のサブセットに加えて、ランク付けされた文書の初期グループがパネル１４０に表示される。コンピュータ１００とサーバ１１０との間の帯域幅を節約するために、典型的な実施形態では、ランク付けされた文書の初期グループは通常、ランク付けされた文書の初期グループの各文書の標識を含み、ユーザが初期のランク付けされた文書における該文書の各々の性質を判断できるようにする。このような標識（ｉｎｄｉｃｉａ）は更に、本明細書ではランク付けされた文書の初期グループと呼ばれる。
【００２８】
本発明のシステム及び方法の概要が開示されてきた。この概要から、本発明の多くの利点及び特徴が明らかにされる。本発明の新しいアルゴリズムは、初期クエリーの改良に使用することができる提案された用語１３６のリストをユーザに自動的に提供する。例えば図２において、初期クエリー１３２は「スペースシャトル」である。この初期クエリーに応答して、本発明の実施形態は、「チャレンジャー大事故」のような用語１３６を含む候補用語のサブセットを提供する。初期クエリーへの用語「チャレンジャー大事故」の追加、或いは初期クエリーの用語「チャレンジャー大事故」への置換は、ユーザの関心事に恐らくはより近接して一致するクエリーをユーザに提供する。候補用語の新しいサブセットを使用することによって、ユーザは、ランク付けされた文書の初期グループ内の文書（又はその標識（ｉｎｄｉｃｉａ））を分析することなく改善されたクエリーを構築することができる。従って、本発明を使用すると、多すぎる（又は少なすぎる）結果、或いはユーザの情報の必要性に直接関係しない結果を初期クエリーが生成する理由を識別する必要性がもはやなくなる。
【００２９】
本発明の概要及び利点を提示してきたので、次に本発明のシステム及び方法の更に詳細な説明を開示する。この目的のために、図３は、本発明の１つの実施形態によるサーチエンジンサーバ１１０を示している。好ましい実施形態において、サーチエンジンサーバ１１０は、図３に概略的に示すように１つ又はそれ以上のコンピュータシステム３００を使用して実施される。大量のクエリーを処理するよう設計されたサーチエンジンは、図３に示されるものよりも更に複雑なコンピュータアーキテクチャを使用することができることは当業者には理解されるであろう。例えば、サーバのフロントエンドセットを用いて、実際にクエリーを処理するバックエンドサーバのセット間でクエリーを受信及び分散することができる。このようなシステムでは、図３に示されたシステム３００は、バックエンドサーバの１つとなる。
【００３０】
コンピュータシステム３００は通常、ユーザインターフェース３０４（ディスプレイ３０６及びキーボード３０８を含む）、１つ又はそれ以上の処理ユニット（ＣＰＵ）３０２、ネットワーク又は他の通信インターフェース３１０、メモリ３１４、及びこれらの構成要素を相互接続するための１つ又はそれ以上の通信バス３１２を有することになる。メモリ３１４は、高速ランダムアクセスメモリを含むことができ、また、１つ又はそれ以上の磁気ディスク記憶装置（図示せず）などの不揮発性メモリを含むことができる。メモリ３１４は、（１つ又は複数の）中央処理ユニット３０２から遠隔に設置される大容量記憶装置を含むことができる。メモリ３１４は、
・ 種々の基本システムサービスを扱い、且つハードウェア従属タスクを実行するための手順を含むオペレーティングシステム３１６と、
・ インターネット、他のワイドエリアネットワーク、ローカルエリアネットワーク（例えば、ローカル無線ネットワークはクライアントコンピュータ１００をコンピュータ３００に接続できる）、メトロポリタンエリアネットワークなどの１つ又はそれ以上の通信ネットワークを介して種々のクライアントコンピュータ１００（図１）及び場合によっては他のサーバ又はコンピュータにシステム３００を接続するのに使用されるネットワーク通信モジュール３１８と、
・ クライアントコンピュータ１００からクエリーを受信するためのクエリーハンドラ３２０と、
・ クエリーに関係のある文書の文書インデックス３５２をサーチして、クエリーに関係のあるランク付けされた文書の初期グループを形成するためのサーチエンジン３２２と、
・ 本発明の多くの態様を実施するためのクエリー改良提案エンジン３２４と、
を記憶することが好ましい。
【００３１】
クエリー改良提案エンジン３２４は、実行可能な手順、サブモジュール、テーブル、及び他のデータ構造を含むことができる。１つの実施形態において、改良提案エンジン３２４は、
・ ランク付けされた文書の初期グループと共に提示するための候補用語のサブセットを識別するための選択関数３２６と、
・ 提示のために候補用語のサブセットとランク付けされた文書の初期グループとをフォーマッティングするための結果フォーマッティングモジュール３２８と、
を含む。
【００３２】
本発明の方法は、クエリー１３２が文書インデクサ３４４の動作でクエリーハンドラ３２０によって受信される前に始まる。文書インデクサ３４４は、ウェブクローリング及びインデキシング技術を使用して文書インデックス３５２を構築する。しかしながら、この従来の機能に加えて、文書インデクサ３４４は、文書インデックス３５２の文書を更に処理する新しいプログラムモジュールを含む。例えば、文書インデクサ３４４は、「候補用語セットのコンストラクタ」３４６を含む。好ましい実施形態において、コンストラクタ３４６は、文書インデックス３５２の各文書を調べる。他の実施形態において、予め定められた基準を満たしている文書（例えば、予め定められた言語のセットのうちの１つのテキストが含まれている文書）だけがコンストラクタ３４６によって調べられる。
【００３３】
調べられる各文書について、コンストラクタ３４６は、文書に埋め込まれた何らかの候補用語を該文書が含むかどうかを判定する。このタスクをコンストラクタ３４６が達成することができる多くの異なる方法が存在し、全てのこのような方法は本発明の範囲内に含まれる。１つの実施形態において、タスクは、文書からの用語を候補用語のマスターリスト３４２に一致させることによって達成される。候補用語のマスターリスト３４２は、全ての可能性のある候補用語を含む。幾つかの実施形態において、リスト３４２は、有効な候補用語のリストを備えるＵｎｉｘスタイルのテキストファイルである。リスト３４２の代表的なフォーマットは、１行につき１つの候補用語があり、リスト３４２固有の各候補用語は、全てのコンマ、タブ、エンドライン、及び＠記号が省略されてＵＴＦ−８で符号化される。幾つかの実施形態において、マスターリストは、名詞及び名詞句（クエリー用語として有用となる可能性が最も高い用語の種類）に限定され、制限されたクエリー改良値のどのような名詞句も明示的に取り除かれる。
【００３４】
典型的な実施形態では、文書インデックス３５２の各文書の第１部分のみが候補用語について調べられる。例えば、幾つかの事例では、文書インデックス３５２の各文書の最初の１００，０００バイトのみがコンストラクタ３４６によって調べられる。幾つかの実施形態において、コンストラクタ３４６は、文書の用語の最大数（例えば、１００、１０００、５０００など）が検討されるまで文書インデックス３５２の文書を調べる。幾つかの実施形態において、文書の候補用語のサーチは、文書の固有の用語の閾値数がマスターリスト３４２（例えば１００用語）内で発生したことが判明した時点で終了する。
【００３５】
本発明の幾つかの実施形態は、１つより多い候補用語のマスターリスト３４２を提供する。各マスターリスト３４２は、種々の言語について最適化される。例えば、第１リスト３４２は英語について最適化され、第２リスト３４２はスペイン語について最適化される。従って、英語リスト３４２は英語の文書において見られる情報用語を含むことになり、スペイン語リスト３４２はスペイン語の文書において見られる情報用語を含むことになる。同様に、本発明の幾つかの実施形態は、フランス語、ドイツ語、ポルトガル語、イタリア語、ロシア語、中国語、又は日本語について最適化されたリストを含む。本発明の幾つかの実施形態において、リスト３４２は、カテゴリーの他のタイプについて最適化される。例えば、幾つかの実施形態において、リスト３４２は、科学用語、ファッション用語、光学用語、又は旅行用語を含めるように最適化される。しかしながら、好ましい実施形態において、各マスターリスト３４２は、情報用語を可能な限り含む。実際に、マスターリスト３４２は、１０，０００，０００より多い用語を含むことができ、通常は１，０００，０００よりかなり多い用語を含む。これらの用語の各々は、語又は句とすることができる。理解しやすいように、代表的な句は「チャレンジャー大事故」である。
【００３６】
文書で使用される主たる言語を決定する方法は、当該技術分野で公知である。従って、本発明の幾つかの実施形態においては、コンストラクタ３４６は、（ｉ）調べられている文書の言語を決定し、及び（ｉｉ）文書と同じ言語について最適化されたマスターリスト３４２を使用するためにこうした方法を用いる。
【００３７】
マスターリスト３４２にある１つ又はそれ以上の候補用語がインデックス３５２の文書の上位部分（例えば、最初の１００キロバイト）に組み込まれている場合、コンストラクタ３４６による文書の調査の最終結果は、これらの用語の識別である。こうした用語がコンストラクタ３４６によって識別されると、これらはランク付けされた形式で文書と関連付けられたデータ構造に付加される。このデータ構造は、候補用語のセットと呼ばれる。インデックス３５２がコンストラクタ３４６によって調べられた後、その上位部分に候補用語を組み込んだインデックス３５２内の各文書は、こうした用語を含む候補用語のそれぞれのセットに関連付けられることになる。従って、例えば、インデックス３５２において候補用語を含む２つの文書ＡとＢがある場合、候補用語の第１セットが文書Ａに関連付けられ、候補用語の第２セットは文書Ｂに関連付けられる。候補用語の第１セットは、文書Ａの上位部分に組み込まれた各候補用語を含むことになり、ランク付けされた候補用語の第２セットは、文書Ｂの上位部分に組み込まれた各用語を含むことになる。実際には、候補用語の各セットは、以下に更に詳細に開示されるように内部的にランク付けされて、候補用語のそれぞれのランク付けされたセットを形成するようにする。
【００３８】
図４は、コンストラクタ３４６による文書インデックス３５２での文書４０２の調査が文書インデックス３５２の修正をどのように生じさせるかを示している。コストラクター３４６がインデックス３５２の文書を調べる前に、インデックス３５２の各文書４０２は、文書４０２のユニフォームリソースロケーション（ＵＲＬ）４０６並びに特徴値のセット４０８を含む。特徴値４０８は、文書に関連付けられたメタデータを含み、更に、ランキング文書がクエリーに潜在的に関係するものとして識別されたときにサーチエンジンを支援する値を含む。特徴値は、文書のファイルフォーマット、文書の長さ、文書への周知のインバウンドリンク（他の文書からの）の数、文書のタイトル（例えば、クエリーに応答するものとして文書が選択された時間を表示するための）などの指標を含むことができる。文書４０２がコンストラクタ３４６（図３）によって調べられた後で、候補用語のセット４１０は文書４０２に関連付けられる。
【００３９】
本発明の幾つかの実施形態において、文書内の用語をリスト３４２の候補用語と一致させる方法は、その用語をリスト３４２の可能性のある最も複雑な候補用語と確実に一致させる方式で実行される。例えば、ＡとＢを各語とするときに用語「ＡＢ」がインデックス３５２の文書に組み込まれる場合を考える。更に、リスト３４２は、「Ａ」、「Ｂ」、及び「ＡＢ」を含むと仮定する。これが起こる場合、文書の用語「ＡＢ」は、リスト３４２の「ＡＢ」と一致することになり、「Ａ」又は「Ｂ」とは一致しない。このようなマッチングを行うことができる幾つかの方法が存在し、全てのこのようなマッチング手法は本発明の範囲内にある。１つのこのようなマッチング方法は、以下の論理を有する「左−右貪欲アルゴリズム」を使用する：
調べられる文書の形式「ＡＢＣＤ．．．」の各文について：
Ａはリスト３４２の候補用語の接頭辞であるか？
○はい：「ＡＢ」はリスト３４２の候補用語の接頭辞であるか？
■はい：「ＡＢＣ」はリスト３４２の候補用語の接頭辞であるか？
●はい−＞同じ方式で文全体のドリリングを続ける
●いいえ：文書と関連付けられた候補用語のセット４１０に「ＡＢ」を加え、Ｃに移り、「ＣＤＥＦ．．．」を検討する
■いいえ：文書と関連付けられた候補用語のセット４１０に「Ａ」を加え、Ｂに移り、「ＢＣＤＥ．．．」を検討する
○いいえ：Ｂに移り、「ＢＣＤＥ．．．」の検討を始める
このようなアルゴリズムは、「文」が行のような文書のある任意の量であるか、或いは２つの句の境界又は他の区切り点の間の文書の部分であり、及び「ＡＢＣＤ．．．」が用語の各語である場合、リスト３４２の最も複雑な用語を文書の用語に確実に一致させる。関連する方法では、コンストラクタ３４６は、第１候補用語が候補用語のセットにおける第２候補用語のサブセットである場合、候補用語のセット４１０の第１候補用語を廃棄する。
【００４０】
本発明の幾つかの実施形態において、、セット４１０に関連付けられた文書の全部又は上位部分（例えば最初の１００キロバイト）においてランク付けされた用語のセット４１０の各候補用語が現れる回数が追跡される。例えば、セット４１０の候補用語「Ａ」がセット４１０と関連付けられた文書の上位部分に１２回現れる場合には、用語「Ａ」が文書に１２回現れるという指示が示され、どの候補用語がランク付けされた候補用語の最終セットに残ることになるかを判定するよう設計された重み付け方式で使用される。
【００４１】
幾つかの実施形態において、関連する文書に用語が現れる回数の表示は、用語が文書の語の第１閾値数内に現れる事例毎に重みが追加される。例えば、第１閾値の値が１５語である場合を考えてみる。更に、この例示的な場合において、候補用語「Ａ」は正確に二度現れる。句「Ａ」の第１の出現は、１５語限界の前であり、「Ａ」の第２の出現は１５語限界の後である。この例示的な場合に使用される重み付け方式において、最初の１５語内に現れている語は、二倍の重みを受け取る。従って、文書と関連付けられる候補用語のセット４０２では、候補用語「Ａ」は、用語が文書の上位部分において（２*１＋１）、すなわち３回出現する指示と共にリストされることになる。最初の閾値のより複雑な形式が可能であることは、当業者であれば理解するであろう。例えば、候補用語カウントに加えられた重みは、文書の候補用語の位置の関数とすることができる。例えば、これは、文書の始めに最大値を有し、且つ文書の最後に最小値を有する線形関数（又は非線形関数、もしくは区分線形関数）とすることができる。代替えとして重みをバスケットに加えることができ、この場合、文書の始め（第１バスケット）に大きな重みがあり、文書の第２部分（第２バスケット）に低い重みがあり、文書の第３部分（第３バスケット）に更に低い重みなどがある。
【００４２】
（ｉ）候補用語の回数の指示が関連する文書に現れ、且つ（ｉｉ）コンストラクタ３４６がランク付けされた候補用語のセット４１０の第１候補用語を廃棄する実施形態では、第１候補用語がランク付けされた候補用語のセットの第２候補用語のサブセットである場合には、第２候補用語は、第１候補用語がコンストラクタ３４６によって文書内で識別された回数でクレジットされる。
【００４３】
コンストラクタ３４６に加えて、インデクサ３４４は冗長フィルタ３４８を含む。フィルタ３４８は、正字の異形又は屈折異形を取り除いて最後に候補用語のセットとなることができるよう設計されている。用語の正字の異形は、用語についての他の正しいスペル（綴り）を有する。用語の屈折異形は、別の接尾辞、又は用語のアクセント形式を有する。幾つかの実施形態において、正字の異形及び／又は屈折異形は、異形リスト３６０に記憶される（図３）。従って、冗長フィルタ３４８の仕事は、候補用語のセット４１０の候補用語のペアが異形リスト３６０に確実に存在しないようにすることである。候補用語のセット４１０の候補用語のペアが異形リスト３６０に存在するときには、ペアに由来する１つの用語は、フィルタ３４８によってセット４１０から廃棄される。幾つかの実施形態において、ペアの第１用語がセット４１０から効率的に廃棄され、ペアの第２用語は保存されることになる。しかしながら、幾つかの実施形態において、第２用語は、廃棄された第１用語と結合されるように修正されることになる。例えば、用語Ａ及びＢが屈折異形又は正字の異形である場合、用語の１つ、すなわちＡは廃棄され、別の用語Ｂが保存される。更に、用語ＢはＡ，Ｂとして上書きされる。この特徴は、クエリー改良提案エンジン３２４のような本発明のより高レベルのモジュールによって使用可能な基礎となる文書についての有用な情報を保存するので有利である。通常、エンジン３２４は、これらのマージされた正字の異形又は屈折異形の候補用語が現れる場合の第１（廃棄されなかった）用語だけを提示することになる。例えば、上書きされた用語Ａ、Ｂの場合、用語「Ａ」だけがパネル１４０に提示された候補用語のサブセットに含まれる。通常、リスト３６０に現れている用語のペアで廃棄された用語は、関連する文書においてあまり頻繁には現れない用語である。幾つかの実施形態において、ある種のノイズワード（例えば、ａ、ｔｈｅ、ｗｈｏ、ｗｈａｔ、ｗｈｅｒｅなど）の有無だけが相違する候補用語は、正字の異形又は屈折異形を含む候補用語が共にフォールドされるのと同じ方式でフォールドされる。同様に、幾つかの実施形態において、候補用語の所与のセットの２つの用語の違いが句読点の有無だけである場合、２つの用語は、正字の異形又は屈折異形を含む候補用語が共にフォールドされるのと同じ方式で共にフォールドされる。幾つかの実施形態において、候補用語のセットの各句は、同じケース（例えば小文字）に変換される。この規則の例外は、６つ又はこれより少ない大文字の単語であるこれらの用語が、こうした用語が頭辞語になる可能性がある理由から小文字には変換されないことである。
【００４４】
（ｉ）候補用語の回数の指示が関連する文書に現れ、（ｉｉ）候補用語のセットの第１候補用語が候補用語のセットの第２候補用語の正字の異形又は屈折異形であるために、候補用語のセットの第１候補用語をフィルタ３４８が廃棄する両方の実施形態において、第２候補用語は、第１候補用語がコンストラクタ３４６によって文書で識別された回数でクレジットされる。言い換えると、２つの候補用語の間の違いが、候補用語の一方が他方の候補用語の対応する語の屈折異形又は正字の異形である単語を含むだけである場合に、候補用語の一方が廃棄される。この実施例は、候補用語「ｔｏｗ ｔｒｕｃｋ」と「ｔｏｗ ｔｒｕｃｋｓ」の場合に起こる。この実施例では、２つの候補用語の間の違いは、第１用語の「ｔｒｕｃｋ」の列挙と第２用語での「ｔｒｕｃｋｓ」の列挙だけである。
【００４５】
文書インデクサ３４４についての多くの詳細が開示されてきた。このステージでは、インデクサ３４４の幾つかの実施形態によって用いられるステップを開示する図５のフロー線図を検証することが有益である。他のインデキシングデューティ（例えば、ウェブクローラによって見出される文書の中の語の従来のインデキシング）の全部又は一部の後で、インデクサ３４４はコンストラクタ３４６に制御をわたし、該コンストラクタ３４６はインデックスされた文書を選択する（図５のステップ５０２）。
【００４６】
ステップ５０４で、文書中の用語が候補用語のマスターリスト３４２と比較される。用語がマスターリスト３４２にある（５０６−はい）の場合、用語は、文書に関連付けられた候補用語のセット４０２に加えられる（５１０）。ステップ５０４が、上記に説明された左−右貪欲アルゴリズムなどのより複雑なマッチング方式を包含できる点に留意されたい。
【００４７】
幾つかの実施形態において、比較されることになる文書はウェブページである。従って、マスターリスト３４２に対する比較に適した有効な語を構成するものに関して幾つかの決定を行う必要がある。１つの方法では、実際にはウェブページである文書を構文解析して句抽出のためのテキストを見出す。１つの実施形態において、句マッチングは、全ての「ビジブル」テキストプラスメタページ記述を使用してステップ５０４で実行され、このような句は、ＨＴＭＬコード、ジャバスクリプトなどを含まない。有効な句を得るために、ウェブページ内の「句境界」（例えばテーブルタグ）が、リスト３４２との比較のために文書から抽出された表現が句境界を跨がないように保存される。本発明の幾つかの実施形態に使用される句境界の付加的な実施例は、限定ではないが「，」、「？」のような句読点、空行などを含む。
【００４８】
本発明の幾つかの実施形態において、マスターリスト３４２は、幾つかの異種ソースから集められた用語の極めて大きなセットである。従って、ステップ５０４で、情報の候補用語だけが確実に選択されて候補用語のセットに含まれるように付加的なフィルタリングを実行することができる。幾つかの実施形態において、マスターリスト３４２内の用語と比較される文書内の用語は、比較の前に処理される。例えば、幾つかの実施形態において、句読点マークはリスト３４２との比較の前に用語から取り除かれる。幾つかの実施形態において、句読点文字は、リスト３４２との比較の前にスペースに置き換えられる。幾つかの実施形態において、ノイズ用語のリスト３５４がメモリ３１４に記憶される。代表的なノイズ用語は、限定ではないが、「ａ」、「ｔｈｅ」、「ｗｈｏ」、「ｗｈａｔ」、及び「ｗｈｅｒｅ」などの語を含む。従って、ノイズ用語のリスト３５４がメモリ３１４に記憶される実施形態において、比較ステップ５０４では、マスターリスト３４２と比較されることになる用語がノイズ用語のリスト３５４内に存在するかどうかが最初に判定されることになる。存在する場合には、用語は無視され、リスト３４２とは比較されない。幾つかの実施形態において、ステップ５０４で文字の少なくともある最小閾値を包含する用語だけが比較される。例えば、幾つかの実施形態では、ステップ５０４で少なくとも４つの文字を包含する用語だけを比較する。
【００４９】
決定５０６の結果に関わらず、コンストラクタ３４６によって文書内の他のいずれかの用語をマスターリスト３４２と比較する必要があるかどうかに関して判定５０８が行われる。決定５０８の結果を判定するために使用できる多くの種々の条件（例えば、用語カットオフの最大数、固有用語カットオフの最大数、セット４１０内に既に存在する候補用語の最大数など）が開示されている。
【００５０】
図５のフローチャートに続くのは任意選択のステップである。任意選択のステップ５１２で、冗長用語は、文書に関連付けられた候補用語のセットにフォールドされる。任意選択のステップ５１４で、インデックス３５２内の文書が分類される（例えば第１及び第２クラスに）。
【００５１】
分類ステップ５１４を行うことができる幾つかの異なる方法があり、全てのこのような方法は本発明の範囲内に含まれる。例えば、幾つかの実施形態において、各文書４０２は第１又は第２クラスに分類される。好ましい実施形態において、第１クラスは家族向けクラスであり、第２クラスは非家族向けクラスである。文書４０２は、性的に露骨な、不快な、或いは暴力的な言葉を含む場合には第２クラスに分類される。それ以外は、第１クラスに分類される。幾つかの実施形態において、分類モジュール３５０（図３）は、このような分類を行うために使用される。一般的に分類モジュール３５０は、文書が、性的に露骨な、不快な、或いは暴力を含む傾向があるかどうか判定することによって働く。このような傾向がある場合には、該文書は非家族向けと指定される。この指定は、分類されたセット４１０に関連付けられる文書に対応する特徴値４０８（図４）に記憶される。
【００５２】
この段階では、通常候補用語のセット内に多数の候補用語が存在する。例えば、１０００もの数の候補用語を候補用語のセットに加えることができる実施形態では、候補用語のセットはこの段階で１０００の用語を含むことができる。各候補用語セット内の候補用語の数に関わらず、これらはランク付けされない。従って、ステップ５１６において候補用語がランク付けされ、ランク付けされた候補用語のＮ番目までの最も高い数が、候補セットに残ることが許可され、全ての他の候補用語が取り除かれて、ランク付けされたセット（５１６）のＮ番目（例えば２０）までの最も代表的な用語だけを保持するようにする。従って、ステップ５１６の有効作用は、候補用語のセットからランク付けされた候補用語のセットを作り出すことである。更にステップ５１６で、トップランクの用語（例えばトップ２０）だけがランク付けされた候補用語のセットに残ることが許可される。
【００５３】
ランク付け関数によって使用される基準又はパラメータは、各用語が文書に現れる回数、用語が文書の予め定義された初期部分に現れるかどうか、文書での用語の最初の位置、及び用語の文字数のうちの１つ又はそれ以上を含むことができる。これらのパラメータに基づいて、ランクが各候補用語に割り当てられ、次いで、最も高いランクを有するＮ番目までの用語だけがランク付け候補用語のセット内に保持される。他の用語は、そのセットから削除される。各文書と関連付けられた候補用語の数を制限することは、文書インデックスが過剰に大きくなるのを防ぐのに役立ち、処理の速度を最優先する場合にクエリー時に考慮する必要のある用語の量を低減する。ある文書についてランク付けされた候補用語のセットは、文書のインデックスエントリー（図４の４１０を参照）、候補用語を表わしているストリングのセット（任意選択的に圧縮される）又はインデックスに記憶することによって文書と関連付けることができ、ここでは各インデックス値は、候補用語のマスターリスト３４２における用語を示す。関係する値は、ランキングプロセスで使用される用語スコアが文書及び／又は文書の用語の第１位置に現れるように、文書と関連付けられた各候補用語（又は候補用語へのポインタ）と共に文書の文書インデックス３５２エントリーに記憶することができる。しかしながら、好ましい実施形態において、このような付加的な値は文書インデックス３５２には記憶されない。
【００５４】
ランク付けされた候補用語のセット４１０が文書インデックス３５２の文書に関連付けられるプロセスを説明してきた。次に、本発明の１つの実施形態に従って、このようなセット４１０が提示用の候補用語のサブセットを構成するのに使用される方法を説明する図６に注目されたい。ステップ６０２で、クエリーはクエリーハンドラ３２０によって受信される。ステップ６０４で、クエリーは、文書インデックス３５２からランク付けされた文書の初期グループを検索することによって処理される。幾つかの実施形態において、ランク付けされた文書の初期グループがその文書自体以外の文書の標識（ｉｎｄｉｃｉａ）のみを包含できる点は理解されるであろう。しかしながら、この標識（ｉｎｄｉｃｉａ）は、文書の初期セットの各文書に対するユニフォームリソースロケータ（ＵＲＬ）を含むことになる。従って、各文書は、ユーザによって引き続き要求される場合にはインターネット（又はネットワークの他のある形態）から検索することができる。幾つかの実施形態において、文書の初期セットは、サーバ３００（図３）のメモリ３１４にサーチ結果３４０として記憶される。再び図６を参照すると、提案されたクエリー改良のリスト（候補用語のサブセット）がサーチ結果３４０を使用して作成される（６０６）。
【００５５】
提案されたクエリー改良のリスト（候補用語のサブセット）が作成される方法は、クエリーが家族向けサーチであるかどうかに依存することになる。任意選択のステップ６０８で、サーチ結果３４０（ランク付けされた文書の初期グループ）の各トップランクの文書（例えば最初の５０文書）について文書の分類が行われる。サーチ結果３４０でのトップランクの文書の閾値パーセンテージが、第１分類（家族向け分類）に属する場合、第１分類に属さないトップランクの文書と関連付けられた候補用語の全てのセット４１０は、図６の後続のあらゆるステップにおいても使用されない。幾つかの実施形態において、家族向け以外の分類はインデキシング（図５）中に文書を分類するのに使用される。このような実施形態では、このような分類を使用して、ランク付けされた候補用語のどのセットが候補用語のサブセットを構成するのに使用されるかをステップ６０８で判定することができる。例示的な実施形態において、Ｍ個のトップランクの文書（例えば、サーチ結果３４０からの１０個のトップランクの文書）のみの分類は、ステップ６０８で判定を行うのに使用される。例えば、１０個のトップランクの文書の少なくとも８つが家族向けであると分類される場合、非家族向け文書からの候補用語は、提案されたクエリー改良のリストを作成するのに使用されるランク付けされた候補用語のセットから除外される。
【００５６】
ステップ６１０で、サーチ結果３４０の文書に関連するランク付けされた候補用語のそれぞれのセットの１つ又はそれ以上内に存在する候補用語のサブセットが選択される。１つの実施形態において、この選択関数は、ランク付けされた文書の初期グループ（サーチ結果３４０）のトップランクの文書に関連するランク付けされた候補用語の各それぞれのセット４１０における各候補用語に重み付け関数を適用する段階を含む。ランク付けされた文書の初期グループ内の各トップランクの文書は、閾値ランキングより数値的に小さいランキングを有する。幾つかの実施形態において、トップランクの文書は、Ｔを５０などの予め定義された数（及び好ましくは５から２００までの範囲、更に好ましくは２０から１００までの範囲にある）とすると、Ｔ個のトップランクの文書である。ステップ６１０では、関係する用語をユーザに提示される候補用語のサブセットに集める機会を最大にするために、トップランクの文書だけが検討される。種々の実施形態において、トップ５、１０、１５、２０、５０、又は１００の文書だけが検討される。最も高い重みを受け取るこれらの候補用語は、候補用語のサブセットに含まれる。幾つかの実施形態において、候補用語のサブセットの用語の数は、２５より少ない数に制限される。
【００５７】
幾つかの実施形態において、サーチ結果３４０の初期グループに文書のカットオフ数より少ない文書がある場合、候補用語のサブセットは構築されず、候補用語のサブセットはユーザに提示されない。例えば、１つの実施形態において、サーチ結果３４０の初期グループにおいて３５より少ない文書がある場合には候補用語のサブセットは構築されない。
【００５８】
本発明は、サーチ結果３４０のトップランクの文書に関連付けられたセット４１０の各々において候補用語をスコアするための幾つかの異なる重み付け関数を提供する。これらの異なる重み付け関数は、エンジン３２２（図３）の選択関数３２４の種々の実施形態で使用される。
【００５９】
幾つかの実施形態において、関数３２４（重み付け関数）によって候補用語に加えられる重みは、（ｉ）候補用語を含むもの、及び（ｉｉ）トップランクの文書にそれぞれ関連付けられるものの両方であるランク付けされた候補用語のセットの数に応じて決定される。例えば、５０のトップランクの文書があり、候補用語「スペースシャトル」がトップランクの文書にそれぞれ関連するランク付けされた候補用語のセットの３つにおいて現れる場合を考える。この場合、３の重みが、候補用語「スペースシャトル」に加えられることになる。
【００６０】
幾つかの実施形態において、選択関数３２６によって候補用語に加えられる重みは、（ｉ）候補用語を含み（ｉｉ）トップランクの文書にそれぞれ関連するランク付けされた候補用語のこれらのセットの候補用語の関数（例えば平均）に応じて決定される。幾つかの実施形態は、用語を含むセットと用語を含まないセットの両方を考慮する。用語を含まないセットは、用語がセット内に存在しないことを示す平均化のための数値を割り当てられる。このような重み付け係数は、ランク付けされた候補用語の各セットが実際にはランク付けされた順序リストであることを利用する。従って、候補用語「スペースシャトル」がトップランク文書にそれぞれ関連付けられた候補用語の多くのセットのランク付けリストのトップに現れる場合には、この重み付け方式では比較的高い重みを受け取ることになる。逆に、用語「スペースシャトル」が、これが現れるランク付けされた候補用語の各セットの最終用語の間にある場合、該用語はこの重み付け方式で比較的低い重みを受け取ることになる。
【００６１】
幾つかの実施形態において、関数３２４によって候補用語に加えられる重みは、受信クエリーの用語が候補用語内に存在するかどうかに応じて決定される。例えば、クエリー用語が「シャトル」であって候補用語が「スペースシャトル」である場合、候補用語は全重みが与えられ、これ以外は重みを与えられない。
【００６２】
幾つかの実施形態において、関数３２４（重み付け関数）によって候補用語に加えられる重みは、候補用語の文字数に応じて決定される。例えば、候補用語「スペースシャトル」は、候補用語「犬」よりもより大きな重みを受け取ることになる。
【００６３】
幾つかの実施形態において、関数３２４によって候補用語に加えられる重みは、候補用語を含むランク付けされた候補用語のセットに関連付けられたトップランクの文書のランクの関数（例えば平均）に応じて決定される。このような重み付け方式は、サーチエンジン３２２によってサーチ結果の初期セットに既に加えられているランキングを活用する。このような重み付け方式では、より高いランクの文書と関連付けられたセット４１０からの候補用語は、より低いランクの文書と関連付けられた候補用語よりも高い優先度が与えられる。例えば、候補用語「スペースシャトル」が、ランク付けされた文書の初期グループ内のトップランクの文書の文書２、４、及び６に関連するランク付けされた候補用語のそれぞれのセットに現れる場合を考える。すなわち、この重み付け方式では、用語「スペースシャトル」は値４の関数である重みを受け取ることになる。ここで、用語「スペースシャトル」が、ランク付けされた文書の初期グループのトップランク文書におくる文書１０、２０、及び３０に関連するランク付けされた候補用語のそれぞれのセットに現れると仮定する。すなわち、この重み付け方式では、用語「スペースシャトル」は値２０の関数である重みを受け取ることになる。この重み付け方式では、値４は値２０で作られた重みに比べてより良好な重みを作り出すことになる（候補用語の重みを上げることになる）。幾つかの実施形態において、候補用語を含まないセットがこの重み付け関数で考慮される。これらは平均するための数値を割り当てられる。
【００６４】
幾つかの実施形態において、語が最初に候補用語として生じる文書のランクは重み付け関数に使用される。
【００６５】
選択関数３２６の種々の実施形態によって使用される特定の重み付け係数を、このような係数を導入するために概説してきた。しかしながら、好ましい実施形態において、幾つかのこのような係数は望ましい結果をもたらすために組み合わされる。以下は、選択関数３２６の幾つかの好ましい実施形態である。
【００６６】
幾つかの実施形態において、関数３２４によって候補用語に加えられる重みは、ＴｅｒｍＣｏｕｎｔ、ＴｅｒｍＰｏｓｉｔｉｏｎ、ＲｅｓｕｌｔＰｏｓｉｔｉｏｎ、ＴｅｒｍＬｅｎｇｔｈ、及びＱｕｅｒｙＩｎｃｌｕｓｉｏｎのいずれかの組合せ（又はいずれかの重み付けの組合せ）に応じて決定され、ここで、
ＴｅｒｍＣｏｕｎｔは、（ｉ）候補用語を含み、且つ（ｉｉ）トップランクの文書にそれぞれ関連するランク付けされた候補用語のセットの数であり、
ＴｅｒｍＰｏｓｉｔｉｏｎは、（ｉ）候補用語を含み、且つ（ｉｉ）トップランクの文書にそれぞれ関連するランク付けされた候補用語のセットにおける候補用語の位置の関数（例えば平均）であり、
ＲｅｓｕｌｔＰｏｓｉｔｉｏｎは、候補用語を含むランク付けされた候補用語のセットに関連付けられたトップランクの文書のランクの関数（例えば平均）であり、
ＴｅｒｍＬｅｎｇｔｈは、候補用語の文字数（候補用語の複雑性）であり、
ＱｕｅｒｙＩｎｃｌｕｓｉｏｎは、受信クエリーの用語が候補用語内に存在するかどうかを示す値である。
【００６７】
本明細書で使用されるＱｕｅｒｙＩｎｃｌｕｓｉｏｎの適用（例えば、ＱｕｅｒｙＩｎｃｌｕｓｉｏｎが１のような非ゼロ値である場合）は、受信クエリーの用語が候補用語内に存在する場合に候補用語の重みが増やされることを意味する。更に、ＱｕｅｒｙＩｎｃｌｕｓｉｏｎの非適用（例えば、ＱｕｅｒｙＩｎｃｌｕｓｉｏｎがゼロに等しく設定される場合）は、受信クエリーの用語が候補用語内に存在しい場合に候補用語の重みが増やされないことを意味する。幾つかの実施形態において、候補用語はノイズ用語（例えば、ａ、ｔｈｅ、ｗｈｏ、ｗｈａｔ、ｗｈｅｒｅなど）に対してクレジットされない。従って、クエリーがノイズワード「ｆｏｒ」を含み、且つ候補用語がワード「ｆｏｒ」を含む場合には、クレジットは候補用語に与えられず、ＱｕｅｒｙＩｎｃｌｕｓｉｏｎは重みが増やされない。
【００６８】
幾つかの実施形態において、関数３２４によって候補用語に加えられる重みは次式に従って求められる。
ＴｅｒｍＣｏｕｎｔ＋ＴｅｒｍＰｏｓｉｔｉｏｎ＋ＲｅｓｕｌｔＰｏｓｉｔｉｏｎ＋ＴｅｒｍＬｅｎｇｔｈ＋ＱｕｅｒｙＩｎｃｌｕｓｉｏｎ
ここで、重みＴｅｒｍＣｏｕｎｔ、ＴｅｒｍＰｏｓｉｔｉｏｎ、ＲｅｓｕｌｔＰｏｓｉｔｉｏｎ、ＴｅｒｍＬｅｎｇｔｈ、及びＱｕｅｒｙＩｎｃｌｕｓｉｏｎは、上記に定義されたものと同じである。幾つかの実施形態において、ＴｅｒｍＣｏｕｎｔ、ＴｅｒｍＰｏｓｉｔｉｏｎ、ＲｅｓｕｌｔＰｏｓｉｔｉｏｎ、ＴｅｒｍＬｅｎｇｔｈ、及びＱｕｅｒｙＩｎｃｌｕｓｉｏｎは、各々別々に重み付けされる。
【００６９】
幾つかの実施形態において、関数３２４によって候補用語に加えられる重みは、次式に従って求められる。
（ＴｅｒｍＣｏｕｎｔ*ｗ1）＋
（ＴｅｒｍＰｏｓｉｔｉｏｎ*（ｗ2＋（ＲｅｆｉｎｅｍｅｎｔＤｅｐｔｈ*ｗ2´）））＋
（ＲｅｓｕｌｔＰｏｓｉｔｉｏｎ*ｗ3）＋
（ＴｅｒｍＬｅｎｇｔｈ*（ｗ4＋（ＲｅｆｉｎｅｍｅｎｔＤｅｐｔｈ*ｗ4´）））＋
（ＱｕｅｒｙＩｎｃｌｕｓｉｏｎ*（ｗ5＋（ＲｅｆｉｎｅｍｅｎｔＤｅｐｔｈ*ｗ5´）））
ここで、ｗ1、ｗ2、ｗ3、ｗ4、ｗ5、ｗ2´、ｗ4´、及びｗ5´は別々の重みである。更に、ＲｅｆｉｎｅｍｅｎｔＤｅｐｔｈは、受信クエリーについて処理が行われた回数である。言い換えると、ＲｅｆｉｎｅｍｅｎｔＤｅｐｔｈは、ユーザがオリジナルのサーチクエリーに候補用語のサブセットからの用語を加える任意選択のステップ６１４の実行操作によってステップ６０２から６１２が繰り返される回数である。１つの実施形態において、 ｗ1＝１００
ｗ2＝１５
ｗ2´＝１５
ｗ3＝１
ｗ4＝１
ｗ4´＝０
ｗ5＝１００、及び
ｗ5´＝５０である。
【００７０】
本発明の幾つかの実施形態において、選択関数６１０はランク付けされた候補用語のセットの幾つかの候補用語を取り除くことになる。例えば、幾つかの実施形態において、ある接頭辞又は接尾辞だけが異なるランク付けされた候補用語のセットの候補用語は、共にフォールドされる。例えば、幾つかの実施形態において、接頭辞のリスト及び接尾辞のリストはメモリ３１４に記憶される。２つの候補用語の違いが、候補用語の一方が他方の候補用語の対応する語に対して語の最初にある接頭辞、又は語の最後にある接尾辞が異なる語を含むだけの場合、２つの候補用語は共にフォールドされる。幾つかの実施形態において、接頭辞の３つのクラス（及び接尾辞の３つの類似のクラス）がある。候補用語が第１クラスに属している接頭辞を含む場合、その語は廃棄される。候補用語が第２クラスに属する接頭辞を含む場合、その接頭辞は取り除かれる。候補用語が第３クラスに属する接頭辞を含む場合、評価が行われる。この評価において、トップランクの文書と関連するランク付けされた候補用語のセットの各々は、接頭辞を含まない同じ用語の事例についてサーチされる。このような事例が見つからない場合、接頭辞はストリップされない。このような事例が見つかった場合、接頭辞はストリップされる。このタイプの接頭辞（及び接尾辞）処理は、多くの事例で有用である。例えば、候補用語が「ｔｈｅ ｃａｒｓ」である場合を考える。通常、接頭辞「ｔｈｅ」は、ストリップすべき接頭辞であると考えられる。しかしながら、候補用語が名称「ｔｈｅ ｃａｒｓ」で一般的に呼ばれている有名な音楽グループを意味する場合がある。従って、サーチは、接頭辞「ｔｈｅ」のない用語「ｃａｒｓ」がトップランクの文書と関連するランク付けされた候補用語の他のセットのいずれかに見つかるかどうかを確実に調べる。このような事例が現れない場合には、接頭辞はストリップされない。この実施例では、本明細書で使用される接頭辞を上述の接辞（例えば、ｕｎ−、ｎｏｎ−など）或いは上述の語又は句（例えば、ｔｈｅ、ｏｆ、ｔｏ ｇｏなど）とすることができる点に留意されたい。
【００７１】
ステップ６１２で、候補用語のサブセットがユーザに提示される。ステップ６１４で、ユーザは、候補用語のサブセットの用語１３６（図２）を任意選択的に選択し、オリジナル（受信された）クエリーとパネル１４０（図２）に表示された候補用語のサブセットから選択された候補用語１３６とを含む変更されたクエリーで、処理（ステップ６０４）、選択（ステップ６０６）、及び提示（ステップ６１２）が繰り返される。上記に説明されたように、幾つかの実施形態では、ユーザは、以前に提出されたクエリーに追加するため、以前に提出されたクエリーと置き換えるため、又は以前に提出されたクエリーと共に排他的な用語として使用するために用語１３６を選択することができる。
【００７２】
本明細書で引用される全ての引例は、全体的に、及び各個々の出版物又は特許もしくは特許出願が具体的であり且つ全ての目的のためその全てにおいて本明細書に組み込まれることが個々に示される程度まで全ての目的のために本明細書に組み込まれる。
【００７３】
本発明は、コンピュータ可読記憶媒体に組み込まれたコンピュータプログラム機構を含むコンピュータプログラム製品として実施することができる。例えば、このコンピュータプログラム製品は、図３に示されたプログラムモジュールを包含できる。これらのプログラムモジュールは、ＣＤ−ＲＯＭ、磁気ディスク記憶製品、或いは他の何らかのコンピュータ可読データ又はプログラム記憶製品に記憶できる。コンピュータプログラム製品のソフトウェアモジュールもまた、インターネット又は他の方法を介して、搬送波上のコンピュータデータ信号（これにソフトウェアモジュールが組み込まれる）の伝送によって電気的に配信することができる。
【００７４】
本発明の多くの修正及び変形は、当業者には明らかなように本発明の精神及び範囲から逸脱することなく行うことができる。本明細書で説明された特定の実施形態は、例証としてのみ提供される。実施形態は、本発明の原理、及びその実際的応用を正しく説明するために選ばれて説明されたが、これによって当業者は企図される特定の用途に適する種々の修正により本発明及び種々の実施形態をより良好に利用することができる。本発明は、添付の請求項が与える均等物の全範囲と共にこれらの請求項によってのみ限定されるものとする。
【符号の説明】
【００７５】
１００ クライアントコンピュータ
１１０ サーチエンジンサーバ
１２０ 文書インデックス
【技術分野】
【０００１】
本出願は、２００３年３月２１日に出願した代理人整理番号１０１３０−０４４−８８８の名称が「対話形サーチクエリー改良のためのシステム及び方法」の米国特許出願番号第６０／４５６，９０５号に対する優先権を主張し、その全体が引用により本明細書に組み込まれる。本発明は、データベース内の文書、或いはインターネット又はイントラネットに結合されたサーバ上に格納された文書を探し出すためのサーチエンジンなどのサーチエンジン分野に関し、詳細には、本発明は、ユーザにとって関心のある文書を探し出すためにそのサーチクエリーを改良する際にサーチエンジンのユーザを支援するためのシステム及び方法に関する。
【背景技術】
【０００２】
ユーザの情報のニーズを伝え、該ニーズが目標文書の語彙内で表現される方法と一致する検索式を作ることは、テキストサーチエンジンのユーザにとって困難な認知タスクとして長い間認識されてきた。サーチエンジンユーザの大多数は、１つ又は２つの語だけのクエリーを用いて文書のサーチを始め、次いで、サーチエンジンによって得られた最初の１０位の結果の中にユーザが求める文書又は複数の文書が見つからないと失望する。少なくとも幾つかのサーチでは、結果をランク付けする方法を改善することによってユーザの満足度を向上させることができるが、極めて広範なサーチクエリーでは、多くの様々なサーチエンジンユーザのより具体的な情報要求を満たすことはできない。ユーザがクエリー式を改良するのを助ける１つの方法は、丁度司書が情報を探している人と対面した会話で行うように、用語の提案を提供することである。しかしながら、システムでは、概念的にクエリーに関係する可能性のある何百の中から、サーチを行っているユーザに最も関係がありそうな用語がどれであるかを「推測」しなければならないので、これを自動的に行うことは全く別のことである。関連する用語を選択するための一般的な方法には、オンラインシソーラス又は以前のログに記録されたクエリーのデータベース（現在のクエリー内の１つ又はそれ以上の語を含む以前のクエリーを見つけるためにサーチすることができる）に照会することが含まれる。このような方法の欠点は、このようにして得られた関連用語が文書自体のコーパス内で使用される内容又は語彙を実際に反映している保証がないことである。この理由により、関連用語をクエリーの実際の結果から動的に収集しようと試みる代替方法が多くの関心を集めている。
【０００３】
改良提案を生成するためにサーチ結果セットを使用する幾つかの従来方法には、用語関連性フィードバック（例えば、「Ｆａｓｔ ａｎｄ Ｅｆｆｅｃｔｉｖｅ Ｑｕｅｒｙ Ｒｅｆｉｎｅｍｅｎｔ」， Ｖｅｌｅｚ他， ＳＩＧＩＲ’９７会報 ｐ６−ｐ１５）、ハイパーインデックス（「Ｑｕｅｒｙ Ｒｅｆｏｒｍｕｌａｔｉｏｎ ｏｎ ｔｈｅ Ｉｎｔｅｒｎｅｔ：Ｅｍｐｉｒｉｃａｌ Ｄａｔａ ａｎｄ ｔｈｅ Ｈｙｐｅｒｉｎｄｅｘ Ｓｅａｒｃｈ Ｅｎｇｉｎｅ」， Ｂｒｕｚａ及びＤｅｎｎｉｓ， ＲＩＡＯ’９７会報 ｐ５００−ｐ５０９）、パラフレーズ（「Ｔｈｅ Ｐａｒａｐｈｒａｓｅ Ｓｅａｒｃｈ Ａｓｓｉｓｔａｎｔ：Ｔｅｒｍｉｎｏｌｏｇｉｃａｌ Ｆｅｅｄｂａｃｋ ｆｏｒ Ｉｔｅｒａｔｉｖｅ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｅｅｋｉｎｇ」， Ａｎｉｃｋ及びＴｉｐｉｒｎｅｎｉ，ＳＩＧＩＲ’９９会報、ｐ１５３−ｐ１５９）、及びクラスタリング（「Ｗｅｂ Ｄｏｃｕｍｅｎｔ Ｃｌｕｓｔｅｒｉｎｇ：Ａ Ｆｅａｓｉｂｉｌｉｔｙ Ｄｅｍｏｎｓｔｒａｔｉｏｎ」， Ｚａｍｉｒ及びＥｔｚｉｏｎｉ， ＳＩＧＩＲ’９８会報 ｐ４６−ｐ５４）がある。ほとんどの関連性フィードバック法は、部分一致サーチエンジン用に設計されており、通常、ユーザによって関連するもの或いは関連しないものとして明示的にタグ付けされた検索文書のサブセット全体にわたる計算から得られた複数の重み付けされた用語を付加することによって、クエリー式を展開することを伴う。ハイパーインデックスは、サーチエンジンによって返された断片の全体にわたり構文解析器を作動させて、クエリー用語を包含する名詞句を抽出する。パラフレーズは、結果として得られたセット文書から名詞句を抽出し、語句拡散に基づいて表示するためのフィードバック用語を選択する。クラスタリング法は、結果のセット断片をクラスタ化し、それぞれのクラスタ内に出現してくる用語から代表的なクエリー用語を得ようとするものである。これらの方法の多くは機能的であるが、生成されたフィードバック用語のランタイム性能又は関連性のいずれかの原因により、巨大なウェブサーチエンジンでも多少不十分である。サーチを向上させるための関連のサーチ用語の識別において、ユーザを支援する効率的な方法に対する当該技術分野における必要性がある。
【０００４】
従来技術の限界をよく理解するためには、「Ｆａｓｔ ａｎｄ Ｅｆｆｅｃｔｉｖｅ Ｑｕｅｒｙ Ｒｅｆｉｎｅｍｅｎｔ」， Ｖｅｌｅｚ他， ＳＩＧＩＲ’９７会報 ｐ６−ｐ１５を綿密に調べることで保証される。Ｖｅｌｅｚ他は、初期クエリーを改良するために、自動的な提案からの用語を初期クエリーに付加するクエリー改良のシステム及び方法を提供する。Ｖｅｌｅｚ他の文献では、一般的なクエリー改良プログラムＤＭをベースに構成されている。Ｖｅｌｅｚ他文献で示されるように、ＤＭは以下のステップを有する：
Ｃ＝文書コーパス
ｑ＝ユーザクエリー
ｒ＝検討するマッチング文書の数
Ｗfcn（Ｓ）＝アルゴリズム特定重み用語セットＳ
とすると、
１．クエリーｑにマッチする文書のセットＤ（ｑ）∈Ｃを計算する。
２．文書にマッチするトップｒのサブセットＤr（ｑ）を選択する。
３．ｄが文書、ｔが用語である場合に、Ｔ（ｑ）＝｛ｔ｜∃ｄ∈Ｄr（ｑ）：ｔ∈ｄ｝であるような文書Ｄr（ｑ）から用語のセットＴ（ｑ）を計算する。
４．最も高い重みＷfcn（Ｓ）でＴ（ｑ）からｎ個の用語のサブセットＳを計算する。
５．Ｓを用語提案のセットとしてユーザに提示する。
Ｖｅｌｅｚ他文献で示されるように、この方法は、高コストのランタイム技法であるので満足できるものではない。言い換えると、文書データベース（コーパス）が大きい場合において、ＤＭを使用して用語提案のセットＳを計算するために不満足な時間量を取ることになる。
【０００５】
Ｖｅｌｅｚ他は、ＤＭによって動的に実行される作業のかなりの量を事前計算することによってＤＭの速度を向上させようとしている。この事前計算段階では、Ｖｅｌｅｚ他は、コーパスの各単語の用語ｔを、単一の用語クエリーｔを所与としてＤＭアルゴリズムが提案する用語のそれぞれのセットｍにマップするデータ構造を作成する。次に、ランタイムにおいて、ユーザから任意のクエリーが受信される。クエリーは通常、用語のセットを含む。クエリーに応答して、Ｖｅｌｅｚ他は、クエリーの用語の各々に対応する用語のそれぞれのセットｍを収集し、これらのセットの各々を単一のセットにマージし、次いで、これが改良されたサーチのための提案としてユーザに戻される。例えば、ユーザがクエリー「スペースシャトル」を入力する場合を考える。この事例では、Ｖｅｌｅｚ他は、語「スペース」に対して事前計算されている用語のセットｍと、語「シャトル」に対して事前計算されている用語のセットｍとを取得することができ、これらを一緒にマージしてクエリー「スペースシャトル」に対して提案される用語のセットを得るようにする。
【０００６】
この方法は、オフラインで用語の関連性のサブセットを事前計算することによってランタイム性能を向上させるが、Ｖｅｌｅｚ他の方法には欠点がある。第１に、文脈の問題がある。Ｖｅｌｅｚ他の方法は、用語ｔがそれ自体で或いは複数用語クエリーの一部として現れるかどうかに関わらず、所与の用語ｔに関連する用語のセットｍが同じであるという仮定に依存する。しかしながら、この仮定は常に真であるとは限らない。複数用語句内に現れる用語は、ある事例においては、それ自体が現れている用語に対して完全に異なる意味を表すことがある。Ｖｅｌｅｚ他でのベースとなる仮定により、この方法は幾つかの事例では不適切なサーチ用語提案を潜在的にもたらす可能性があり、或いは、クエリー全体の文脈内でより関連性があるはずの他の提案を見逃す可能性がある。第２に、コーパス（文書データベース）が変わると、Ｖｅｌｅｚ他の方法は、用語の各セットｍが、場合によってはコーパスに最近加えられたファイルを含むコーパスの複数のファイルのコンテンツに依存するので、コーパスの用語ｔにそれぞれ関連する用語のセットｍを再計算することが必要となる。
【０００７】
Ｘｕ及びＣｒｏｆｔ，ＳＩＧＩＲ’９７、ｐ４−ｐ１１は、幾つかの概念（サーチ用語）を含むことができるサーチクエリーが受け取られる前に、所与の概念に関係する用語のセットが事前計算される別の方法を説明している。Ｖｅｌｅｚ他の方法と同様に、Ｘｕ及びＣｒｏｆｔの方法は、コーパスが時間につれて変化するときに概念に関連する用語の広範な再計算を必要とする、静的クロス文書データ構造及び統計の構成に依存する。従って、Ｘｕ及びＣｒｏｆｔの計算要求は、極めて大きな動的文書データベースにとっては不満足なものである。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】米国特許出願番号第６０／４５６，９０５号公報
【非特許文献】
【０００９】
【非特許文献１】「Ｆａｓｔ ａｎｄ Ｅｆｆｅｃｔｉｖｅ Ｑｕｅｒｙ Ｒｅｆｉｎｅｍｅｎｔ」， Ｖｅｌｅｚ他， ＳＩＧＩＲ’９７会報 ｐ６−ｐ１５
【非特許文献２】「Ｑｕｅｒｙ Ｒｅｆｏｒｍｕｌａｔｉｏｎ ｏｎ ｔｈｅ Ｉｎｔｅｒｎｅｔ：Ｅｍｐｉｒｉｃａｌ Ｄａｔａ ａｎｄ ｔｈｅ Ｈｙｐｅｒｉｎｄｅｘ Ｓｅａｒｃｈ Ｅｎｇｉｎｅ」， Ｂｒｕｚａ及びＤｅｎｎｉｓ， ＲＩＡＯ’９７会報 ｐ５００−ｐ５０９
【非特許文献３】「Ｔｈｅ Ｐａｒａｐｈｒａｓｅ Ｓｅａｒｃｈ Ａｓｓｉｓｔａｎｔ：Ｔｅｒｍｉｎｏｌｏｇｉｃａｌ Ｆｅｅｄｂａｃｋ ｆｏｒ Ｉｔｅｒａｔｉｖｅ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｅｅｋｉｎｇ」， Ａｎｉｃｋ及びＴｉｐｉｒｎｅｎｉ，ＳＩＧＩＲ’９９会報、ｐ１５３−ｐ１５９
【非特許文献４】「Ｗｅｂ Ｄｏｃｕｍｅｎｔ Ｃｌｕｓｔｅｒｉｎｇ：Ａ Ｆｅａｓｉｂｉｌｉｔｙ Ｄｅｍｏｎｓｔｒａｔｉｏｎ」， Ｚａｍｉｒ及びＥｔｚｉｏｎｉ， ＳＩＧＩＲ’９８会報 ｐ４６−ｐ５４
【発明の概要】
【００１０】
上記従来技術から、ユーザの好みにより近いサーチ結果をもたらすために、サーチクエリーをより絞り込んで定義されたクエリーに改良する際にユーザへの支援を提供することが望まれる。
本発明は、文書インデックスから文書を検索するよう設計されたサーチクエリーを改良するための改善された方法を提供する。本発明は、コーパスが更新される度に再計算しなければならないクロス文書データ構造又はグローバル統計に依存しないので有利である。更に本発明は、句のミックス、単語用語、及び特殊化（クエリー用語を含む句）を含む関連のある提案の短いリストを作成するために、周知の方法に比べてランタイムでフェッチする必要のある結果が少ないので、クエリー時（ランタイム）にＩ／Ｏ資源を必要とすることが著しく少ない。本発明において、文書インデックスでの各文書は、例えば文書インデックスの作成中にクエリーに先立つある時間に処理される。この処理では、文書インデックスでの各文書は、文書がその文書に対するランク付けされた候補用語のセット内に含むのに何らかの適切な用語を含むかどうかを判定するために調べられる。文書がこのような用語を含む場合、文書への文書インデックスの入力は、文書と関連付けられた用語のセットを含むよう構成される。この用語のセットは、ランク付けされた候補用語のセットと呼ばれる。
【００１１】
クエリーが受け取られると、文書の初期グループが文書インデックスから検索される。文書の初期グループは、クエリーに対する関連性によってランク付けされる。文書の「初期グループ」は、クエリーに対して潜在的に関係があるものとして識別された文書のフルセットのうちのセブセットとすることができる。１つの実施形態において、初期グループでの文書の数は、クエリーに潜在的に関係があるものとして識別された全文書より少なく、パラメータ値は通常２０と２００の間（例えば５０）である。次に、重み付け関数は、ランク付けされた文書の初期グループでの文書に関連するランク付けされた候補用語のいずれかのセットに現れる各候補用語に加えられる。トップスコアリング候補用語は、クエリーに応答してランク付けされた文書の初期グループと共に提示される。提示された候補用語の１つをユーザが選択することにより、オリジナルのサーチクエリーへ用語を付加することになる。
【００１２】
本発明の１つの態様は、受信クエリーを改良する方法を提供する。受信クエリーは、受信クエリーに対応するランク付けされた文書の初期グループを作成するように処理される。ランク付けされた文書の初期グループでの文書の全部又は一部の各文書は、ランク付けされた候補用語のそれぞれのセットに関連付けられる。候補用語の種々のそれぞれのセットにおける各候補用語は、ランク付けされた文書の初期グループの文書内に組み込まれる。各候補用語は、語又は句とすることができる。更に、好ましい実施形態において、候補用語の種々のそれぞれのセットは受信クエリーを処理する前の時点で構成される。この方法は、続いて、ランク付けされた候補用語の種々のそれぞれのセットの１つまたはそれ以上内にある候補用語のサブセットを選択する。選択関数は、この候補用語のサブセットを選択するのに使用される。次に受信クエリーに応答して、ランク付けされた文書の初期グループと候補用語のサブセットとが提示される。幾つかの実施形態において、処理、選択、及び提示が、オリジナルの受信クエリーと候補用語のサブセットからの候補用語とを含む変更されたクエリーを使用して繰り返される。
【００１３】
幾つかの実施形態において、文書と関連付けられた候補用語のセットは、文書の用語を候補用語のマスターリストと比較することによって構成される。用語が候補用語のマスターリストに存在する場合、その用語は、候補用語として文書と関連付けられた候補用語のセットに加えられる。幾つかの実施形態において、候補用語のマスターリストは、１０，０００，０００より多い候補用語を含む。この比較は、文書内の用語の最大数が検討されるか或いは固有の用語の閾値数が検討されるまで繰り返される。次に重み付け及び／又は選択関数が、ランク付けされた候補用語のセットを作成するために候補用語のセットに加えられる。一般的に、この重み付け及び／又は選択関数は、候補用語をランク付けし、次いで、高くランク付けされた用語だけが保持されるカットオフを適用する。幾つかの実施形態において、候補用語のマスターリストは、特定の言語（例えば、英語、スペイン語、フランス語、ドイツ語、ポルトガル語、イタリア語、ロシア語、中国語、又は日本語）について最適化される。幾つかの実施形態において、ランク付けされた文書の初期グループにおける文書の全部又は一部の各文書は、候補用語のマスターリストが最適化された言語と同じ言語である。
【００１４】
幾つかの実施形態において、文書インデックスの各文書は、クエリープロセスの前（例えば初期文書インデックス中）の時点で分類される。幾つかの実施形態において、２つの可能なクラス、すなわち第１の家族向けクラスと第２の非家族向けクラスがある。文書の分類の指定は、文書インデックスに含まれる。
【００１５】
幾つかの実施形態において、実際には、ランク付けされた候補用語のセットのより複雑な用語のサブセット（サブストリング）であるランク付けされた候補用語のセット内の単語候補用語が廃棄される。更に、より複雑な用語は、ランク付けされた候補用語のセットに関連する文書の全部或いは上位部分において単純な用語が現れた事例の回数に対してクレジットが与えられる。この廃棄及びクレジットは、ランク付けされた候補用語のセットにおけるより複雑な候補用語のサブセットである単語候補用語が無くなるまで繰り返される。更に、同じ手順をより複雑な用語のサブセットである複数語候補用語に適用できる。
【００１６】
幾つかの実施形態において、ランク付けされた候補用語のセット内の第２用語の正字の異形又は屈折異形であるランク付けされた候補用語のセットにおける候補用語が廃棄される。更に、第２用語は、ランク付けされた候補用語のセットに関連する文書の全部又は上位部分において正字の異形又は屈折異形用語が現れた事例の回数に対してクレジットが与えられる。この廃棄及びクレジットは、ランク付けされた候補用語のセット内の別の用語の正字の異形又は屈折異形である用語が無くなるまで繰り返される。幾つかの事例では、第２用語は、両方の（例えば複数の）正字の異形又は屈折異形を含む結合用語として候補セット内に上書きされ、関連する文書の全部或いは上位部分に最も現れた異形が結合用語に最初に現れる。幾つかの実施形態において、結合用語が提示された候補用語のサブセットに含めるために選択される場合、結合用語の第１部分のみがユーザに提示される。
【００１７】
本発明の幾つかの実施形態は、クエリーに応答して提示されることになる候補用語のサブセットを選択するのに使用される種々の選択関数を提供する。幾つかの実施形態において、この選択関数は、ランク付けされた文書の初期グループ内のトップランクの文書と関連付けられた候補用語のセットにおいて見つけられた情報を利用する。この情報は、ランキングの２つの形式を含む。最初に、文書がランク付けされる。次に、ランク付けされた文書の初期グループ内の文書と関連するランク付けされた候補用語の各セット内の各候補用語がランク付けされる。
【００１８】
１つの実施形態において、選択関数は、（ｉ）ランク付けされた文書の初期グループ内のトップランクの文書に関連するランク付けされた候補用語の各それぞれのセット内の各候補用語に対して重み付け関数を適用することを含む。本明細書で使用されるランク付けされた文書の初期グループの各トップランクの文書は、ある閾値ランキングよりも数値的に小さいランク（例えば５０、すなわちトップランクの文書がクエリーに戻されたランク付けされた文書の初期グループのトップ５０の文書内にある）を有する文書である。例えば、ランク付けされた文書の初期グループが１００の文書を含み、閾値ランキングが５０である場合を考える。このとき、最初の５０の文書はトップランクの文書とみなすことになる。最も高い重みを受け取っているこれらの候補用語は、クエリー結果と共に提示される候補用語のサブセット内に含まれる。幾つかの実施形態において、重み付け関数によって候補用語に加えられる重みは、候補用語が現れるトップランクの文書と関連付けられた候補用語のセットの数に応じて、ランク付けされた候補用語の各こうしたセット内の候補用語の平均位置に応じて、受信クエリーの用語が候補用語内に存在するかどうかによって、候補用語内の文字数によって、或いは候補用語の関連するセット内に用語を含むトップランクの文書の平均ランク位置によって決定される。幾つかの実施形態において、重み付け関数によって候補用語に加えられる重みは、ＴｅｒｍＣｏｕｎｔ、ＴｅｒｍＰｏｓｉｔｉｏｎ、ＲｅｓｕｌｔＰｏｓｉｔｉｏｎ、ＴｅｒｍＬｅｎｇｔｈ、及びＱｕｅｒｙＩｎｃｌｕｓｉｏｎのいずれかの組合せ又はいずれかの重み付けサブセットに応じて決定され、ここで、
ＴｅｒｍＣｏｕｎｔは、（ｉ）候補用語を含み、且つ（ｉｉ）トップランクの文書にそれぞれ関連するランク付けされた候補用語のセットの数であり、
ＴｅｒｍＰｏｓｉｔｉｏｎは、（ｉ）候補用語を含み、且つ（ｉｉ）トップランクの文書にそれぞれ関連するランク付けされた候補用語のこれらのセットにおける候補用語の位置の関数（例えば平均）であり、
ＲｅｓｕｌｔＰｏｓｉｔｉｏｎは、候補用語を含むランク付けされた候補用語のセットに関連付けられるこれらのトップランクの文書のランクの関数（例えば平均）であり、
ＴｅｒｍＬｅｎｇｔｈは、候補用語の文字の数（候補用語の複雑性）であり、
ＱｕｅｒｙＩｎｃｌｕｓｉｏｎは、受信クエリーの用語が候補用語内に存在するかどうかを示す値である。
幾つかの実施形態において、重み付け関数によって候補用語に加えられる重みは、次式に応じて決定される。
ＴｅｒｍＣｏｕｎｔ＋ＴｅｒｍＰｏｓｉｔｉｏｎ＋ＲｅｓｕｌｔＰｏｓｉｔｉｏｎ＋ＴｅｒｍＬｅｎｇｔｈ＋ＱｕｅｒｙＩｎｃｌｕｓｉｏｎ
【００１９】
幾つかの実施形態において、ＴｅｒｍＣｏｕｎｔ、ＴｅｒｍＰｏｓｉｔｉｏｎ、ＲｅｓｕｌｔＰｏｓｉｔｉｏｎ、ＴｅｒｍＬｅｎｇｔｈ、及びＱｕｅｒｙＩｎｃｌｕｓｉｏｎは各々、別々に重み付けされる。幾つかの実施形態において、重み付け関数によって候補用語に加えられる重みは、次式に応じて決定される。
（ＴｅｒｍＣｏｕｎｔ*ｗ1）＋
（ＴｅｒｍＰｏｓｉｔｉｏｎ*（ｗ2＋（ＲｅｆｉｎｅｍｅｎｔＤｅｐｔｈ*ｗ2´）））＋
（ＲｅｓｕｌｔＰｏｓｉｔｉｏｎ*ｗ3）＋
（ＴｅｒｍＬｅｎｇｔｈ*（ｗ4＋（ＲｅｆｉｎｅｍｅｎｔＤｅｐｔｈ*ｗ4´）））＋
（ＱｕｅｒｙＩｎｃｌｕｓｉｏｎ*（ｗ5＋（ＲｅｆｉｎｅｍｅｎｔＤｅｐｔｈ*ｗ5´）））
ここで、ｗ1、ｗ2、ｗ3、ｗ4、ｗ5、ｗ2´、ｗ4´、及びｗ5´は別々の重みであり、ＲｅｆｉｎｅｍｅｎｔＤｅｐｔｈは受信クエリーに対して処理が行われた回数である。
【００２０】
幾つかの実施形態において、選択関数は、ランク付けされた文書の初期グループ内の各文書について文書の分類を決定する段階を含む。次いで、文書のセットの閾値パーセンテージが第１分類（例えば、家族向けカテゴリー）に属する場合には、第２分類（例えば、非家族向けカテゴリー）のメンバーである文書に属するランク付けされた候補用語の全セットは、候補用語のサブセットを形成するのには使用されない。
【００２１】
本発明の別の態様は、コンピュータシステムと共に使用するコンピュータプログラム製品を提供する。コンピュータプログラム製品は、コンピュータ可読記憶媒体とこれに組み込まれたコンピュータプログラム機構とを含む。コンピュータプログラム機構は、受信クエリーを改良するためのクエリー改良提案エンジンを含む。このエンジンは、受信クエリーに対応するランク付けされた文書の初期グループを作成するように受信クエリーを処理する命令を含む。ランク付けされた文書の初期グループ内の文書の全部又は一部の各文書は、ランク付けされた候補用語のそれぞれのセットの各候補用語が文書内に組み込まれるように、ランク付けされた候補用語のそれぞれのセットに関連付けられる。ランク付けされた候補用語の各それぞれのセットは、受信クエリーの処理の前の時点で識別される。エンジンは更に、選択関数に従って、候補用語のそれぞれのセットの１つ又はそれ以上内にある候補用語のサブセットを選択する命令を含む。更に、エンジンは、受信クエリーに応答して、ランク付けされた文書の初期グループと候補用語のサブセットとを提示する命令を含む。
【００２２】
本発明の更に別の態様は、複数のユニフォームリソースロケータ（ＵＲＬ）から構成される文書インデックスデータ構造を提供する。各ＵＲＬはそれぞれの文書を指定する。複数のＵＲＬによって指定されたそれぞれの文書の全部又は一部の各文書は、ランク付けされた候補用語のそれぞれのセットに関連付けられる。ランク付けされた候補用語のそれぞれのセットの各候補用語は、ランク付けされた候補用語のセットに関連する文書に組み込まれる候補用語を含む。更に、これらの候補用語は、重み付け関数によってランク付けされる。幾つかの実施形態において、ランク付けされた候補用語のそれぞれのセットは、
（Ａ）ランク付けされた候補用語のそれぞれのセットに関連する文書内の用語を候補用語のマスターリストと比較し、ここで、その用語が候補用語のマスターリスト内に存在する場合には、その用語をランク付けされた候補用語のそれぞれのセットに候補用語として加え、
（Ｂ）文書内の用語の最大数が検討されるまで比較を繰り返し、
（Ｃ）重み付け関数に従って候補用語をランク付けし、これによりランク付けされた候補用語を形成する、
ことによって生成される。
【図面の簡単な説明】
【００２３】
【図１】サーチエンジンにクエリーを依頼しているクライアントコンピュータを示す図である。
【図２】本発明の実施形態に従って作り出される、クエリー改良提案を含むサーチ結果ページを示す図である。
【図３】サーチエンジンサーバのブロック図である。
【図４】サーチエンジンインデックスのブロック図である。
【図５】文書インデックス方法のフローチャートである。
【図６】ユーザによって提出されたクエリーを処理するための手順のフローチャートである。
【発明を実施するための形態】
【００２４】
本発明の上述の特徴及び利点、並びに本発明の付加的な特徴及び利点は、図面を併用しながら本発明の好ましい実施形態の詳細な説明の結果として以下でより明確に理解されるであろう。
同じ参照符号は、幾つかの図面全体を通して対応する要素を示す。
【００２５】
典型的な実施形態において、本発明は、効率的な方法でユーザのクエリーに潜在的により高度に関連し、且つ目標文書の語彙を反映するクエリー改良提案（候補用語のサブセット）の小さなセット（１０−２０）を作成する。
【００２６】
図１に示されるように、サーチクエリーは、クライアントコンピュータ１００によってサーチエンジンサーバ１１０に提出される。サーチエンジンサーバ１１０は、サーチクエリーを受信すると、該サーチクエリーに関連する文書インデックス１２０において文書を識別する。更に、サーチエンジンサーバ１１０は、例えば他のランキング要因のうちでサーチクエリーに対するこれらの関連性によって関連する文書をランク付けする。次いで、このランク付けされた文書のグループの記述（サーチ結果）は、ランク付けされた文書のグループとしてクライアントコンピュータ１００に戻される。本発明においては、候補用語のサブセットの形式（サーチ改良提案）での付加的な情報は、ランク付けされた文書の初期グループと共にクライアントコンピュータに戻される。
【００２７】
サーバ１１０が候補用語のサブセットを作成する方法の詳細に移る前に、本発明の利点をより良く理解できるように、サーチエンジンサーバ１１０の実施形態によって戻されたサーチ結果及びサーチ改良提案のスクリーンショットが図２に提供されている。図２で、ユーザは初期クエリー（受信クエリー）１３２を提供する。検索ボタン１３４が押されると、クエリー１３２がクライアントコンピュータ１００からサーチエンジンサーバ１１０に送られる。クエリー１３２が受信されると、サーチエンジンサーバ１１０は、受信クエリー１３２を処理し、サーチ結果及びサーチ改良提案をランク付けされた文書の初期グループ及び候補用語のサブセットの形式でクライアントコンピュータ１００に送り返す。候補用語のサブセットは、インターフェース１８０のパネル１４０に表示される。具体的には、候補用語のサブセットの各用語１３６が、タグ１３８と共に領域１４０内に表示される。同時に、サーチ結果のリスティング（ランク付けされた文書の初期リストのトップランクの文書）がパネル１４２に表示される。本発明のシステム及び方法は、オリジナルのクエリー１３２を絞り込み、変更し、又は改善することができる用語１３６を識別することに関する。ユーザがタグ１３８を押すと、タグ１３８に対応する用語１３６が初期クエリー１３２に付加され、新しいクエリーに関してプロセス全体が繰り返される。ユーザが別のタグ１３９を押すと、タグ１３８に対応する用語１３６は初期クエリー１３２を更新し、サーチエンジンサーバは、当該用語１３６を新しいクエリーとして処理する。図示されていない実施形態において、各用語１３６に対応する１つ又はそれ以上の付加的なタグは、パネル１４０に追加することができる。１つの実施例では、対応する用語１３６を例外リストに付加するのに使用されるタグが存在する。例えば、オリジナルクエリーを「Ａ」とし、ユーザが用語「Ｂ」の排他タグを押すと、新しいクエリーが「Ａ」になり「Ｂ」ではなくなる。パネル１４０に表示された用語のサブセットに加えて、ランク付けされた文書の初期グループがパネル１４０に表示される。コンピュータ１００とサーバ１１０との間の帯域幅を節約するために、典型的な実施形態では、ランク付けされた文書の初期グループは通常、ランク付けされた文書の初期グループの各文書の標識を含み、ユーザが初期のランク付けされた文書における該文書の各々の性質を判断できるようにする。このような標識（ｉｎｄｉｃｉａ）は更に、本明細書ではランク付けされた文書の初期グループと呼ばれる。
【００２８】
本発明のシステム及び方法の概要が開示されてきた。この概要から、本発明の多くの利点及び特徴が明らかにされる。本発明の新しいアルゴリズムは、初期クエリーの改良に使用することができる提案された用語１３６のリストをユーザに自動的に提供する。例えば図２において、初期クエリー１３２は「スペースシャトル」である。この初期クエリーに応答して、本発明の実施形態は、「チャレンジャー大事故」のような用語１３６を含む候補用語のサブセットを提供する。初期クエリーへの用語「チャレンジャー大事故」の追加、或いは初期クエリーの用語「チャレンジャー大事故」への置換は、ユーザの関心事に恐らくはより近接して一致するクエリーをユーザに提供する。候補用語の新しいサブセットを使用することによって、ユーザは、ランク付けされた文書の初期グループ内の文書（又はその標識（ｉｎｄｉｃｉａ））を分析することなく改善されたクエリーを構築することができる。従って、本発明を使用すると、多すぎる（又は少なすぎる）結果、或いはユーザの情報の必要性に直接関係しない結果を初期クエリーが生成する理由を識別する必要性がもはやなくなる。
【００２９】
本発明の概要及び利点を提示してきたので、次に本発明のシステム及び方法の更に詳細な説明を開示する。この目的のために、図３は、本発明の１つの実施形態によるサーチエンジンサーバ１１０を示している。好ましい実施形態において、サーチエンジンサーバ１１０は、図３に概略的に示すように１つ又はそれ以上のコンピュータシステム３００を使用して実施される。大量のクエリーを処理するよう設計されたサーチエンジンは、図３に示されるものよりも更に複雑なコンピュータアーキテクチャを使用することができることは当業者には理解されるであろう。例えば、サーバのフロントエンドセットを用いて、実際にクエリーを処理するバックエンドサーバのセット間でクエリーを受信及び分散することができる。このようなシステムでは、図３に示されたシステム３００は、バックエンドサーバの１つとなる。
【００３０】
コンピュータシステム３００は通常、ユーザインターフェース３０４（ディスプレイ３０６及びキーボード３０８を含む）、１つ又はそれ以上の処理ユニット（ＣＰＵ）３０２、ネットワーク又は他の通信インターフェース３１０、メモリ３１４、及びこれらの構成要素を相互接続するための１つ又はそれ以上の通信バス３１２を有することになる。メモリ３１４は、高速ランダムアクセスメモリを含むことができ、また、１つ又はそれ以上の磁気ディスク記憶装置（図示せず）などの不揮発性メモリを含むことができる。メモリ３１４は、（１つ又は複数の）中央処理ユニット３０２から遠隔に設置される大容量記憶装置を含むことができる。メモリ３１４は、
・ 種々の基本システムサービスを扱い、且つハードウェア従属タスクを実行するための手順を含むオペレーティングシステム３１６と、
・ インターネット、他のワイドエリアネットワーク、ローカルエリアネットワーク（例えば、ローカル無線ネットワークはクライアントコンピュータ１００をコンピュータ３００に接続できる）、メトロポリタンエリアネットワークなどの１つ又はそれ以上の通信ネットワークを介して種々のクライアントコンピュータ１００（図１）及び場合によっては他のサーバ又はコンピュータにシステム３００を接続するのに使用されるネットワーク通信モジュール３１８と、
・ クライアントコンピュータ１００からクエリーを受信するためのクエリーハンドラ３２０と、
・ クエリーに関係のある文書の文書インデックス３５２をサーチして、クエリーに関係のあるランク付けされた文書の初期グループを形成するためのサーチエンジン３２２と、
・ 本発明の多くの態様を実施するためのクエリー改良提案エンジン３２４と、
を記憶することが好ましい。
【００３１】
クエリー改良提案エンジン３２４は、実行可能な手順、サブモジュール、テーブル、及び他のデータ構造を含むことができる。１つの実施形態において、改良提案エンジン３２４は、
・ ランク付けされた文書の初期グループと共に提示するための候補用語のサブセットを識別するための選択関数３２６と、
・ 提示のために候補用語のサブセットとランク付けされた文書の初期グループとをフォーマッティングするための結果フォーマッティングモジュール３２８と、
を含む。
【００３２】
本発明の方法は、クエリー１３２が文書インデクサ３４４の動作でクエリーハンドラ３２０によって受信される前に始まる。文書インデクサ３４４は、ウェブクローリング及びインデキシング技術を使用して文書インデックス３５２を構築する。しかしながら、この従来の機能に加えて、文書インデクサ３４４は、文書インデックス３５２の文書を更に処理する新しいプログラムモジュールを含む。例えば、文書インデクサ３４４は、「候補用語セットのコンストラクタ」３４６を含む。好ましい実施形態において、コンストラクタ３４６は、文書インデックス３５２の各文書を調べる。他の実施形態において、予め定められた基準を満たしている文書（例えば、予め定められた言語のセットのうちの１つのテキストが含まれている文書）だけがコンストラクタ３４６によって調べられる。
【００３３】
調べられる各文書について、コンストラクタ３４６は、文書に埋め込まれた何らかの候補用語を該文書が含むかどうかを判定する。このタスクをコンストラクタ３４６が達成することができる多くの異なる方法が存在し、全てのこのような方法は本発明の範囲内に含まれる。１つの実施形態において、タスクは、文書からの用語を候補用語のマスターリスト３４２に一致させることによって達成される。候補用語のマスターリスト３４２は、全ての可能性のある候補用語を含む。幾つかの実施形態において、リスト３４２は、有効な候補用語のリストを備えるＵｎｉｘスタイルのテキストファイルである。リスト３４２の代表的なフォーマットは、１行につき１つの候補用語があり、リスト３４２固有の各候補用語は、全てのコンマ、タブ、エンドライン、及び＠記号が省略されてＵＴＦ−８で符号化される。幾つかの実施形態において、マスターリストは、名詞及び名詞句（クエリー用語として有用となる可能性が最も高い用語の種類）に限定され、制限されたクエリー改良値のどのような名詞句も明示的に取り除かれる。
【００３４】
典型的な実施形態では、文書インデックス３５２の各文書の第１部分のみが候補用語について調べられる。例えば、幾つかの事例では、文書インデックス３５２の各文書の最初の１００，０００バイトのみがコンストラクタ３４６によって調べられる。幾つかの実施形態において、コンストラクタ３４６は、文書の用語の最大数（例えば、１００、１０００、５０００など）が検討されるまで文書インデックス３５２の文書を調べる。幾つかの実施形態において、文書の候補用語のサーチは、文書の固有の用語の閾値数がマスターリスト３４２（例えば１００用語）内で発生したことが判明した時点で終了する。
【００３５】
本発明の幾つかの実施形態は、１つより多い候補用語のマスターリスト３４２を提供する。各マスターリスト３４２は、種々の言語について最適化される。例えば、第１リスト３４２は英語について最適化され、第２リスト３４２はスペイン語について最適化される。従って、英語リスト３４２は英語の文書において見られる情報用語を含むことになり、スペイン語リスト３４２はスペイン語の文書において見られる情報用語を含むことになる。同様に、本発明の幾つかの実施形態は、フランス語、ドイツ語、ポルトガル語、イタリア語、ロシア語、中国語、又は日本語について最適化されたリストを含む。本発明の幾つかの実施形態において、リスト３４２は、カテゴリーの他のタイプについて最適化される。例えば、幾つかの実施形態において、リスト３４２は、科学用語、ファッション用語、光学用語、又は旅行用語を含めるように最適化される。しかしながら、好ましい実施形態において、各マスターリスト３４２は、情報用語を可能な限り含む。実際に、マスターリスト３４２は、１０，０００，０００より多い用語を含むことができ、通常は１，０００，０００よりかなり多い用語を含む。これらの用語の各々は、語又は句とすることができる。理解しやすいように、代表的な句は「チャレンジャー大事故」である。
【００３６】
文書で使用される主たる言語を決定する方法は、当該技術分野で公知である。従って、本発明の幾つかの実施形態においては、コンストラクタ３４６は、（ｉ）調べられている文書の言語を決定し、及び（ｉｉ）文書と同じ言語について最適化されたマスターリスト３４２を使用するためにこうした方法を用いる。
【００３７】
マスターリスト３４２にある１つ又はそれ以上の候補用語がインデックス３５２の文書の上位部分（例えば、最初の１００キロバイト）に組み込まれている場合、コンストラクタ３４６による文書の調査の最終結果は、これらの用語の識別である。こうした用語がコンストラクタ３４６によって識別されると、これらはランク付けされた形式で文書と関連付けられたデータ構造に付加される。このデータ構造は、候補用語のセットと呼ばれる。インデックス３５２がコンストラクタ３４６によって調べられた後、その上位部分に候補用語を組み込んだインデックス３５２内の各文書は、こうした用語を含む候補用語のそれぞれのセットに関連付けられることになる。従って、例えば、インデックス３５２において候補用語を含む２つの文書ＡとＢがある場合、候補用語の第１セットが文書Ａに関連付けられ、候補用語の第２セットは文書Ｂに関連付けられる。候補用語の第１セットは、文書Ａの上位部分に組み込まれた各候補用語を含むことになり、ランク付けされた候補用語の第２セットは、文書Ｂの上位部分に組み込まれた各用語を含むことになる。実際には、候補用語の各セットは、以下に更に詳細に開示されるように内部的にランク付けされて、候補用語のそれぞれのランク付けされたセットを形成するようにする。
【００３８】
図４は、コンストラクタ３４６による文書インデックス３５２での文書４０２の調査が文書インデックス３５２の修正をどのように生じさせるかを示している。コストラクター３４６がインデックス３５２の文書を調べる前に、インデックス３５２の各文書４０２は、文書４０２のユニフォームリソースロケーション（ＵＲＬ）４０６並びに特徴値のセット４０８を含む。特徴値４０８は、文書に関連付けられたメタデータを含み、更に、ランキング文書がクエリーに潜在的に関係するものとして識別されたときにサーチエンジンを支援する値を含む。特徴値は、文書のファイルフォーマット、文書の長さ、文書への周知のインバウンドリンク（他の文書からの）の数、文書のタイトル（例えば、クエリーに応答するものとして文書が選択された時間を表示するための）などの指標を含むことができる。文書４０２がコンストラクタ３４６（図３）によって調べられた後で、候補用語のセット４１０は文書４０２に関連付けられる。
【００３９】
本発明の幾つかの実施形態において、文書内の用語をリスト３４２の候補用語と一致させる方法は、その用語をリスト３４２の可能性のある最も複雑な候補用語と確実に一致させる方式で実行される。例えば、ＡとＢを各語とするときに用語「ＡＢ」がインデックス３５２の文書に組み込まれる場合を考える。更に、リスト３４２は、「Ａ」、「Ｂ」、及び「ＡＢ」を含むと仮定する。これが起こる場合、文書の用語「ＡＢ」は、リスト３４２の「ＡＢ」と一致することになり、「Ａ」又は「Ｂ」とは一致しない。このようなマッチングを行うことができる幾つかの方法が存在し、全てのこのようなマッチング手法は本発明の範囲内にある。１つのこのようなマッチング方法は、以下の論理を有する「左−右貪欲アルゴリズム」を使用する：
調べられる文書の形式「ＡＢＣＤ．．．」の各文について：
Ａはリスト３４２の候補用語の接頭辞であるか？
○はい：「ＡＢ」はリスト３４２の候補用語の接頭辞であるか？
■はい：「ＡＢＣ」はリスト３４２の候補用語の接頭辞であるか？
●はい−＞同じ方式で文全体のドリリングを続ける
●いいえ：文書と関連付けられた候補用語のセット４１０に「ＡＢ」を加え、Ｃに移り、「ＣＤＥＦ．．．」を検討する
■いいえ：文書と関連付けられた候補用語のセット４１０に「Ａ」を加え、Ｂに移り、「ＢＣＤＥ．．．」を検討する
○いいえ：Ｂに移り、「ＢＣＤＥ．．．」の検討を始める
このようなアルゴリズムは、「文」が行のような文書のある任意の量であるか、或いは２つの句の境界又は他の区切り点の間の文書の部分であり、及び「ＡＢＣＤ．．．」が用語の各語である場合、リスト３４２の最も複雑な用語を文書の用語に確実に一致させる。関連する方法では、コンストラクタ３４６は、第１候補用語が候補用語のセットにおける第２候補用語のサブセットである場合、候補用語のセット４１０の第１候補用語を廃棄する。
【００４０】
本発明の幾つかの実施形態において、、セット４１０に関連付けられた文書の全部又は上位部分（例えば最初の１００キロバイト）においてランク付けされた用語のセット４１０の各候補用語が現れる回数が追跡される。例えば、セット４１０の候補用語「Ａ」がセット４１０と関連付けられた文書の上位部分に１２回現れる場合には、用語「Ａ」が文書に１２回現れるという指示が示され、どの候補用語がランク付けされた候補用語の最終セットに残ることになるかを判定するよう設計された重み付け方式で使用される。
【００４１】
幾つかの実施形態において、関連する文書に用語が現れる回数の表示は、用語が文書の語の第１閾値数内に現れる事例毎に重みが追加される。例えば、第１閾値の値が１５語である場合を考えてみる。更に、この例示的な場合において、候補用語「Ａ」は正確に二度現れる。句「Ａ」の第１の出現は、１５語限界の前であり、「Ａ」の第２の出現は１５語限界の後である。この例示的な場合に使用される重み付け方式において、最初の１５語内に現れている語は、二倍の重みを受け取る。従って、文書と関連付けられる候補用語のセット４０２では、候補用語「Ａ」は、用語が文書の上位部分において（２*１＋１）、すなわち３回出現する指示と共にリストされることになる。最初の閾値のより複雑な形式が可能であることは、当業者であれば理解するであろう。例えば、候補用語カウントに加えられた重みは、文書の候補用語の位置の関数とすることができる。例えば、これは、文書の始めに最大値を有し、且つ文書の最後に最小値を有する線形関数（又は非線形関数、もしくは区分線形関数）とすることができる。代替えとして重みをバスケットに加えることができ、この場合、文書の始め（第１バスケット）に大きな重みがあり、文書の第２部分（第２バスケット）に低い重みがあり、文書の第３部分（第３バスケット）に更に低い重みなどがある。
【００４２】
（ｉ）候補用語の回数の指示が関連する文書に現れ、且つ（ｉｉ）コンストラクタ３４６がランク付けされた候補用語のセット４１０の第１候補用語を廃棄する実施形態では、第１候補用語がランク付けされた候補用語のセットの第２候補用語のサブセットである場合には、第２候補用語は、第１候補用語がコンストラクタ３４６によって文書内で識別された回数でクレジットされる。
【００４３】
コンストラクタ３４６に加えて、インデクサ３４４は冗長フィルタ３４８を含む。フィルタ３４８は、正字の異形又は屈折異形を取り除いて最後に候補用語のセットとなることができるよう設計されている。用語の正字の異形は、用語についての他の正しいスペル（綴り）を有する。用語の屈折異形は、別の接尾辞、又は用語のアクセント形式を有する。幾つかの実施形態において、正字の異形及び／又は屈折異形は、異形リスト３６０に記憶される（図３）。従って、冗長フィルタ３４８の仕事は、候補用語のセット４１０の候補用語のペアが異形リスト３６０に確実に存在しないようにすることである。候補用語のセット４１０の候補用語のペアが異形リスト３６０に存在するときには、ペアに由来する１つの用語は、フィルタ３４８によってセット４１０から廃棄される。幾つかの実施形態において、ペアの第１用語がセット４１０から効率的に廃棄され、ペアの第２用語は保存されることになる。しかしながら、幾つかの実施形態において、第２用語は、廃棄された第１用語と結合されるように修正されることになる。例えば、用語Ａ及びＢが屈折異形又は正字の異形である場合、用語の１つ、すなわちＡは廃棄され、別の用語Ｂが保存される。更に、用語ＢはＡ，Ｂとして上書きされる。この特徴は、クエリー改良提案エンジン３２４のような本発明のより高レベルのモジュールによって使用可能な基礎となる文書についての有用な情報を保存するので有利である。通常、エンジン３２４は、これらのマージされた正字の異形又は屈折異形の候補用語が現れる場合の第１（廃棄されなかった）用語だけを提示することになる。例えば、上書きされた用語Ａ、Ｂの場合、用語「Ａ」だけがパネル１４０に提示された候補用語のサブセットに含まれる。通常、リスト３６０に現れている用語のペアで廃棄された用語は、関連する文書においてあまり頻繁には現れない用語である。幾つかの実施形態において、ある種のノイズワード（例えば、ａ、ｔｈｅ、ｗｈｏ、ｗｈａｔ、ｗｈｅｒｅなど）の有無だけが相違する候補用語は、正字の異形又は屈折異形を含む候補用語が共にフォールドされるのと同じ方式でフォールドされる。同様に、幾つかの実施形態において、候補用語の所与のセットの２つの用語の違いが句読点の有無だけである場合、２つの用語は、正字の異形又は屈折異形を含む候補用語が共にフォールドされるのと同じ方式で共にフォールドされる。幾つかの実施形態において、候補用語のセットの各句は、同じケース（例えば小文字）に変換される。この規則の例外は、６つ又はこれより少ない大文字の単語であるこれらの用語が、こうした用語が頭辞語になる可能性がある理由から小文字には変換されないことである。
【００４４】
（ｉ）候補用語の回数の指示が関連する文書に現れ、（ｉｉ）候補用語のセットの第１候補用語が候補用語のセットの第２候補用語の正字の異形又は屈折異形であるために、候補用語のセットの第１候補用語をフィルタ３４８が廃棄する両方の実施形態において、第２候補用語は、第１候補用語がコンストラクタ３４６によって文書で識別された回数でクレジットされる。言い換えると、２つの候補用語の間の違いが、候補用語の一方が他方の候補用語の対応する語の屈折異形又は正字の異形である単語を含むだけである場合に、候補用語の一方が廃棄される。この実施例は、候補用語「ｔｏｗ ｔｒｕｃｋ」と「ｔｏｗ ｔｒｕｃｋｓ」の場合に起こる。この実施例では、２つの候補用語の間の違いは、第１用語の「ｔｒｕｃｋ」の列挙と第２用語での「ｔｒｕｃｋｓ」の列挙だけである。
【００４５】
文書インデクサ３４４についての多くの詳細が開示されてきた。このステージでは、インデクサ３４４の幾つかの実施形態によって用いられるステップを開示する図５のフロー線図を検証することが有益である。他のインデキシングデューティ（例えば、ウェブクローラによって見出される文書の中の語の従来のインデキシング）の全部又は一部の後で、インデクサ３４４はコンストラクタ３４６に制御をわたし、該コンストラクタ３４６はインデックスされた文書を選択する（図５のステップ５０２）。
【００４６】
ステップ５０４で、文書中の用語が候補用語のマスターリスト３４２と比較される。用語がマスターリスト３４２にある（５０６−はい）の場合、用語は、文書に関連付けられた候補用語のセット４０２に加えられる（５１０）。ステップ５０４が、上記に説明された左−右貪欲アルゴリズムなどのより複雑なマッチング方式を包含できる点に留意されたい。
【００４７】
幾つかの実施形態において、比較されることになる文書はウェブページである。従って、マスターリスト３４２に対する比較に適した有効な語を構成するものに関して幾つかの決定を行う必要がある。１つの方法では、実際にはウェブページである文書を構文解析して句抽出のためのテキストを見出す。１つの実施形態において、句マッチングは、全ての「ビジブル」テキストプラスメタページ記述を使用してステップ５０４で実行され、このような句は、ＨＴＭＬコード、ジャバスクリプトなどを含まない。有効な句を得るために、ウェブページ内の「句境界」（例えばテーブルタグ）が、リスト３４２との比較のために文書から抽出された表現が句境界を跨がないように保存される。本発明の幾つかの実施形態に使用される句境界の付加的な実施例は、限定ではないが「，」、「？」のような句読点、空行などを含む。
【００４８】
本発明の幾つかの実施形態において、マスターリスト３４２は、幾つかの異種ソースから集められた用語の極めて大きなセットである。従って、ステップ５０４で、情報の候補用語だけが確実に選択されて候補用語のセットに含まれるように付加的なフィルタリングを実行することができる。幾つかの実施形態において、マスターリスト３４２内の用語と比較される文書内の用語は、比較の前に処理される。例えば、幾つかの実施形態において、句読点マークはリスト３４２との比較の前に用語から取り除かれる。幾つかの実施形態において、句読点文字は、リスト３４２との比較の前にスペースに置き換えられる。幾つかの実施形態において、ノイズ用語のリスト３５４がメモリ３１４に記憶される。代表的なノイズ用語は、限定ではないが、「ａ」、「ｔｈｅ」、「ｗｈｏ」、「ｗｈａｔ」、及び「ｗｈｅｒｅ」などの語を含む。従って、ノイズ用語のリスト３５４がメモリ３１４に記憶される実施形態において、比較ステップ５０４では、マスターリスト３４２と比較されることになる用語がノイズ用語のリスト３５４内に存在するかどうかが最初に判定されることになる。存在する場合には、用語は無視され、リスト３４２とは比較されない。幾つかの実施形態において、ステップ５０４で文字の少なくともある最小閾値を包含する用語だけが比較される。例えば、幾つかの実施形態では、ステップ５０４で少なくとも４つの文字を包含する用語だけを比較する。
【００４９】
決定５０６の結果に関わらず、コンストラクタ３４６によって文書内の他のいずれかの用語をマスターリスト３４２と比較する必要があるかどうかに関して判定５０８が行われる。決定５０８の結果を判定するために使用できる多くの種々の条件（例えば、用語カットオフの最大数、固有用語カットオフの最大数、セット４１０内に既に存在する候補用語の最大数など）が開示されている。
【００５０】
図５のフローチャートに続くのは任意選択のステップである。任意選択のステップ５１２で、冗長用語は、文書に関連付けられた候補用語のセットにフォールドされる。任意選択のステップ５１４で、インデックス３５２内の文書が分類される（例えば第１及び第２クラスに）。
【００５１】
分類ステップ５１４を行うことができる幾つかの異なる方法があり、全てのこのような方法は本発明の範囲内に含まれる。例えば、幾つかの実施形態において、各文書４０２は第１又は第２クラスに分類される。好ましい実施形態において、第１クラスは家族向けクラスであり、第２クラスは非家族向けクラスである。文書４０２は、性的に露骨な、不快な、或いは暴力的な言葉を含む場合には第２クラスに分類される。それ以外は、第１クラスに分類される。幾つかの実施形態において、分類モジュール３５０（図３）は、このような分類を行うために使用される。一般的に分類モジュール３５０は、文書が、性的に露骨な、不快な、或いは暴力を含む傾向があるかどうか判定することによって働く。このような傾向がある場合には、該文書は非家族向けと指定される。この指定は、分類されたセット４１０に関連付けられる文書に対応する特徴値４０８（図４）に記憶される。
【００５２】
この段階では、通常候補用語のセット内に多数の候補用語が存在する。例えば、１０００もの数の候補用語を候補用語のセットに加えることができる実施形態では、候補用語のセットはこの段階で１０００の用語を含むことができる。各候補用語セット内の候補用語の数に関わらず、これらはランク付けされない。従って、ステップ５１６において候補用語がランク付けされ、ランク付けされた候補用語のＮ番目までの最も高い数が、候補セットに残ることが許可され、全ての他の候補用語が取り除かれて、ランク付けされたセット（５１６）のＮ番目（例えば２０）までの最も代表的な用語だけを保持するようにする。従って、ステップ５１６の有効作用は、候補用語のセットからランク付けされた候補用語のセットを作り出すことである。更にステップ５１６で、トップランクの用語（例えばトップ２０）だけがランク付けされた候補用語のセットに残ることが許可される。
【００５３】
ランク付け関数によって使用される基準又はパラメータは、各用語が文書に現れる回数、用語が文書の予め定義された初期部分に現れるかどうか、文書での用語の最初の位置、及び用語の文字数のうちの１つ又はそれ以上を含むことができる。これらのパラメータに基づいて、ランクが各候補用語に割り当てられ、次いで、最も高いランクを有するＮ番目までの用語だけがランク付け候補用語のセット内に保持される。他の用語は、そのセットから削除される。各文書と関連付けられた候補用語の数を制限することは、文書インデックスが過剰に大きくなるのを防ぐのに役立ち、処理の速度を最優先する場合にクエリー時に考慮する必要のある用語の量を低減する。ある文書についてランク付けされた候補用語のセットは、文書のインデックスエントリー（図４の４１０を参照）、候補用語を表わしているストリングのセット（任意選択的に圧縮される）又はインデックスに記憶することによって文書と関連付けることができ、ここでは各インデックス値は、候補用語のマスターリスト３４２における用語を示す。関係する値は、ランキングプロセスで使用される用語スコアが文書及び／又は文書の用語の第１位置に現れるように、文書と関連付けられた各候補用語（又は候補用語へのポインタ）と共に文書の文書インデックス３５２エントリーに記憶することができる。しかしながら、好ましい実施形態において、このような付加的な値は文書インデックス３５２には記憶されない。
【００５４】
ランク付けされた候補用語のセット４１０が文書インデックス３５２の文書に関連付けられるプロセスを説明してきた。次に、本発明の１つの実施形態に従って、このようなセット４１０が提示用の候補用語のサブセットを構成するのに使用される方法を説明する図６に注目されたい。ステップ６０２で、クエリーはクエリーハンドラ３２０によって受信される。ステップ６０４で、クエリーは、文書インデックス３５２からランク付けされた文書の初期グループを検索することによって処理される。幾つかの実施形態において、ランク付けされた文書の初期グループがその文書自体以外の文書の標識（ｉｎｄｉｃｉａ）のみを包含できる点は理解されるであろう。しかしながら、この標識（ｉｎｄｉｃｉａ）は、文書の初期セットの各文書に対するユニフォームリソースロケータ（ＵＲＬ）を含むことになる。従って、各文書は、ユーザによって引き続き要求される場合にはインターネット（又はネットワークの他のある形態）から検索することができる。幾つかの実施形態において、文書の初期セットは、サーバ３００（図３）のメモリ３１４にサーチ結果３４０として記憶される。再び図６を参照すると、提案されたクエリー改良のリスト（候補用語のサブセット）がサーチ結果３４０を使用して作成される（６０６）。
【００５５】
提案されたクエリー改良のリスト（候補用語のサブセット）が作成される方法は、クエリーが家族向けサーチであるかどうかに依存することになる。任意選択のステップ６０８で、サーチ結果３４０（ランク付けされた文書の初期グループ）の各トップランクの文書（例えば最初の５０文書）について文書の分類が行われる。サーチ結果３４０でのトップランクの文書の閾値パーセンテージが、第１分類（家族向け分類）に属する場合、第１分類に属さないトップランクの文書と関連付けられた候補用語の全てのセット４１０は、図６の後続のあらゆるステップにおいても使用されない。幾つかの実施形態において、家族向け以外の分類はインデキシング（図５）中に文書を分類するのに使用される。このような実施形態では、このような分類を使用して、ランク付けされた候補用語のどのセットが候補用語のサブセットを構成するのに使用されるかをステップ６０８で判定することができる。例示的な実施形態において、Ｍ個のトップランクの文書（例えば、サーチ結果３４０からの１０個のトップランクの文書）のみの分類は、ステップ６０８で判定を行うのに使用される。例えば、１０個のトップランクの文書の少なくとも８つが家族向けであると分類される場合、非家族向け文書からの候補用語は、提案されたクエリー改良のリストを作成するのに使用されるランク付けされた候補用語のセットから除外される。
【００５６】
ステップ６１０で、サーチ結果３４０の文書に関連するランク付けされた候補用語のそれぞれのセットの１つ又はそれ以上内に存在する候補用語のサブセットが選択される。１つの実施形態において、この選択関数は、ランク付けされた文書の初期グループ（サーチ結果３４０）のトップランクの文書に関連するランク付けされた候補用語の各それぞれのセット４１０における各候補用語に重み付け関数を適用する段階を含む。ランク付けされた文書の初期グループ内の各トップランクの文書は、閾値ランキングより数値的に小さいランキングを有する。幾つかの実施形態において、トップランクの文書は、Ｔを５０などの予め定義された数（及び好ましくは５から２００までの範囲、更に好ましくは２０から１００までの範囲にある）とすると、Ｔ個のトップランクの文書である。ステップ６１０では、関係する用語をユーザに提示される候補用語のサブセットに集める機会を最大にするために、トップランクの文書だけが検討される。種々の実施形態において、トップ５、１０、１５、２０、５０、又は１００の文書だけが検討される。最も高い重みを受け取るこれらの候補用語は、候補用語のサブセットに含まれる。幾つかの実施形態において、候補用語のサブセットの用語の数は、２５より少ない数に制限される。
【００５７】
幾つかの実施形態において、サーチ結果３４０の初期グループに文書のカットオフ数より少ない文書がある場合、候補用語のサブセットは構築されず、候補用語のサブセットはユーザに提示されない。例えば、１つの実施形態において、サーチ結果３４０の初期グループにおいて３５より少ない文書がある場合には候補用語のサブセットは構築されない。
【００５８】
本発明は、サーチ結果３４０のトップランクの文書に関連付けられたセット４１０の各々において候補用語をスコアするための幾つかの異なる重み付け関数を提供する。これらの異なる重み付け関数は、エンジン３２２（図３）の選択関数３２４の種々の実施形態で使用される。
【００５９】
幾つかの実施形態において、関数３２４（重み付け関数）によって候補用語に加えられる重みは、（ｉ）候補用語を含むもの、及び（ｉｉ）トップランクの文書にそれぞれ関連付けられるものの両方であるランク付けされた候補用語のセットの数に応じて決定される。例えば、５０のトップランクの文書があり、候補用語「スペースシャトル」がトップランクの文書にそれぞれ関連するランク付けされた候補用語のセットの３つにおいて現れる場合を考える。この場合、３の重みが、候補用語「スペースシャトル」に加えられることになる。
【００６０】
幾つかの実施形態において、選択関数３２６によって候補用語に加えられる重みは、（ｉ）候補用語を含み（ｉｉ）トップランクの文書にそれぞれ関連するランク付けされた候補用語のこれらのセットの候補用語の関数（例えば平均）に応じて決定される。幾つかの実施形態は、用語を含むセットと用語を含まないセットの両方を考慮する。用語を含まないセットは、用語がセット内に存在しないことを示す平均化のための数値を割り当てられる。このような重み付け係数は、ランク付けされた候補用語の各セットが実際にはランク付けされた順序リストであることを利用する。従って、候補用語「スペースシャトル」がトップランク文書にそれぞれ関連付けられた候補用語の多くのセットのランク付けリストのトップに現れる場合には、この重み付け方式では比較的高い重みを受け取ることになる。逆に、用語「スペースシャトル」が、これが現れるランク付けされた候補用語の各セットの最終用語の間にある場合、該用語はこの重み付け方式で比較的低い重みを受け取ることになる。
【００６１】
幾つかの実施形態において、関数３２４によって候補用語に加えられる重みは、受信クエリーの用語が候補用語内に存在するかどうかに応じて決定される。例えば、クエリー用語が「シャトル」であって候補用語が「スペースシャトル」である場合、候補用語は全重みが与えられ、これ以外は重みを与えられない。
【００６２】
幾つかの実施形態において、関数３２４（重み付け関数）によって候補用語に加えられる重みは、候補用語の文字数に応じて決定される。例えば、候補用語「スペースシャトル」は、候補用語「犬」よりもより大きな重みを受け取ることになる。
【００６３】
幾つかの実施形態において、関数３２４によって候補用語に加えられる重みは、候補用語を含むランク付けされた候補用語のセットに関連付けられたトップランクの文書のランクの関数（例えば平均）に応じて決定される。このような重み付け方式は、サーチエンジン３２２によってサーチ結果の初期セットに既に加えられているランキングを活用する。このような重み付け方式では、より高いランクの文書と関連付けられたセット４１０からの候補用語は、より低いランクの文書と関連付けられた候補用語よりも高い優先度が与えられる。例えば、候補用語「スペースシャトル」が、ランク付けされた文書の初期グループ内のトップランクの文書の文書２、４、及び６に関連するランク付けされた候補用語のそれぞれのセットに現れる場合を考える。すなわち、この重み付け方式では、用語「スペースシャトル」は値４の関数である重みを受け取ることになる。ここで、用語「スペースシャトル」が、ランク付けされた文書の初期グループのトップランク文書におくる文書１０、２０、及び３０に関連するランク付けされた候補用語のそれぞれのセットに現れると仮定する。すなわち、この重み付け方式では、用語「スペースシャトル」は値２０の関数である重みを受け取ることになる。この重み付け方式では、値４は値２０で作られた重みに比べてより良好な重みを作り出すことになる（候補用語の重みを上げることになる）。幾つかの実施形態において、候補用語を含まないセットがこの重み付け関数で考慮される。これらは平均するための数値を割り当てられる。
【００６４】
幾つかの実施形態において、語が最初に候補用語として生じる文書のランクは重み付け関数に使用される。
【００６５】
選択関数３２６の種々の実施形態によって使用される特定の重み付け係数を、このような係数を導入するために概説してきた。しかしながら、好ましい実施形態において、幾つかのこのような係数は望ましい結果をもたらすために組み合わされる。以下は、選択関数３２６の幾つかの好ましい実施形態である。
【００６６】
幾つかの実施形態において、関数３２４によって候補用語に加えられる重みは、ＴｅｒｍＣｏｕｎｔ、ＴｅｒｍＰｏｓｉｔｉｏｎ、ＲｅｓｕｌｔＰｏｓｉｔｉｏｎ、ＴｅｒｍＬｅｎｇｔｈ、及びＱｕｅｒｙＩｎｃｌｕｓｉｏｎのいずれかの組合せ（又はいずれかの重み付けの組合せ）に応じて決定され、ここで、
ＴｅｒｍＣｏｕｎｔは、（ｉ）候補用語を含み、且つ（ｉｉ）トップランクの文書にそれぞれ関連するランク付けされた候補用語のセットの数であり、
ＴｅｒｍＰｏｓｉｔｉｏｎは、（ｉ）候補用語を含み、且つ（ｉｉ）トップランクの文書にそれぞれ関連するランク付けされた候補用語のセットにおける候補用語の位置の関数（例えば平均）であり、
ＲｅｓｕｌｔＰｏｓｉｔｉｏｎは、候補用語を含むランク付けされた候補用語のセットに関連付けられたトップランクの文書のランクの関数（例えば平均）であり、
ＴｅｒｍＬｅｎｇｔｈは、候補用語の文字数（候補用語の複雑性）であり、
ＱｕｅｒｙＩｎｃｌｕｓｉｏｎは、受信クエリーの用語が候補用語内に存在するかどうかを示す値である。
【００６７】
本明細書で使用されるＱｕｅｒｙＩｎｃｌｕｓｉｏｎの適用（例えば、ＱｕｅｒｙＩｎｃｌｕｓｉｏｎが１のような非ゼロ値である場合）は、受信クエリーの用語が候補用語内に存在する場合に候補用語の重みが増やされることを意味する。更に、ＱｕｅｒｙＩｎｃｌｕｓｉｏｎの非適用（例えば、ＱｕｅｒｙＩｎｃｌｕｓｉｏｎがゼロに等しく設定される場合）は、受信クエリーの用語が候補用語内に存在しい場合に候補用語の重みが増やされないことを意味する。幾つかの実施形態において、候補用語はノイズ用語（例えば、ａ、ｔｈｅ、ｗｈｏ、ｗｈａｔ、ｗｈｅｒｅなど）に対してクレジットされない。従って、クエリーがノイズワード「ｆｏｒ」を含み、且つ候補用語がワード「ｆｏｒ」を含む場合には、クレジットは候補用語に与えられず、ＱｕｅｒｙＩｎｃｌｕｓｉｏｎは重みが増やされない。
【００６８】
幾つかの実施形態において、関数３２４によって候補用語に加えられる重みは次式に従って求められる。
ＴｅｒｍＣｏｕｎｔ＋ＴｅｒｍＰｏｓｉｔｉｏｎ＋ＲｅｓｕｌｔＰｏｓｉｔｉｏｎ＋ＴｅｒｍＬｅｎｇｔｈ＋ＱｕｅｒｙＩｎｃｌｕｓｉｏｎ
ここで、重みＴｅｒｍＣｏｕｎｔ、ＴｅｒｍＰｏｓｉｔｉｏｎ、ＲｅｓｕｌｔＰｏｓｉｔｉｏｎ、ＴｅｒｍＬｅｎｇｔｈ、及びＱｕｅｒｙＩｎｃｌｕｓｉｏｎは、上記に定義されたものと同じである。幾つかの実施形態において、ＴｅｒｍＣｏｕｎｔ、ＴｅｒｍＰｏｓｉｔｉｏｎ、ＲｅｓｕｌｔＰｏｓｉｔｉｏｎ、ＴｅｒｍＬｅｎｇｔｈ、及びＱｕｅｒｙＩｎｃｌｕｓｉｏｎは、各々別々に重み付けされる。
【００６９】
幾つかの実施形態において、関数３２４によって候補用語に加えられる重みは、次式に従って求められる。
（ＴｅｒｍＣｏｕｎｔ*ｗ1）＋
（ＴｅｒｍＰｏｓｉｔｉｏｎ*（ｗ2＋（ＲｅｆｉｎｅｍｅｎｔＤｅｐｔｈ*ｗ2´）））＋
（ＲｅｓｕｌｔＰｏｓｉｔｉｏｎ*ｗ3）＋
（ＴｅｒｍＬｅｎｇｔｈ*（ｗ4＋（ＲｅｆｉｎｅｍｅｎｔＤｅｐｔｈ*ｗ4´）））＋
（ＱｕｅｒｙＩｎｃｌｕｓｉｏｎ*（ｗ5＋（ＲｅｆｉｎｅｍｅｎｔＤｅｐｔｈ*ｗ5´）））
ここで、ｗ1、ｗ2、ｗ3、ｗ4、ｗ5、ｗ2´、ｗ4´、及びｗ5´は別々の重みである。更に、ＲｅｆｉｎｅｍｅｎｔＤｅｐｔｈは、受信クエリーについて処理が行われた回数である。言い換えると、ＲｅｆｉｎｅｍｅｎｔＤｅｐｔｈは、ユーザがオリジナルのサーチクエリーに候補用語のサブセットからの用語を加える任意選択のステップ６１４の実行操作によってステップ６０２から６１２が繰り返される回数である。１つの実施形態において、 ｗ1＝１００
ｗ2＝１５
ｗ2´＝１５
ｗ3＝１
ｗ4＝１
ｗ4´＝０
ｗ5＝１００、及び
ｗ5´＝５０である。
【００７０】
本発明の幾つかの実施形態において、選択関数６１０はランク付けされた候補用語のセットの幾つかの候補用語を取り除くことになる。例えば、幾つかの実施形態において、ある接頭辞又は接尾辞だけが異なるランク付けされた候補用語のセットの候補用語は、共にフォールドされる。例えば、幾つかの実施形態において、接頭辞のリスト及び接尾辞のリストはメモリ３１４に記憶される。２つの候補用語の違いが、候補用語の一方が他方の候補用語の対応する語に対して語の最初にある接頭辞、又は語の最後にある接尾辞が異なる語を含むだけの場合、２つの候補用語は共にフォールドされる。幾つかの実施形態において、接頭辞の３つのクラス（及び接尾辞の３つの類似のクラス）がある。候補用語が第１クラスに属している接頭辞を含む場合、その語は廃棄される。候補用語が第２クラスに属する接頭辞を含む場合、その接頭辞は取り除かれる。候補用語が第３クラスに属する接頭辞を含む場合、評価が行われる。この評価において、トップランクの文書と関連するランク付けされた候補用語のセットの各々は、接頭辞を含まない同じ用語の事例についてサーチされる。このような事例が見つからない場合、接頭辞はストリップされない。このような事例が見つかった場合、接頭辞はストリップされる。このタイプの接頭辞（及び接尾辞）処理は、多くの事例で有用である。例えば、候補用語が「ｔｈｅ ｃａｒｓ」である場合を考える。通常、接頭辞「ｔｈｅ」は、ストリップすべき接頭辞であると考えられる。しかしながら、候補用語が名称「ｔｈｅ ｃａｒｓ」で一般的に呼ばれている有名な音楽グループを意味する場合がある。従って、サーチは、接頭辞「ｔｈｅ」のない用語「ｃａｒｓ」がトップランクの文書と関連するランク付けされた候補用語の他のセットのいずれかに見つかるかどうかを確実に調べる。このような事例が現れない場合には、接頭辞はストリップされない。この実施例では、本明細書で使用される接頭辞を上述の接辞（例えば、ｕｎ−、ｎｏｎ−など）或いは上述の語又は句（例えば、ｔｈｅ、ｏｆ、ｔｏ ｇｏなど）とすることができる点に留意されたい。
【００７１】
ステップ６１２で、候補用語のサブセットがユーザに提示される。ステップ６１４で、ユーザは、候補用語のサブセットの用語１３６（図２）を任意選択的に選択し、オリジナル（受信された）クエリーとパネル１４０（図２）に表示された候補用語のサブセットから選択された候補用語１３６とを含む変更されたクエリーで、処理（ステップ６０４）、選択（ステップ６０６）、及び提示（ステップ６１２）が繰り返される。上記に説明されたように、幾つかの実施形態では、ユーザは、以前に提出されたクエリーに追加するため、以前に提出されたクエリーと置き換えるため、又は以前に提出されたクエリーと共に排他的な用語として使用するために用語１３６を選択することができる。
【００７２】
本明細書で引用される全ての引例は、全体的に、及び各個々の出版物又は特許もしくは特許出願が具体的であり且つ全ての目的のためその全てにおいて本明細書に組み込まれることが個々に示される程度まで全ての目的のために本明細書に組み込まれる。
【００７３】
本発明は、コンピュータ可読記憶媒体に組み込まれたコンピュータプログラム機構を含むコンピュータプログラム製品として実施することができる。例えば、このコンピュータプログラム製品は、図３に示されたプログラムモジュールを包含できる。これらのプログラムモジュールは、ＣＤ−ＲＯＭ、磁気ディスク記憶製品、或いは他の何らかのコンピュータ可読データ又はプログラム記憶製品に記憶できる。コンピュータプログラム製品のソフトウェアモジュールもまた、インターネット又は他の方法を介して、搬送波上のコンピュータデータ信号（これにソフトウェアモジュールが組み込まれる）の伝送によって電気的に配信することができる。
【００７４】
本発明の多くの修正及び変形は、当業者には明らかなように本発明の精神及び範囲から逸脱することなく行うことができる。本明細書で説明された特定の実施形態は、例証としてのみ提供される。実施形態は、本発明の原理、及びその実際的応用を正しく説明するために選ばれて説明されたが、これによって当業者は企図される特定の用途に適する種々の修正により本発明及び種々の実施形態をより良好に利用することができる。本発明は、添付の請求項が与える均等物の全範囲と共にこれらの請求項によってのみ限定されるものとする。
【符号の説明】
【００７５】
１００ クライアントコンピュータ
１１０ サーチエンジンサーバ
１２０ 文書インデックス
【特許請求の範囲】
【請求項１】
受信クエリーを改良するための方法であって、サーチサーバに送信されたクエリーに応じて、前記サーチサーバは、
前記受信クエリーに対応するトップランク付けされた文書の初期グループを作成するように該受信クエリーを処理するステップと、
前記初期グループ内の文書の全部又は一部の各文書を事前計算済みのランク付けされた候補用語の各セットに関連付けて、前記ランク付けされた候補用語の各セットの各候補用語が、前記各文書内に組み込まれるようにするステップと、
前記初期グループ内の１以上のトップランク付けされた文書のために、前記１以上のトップランク付けされた文書の分類を決定するステップと、
選択関数に従って、前記１以上のトップランク付けされた文書の分類に対応する前記ランク付けされた候補用語の各セット内にある候補用語のサブセットを選択するステップであって、前記サーチサーバは、前記選択関数において、
（ｉ）前記トップランク付けされた文書の初期グループ内の文書に関連する前記ランク付けされた候補用語の各セット内の各候補用語に重み付け関数を適用し、前記ランク付けされた文書の初期グループ内の各トップランクの文書が閾値ランキングより数値的に小さいランキングを有し、（ｉｉ）前記候補用語のサブセットについて、最も高い重みを受け取る候補用語を選択し、さらに、（ｉｉｉ）前記重み付け関数によって候補用語に加えられる重みに対して、（ａ）前記候補用語を含み、且つ（ｂ）トップランクの文書にそれぞれ関連するランク付けされた候補用語のセットの数に応じて決定される重みを適用する当該ステップを実行し、
前記受信クエリーに応答して、前記トップランク付けされた文書の初期グループと前記候補用語のサブセットとを提示するステップとを実行する、ことを特徴とする方法。
【請求項２】
前記トップランク付けされた文書の初期グループ内の文書の全部又は一部について、当該各文書と関連する前記ランク付けされた候補用語の各セットが、
（Ａ）前記トップランク付けされた文書の用語を候補用語のマスターリストと比較し、前記用語が前記候補用語のマスターリスト内にある場合に該用語を前記候補用語のセットに加え、
（Ｂ）前記文書の用語と前記候補用語のマスターリストとの比較を繰り返し、
（Ｃ）前記候補用語のセット内の候補用語をランク付けして、これにより前記ランク付けされた候補用語の各セットを形成する、
ことによって識別される、請求項１に記載の方法。
【請求項３】
前記比較ステップ（Ａ）の処理によって候補用語が識別される回数が、前記ランキング（Ｃ）によって使用されて、前記ランク付けされた候補用語のセット内の前記候補用語をランク付ける、請求項２に記載の方法。
【請求項４】
前記ステップ（ｉｉｉ）に代って、前記重み付け関数によって候補用語に加えられる前記重みが、（ａ）前記候補用語を含み、且つ（ｂ）前記トップランクの文書にそれぞれ関連するランク付けされた候補用語のセット内の前記候補用語の平均位置に応じて決定されることを特徴とする請求項１に記載の方法。
【請求項５】
前記ステップ（ｉｉｉ）に代って、前記重み付け関数によって候補用語に加えられる前記重みが、前記候補用語の文字数に応じて決定されることを特徴とする請求項１に記載の方法。
【請求項６】
前記ステップ（ｉｉｉ）に代って、前記重み付け関数によって候補用語に加えられる前記重みが、前記候補用語を含む前記トップランク付けされた文書の初期グループ内の文書の位置に応じて決定されることを特徴とする請求項１に記載の方法。
【請求項７】
前記ステップ（ｉｉｉ）に代って、前記重み付け関数によって候補用語に加えられる前記重みが、前記候補用語を含むランク付けされた候補用語のセットに関連付けられた前記トップランクの文書の平均ランクに応じて決定されることを特徴とする請求項１に記載の方法。
【請求項８】
前記ステップ（ｉｉｉ）に代って、前記重み付け関数によって候補用語に加えられる前記重みが、ＴｅｒｍＣｏｕｎｔ＋ＴｅｒｍＰｏｓｉｔｉｏｎ＋ＲｅｓｕｌｔＰｏｓｉｔｉｏｎ＋ＴｅｒｍＬｅｎｇｔｈ＋ＱｕｅｒｙＩｎｃｌｕｓｉｏｎに応じて決定され、ここで、
ＴｅｒｍＣｏｕｎｔは、（ｉ）前記候補用語を含み、且つ（ｉｉ）前記トップランクの文書にそれぞれ関連するランク付けされた候補用語のセットの数であり、
ＴｅｒｍＰｏｓｉｔｉｏｎは、（ｉ）前記候補用語を含み、且つ（ｉｉ）前記トップランクの文書にそれぞれ関連するランク付けされた候補用語のセットにおける候補用語のランク位置の関数であり、
ＲｅｓｕｌｔＰｏｓｉｔｉｏｎは、前記候補用語を含むランク付けされた候補用語のセットに関連付けられるトップランクの文書のランクの関数であり、
ＴｅｒｍＬｅｎｇｔｈは、前記候補用語の文字数（候補用語の複雑性）であり、
ＱｕｅｒｙＩｎｃｌｕｓｉｏｎは、前記受信クエリーの用語が前記ランク付けされた候補用語のセット内に存在するかどうかを示す値であることを特徴とする請求項１に記載の方法。
【請求項９】
ＴｅｒｍＣｏｕｎｔ、ＴｅｒｍＰｏｓｉｔｉｏｎ、ＲｅｓｕｌｔＰｏｓｉｔｉｏｎ、ＴｅｒｍＬｅｎｇｔｈ、及びＱｕｅｒｙＩｎｃｌｕｓｉｏｎは、各々別々に重み付けされることを特徴とする請求項８に記載の方法。
【請求項１０】
前記サーチサーバは更に、前記受信クエリーと前記候補用語のサブセットからの候補用語とを含む変更されたクエリーを使用して、任意選択的に前記受信クエリーを処理するステップ、選択するステップ、及び提示するステップの繰り返しを実行する請求項８に記載の方法。
【請求項１１】
前記重み付け関数によって候補用語に加えられる前記重みが、次式に応じて決定されることを特徴とする請求項１０に記載の方法。
（ＴｅｒｍＣｏｕｎｔ*ｗ1）＋
（ＴｅｒｍＰｏｓｉｔｉｏｎ*（ｗ2＋（ＲｅｆｉｎｅｍｅｎｔＤｅｐｔｈ*ｗ2´）））＋
（ＲｅｓｕｌｔＰｏｓｉｔｉｏｎ*ｗ3）＋
（ＴｅｒｍＬｅｎｇｔｈ*（ｗ4＋（ＲｅｆｉｎｅｍｅｎｔＤｅｐｔｈ*ｗ4´）））＋
（ＱｕｅｒｙＩｎｃｌｕｓｉｏｎ*（ｗ5＋（ＲｅｆｉｎｅｍｅｎｔＤｅｐｔｈ*ｗ5´）））
ここで、ｗ1、ｗ2、ｗ3、ｗ4、ｗ5、ｗ2´、ｗ4´、及びｗ5´は別々の重みであり、ＲｅｆｉｎｅｍｅｎｔＤｅｐｔｈは前記受信クエリーに対して前記処理が行われた回数である。
【請求項１２】
コンピュータシステムと共に使用されるコンピュータ読み取り可能な記録媒体であって、受信クエリーを改良するためのクエリー改良提案エンジンに、
前記受信クエリーに対応するトップランク付けされた文書の初期グループを作成するように前記受信クエリーを処理させ、
前記トップランク付けされた文書の初期グループ内の文書の全部又は一部の各文書を、事前計算済みのランク付けされた候補用語の各セットに関連付けて、前記ランク付けされた候補用語の各セットの各候補用語が前記各文書内に組み込まれるように処理させ、
前記初期グループ内の１以上のトップランク付けされた文書のために、前記１以上のトップランク付けされた文書の分類を決定するように処理させ、
選択関数に従って、前記１以上のトップランク付けされた文書の分類に対応する前記候補用語の各セット内にある候補用語のサブセットを選択させ、ここで、前記選択関数は、
（ｉ）前記トップランク付けされた文書の初期グループ内の文書に関連するランク付けされた候補用語の各セット内の各候補用語に重み付け関数を適用する命令であって、前記トップランク付けされた文書の初期グループ内の各文書が閾値ランキングより数値的に小さいランキングを有する命令と、（ｉｉ）前記候補用語のサブセットについて、最も高い重みを受け取る候補用語を選択する命令とを含み、さらに、（ｉｉｉ）前記重み付け関数によって候補用語に加えられる重みに対して、（ａ）前記候補用語を含み、且つ（ｂ）トップランクの文書にそれぞれ関連するランク付けされた候補用語のセットの数に応じて決定される重みを適用することを含み、
前記受信クエリーに応答して、前記トップランク付けされた文書の初期グループ及び前記候補用語のサブセットを提示させる、
プログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１３】
前記トップランク付けされた文書の初期グループ内の文書の全部又は一部について、当該各文書と関連する前記ランク付けされた候補用語の各セットが、
（Ａ）前記トップランク付けされた文書の用語を候補用語のマスターリストと比較し、前記用語が前記候補用語のマスターリスト内にある場合に、前記文書の用語を候補用語として前記文書と関連する前記ランク付けされた候補用語の各セットに加え、
（Ｂ）前記文書内の用語の最大数が検討されるまで、前記文書の用語と前記候補用語のマスターリストとの比較を再実行する、
ことによって識別される、請求項１２に記載のコンピュータ読み取り可能な記録媒体。
【請求項１４】
前記（Ａ）の比較によって候補用語が識別される回数が、前記文書に関連する前記ランク付けされた候補用語の各セットに含まれる、請求項１３に記載の方法。
【請求項１５】
前記（ｉｉｉ）に代って、前記重み付け関数によって候補用語に加えられる重みが、（ａ）前記候補用語を含み、且つ（ｂ）トップランクの文書にそれぞれ関連するランク付けされた候補用語のセット内の前記候補用語の平均位置に応じて決定されることを特徴とする請求項１２に記載のコンピュータ読み取り可能な記録媒体。
【請求項１６】
前記（ｉｉｉ）に代って、前記重み付け関数によって候補用語に加えられる重みが、前記候補用語の文字数に応じて決定されることを特徴とする請求項１２に記載のコンピュータ読み取り可能な記録媒体。
【請求項１７】
前記（ｉｉｉ）に代って、前記重み付け関数によって候補用語に加えられる重みが、前記候補用語を含む前記トップランク付けされた文書の初期グループ内の文書の位置に応じて決定されることを特徴とする請求項１２に記載のコンピュータ読み取り可能な記録媒体。
【請求項１８】
前記（ｉｉｉ）に代って、前記重み付け関数によって候補用語に加えられる重みが、前記候補用語を含むランク付けされた候補用語のセットに関連付けられた前記トップランクの文書の平均ランクに応じて決定されることを特徴とする請求項１２に記載のコンピュータ読み取り可能な記録媒体。
【請求項１９】
前記（ｉｉｉ）に代って、前記重み付け関数によって候補用語に加えられる重みが、ＴｅｒｍＣｏｕｎｔ＋ＴｅｒｍＰｏｓｉｔｉｏｎ＋ＲｅｓｕｌｔＰｏｓｉｔｉｏｎ＋ＴｅｒｍＬｅｎｇｔｈ＋ＱｕｅｒｙＩｎｃｌｕｓｉｏｎに応じて決定され、ここで、
ＴｅｒｍＣｏｕｎｔは、各トップランクの文書の上位部分に前記候補用語が現れる回数であり、
ＴｅｒｍＰｏｓｉｔｉｏｎは、前記候補用語が現れる各トップランクの文書内の前記候補用語の位置の関数であり、
ＲｅｓｕｌｔＰｏｓｉｔｉｏｎは、前記候補用語を含む前記トップランク付けされた文書の初期グループにおける文書の位置の関数であり、
ＴｅｒｍＬｅｎｇｔｈは、前記候補用語の文字数であり、
ＱｕｅｒｙＩｎｃｌｕｓｉｏｎは、前記受信クエリーの用語が前記候補用語内に存在する場合はゼロではなく、ＱｕｅｒｙＩｎｃｌｕｓｉｏｎは、前記受信クエリーの用語が前記候補用語内に存在しない場合はゼロであることを特徴とする請求項１２に記載のコンピュータ読み取り可能な記録媒体。
【請求項２０】
ＴｅｒｍＣｏｕｎｔ、ＴｅｒｍＰｏｓｉｔｉｏｎ、ＲｅｓｕｌｔＰｏｓｉｔｉｏｎ、ＴｅｒｍＬｅｎｇｔｈ、及びＱｕｅｒｙＩｎｃｌｕｓｉｏｎは、各々別々に重み付けされることを特徴とする請求項１９に記載のコンピュータ読み取り可能な記録媒体。
【請求項２１】
前記クエリー改良提案エンジンは更に、前記受信クエリーと前記候補用語のサブセットからの候補用語とを含む変更されたクエリーを使用して、任意選択的に前記受信クエリーを処理すること、選択すること、及び提示することの繰り返しを実行する請求項１９に記載のコンピュータ読み取り可能な記録媒体。
【請求項２２】
前記重み付け関数によって候補用語に加えられる重みが、次式に応じて決定されることを特徴とする請求項２１に記載のコンピュータ読み取り可能な記録媒体。
（ＴｅｒｍＣｏｕｎｔ*ｗ1）＋
（ＴｅｒｍＰｏｓｉｔｉｏｎ*（ｗ2＋（ＲｅｆｉｎｅｍｅｎｔＤｅｐｔｈ*ｗ2´）））＋
（ＲｅｓｕｌｔＰｏｓｉｔｉｏｎ*ｗ3）＋
（ＴｅｒｍＬｅｎｇｔｈ*（ｗ4＋（ＲｅｆｉｎｅｍｅｎｔＤｅｐｔｈ*ｗ4´）））＋
（ＱｕｅｒｙＩｎｃｌｕｓｉｏｎ*（ｗ5＋（ＲｅｆｉｎｅｍｅｎｔＤｅｐｔｈ*ｗ5´）））
ここで、ｗ1、ｗ2、ｗ3、ｗ4、ｗ5、ｗ2´、ｗ4´、及びｗ5´は別々の重みであり、ＲｅｆｉｎｅｍｅｎｔＤｅｐｔｈは前記受信クエリーに対して前記処理が行われた回数である。
【請求項２３】
受信クエリーを改良するためのコンピュータシステムであって、
中央処理ユニットと、
前記中央処理ユニットに結合された、クエリー改良提案エンジンを記憶するメモリと、を含み、
前記クエリー改良提案エンジンが、
前記受信クエリーに対応するトップランク付けされた文書の初期グループを作成するように前記受信クエリーを処理し、ここで、前記トップランク付けされた文書の初期グループ内の文書の全部又は一部の各文書が、事前計算済みのランク付けされた候補用語の各セットに関連付けられ、その結果、前記ランク付けされた候補用語の各セットの各候補用語が前記文書内に組み込まれ、
前記初期グループ内の１以上のトップランク付けされた文書のために、前記１以上のトップランク付けされた文書の分類を決定し、
選択関数に従って、前記１以上のトップランク付けされた文書の分類に対応する前記ランク付けされた候補用語の各セット内にある候補用語のサブセットを選択し、ここで、前記選択関数は、（ｉ）前記トップランク付けされた文書の初期グループ内の文書に関連するランク付けされた候補用語の各セット内の各候補用語に重み付け関数を適用する命令であって、前記トップランク付けされた文書の初期グループ内の各文書が閾値ランキングより数値的に小さいランキングを有する命令と、（ｉｉ）前記候補用語のサブセットについて、最も高い重みを受け取る候補用語を選択する命令とを含み、さらに、（ｉｉｉ）前記重み付け関数によって候補用語に加えられる重みに対して、（ａ）前記候補用語を含み、且つ（ｂ）トップランクの文書にそれぞれ関連するランク付けされた候補用語のセットの数に応じて決定される重みが適用され、
前記受信クエリーに応答して、前記トップランク付けされた文書の初期グループ及び前記候補用語のサブセットを提示する、
ことを特徴とするコンピュータシステム。
【請求項２４】
前記トップランク付けされた文書の初期グループ内の文書の全部又は一部について、当該各文書と関連する前記ランク付けされた候補用語の各セットが、
（Ａ）前記トップランク付けされた文書の用語を候補用語のマスターリストと比較し、前記用語が前記候補用語のマスターリスト内にある場合に、前記文書の用語を候補用語として前記文書と関連するランク付けされた候補用語の各セットに加え、
（Ｂ）前記文書内の用語の最大数が検討されるまで、前記文書の用語と前記候補用語のマスターリストとの比較を再実行する、
ことによって識別される、請求項２３に記載のコンピュータシステム。
【請求項２５】
前記トップランク付けされた文書の初期グループ内の文書の全部又は一部について、前記（Ａ）の比較ための命令によって候補用語が識別される回数が、前記文書と関連する前記ランク付けされた候補用語の各セットに含まれる、請求項２４に記載のコンピュータシステム。
【請求項２６】
前記（ｉｉｉ）に代って、前記重み付け関数によって候補用語に加えられる重みが、（ａ）前記候補用語を含み、且つ（ｂ）トップランクの文書にそれぞれ関連するランク付けされた候補用語のセット内の前記候補用語の平均位置に応じて決定されることを特徴とする請求項２３に記載のコンピュータシステム。
【請求項２７】
前記（ｉｉｉ）に代って、前記重み付け関数によって候補用語に加えられる重みが、前記候補用語の文字数に応じて決定されることを特徴とする請求項２３に記載のコンピュータシステム。
【請求項２８】
前記（ｉｉｉ）に代って、前記重み付け関数によって候補用語に加えられる重みが、前記候補用語を含む前記トップランク付けされた文書の初期グループ内の文書の位置に応じて決定されることを特徴とする請求項２３に記載のコンピュータシステム。
【請求項２９】
前記（ｉｉｉ）に代って、前記重み付け関数によって候補用語に加えられる重みが、前記候補用語を含むランク付けされた候補用語のセットに関連付けられた前記トップランクの文書の平均ランクに応じて決定されることを特徴とする請求項２３に記載のコンピュータシステム。
【請求項３０】
前記（ｉｉｉ）に代って、前記重み付け関数によって候補用語に加えられる重みが、ＴｅｒｍＣｏｕｎｔ＋ＴｅｒｍＰｏｓｉｔｉｏｎ＋ＲｅｓｕｌｔＰｏｓｉｔｉｏｎ＋ＴｅｒｍＬｅｎｇｔｈ＋ＱｕｅｒｙＩｎｃｌｕｓｉｏｎに応じて決定され、ここで、
ＴｅｒｍＣｏｕｎｔは、各トップランクの文書の上位部分に前記候補用語が現れる回数であり、
ＴｅｒｍＰｏｓｉｔｉｏｎは、前記候補用語が現れる各トップランクの文書内の前記候補用語の位置の関数であり、
ＲｅｓｕｌｔＰｏｓｉｔｉｏｎは、前記候補用語を含む前記トップランク付けされた文書の初期グループにおける文書の位置の関数であり、
ＴｅｒｍＬｅｎｇｔｈは、前記候補用語の文字数であり、
ＱｕｅｒｙＩｎｃｌｕｓｉｏｎは、前記受信クエリーの用語が前記候補用語内に存在する場合適用され、ＱｕｅｒｙＩｎｃｌｕｓｉｏｎは、前記受信クエリーの用語が前記候補用語内に存在しない場合に適用されないことを特徴とする請求項２３に記載のコンピュータシステム。
【請求項３１】
ＴｅｒｍＣｏｕｎｔ、ＴｅｒｍＰｏｓｉｔｉｏｎ、ＲｅｓｕｌｔＰｏｓｉｔｉｏｎ、ＴｅｒｍＬｅｎｇｔｈ、及びＱｕｅｒｙＩｎｃｌｕｓｉｏｎは、各々別々に重み付けされることを特徴とする請求項３０に記載のコンピュータシステム。
【請求項３２】
前記クエリー改良提案エンジンは更に、前記受信クエリーと前記候補用語のサブセットからの候補用語とを含む変更されたクエリーを使用して、任意選択的に前記受信クエリーを処理すること、選択すること、及び提示することの繰り返しを実行する請求項３０に記載のコンピュータシステム。
【請求項３３】
前記重み付け関数によって候補用語に加えられる重みが、次式に応じて決定されることを特徴とする請求項３２に記載のコンピュータシステム。
（ＴｅｒｍＣｏｕｎｔ*ｗ1）＋
（ＴｅｒｍＰｏｓｉｔｉｏｎ*（ｗ2＋（ＲｅｆｉｎｅｍｅｎｔＤｅｐｔｈ*ｗ2´）））＋
（ＲｅｓｕｌｔＰｏｓｉｔｉｏｎ*ｗ3）＋
（ＴｅｒｍＬｅｎｇｔｈ*（ｗ4＋（ＲｅｆｉｎｅｍｅｎｔＤｅｐｔｈ*ｗ4´）））＋
（ＱｕｅｒｙＩｎｃｌｕｓｉｏｎ*（ｗ5＋（ＲｅｆｉｎｅｍｅｎｔＤｅｐｔｈ*ｗ5´）））
ここで、ｗ1、ｗ2、ｗ3、ｗ4、ｗ5、ｗ2´、ｗ4´、及びｗ5´は別々の重みであり、ＲｅｆｉｎｅｍｅｎｔＤｅｐｔｈは前記受信クエリーに対して前記処理が行われた回数である。
【請求項１】
受信クエリーを改良するための方法であって、サーチサーバに送信されたクエリーに応じて、前記サーチサーバは、
前記受信クエリーに対応するトップランク付けされた文書の初期グループを作成するように該受信クエリーを処理するステップと、
前記初期グループ内の文書の全部又は一部の各文書を事前計算済みのランク付けされた候補用語の各セットに関連付けて、前記ランク付けされた候補用語の各セットの各候補用語が、前記各文書内に組み込まれるようにするステップと、
前記初期グループ内の１以上のトップランク付けされた文書のために、前記１以上のトップランク付けされた文書の分類を決定するステップと、
選択関数に従って、前記１以上のトップランク付けされた文書の分類に対応する前記ランク付けされた候補用語の各セット内にある候補用語のサブセットを選択するステップであって、前記サーチサーバは、前記選択関数において、
（ｉ）前記トップランク付けされた文書の初期グループ内の文書に関連する前記ランク付けされた候補用語の各セット内の各候補用語に重み付け関数を適用し、前記ランク付けされた文書の初期グループ内の各トップランクの文書が閾値ランキングより数値的に小さいランキングを有し、（ｉｉ）前記候補用語のサブセットについて、最も高い重みを受け取る候補用語を選択し、さらに、（ｉｉｉ）前記重み付け関数によって候補用語に加えられる重みに対して、（ａ）前記候補用語を含み、且つ（ｂ）トップランクの文書にそれぞれ関連するランク付けされた候補用語のセットの数に応じて決定される重みを適用する当該ステップを実行し、
前記受信クエリーに応答して、前記トップランク付けされた文書の初期グループと前記候補用語のサブセットとを提示するステップとを実行する、ことを特徴とする方法。
【請求項２】
前記トップランク付けされた文書の初期グループ内の文書の全部又は一部について、当該各文書と関連する前記ランク付けされた候補用語の各セットが、
（Ａ）前記トップランク付けされた文書の用語を候補用語のマスターリストと比較し、前記用語が前記候補用語のマスターリスト内にある場合に該用語を前記候補用語のセットに加え、
（Ｂ）前記文書の用語と前記候補用語のマスターリストとの比較を繰り返し、
（Ｃ）前記候補用語のセット内の候補用語をランク付けして、これにより前記ランク付けされた候補用語の各セットを形成する、
ことによって識別される、請求項１に記載の方法。
【請求項３】
前記比較ステップ（Ａ）の処理によって候補用語が識別される回数が、前記ランキング（Ｃ）によって使用されて、前記ランク付けされた候補用語のセット内の前記候補用語をランク付ける、請求項２に記載の方法。
【請求項４】
前記ステップ（ｉｉｉ）に代って、前記重み付け関数によって候補用語に加えられる前記重みが、（ａ）前記候補用語を含み、且つ（ｂ）前記トップランクの文書にそれぞれ関連するランク付けされた候補用語のセット内の前記候補用語の平均位置に応じて決定されることを特徴とする請求項１に記載の方法。
【請求項５】
前記ステップ（ｉｉｉ）に代って、前記重み付け関数によって候補用語に加えられる前記重みが、前記候補用語の文字数に応じて決定されることを特徴とする請求項１に記載の方法。
【請求項６】
前記ステップ（ｉｉｉ）に代って、前記重み付け関数によって候補用語に加えられる前記重みが、前記候補用語を含む前記トップランク付けされた文書の初期グループ内の文書の位置に応じて決定されることを特徴とする請求項１に記載の方法。
【請求項７】
前記ステップ（ｉｉｉ）に代って、前記重み付け関数によって候補用語に加えられる前記重みが、前記候補用語を含むランク付けされた候補用語のセットに関連付けられた前記トップランクの文書の平均ランクに応じて決定されることを特徴とする請求項１に記載の方法。
【請求項８】
前記ステップ（ｉｉｉ）に代って、前記重み付け関数によって候補用語に加えられる前記重みが、ＴｅｒｍＣｏｕｎｔ＋ＴｅｒｍＰｏｓｉｔｉｏｎ＋ＲｅｓｕｌｔＰｏｓｉｔｉｏｎ＋ＴｅｒｍＬｅｎｇｔｈ＋ＱｕｅｒｙＩｎｃｌｕｓｉｏｎに応じて決定され、ここで、
ＴｅｒｍＣｏｕｎｔは、（ｉ）前記候補用語を含み、且つ（ｉｉ）前記トップランクの文書にそれぞれ関連するランク付けされた候補用語のセットの数であり、
ＴｅｒｍＰｏｓｉｔｉｏｎは、（ｉ）前記候補用語を含み、且つ（ｉｉ）前記トップランクの文書にそれぞれ関連するランク付けされた候補用語のセットにおける候補用語のランク位置の関数であり、
ＲｅｓｕｌｔＰｏｓｉｔｉｏｎは、前記候補用語を含むランク付けされた候補用語のセットに関連付けられるトップランクの文書のランクの関数であり、
ＴｅｒｍＬｅｎｇｔｈは、前記候補用語の文字数（候補用語の複雑性）であり、
ＱｕｅｒｙＩｎｃｌｕｓｉｏｎは、前記受信クエリーの用語が前記ランク付けされた候補用語のセット内に存在するかどうかを示す値であることを特徴とする請求項１に記載の方法。
【請求項９】
ＴｅｒｍＣｏｕｎｔ、ＴｅｒｍＰｏｓｉｔｉｏｎ、ＲｅｓｕｌｔＰｏｓｉｔｉｏｎ、ＴｅｒｍＬｅｎｇｔｈ、及びＱｕｅｒｙＩｎｃｌｕｓｉｏｎは、各々別々に重み付けされることを特徴とする請求項８に記載の方法。
【請求項１０】
前記サーチサーバは更に、前記受信クエリーと前記候補用語のサブセットからの候補用語とを含む変更されたクエリーを使用して、任意選択的に前記受信クエリーを処理するステップ、選択するステップ、及び提示するステップの繰り返しを実行する請求項８に記載の方法。
【請求項１１】
前記重み付け関数によって候補用語に加えられる前記重みが、次式に応じて決定されることを特徴とする請求項１０に記載の方法。
（ＴｅｒｍＣｏｕｎｔ*ｗ1）＋
（ＴｅｒｍＰｏｓｉｔｉｏｎ*（ｗ2＋（ＲｅｆｉｎｅｍｅｎｔＤｅｐｔｈ*ｗ2´）））＋
（ＲｅｓｕｌｔＰｏｓｉｔｉｏｎ*ｗ3）＋
（ＴｅｒｍＬｅｎｇｔｈ*（ｗ4＋（ＲｅｆｉｎｅｍｅｎｔＤｅｐｔｈ*ｗ4´）））＋
（ＱｕｅｒｙＩｎｃｌｕｓｉｏｎ*（ｗ5＋（ＲｅｆｉｎｅｍｅｎｔＤｅｐｔｈ*ｗ5´）））
ここで、ｗ1、ｗ2、ｗ3、ｗ4、ｗ5、ｗ2´、ｗ4´、及びｗ5´は別々の重みであり、ＲｅｆｉｎｅｍｅｎｔＤｅｐｔｈは前記受信クエリーに対して前記処理が行われた回数である。
【請求項１２】
コンピュータシステムと共に使用されるコンピュータ読み取り可能な記録媒体であって、受信クエリーを改良するためのクエリー改良提案エンジンに、
前記受信クエリーに対応するトップランク付けされた文書の初期グループを作成するように前記受信クエリーを処理させ、
前記トップランク付けされた文書の初期グループ内の文書の全部又は一部の各文書を、事前計算済みのランク付けされた候補用語の各セットに関連付けて、前記ランク付けされた候補用語の各セットの各候補用語が前記各文書内に組み込まれるように処理させ、
前記初期グループ内の１以上のトップランク付けされた文書のために、前記１以上のトップランク付けされた文書の分類を決定するように処理させ、
選択関数に従って、前記１以上のトップランク付けされた文書の分類に対応する前記候補用語の各セット内にある候補用語のサブセットを選択させ、ここで、前記選択関数は、
（ｉ）前記トップランク付けされた文書の初期グループ内の文書に関連するランク付けされた候補用語の各セット内の各候補用語に重み付け関数を適用する命令であって、前記トップランク付けされた文書の初期グループ内の各文書が閾値ランキングより数値的に小さいランキングを有する命令と、（ｉｉ）前記候補用語のサブセットについて、最も高い重みを受け取る候補用語を選択する命令とを含み、さらに、（ｉｉｉ）前記重み付け関数によって候補用語に加えられる重みに対して、（ａ）前記候補用語を含み、且つ（ｂ）トップランクの文書にそれぞれ関連するランク付けされた候補用語のセットの数に応じて決定される重みを適用することを含み、
前記受信クエリーに応答して、前記トップランク付けされた文書の初期グループ及び前記候補用語のサブセットを提示させる、
プログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１３】
前記トップランク付けされた文書の初期グループ内の文書の全部又は一部について、当該各文書と関連する前記ランク付けされた候補用語の各セットが、
（Ａ）前記トップランク付けされた文書の用語を候補用語のマスターリストと比較し、前記用語が前記候補用語のマスターリスト内にある場合に、前記文書の用語を候補用語として前記文書と関連する前記ランク付けされた候補用語の各セットに加え、
（Ｂ）前記文書内の用語の最大数が検討されるまで、前記文書の用語と前記候補用語のマスターリストとの比較を再実行する、
ことによって識別される、請求項１２に記載のコンピュータ読み取り可能な記録媒体。
【請求項１４】
前記（Ａ）の比較によって候補用語が識別される回数が、前記文書に関連する前記ランク付けされた候補用語の各セットに含まれる、請求項１３に記載の方法。
【請求項１５】
前記（ｉｉｉ）に代って、前記重み付け関数によって候補用語に加えられる重みが、（ａ）前記候補用語を含み、且つ（ｂ）トップランクの文書にそれぞれ関連するランク付けされた候補用語のセット内の前記候補用語の平均位置に応じて決定されることを特徴とする請求項１２に記載のコンピュータ読み取り可能な記録媒体。
【請求項１６】
前記（ｉｉｉ）に代って、前記重み付け関数によって候補用語に加えられる重みが、前記候補用語の文字数に応じて決定されることを特徴とする請求項１２に記載のコンピュータ読み取り可能な記録媒体。
【請求項１７】
前記（ｉｉｉ）に代って、前記重み付け関数によって候補用語に加えられる重みが、前記候補用語を含む前記トップランク付けされた文書の初期グループ内の文書の位置に応じて決定されることを特徴とする請求項１２に記載のコンピュータ読み取り可能な記録媒体。
【請求項１８】
前記（ｉｉｉ）に代って、前記重み付け関数によって候補用語に加えられる重みが、前記候補用語を含むランク付けされた候補用語のセットに関連付けられた前記トップランクの文書の平均ランクに応じて決定されることを特徴とする請求項１２に記載のコンピュータ読み取り可能な記録媒体。
【請求項１９】
前記（ｉｉｉ）に代って、前記重み付け関数によって候補用語に加えられる重みが、ＴｅｒｍＣｏｕｎｔ＋ＴｅｒｍＰｏｓｉｔｉｏｎ＋ＲｅｓｕｌｔＰｏｓｉｔｉｏｎ＋ＴｅｒｍＬｅｎｇｔｈ＋ＱｕｅｒｙＩｎｃｌｕｓｉｏｎに応じて決定され、ここで、
ＴｅｒｍＣｏｕｎｔは、各トップランクの文書の上位部分に前記候補用語が現れる回数であり、
ＴｅｒｍＰｏｓｉｔｉｏｎは、前記候補用語が現れる各トップランクの文書内の前記候補用語の位置の関数であり、
ＲｅｓｕｌｔＰｏｓｉｔｉｏｎは、前記候補用語を含む前記トップランク付けされた文書の初期グループにおける文書の位置の関数であり、
ＴｅｒｍＬｅｎｇｔｈは、前記候補用語の文字数であり、
ＱｕｅｒｙＩｎｃｌｕｓｉｏｎは、前記受信クエリーの用語が前記候補用語内に存在する場合はゼロではなく、ＱｕｅｒｙＩｎｃｌｕｓｉｏｎは、前記受信クエリーの用語が前記候補用語内に存在しない場合はゼロであることを特徴とする請求項１２に記載のコンピュータ読み取り可能な記録媒体。
【請求項２０】
ＴｅｒｍＣｏｕｎｔ、ＴｅｒｍＰｏｓｉｔｉｏｎ、ＲｅｓｕｌｔＰｏｓｉｔｉｏｎ、ＴｅｒｍＬｅｎｇｔｈ、及びＱｕｅｒｙＩｎｃｌｕｓｉｏｎは、各々別々に重み付けされることを特徴とする請求項１９に記載のコンピュータ読み取り可能な記録媒体。
【請求項２１】
前記クエリー改良提案エンジンは更に、前記受信クエリーと前記候補用語のサブセットからの候補用語とを含む変更されたクエリーを使用して、任意選択的に前記受信クエリーを処理すること、選択すること、及び提示することの繰り返しを実行する請求項１９に記載のコンピュータ読み取り可能な記録媒体。
【請求項２２】
前記重み付け関数によって候補用語に加えられる重みが、次式に応じて決定されることを特徴とする請求項２１に記載のコンピュータ読み取り可能な記録媒体。
（ＴｅｒｍＣｏｕｎｔ*ｗ1）＋
（ＴｅｒｍＰｏｓｉｔｉｏｎ*（ｗ2＋（ＲｅｆｉｎｅｍｅｎｔＤｅｐｔｈ*ｗ2´）））＋
（ＲｅｓｕｌｔＰｏｓｉｔｉｏｎ*ｗ3）＋
（ＴｅｒｍＬｅｎｇｔｈ*（ｗ4＋（ＲｅｆｉｎｅｍｅｎｔＤｅｐｔｈ*ｗ4´）））＋
（ＱｕｅｒｙＩｎｃｌｕｓｉｏｎ*（ｗ5＋（ＲｅｆｉｎｅｍｅｎｔＤｅｐｔｈ*ｗ5´）））
ここで、ｗ1、ｗ2、ｗ3、ｗ4、ｗ5、ｗ2´、ｗ4´、及びｗ5´は別々の重みであり、ＲｅｆｉｎｅｍｅｎｔＤｅｐｔｈは前記受信クエリーに対して前記処理が行われた回数である。
【請求項２３】
受信クエリーを改良するためのコンピュータシステムであって、
中央処理ユニットと、
前記中央処理ユニットに結合された、クエリー改良提案エンジンを記憶するメモリと、を含み、
前記クエリー改良提案エンジンが、
前記受信クエリーに対応するトップランク付けされた文書の初期グループを作成するように前記受信クエリーを処理し、ここで、前記トップランク付けされた文書の初期グループ内の文書の全部又は一部の各文書が、事前計算済みのランク付けされた候補用語の各セットに関連付けられ、その結果、前記ランク付けされた候補用語の各セットの各候補用語が前記文書内に組み込まれ、
前記初期グループ内の１以上のトップランク付けされた文書のために、前記１以上のトップランク付けされた文書の分類を決定し、
選択関数に従って、前記１以上のトップランク付けされた文書の分類に対応する前記ランク付けされた候補用語の各セット内にある候補用語のサブセットを選択し、ここで、前記選択関数は、（ｉ）前記トップランク付けされた文書の初期グループ内の文書に関連するランク付けされた候補用語の各セット内の各候補用語に重み付け関数を適用する命令であって、前記トップランク付けされた文書の初期グループ内の各文書が閾値ランキングより数値的に小さいランキングを有する命令と、（ｉｉ）前記候補用語のサブセットについて、最も高い重みを受け取る候補用語を選択する命令とを含み、さらに、（ｉｉｉ）前記重み付け関数によって候補用語に加えられる重みに対して、（ａ）前記候補用語を含み、且つ（ｂ）トップランクの文書にそれぞれ関連するランク付けされた候補用語のセットの数に応じて決定される重みが適用され、
前記受信クエリーに応答して、前記トップランク付けされた文書の初期グループ及び前記候補用語のサブセットを提示する、
ことを特徴とするコンピュータシステム。
【請求項２４】
前記トップランク付けされた文書の初期グループ内の文書の全部又は一部について、当該各文書と関連する前記ランク付けされた候補用語の各セットが、
（Ａ）前記トップランク付けされた文書の用語を候補用語のマスターリストと比較し、前記用語が前記候補用語のマスターリスト内にある場合に、前記文書の用語を候補用語として前記文書と関連するランク付けされた候補用語の各セットに加え、
（Ｂ）前記文書内の用語の最大数が検討されるまで、前記文書の用語と前記候補用語のマスターリストとの比較を再実行する、
ことによって識別される、請求項２３に記載のコンピュータシステム。
【請求項２５】
前記トップランク付けされた文書の初期グループ内の文書の全部又は一部について、前記（Ａ）の比較ための命令によって候補用語が識別される回数が、前記文書と関連する前記ランク付けされた候補用語の各セットに含まれる、請求項２４に記載のコンピュータシステム。
【請求項２６】
前記（ｉｉｉ）に代って、前記重み付け関数によって候補用語に加えられる重みが、（ａ）前記候補用語を含み、且つ（ｂ）トップランクの文書にそれぞれ関連するランク付けされた候補用語のセット内の前記候補用語の平均位置に応じて決定されることを特徴とする請求項２３に記載のコンピュータシステム。
【請求項２７】
前記（ｉｉｉ）に代って、前記重み付け関数によって候補用語に加えられる重みが、前記候補用語の文字数に応じて決定されることを特徴とする請求項２３に記載のコンピュータシステム。
【請求項２８】
前記（ｉｉｉ）に代って、前記重み付け関数によって候補用語に加えられる重みが、前記候補用語を含む前記トップランク付けされた文書の初期グループ内の文書の位置に応じて決定されることを特徴とする請求項２３に記載のコンピュータシステム。
【請求項２９】
前記（ｉｉｉ）に代って、前記重み付け関数によって候補用語に加えられる重みが、前記候補用語を含むランク付けされた候補用語のセットに関連付けられた前記トップランクの文書の平均ランクに応じて決定されることを特徴とする請求項２３に記載のコンピュータシステム。
【請求項３０】
前記（ｉｉｉ）に代って、前記重み付け関数によって候補用語に加えられる重みが、ＴｅｒｍＣｏｕｎｔ＋ＴｅｒｍＰｏｓｉｔｉｏｎ＋ＲｅｓｕｌｔＰｏｓｉｔｉｏｎ＋ＴｅｒｍＬｅｎｇｔｈ＋ＱｕｅｒｙＩｎｃｌｕｓｉｏｎに応じて決定され、ここで、
ＴｅｒｍＣｏｕｎｔは、各トップランクの文書の上位部分に前記候補用語が現れる回数であり、
ＴｅｒｍＰｏｓｉｔｉｏｎは、前記候補用語が現れる各トップランクの文書内の前記候補用語の位置の関数であり、
ＲｅｓｕｌｔＰｏｓｉｔｉｏｎは、前記候補用語を含む前記トップランク付けされた文書の初期グループにおける文書の位置の関数であり、
ＴｅｒｍＬｅｎｇｔｈは、前記候補用語の文字数であり、
ＱｕｅｒｙＩｎｃｌｕｓｉｏｎは、前記受信クエリーの用語が前記候補用語内に存在する場合適用され、ＱｕｅｒｙＩｎｃｌｕｓｉｏｎは、前記受信クエリーの用語が前記候補用語内に存在しない場合に適用されないことを特徴とする請求項２３に記載のコンピュータシステム。
【請求項３１】
ＴｅｒｍＣｏｕｎｔ、ＴｅｒｍＰｏｓｉｔｉｏｎ、ＲｅｓｕｌｔＰｏｓｉｔｉｏｎ、ＴｅｒｍＬｅｎｇｔｈ、及びＱｕｅｒｙＩｎｃｌｕｓｉｏｎは、各々別々に重み付けされることを特徴とする請求項３０に記載のコンピュータシステム。
【請求項３２】
前記クエリー改良提案エンジンは更に、前記受信クエリーと前記候補用語のサブセットからの候補用語とを含む変更されたクエリーを使用して、任意選択的に前記受信クエリーを処理すること、選択すること、及び提示することの繰り返しを実行する請求項３０に記載のコンピュータシステム。
【請求項３３】
前記重み付け関数によって候補用語に加えられる重みが、次式に応じて決定されることを特徴とする請求項３２に記載のコンピュータシステム。
（ＴｅｒｍＣｏｕｎｔ*ｗ1）＋
（ＴｅｒｍＰｏｓｉｔｉｏｎ*（ｗ2＋（ＲｅｆｉｎｅｍｅｎｔＤｅｐｔｈ*ｗ2´）））＋
（ＲｅｓｕｌｔＰｏｓｉｔｉｏｎ*ｗ3）＋
（ＴｅｒｍＬｅｎｇｔｈ*（ｗ4＋（ＲｅｆｉｎｅｍｅｎｔＤｅｐｔｈ*ｗ4´）））＋
（ＱｕｅｒｙＩｎｃｌｕｓｉｏｎ*（ｗ5＋（ＲｅｆｉｎｅｍｅｎｔＤｅｐｔｈ*ｗ5´）））
ここで、ｗ1、ｗ2、ｗ3、ｗ4、ｗ5、ｗ2´、ｗ4´、及びｗ5´は別々の重みであり、ＲｅｆｉｎｅｍｅｎｔＤｅｐｔｈは前記受信クエリーに対して前記処理が行われた回数である。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図２】
【図３】
【図４】
【図５】
【図６】
【公開番号】特開２０１３−１０９７８１（Ｐ２０１３−１０９７８１Ａ）
【公開日】平成２５年６月６日（２０１３．６．６）
【国際特許分類】
【出願番号】特願２０１３−３１８９０（Ｐ２０１３−３１８９０）
【出願日】平成２５年２月２１日（２０１３．２．２１）
【分割の表示】特願２００６−５０７４５０（Ｐ２００６−５０７４５０）の分割
【原出願日】平成１６年３月２２日（２００４．３．２２）
【出願人】（５０１４３８４８５）ヤフー！ インコーポレイテッド (200)
【公開日】平成２５年６月６日（２０１３．６．６）
【国際特許分類】
【出願日】平成２５年２月２１日（２０１３．２．２１）
【分割の表示】特願２００６−５０７４５０（Ｐ２００６−５０７４５０）の分割
【原出願日】平成１６年３月２２日（２００４．３．２２）
【出願人】（５０１４３８４８５）ヤフー！ インコーポレイテッド (200)
[ Back to top ]