(57)【要約】  検索クエリのようなオリジナルのユーザ入力に基づいて修正/絞込みされたユーザ入力を生成するシステムおよび方法を開示する。本方法は、ローマ字ベースおよび/または中国語などの非ローマ字ベースの言語において実装されうる。本方法は、オリジナルのユーザ入力を受け取る段階と、その中にあるコアタームを識別する段階と、類似度行列に従ってオリジナル入力における(複数の)コアタームを他のタームに置き換えることで、潜在的な代替入力を決定する段階、および/または拡張/縮小テーブルに従って、オリジナル入力における単語シーケンスを他の単語シーケンスに置換する段階であって、一方のシーケンスは他のシーケンスの部分列である段階と、各潜在的代替入力の尤度を計算する段階と、所定の基準、例えば、代替入力の尤度が少なくともオリジナル入力の尤度であることに従って、最も有望な代替入力を選択する段階とを含む。
2008541233.tif 000002
【特許請求の範囲】
【請求項１】
代替のユーザ入力を提案するための方法であって、
オリジナルのユーザ入力を受け取る段階であって、前記入力は、少なくとも1つのコアタームを有する段階と、
前記オリジナルのユーザ入力における前記少なくとも1つのタームを識別する段階と、
(a)2つのターム間の類似度値を有する類似度行列に従って、前記オリジナルのユーザ入力における少なくとも1つのコアタームを他のタームに置き換える段階、および、(b)拡張/縮小テーブルに従って、前記オリジナルのユーザ入力における単語シーケンスを他の単語シーケンスに置換する段階であって、一方のシーケンスは、他のシーケンスの部分列であり、前記拡張/縮小テーブルは、タームのシーケンスに関連付けられた頻度値を有する段階のうちの少なくとも一方を行うことによって、少なくとも1つの潜在的代替ユーザ入力を決定する段階と、
前記潜在的代替ユーザ入力の尤度を計算する段階と、
所定の基準に従って、前記少なくとも1つの潜在的代替ユーザ入力から1つまたは複数の最も有望な代替ユーザ入力を選択する段階とを含む方法。
【請求項２】
前記1つまたは複数の最も有望な代替ユーザ入力を選択するための前記所定の基準は、前記選択された代替ユーザ入力の尤度が、少なくとも前記オリジナルのユーザ入力の尤度であることを含む、請求項1に記載の方法。
【請求項３】
前記オリジナルのユーザ入力は、オリジナルのユーザ検索クエリである、請求項1に記載の方法。
【請求項４】
前記オリジナルのユーザ入力は、非ローマ字ベースの言語である、請求項1に記載の方法。
【請求項５】
前記オリジナルのユーザ入力が、提案される代替ユーザ入力の事前計算済みキャッシュ内にあるかどうかを決定する段階と、
前記オリジナルのユーザ入力が前記事前計算済みキャッシュ内にあると決定されると、前記事前計算済みキャッシュ内に格納された事前計算された最も有望な代替ユーザ入力のうちの少なくとも1つを出力する段階とをさらに含む、請求項1に記載の方法。
【請求項６】
前記類似度行列は、コーパス、ユーザ入力ログ、およびユーザセッションデータのうちの少なくとも1つから生成される、請求項1に記載の方法。
【請求項７】
前記類似度行列は、前記コーパスにおける単語についての特徴ベクトルを構成し、それらの特徴ベクトルを使用して2つの単語間の類似度値を決定することによって生成される、請求項6に記載の方法。
【請求項８】
前記拡張/縮小テーブルは、ユーザ入力ログおよびユーザ入力データベースのうちの少なくとも一方から生成される、請求項1に記載の方法。
【請求項９】
前記拡張/縮小テーブルは、頻出単語シーケンスを決定し、句ではない単語シーケンスを除去し、カウントを頻度値としてタームシーケンスと関連付けることによって生成される、請求項8に記載の方法。
【請求項１０】
前記潜在的代替ユーザ入力の前記尤度を計算する段階は、(a)前記オリジナルのユーザ入力と前記潜在的代替ユーザ入力の間の関連性と、(b)前記潜在的代替ユーザ入力がユーザによって選択される確率と、(c)前記潜在的代替ユーザ入力についての位置のスコアとのうち少なくとも1つを決定する段階を含む、請求項1に記載の方法。
【請求項１１】
前記オリジナルのユーザ入力と前記潜在的代替ユーザ入力の間の前記関連性は、前記オリジナルの入力と前記潜在的代替ユーザ入力のアライメントされたターム間の相関値を使用して決定される、請求項10に記載の方法。
【請求項１２】
代替ユーザ入力を提案するためのシステムであって、
提案/絞込みサーバを含み、前記提案/絞込みサーバは、少なくとも1つのコアタームを有するオリジナルのユーザ入力を受け取り、前記オリジナルのユーザ入力における前記少なくとも1つのコアタームを識別し、(a)2つのターム間の類似度値を有する類似度行列に従って、前記オリジナルのユーザ入力における少なくとも1つのコアタームを他のタームに置き換えること、および、(b)拡張/縮小テーブルに従って、前記オリジナルのユーザ入力における単語シーケンスを他の単語シーケンスに置換することであって、一方のシーケンスは他のシーケンスの部分列であり、前記拡張/縮小テーブルはタームシーケンスと関連付けられた頻度値を有する置換することのうちの少なくとも一方を行うことによって少なくとも1つの潜在的代替ユーザ入力を決定し、前記潜在的代替ユーザ入力の尤度を計算し、所定の基準に従って、前記少なくとも1つの潜在的代替ユーザ入力から1つまたは複数の最も有望な代替ユーザ入力を選択し出力するように構成されたシステム。
【請求項１３】
前記オリジナルのユーザ入力は、オリジナルのユーザ検索クエリである、請求項12に記載のシステム。
【請求項１４】
前記オリジナルのユーザ入力は、非ローマ字ベースの言語である、請求項12に記載のシステム。
【請求項１５】
提案される代替ユーザ入力の事前計算済みキャッシュをさらに含み、前記提案/絞込みサーバは、さらに、前記オリジナルのユーザ入力が、前記事前計算済みキャッシュ内にあるかどうかを決定し、前記オリジナルのユーザ入力が前記事前計算済みキャッシュ内にあると決定されると、前記事前計算済みキャッシュ内に格納された事前計算された最も有望な代替ユーザ入力を出力するように構成された、請求項12に記載のシステム。
【請求項１６】
コーパス、ユーザ入力ログ、およびユーザセッションデータのうちの少なくとも1つをさらに含み、前記類似度行列は、前記コーパス、前記ユーザ入力ログ、および前記ユーザセッションデータのうちの少なくとも1つを使用して生成される、請求項12に記載のシステム。
【請求項１７】
前記提案/絞込みサーバは、さらに、前記コーパスにおける単語についての特徴ベクトルを構成し、それらの特徴ベクトルを使用して2つの単語間の類似度値を決定することによって、前記類似度行列を生成するように構成された、請求項16に記載のシステム。
【請求項１８】
ユーザ入力ログおよびユーザ入力データベースのうちの少なくとも一方をさらに含み、前記提案/絞込みサーバは、さらに、前記ユーザ入力ログおよび前記ユーザ入力データベースのうちの少なくとも一方から前記拡張/縮小テーブルを生成するように構成された、請求項12に記載のシステム。
【請求項１９】
前記提案/絞込みサーバは、さらに、頻出単語シーケンスを決定し、句ではない単語シーケンスを除去し、カウントを頻度値として各タームシーケンスと関連付けることによって、前記拡張/縮小テーブルを生成するように構成された、請求項18に記載のシステム。
【請求項２０】
前記提案/絞込みサーバは、(a)前記オリジナルのユーザ入力と前記潜在的代替ユーザ入力の間の関連性と、(b)前記潜在的代替ユーザ入力がユーザによって選択される確率と、(c)前記潜在的代替ユーザ入力についての位置のスコアとのうち少なくとも1つを決定することによって、前記潜在的代替ユーザ入力の前記尤度を計算するようにさらに構成された、請求項12に記載のシステム。
【請求項２１】
前記提案/絞込みサーバは、さらに、前記オリジナルの入力と前記潜在的代替ユーザ入力のアライメントされたターム間の相関値を使用することによって、前記オリジナルのユーザ入力と前記潜在的代替ユーザ入力の間の前記関連性を決定するように構成された、請求項20に記載のシステム。
【請求項２２】
コンピュータシステムと併せて使用するためのコンピュータプログラム製品であって、前記コンピュータプログラム製品は、コンピュータプロセッサ上で実行可能な命令が格納されたコンピュータ可読記憶媒体を含み、前記命令は、
少なくとも1つのコアタームを有するオリジナルのユーザ入力を受け取ることと、
前記オリジナルのユーザ入力における前記少なくとも1つのコアタームを識別することと、
(a)2つのターム間の類似度値を有する類似度行列に従って、前記オリジナルのユーザ入力における少なくとも1つのコアタームを他のタームに置き換えること、および、(b)拡張/縮小テーブルに従って、前記オリジナルのユーザ入力における単語シーケンスを他の単語シーケンスに置換することであって、一方のシーケンスは他のシーケンスの部分列であり、前記拡張/縮小テーブルは各タームシーケンスと関連付けられた頻度値を有する置換することのうちの少なくとも一方を行うことによって少なくとも1つの潜在的代替ユーザ入力を決定することと、
前記潜在的代替ユーザ入力の尤度を計算することと、
所定の基準に従って、前記少なくとも1つの潜在的代替ユーザ入力から1つまたは複数の最も有望な代替ユーザ入力を選択することとを含むコンピュータプログラム製品。
【請求項２３】
前記命令は、
前記オリジナルのユーザ入力が、提案される代替ユーザ入力の事前計算済みキャッシュ内にあるかどうかを決定すること、および、
前記オリジナルのユーザ入力が前記事前計算済みキャッシュ内にあると決定されると、前記事前計算済みキャッシュ内に格納された事前計算された最も有望な代替ユーザ入力を出力することをさらに含む、請求項22に記載のコンピュータプログラム製品。
【請求項２４】
前記類似度行列は、コーパス、ユーザ入力ログ、およびユーザセッションデータのうちの少なくとも1つから生成される、請求項22に記載のコンピュータプログラム製品。
【請求項２５】
前記類似度行列は、前記コーパスにおける単語についての特徴ベクトルを構成し、それらの特徴ベクトルを使用して2つの単語間の類似度値を決定することによって生成される、請求項24に記載のコンピュータプログラム製品。
【請求項２６】
前記拡張/縮小テーブルは、ユーザ入力ログおよびユーザ入力データベースのうちの少なくとも一方から生成される、請求項22に記載のコンピュータプログラム製品。
【請求項２７】
前記拡張/縮小テーブルは、頻出単語シーケンスを決定し、句ではない単語シーケンスを除去し、カウントを頻度値として各タームシーケンスと関連付けることによって生成される、請求項26に記載のコンピュータプログラム製品。
【請求項２８】
前記潜在的代替ユーザ入力の前記尤度を計算することは、(a)前記オリジナルのユーザ入力と前記潜在的代替ユーザ入力の間の関連性と、(b)前記潜在的代替ユーザ入力がユーザによって選択される確率と、(c)前記潜在的代替ユーザ入力についての位置のスコアとのうち少なくとも1つを決定することを含む、請求項22に記載のコンピュータプログラム製品。
【請求項２９】
前記オリジナルのユーザ入力と前記潜在的代替ユーザ入力の間の前記関連性は、前記オリジナルの入力と前記潜在的代替ユーザ入力のアライメントされたターム間の相関値を使用して決定される、請求項28に記載のコンピュータプログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、代替のユーザ入力を生成することに関する。より詳細には、検索クエリのようなオリジナルのユーザ入力に基づいて修正または絞込みされたユーザ入力を生成するためのシステムおよび方法を開示する。
【背景技術】
【０００２】
多くのユーザは、所与の検索セッション中に、しばしば、時には繰り返して彼らのオリジナルの検索クエリを修正するまたは絞り込む。例えば、ユーザは、所望の検索結果が生成されるまで、オリジナルの検索クエリを、より特定的な検索クエリ、より広範な検索クエリ、および/または代替の検索タームを使用する検索クエリに、修正することができる。ユーザ検索クエリの絞込みは、ローマ字ベースの言語、例えば、英語でのクエリ、ならびに、非ローマ字ベースの言語、例えば、中国語、日本語、およびコリア語(CJK)、タイ語などでのクエリについて行われる。一般に、ユーザは、オリジナルの検索クエリにより良い検索結果のセットがもたらされないとき、例えば、検索クエリが特定的すぎるまたは広範すぎる、あるいは検索クエリが不適切なタームを使用した場合に、ユーザの検索クエリを修正するまたは絞り込む。例えば、1つまたは複数の検索タームが曖昧であり、返されたドキュメントのいくつかが、ユーザの意図したものと異なる曖昧な検索タームの意味に関係するとき、および/または、ユーザが、検索タームの多くの側面のうちの所定の検索タームの1つの側面のみに関心があるとき、オリジナルのユーザ検索クエリは、多くの無関係の結果をもたらすことがある。また、ユーザが単に所与の検索タームに関係する概念を調べているときも、オリジナルのユーザ検索クエリは、多くの無関係の結果をもたらすことがある。
【０００３】
多くの検索エンジンは、ユーザのオリジナルの検索クエリに関係した提案される検索クエリのリストを提供する。例えば、ユーザのオリジナルの検索クエリが「Amazon」の場合、検索エンジンは、「Amazon.com」、「Amazon Rainforest」、および「Amazon River」などのような他の関係した検索クエリを提案することができる。検索クエリの提案は、CJKユーザなど非ローマ字ベースの言語のユーザのために特に有用でありうる。具体的には、非ローマ字ベースの言語は、一般に、文字の一組が大きく、各文字が、一般のローマ字ベースのキーボードを使用して何回かのキーストロークを必要としうるため、非ローマ字ベースの言語のユーザは、修正された検索クエリをタイプするよりも、提案される検索クエリをクリックまたは選択することを好むことになろう。例えば、多くの中国語ユーザは、ピンイン(表音式綴り)を使用して漢字を入力する。従来のピンイン入力システムでは、通常、ピンイン入力を変換して漢字セットの候補のリストを提供し、ユーザが、そこから所期の漢字のセットを選択することができる。明らかなように、この多段階の入力プロセスは、冗長かつ時間のかかるおそれがある。
【０００４】
検索クエリの提案は、ローマ字ベースの言語ユーザにも有用でありうる。多くの検索エンジン、例えば、Yahoo、Teoma、Alta Vista、Askjeeves、AllTheWeb、Baiduなどが、関連検索、クエリ絞込み、またはクエリクラスタリングの形態でそのような機能を提供している。
【発明の開示】
【課題を解決するための手段】
【０００５】
検索クエリのようなオリジナルのユーザ入力に基づいて修正または絞込みされたユーザ入力を生成するためのシステムおよび方法を開示する。本発明は、プロセス、装置、システム、デバイス、方法、あるいは、コンピュータ可読記憶媒体、またはプログラム命令が光学的または電子的通信回線を介して送られるコンピュータネットワークなどのコンピュータ可読媒体を含む、数多くの様式で実装することができることは理解されるべきである。コンピュータという用語は、一般に、携帯情報端末(PDA)、携帯電話、ネットワークスイッチのような計算機能力を有する任意のデバイスを指す。本発明のいくつかの独創的な実施形態を、以下に説明する。
【０００６】
本方法は、中国語など非ローマ字ベースの言語におけるクエリに適用することができる。本方法は、一般に、オリジナルのユーザ入力におけるコアタームを受け取り識別する段階と、類似度行列に従ってオリジナル入力における(複数の)コアタームを他のタームに置き換えることによって、潜在的な代替ユーザ入力を決定する段階、および/または拡張/縮小テーブルに従って、オリジナル入力における単語のシーケンスを他の単語シーケンスに置換する段階であって、一方のシーケンスは他のシーケンスの部分列である段階と、潜在的な代替ユーザ入力の尤度を計算する段階と、所定の基準、例えば、各選択された代替ユーザ入力の尤度が少なくともオリジナルのユーザ入力の尤度であることに従って、最も有望な代替ユーザ入力を選択する段階とを含むことができる。前記方法はまた、オリジナルのユーザ入力が、提案される代替ユーザ入力の事前計算済みキャッシュ内にあるかどうかを決定する段階と、そうである場合は、事前計算済みキャッシュ内に格納された事前計算された最も有望な代替ユーザ入力を出力する段階とを含むこともできる。
【０００７】
類似度行列は、コーパスを使用して生成されることができ、2つの類似したタームの間の類似度値を有することができる。このような2つの類似したタームには、「New York」と「Los Angeles」のように、非常に高い類似度を有することができるが、対応するターム(NewとLosならびにYorkとAngeles)の各対は高い類似度を有していない句のタームが含まれる。一実施形態では、類似度行列は、コーパスにおける単語についての特徴ベクトルを構成しそれらの特徴ベクトルを使用して2つの単語/句の間の類似度値を決定することによって、生成されうる。
【０００８】
拡張/縮小テーブルは、ユーザ入力データベースから生成されることができ、タームのシーケンスの各対に関連付けられた頻度値を有することができる。一実施形態では、拡張/縮小テーブルは、頻出単語シーケンスを決定し、句ではない単語シーケンスを除去し、カウントを頻度値として各タームのシーケンスと関連付けることによって生成されうる。単なる例示として、拡張/縮小テーブル内のエントリの例は、「The United States of America」と「United States」である。
【０００９】
潜在的な代替ユーザ入力の尤度は、(a)オリジナルのユーザ入力と潜在的な代替ユーザ入力の間の関連性、(b)潜在的な代替ユーザ入力がユーザによって選択される確率、および(c)潜在的な代替ユーザ入力に対する位置のスコアのうちの少なくとも1つを決定することによって計算されうる。特に、オリジナルのユーザ入力と潜在的な代替ユーザ入力の間の関連性は、オリジナルの入力と潜在的な代替ユーザ入力のアライメントされたターム間の相関値を使用して決定されうる。
【００１０】
他の実施形態では、代替ユーザ入力を提案するためのシステムが、一般に、提案/絞込みサーバを含み、提案/絞込みサーバは、少なくとも1つのコアタームを有するオリジナルのユーザ入力を受け取り、オリジナルのユーザ入力におけるコアタームを識別し、(a)2つのターム間の類似度値を有する類似度行列に従って、オリジナルのユーザ入力における少なくとも1つのコアタームを他のタームに置き換えること、および、(b)拡張/縮小テーブルに従って、オリジナルのユーザ入力における単語シーケンスを他の単語シーケンスに置換することであって、一方のシーケンスは他のシーケンスの部分列であり、拡張/縮小テーブルは各タームシーケンスと関連付けられた頻度値を有する置換することのうちの少なくとも一方を行うことによって潜在的な代替ユーザ入力を決定し、潜在的な代替ユーザ入力の尤度を計算し、所定の基準に従って最も有望な代替ユーザ入力を選択し出力するように構成されている。
【００１１】
さらに他の実施形態では、代替ユーザ入力を提案するためのコンピュータプログラム製品が、コンピュータシステムと併せて使用され、コンピュータプログラム製品は、コンピュータプロセッサ上で実行可能な命令が格納されたコンピュータ可読記憶媒体を含む。前記命令は、一般に、オリジナルのユーザ入力におけるコアタームを受け取り識別することと、類似度行列に従ってオリジナル入力における(複数の)コアタームを他のタームに置き換えることによって潜在的な代替ユーザ入力を決定すること、および/または、拡張/縮小テーブルに従ってオリジナル入力における単語シーケンスを他の単語シーケンスに置換することであって一方のシーケンスは他のシーケンスの部分列である置換することと、潜在的な代替ユーザ入力の尤度と任意選択で潜在的代替ユーザ入力の予測ユーザ満足度とを計算することと、所定の基準、例えば、各選択された代替ユーザ入力の尤度が少なくともオリジナルのユーザ入力の尤度であることに従って最も有望な代替ユーザ入力を選択することとを含むことができる。
【００１２】
システムおよび方法を実装するアプリケーションは、提案される代替入力を提供する、または検索エンジンなどのリモートサーバとインターフェースをとるように、検索エンジン上などのサーバサイト上に実装されても、またはユーザのコンピュータなどクライアントサイト上に例えばダウンロードされるように実装されもよい。
【００１３】
上記および他の本発明の特徴および利点は、本発明の原理を例示する以下の詳細な説明および添付の図面により詳細に示される。
【００１４】
本発明は、添付の図面と併せて以下の詳細な説明により容易に理解されよう。図面において、同じ参照番号は同種の構造要素を示す。
【発明を実施するための最良の形態】
【００１５】
検索クエリのようなオリジナルのユーザ入力に基づいて修正または絞込みされたユーザ入力を生成するためのシステムおよび方法を開示する。単に明瞭にするために、本明細書に提示される例は、一般に中国語のクエリ入力の観点から提示されることに留意されたい。しかし、絞込み/修正されたユーザ入力を提示するためのシステムおよび方法は、日本語、コリア語、タイ語など他の非ローマ字ベースの言語ならびにローマ字ベースの言語に対して同様に適用可能でありうる。また、絞込み/修正されたユーザ入力を提示するためのシステムおよび方法は、他の非クエリユーザ入力に対して同様に適用可能でありうる。以下の説明は、任意の当業者が本発明を作製し使用することを可能にするために提示される。単に例として特定の実施形態および用途の説明を示すが、当業者には様々な修正形態が容易に理解されよう。本明細書に定義される一般的原理は、本発明の趣旨および範囲から逸脱することなく他の実施形態および用途に適用することができる。したがって、本発明は、本明細書に開示の原理および特徴と一致する多数の代替形態、修正形態、および等価形態を含む最も広い範囲が与えられることになる。分かりやすさのため、本発明に関する技術分野で知られている技術資料に関する細部はついては、本発明を不必要に不明瞭にしないために詳細には説明しない。
【００１６】
検索クエリのようなオリジナルのユーザ入力に基づいて修正または絞込みされたユーザ入力を生成するためのシステムおよび方法は、ユーザのクエリ履歴、およびユーザクエリのターム間の関係に基づく。このシステムおよび方法は、新しい名前エンティティ(例えば、固有名詞や、映画、歌、および製品の名前など)を含む新しいタームとターム間の関係とを抽出するためのシステムおよび方法を含むことができる。本明細書に説明されるシステムおよび方法は、クエリ(または他のユーザ入力)の絞込みを生成する際に使用するのに適しているが、ニュース記事の分類、スペル訂正、メディア検索および区分など他の多くの用途にも適応されうる。多くのユーザにとって、最初の検索クエリは、最良の検索クエリではないことが多く、したがって、所与の検索セッション中に、ユーザは、時には何回も、検索クエリを修正または絞り込む。
【００１７】
図1Aは、ユーザ検索クエリ22のようなオリジナルのユーザ入力から提案される修正/絞込み済みの入力26を生成するための例示的システム20のブロック図である。システム20は、一般に、様々なデータソースから導出されうる確率を使用して提案される修正/絞込み済みのクエリ26を生成する提案/絞込みサーバ24を含む。様々なデータソースの例には、事前計算されたクエリ提案または絞込みのキャッシュを格納するオプションの提案/絞込みキャッシュ36が含まれる。提案/絞込みキャッシュ36は、提案/絞込みサーバ24のセッションパーサ24Cによって初期に生成されうる。他のデータソースは、提案/絞込みサーバ24の類似単語エクストラクタ24Aによって生成されうる類似度行列38、および、拡張/縮小テーブルジェネレータ24Bによって作成されうる拡張/縮小テーブル39とすることができる。類似度行列38および拡張/縮小テーブル39は、タームおよび/またはタームのシーケンスの間の関係をおおまかに近似する。システム20は、類似度行列38および/または拡張/縮小テーブル39を定期的に更新および/または再生成することができる。提案/絞込みサーバ24の類似単語エクストラクタ24A、拡張/縮小テーブルジェネレータ24B、およびセッションパーサ24Cは、図1Bから1Dを参照して以下でより詳細にそれぞれ説明される。
【００１８】
図1Bは、類似単語エクストラクタ24Aによって類似度行列38を生成するためのプロセスを示すブロック図である。図示のように、類似単語エクストラクタ24Aは、類似度行列38を生成するために様々なデータソースを利用することができる。類似単語エクストラクタ24Aによって利用されるデータソースの例には、ウェブコーパス30(例えば、ニュース、ウェブページ、およびアンカテキスト情報)のようなコーパス、クエリログ32に格納されるようなクエリおよび関連するユーザ選択、ならびに/または、各所与のセッションにおけるクエリの履歴を含むことができるセッションデータ34が含まれる。また、ウェブコーパス30が、アンカテキスト情報を含むことができる。クエリログ32は、ユーザクエリのログだけではなく、例えばユーザによる検索結果の選択、および、ユーザが検索結果に戻る前に選択された検索結果において留まった期間を含むこともできる。
【００１９】
図1Cは、拡張/縮小テーブルジェネレータ24Bによって抽出/縮小テーブル39を生成するためのプロセスを示すブロック図である。図示のように、拡張/縮小テーブルジェネレータ24Bは、抽出/縮小テーブル39を生成するためにデータソースとしてクエリログ32および/またはセッションデータ34を利用することができる。図1Dは、セッションパーサ24Cによって初期修正/絞込みキャッシュ36aを生成するためのプロセスを示すブロック図である。図示のように、セッションパーサ24Cは、初期修正/絞込みキャッシュ36aを生成するためにそれのデータソースとしてセッションデータ34を利用することができる。
【００２０】
図2Aおよび2Bは、提案/絞込みサーバ24によって行われうる例示的プロセスを示すフローチャートである。具体的には、図2Aは、図1Aに示されるシステム20によって実装されうる修正/絞込みユーザ入力キャッシュを生成するための例示的プロセス40を示すフローチャートである。ブロック41で、初期修正/絞込みキャッシュは、セッションパーサを使用してセッションデータから生成することができる。前述のように、セッションデータは、各所与のユーザの入力またはクエリセッションにおけるクエリの履歴を含むことができる。次いで、プロセス40は、ブロック42において、所定の数の最も一般的なユーザ入力(例えばクエリ)のそれぞれについて、ブロック43から48を含むループに入る。具体的には、ブロック43で、プロセスは、キャッシュにおける提案される修正/絞込み済みクエリの探索を行う。ブロック43における探索の結果、提案1, 2, ..., Mを導くことができる。
【００２１】
修正/絞込みキャッシュ内の各ユーザ入力またはクエリエントリは、所定の数N個の提案されるクエリのリストを含むことができる。したがって、提案M+1, M+2, ..., Nを生成するために、すなわち、各クエリについて提案されるクエリリストを満たすために、ブロック44から47も実行することができる。具体的には、ブロック44および45において、追加の提案される修正/絞込み済み(代替)クエリを生成するために、拡張されたクエリ束を(概念的に)構築することができる。ブロック44は、一般にターム置換クエリ修正/絞込み方法を表し、ブロック45は、一般に拡張/縮小クエリ修正/絞込み方法を表す。詳細には、ブロック44で、同様のタームの類似度行列を使用してオリジナルのクエリを類似のタームに置き換えることによって、拡張されたクエリ束を構築することができる。ターム置換は、オリジナルのクエリにおける(句のタームを含む)単語またはタームを同様の単語またはタームに置き換える。同様のタームには、同義語もしくは類義語(例えば、communityおよびneighborhood)、頭字語、および/または、同じ統語/意味範疇におけるターム(例えば、ToyotaとHonda、DellとHP、DVDとdigital camera、ならびに、NokiaとMotorola)が含まれうる。
【００２２】
ブロック45で、複合語の対の拡張/縮小テーブルを使用してオリジナルのクエリにおけるタームを追加/削除することによって、拡張されたクエリ束が、追加としてかつ/または代替として構築されうる。特に、拡張/縮小テーブルにおける各エントリは、一方の複合語が他方の部分列である一対の複合語であり、例えば、T1T2<=>T1T2T3、およびT4T5T6<=>T4T5である。中国語の複合語の対には、例えば、ShanghaiとShanghai City、ならびに、Televisionとtelevision setが含まれる。複合語の対には、曖昧なタームとそれらの曖昧でないコンテキスト(例えば、Amazonと、Amazon rain forestおよび/またはAmazon.com)、概念とそれらの絞込み(例えば、cellと、stem cellおよび/またはcell phone)、タームとそれらの属性、(例えば、コンピュータと、メモリ、ハードディスクドライブ、および/またはDVDドライブ)、ならびに、名前(例えば、人および会社などの名前)とそれらに対応する活動、仕事、製品など(例えば、Tom HanksとForrest Gumpのように俳優-映画、AppleとiPodのように会社-製品、Bill GatesとMicrosoftまたはCEOのように人-会社または肩書き、著者-本、歌手-歌など)が含まれうる。
【００２３】
拡張されたクエリ束が、様々な代替パスを含むように構築された後、ブロック46で、拡張されたクリア束における所定の数の最良のクエリに対するパスおよびスコアが、潜在的な提案されるクエリとして識別される。ブロック47で、スコアが少なくともオリジナルの一般的ユーザクエリのスコアである潜在的な提案されるクエリのみが、提案される修正/絞込み済みクエリとして提供されるように、オリジナルの一般的ユーザクエリのスコアを計算する。スコアは、所与のクエリ(オリジナルまたは潜在的な提案されるクエリ)が、ユーザにより選択または意図されたクエリである尤度を表すことができる。スコアが少なくともオリジナルの一般的ユーザクエリのスコアであるクエリは、修正/絞込みキャッシュ内に提案リストエントリを満たすために、提案される修正/絞込み済みクエリとして提供することができる。結果の提案されるクエリは、事前計算済み修正/絞込みクエリキャッシュに格納することができる。プロセス40またはブロック42から49を含むループは、修正/絞込みキャッシュを更新するために定期的に繰り返すことができることに留意されたい。
【００２４】
図2Bは、図1Aに示されるシステム20によって実装されうる提案される修正/絞込み済みのユーザクエリなどのユーザ入力を生成するための例示的プロセス50を示すフローチャートである。ブロック51で、ユーザクエリなどのユーザ入力が、受け取られる。判断ブロック52で、ブロック51で受け取られたオリジナルのユーザ入力が、オプションの事前計算済み修正/絞込みキャッシュにおけるエントリと比較されうる。判断ブロック52で、オリジナルのユーザクエリが提案/絞込みキャッシュ内にあると決定された場合、ブロック53で、サイズNのクエリ提案リストが、事前計算済み修正/絞込みキャッシュからのN個までの事前計算されたクエリ提案により、少なくとも部分的に満たされる。判断ブロック54で提案リストが充足されていると決定された場合、プロセス50は完了する。提案リストは、所定のサイズN、例えば10個の提案であっても、単一の最良の提案であってもよいことに留意されたい。一方、判断ブロック54で提案リストが充足されていないと決定された場合、プロセス50は、ブロック55および56に進む。同様に、判断ブロック52でオリジナルのユーザクエリが提案/絞込みキャッシュ内にないと決定された場合、プロセスは、やはりブロック55および56に進む。ブロック55から58は、図2Aを参照して先に述べたプロセス40のブロック44から47と同様であることに留意されたい。したがって、簡明にするため、それらが同様である範囲において、本明細書では説明を繰り返さない。
【００２５】
ブロック55および56で、拡張されたクエリ束が、提案される修正/絞込み済み(代替)クエリを生成するために(概念的に)構築される。拡張されたクエリ束が、様々な代替パスを含むように構築された後、ブロック57で、拡張されたクリア束における所定の数の最良のクエリに対するパスおよびスコアが、潜在的な提案されるクエリとして識別される。ブロック58で、スコアが少なくともオリジナルのユーザクエリのスコアである潜在的な提案されるクエリのみが、提案される修正/絞込み済みクエリとして提供されるように、オリジナルのユーザクエリのスコアを計算する。スコアが少なくともオリジナルのユーザクエリのスコアであるクエリは、提案リストまたは提案リストの残部を満たすために、提案される修正/絞込み済みクエリとしてユーザに提供することができる。図示されていないが、代わりに単一の最良のクエリを提供してもよい。また、オリジナルのユーザクエリおよび結果の提案されるクエリは、さらに事前計算済み修正/絞込みクエリキャッシュに格納されうる。
【００２６】
提案される修正/絞込み済みユーザ入力を生成するためのプロセス40および50の種々のブロックについて、図示し図2Aおよび2Bを参照して上記に説明したが、以下でさらに詳細に説明する。
【００２７】
図3は、例示的な拡張されたクエリ束の図を示す。図示のように、オリジナルのクエリは、様々なコアワードまたはタームT1, T2, T3, T4および非コアワードまたはタームs1, s2, s3を含むことができる。例えば、中国語のクエリ「URL's of sina」において、コアタームまたはエンティティは、「URL's」よりはむしろ「sina」である。非コアタームは、一般に、ストップワードも含む。一般に、ストップワードは、例えば、ウェブコーパスなどのコーパスにおいて、30個の最も頻繁に出現する中国語の単語または100個の最も頻繁に出現する英語の単語として定義される。
【００２８】
オリジナルのクエリのコアエンティティが識別された後、1つまたは複数のクエリ修正または絞込み方法、例えば、タームの置換および/または拡張/縮小を、拡張されたクエリ束に適用することができる。前述のように、ターム置換は、コアエンティティに類似し(例えば、同義語または類義語)、例えば類似度行列を使用して識別されうる、単語および/またはタームの置換を指している。単に例示のために、図3は、拡張されたクエリ束が、タームT1をT1'またはT1''に置き換え、かつ/または、タームT4をT4'に置き換えることによって、構築することができることを示す。
【００２９】
また前述のように、拡張/縮小は、例えば複合語の拡張/縮小テーブルを使用して、コアエンティティをオリジナルのクエリに追加すること、および/または、コアエンティティのいくつかをオリジナルのクエリから削除することを指す。単に例示として、複合語の拡張/縮小テーブルは、対の複合語T1T2とT1T2T5のテーブルエントリを含むことができ、それにより、図3内のオリジナルのクエリにおける複合語T1T2は、拡張されたクエリ束上にさらに構築されるように複合語T1T2T5に置き換えることができる(すなわち、新しいタームT5を追加する)。同様に、複合語の拡張/縮小テーブルはまた、対の複合語T2T3T4とT3T4のテーブルエントリを含むことができ、それにより、図3内のオリジナルのクエリにおける複合語T2T3T4は、拡張されたクエリ束上にさらに構築されるように複合語T3T4に置き換えることができる(すなわち、コアエンティティT2を削除する)。
【００３０】
類似タームの類似度行列を生成するための1つの例示的な方法を、図4から7を参照してより詳細に説明する。図4は、提案される修正/絞込み済みクエリをクエリタームの置換によって生成する際に使用するための類似度行列を構成するための例示的プロセス60示すフローチャートである。類似度行列は、単語またはタームwの各対の間の分布単語類似度の行列とすることができる。各単語wの分布単語類似度は、コーパス、例えばウェブページ内の各単語wごとに特徴ベクトルを構成し、単語の各対の間の類似度を、それぞれの特徴ベクトルの間の角度の余弦として決定することにより得ることができる。単語またはタームの特徴ベクトルは、単語またはタームのすべての出現における周囲の単語を含むことができる。
【００３１】
特徴ベクトルおよび類似度行列の構成の一例を、図4を参照して提示するが、他の様々な特徴ベクトルおよび類似度行列構成方法も同様に採用されうる。具体的には、ブロック62で、ウェブコーパスなどのコーパスにおける各単語/タームwの特徴ベクトルが、特徴ベクトルの各特徴fについてのカウントとともに構成される。単語/タームwの特徴は、第1の非ストップワードまで単語/タームwの前および後に出現する単語を含むことができる。単に例示として、文「Because communities assess at different percentages of fair market value, the only way to compare tax rates between communities is by using equalized rate」が与えられたとすると、(コミュニティは異なるパーセンテージの適正市場価格において課税するため、コミュニティ間の税率を比較する唯一の方法は、平準化されたレートを使用することによる)単語communitiesの特徴およびそれらの対応する共起カウントは、図5の表のように挙げられる。所与の単語について異なる形態を有する言語、例えば、「community」と「communities」のように単数と複数や、「walk」、「walking」、および「walked」のように異なる時制を有する言語では、システムは、異なる形態の単語を、おおまかには同様のタームであるが別個の単語として取り扱うことに留意されたい。このような所与の単語の異なる形態の取扱いは、典型的には例えば中国語の場合などのようにそうした区別を持たない言語に関しては該当しないことがある。さらに、プレフィックス「L」または「R」を有する特徴はそれぞれ、単語wの左または右に出現する単語であることにも留意されたい。この実施形態では、単語wの所与のインスタンスの左および右の各側にある1つまたは複数の特徴のカウントの合計が1である。例えば、単語「communities」の第1のインスタンスにおいて、左および右の各特徴は、1のカウントが割り当てられる。さらに、単語「communities」に隣接する1つまたは複数のストップワード、例えば、「between」、「is」、および「by」があるとき、単語「communities」の所与のインスタンスの各側についての特徴のカウントは、均等に分割され、したがって小数として計算される。単語「communities」の第2のインスタンスでは、左の特徴が2つあり、各左の特徴に、0.5のカウントが割り当てられる。同様に、単語「communities」の第2のインスタンスでは、右の特徴が2つあり、各右の特徴に、0.33のカウントが割り当てられる。
【００３２】
図4を再び参照すると、ブロック64で、特徴ベクトルにおける各特徴fの値が、単語wと特徴fの間のポイントワイズ相互情報量MIとして決定することができる。ポイントワイズ相互情報量MIの値が使用される理由は、頻繁に出現する単語、例えばストップワードは、より多いカウントを有する傾向があるが、こうした単語は意味的に無効であることが多いからである。したがって、特徴のカウントが特徴の重要性の良い指標となりえないので、単語wと特徴fの間のポイントワイズ相互情報量MI(w, f)は、特徴fの値として使用されうる。ポイントワイズ相互情報量MI(w, f)は、それらが独立の場合に共起する、wとfの観測された同時確率P(w, f)、wの期待確率P(w)、およびfの期待確率P(f)の間の比の対数として定義される。
【００３３】
【数１】
2008541233.tif 000003
【００３４】
上式で、特徴P(f)と単語P(w)の確率(例えば、相対度数)は、例えば、コーパスにおけるそれらの各確率を使用して決定することができる。図6は、単に例として、ウェブコーパスから生成されるターム「communities」についての例示的な特徴および対応する確率を列挙するテーブルである。図6に示される特徴ベクトルテーブルは、単語「communities」の特徴のサブセット、ならびに、特徴と単語「communities」の間の確率および相互情報量を列挙する。特徴ベクトルは、かなり大きくなりうることに留意されたい。例えば、コーパスから抽出される単語communitiesの特徴のフルセットは、およそ2000個の要素を含む。
【００３５】
図4を再び参照すると、ブロック66で、2つの単語または句w1とw2の間の類似度すなわち値simは、特徴ベクトルにおける特徴の値を使用して、それらの特徴ベクトルの間の角度の余弦として決定することができる。具体的には、2つのタームまたは単語w1とw2の間の類似度simは、次のように定義される。
【００３６】
【数２】
2008541233.tif 000004
【００３７】
上式で、w1およびw2の特徴ベクトルはそれぞれ、(f11, f12 ..., f1n)および(f21, f22 ..., f2n)によって表される。
【００３８】
次いでブロック68で、類似度行列が、タームについて単語の各対ごとの類似度値から構成され、クエリタームを同様のタームに置き換えることによって提案される修正/絞込み済みクエリを生成する際に使用されうる。特に、類似度値は、例えば、潜在的な提案クエリに対するスコアを決定する際に使用されうる。類似度行列は、定期的に再計算されうる、かつ/または、新しく識別されたタームなどのタームについての類似度値が、行列に追加されうることに留意されたい。図7は、提案される修正/絞込み済みクエリを生成するために同様のタームを置き換える際に利用されうる例示的類似度行列である。
【００３９】
ターム置換クエリ修正/絞込み方法を適用する際に使用するための類似度行列を生成するための例示的方法を提示したが、ここで、拡張/縮小クエリ修正/絞込み方法を適用する際に使用するための複合語の対の拡張/縮小テーブルを生成するための例示的方法を、図8から11を参照してより詳細に以下に説明する。図8は、複合語の対の抽出/縮小テーブルを構成するための例示的プロセス70を示すフローチャートである。前述のように、拡張/縮小テーブルにおける各エントリは、複合語の一対であり、その一方の複合語は他方の部分列であり、したがって、クエリが、拡張/縮小テーブル内のエントリにおける複合語の対の一方の複合語を含む場合、その複合語は、束を拡張する際に、複合語の対のエントリの他方の複合語で置換することができるようになされている。理想的には、抽出/縮小テーブル内の各複合語は、意味のある句であるべきである。単に例として、複合語の対は、ShanghaiとShanghai City、または、televisionとtelevision setにすることができる。前述のように、複合語の対には、例えば、曖昧なタームとそれらの曖昧でないコンテキスト(例えば、AmazonとAmazon rain forest)、人の名前とそれらの対応する活動、タームの属性、概念の絞込み、俳優、著者、製品、人の地位などが含まれうる。
【００４０】
ブロック71で、クエリログ(またはユーザ入力の他のデータベース)におけるクエリを、クエリに対する全体的確率を最大限にする単語シーケンスに区分化することができる。具体的には、中国語の単語はスペースまたは他の区切りで明示的に線引きする必要がなく、したがって、クエリが、区切りなしの中国語文字の列となりうるので、文字のシーケンスを単語のシーケンスに区分化するためにセグメンタを利用することができる。単語のシーケンスは、単語の確率の積が、文字のシーケンスのすべてのあり得るセグメントのうちで最大となるようにすることができる。明らかなように、ブロック71は、隣接単語間に明白な線引きがある英語などの特定の言語では行われる必要がない。
【００４１】
複合語/句を識別するために、ブロック72で、頻出の単語シーケンスまたはnグラム(nシーケンスのシーケンス)を識別する。また、ブロック72では、任意の長さの頻出単語シーケンスを識別するために、単語シーケンス中のすべての隣接する対の単語が頻出のnグラムである単語シーケンスについてのカウントを取る。頻出単語シーケンスは、複合語であってもそうでなくてもよい。例えば、頻出単語シーケンスのうちのいくつかが、複合語であり、他の単語シーケンスは、句ではないまたは非複合語のシーケンスでありうる。
【００４２】
ブロック73で、句ではないシーケンスが、複合語/句が、最小数のクエリの始めおよび終わりに出現するように(ただし同じクエリ内である必要はない)求めることによって識別される。クエリの最小数は、1以上の任意の数とすることができるが、通常は、1よりかなり大きく、例えば、50または100である。
【００４３】
ブロック74で、ウェブコーパスなどのコーパスにおけるnグラムごとの特徴ベクトルが、特徴ベクトルにおける各特徴fについてのカウントとともに構成される。ブロック75で、特徴ベクトルにおける各特徴fの値は、nグラムと特徴fの間のポイントワイズ相互情報量MIとして決定することができる。ブロック76で、2つのnグラムの間の類似度すなわち値simは、特徴ベクトルにおける特徴の値を使用して、それらの特徴ベクトルの間の角度の余弦として決定することができる。ブロック74、75、および76は、図4を参照して上述したプロセス60のブロック62、64、および66とそれぞれ同様であることに留意されたい。したがって、簡明にするため、それらが同様である範囲において、本明細書では説明を繰り返さない。
【００４４】
次いでブロック77で、拡張/縮小テーブルを、一方の複合語が他方の部分列である対の複合語として構成することができる。また、複合語のカウントを決定して拡張/縮小テーブルに格納することもできる。
【００４５】
図9は、提案される修正/絞込み済みクエリを生成するためにクエリにおける複合語を置換する際に使用するための拡張/縮小テーブルにおけるいくつかの例示的エントリを示すテーブルである。図示のように、拡張/縮小テーブルの各行は、2つの複合語または単語シーケンスを含み、そのうち一方の複合語は他方の部分列である。また、各複合語は、カウント(または他の頻度値)に関連付けられ、カウントは、例えば、クエリログまたは何らかの他のユーザ入力データベースより決定することができる。カウントは、カットオフとして、データベースのサイズを小さくするために使用することができ、かつ/または、例えばログ(カウント)の使用によって、タームまたは複合語に対する重みを決定するために、少なくとも部分的に使用することができる。図2Aおよび2Bを参照して前述したように、クエリ束が、タームを置き換えることによって、かつ/または、オリジナルのクエリにおけるタームを追加/削除することによって拡張されると、N個の最良のクエリのパスおよびスコアが、潜在的な提案されるクエリとして拡張された束から決定される。図10は、提案される修正/絞込み済みクエリのスコア、例えば、拡張されたクエリ束におけるパスを決定するための例示的プロセス80を示すフローチャートである。
【００４６】
クエリ提案の決定は、現在のクエリセッションにおける先行クエリに基づく予測問題として取り扱うことができる。現在の検索セッションにおいてクエリの履歴Q1, Q2, ..., Qn-1が与えられたとすると、ユーザが最も選択する見込みがある次のクエリQnは何であるかに関して予測を行うことができる。提案または予測される次のクエリQnは、現在のセッションにおけるクエリの履歴Q1, Q2, ..., Qn-1に関連するだけでなく、良好な検索結果をもたらすべきである。検索結果の良好さの程度の測定は、例えば、クリック位置(ユーザが選択する検索結果の位置)およびクリック期間(ユーザが選択された検索結果のページに留まる期間)の関数とすることができる。
【００４７】
一実施形態では、潜在的な提案されるクエリに対するスコアは、以下の目的関数Fの値として決定することができる。
F(Q, Q1, ..., Qn-1)=Rel(Q, Q1, ..., Qn-1)*Click(Q)*Position(Q)
ただし、
Rel(Q, Q1, ..., Qn-1)は、クエリの履歴Q1, ..., Qn-1と候補の提案されるクエリQとの間の関連性であり、
Click(Q)は、候補の提案されるクエリQがユーザによって選択される確率であり、
Position(Q)は、クリックされることになる候補の提案されるクエリQに対する検索結果の位置である。
【００４８】
図2を参照して前述したように、1つまたは複数の提案または予測される次のクエリQが、ユーザに提供されうる。したがって、最良のN個の提案の次のクエリ(例えば、拡張されたクエリ束におけるパス)は、最も高い目的関数値を有するN個のクエリであり、そして、最良の(例えば、最も有望な)提案される次のクエリは、下記の目的関数Fの値を最大化するクエリとして表現されうる。
Qn=ArgMax_Q{F(Q, Q1, ..., Qn-1)}
【００４９】
図10のフローチャートに、各潜在的提案または予測される次のクエリQ90に対するスコアの決定が示される。ブロック82で、現在のセッションにおけるユーザクエリの履歴Q1, ..., Qn-1と予測されるクエリQとの間の関連性Rel(Q, Q1, ..., Qn-1)が、クエリにおけるアライメントされたタームの相関を使用して決定される。具体的には、関連性関数Relを推定するために、オリジナルのクエリQにおけるタームまたはコアエンティティが識別される。コアエンティティ間の相関を使用して、2つのクエリQとQ'の間の関連性Rel(Q, Q')を、それらのコアエンティティの相関から導出することができる。具体的には、関連性Rel(Q, Q')は、以下のように表現することができる。
Rel(Q, Q')=Max_f Prod_{i=1}^k Cor(Ti, Ti')*w(Ti)
ただし、
アライメント関数f=f(T1, T2, ..., Tk, T1', T2', ..., Tk')は、関連するクエリQとQ'のタームをマップし(例えば、図11に例が示される、{T1, ..., Tk, e} と{T1', ..., Tk', e}の間のマッピング)、
Cor(Ti, Ti')は、タームTi, Ti'間の相関であって実数のベクトルであり、
Q=T1, T2, ..., Tk(任意のタームTiが空のタームeでありうるクエリQにおけるコアエンティティ)であり、
Q=T1', T2', ..., Tk'(任意のタームTi'が空のタームeでありうるクエリQ'におけるコアエンティティ)であり、
W(Ti)は、タームTiの重要度であって、例えば、Tiに対するTF/IDFであり、この場合、TFは、ターム頻度(例えば、タームのカウント)を表し、IDFは、反転したドキュメント頻度を表す。
【００５０】
ブロック84で、クエリQがユーザによって選択される確率Click(Q)が、例えば、クリック期間または正規化されたクリック期間から決定される。ブロック86で、予測されるクエリQについての位置のスコアPosition(Q)が、例えば、クリック位置、正規化されたクリック位置、または反転されたクリック位置から決定される。最後にブロック88で、潜在的な提案または予測される次のクエリQについての目的関数Fの値が、上記のブロック82、84、および86の結果から決定される。
【００５１】
2つのクエリ間の関連性を決定する際に使用される相関値Cor(T, Ti')の決定について、図12を参照してより詳細に説明する。具体的には、図12は、タームまたはコアエンティティの対T, T'の間の相関値を生成するための例示的プロセス90を示すフローチャートである。ブロック92で、新しいコアエンティティを、相互情報量を使用して、コーパス、例えばウェブページ、およびユーザクエリから識別することができる。ブロック92の一例示的実装形態では、Motorolaがエンティティであって、コーパス内に「Motorola announced」、「Motorola cell phone」、および「buy Motorola」に加えて、「Nokia announced」、「Nokia cell phone」、および「buy Nokia」もある場合、Nokiaもエンティティとして識別される。既製の辞書により当初のコアエンティティを提供できるが、多くの新しいコアエンティティが用語集にしばしば取り込まれることに留意されたい。新しいコアエンティティの例には、例えば人および会社の名前などの固有名、ならびに、製品モデルや映画および歌の題名など他の様々な新しい単語および句が含まれる。
【００５２】
ブロック94で、コアエンティティの対T, T'の間の相関値を、例えば、クエリログ、ウェブページ、およびアンカテキストを使用して決定することができる。2つのコアエンティティT1とT2の間の相関は、以下のように実数のベクトルの関数として定義することができる。
Cor(T1, T2)=f(w1, w2, ..., wn)
ただし、w1, w2, ..., wnは、いくつかの所定の関係の重みである。所定の関係の例として、(1)同義語、頭字語、および反意語、(2)複合句、例えば、Shanghai対Shanghai City、television対television machine、(3)同じ統語/意味範疇におけるターム、例えば、ToyotaとHonda、(4)曖昧なタームとそれらの曖昧でないコンテキスト、(5)人の名前とそれらの対応する活動、例えば、Oprahとtalk show host、(6)タームの属性、例えば、computerとmemory、(7)概念の絞込み、例えば、Amazonと、Amazon River、Amazon Rain Forest、およびAmazon.com、(8)英語-俳優、本-著者、会社-製品、人物-地位など、例えば、Tom HanksとForrest Gump、およびBill GatesとCEO、が挙げられる。
【００５３】
ブロック96で、相関ベクトルCor(T1, T2)の値は、[0-1]に正規化することができる。
【００５４】
修正または絞込みされたユーザ入力を生成するためのシステムおよび方法は、ユーザが使用する見込みのある、かつ/または、ユーザが選択する見込みのある最上位の結果を生成する、クエリを提示することができる。このシステムおよび方法は、2つのクエリの間の相関を定量的に測定する。明らかなように、2つのクエリは、どんな共通のタームも同義語さえも有する必要がない。例えば、歌「Now and Forever」のmp3ファイルに対する(例えば、中国語での)オリジナルのクエリ「Now and Forever' mp3」に関係したクエリには、「CoCo Lee」(この歌の歌手)とともに、例えば、同じアーティストによる他の歌またはアルバムも含まれる。したがって、提案されるクエリは、オリジナルのクエリの単なる拡張ではなく、より良い検索結果、例えば、ユーザがより選択する見込みがある検索結果を有するクエリである。一実施形態では、提案されるクエリは、オリジナルのクエリが短く曖昧である場合に、クエリ語義曖昧性解消を達成するクエリを含むことができる。他の例では、提案されるクエリは、オリジナルのクエリが、長くかつ/または互いに排他的なタームを含みうる場合に、オリジナルのクエリをより短いクエリに分割するクエリを含むことができる。
【００５５】
本発明の例示的実施形態が本明細書に説明され例示されているが、それらは単に例示であって、本発明の趣旨および範囲から逸脱することなく修正が可能であることは理解されよう。したがって、本発明の範囲は、修正されうる添付の特許請求の範囲においてのみ限定されるものであり、各請求項は、明確に、本発明の実施形態として本明細書の具体的な実施形態の説明に組み込まれる。
【図面の簡単な説明】
【００５６】
【図１Ａ】ユーザ検索クエリなどの提案される修正/絞込み済みのユーザ入力を生成するための例示的システムを示すブロック図である。
【図１Ｂ】提案-絞込みサーバの類似単語エクストラクタによって類似度行列を生成するためのプロセスを示すブロック図である。
【図１Ｃ】提案-絞込みサーバの拡張/縮小テーブルジェネレータによって抽出/縮小テーブルを生成するためのプロセスを示すブロック図である。
【図１Ｄ】提案-絞込みサーバのセッションパーサによって初期修正/絞込みキャッシュを生成するためのプロセスを示すブロック図である。
【図２Ａ】図1Aに示されるシステムによって実装されうる修正/絞込みユーザ入力キャッシュを生成するための例示的プロセスを示すフローチャートである。
【図２Ｂ】図1Aに示されるシステムによって実装されうるユーザクエリなどの提案される修正/絞込み済みのユーザ入力を生成するための例示的プロセスを示すフローチャートである。
【図３】オリジナルのユーザクエリをパースすることによって生成される例示的クエリ束を示す図である。
【図４】提案される修正/絞込み済みクエリをクエリタームの置換によって生成する際に使用するための類似度行列を構成するための例示的プロセスを示すフローチャートである。
【図５】例示的テキストから生成されるターム「communities」についての特徴および対応するカウントを列挙するテーブルを示す図である。
【図６】コーパスから生成されるターム「communities」についての例示的な特徴および対応するカウントを列挙するテーブルを示す図である。
【図７】提案される修正/絞込み済みクエリを生成するためにタームを置き換える際に使用するための例示的類似度行列を示す図である。
【図８】クエリにおける複合語を置換することによって提案される修正/絞込み済みクエリを生成する際に使用するための複合語の対の抽出/縮小テーブルを構成するための例示的プロセスを示すフローチャートである。
【図９】提案される修正/絞込み済みクエリを生成するためにクエリにおける複合語を置換する際に使用するための拡張/縮小テーブルにおけるいくつかの例示的エントリを示すテーブルである。
【図１０】提案される修正/絞込み済みクエリのスコアを決定するための例示的プロセスを示すフローチャートである。
【図１１】タームの2つのクエリQとQ'のアライメントマッピングの例を示す図である。
【図１２】検出された新しいエンティティについての相関値を生成するための例示的プロセスを示すフローチャートである。
【符号の説明】
【００５７】
22    ユーザ検索クエリ
24    提案/絞込みサーバ
24A    類似単語エクストラクタ
24B    拡張/縮小テーブルジェネレータ
24C    セッションパーサ
26    修正/絞込み済みのクエリ
30    ウェブコーパス
32    クエリログ
34    セッションデータ
36    修正/絞込みキャッシュ
36a    初期修正/絞込みキャッシュ
38    類似度行列
39    拡張/縮小テーブル
【図１Ａ】
2008541233.tif 000005
【図１Ｂ】
2008541233.tif 000006
【図１Ｃ】
2008541233.tif 000007
【図１Ｄ】
2008541233.tif 000008
【図２Ａ】
2008541233.tif 000009
【図２Ｂ】
2008541233.tif 000010
【図３】
2008541233.tif 000011
【図４】
2008541233.tif 000012
【図５】
2008541233.tif 000013
【図６】
2008541233.tif 000014
【図７】
2008541233.tif 000015
【図８】
2008541233.tif 000016
【図９】
2008541233.tif 000017
【図１０】
2008541233.tif 000018
【図１１】
2008541233.tif 000019
【図１２】
2008541233.tif 000020
【国際調査報告】
2008541233.tif 000021
2008541233.tif 000022
2008541233.tif 000023
2008541233.tif 000024