表意文字と表音文字とを有する言語のための自動補完方法およびシステム
【課題】クエリの入力を高速化するシステムおよび方法を提供する。
【解決手段】表意文字と表音文字とを有する言語のための、クエリ補完を提案するための方法であって、０以上の表意文字と、それに続く少なくとも１つの表音文字とを含む部分クエリを、検索要求者から受信するステップと、ランク付け基準に従って順序付けされた予測クエリの組の１つを、前記部分クエリから予測するステップであって、前記組は表意文字を含む、ステップと、順序付けされた予測クエリの前記組を、前記検索要求者に伝えるステップとを含む。
【解決手段】表意文字と表音文字とを有する言語のための、クエリ補完を提案するための方法であって、０以上の表意文字と、それに続く少なくとも１つの表音文字とを含む部分クエリを、検索要求者から受信するステップと、ランク付け基準に従って順序付けされた予測クエリの組の１つを、前記部分クエリから予測するステップであって、前記組は表意文字を含む、ステップと、順序付けされた予測クエリの前記組を、前記検索要求者に伝えるステップとを含む。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、コンピュータネットワーク（例えば、コンピュータシステムの分散システム）内の文書を検索する（locating）ための検索エンジンの分野に関し、特に、非表音記号（non-phonetic symbols）を含む言語でのユーザの要求を予測することによって、所望の検索を高速化するためのシステムおよび方法に関する。
【背景技術】
【０００２】
検索エンジンは、ワールドワイドウェブ（ＷＷＷ）上の文書、またはインターネットのコンピュータ上に記憶された文書などの、大規模な文書データベース内の文書を検索するための強力なツールを提供する。文書は、ユーザによって発行される検索クエリに応答して検索される。検索クエリは、１つまたは複数の検索タームからなっていてもよい。
【０００３】
クエリを入力する一方法においては、ユーザは、すべての検索タームが入力されるまで検索タームを連続的に追加することによって、クエリを入力する。クエリのすべての検索タームが入力されたことをユーザが合図すると、クエリは検索エンジンに送信される。例えば、キーボード上のエンターキーを押すことによって復改文字を入力すること、または、グラフィカルユーザインタフェース上の「検索」ボタンをクリックすることなどによる、クエリの完成を合図する代替の方法を、ユーザは有していてもよい。クエリが検索エンジンによって受信されたら、検索エンジンは、検索クエリを処理し、検索クエリに応答して文書を検索し、文書のリストをユーザに返す。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
アルファベット文字体系（alphabetic writing systems）に主として基づく言語ではない言語においては、多くの場合、クエリの言語要素を作成するために、キーボードから文字列が入力される。この方法によるクエリの入力は、時間がかかる可能性がある。
【０００５】
クエリは、一般に、クエリが完成したことをユーザが合図するまで、検索エンジンに送信されないため、ユーザが全ての検索クエリ（the full search query）を完成させている間に時間が経過する。このプロセスを高速化するシステムおよび方法を有することが望ましい。
【課題を解決するための手段】
【０００６】
一実施形態においては、表意文字と表音文字（ideographs and phonetic characters）とを有する言語のためのクエリ補完（query completion）を提案する方法は、検索要求者から部分クエリを受信するステップを含む。部分クエリは、完全なクエリ（complete query）の部分である。１つまたは複数の表意文字を有する少なくとも１つの文字列を含む、予測クエリの組（a set of predicted queries）が、予測され、ランク付け基準に従って順序付けされる。順序付けされた予測クエリの組は、検索要求者に伝えられる。
【０００７】
検索要求者は、予測クエリの順序付けされた組から、それぞれのクエリを選択してもよく、次に、クエリの補完を指示してもよい。検索エンジンは、クエリを処理して、検索結果の組を生成する。あるいは、検索要求者は、完全なクエリが入力されるまで、または、予測クエリの新しい組が送信されて検索要求者に提示されるまで、クエリ情報の入力を継続してもよい。
【０００８】
本発明の前述の実施形態、および追加の実施形態は、以下の、本発明のさまざまな態様の詳細な説明を、図面と組み合わせた場合の結果として、より明確に理解される。複数の図面にわたる同様の参照番号は、対応する部分を意味している。
【図面の簡単な説明】
【０００９】
【図１】本発明の一部の実施形態による、クエリを予測するためのプロセスを示す。
【図２】本発明の一部の実施形態による、検索システムのブロック図を示す。
【図３】本発明の一部の実施形態による、検索アシスタントのプロセスを示す。
【図４】本発明の一部の実施形態による、クエリ入力を受信し、それに対する応答を作成するためのプロセスを示す。
【図５】本発明の一部の実施形態による、フィンガープリント−テーブルマップの作成および使用に関連する情報の流れを示す。
【図６】本発明の一部の実施形態による、入力文字列の関連性を示す。
【図７】本発明の一部の実施形態による、履歴クエリを処理するためのプロセスを示す。
【図８】本発明の一部の実施形態による、履歴クエリの処理において使用される例示的テーブルの部分を示す。
【図９】本発明の一部の実施形態による、サフィックスを使用したクエリ補完テーブルに関連するデータ構造を示す。
【図１０】本発明の一部の実施形態による、例示的クエリ補完テーブルの部分を示す。
【図１１】本発明の一部の実施形態による、例示的スクリーンショットを示す。
【図１２】本発明の一部の実施形態の実装に適した、検索エンジンを示す。
【図１３】本発明の一部の実施形態の実装に適した、クライアントを示す。
【図１４】本発明の一部の実施形態による、表意文字と表音文字とを含む履歴クエリを処理するためのプロセスを示す。
【図１５】本発明の一部の実施形態による、選択された表意文字のための複数の音声表示を示す。
【図１６】本発明の一部の実施形態による、表音文字と表意文字とを含む例示的クエリ補完テーブルの部分を示す。
【発明を実施するための形態】
【００１０】
本発明の一実施形態においては、ユーザが完全なクエリの入力を完了する前に、ユーザのクエリの部分が検索エンジンに送信される。検索エンジンは、クエリの送信された部分を使用して、ユーザの最終的なクエリを予測する。これらの予測は、ユーザに送り返される。予測のうちの１つが、ユーザの意図するクエリである場合、ユーザは、クエリの入力を完了することなく、その予測クエリを選択することができる。一部の実施形態では、選択されたクエリが検索エンジンに送信され、検索エンジンは、選択されたクエリに対応するクエリ結果の組を返す。
【００１１】
図１は、クライアントシステム１０４と検索エンジン１０６とを含む、本発明の例示的実施形態を示す。ユーザが検索クエリを入力するとき、ユーザの入力は、クライアントシステムによって監視される（１０８）。ユーザが検索クエリの完成を合図する前に、ユーザのクエリの部分が、クライアントシステム１０４から検索エンジン１０６に送信される（１１０）。クエリの部分は、いくつかの文字、１つの検索ターム、または２つ以上の検索タームであってもよい。一部の実施形態では、部分入力は、インターネット・エンジニアリング・タスク・フォース（Ｉｎｔｅｒｎｅｔ Ｅｎｇｉｎｅｅｒｉｎｇ Ｔａｓｋ Ｆｏｒｃｅ）によって公布されたＲＦＣ１７３８に記載されているような、ユニフォーム資リソースロケータ（ＵＲＬ）としばしば呼ばれる、コンテンツ位置識別子の形態であってもよい。ＵＲＬは、コンピュータおよびコンピュータネットワーク内の資源を識別するために使用されることが可能である。ＵＲＬは、さらに、文書、フォルダ、またはサービスなどの、コンピュータ上でローカルに利用できる資源を識別するためにも使用されることが可能である。用語「ＵＲＬ」は、本明細書内では、以下に限定されないが、インターネットアドレス、ＲＦＣ１７３８準拠アドレス、ならびに、多くのコンピュータシステムおよびローカルエリアネットワーク内で使用されているようなファイルパス名を含む、任意の形態のコンテンツ位置識別子を意味するために使用される。検索エンジン１０６は、部分クエリを処理のために受信し（１１２）、ユーザが企図した完全なクエリ（またはＵＲＬ）についての予測を行う（１１４）。予測は、ランク付け基準に従って順序付けされる。例えば、一部の実施形態では、より高い発行頻度を有するクエリは、より低い発行頻度を有するクエリよりも前に順序付けされる。検索エンジン１０６は、順序付けされた予測の作成を補助するために、いくつかのクエリ補完テーブル（以下にさらに詳細に記載する）を使用する。クエリ補完テーブルは、検索エンジン１０６によって受信された、以前に入力された検索クエリを使用して作成される。一部の実施形態では、以前のクエリは、ユーザのコミュニティからの検索クエリを含む。予測クエリは、クライアントシステム１０６に送り返され（１１６）、次に、ユーザに提示される（１１８）。予測クエリのうちの１つが、ユーザが所望のクエリとして意図したものである場合、ユーザは、この予測クエリを選択して、所望のクエリの入力を完了させることなく、先に進むことができる。予測クエリが、ユーザが考えていたものを反映していない場合、ユーザは、所望の検索クエリの入力を継続してもよい。
【００１２】
図２は、本発明の一部の実施形態による検索システム２００を例示し、さらに、以下の詳細な議論で参照される、さまざまな機能構成要素を示す。検索システム２００は、１つまたは複数のクライアントシステム２０２を含んでもよい。各クライアントシステム２０２は、検索アシスタント２０４を有する。クライアントシステム２０２は、通信ネットワーク２０６に接続される。通信ネットワーク２０６は、クライアントシステム２０２を検索エンジン２０８に接続する。検索エンジン２０８は、通信ネットワーク２０６に接続されたクエリサーバ２１０と、予測サーバ２１２と、クエリ処理コントローラ２１４とを含む。
【００１３】
クエリサーバ２１０は、クライアント通信モジュール２１６と、クエリ受信・処理および応答モジュール２１８と、部分クエリ受信・処理および応答モジュール２２０と、ユーザ情報処理モジュール２２２と、クエリログ２２４とが、すべて相互接続されたものを含む。一部の実施形態では、より少ない、および／または追加の、モジュールまたは機能が、クエリサーバ２１０内に含まれる。クエリサーバ２１０の部分として図２に示すモジュールは、一例示的実施形態で実行される機能を表す。予測サーバ２１２は、部分クエリ受信・処理および応答モジュール２２０と、順序付け組ビルダ（ordered set builder）２４２と、クエリログ２２４とに接続される。順序付け組ビルダ２４２は、クエリとＵＲＬ要求とのログから、順序付けされた予測クエリの組を作成するものであり、クエリログ２２４に接続される。一部の実施形態では、順序付け組ビルダ２４２は、ＵＲＬデータベース２２５にも結合され、一部の実施形態では、言語辞書２４４に結合される。言語辞書２４４は、さまざまな記号言語要素についての表音表示（phonetic representations）のような、特定の言語要素に関する情報を提供してもよく、あるいは、クエリまたはクエリタームに関連する、語または概念を提供してもよい。一部の実施形態では、順序付け組ビルダ２４２および言語辞書２４４は、予測サーバ２１２の部分である。そのような実施形態では、予測サーバ２１２は、クエリログ２２４およびＵＲＬデータベース２２５に直接接続される。
【００１４】
クエリ処理コントローラ２１４は、逆文書インデックス（inverse document index）２２８と、文書データベース２３０と、クエリキャッシュ２３２と、ＵＲＬデータベース２２５とに接続される。キャッシュ２３２は、インデックス２３４を含んでもよく、インデックス２３４の機能は、キャッシュされた結果２３６内のエントリを検出することである。キャッシュされた結果２３６は、識別されたクエリのためのキャッシュエントリ２３８と、予期されるクエリのためのキャッシュエントリ２４０とを含んでもよい。逆文書インデックス２２８と文書データベース２３０とは、一括して、文書データベースと呼ばれることがある。一部の実施形態では、「文書データベースを検索している」とは、指定された検索クエリまたはタームに一致する文書を識別するために、逆文書インデックス２２８を検索していることを意味する。
【００１５】
図では別個のブロックとして示されているが、図２は、機能要素の構造マッピングとしてよりも、むしろ、本発明の実施形態の機能的説明として意図されている。実際の実装は、さまざまな構成要素の中でグループ化された、または分割された機能要素を有してもよいことを、当業者は認識するであろう。例えば、クエリログ２２４は、クエリサーバ２１０とは別個のものであってもよい。一部の実施形態では、クエリログ２２４は、クエリログ情報の記憶および処理が主な機能である、１つまたは複数のサーバ上に記憶されてもよい。同様に、ＵＲＬデータベース２２５は、既知のＵＲＬに関する情報の記憶および処理が主な目的である、１つまたは複数のサーバ上に記憶されてもよい。
【００１６】
図３は、クライアントシステム２０２（図２）の検索アシスタント２０４に実装されてもよい、本発明の実施形態を示す。検索アシスタント２０４は、クライアントシステム１０４上での、ユーザによる検索クエリの入力を監視する（３０２）。一部の実施形態では、検索アシスタント２０４は、ブラウザウィンドウのアドレスフィールド内などへの、ユニフォームリソースロケータ（ＵＲＬ）のユーザ入力を監視する。ユーザは、検索クエリまたはＵＲＬを、ブラウザウィンドウ、検索ツール、またはその他の任意の入力機構を含む、いくつかの方法で入力してもよい。検索アシスタント２０４は、２つの異なるシナリオを識別してもよい。第１に、検索アシスタント２０４は、ユーザが入力文字列の完成を指示した場合、または提示された予測を選択した場合に、最終入力（３０２−最終入力）を受信または識別する。第２に、検索アシスタント２０４は、（以下に記載するように）ユーザが入力文字列の完成を指示する前に入力が識別された場合に、部分入力（３０２−部分入力）を受信または識別する。第３の、任意選択のシナリオ（以下にさらに詳細に記載する）では、検索アシスタント２０４は、指定された期間内に予測のうちの１つをユーザが選択しなかったことの通知を、判定または受信する。
【００１７】
最終入力または選択（３０２−最終入力）が検索クエリとして識別された場合、入力は、処理のために検索エンジン２０８に送信される（３０４）。検索エンジン２０８は検索結果の組を返し、その検索結果の組は、検索アシスタント２０４によって受信されるか（３０６）、または、ブラウザアプリケーションなどのクライアントアプリケーションによって受信される。検索結果のリストは、ユーザがさらなる調査のために文書のうちの１つを選択してもよいように、ユーザに提示される（例えば、視覚的に、または聴覚的に）。最終入力がＵＲＬである場合、要求は適切な文書ホストに送信され（３０４）、文書が、利用可能な場合は、返される（３０６）。応答が受信された後は（３０６）、ユーザの入力活動が再び監視される（３０２）。一部の実施形態では、ＵＲＬ要求は、ロギングのために検索エンジン２０８に送信され、そしてその要求は、適切な文書ホストに転送される。
【００１８】
最終入力は、ユーザが、キャリッジリターンまたは同等の文字を入力した場合、あるいは、検索クエリの入力中にユーザに提示されるグラフィカルユーザインタフェース（ＧＵＩ）内の検索ボタンを選択した場合などの、いくつかの方法で、検索アシスタント２０４によって識別されてもよく、あるいは可能であれば、検索クエリの入力中にユーザに提示される、可能なクエリの組のうちの１つを選択することによって識別されてもよい。当業者は、検索クエリの最終入力を合図するためのいくつかの方法を認識するであろう。
【００１９】
ユーザが最終入力を合図する前に、部分入力が識別されてもよい（３０２−部分入力）。部分入力は、いくつかの方法で識別されてもよい。検索クエリの場合、部分入力は、検索クエリの１つの検索ターム、複数の検索ターム、または検索タームの、事前定義された数の文字を含む。
【００２０】
一部の実施形態では、部分入力は、区切り文字またはその他の文字の入力（例えば、以下に限定されないが、引用文字、終止符、括弧文字、スラッシュ文字、矢印キーの検出、またはタブの入力）を検出することによって識別される。区切り文字の入力は、ユーザが前記入力の所望のタームまたは部分の入力を完了し、次の検索タームまたは部分に移動しつつあることを示してもよい。
【００２１】
一部の実施形態では、部分入力は、文字の所定数の入力を検出することによって識別されてもよい。それらの実施形態では、前記入力は、完全な入力よりも少ない数の文字を含むが、さらに、ユーザがすべての文字を入力してしまう前に部分入力を識別することが望ましい場合がある。このテクニックは、例えば、検索タームまたはＵＲＬが多数の文字を含む場合、または、前記文字の所定数が有用な予測をもたらすのに十分なだけ大きい場合に望ましい。
【００２２】
一部の実施形態では、部分入力は、一定期間内における入力文字の欠如が検出されることによって識別されてもよく、前記欠如は、ユーザによる間断を表す。前記間断は、ユーザが１つの検索タームを、または完全な文字列の部分を入力してしまったにもかかわらず、別のタームの入力を開始するために、スペースキー（またはその他の区切り文字）を入力していないことを表してもよく、あるいは、検索クエリは実際には完成したが、ユーザがまだそのように合図していないことを表してもよい。
【００２３】
部分入力が識別される方法にかかわらず、部分入力は、処理のために検索エンジン２０８に送信される（３０８）。部分検索クエリに応答して、検索エンジン２０８は、順序付けされた予測された検索クエリおよび／またはＵＲＬの組を返し（３１０）、その組は、ランク付け基準に従って順序付けされて、ユーザに提示される（３１２）。予測は、いくつかの方法でユーザに表示されてもよい。例えば、予測は、ドロップダウンウィンドウ内に、永続的または非永続的なウィンドウ内に（a persistent, or non-persistent window）、あるいは、その他の方法で表示されてもよい。一部の実施形態では、ユーザが以前に発行したクエリが、ユーザに視覚的に示されてもよい（例えば、ユーザ自身が以前に入力したクエリを強調表示することにより）。
【００２４】
一部の実施形態では、予測された検索クエリは、ユーザのコミュニティによる発行頻度に従って順序付けされる。一部の実施形態では、検索クエリは、少なくとも部分的には、クエリが発行された最後の時間／日付値に従って順序付けされる。一部の実施形態では、検索クエリは、ユーザパーソナライズ情報またはコミュニティ情報などの、パーソナライズ情報に従って順序付けされる。例えば、ユーザパーソナライズ情報は、ユーザにとって関心のある情報の、主題、概念、またはカテゴリに関する情報を含んでもよい。ユーザパーソナライズ情報は、ユーザによって直接提供されてもよく、あるいは、ユーザの許可により、ユーザの以前の検索またはブラウジング活動から推論されてもよく、あるいは、ユーザに関連付けられたグループ、またはユーザが（例えば、メンバーとして、または従業員として）属するグループに関する情報に、少なくとも部分的に基づいてもよい。予測された検索クエリの組は、最初に、事前定義された人気基準（popularity criteria）などの、第１のランク付け基準に従って順序付けされてもよく、次に、いずれかの予測された検索クエリがユーザのユーザパーソナライズ情報に一致する場合は、一致している予測された検索クエリを、予測された検索クエリの順序付けされた組の最上部に、または最上部により近いところに配置するように順序付けし直されてもよい。
【００２５】
当業者は、予測された検索クエリおよび／またはＵＲＬをユーザに提示する、いくつかの方法を認識するであろう。例えば、予測された検索クエリおよび／またはＵＲＬは、ドロップダウンメニュー内で提示されてもよい。予測クエリおよび／またはＵＲＬがユーザに提示される方法にかかわらず、ユーザは、予測のうちの１つが、意図する入力に一致すると判断した場合、クエリおよび／またはＵＲＬのうちの１つを選択してもよい。場合によっては、予測は、考慮されていなかった追加情報をユーザに提供してもよい。例えば、ユーザは、検索ストラテジの一部として１つのクエリを考えているかもしれないが、予測された結果を見て入力ストラテジを変更してもよい。組が提示されたら（３１２）、ユーザの入力が再び監視される。ユーザが予測のうちの１つを選択した場合（３０２−最終）、要求は、検索要求として検索エンジン２０８に、またはＵＲＬ要求として資源ホストに、適宜送信される（３０４）。要求が送信された後は、ユーザの入力活動が再び監視される（３０２）。上述のように、一部の実施形態では、ＵＲＬ要求は、ロギングの目的のために、検索エンジン２０８に送信される。
【００２６】
他方、指定された期間内に、予測のうちの１つをユーザが選択していない場合、ユーザは、最初に返された予測の中に、満足のいく予測を見いださなかった可能性がある。例えば、ユーザの意図する入力は、順序付けされた予測の組の中に含まれるための十分に高いランク付け値を有さなかった。したがって、一部の任意選択の実施形態では、指定された期間（例えば、５秒または１０秒）内に、予測のうちの１つをユーザが選択していない場合（３０２−タイムアウト）、別の予測の組に対する要求が、検索エンジン２０８に送信される（３１８）。後続の予測の組（the subsequent set of predictions）は、以前に発行された組よりも低いランク付け値を有する予測を含んでもよい。あるいは、第２の組の中の予測を識別するために、第２の基準の組が使用されてもよく、ここで、第２の基準の組は、第１の予測の組を選択およびランク付けするために使用された第１の基準の組とは異なるものである。例えば、２つの組のうちの一方は、要求者に関する個人情報を考慮に入れた選択基準を使用してもよく、もう一方の組は、使用しなくてもよい。一部の任意選択の実施形態では、後続の予測の１つまたは複数の組を要求するために、その他のトリガが使用されてもよい。例えば、ユーザ始動の動作（例えば、「タブ」キー、矢印キー、ファンクションキーなどの押下）が、後続の組の要求を発生させてもよい。一部の実施形態では、いずれの予測された結果が検索要求者にすでに伝えられたかを識別するために、検索要求者に関連付けられた情報がサーバにおいて維持される。一部の実施形態では、クライアントは、いずれの結果が検索要求者にすでに伝えられたかを示す情報を、後続の要求に対する要求の中に含める。そのような一実施形態においては、予測サーバ２１２は、この情報を使用して、後続の予測された結果から、以前に予測された結果のすべてを、または、以前に予測された結果のサブセットを除外する。別の実施形態では、以前に予測された結果に関する情報は、予測サーバ２１２が、要求者の部分クエリに一致する、追加の予測された結果を識別することが可能な場合に限り、追加の、または異なる結果を生成するために、予測サーバ２１２によって使用される。一部の実施形態では、後続の予測の組をトリガとして（triggering）、検索要求者の、ローカルに記憶された検索クエリを使用して予測が作成されるのに対して、他の実施形態では、後続の予測の組は、要求者の部分クエリに一致するものがもしあれば、ユーザのコミュニティの履歴クエリに基づいて生成される予測と、検索要求者の履歴検索クエリ（存在する場合）とに基づいて生成される予測の、両方を含む。
【００２７】
一部の実施形態では、予測された結果の１つまたは複数の組は、クライアントにおいてローカルにキャッシュされる。検索要求者が、（例えば、バックスペースキーを押して一部の文字を削除することにより）以前の部分入力を反映するように現在のクエリを修正した場合、部分入力が検索エンジンに送信される代わりに、以前の部分入力に関連付けられた、予測された結果の組がクライアントキャッシュから取り出されて、ユーザに再び提示される。
【００２８】
一部の実施形態では、検索エンジン２０８は、任意選択として（optionally）、予測された結果を返してもよい（３２０）。この動作は、予測の受信（３１０）とオーバーラップしてもよく、図３では３２０への点線によって示されている。予測された結果が提示され（３２０）、ユーザの監視が再開される（３０２）。ユーザへの提示は、いくつかの方法で実現されてもよい。例えば、結果は、非永続的ウィンドウの部分内に、ポップアップウィンドウ内に、現在の表示の部分内に、またはユーザインタフェースの部分内に表示されてもよい。クエリの入力のため、および予測された結果の提示のために使用されるウェブページは、予測された結果の表示を容易にするための、および、予測された結果のうちのいずれかのユーザによる選択に応答するための、ジャバスクリプト（Ｊａｖａ（登録商標）Ｓｃｒｉｐｔ）あるいはその他の埋め込みコードまたは命令を含んでもよい。その他の方法も考えられる。予測された結果は、予測クエリまたはＵＲＬのうちの１つまたは複数である要求に基づいて返されたであろう文書または情報に対応する。一部の実施形態では、予測された結果は、予測された結果に対応する１つまたは複数の位置におけるコンテンツの断片(snippets)を含んでもよい。一部の実施形態では、予測された結果は、予測された結果に対応する１つまたは複数の位置における、１つまたは複数のウェブページまたはその他のコンテンツの、１つまたは複数のサムネイルを含んでもよい。一部の実施形態では、結果は、予測クエリの１つまたは複数に基づく検索結果である。例えば、一部の実施形態では、提示される結果（３２０）は、予測クエリまたは予測されたＵＲＬのうちの１つまたは複数に関連する、１つまたは複数の文書であってもよい。したがって、ユーザは、要求（例えば、検索要求またはＵＲＬ要求）の入力を完了する前に、所望の要求に一致する、提示される予測された結果を有してもよい。そのような状況においては、ユーザは、所望の結果を取得するために、入力を完了する必要がなかったため、ユーザから見た処理待ち時間は、事実上、０未満に減少する（reduced to less than zero）。
【００２９】
図４は、一部の実施形態に従って、検索エンジン２０８が入力を受信した場合に、検索エンジン２０８内で発生する動作を示す。検索エンジン２０８は、入力を受信し、入力が最終入力を示すか、または部分入力を示すかを判定する（４０２）。検索エンジン２０８は、受信された入力が最終クエリであると判定した場合（４０２−最終クエリ）、クエリに関連する検索結果がキャッシュ２３２内に存在するかどうかを判定する（４０４）。関連する検索結果がキャッシュ２３２内にある場合（４０４−ｙｅｓ）、それらの結果がクライアント１０４に返される（４０６）。他方、検索結果がキャッシュ内にない場合（４０４−ｎｏ）、クエリに関連する検索結果が取得され（４０８）、クライアント１０４に返される（４０６）。一部の実施形態では、ＵＲＬ要求は、完成した場合、検索エンジン２０８によって受信されず、その理由は、検索アシスタントが要求を資源ホストに送信するためである。一部の実施形態では、ＵＲＬ要求は、（ＵＲＬデータベース内への記憶などの）トラッキングの目的のために、検索エンジン２０８によって受信され、そしてその要求は、検索エンジン２０８によって資源ホストに転送される。
【００３０】
検索エンジン２０８は、受信された入力が部分入力であったと判定した場合（４０２−部分）、部分入力に対応する、順序付けされた一致の組（a set of ordered matches）を決定して（４１０）、その組をクライアント１０４に送信する（４１２）。以下で説明するように、一部の実施形態では、クライアント１０４に送信される順序付けされた一致の組は、順序付けされた一致の、多くの事前計算された組のうちの１つである。以下の動作は部分クエリに関して説明するが、同じテクニックが、ＵＲＬの部分入力に同様に適用可能である。一部の実施形態では、返される順序付けされた一致の組は、クエリのみに関連する。一部の実施形態では、順序付けされた一致の組は、ＵＲＬのみに関連する。また、一部の実施形態では、順序付けされた一致の組は、クエリおよびＵＲＬの両方に関連する。
【００３１】
一部の実施形態に従って、検索エンジン２０８が、順序付けされた一致のいずれの組を返すかを決定する方法を理解するための補助として、順序付けされた組がどのように作成され使用されるかの説明から開始することが役に立つ。図５は、部分的に入力されたクエリに対応するクエリを予測するために使用される、履歴クエリ（すなわち、以前に発行されたクエリ）に関連付けられたデータ構造の組を示す。検索エンジンまたはユーザ入力予測システムは、さらに、部分的に入力されたＵＲＬに対応するＵＲＬを予測するために使用される、履歴ＵＲＬ（すなわち、以前に発行されたＵＲＬ）に関連付けられた、類似したデータ構造の組も含んでもよい。
【００３２】
図５を参照すると、履歴クエリログ５０２が１つまたは複数のフィルタ５０４によってフィルタリングされて、許可された履歴クエリのリスト（authorized historical queries list）５０６が作成される。順序付け組ビルダ５０８は、特定の基準に基づいて、許可された履歴クエリのリスト５０６から、１つまたは複数のフィンガープリント−テーブルマップ（fingerprint-table map）５１０を作成する。部分クエリが送信された場合（図３、３０８）、その部分クエリは、検索エンジン２０８において、部分クエリ５１３として受信される。部分クエリ５１３にハッシュ関数５１４が適用されて、フィンガープリント、すなわち、ｂビットの２進値（例えば、６４ビットの数）が作成される。適切なフィンガープリント−テーブルマップ５１０（例えば、５１０−１）が、フィンガープリント（例えば、５１５）について検索され、そのフィンガープリントに関連付けられたクエリ補完テーブル５１６が識別される。クエリ補完テーブル５１６は、部分クエリ５１３に関連する、予測クエリの順序付けされた組を提供する。
【００３３】
適切なフィンガープリント−テーブルマップ５１０は、ユーザまたは要求に関連付けられた、いくつかの異なる要因に基づいて選択されてもよい。適切なフィンガープリント−テーブルマップ５１０を選択するために使用される情報は、ユーザまたは検索アシスタント２０４によって提供されたプロファイル情報から、または、要求そのものから収集された情報（例えば、言語）から、または、ユーザ情報処理モジュール２２２内の、ユーザに関連付けられた情報から、または、その他の情報源から得られるものであってもよい。例えば、フィンガープリント−テーブルマップは、ユーザまたは検索要求者に関連付けられた特定の接続情報（例えば、装置タイプ、接続速度、接続タイプなど）に基づいて選択されてもよい。一部の実施形態では、予測の数、またはそれぞれのクエリ予測の長さは、そのような接続情報に依存してもよい。小さなユーザインタフェースを有する装置は、より少ない数の予測を、および／または、より少ない数のタームを有するクエリを受信してもよい。クエリタームは、それに関連付けられた重要度係数を有してもよく、より低い重要度係数を有するタームは、より高い重要度係数を有するタームよりも前に、クエリから切り捨てられてもよい。一部の実施形態では、フィンガープリント−テーブルマップ５１０の異なる組は、ユーザのそれぞれのカテゴリのために使用されてもよく、それにより、ユーザに関連付けられた１つまたは複数のカテゴリまたはトピックに従ってバイアスがかけられた、予測された結果が提供されてもよい。例えば、特定のウェブサイトから受信した部分検索クエリは、同じウェブサイトから受信した、または、該特定のウェブサイトに類似していると見なされるウェブサイトのグループから受信した履歴クエリから生成された、フィンガープリント−テーブルマップの組を使用して、予測された結果にマッピングされてもよい。同様に、個々のユーザは、そのユーザの許可により、ユーザに関する情報、またはユーザに関連付けられたグループに関する情報を指定するユーザプロファイルを有してもよく、その「パーソナライズ情報」は、そのユーザのための結果を予測する際に使用するフィンガープリント−テーブルマップのそれぞれの組を識別するために使用されてもよい。フィンガープリント−テーブルマップ５１０の複数の組は、同じクエリ補完テーブル５１６を指してもよく、クエリ補完テーブル５１６は、フィンガープリント−テーブルマップ５１６よりもはるかに多くの記憶領域を占めるため、フィンガープリント−テーブルマップ５１０の複数の組を追加することに関連するオーバヘッドは少量とすることができることに注意されたい。
【００３４】
一部の実施形態では、フィンガープリントが作成される前に、部分クエリへの何らかの前処理が発生する。一実施形態では、完全な検索タームのうちの１つまたは複数を辞書内のエントリと比較することによって、部分クエリ内の顕著なミススペル語が識別され、訂正される。正しいスペルの語を含むクエリから予測された１つまたは複数の結果は、ユーザに返される予測された結果とマージされる。別の例では、一般的なプレフィックス情報が削除されてもよい（例えば、「ｈｔｔｐ：／／」または「ｗｗｗ．」）。一部の実施形態では、クエリ内のタームが分析され、検索ターム内に組み入れられた、特定の情報カテゴリを示す概念が抽出される（例えば、「技術」、「食物」、「音楽」、または「動物」）。抽出された概念のうちの１つまたは複数に関連するクエリから予測された１つまたは複数の結果は、ユーザに返される予測された結果とマージされる。
【００３５】
履歴クエリログ５０２は、一定期間にわたって検索エンジン２０８によって受信された、以前に発行されたクエリの記録を含む。一部の実施形態では、クエリは、特定のユーザからのものである。一部の実施形態では、クエリは、同じワークグループに属している、同じ言語を使用している、同じ国または地理的領域に関連付けられたインターネットアドレスを有しているなどの、少なくとも１つの類似した特性を共有するユーザのコミュニティからのものである。コミュニティの選択により、以前に発行されたクエリのプールが特定され、そこから予測が引き出される。異なるコミュニティは、異なる予測の組を生成する傾向がある。
【００３６】
履歴クエリログ５０２は、さらに、それぞれの発行されたクエリに関連付けられた情報も含んでもよい。一部の実施形態では、クエリ情報は、クエリが発行または受信された日付と時刻を含む。一部の実施形態では、クエリ情報は、クエリの発行元のインターネットプロトコル（ＩＰ）アドレスを含む。一部の実施形態では、クエリ情報は、クエリの固有ソース識別子（例えば、ユーザのマシン上に記憶されたクッキー（ｃｏｏｋｉｅ）からの値であって、その値は特定の検索アシスタント２０４に関連付けられている）を含む。固有識別子は、いかなる特定のユーザも直接には識別しないが、ブラウザまたはツールバーの特定のインストールに関連付けられてもよい。一部の実施形態では、ユーザは、ユーザ情報処理モジュール２２２を使用してアクセスすることができる特定のパーソナライズ特徴について、固有識別子を使用した直接の識別を許可してもよい。
【００３７】
一部の実施形態では、フィンガープリント値はクエリと関連付けられる。フィンガープリント値は、クエリ文字列にハッシュ関数を適用することによって計算されてもよい。一部の実施形態では、クエリ言語または、ユーザ嗜好に従ってユーザまたは検索アシスタントにより提供されてもよいその他の情報（例えば、ユーザの特定の嗜好を示す識別またはプロファイル情報）などの、その他のタイプのメタデータが、クエリと関連付けられて記憶されてもよい。一部の実施形態では、メタ情報は、クエリ内のタームの分析から収集されたカテゴリまたは概念情報を含む。クエリが記録されている期間は、調節可能であり、それは、記憶容量と、可能な予測精度との間のトレードオフを表す。より長い期間は、コミュニティ全体にわたるクエリの人気がより正確に反映されるが、これにはより多くの記憶領域が必要とされる。他方、長い期間にわたる人気のランク付けは、現在の出来事についての一時的な人気は反映しない可能性がある。
【００３８】
１つまたは複数のフィルタ５０４は、さらなる処理のために許可されるクエリを決定するために使用される。例えば、フィルタは、さまざまな基準に基づいて特定のクエリを除去してもよい。一部の実施形態では、特定の数よりも多くの個別発行者（unique submitters）から受信されていないクエリが、許可された履歴クエリのリスト５０６内に含められるのを、プライバシーフィルタ５０４が防止する。これは、各クエリに関連付けられた固有識別子（存在する場合）を調べて、少なくともｎ人の個別発行者によって発行されたクエリのみを識別することによって実現されてもよく、ここで、ｎは、プライバシーに対する関心（privacy concerns）に基づいて選択される数（例えば、３人または５人の固有発行者）である。一部の実施形態では、フィルタ５０４は、まれにしか発行されず、したがってユーザによって選択されそうにないクエリを、除去するフィルタを含む。一部の実施形態では、フィルタ５０４は、クエリ内の１つまたは複数の特定のキーワードの存在などの、いくつかの異なる要因に基づいて、および／または、クエリに対応する検索結果または文書のコンテンツに基づいて、特定のクエリが含まれるのを阻止する、妥当性フィルタ５０４を含む。その他のタイプのフィルタが容易に想像されてもよい。例えば、許可された履歴クエリのリスト５０６が、最近発行されたクエリを表すように、フィルタは、特定の過去時点（historical point）よりも前に発行されたクエリを阻止してもよい。何が最近と見なされるかは、実施形態により異なる（例えば、時間、日、週、月、または年）。さらに別の例では、多数の人為的に生成されたクエリまたはＵＲＬの発行によって、クエリ／ＵＲＬ予測システムがスプーフィングされる（being spoofed）のを防止するために、アンチスプーフィングフィルタ５０４が使用されてもよい。例えば、アンチスプーフィングフィルタ５０４は、同じユーザまたは同じクライアントコンピュータから受信した、複数の同じクエリまたはＵＲＬの発行を、除去してもよい。
【００３９】
１つまたは複数のフィルタ５０４によって、履歴クエリログ５０２がフィルタリングされた後の結果は、許可された履歴クエリのリスト５０６、すなわち、提案されるクエリ補完としてユーザに返される資格があるクエリのリストである。許可された履歴クエリのリスト５０６は、履歴クエリ５０６−１〜履歴クエリ５０６−ｑを含み、ここで、ｑは、許可された履歴クエリのリスト５０６内に含まれるクエリの数を表す。ｑの値は、履歴クエリログ５０２からフィルタリングして得られたクエリ（queries filtered）の総数以下であってもよい。例えば、所定のしきい値未満の頻度を有する、フィルタリングして得られたクエリは、無視されてもよい。一部の実施形態では、新しい許可された履歴クエリのリスト５０６が、毎時間、毎夜、毎週、またはその他の周期などで、定期的に構築される。一部の実施形態では、現在の許可された履歴クエリのリスト５０６は、適切なフィルタリングの後、クエリログ２２４への最近の入力に基づいて更新される。
【００４０】
許可された履歴クエリのリスト５０６（例えば、５０６−１）内の各クエリは、クエリと、その頻度と、任意選択としてメタ情報とを含む。クエリは、文字列であってもよい。頻度情報は、一定期間にわたっての、クエリが発行された回数を示す。上述のように、個別検索者がクエリを発行した回数を計数するために、固有識別子が使用されてもよい。それぞれのユーザが複数の検索アシスタントを使用する場合があり、また、一部のクエリは固有識別子を含まない場合があるため、頻度の数は、検索クエリを発行している個別ユーザの実際の数を表さない可能性がある。それにもかかわらず、クエリの頻度は、クエリの人気の代用として働いてもよい。一部の実施形態では、許可された履歴クエリのリスト５０６は、クエリに基づいてアルファベット順に順序付けされる。他の実施形態では、許可された履歴クエリのリスト５０６は、クエリの頻度に基づいて順序付けされる。
【００４１】
メタ情報は、履歴クエリログ５０２に関連して上述した、メタ情報に類似した情報を含んでもよい（例えば、位置または言語情報）。一部の例では、同じクエリが、履歴クエリログ５０２内に、クエリ文字列では異ならないが、メタ情報では異なるエントリを有する。したがって、特定の許可された履歴クエリ５０６−１についてのメタ情報は、同じクエリについての異なるメタ情報を示してもよい。例えば、ヨーロッパとアジアのような、２つの異なる位置から発行されたクエリについてのメタ情報は、両方の位置を、クエリのソース位置として示す。メタ情報は、さらに、クエリを発行したユーザのタイプを示す、ユーザプロファイリング情報も示してもよい。当業者は、特性の共通の組（例えば、言語または位置）によって関連付けられるクエリを分類またはグループ化するために役立つ可能性がある、さまざまなタイプのメタ情報を認識するであろう。一部の実施形態では、クエリタームが分析され、特定の情報カテゴリに関連付けられる。例えば、「犬」および「品種」を含む検索クエリは、「犬」または「動物」カテゴリに関連付けられる。一部の実施形態でのメタ情報は、このカテゴリ情報を含む。一部の実施形態では、許可された履歴クエリのリスト５０６内の１つのエントリについてのメタ情報は、複数のクエリから生成される（例えば、クエリが発行された最後の日付／時刻値としてクエリの日付／時刻を提供することによって）。
【００４２】
順序付け組ビルダ５０８は、許可された履歴クエリのリスト５０６を使用して、フィンガープリント−テーブルマップの組５１０−１〜５１０−ｔを構築し、ここで、ｔは構築されるフィンガープリント−テーブルマップ５１０の数を表す。予測クエリを分類するために所望される方法の数に応じて、任意の数のフィンガープリント−テーブルマップ５１０が構築されてもよい。それぞれのフィンガープリント−テーブルマップ５１０は、順序付けされた予測の組を複数含み、それぞれの組は特定の部分クエリにマッピングされている。フィンガープリント−テーブルマップ５１０は、メタ情報内に見いだすことができるような情報の特性に基づいて、異なっている。例えば、各言語について１つのフィンガープリント−テーブルマップ５１０があってもよい（例えば、英語のクエリについて１つ、フランス語のクエリについて１つ、日本語のクエリについて１つ）。同様に、地理的領域について、さまざまなフィンガープリント−テーブルマップ５１０が作成されてもよい。別の例として、特定のネットワークまたは特定の個人グループ（例えば、会社）からのクエリなどの、特定のＩＰアドレスまたはアドレスグループからのクエリから、さまざまなフィンガープリント−テーブルマップ５１０が作成されてもよい。メタ情報を使用してさまざまなフィンガープリント−テーブルマップ５１０を作成することにより、検索者の特性に類似した特性を有するユーザに基づいた予測が可能になり、それにより、正しい予測の可能性が増加する。一部の実施形態では、異なるフィンガープリント−テーブルマップ５１０は、クエリについての異なるランク付け基準に基づいてもよい（例えば、頻度、最後の日付／時刻、パーソナライズカテゴリまたは特性など）。一部の実施形態では、異なるフィンガープリント−テーブルマップ５１０は、ユーザ入力のタイプ（すなわち、クエリ文字列またはＵＲＬ）に基づく。
【００４３】
フィンガープリント−テーブルマップ５１０−１を例として使用すると、それぞれのフィンガープリント−テーブルマップ５１０は、複数のエントリ５１２−１〜５１２−ｆを含み、ここで、ｆはフィンガープリント−テーブルマップ５１０−１内のエントリ数を表す。どの特定のフィンガープリント−テーブルマップ５１０においても、そのエントリ数は、異なる部分クエリ（それに対して、予測サーバ２１２は予測を返す）の数に依存する。
【００４４】
フィンガープリント−テーブルマップ５１０−１内の各エントリ（例えば、５１２−２）は、フィンガープリント（例えば、フィンガープリント（２）５１５）と、クエリ補完テーブル（例えば、クエリ補完テーブル（２）５１６）とを含む。フィンガープリント−テーブルマップ５１０は、フィンガープリント（例えば、フィンガープリント（２）５１５）をクエリ補完テーブル（例えば、クエリ補完テーブル（２）５１６）に関連付ける働きをする。
【００４５】
フィンガープリント（２）５１５は、部分クエリのフィンガープリント値を表す。フィンガープリント（２）５１５は、例えば、部分クエリにハッシュ関数を適用して、ｂビットの２進値（例えば、６４ビットの数）を作成することによって計算されてもよい。したがって、部分クエリ５１３のフィンガープリントに一致するフィンガープリント（例えば、フィンガープリント５１５）を探して、フィンガープリント−テーブルマップ５１０−１が検索することができる。
【００４６】
クエリ補完テーブル（２）５１６は、クエリ補完フィンガープリント５１８−１〜５１８−ｎのリストを含み、ここで、ｎは、クエリ補完テーブル（２）５１６内のクエリ補完フィンガープリントの数を表す。一部の実施形態では、ｎは、検索アシスタント２０４に返される、予測クエリの数を表す（例えば、１０個の予測クエリ）。他の実施形態では、ｎ個未満が返される。一部の実施形態では、ｎは、順序付けされたクエリの組において返される結果の数よりも大きい。一部の実施形態では、ｎは、返される数の２倍であり、最初のｎ／２個は、順序付けされた、予測クエリの第１の組として提供され、２番目のｎ／２個は、順序付けされた、予測クエリの後続の組として提供される（例えば、第２の１０個の予測クエリの組が、特定の条件が満たされれば、第１の１０個の組に続いて送信される）。一部の実施形態では、クエリ補完テーブル５１６は、各クエリ補完フィンガープリント５１８についての得点を含む。得点は、クエリ補完テーブル５１６内の項目を、得点の高い順に順序付けするために使用される。一部の実施形態では、得点は、クエリ補完テーブルの永続的な部分であり、他の実施形態では、得点は、クエリ補完テーブル５１６の形成が完了した後、削除されるか、または、保持されない。
【００４７】
各クエリ補完フィンガープリント５１８は、完全なクエリに関連付けられたフィンガープリント値である。クエリ補完フィンガープリント５１８（例えば、５１８−２）は、関連するクエリレコード５２０にマッピングされる。クエリレコード５２０は、完全なクエリのクエリ文字列を含む、クエリ文字列５２２を含む。この方法は、複数のクエリ補完テーブル５１２内のエントリが同じクエリ文字列５２２を参照することを容易にし、しかも、実際のクエリ文字列が１つの位置に記憶されることのみを要求する（例えば、クエリ文字列５２２）。ただし、一部の実施形態では、クエリ文字列５２２は、クエリ補完テーブル５１２内に、クエリ補完フィンガープリント５１８の代わりに記憶されてもよい。一部の実施形態では、ＵＲＬ文字列についてのクエリレコード５２０は、ＵＲＬに関連付けられたタイトルを表すＵＲＬタイトル５２４を含む。一部の実施形態では、ＵＲＬに関連付けられた追加情報が、情報５２６内に提供される。
【００４８】
一部の実施形態では、クエリ補完テーブル５１２−２は、フィンガープリント５１５に関連付けられた部分クエリに関連する、ｎ個のクエリの順序付けされたリストである。リストは、（発行の頻度、日付／時刻などのような）さまざまなランク付け基準に従って順序付けされてもよい。一部の実施形態では、ランク付け基準は、発行の頻度と日付／時刻との両方などの、２つ以上の要因を考慮に入れたものであってもよく、そのためには、２つ以上の要因のそれぞれを考慮に入れた得点またはランクを各クエリについて生成する。単純な例では、日付／時刻が２４時間前よりも古い履歴クエリは、クエリのランク付け得点に値「１」を提供してもよく、日付／時刻が過去２４時間以内である履歴クエリは、クエリのランク付け得点に値「２」を提供してもよい。この例では、それぞれの許可された履歴クエリのランクの決定において、最近の履歴クエリは、より古い履歴クエリよりもより重く重み付けされる。
【００４９】
一部の実施形態では、順序付け組ビルダ５０６は、フィンガープリント−テーブルマップ５１０と、関連するクエリ補完テーブル５１２および／または９１０（図９）とを定期的に（例えば、毎時間、毎日、毎週）作成または更新し、それにより、予測サーバによって生成されるクエリおよび／またはＵＲＬ予測は、該当するユーザのコミュニティによって最近発行されたクエリおよび／またはＵＲＬと整合性のあるものに維持される。
【００５０】
図６を参照すると、部分クエリ「ｈｏ」６０２は、完全なクエリの組６０４を、部分クエリ６０２に関連するものとして有してもよい。完全なクエリの組６０４の最初の位置は、最も高い頻度値を有するクエリ（例えば、「ｈｏｔｍａｉｌ」）を含み、それに続く第２の位置は、次に高い頻度値を有するクエリ（例えば、「ｈｏｔ ｄｏｇｓ」）を含み、以下同様となる。この例では、所与の部分クエリへの、完全なクエリの関連性は、完全なクエリの先頭における部分クエリの存在によって決定される（例えば、文字「ｈｏ」によって、完全なクエリ「ｈｏｔｍａｉｌ」および「ｈｏｔｅｌｓ ｉｎ Ｓａｎ Ｆｒａｎｃｉｓｃｏ」は開始される）。他の実施形態では、完全なクエリの組６０６によって示されるように、関連性は、完全なクエリ内の任意の位置に配置された検索タームの先頭における部分クエリの存在によって決定される（例えば、文字「ｈｏ」は、「ｈｏｔｍａｉｌ」の先頭において、および、「ｃｈｅａｐ ｈｏｔｅｌｓ ｉｎ Ｃａｐｅ Ｔｏｗｎ」内の２番目の検索タームの先頭において見いだされる）。
【００５１】
クエリ補完テーブル５１２の組を作成するために、許可された履歴クエリ５０６内のクエリのうちの１つが選択される（図７、７０２）。一部の実施形態では、所望のメタ情報を有するクエリのみが処理される（例えば、英語によるクエリ）。選択されたクエリから、最初の部分クエリが識別される（７０４）。一実施形態では、最初の部分クエリは、選択されたクエリの最初の文字である（すなわち、クエリ文字列「ｈｏｔ ｄｏｇ ｉｎｇｒｅｄｉｅｎｔｓ」に対しては「ｈ」）。一部の実施形態では、部分クエリが識別される前に、前処理が適用される（例えば、「ｈｔｔｐ：／／」または「ｗｗｗ」の除去）。部分クエリと、部分クエリに対応する完全なクエリと、その頻度とを示すエントリが、テーブル内に作成される。他の実施形態では、ランク付けのために使用されるその他の情報が記憶される（例えば、日付／時刻値、または、２つ以上の要因に基づいて計算されたランク付け得点）。部分クエリが、クエリ全体を表さない場合、クエリ処理は完了していない（７０８−ｎｏ）。したがって、次の部分クエリが識別される（７１０）。一部の実施形態では、次の部分クエリは、前に識別された部分クエリに次の追加の文字を追加することにより識別される（すなわち、クエリ文字列「ｈｏｔ ｄｏｇ ｉｎｇｒｅｄｉｅｎｔｓ」に対しては「ｈｏ」）。識別（７１０）およびクエリ補完テーブルの更新（７０６）のプロセスは、クエリ全体が処理されるまで継続される（７０８−ｙｅｓ）。すべてのクエリがまだ処理されていない場合（７１２−ｎｏ）、次のクエリが選択され、すべてのクエリが処理されるまで処理される（７１２−ｙｅｓ）。一部の実施形態では、クエリ補完テーブルに項目が追加される場合、テーブル内の項目がランクまたは得点に従って順序付けされるように、項目は挿入される。別の実施形態では、すべてのクエリ補完テーブルは、テーブル構築プロセスの最後にソートされ、それにより、各クエリ補完テーブル内の項目は、クエリ補完テーブル内の項目のランクまたは得点に従って順序付けされる。さらに、１つまたは複数のクエリ補完テーブルは、テーブルが所定の数のエントリよりも多くを含まないように、切り捨てられてもよい。
【００５２】
図８を参照すると、クエリ文字列「ｈｏｔ ｄｏｇ ｉｎｇｒｅｄｉｅｎｔｓ」の最初の５文字の例示的処理が、テーブル８０２の８０４〜８１２において示されており、クエリ文字列「ｈｏｔｍａｉｌ」の最初の４文字の例示的処理が、８１４〜８２０において示されている。
【００５３】
一部の実施形態では、所与の部分クエリに対するクエリ補完テーブルは、所与の部分クエリに関連するｎ個の最も頻繁に発行されたクエリをテーブルから識別し、最高のランク（例えば、最高のランク付け得点または頻度）を有するクエリがリストの最上位になるように、それらをランク付けされた順序で配置することによって作成される。例えば、部分クエリ「ｈｏｔ」に対するクエリ補完テーブルは、完全なクエリ文字列８０８および８１８の両方を含む。ランク付けが頻度に基づく場合、「ｈｏｔｍａｉｌ」のクエリ文字列は、「ｈｏｔ ｄｏｇ ｉｎｇｒｅｄｉｅｎｔｓ」のクエリ文字列よりも上に現れ、その理由は、８１８内のクエリ文字列の頻度（すなわち、３００，０００）が、８０８内のクエリ文字列の頻度（すなわち、１００，０００）よりも大きいためである。一部の実施形態では、特定のウェブページに割り当てられた、ウェブページの組の中でのその重要性の指標を提供する値（例えば、ページランク（ＰａｇｅＲａｎｋ））が、ＵＲＬの人気度に与えられてもよい。したがって、予測の順序付けされた組がユーザに返される場合、選択される可能性がより高いクエリが最初に提示される。上述のように、メタ情報から引き出された他の値が、ランク付けのために使用されてもよい（例えば、日付／時刻値、またはパーソナライズ情報）。
【００５４】
図９および図１０を参照すると、一部の実施形態では、履歴クエリ文字列を、４文字などの、事前定義されたサイズＣの「チャンク」に分割することによって、クエリ補完テーブルの数が減らされる。Ｃ未満の長さの部分クエリに対するクエリ補完テーブルは、変化しない。長さが少なくともＣである部分クエリについては、部分クエリは、プレフィックス部分およびサフィックス部分の、２つの部分に分割される。サフィックス部分の長さＳは、部分クエリ（Ｌ） ｍｏｄｕｌｏ Ｃの長さに等しい。
Ｓ＝Ｌ ｍｏｄｕｌｏ Ｃ
ここで、Ｌは、部分クエリの長さである。プレフィックス部分の長さＰは、部分クエリの長さからサフィックスの長さを引いた長さである（Ｐ＝Ｌ−Ｓ）。したがって、例えば、１０文字の長さを有する部分クエリ（例えば、「ｈｏｔ ｐｏｔａｔｏ」）では、チャンクサイズＣが４の場合、サフィックスの長さＳは２、プレフィックスの長さＰは８となる。
【００５５】
図７のステップ７０６に示すプロセスを実行する場合の、部分クエリに対応するクエリ補完テーブルを識別または作成する工程を、図９に概念的に示す。図９は、クエリ補完テーブルの生成のため、および、ユーザが入力した部分クエリの処理時のルックアップのための、両方に使用されるプロセスを概略的に示す。部分クエリの長さが１つの「チャンク」のサイズＣ未満の場合、部分クエリは、例えば、ハッシュ関数５１４（図５）を使用することにより、クエリフィンガープリント５１５にマッピングされる。フィンガープリント５１５は、フィンガープリント−テーブルマップ５１０によって、クエリ補完テーブル５１６にマッピングされ、クエリ補完テーブル５１６は、クエリレコード５２０の組への、クエリ補完フィンガープリント５１８またはポインタを含む（クエリレコード５２０は、図５の、クエリ文字列５２２を含む）。
【００５６】
部分クエリの長さが、１つのチャンクのサイズＣで少なくともある場合、部分クエリ９０２は、プレフィックス９０４とサフィックス９０６とに分解され、それらの長さは、上述のように、チャンクサイズによって決定される。例えば、プレフィックス９０４にハッシュ関数５１４を適用することによって、プレフィックス９０４に対するフィンガープリント９０８が生成され、そのフィンガープリント９０８は、次に、フィンガープリント−テーブルマップ５１０によって、「チャンクされた」クエリ補完テーブル９１０にマッピングされる。チャンクされたクエリ補完テーブル９１０の各エントリ９１１は、クエリ補完フィンガープリント９１２だけでなく、サフィックスエントリ９１４も有するという点で、チャンクされたクエリ補完テーブル９１０の構造は、図５に示すクエリ補完テーブル５１６とは異なる。各エントリ９１１は、任意選択として、クエリ補完テーブル９１０内のエントリを順序付けするために使用される得点９１６も含んでもよい。サフィックスは、０〜（Ｃ−１）のいずれの値であってもよい長さＳを有し、部分クエリの、プレフィックス９０４内に含まれていない０以上の文字を含む。一部の実施形態では、履歴クエリについてのクエリ補完テーブルエントリ９１１を生成する場合、それぞれのチャンクされたクエリ補完テーブル９１０内に、履歴クエリに対応する１つのエントリのみが作成される。特に、その１つのエントリ９１１は、履歴クエリについての、最大Ｃ−１文字の長さとなり得るサフィックスを含む。他の実施形態では、特定の履歴クエリについて、それぞれのチャンクされたクエリ補完テーブル９１０内に、各別個のサフィックスについて１つの、最大Ｃ個のエントリが作成される。
【００５７】
図１０は、履歴クエリ「ｈｏｔ ｐｏｔａｔｏ」に対応するエントリ９１１を含む、クエリ補完テーブルの組を示す。この例では、チャンクサイズＣは、４に等しいと仮定している。他の実施形態では、チャンクサイズは、２、３、５、６、７、８、またはその他の任意の適切な値であってもよい。チャンクサイズＣは、経験的な情報に基づいて選択されてもよい。図１０に示すクエリ補完テーブルのうちの最初の３つ、５１６−１〜５１６−３は、それぞれ、部分クエリ「ｈ」、「ｈｏ」、「ｈｏｔ」についてのものである。次の２つのクエリ補完テーブル９１０−１および９１０−２は、それぞれ、部分クエリ長７および１０を有する、部分クエリ「ｈｏｔ ｐｏｔ」および「ｈｏｔ ｐｏｔａｔｏ」に対応する。図７のステップ７１０を再び参照すると、ステップ７１０によって部分的に形成されるループの各繰り返しで、部分クエリの長さは、最初、長さがＣ−１に達するまでは、１文字のステップで増加し、次に、部分クエリの長さは、履歴クエリの全長に達するまで、Ｃ文字のステップで増加する。
【００５８】
それぞれのチャンクされたクエリ補完テーブルのエントリ９１１は、エントリ９１１内のクエリ補完フィンガープリント９１２によって識別されるクエリ文字列の、（得点９１６によって表される）ランク付け値に従って順序付けされる。Ｃ文字未満を有する部分クエリについては、関連するクエリ補完テーブル５１６内のクエリの数は、予測として返すクエリの数を表してもよい、第１の値（例えば、１０または２０）である。一部の実施形態では、それぞれのチャンクされたクエリ補完テーブル９１０内のエントリ９１１の最大数（例えば、１０００〜１０，０００の数）は、第１の値よりもかなり大きい。それぞれのチャンクされたクエリ補完テーブル９１０は、通常のクエリ補完テーブルの数十〜数百倍の場所を要してもよい。したがって、それぞれのチャンクされたクエリ補完テーブル９１０は、含まれるエントリ数（ｐ）が、チャンクされたクエリ補完テーブルに一致するプレフィックス部分を有する、許可された履歴クエリのすべて、またはほとんどすべてに対応する数であって、同時に、ユーザが指定した部分クエリに対する、予測クエリのリストを生成するために、過度の待ち時間が発生するほど長くないような数となるように、サイズが決定される。
【００５９】
クエリ補完テーブル５１６、９１０およびフィンガープリント−テーブルマップ５１０が、履歴クエリの組から生成された後は、これらの同じデータ構造（またはそのコピー）が、ユーザが入力した部分クエリに対応する、クエリの予測された組を識別するために使用される。図９に示すように、ユーザが入力した部分クエリは、最初に、部分クエリ９０２全体に対してまたは部分クエリのプレフィックス部分９０４に対して（部分クエリの長さによって決定される）、ハッシュ関数５１４を適用することによって、クエリフィンガープリント５１５または９０８にマッピングされる。クエリフィンガープリント５１５または９０４は、次に、フィンガープリント−テーブルマップ５１０内のクエリフィンガープリントのルックアップを実行することによって、クエリ補完テーブル５１６または９１０にマッピングされる。最後に、最大Ｎ個の予測クエリの、順序付けされた組が、識別されたクエリ補完テーブルから抽出される。部分クエリの長さがチャンクサイズ未満の場合、予測クエリの順序付けされた組は、識別されたクエリ補完テーブル内の上位Ｎ個のクエリである。部分クエリの長さがチャンクサイズ以上である場合、識別されたクエリ補完テーブルは、部分クエリのサフィックスに一致する上位Ｎ個の項目について検索される。クエリ補完テーブル９１０内のエントリは、ランクの大きい順に順序付けされているため、一致するエントリを探す検索プロセスは、最上部から開始されて、返すべき所望の数（Ｎ）の予測が取得されるまで（例えば、１０個）、またはクエリ補完テーブル９１０の末尾に到達するまで、継続される。「一致」は、部分クエリのサフィックス９０６が、エントリ９１１内のサフィックス９１４の対応する部分と同じ場合に、存在する。例えば、図１０を参照すると、１文字のサフィックス＜ｐ＞は、サフィックス＜ｐｏｔ＞および＜ｐａｌ＞を有する、エントリ９１１−３および９１１−４にそれぞれ一致する。長さ０を有する空のサフィックス（ヌル文字列とも呼ばれる）は、クエリ補完テーブル内のすべてのエントリに一致し、したがって、部分クエリのサフィックス部分がヌル文字列の場合、テーブル内の上位Ｎ項目が、予測クエリとして返される。
【００６０】
上に述べたように、部分ＵＲＬに対応する、予測されたＵＲＬの順序付けされた組を識別するためのデータ構造およびプロセスは、ユーザが入力した部分クエリに対応する、予測クエリの順序付けされた組を識別するための、上記のデータ構造およびプロセスと同様である。ＵＲＬとクエリ文字列とは異なる用途を有してもよいが、両方とも、ユーザによる部分入力の後で値が予測することができる文字または記号の列として取り扱われてもよい。一部の実施形態では、ＵＲＬ補完テーブル１２３４（図１２）およびＵＲＬフィンガープリント−テーブルマップ１２３６（図１２）の組の構築に使用される、「履歴ＵＲＬ」の組は、特定のユーザによって、あるいは、ユーザの組またはコミュニティによって入力されたＵＲＬを含んでもよい。別の実施形態では、ＵＲＬ補完テーブルおよびＵＲＬフィンガープリント−テーブルマップの組の構築に使用される、「履歴ＵＲＬ」の組は、文書データベース（検索エンジンの文書データベースなど）に記憶された文書のＵＲＬを含んでもよい。
【００６１】
図１１は、本発明の一部の実施形態による、ブラウザおよびツールバーを使用する場合のユーザへの表示を示す。ブラウザ１１０２は、部分クエリ＜ｈｏｔ＞の入力を示すテキスト入力ボックス１１０６を含む、ツールバー１１０４を含む。部分クエリの検出、および、クエリサーバからの予測クエリの最終的な受信に応答して、予測が、ユーザによる選択が可能となるように、表示領域１１０８内に表示される。同様に、図示されていないが、アドレスバー１１１０内への部分ＵＲＬのユーザ入力の検出に応答して、予測されたＵＲＬの順序付けされた組が、ユーザによる選択が可能となるように、アドレスバー１１１０のすぐ下または隣の表示領域（図示せず）内に表示されてもよい。
【００６２】
図１２を参照すると、上記の方法およびデータ構造を実装する検索エンジン１２０２の実施形態は、１つまたは複数の処理ユニット（ＣＰＵ）１２０４と、１つまたは複数のネットワークまたはその他の通信インタフェース１２０６と、メモリ１２０８と、これらの構成要素を相互接続するための１つまたは複数の通信バス１２１０とを含む。検索エンジン１２０２は、任意選択として、ディスプレイ装置１２１４とキーボード１２１６とを備えるユーザインタフェース１２１２を含んでもよい。メモリ１２０８は、高速ランダムアクセスメモリを含んでもよく、さらに、１つまたは複数の、磁気または光記憶ディスクのような不揮発性メモリも含んでもよい。メモリ１２０８は、ＣＰＵ１２０４から離れた場所に配置された大容量記憶装置を含んでもよい。メモリ１２０８は、以下の要素、あるいは、そのような要素のサブセットまたはスーパーセットを記憶してもよい。
・さまざまな基本システムサービスを処理するための、およびハードウェア依存タスクを実行するための手続きを含む、オペレーティングシステム１２１８。
・インターネット、その他のワイドエリアネットワーク、ローカルエリアネットワーク、メトロポリタンエリアネットワークなどの、１つまたは複数の通信インタフェース１２１６（有線または無線）を介して、検索エンジン１２０２を他のコンピュータに接続するために使用されるネットワーク通信モジュール（または命令）１２２０。
・完全なクエリまたは部分クエリを受信して、検索結果と、予測クエリと、予測された検索結果とを返す、クエリサーバ２１０。
・部分クエリを受信して、クエリまたはＵＲＬの予測の順序付けされた組を返す、予測サーバ２１２。
【００６３】
一部の実施形態では、クエリサーバ２１０は、以下の要素、またはそのような要素のサブセットを含む。情報を受信および送信するためのクライアント通信モジュール２１６と、完全な検索クエリを受信して応答するための、クエリ受信・処理および応答モジュール２１８と、完全な検索クエリを受信して応答するための、部分クエリ受信・処理および応答モジュール２２０と、複数のユーザのそれぞれのユーザプロファイル１２２８を含むユーザ情報データベース１２２６からのユーザ情報にアクセスするための、ユーザ情報および処理モジュール２２２と、以前に発行されたクエリに関する情報を記憶するためのクエリログ２２４と、ＵＲＬログまたはデータベース２２５。一部の実施形態では、クエリサーバ２１０は、これらのモジュールのサブセットを含む。一部の実施形態では、クエリサーバ２１０は、追加のモジュールを含む。
【００６４】
一部の実施形態では、予測サーバ２１２は、以下の要素、あるいは、そのような要素のサブセットまたはスーパーセットを含む。
・部分クエリを受信するための、クエリ受信モジュール（または命令）１２３０。
・クエリ補完テーブル５１６、９１０およびクエリフィンガープリント−テーブルマップ５１０を生成するための、クエリ／ＵＲＬ補完テーブルビルダ（または命令）１２３２；一部の実施形態では、クエリ／ＵＲＬ補完テーブルビルダ１２２３は、さらに、ＵＲＬ補完テーブル１２３４およびＵＲＬフィンガープリント−テーブルマップ１２３６も生成する。
・予測クエリまたはＵＲＬの組を取得するための、予測モジュール（または命令）１２３８。
【００６５】
一部の実施形態では、予測サーバ２１２は、さらに、以下のうちの１つまたは複数も含む。
・特定のユーザプロファイル情報に少なくとも部分的に基づいて予測クエリの組を選択するための、パーソナライズモジュール（または命令）１２４０。
・特定のクエリに関連付けられた概念を判定するための、概念モジュール（または命令）１２４２。
・ユーザのコミュニティに関連付けられた特性の組を判定するための、コミュニティ特性モジュール（または命令）１２４４。
・受信されたクエリまたはクエリタームの代替のスペリングを識別するための、スペリングモジュール（または命令）１２４６。
・さまざまな記号言語要素のための表音表示を提供する、言語辞書１２４８。
【００６６】
一部の実施形態では、ユーザ情報処理モジュール２２２、パーソナライズモジュール１２４０、概念モジュール１２４２、コミュニティ特性モジュール１２４４、およびスペルモジュール１２４６のうちの、１つまたは複数は実装されない。実装された場合、ユーザ情報処理モジュール２２２のユーザプロファイル１２２８は、予測クエリまたはＵＲＬを選択または順序付けするために適した情報を含んでもよい。例えば、ユーザプロファイル１２２８は、特定のユーザにとって関心のある情報のカテゴリを識別してもよい。ユーザプロファイル１２２８は、さらに、ユーザが属している、またはユーザが関連している、ユーザのコミュニティに関連付けられた情報も含んでもよい。ユーザ情報処理モジュール２２２は、個人情報をコミュニティ情報とマージして、ユーザプロファイル１２２８を生成してもよい。
【００６７】
実装された場合、概念モジュール１２４２は、履歴クエリを、ユーザプロファイル１２２８内の情報と照合するために適した情報の概念またはカテゴリにマッピングする。同様に、概念モジュール１２４２は、例えば、履歴ＵＲＬに対応する文書のコンテンツ内の情報の主要な概念、主題、またはカテゴリの組を判定することによって、履歴ＵＲＬを情報の概念またはカテゴリにマッピングするように構成されてもよい。概念モジュール１２４２によって識別される概念、主題、またはカテゴリ情報は、クエリ補完テーブルまたはＵＲＬ補完テーブルのエントリ内に、または、クエリ／ＵＲＬ補完テーブルによって識別されるクエリレコードまたはＵＲＬレコード内に記憶されてもよい。部分クエリまたはＵＲＬを処理する場合、予測クエリまたはＵＲＬの組は順序付けし直されてもよく、それにより、概念、主題、またはカテゴリ情報が、要求中のユーザのユーザプロファイル内の情報に一致する予測クエリまたはＵＲＬは、概念またはカテゴリ情報が、要求中のユーザのユーザプロファイル内の情報に一致しない予測クエリまたはＵＲＬよりも、予測クエリまたはＵＲＬのリスト内で上位に配置されてもよい。
【００６８】
別の実施形態では、概念モジュール１２４２は、部分クエリ内の１つまたは複数のタームを、それらのタームの概念またはカテゴリマッピングに従って、１つまたは複数の置換タームにマッピングするように構成されてもよい。予測クエリの順序付けされた組が、１つまたは複数の置換タームを含む部分クエリに対して生成され、次に、それらの予測クエリは、別個に、または、ユーザによって入力されたとおりの部分クエリを使用して生成された結果とマージされて、ユーザに送信される。
【００６９】
図１２は、一実施形態における検索エンジン１２０２の内部構造を示す。一部の他の実施形態では、検索エンジン１２０２は、スループットと信頼性を向上するために、複数のサーバを使用して実装されてもよいことが理解されるべきである。例えば、クエリログ２２４は、別個のサーバ上に実装されてもよく、このサーバは、検索エンジン１２０２のサーバである他のサーバと通信を行い、連携して動作する。別の例として、クエリ／ＵＲＬ補完テーブルビルダ１２３２、および／または、言語辞書１２４８は、独立したサーバまたはコンピューティング装置（例えば、図２の、順序付け組ビルダ２４２および言語辞書２４４）内に実装されてもよい。
【００７０】
本明細書における説明は、検索要求者から離れた場所に配置された文書とともに使用するように設計された検索エンジンに関して行ったが、本明細書で開示された概念は、他の検索環境に等しく適用可能であることが理解されるべきである。例えば、本明細書で説明されたのと同様の技術が、クエリまたは検索の実行対象となる任意のタイプの情報リポジトリ（例えば、アドレス帳、製品情報データベース、ファイルサーバ、ウェブサイトなど）に対するクエリに適用されてもよい。したがって、「検索エンジン」という用語は、そのようなすべての用途を包含するように広く解釈されるべきである。
【００７１】
図１３を参照すると、上記の方法を実装するクライアントシステム１３００の実施形態は、１つまたは複数の処理ユニット（ＣＰＵ）１３０２と、１つまたは複数のネットワークまたはその他の通信インタフェース１３０４と、メモリ１３０６と、これらの構成要素を相互接続するための１つまたは複数の通信バス１３０８とを含む。検索エンジン１３００は、任意選択として、ディスプレイ装置１３１２および／またはキーボード１３１４を備えるユーザインタフェース１３１０を含んでもよい。メモリ１３０６は、高速ランダムアクセスメモリを含んでもよく、さらに、１つまたは複数の、磁気または光記憶ディスクのような不揮発性メモリも含んでもよい。メモリ１３０６は、ＣＰＵ１３０２から離れた場所に配置された大容量記憶装置を含んでもよい。メモリ１３０６は、以下を記憶してもよい。
・さまざまな基本システムサービスを処理するための、およびハードウェア依存タスクを実行するための手続きを含む、オペレーティングシステム１３１６。
・１つまたは複数の通信ネットワークインタフェース１３０４と、インターネット、その他のワイドエリアネットワーク、ローカルエリアネットワーク、メトロポリタンエリアネットワークなどの、１つまたは複数の通信ネットワークとを介して、クライアントシステム１３００を他のコンピュータに接続するために使用されるネットワーク通信モジュール（または命令）１３１８。
・検索クエリの入力のためにユーザとインタフェースし、検索結果を表示するための、ブラウザまたはツール１３２０。
・検索アシスタント１３２２。
【００７２】
一部の実施形態では、検索アシスタント１３２２は、ブラウザ／ツール１３２０から分離しており、他の実施形態では、検索アシスタントは、ブラウザ／ツール１３２０内に組み込まれている。
【００７３】
検索アシスタント１３２２は、以下の要素、またはそのような要素のサブセットを含んでもよい。検索クエリの入力を監視し、検索エンジンに送信する部分クエリを選択するための入力および選択監視モジュール（または命令）１３２４と、部分検索クエリおよび最終検索クエリを検索エンジンに送信するための送信モジュール（または命令）１３２６と、予測クエリを受信するための予測クエリ受信モジュール（または命令）１３２８と、予測された検索結果を受信するための、予測された検索結果受信モジュール（または命令）１３３０と、予測および結果を表示するための表示モジュール（または命令）１３３２と、検索結果を受信するための、任意選択の検索結果受信モジュール（または命令）１３３４。最終的な（すなわち、完全な）クエリの送信、完全なクエリに対する検索結果の受信、およびそのような結果の表示は、ブラウザ／ツール１３２０、検索アシスタント１３２２、またはそれらの組み合わせによって処理されてもよい。検索アシスタント１３２２は、さらに、部分的および完全なＵＲＬを処理するための、対応する機能の組も提供してもよく、それらのＵＲＬは、上記と同じ要素によって、または類似した要素の組によって処理されてもよい。検索アシスタント１３２２は、多くの方法で実装されてもよい。例えば、検索アシスタント１３２２は、ブラウザの一部として、ツールバーの一部として、デスクトップアプリケーションの一部として、または、（ジャバスクリプト（Ｊａｖａ（登録商標）Ｓｃｒｉｐｔ）などの）実行可能命令を使用してウェブページ上に実装されてもよい。少なくとも、検索アシスタントは、部分クエリ情報を検索システムに送信する。検索アシスタントは、さらに、予測された結果の表示と、表示された予測結果のユーザによる選択とを可能にしてもよい。
【００７４】
図１２および図１３では別個のモジュールまたは構成要素として示されているが、さまざまなモジュールまたは構成要素は、検索エンジンまたはクライアントのいずれかの内部に、配置または共同配置されてもよい。例えば、一部の実施形態では、予測サーバ３１２および／または様々なクエリ補完テーブル５１２および／または９１０の部分は、クライアントシステム２０２上に存在するか、あるいは、検索アシスタント２０４の部分を形成する。例えば、一部の実施形態では、最も人気のある検索についての、クエリ補完テーブルおよびフィンガープリント−テーブルマップは、クライアントシステム２０２に定期的にダウンロードされてもよく、それにより、少なくとも部分的に入力されたクエリまたはＵＲＬについて、完全なクライアントベースのクエリまたはＵＲＬ入力予測が提供されてもよい。
【００７５】
別の実施形態では、検索アシスタント２０４は、ユーザの以前の検索およびＵＲＬ入力に少なくとも部分的に基づいて、検索またはＵＲＬ予測を行うための予測サーバ３１２のローカルバージョンを含んでもよい。代わりとして、またはそれに加えて、ローカル予測サーバ３１２は、検索エンジンまたはリモート予測サーバからダウンロードされたデータに基づいて予測を生成してもよい。さらに、クライアントアシスタント２０４は、ローカルに生成された予測の組とリモートで生成された予測の組とを、ユーザに提示するためにマージしてもよい。結果は、例えば、２つの組を交互配置することによって（by interleaving the two sets）、または、ユーザによって以前に発行されたクエリにバイアスをかけて、それらのクエリが、予測クエリの組み合わせリストの最上位の方に配置または挿入される傾向があるようにしながら、それらの組をマージすることによってなど、いくつかの方法のうちのいずれかでマージされてもよい。一部の実施形態では、クライアントアシスタント２０４は、ユーザにとって重要と見なされるクエリを、予測の組の中に挿入する。例えば、ユーザによって頻繁に発行されるが、検索エンジンから取得された組の中に含まれていないクエリが、予測の中に挿入されてもよい。
【００７６】
上述のテクニックは、フィンガープリント−テーブルマップ５１０が生成されるプロセスを変更することによって、アルファベット文字体系に主として基づく言語以外の言語に適合させられてもよい。例えば、上述のテクニックは、表語文字（logograms）（語の部分または語全体を表す記号）、表意文字（ideograms）（抽象的概念を図式的に表す記号）、表音文字（phonetics）（アルファベットおよび音節文字表において使用される書記素におけるような、特定の音を表す記号）、および意味−表音複合文字（semantic-phonetic compounds）（記号の意味を表すかまたは示唆する意味要素と、発音を示すかまたは示唆する音声要素とを含む記号）などの、記号またはピクトグラムを有する言語に適用されてもよい。本明細書での目的のために、アルファベットではない記号またはピクトグラム、すなわち文字は、一般に、「表意文字（ideographs）」と呼ぶ。
【００７７】
主として非アルファベットの言語に上述のテクニックを適合させるための、一部の実施形態を示すために、日本語が使用される。日本語は、文字体系の混合を使用し、漢字、仮名、ローマ字、アラビア数字、および漢数字を含む。漢字は、いくつかの源に由来する「文字」である。一部の漢字は中国語に由来し（通常、２つ以上の発音を有し、発音は意味または意味論に基づく）、一部は中国語から採用されたものであり（通常、「標準の」発音を有する）、一部は日本語のためにのみ作られたものである。仮名は、平仮名（主として、日本語固有の語またはかなり昔に中国語から借用された語を表すために使用される）および片仮名（主として、外来語または擬音語を書くため、あるいは、テキストに「魅力的な」外観を与えるために使用される）という、２つの日本語音節文字表（Japanese syllabaries）の表音文字である。一部の例では、漢字表現は、特定の活用を示すための、および／または、発音を補助するための、１つまたは複数の送り仮名（trailing Kana characters）を含む。ローマ字は、ローマ字アルファベットの文字である。
【００７８】
平仮名および片仮名のそれぞれは、４６文字を含み、大部分が、母音と、母音−子音の組み合わせとからなる。日本語テキストは、一般に、１つまたは複数の漢字文字についての仮名音声表示を入力し、次に、それが漢字表現に変換されることによって、コンピュータ内に入力される。一入力方法によれば、（コンピュータキーボードからの）ローマ字文字の列が、中間テキスト入力領域内に入力されるか、または表示される。仮名文字を生成する各ローマ字文字の列が認識されるにつれて、中間テキスト入力領域内で、仮名文字が、表示されたローマ字文字に取って代わるか、または表示される。例えば、ローマ字列「ｔｉ」をタイプすると、平仮名「ち」が生成される。所望の数の仮名文字が入力された後で、ユーザは、仮名表現を、所望のテキスト領域内に直接配置してもよく、あるいは、ユーザ始動の操作によって、仮名表現のすべてまたは部分を漢字表現に選択的に変換してもよい。例えば、ローマ字列「ｔｉ」に続いて「ｋｅ」をタイプすると、英語「ｓａｌｍｏｎ」の仮名表現である、平仮名「さけ」が生成される。この仮名文字列は、「スペースバー」の押下、またはファンクションキーの押下などの、ユーザ始動の操作によって、「ｓａｌｍｏｎ」の漢字表現、つまり「鮭」に変換されてもよい。一部の例では、仮名から漢字への変換は、自動的に試みられる。しかしながら、多くの場合、変換にはユーザの何らかの介入が必要とされる。仮名による同じ音声表示が、複数の漢字表現にマッピングされる場合があるため、ユーザは、一般に、複数の漢字表現から選択する必要がある。例えば、（ローマ字文字の列「ｈｏ」およびそれに続く「ｓｉ」によって生成される）表音文字列「ほし」は、「端」（ｔｉｐまたはｅｎｄを意味する）、「橋」（ｂｒｉｄｇｅを意味する）、および「箸」（ｃｈｏｐｓｔｉｃｋｓを意味する）という、３つの漢字表現と整合性がある。その上、１つの漢字表現は、複数の音声表示を有する場合がある。例えば、「鮭」（ｓａｌｍｏｎを意味する）は、「さけ」（ローマ字文字の列「ｔｉ」およびそれに続く「ｋｅ」によって生成される）と、「しやけ」（ローマ字文字の列「ｓｉ」、「ｙａ」、および「ｋｅ」によって生成される）という音声表示を、少なくとも有する。
【００７９】
クエリを入力するユーザは、一般に、クエリ入力領域内に表音文字の列を入力することによって、各クエリタームを入力する。表音文字列は、通常、クエリが形成されるにつれて、表意文字に変換される。クエリは、通常、１つまたは複数の表意文字、および／または、１つまたは複数の表音文字を、所望の順序で含む。予測サーバは、１つまたは複数の表意文字からなる部分クエリに基づいて検索クエリを予測するだけでなく、ユーザが音声表示を入力するにつれて、表意文字の部分表音文字入力を使用して予測を行うことが望ましい。したがって、そして、他の組み合わせに加えて、０以上の表意文字とそれに続く１つまたは複数の表音文字とからなる部分クエリ入力に対して、予測が行われる。一部の実施形態では、これらの予測は、フィンガープリント−テーブルマップの作成に使用される図７のプロセスを、言語の特定の文字体系を考慮に入れて修正することによって達成されてもよい。修正されたプロセスは、１つまたは複数の表音文字による表意文字の入力を考慮する。図１４を参照すると、表意文字と表音文字との両方を含み、表意文字と音声表示との間に複数のマッピングが存在してもよい言語文字体系を考慮した、フィンガープリント−テーブルマップの作成のためのプロセスが示されている。当業者は、図１４に示す方法が、他の言語に拡張されてもよいことを容易に認識するであろう。
【００８０】
処理対象の言語によるクエリを有する、許可された履歴クエリのリスト（例えば、図５の、許可された履歴クエリのリスト５０６）から、クエリが選択される（１４０２）。一部の実施形態では、この許可された履歴クエリのリストは、図５を参照した説明に従って生成される。最初のクエリ単位が識別される（１４０４）。クエリ単位は、いくつかの方法で決定されてもよい。一部の実施形態では、クエリ単位は、語または概念を表す、認識された順序での、１つまたは複数の漢字文字（および、活用または発音のために使用される適切な平仮名）からなる。一部の例では、さまざまな語または概念を表す漢字文字は、区切り文字（例えば、空白文字）なしで、漢字文字の１つの文字列として表される。一部の例では、クエリ単位は、１つの漢字文字である。一部の例では、クエリ単位は、１つまたは複数の漢字、および／または、１つまたは複数の表音文字である。一部の実施形態では、表意文字が識別される前に、前処理が適用される（例えば、「ｈｔｔｐ：／／」の除去）。任意の以前のクエリ単位と現在のクエリ単位、現在のクエリ単位に対応する完全なクエリ、およびクエリの頻度を示すエントリが、テーブル内に作成される（１４０６）。他の実施形態では、ランク付けのために使用されるその他の情報が記憶される（例えば、日付／時刻値、または、２つ以上の要因に基づいて計算されたランク付け得点）。
【００８１】
現在のクエリ単位が表意文字である場合、表意文字と整合性がある音声表示が識別される（１４０８）。一実施形態では、表意文字と整合性がある、少なくとも１つの可能な音声表示を返すために、辞書（例えば、図２の、言語辞書２４２）が調べられる。以前の文字に現在の文字を追加することによって、完全な音声表示を構築するために表音文字が入力されると、それら表音文字の増加加算（the incremental addition）を表すインクリメンタルクエリ文字列が、各音声表示から判定される（１４１０）。例えば、現在のクエリ単位として「鮭」が識別されている場合、音声表示のうちの１つは（上述のように）「さけ」である。音声表示「さけ」は、２つの表音文字（すなわち、「さ」および「け」）を含むため、第１のインクリメンタルクエリ文字列は、第１の表音文字からなる「さ」となり、第２のインクリメンタルクエリ文字列は、第１および第２の文字からなる「さけ」となる。各インクリメンタルクエリ文字列（および、任意の以前の表意文字およびクエリ単位（存在する場合）を含む）、インクリメンタルクエリ文字列に対応する完全なクエリ、およびクエリの頻度についてのエントリが、テーブル内に作成される（１４１２）。一部の例では、クエリ単位は、２つ以上の表意文字、あるいは、１つまたは複数の表意文字と、それに続く１つまたは複数の表音文字とを含む。各インクリメンタルクエリ文字列が構築されるにつれて、表音文字の完全な列が、それらの対応する表意文字によって置き換えられる。例えば、クエリ単位が「認める」（すなわち、ａｃｋｎｏｗｌｅｄｇｅを意味し、仮名文字「める」は活用語尾を提供する）である場合、１つの可能な完全な表音文字列は「みとめる」である（ここで、「みと」は、漢字「認」の仮名表示である）。インクリメンタルクエリ文字列が構築されるにつれて（例えば、「み」および「みと」）、表音文字の特定の列が認識された場合（例えば、「みと」）、その特定の列は適切な表意文字（例えば、「認」）によって置き換えられ、後続のインクリメンタルクエリ文字列（例えば、「認め」および「認める」）のために使用される。
【００８２】
クエリが完全に処理されていない場合（１４１４−ｎｏ）、次のクエリ単位が識別されて（１４１６）、上記のように処理される。現在のクエリが完全に処理された場合（１４１４−ｙｅｓ）、処理のためにまだ残されているクエリがさらにあるならば、（１４１８−ｎｏ）、別のクエリが選択されて、上記のように処理される。プロセスは、処理されるべきすべてのクエリが処理されるまで（１４１８−ｙｅｓ）継続される。
【００８３】
上述のプロセスは、図１５および図１６を参照することによって、よりよく理解することができる。例示的クエリ文字列１５０２は、第１の表意文字１５０４（すなわち、ｓａｌｍｏｎを表す漢字「鮭」）と、第２の表意文字１５０６（すなわち、Ｊａｐａｎを表す漢字「日本」）とを有するクエリを表す。第１の表意文字１５０４は、第１の音声表示１５０８（すなわち、「ｓａｋｅ」と発音される「さけ」）と、第２の音声表示１５１０（すなわち、「ｓｈａ−ｋｅ」と発音される「しゃけ」）とを有する。同様に、第２の表意文字１５０６は、第１の音声表示１５１２（すなわち、「ｎｉｈｏｎ」と発音される「にほん」）と、第２の音声表示１５１４（すなわち、「ｎｉｐｐｏｎ」と発音される「にっぽん」とを有する。
【００８４】
図１６は、図１５のクエリ文字列１５０２を処理するための一方法を示す。最初に、クエリ文字列１５０２の第１のクエリ単位が識別され（すなわち、「鮭」）、部分クエリ単位１６０６と、完全なクエリ１６０８と、クエリ頻度１６１０とを示す、対応するエントリ１６０２が、テーブル１６０４内に作成される。一部の実施形態では、クエリのランク付けの基となる、クエリに関連付けられたその他のまたは追加の情報が含まれてもよい。「鮭」の音声表示が識別され（すなわち、「さけ」および「しゃけ」）、インクリメンタルクエリ文字列が判定されて、対応するエントリがテーブル１６０４内に作成される。例えば、第１の音声表示「さけ」は、インクリメンタル文字列「さ」および「さけ」を含む。したがって、インクリメンタルクエリ文字列「さ」に対応するエントリ１６１２が作成され、インクリメンタルクエリ文字列「さけ」に対応するエントリ１６１４が作成される。第２の音声表示に関連付けられたインクリメンタルクエリ文字列についてのエントリも作成される（例えば、１６１６、１６１８、および１６２０）。次に、次のクエリ単位が識別され（すなわち、「日本」）、両方の表意文字を含む（そして、第１の表意文字の音声表示は何も含まない）対応するエントリ１６２２が、テーブル１６０４内に作成される。最後に、「日本」の音声表示が判定されて、対応するエントリが作成される（例えば、エントリ１６２４）。上記のプロセスは、クエリ単位が１つまたは２つ以上の表意文字を含む場合にも、同様に適用されることに注意されたい。（例えば、表意文字の末尾に追加された）表音文字がクエリ内に見つかった場合、その表音文字は、見つかったときに部分クエリ内に含められる（そして、対応するエントリがテーブル１６０４内に作成される）。上記のプロセスは、入力が部分的に入力されたＵＲＬである場合も、同様に実施される。ＵＲＬは、事前定義された区切り文字（例えば、「＞」および「／」）を含み、空白文字を含まない、クエリタームの列と同等である。
【００８５】
様々な所望のクエリ補完テーブルおよびフィンガープリント−テーブルマップが、図７および図８を参照して上述したように、クエリの処理中または処理後に作成されてもよい。
【００８６】
クエリの表意文字を実現するために入力される様々な表音文字列を考慮に入れることにより、音声表示の列が完成する前に予測が行われてもよい。０以上の表意文字と１つまたは複数の表音文字とを含む、検索要求者から受信された部分クエリから、クエリ補完テーブルが識別される。
【００８７】
本発明のさまざまな実施形態を、英語および日本語を使用して説明したが、本明細書で説明した概念を他の言語に拡張する方法を、当業者は容易に認識するであろう。例えば、入力文字の可能性のある列は、許可された履歴クエリと、それらの可能性のある入力文字列に基づいて作成された、様々なクエリ補完テーブルと、フィンガープリント−テーブルマップとから決定されてもよい。
【００８８】
さまざまな図面のうちの一部は、いくつかの論理ステージを特定の順序で示すが、順序に依存しないステージは、順序付けし直されてもよく、その他のステージは、組み合わされるか、または切り離されてもよい。一部の再順序付けまたはその他のグループ化については具体的に述べたが、その他については、当業者にとって明白であり、したがって代替方法の網羅的なリストは示していない。さらに、ステージは、ハードウェア、ファームウェア、ソフトウェア、またはそれらの任意の組み合わせで実装されてもよいことが認識されるべきである。
【００８９】
以上の記載は、説明の目的のために、特定の実施形態に関して行った。しかし、上述の具体的な説明は、開示された厳密な形態で本発明が網羅されたり限定されたりすることを意図するものではない。上記の教示を考慮すれば多くの変更および変形が可能である。実施形態は、本発明の原理とその実際的な適用例とを最もよく説明するために、そしてそれにより、当業者が、本発明およびさまざまな実施形態を、企図された特定の使用に適したさまざまな変更とともに、最もよく利用できるようにするために、選択され説明されたものである。
【技術分野】
【０００１】
本発明は、一般に、コンピュータネットワーク（例えば、コンピュータシステムの分散システム）内の文書を検索する（locating）ための検索エンジンの分野に関し、特に、非表音記号（non-phonetic symbols）を含む言語でのユーザの要求を予測することによって、所望の検索を高速化するためのシステムおよび方法に関する。
【背景技術】
【０００２】
検索エンジンは、ワールドワイドウェブ（ＷＷＷ）上の文書、またはインターネットのコンピュータ上に記憶された文書などの、大規模な文書データベース内の文書を検索するための強力なツールを提供する。文書は、ユーザによって発行される検索クエリに応答して検索される。検索クエリは、１つまたは複数の検索タームからなっていてもよい。
【０００３】
クエリを入力する一方法においては、ユーザは、すべての検索タームが入力されるまで検索タームを連続的に追加することによって、クエリを入力する。クエリのすべての検索タームが入力されたことをユーザが合図すると、クエリは検索エンジンに送信される。例えば、キーボード上のエンターキーを押すことによって復改文字を入力すること、または、グラフィカルユーザインタフェース上の「検索」ボタンをクリックすることなどによる、クエリの完成を合図する代替の方法を、ユーザは有していてもよい。クエリが検索エンジンによって受信されたら、検索エンジンは、検索クエリを処理し、検索クエリに応答して文書を検索し、文書のリストをユーザに返す。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
アルファベット文字体系（alphabetic writing systems）に主として基づく言語ではない言語においては、多くの場合、クエリの言語要素を作成するために、キーボードから文字列が入力される。この方法によるクエリの入力は、時間がかかる可能性がある。
【０００５】
クエリは、一般に、クエリが完成したことをユーザが合図するまで、検索エンジンに送信されないため、ユーザが全ての検索クエリ（the full search query）を完成させている間に時間が経過する。このプロセスを高速化するシステムおよび方法を有することが望ましい。
【課題を解決するための手段】
【０００６】
一実施形態においては、表意文字と表音文字（ideographs and phonetic characters）とを有する言語のためのクエリ補完（query completion）を提案する方法は、検索要求者から部分クエリを受信するステップを含む。部分クエリは、完全なクエリ（complete query）の部分である。１つまたは複数の表意文字を有する少なくとも１つの文字列を含む、予測クエリの組（a set of predicted queries）が、予測され、ランク付け基準に従って順序付けされる。順序付けされた予測クエリの組は、検索要求者に伝えられる。
【０００７】
検索要求者は、予測クエリの順序付けされた組から、それぞれのクエリを選択してもよく、次に、クエリの補完を指示してもよい。検索エンジンは、クエリを処理して、検索結果の組を生成する。あるいは、検索要求者は、完全なクエリが入力されるまで、または、予測クエリの新しい組が送信されて検索要求者に提示されるまで、クエリ情報の入力を継続してもよい。
【０００８】
本発明の前述の実施形態、および追加の実施形態は、以下の、本発明のさまざまな態様の詳細な説明を、図面と組み合わせた場合の結果として、より明確に理解される。複数の図面にわたる同様の参照番号は、対応する部分を意味している。
【図面の簡単な説明】
【０００９】
【図１】本発明の一部の実施形態による、クエリを予測するためのプロセスを示す。
【図２】本発明の一部の実施形態による、検索システムのブロック図を示す。
【図３】本発明の一部の実施形態による、検索アシスタントのプロセスを示す。
【図４】本発明の一部の実施形態による、クエリ入力を受信し、それに対する応答を作成するためのプロセスを示す。
【図５】本発明の一部の実施形態による、フィンガープリント−テーブルマップの作成および使用に関連する情報の流れを示す。
【図６】本発明の一部の実施形態による、入力文字列の関連性を示す。
【図７】本発明の一部の実施形態による、履歴クエリを処理するためのプロセスを示す。
【図８】本発明の一部の実施形態による、履歴クエリの処理において使用される例示的テーブルの部分を示す。
【図９】本発明の一部の実施形態による、サフィックスを使用したクエリ補完テーブルに関連するデータ構造を示す。
【図１０】本発明の一部の実施形態による、例示的クエリ補完テーブルの部分を示す。
【図１１】本発明の一部の実施形態による、例示的スクリーンショットを示す。
【図１２】本発明の一部の実施形態の実装に適した、検索エンジンを示す。
【図１３】本発明の一部の実施形態の実装に適した、クライアントを示す。
【図１４】本発明の一部の実施形態による、表意文字と表音文字とを含む履歴クエリを処理するためのプロセスを示す。
【図１５】本発明の一部の実施形態による、選択された表意文字のための複数の音声表示を示す。
【図１６】本発明の一部の実施形態による、表音文字と表意文字とを含む例示的クエリ補完テーブルの部分を示す。
【発明を実施するための形態】
【００１０】
本発明の一実施形態においては、ユーザが完全なクエリの入力を完了する前に、ユーザのクエリの部分が検索エンジンに送信される。検索エンジンは、クエリの送信された部分を使用して、ユーザの最終的なクエリを予測する。これらの予測は、ユーザに送り返される。予測のうちの１つが、ユーザの意図するクエリである場合、ユーザは、クエリの入力を完了することなく、その予測クエリを選択することができる。一部の実施形態では、選択されたクエリが検索エンジンに送信され、検索エンジンは、選択されたクエリに対応するクエリ結果の組を返す。
【００１１】
図１は、クライアントシステム１０４と検索エンジン１０６とを含む、本発明の例示的実施形態を示す。ユーザが検索クエリを入力するとき、ユーザの入力は、クライアントシステムによって監視される（１０８）。ユーザが検索クエリの完成を合図する前に、ユーザのクエリの部分が、クライアントシステム１０４から検索エンジン１０６に送信される（１１０）。クエリの部分は、いくつかの文字、１つの検索ターム、または２つ以上の検索タームであってもよい。一部の実施形態では、部分入力は、インターネット・エンジニアリング・タスク・フォース（Ｉｎｔｅｒｎｅｔ Ｅｎｇｉｎｅｅｒｉｎｇ Ｔａｓｋ Ｆｏｒｃｅ）によって公布されたＲＦＣ１７３８に記載されているような、ユニフォーム資リソースロケータ（ＵＲＬ）としばしば呼ばれる、コンテンツ位置識別子の形態であってもよい。ＵＲＬは、コンピュータおよびコンピュータネットワーク内の資源を識別するために使用されることが可能である。ＵＲＬは、さらに、文書、フォルダ、またはサービスなどの、コンピュータ上でローカルに利用できる資源を識別するためにも使用されることが可能である。用語「ＵＲＬ」は、本明細書内では、以下に限定されないが、インターネットアドレス、ＲＦＣ１７３８準拠アドレス、ならびに、多くのコンピュータシステムおよびローカルエリアネットワーク内で使用されているようなファイルパス名を含む、任意の形態のコンテンツ位置識別子を意味するために使用される。検索エンジン１０６は、部分クエリを処理のために受信し（１１２）、ユーザが企図した完全なクエリ（またはＵＲＬ）についての予測を行う（１１４）。予測は、ランク付け基準に従って順序付けされる。例えば、一部の実施形態では、より高い発行頻度を有するクエリは、より低い発行頻度を有するクエリよりも前に順序付けされる。検索エンジン１０６は、順序付けされた予測の作成を補助するために、いくつかのクエリ補完テーブル（以下にさらに詳細に記載する）を使用する。クエリ補完テーブルは、検索エンジン１０６によって受信された、以前に入力された検索クエリを使用して作成される。一部の実施形態では、以前のクエリは、ユーザのコミュニティからの検索クエリを含む。予測クエリは、クライアントシステム１０６に送り返され（１１６）、次に、ユーザに提示される（１１８）。予測クエリのうちの１つが、ユーザが所望のクエリとして意図したものである場合、ユーザは、この予測クエリを選択して、所望のクエリの入力を完了させることなく、先に進むことができる。予測クエリが、ユーザが考えていたものを反映していない場合、ユーザは、所望の検索クエリの入力を継続してもよい。
【００１２】
図２は、本発明の一部の実施形態による検索システム２００を例示し、さらに、以下の詳細な議論で参照される、さまざまな機能構成要素を示す。検索システム２００は、１つまたは複数のクライアントシステム２０２を含んでもよい。各クライアントシステム２０２は、検索アシスタント２０４を有する。クライアントシステム２０２は、通信ネットワーク２０６に接続される。通信ネットワーク２０６は、クライアントシステム２０２を検索エンジン２０８に接続する。検索エンジン２０８は、通信ネットワーク２０６に接続されたクエリサーバ２１０と、予測サーバ２１２と、クエリ処理コントローラ２１４とを含む。
【００１３】
クエリサーバ２１０は、クライアント通信モジュール２１６と、クエリ受信・処理および応答モジュール２１８と、部分クエリ受信・処理および応答モジュール２２０と、ユーザ情報処理モジュール２２２と、クエリログ２２４とが、すべて相互接続されたものを含む。一部の実施形態では、より少ない、および／または追加の、モジュールまたは機能が、クエリサーバ２１０内に含まれる。クエリサーバ２１０の部分として図２に示すモジュールは、一例示的実施形態で実行される機能を表す。予測サーバ２１２は、部分クエリ受信・処理および応答モジュール２２０と、順序付け組ビルダ（ordered set builder）２４２と、クエリログ２２４とに接続される。順序付け組ビルダ２４２は、クエリとＵＲＬ要求とのログから、順序付けされた予測クエリの組を作成するものであり、クエリログ２２４に接続される。一部の実施形態では、順序付け組ビルダ２４２は、ＵＲＬデータベース２２５にも結合され、一部の実施形態では、言語辞書２４４に結合される。言語辞書２４４は、さまざまな記号言語要素についての表音表示（phonetic representations）のような、特定の言語要素に関する情報を提供してもよく、あるいは、クエリまたはクエリタームに関連する、語または概念を提供してもよい。一部の実施形態では、順序付け組ビルダ２４２および言語辞書２４４は、予測サーバ２１２の部分である。そのような実施形態では、予測サーバ２１２は、クエリログ２２４およびＵＲＬデータベース２２５に直接接続される。
【００１４】
クエリ処理コントローラ２１４は、逆文書インデックス（inverse document index）２２８と、文書データベース２３０と、クエリキャッシュ２３２と、ＵＲＬデータベース２２５とに接続される。キャッシュ２３２は、インデックス２３４を含んでもよく、インデックス２３４の機能は、キャッシュされた結果２３６内のエントリを検出することである。キャッシュされた結果２３６は、識別されたクエリのためのキャッシュエントリ２３８と、予期されるクエリのためのキャッシュエントリ２４０とを含んでもよい。逆文書インデックス２２８と文書データベース２３０とは、一括して、文書データベースと呼ばれることがある。一部の実施形態では、「文書データベースを検索している」とは、指定された検索クエリまたはタームに一致する文書を識別するために、逆文書インデックス２２８を検索していることを意味する。
【００１５】
図では別個のブロックとして示されているが、図２は、機能要素の構造マッピングとしてよりも、むしろ、本発明の実施形態の機能的説明として意図されている。実際の実装は、さまざまな構成要素の中でグループ化された、または分割された機能要素を有してもよいことを、当業者は認識するであろう。例えば、クエリログ２２４は、クエリサーバ２１０とは別個のものであってもよい。一部の実施形態では、クエリログ２２４は、クエリログ情報の記憶および処理が主な機能である、１つまたは複数のサーバ上に記憶されてもよい。同様に、ＵＲＬデータベース２２５は、既知のＵＲＬに関する情報の記憶および処理が主な目的である、１つまたは複数のサーバ上に記憶されてもよい。
【００１６】
図３は、クライアントシステム２０２（図２）の検索アシスタント２０４に実装されてもよい、本発明の実施形態を示す。検索アシスタント２０４は、クライアントシステム１０４上での、ユーザによる検索クエリの入力を監視する（３０２）。一部の実施形態では、検索アシスタント２０４は、ブラウザウィンドウのアドレスフィールド内などへの、ユニフォームリソースロケータ（ＵＲＬ）のユーザ入力を監視する。ユーザは、検索クエリまたはＵＲＬを、ブラウザウィンドウ、検索ツール、またはその他の任意の入力機構を含む、いくつかの方法で入力してもよい。検索アシスタント２０４は、２つの異なるシナリオを識別してもよい。第１に、検索アシスタント２０４は、ユーザが入力文字列の完成を指示した場合、または提示された予測を選択した場合に、最終入力（３０２−最終入力）を受信または識別する。第２に、検索アシスタント２０４は、（以下に記載するように）ユーザが入力文字列の完成を指示する前に入力が識別された場合に、部分入力（３０２−部分入力）を受信または識別する。第３の、任意選択のシナリオ（以下にさらに詳細に記載する）では、検索アシスタント２０４は、指定された期間内に予測のうちの１つをユーザが選択しなかったことの通知を、判定または受信する。
【００１７】
最終入力または選択（３０２−最終入力）が検索クエリとして識別された場合、入力は、処理のために検索エンジン２０８に送信される（３０４）。検索エンジン２０８は検索結果の組を返し、その検索結果の組は、検索アシスタント２０４によって受信されるか（３０６）、または、ブラウザアプリケーションなどのクライアントアプリケーションによって受信される。検索結果のリストは、ユーザがさらなる調査のために文書のうちの１つを選択してもよいように、ユーザに提示される（例えば、視覚的に、または聴覚的に）。最終入力がＵＲＬである場合、要求は適切な文書ホストに送信され（３０４）、文書が、利用可能な場合は、返される（３０６）。応答が受信された後は（３０６）、ユーザの入力活動が再び監視される（３０２）。一部の実施形態では、ＵＲＬ要求は、ロギングのために検索エンジン２０８に送信され、そしてその要求は、適切な文書ホストに転送される。
【００１８】
最終入力は、ユーザが、キャリッジリターンまたは同等の文字を入力した場合、あるいは、検索クエリの入力中にユーザに提示されるグラフィカルユーザインタフェース（ＧＵＩ）内の検索ボタンを選択した場合などの、いくつかの方法で、検索アシスタント２０４によって識別されてもよく、あるいは可能であれば、検索クエリの入力中にユーザに提示される、可能なクエリの組のうちの１つを選択することによって識別されてもよい。当業者は、検索クエリの最終入力を合図するためのいくつかの方法を認識するであろう。
【００１９】
ユーザが最終入力を合図する前に、部分入力が識別されてもよい（３０２−部分入力）。部分入力は、いくつかの方法で識別されてもよい。検索クエリの場合、部分入力は、検索クエリの１つの検索ターム、複数の検索ターム、または検索タームの、事前定義された数の文字を含む。
【００２０】
一部の実施形態では、部分入力は、区切り文字またはその他の文字の入力（例えば、以下に限定されないが、引用文字、終止符、括弧文字、スラッシュ文字、矢印キーの検出、またはタブの入力）を検出することによって識別される。区切り文字の入力は、ユーザが前記入力の所望のタームまたは部分の入力を完了し、次の検索タームまたは部分に移動しつつあることを示してもよい。
【００２１】
一部の実施形態では、部分入力は、文字の所定数の入力を検出することによって識別されてもよい。それらの実施形態では、前記入力は、完全な入力よりも少ない数の文字を含むが、さらに、ユーザがすべての文字を入力してしまう前に部分入力を識別することが望ましい場合がある。このテクニックは、例えば、検索タームまたはＵＲＬが多数の文字を含む場合、または、前記文字の所定数が有用な予測をもたらすのに十分なだけ大きい場合に望ましい。
【００２２】
一部の実施形態では、部分入力は、一定期間内における入力文字の欠如が検出されることによって識別されてもよく、前記欠如は、ユーザによる間断を表す。前記間断は、ユーザが１つの検索タームを、または完全な文字列の部分を入力してしまったにもかかわらず、別のタームの入力を開始するために、スペースキー（またはその他の区切り文字）を入力していないことを表してもよく、あるいは、検索クエリは実際には完成したが、ユーザがまだそのように合図していないことを表してもよい。
【００２３】
部分入力が識別される方法にかかわらず、部分入力は、処理のために検索エンジン２０８に送信される（３０８）。部分検索クエリに応答して、検索エンジン２０８は、順序付けされた予測された検索クエリおよび／またはＵＲＬの組を返し（３１０）、その組は、ランク付け基準に従って順序付けされて、ユーザに提示される（３１２）。予測は、いくつかの方法でユーザに表示されてもよい。例えば、予測は、ドロップダウンウィンドウ内に、永続的または非永続的なウィンドウ内に（a persistent, or non-persistent window）、あるいは、その他の方法で表示されてもよい。一部の実施形態では、ユーザが以前に発行したクエリが、ユーザに視覚的に示されてもよい（例えば、ユーザ自身が以前に入力したクエリを強調表示することにより）。
【００２４】
一部の実施形態では、予測された検索クエリは、ユーザのコミュニティによる発行頻度に従って順序付けされる。一部の実施形態では、検索クエリは、少なくとも部分的には、クエリが発行された最後の時間／日付値に従って順序付けされる。一部の実施形態では、検索クエリは、ユーザパーソナライズ情報またはコミュニティ情報などの、パーソナライズ情報に従って順序付けされる。例えば、ユーザパーソナライズ情報は、ユーザにとって関心のある情報の、主題、概念、またはカテゴリに関する情報を含んでもよい。ユーザパーソナライズ情報は、ユーザによって直接提供されてもよく、あるいは、ユーザの許可により、ユーザの以前の検索またはブラウジング活動から推論されてもよく、あるいは、ユーザに関連付けられたグループ、またはユーザが（例えば、メンバーとして、または従業員として）属するグループに関する情報に、少なくとも部分的に基づいてもよい。予測された検索クエリの組は、最初に、事前定義された人気基準（popularity criteria）などの、第１のランク付け基準に従って順序付けされてもよく、次に、いずれかの予測された検索クエリがユーザのユーザパーソナライズ情報に一致する場合は、一致している予測された検索クエリを、予測された検索クエリの順序付けされた組の最上部に、または最上部により近いところに配置するように順序付けし直されてもよい。
【００２５】
当業者は、予測された検索クエリおよび／またはＵＲＬをユーザに提示する、いくつかの方法を認識するであろう。例えば、予測された検索クエリおよび／またはＵＲＬは、ドロップダウンメニュー内で提示されてもよい。予測クエリおよび／またはＵＲＬがユーザに提示される方法にかかわらず、ユーザは、予測のうちの１つが、意図する入力に一致すると判断した場合、クエリおよび／またはＵＲＬのうちの１つを選択してもよい。場合によっては、予測は、考慮されていなかった追加情報をユーザに提供してもよい。例えば、ユーザは、検索ストラテジの一部として１つのクエリを考えているかもしれないが、予測された結果を見て入力ストラテジを変更してもよい。組が提示されたら（３１２）、ユーザの入力が再び監視される。ユーザが予測のうちの１つを選択した場合（３０２−最終）、要求は、検索要求として検索エンジン２０８に、またはＵＲＬ要求として資源ホストに、適宜送信される（３０４）。要求が送信された後は、ユーザの入力活動が再び監視される（３０２）。上述のように、一部の実施形態では、ＵＲＬ要求は、ロギングの目的のために、検索エンジン２０８に送信される。
【００２６】
他方、指定された期間内に、予測のうちの１つをユーザが選択していない場合、ユーザは、最初に返された予測の中に、満足のいく予測を見いださなかった可能性がある。例えば、ユーザの意図する入力は、順序付けされた予測の組の中に含まれるための十分に高いランク付け値を有さなかった。したがって、一部の任意選択の実施形態では、指定された期間（例えば、５秒または１０秒）内に、予測のうちの１つをユーザが選択していない場合（３０２−タイムアウト）、別の予測の組に対する要求が、検索エンジン２０８に送信される（３１８）。後続の予測の組（the subsequent set of predictions）は、以前に発行された組よりも低いランク付け値を有する予測を含んでもよい。あるいは、第２の組の中の予測を識別するために、第２の基準の組が使用されてもよく、ここで、第２の基準の組は、第１の予測の組を選択およびランク付けするために使用された第１の基準の組とは異なるものである。例えば、２つの組のうちの一方は、要求者に関する個人情報を考慮に入れた選択基準を使用してもよく、もう一方の組は、使用しなくてもよい。一部の任意選択の実施形態では、後続の予測の１つまたは複数の組を要求するために、その他のトリガが使用されてもよい。例えば、ユーザ始動の動作（例えば、「タブ」キー、矢印キー、ファンクションキーなどの押下）が、後続の組の要求を発生させてもよい。一部の実施形態では、いずれの予測された結果が検索要求者にすでに伝えられたかを識別するために、検索要求者に関連付けられた情報がサーバにおいて維持される。一部の実施形態では、クライアントは、いずれの結果が検索要求者にすでに伝えられたかを示す情報を、後続の要求に対する要求の中に含める。そのような一実施形態においては、予測サーバ２１２は、この情報を使用して、後続の予測された結果から、以前に予測された結果のすべてを、または、以前に予測された結果のサブセットを除外する。別の実施形態では、以前に予測された結果に関する情報は、予測サーバ２１２が、要求者の部分クエリに一致する、追加の予測された結果を識別することが可能な場合に限り、追加の、または異なる結果を生成するために、予測サーバ２１２によって使用される。一部の実施形態では、後続の予測の組をトリガとして（triggering）、検索要求者の、ローカルに記憶された検索クエリを使用して予測が作成されるのに対して、他の実施形態では、後続の予測の組は、要求者の部分クエリに一致するものがもしあれば、ユーザのコミュニティの履歴クエリに基づいて生成される予測と、検索要求者の履歴検索クエリ（存在する場合）とに基づいて生成される予測の、両方を含む。
【００２７】
一部の実施形態では、予測された結果の１つまたは複数の組は、クライアントにおいてローカルにキャッシュされる。検索要求者が、（例えば、バックスペースキーを押して一部の文字を削除することにより）以前の部分入力を反映するように現在のクエリを修正した場合、部分入力が検索エンジンに送信される代わりに、以前の部分入力に関連付けられた、予測された結果の組がクライアントキャッシュから取り出されて、ユーザに再び提示される。
【００２８】
一部の実施形態では、検索エンジン２０８は、任意選択として（optionally）、予測された結果を返してもよい（３２０）。この動作は、予測の受信（３１０）とオーバーラップしてもよく、図３では３２０への点線によって示されている。予測された結果が提示され（３２０）、ユーザの監視が再開される（３０２）。ユーザへの提示は、いくつかの方法で実現されてもよい。例えば、結果は、非永続的ウィンドウの部分内に、ポップアップウィンドウ内に、現在の表示の部分内に、またはユーザインタフェースの部分内に表示されてもよい。クエリの入力のため、および予測された結果の提示のために使用されるウェブページは、予測された結果の表示を容易にするための、および、予測された結果のうちのいずれかのユーザによる選択に応答するための、ジャバスクリプト（Ｊａｖａ（登録商標）Ｓｃｒｉｐｔ）あるいはその他の埋め込みコードまたは命令を含んでもよい。その他の方法も考えられる。予測された結果は、予測クエリまたはＵＲＬのうちの１つまたは複数である要求に基づいて返されたであろう文書または情報に対応する。一部の実施形態では、予測された結果は、予測された結果に対応する１つまたは複数の位置におけるコンテンツの断片(snippets)を含んでもよい。一部の実施形態では、予測された結果は、予測された結果に対応する１つまたは複数の位置における、１つまたは複数のウェブページまたはその他のコンテンツの、１つまたは複数のサムネイルを含んでもよい。一部の実施形態では、結果は、予測クエリの１つまたは複数に基づく検索結果である。例えば、一部の実施形態では、提示される結果（３２０）は、予測クエリまたは予測されたＵＲＬのうちの１つまたは複数に関連する、１つまたは複数の文書であってもよい。したがって、ユーザは、要求（例えば、検索要求またはＵＲＬ要求）の入力を完了する前に、所望の要求に一致する、提示される予測された結果を有してもよい。そのような状況においては、ユーザは、所望の結果を取得するために、入力を完了する必要がなかったため、ユーザから見た処理待ち時間は、事実上、０未満に減少する（reduced to less than zero）。
【００２９】
図４は、一部の実施形態に従って、検索エンジン２０８が入力を受信した場合に、検索エンジン２０８内で発生する動作を示す。検索エンジン２０８は、入力を受信し、入力が最終入力を示すか、または部分入力を示すかを判定する（４０２）。検索エンジン２０８は、受信された入力が最終クエリであると判定した場合（４０２−最終クエリ）、クエリに関連する検索結果がキャッシュ２３２内に存在するかどうかを判定する（４０４）。関連する検索結果がキャッシュ２３２内にある場合（４０４−ｙｅｓ）、それらの結果がクライアント１０４に返される（４０６）。他方、検索結果がキャッシュ内にない場合（４０４−ｎｏ）、クエリに関連する検索結果が取得され（４０８）、クライアント１０４に返される（４０６）。一部の実施形態では、ＵＲＬ要求は、完成した場合、検索エンジン２０８によって受信されず、その理由は、検索アシスタントが要求を資源ホストに送信するためである。一部の実施形態では、ＵＲＬ要求は、（ＵＲＬデータベース内への記憶などの）トラッキングの目的のために、検索エンジン２０８によって受信され、そしてその要求は、検索エンジン２０８によって資源ホストに転送される。
【００３０】
検索エンジン２０８は、受信された入力が部分入力であったと判定した場合（４０２−部分）、部分入力に対応する、順序付けされた一致の組（a set of ordered matches）を決定して（４１０）、その組をクライアント１０４に送信する（４１２）。以下で説明するように、一部の実施形態では、クライアント１０４に送信される順序付けされた一致の組は、順序付けされた一致の、多くの事前計算された組のうちの１つである。以下の動作は部分クエリに関して説明するが、同じテクニックが、ＵＲＬの部分入力に同様に適用可能である。一部の実施形態では、返される順序付けされた一致の組は、クエリのみに関連する。一部の実施形態では、順序付けされた一致の組は、ＵＲＬのみに関連する。また、一部の実施形態では、順序付けされた一致の組は、クエリおよびＵＲＬの両方に関連する。
【００３１】
一部の実施形態に従って、検索エンジン２０８が、順序付けされた一致のいずれの組を返すかを決定する方法を理解するための補助として、順序付けされた組がどのように作成され使用されるかの説明から開始することが役に立つ。図５は、部分的に入力されたクエリに対応するクエリを予測するために使用される、履歴クエリ（すなわち、以前に発行されたクエリ）に関連付けられたデータ構造の組を示す。検索エンジンまたはユーザ入力予測システムは、さらに、部分的に入力されたＵＲＬに対応するＵＲＬを予測するために使用される、履歴ＵＲＬ（すなわち、以前に発行されたＵＲＬ）に関連付けられた、類似したデータ構造の組も含んでもよい。
【００３２】
図５を参照すると、履歴クエリログ５０２が１つまたは複数のフィルタ５０４によってフィルタリングされて、許可された履歴クエリのリスト（authorized historical queries list）５０６が作成される。順序付け組ビルダ５０８は、特定の基準に基づいて、許可された履歴クエリのリスト５０６から、１つまたは複数のフィンガープリント−テーブルマップ（fingerprint-table map）５１０を作成する。部分クエリが送信された場合（図３、３０８）、その部分クエリは、検索エンジン２０８において、部分クエリ５１３として受信される。部分クエリ５１３にハッシュ関数５１４が適用されて、フィンガープリント、すなわち、ｂビットの２進値（例えば、６４ビットの数）が作成される。適切なフィンガープリント−テーブルマップ５１０（例えば、５１０−１）が、フィンガープリント（例えば、５１５）について検索され、そのフィンガープリントに関連付けられたクエリ補完テーブル５１６が識別される。クエリ補完テーブル５１６は、部分クエリ５１３に関連する、予測クエリの順序付けされた組を提供する。
【００３３】
適切なフィンガープリント−テーブルマップ５１０は、ユーザまたは要求に関連付けられた、いくつかの異なる要因に基づいて選択されてもよい。適切なフィンガープリント−テーブルマップ５１０を選択するために使用される情報は、ユーザまたは検索アシスタント２０４によって提供されたプロファイル情報から、または、要求そのものから収集された情報（例えば、言語）から、または、ユーザ情報処理モジュール２２２内の、ユーザに関連付けられた情報から、または、その他の情報源から得られるものであってもよい。例えば、フィンガープリント−テーブルマップは、ユーザまたは検索要求者に関連付けられた特定の接続情報（例えば、装置タイプ、接続速度、接続タイプなど）に基づいて選択されてもよい。一部の実施形態では、予測の数、またはそれぞれのクエリ予測の長さは、そのような接続情報に依存してもよい。小さなユーザインタフェースを有する装置は、より少ない数の予測を、および／または、より少ない数のタームを有するクエリを受信してもよい。クエリタームは、それに関連付けられた重要度係数を有してもよく、より低い重要度係数を有するタームは、より高い重要度係数を有するタームよりも前に、クエリから切り捨てられてもよい。一部の実施形態では、フィンガープリント−テーブルマップ５１０の異なる組は、ユーザのそれぞれのカテゴリのために使用されてもよく、それにより、ユーザに関連付けられた１つまたは複数のカテゴリまたはトピックに従ってバイアスがかけられた、予測された結果が提供されてもよい。例えば、特定のウェブサイトから受信した部分検索クエリは、同じウェブサイトから受信した、または、該特定のウェブサイトに類似していると見なされるウェブサイトのグループから受信した履歴クエリから生成された、フィンガープリント−テーブルマップの組を使用して、予測された結果にマッピングされてもよい。同様に、個々のユーザは、そのユーザの許可により、ユーザに関する情報、またはユーザに関連付けられたグループに関する情報を指定するユーザプロファイルを有してもよく、その「パーソナライズ情報」は、そのユーザのための結果を予測する際に使用するフィンガープリント−テーブルマップのそれぞれの組を識別するために使用されてもよい。フィンガープリント−テーブルマップ５１０の複数の組は、同じクエリ補完テーブル５１６を指してもよく、クエリ補完テーブル５１６は、フィンガープリント−テーブルマップ５１６よりもはるかに多くの記憶領域を占めるため、フィンガープリント−テーブルマップ５１０の複数の組を追加することに関連するオーバヘッドは少量とすることができることに注意されたい。
【００３４】
一部の実施形態では、フィンガープリントが作成される前に、部分クエリへの何らかの前処理が発生する。一実施形態では、完全な検索タームのうちの１つまたは複数を辞書内のエントリと比較することによって、部分クエリ内の顕著なミススペル語が識別され、訂正される。正しいスペルの語を含むクエリから予測された１つまたは複数の結果は、ユーザに返される予測された結果とマージされる。別の例では、一般的なプレフィックス情報が削除されてもよい（例えば、「ｈｔｔｐ：／／」または「ｗｗｗ．」）。一部の実施形態では、クエリ内のタームが分析され、検索ターム内に組み入れられた、特定の情報カテゴリを示す概念が抽出される（例えば、「技術」、「食物」、「音楽」、または「動物」）。抽出された概念のうちの１つまたは複数に関連するクエリから予測された１つまたは複数の結果は、ユーザに返される予測された結果とマージされる。
【００３５】
履歴クエリログ５０２は、一定期間にわたって検索エンジン２０８によって受信された、以前に発行されたクエリの記録を含む。一部の実施形態では、クエリは、特定のユーザからのものである。一部の実施形態では、クエリは、同じワークグループに属している、同じ言語を使用している、同じ国または地理的領域に関連付けられたインターネットアドレスを有しているなどの、少なくとも１つの類似した特性を共有するユーザのコミュニティからのものである。コミュニティの選択により、以前に発行されたクエリのプールが特定され、そこから予測が引き出される。異なるコミュニティは、異なる予測の組を生成する傾向がある。
【００３６】
履歴クエリログ５０２は、さらに、それぞれの発行されたクエリに関連付けられた情報も含んでもよい。一部の実施形態では、クエリ情報は、クエリが発行または受信された日付と時刻を含む。一部の実施形態では、クエリ情報は、クエリの発行元のインターネットプロトコル（ＩＰ）アドレスを含む。一部の実施形態では、クエリ情報は、クエリの固有ソース識別子（例えば、ユーザのマシン上に記憶されたクッキー（ｃｏｏｋｉｅ）からの値であって、その値は特定の検索アシスタント２０４に関連付けられている）を含む。固有識別子は、いかなる特定のユーザも直接には識別しないが、ブラウザまたはツールバーの特定のインストールに関連付けられてもよい。一部の実施形態では、ユーザは、ユーザ情報処理モジュール２２２を使用してアクセスすることができる特定のパーソナライズ特徴について、固有識別子を使用した直接の識別を許可してもよい。
【００３７】
一部の実施形態では、フィンガープリント値はクエリと関連付けられる。フィンガープリント値は、クエリ文字列にハッシュ関数を適用することによって計算されてもよい。一部の実施形態では、クエリ言語または、ユーザ嗜好に従ってユーザまたは検索アシスタントにより提供されてもよいその他の情報（例えば、ユーザの特定の嗜好を示す識別またはプロファイル情報）などの、その他のタイプのメタデータが、クエリと関連付けられて記憶されてもよい。一部の実施形態では、メタ情報は、クエリ内のタームの分析から収集されたカテゴリまたは概念情報を含む。クエリが記録されている期間は、調節可能であり、それは、記憶容量と、可能な予測精度との間のトレードオフを表す。より長い期間は、コミュニティ全体にわたるクエリの人気がより正確に反映されるが、これにはより多くの記憶領域が必要とされる。他方、長い期間にわたる人気のランク付けは、現在の出来事についての一時的な人気は反映しない可能性がある。
【００３８】
１つまたは複数のフィルタ５０４は、さらなる処理のために許可されるクエリを決定するために使用される。例えば、フィルタは、さまざまな基準に基づいて特定のクエリを除去してもよい。一部の実施形態では、特定の数よりも多くの個別発行者（unique submitters）から受信されていないクエリが、許可された履歴クエリのリスト５０６内に含められるのを、プライバシーフィルタ５０４が防止する。これは、各クエリに関連付けられた固有識別子（存在する場合）を調べて、少なくともｎ人の個別発行者によって発行されたクエリのみを識別することによって実現されてもよく、ここで、ｎは、プライバシーに対する関心（privacy concerns）に基づいて選択される数（例えば、３人または５人の固有発行者）である。一部の実施形態では、フィルタ５０４は、まれにしか発行されず、したがってユーザによって選択されそうにないクエリを、除去するフィルタを含む。一部の実施形態では、フィルタ５０４は、クエリ内の１つまたは複数の特定のキーワードの存在などの、いくつかの異なる要因に基づいて、および／または、クエリに対応する検索結果または文書のコンテンツに基づいて、特定のクエリが含まれるのを阻止する、妥当性フィルタ５０４を含む。その他のタイプのフィルタが容易に想像されてもよい。例えば、許可された履歴クエリのリスト５０６が、最近発行されたクエリを表すように、フィルタは、特定の過去時点（historical point）よりも前に発行されたクエリを阻止してもよい。何が最近と見なされるかは、実施形態により異なる（例えば、時間、日、週、月、または年）。さらに別の例では、多数の人為的に生成されたクエリまたはＵＲＬの発行によって、クエリ／ＵＲＬ予測システムがスプーフィングされる（being spoofed）のを防止するために、アンチスプーフィングフィルタ５０４が使用されてもよい。例えば、アンチスプーフィングフィルタ５０４は、同じユーザまたは同じクライアントコンピュータから受信した、複数の同じクエリまたはＵＲＬの発行を、除去してもよい。
【００３９】
１つまたは複数のフィルタ５０４によって、履歴クエリログ５０２がフィルタリングされた後の結果は、許可された履歴クエリのリスト５０６、すなわち、提案されるクエリ補完としてユーザに返される資格があるクエリのリストである。許可された履歴クエリのリスト５０６は、履歴クエリ５０６−１〜履歴クエリ５０６−ｑを含み、ここで、ｑは、許可された履歴クエリのリスト５０６内に含まれるクエリの数を表す。ｑの値は、履歴クエリログ５０２からフィルタリングして得られたクエリ（queries filtered）の総数以下であってもよい。例えば、所定のしきい値未満の頻度を有する、フィルタリングして得られたクエリは、無視されてもよい。一部の実施形態では、新しい許可された履歴クエリのリスト５０６が、毎時間、毎夜、毎週、またはその他の周期などで、定期的に構築される。一部の実施形態では、現在の許可された履歴クエリのリスト５０６は、適切なフィルタリングの後、クエリログ２２４への最近の入力に基づいて更新される。
【００４０】
許可された履歴クエリのリスト５０６（例えば、５０６−１）内の各クエリは、クエリと、その頻度と、任意選択としてメタ情報とを含む。クエリは、文字列であってもよい。頻度情報は、一定期間にわたっての、クエリが発行された回数を示す。上述のように、個別検索者がクエリを発行した回数を計数するために、固有識別子が使用されてもよい。それぞれのユーザが複数の検索アシスタントを使用する場合があり、また、一部のクエリは固有識別子を含まない場合があるため、頻度の数は、検索クエリを発行している個別ユーザの実際の数を表さない可能性がある。それにもかかわらず、クエリの頻度は、クエリの人気の代用として働いてもよい。一部の実施形態では、許可された履歴クエリのリスト５０６は、クエリに基づいてアルファベット順に順序付けされる。他の実施形態では、許可された履歴クエリのリスト５０６は、クエリの頻度に基づいて順序付けされる。
【００４１】
メタ情報は、履歴クエリログ５０２に関連して上述した、メタ情報に類似した情報を含んでもよい（例えば、位置または言語情報）。一部の例では、同じクエリが、履歴クエリログ５０２内に、クエリ文字列では異ならないが、メタ情報では異なるエントリを有する。したがって、特定の許可された履歴クエリ５０６−１についてのメタ情報は、同じクエリについての異なるメタ情報を示してもよい。例えば、ヨーロッパとアジアのような、２つの異なる位置から発行されたクエリについてのメタ情報は、両方の位置を、クエリのソース位置として示す。メタ情報は、さらに、クエリを発行したユーザのタイプを示す、ユーザプロファイリング情報も示してもよい。当業者は、特性の共通の組（例えば、言語または位置）によって関連付けられるクエリを分類またはグループ化するために役立つ可能性がある、さまざまなタイプのメタ情報を認識するであろう。一部の実施形態では、クエリタームが分析され、特定の情報カテゴリに関連付けられる。例えば、「犬」および「品種」を含む検索クエリは、「犬」または「動物」カテゴリに関連付けられる。一部の実施形態でのメタ情報は、このカテゴリ情報を含む。一部の実施形態では、許可された履歴クエリのリスト５０６内の１つのエントリについてのメタ情報は、複数のクエリから生成される（例えば、クエリが発行された最後の日付／時刻値としてクエリの日付／時刻を提供することによって）。
【００４２】
順序付け組ビルダ５０８は、許可された履歴クエリのリスト５０６を使用して、フィンガープリント−テーブルマップの組５１０−１〜５１０−ｔを構築し、ここで、ｔは構築されるフィンガープリント−テーブルマップ５１０の数を表す。予測クエリを分類するために所望される方法の数に応じて、任意の数のフィンガープリント−テーブルマップ５１０が構築されてもよい。それぞれのフィンガープリント−テーブルマップ５１０は、順序付けされた予測の組を複数含み、それぞれの組は特定の部分クエリにマッピングされている。フィンガープリント−テーブルマップ５１０は、メタ情報内に見いだすことができるような情報の特性に基づいて、異なっている。例えば、各言語について１つのフィンガープリント−テーブルマップ５１０があってもよい（例えば、英語のクエリについて１つ、フランス語のクエリについて１つ、日本語のクエリについて１つ）。同様に、地理的領域について、さまざまなフィンガープリント−テーブルマップ５１０が作成されてもよい。別の例として、特定のネットワークまたは特定の個人グループ（例えば、会社）からのクエリなどの、特定のＩＰアドレスまたはアドレスグループからのクエリから、さまざまなフィンガープリント−テーブルマップ５１０が作成されてもよい。メタ情報を使用してさまざまなフィンガープリント−テーブルマップ５１０を作成することにより、検索者の特性に類似した特性を有するユーザに基づいた予測が可能になり、それにより、正しい予測の可能性が増加する。一部の実施形態では、異なるフィンガープリント−テーブルマップ５１０は、クエリについての異なるランク付け基準に基づいてもよい（例えば、頻度、最後の日付／時刻、パーソナライズカテゴリまたは特性など）。一部の実施形態では、異なるフィンガープリント−テーブルマップ５１０は、ユーザ入力のタイプ（すなわち、クエリ文字列またはＵＲＬ）に基づく。
【００４３】
フィンガープリント−テーブルマップ５１０−１を例として使用すると、それぞれのフィンガープリント−テーブルマップ５１０は、複数のエントリ５１２−１〜５１２−ｆを含み、ここで、ｆはフィンガープリント−テーブルマップ５１０−１内のエントリ数を表す。どの特定のフィンガープリント−テーブルマップ５１０においても、そのエントリ数は、異なる部分クエリ（それに対して、予測サーバ２１２は予測を返す）の数に依存する。
【００４４】
フィンガープリント−テーブルマップ５１０−１内の各エントリ（例えば、５１２−２）は、フィンガープリント（例えば、フィンガープリント（２）５１５）と、クエリ補完テーブル（例えば、クエリ補完テーブル（２）５１６）とを含む。フィンガープリント−テーブルマップ５１０は、フィンガープリント（例えば、フィンガープリント（２）５１５）をクエリ補完テーブル（例えば、クエリ補完テーブル（２）５１６）に関連付ける働きをする。
【００４５】
フィンガープリント（２）５１５は、部分クエリのフィンガープリント値を表す。フィンガープリント（２）５１５は、例えば、部分クエリにハッシュ関数を適用して、ｂビットの２進値（例えば、６４ビットの数）を作成することによって計算されてもよい。したがって、部分クエリ５１３のフィンガープリントに一致するフィンガープリント（例えば、フィンガープリント５１５）を探して、フィンガープリント−テーブルマップ５１０−１が検索することができる。
【００４６】
クエリ補完テーブル（２）５１６は、クエリ補完フィンガープリント５１８−１〜５１８−ｎのリストを含み、ここで、ｎは、クエリ補完テーブル（２）５１６内のクエリ補完フィンガープリントの数を表す。一部の実施形態では、ｎは、検索アシスタント２０４に返される、予測クエリの数を表す（例えば、１０個の予測クエリ）。他の実施形態では、ｎ個未満が返される。一部の実施形態では、ｎは、順序付けされたクエリの組において返される結果の数よりも大きい。一部の実施形態では、ｎは、返される数の２倍であり、最初のｎ／２個は、順序付けされた、予測クエリの第１の組として提供され、２番目のｎ／２個は、順序付けされた、予測クエリの後続の組として提供される（例えば、第２の１０個の予測クエリの組が、特定の条件が満たされれば、第１の１０個の組に続いて送信される）。一部の実施形態では、クエリ補完テーブル５１６は、各クエリ補完フィンガープリント５１８についての得点を含む。得点は、クエリ補完テーブル５１６内の項目を、得点の高い順に順序付けするために使用される。一部の実施形態では、得点は、クエリ補完テーブルの永続的な部分であり、他の実施形態では、得点は、クエリ補完テーブル５１６の形成が完了した後、削除されるか、または、保持されない。
【００４７】
各クエリ補完フィンガープリント５１８は、完全なクエリに関連付けられたフィンガープリント値である。クエリ補完フィンガープリント５１８（例えば、５１８−２）は、関連するクエリレコード５２０にマッピングされる。クエリレコード５２０は、完全なクエリのクエリ文字列を含む、クエリ文字列５２２を含む。この方法は、複数のクエリ補完テーブル５１２内のエントリが同じクエリ文字列５２２を参照することを容易にし、しかも、実際のクエリ文字列が１つの位置に記憶されることのみを要求する（例えば、クエリ文字列５２２）。ただし、一部の実施形態では、クエリ文字列５２２は、クエリ補完テーブル５１２内に、クエリ補完フィンガープリント５１８の代わりに記憶されてもよい。一部の実施形態では、ＵＲＬ文字列についてのクエリレコード５２０は、ＵＲＬに関連付けられたタイトルを表すＵＲＬタイトル５２４を含む。一部の実施形態では、ＵＲＬに関連付けられた追加情報が、情報５２６内に提供される。
【００４８】
一部の実施形態では、クエリ補完テーブル５１２−２は、フィンガープリント５１５に関連付けられた部分クエリに関連する、ｎ個のクエリの順序付けされたリストである。リストは、（発行の頻度、日付／時刻などのような）さまざまなランク付け基準に従って順序付けされてもよい。一部の実施形態では、ランク付け基準は、発行の頻度と日付／時刻との両方などの、２つ以上の要因を考慮に入れたものであってもよく、そのためには、２つ以上の要因のそれぞれを考慮に入れた得点またはランクを各クエリについて生成する。単純な例では、日付／時刻が２４時間前よりも古い履歴クエリは、クエリのランク付け得点に値「１」を提供してもよく、日付／時刻が過去２４時間以内である履歴クエリは、クエリのランク付け得点に値「２」を提供してもよい。この例では、それぞれの許可された履歴クエリのランクの決定において、最近の履歴クエリは、より古い履歴クエリよりもより重く重み付けされる。
【００４９】
一部の実施形態では、順序付け組ビルダ５０６は、フィンガープリント−テーブルマップ５１０と、関連するクエリ補完テーブル５１２および／または９１０（図９）とを定期的に（例えば、毎時間、毎日、毎週）作成または更新し、それにより、予測サーバによって生成されるクエリおよび／またはＵＲＬ予測は、該当するユーザのコミュニティによって最近発行されたクエリおよび／またはＵＲＬと整合性のあるものに維持される。
【００５０】
図６を参照すると、部分クエリ「ｈｏ」６０２は、完全なクエリの組６０４を、部分クエリ６０２に関連するものとして有してもよい。完全なクエリの組６０４の最初の位置は、最も高い頻度値を有するクエリ（例えば、「ｈｏｔｍａｉｌ」）を含み、それに続く第２の位置は、次に高い頻度値を有するクエリ（例えば、「ｈｏｔ ｄｏｇｓ」）を含み、以下同様となる。この例では、所与の部分クエリへの、完全なクエリの関連性は、完全なクエリの先頭における部分クエリの存在によって決定される（例えば、文字「ｈｏ」によって、完全なクエリ「ｈｏｔｍａｉｌ」および「ｈｏｔｅｌｓ ｉｎ Ｓａｎ Ｆｒａｎｃｉｓｃｏ」は開始される）。他の実施形態では、完全なクエリの組６０６によって示されるように、関連性は、完全なクエリ内の任意の位置に配置された検索タームの先頭における部分クエリの存在によって決定される（例えば、文字「ｈｏ」は、「ｈｏｔｍａｉｌ」の先頭において、および、「ｃｈｅａｐ ｈｏｔｅｌｓ ｉｎ Ｃａｐｅ Ｔｏｗｎ」内の２番目の検索タームの先頭において見いだされる）。
【００５１】
クエリ補完テーブル５１２の組を作成するために、許可された履歴クエリ５０６内のクエリのうちの１つが選択される（図７、７０２）。一部の実施形態では、所望のメタ情報を有するクエリのみが処理される（例えば、英語によるクエリ）。選択されたクエリから、最初の部分クエリが識別される（７０４）。一実施形態では、最初の部分クエリは、選択されたクエリの最初の文字である（すなわち、クエリ文字列「ｈｏｔ ｄｏｇ ｉｎｇｒｅｄｉｅｎｔｓ」に対しては「ｈ」）。一部の実施形態では、部分クエリが識別される前に、前処理が適用される（例えば、「ｈｔｔｐ：／／」または「ｗｗｗ」の除去）。部分クエリと、部分クエリに対応する完全なクエリと、その頻度とを示すエントリが、テーブル内に作成される。他の実施形態では、ランク付けのために使用されるその他の情報が記憶される（例えば、日付／時刻値、または、２つ以上の要因に基づいて計算されたランク付け得点）。部分クエリが、クエリ全体を表さない場合、クエリ処理は完了していない（７０８−ｎｏ）。したがって、次の部分クエリが識別される（７１０）。一部の実施形態では、次の部分クエリは、前に識別された部分クエリに次の追加の文字を追加することにより識別される（すなわち、クエリ文字列「ｈｏｔ ｄｏｇ ｉｎｇｒｅｄｉｅｎｔｓ」に対しては「ｈｏ」）。識別（７１０）およびクエリ補完テーブルの更新（７０６）のプロセスは、クエリ全体が処理されるまで継続される（７０８−ｙｅｓ）。すべてのクエリがまだ処理されていない場合（７１２−ｎｏ）、次のクエリが選択され、すべてのクエリが処理されるまで処理される（７１２−ｙｅｓ）。一部の実施形態では、クエリ補完テーブルに項目が追加される場合、テーブル内の項目がランクまたは得点に従って順序付けされるように、項目は挿入される。別の実施形態では、すべてのクエリ補完テーブルは、テーブル構築プロセスの最後にソートされ、それにより、各クエリ補完テーブル内の項目は、クエリ補完テーブル内の項目のランクまたは得点に従って順序付けされる。さらに、１つまたは複数のクエリ補完テーブルは、テーブルが所定の数のエントリよりも多くを含まないように、切り捨てられてもよい。
【００５２】
図８を参照すると、クエリ文字列「ｈｏｔ ｄｏｇ ｉｎｇｒｅｄｉｅｎｔｓ」の最初の５文字の例示的処理が、テーブル８０２の８０４〜８１２において示されており、クエリ文字列「ｈｏｔｍａｉｌ」の最初の４文字の例示的処理が、８１４〜８２０において示されている。
【００５３】
一部の実施形態では、所与の部分クエリに対するクエリ補完テーブルは、所与の部分クエリに関連するｎ個の最も頻繁に発行されたクエリをテーブルから識別し、最高のランク（例えば、最高のランク付け得点または頻度）を有するクエリがリストの最上位になるように、それらをランク付けされた順序で配置することによって作成される。例えば、部分クエリ「ｈｏｔ」に対するクエリ補完テーブルは、完全なクエリ文字列８０８および８１８の両方を含む。ランク付けが頻度に基づく場合、「ｈｏｔｍａｉｌ」のクエリ文字列は、「ｈｏｔ ｄｏｇ ｉｎｇｒｅｄｉｅｎｔｓ」のクエリ文字列よりも上に現れ、その理由は、８１８内のクエリ文字列の頻度（すなわち、３００，０００）が、８０８内のクエリ文字列の頻度（すなわち、１００，０００）よりも大きいためである。一部の実施形態では、特定のウェブページに割り当てられた、ウェブページの組の中でのその重要性の指標を提供する値（例えば、ページランク（ＰａｇｅＲａｎｋ））が、ＵＲＬの人気度に与えられてもよい。したがって、予測の順序付けされた組がユーザに返される場合、選択される可能性がより高いクエリが最初に提示される。上述のように、メタ情報から引き出された他の値が、ランク付けのために使用されてもよい（例えば、日付／時刻値、またはパーソナライズ情報）。
【００５４】
図９および図１０を参照すると、一部の実施形態では、履歴クエリ文字列を、４文字などの、事前定義されたサイズＣの「チャンク」に分割することによって、クエリ補完テーブルの数が減らされる。Ｃ未満の長さの部分クエリに対するクエリ補完テーブルは、変化しない。長さが少なくともＣである部分クエリについては、部分クエリは、プレフィックス部分およびサフィックス部分の、２つの部分に分割される。サフィックス部分の長さＳは、部分クエリ（Ｌ） ｍｏｄｕｌｏ Ｃの長さに等しい。
Ｓ＝Ｌ ｍｏｄｕｌｏ Ｃ
ここで、Ｌは、部分クエリの長さである。プレフィックス部分の長さＰは、部分クエリの長さからサフィックスの長さを引いた長さである（Ｐ＝Ｌ−Ｓ）。したがって、例えば、１０文字の長さを有する部分クエリ（例えば、「ｈｏｔ ｐｏｔａｔｏ」）では、チャンクサイズＣが４の場合、サフィックスの長さＳは２、プレフィックスの長さＰは８となる。
【００５５】
図７のステップ７０６に示すプロセスを実行する場合の、部分クエリに対応するクエリ補完テーブルを識別または作成する工程を、図９に概念的に示す。図９は、クエリ補完テーブルの生成のため、および、ユーザが入力した部分クエリの処理時のルックアップのための、両方に使用されるプロセスを概略的に示す。部分クエリの長さが１つの「チャンク」のサイズＣ未満の場合、部分クエリは、例えば、ハッシュ関数５１４（図５）を使用することにより、クエリフィンガープリント５１５にマッピングされる。フィンガープリント５１５は、フィンガープリント−テーブルマップ５１０によって、クエリ補完テーブル５１６にマッピングされ、クエリ補完テーブル５１６は、クエリレコード５２０の組への、クエリ補完フィンガープリント５１８またはポインタを含む（クエリレコード５２０は、図５の、クエリ文字列５２２を含む）。
【００５６】
部分クエリの長さが、１つのチャンクのサイズＣで少なくともある場合、部分クエリ９０２は、プレフィックス９０４とサフィックス９０６とに分解され、それらの長さは、上述のように、チャンクサイズによって決定される。例えば、プレフィックス９０４にハッシュ関数５１４を適用することによって、プレフィックス９０４に対するフィンガープリント９０８が生成され、そのフィンガープリント９０８は、次に、フィンガープリント−テーブルマップ５１０によって、「チャンクされた」クエリ補完テーブル９１０にマッピングされる。チャンクされたクエリ補完テーブル９１０の各エントリ９１１は、クエリ補完フィンガープリント９１２だけでなく、サフィックスエントリ９１４も有するという点で、チャンクされたクエリ補完テーブル９１０の構造は、図５に示すクエリ補完テーブル５１６とは異なる。各エントリ９１１は、任意選択として、クエリ補完テーブル９１０内のエントリを順序付けするために使用される得点９１６も含んでもよい。サフィックスは、０〜（Ｃ−１）のいずれの値であってもよい長さＳを有し、部分クエリの、プレフィックス９０４内に含まれていない０以上の文字を含む。一部の実施形態では、履歴クエリについてのクエリ補完テーブルエントリ９１１を生成する場合、それぞれのチャンクされたクエリ補完テーブル９１０内に、履歴クエリに対応する１つのエントリのみが作成される。特に、その１つのエントリ９１１は、履歴クエリについての、最大Ｃ−１文字の長さとなり得るサフィックスを含む。他の実施形態では、特定の履歴クエリについて、それぞれのチャンクされたクエリ補完テーブル９１０内に、各別個のサフィックスについて１つの、最大Ｃ個のエントリが作成される。
【００５７】
図１０は、履歴クエリ「ｈｏｔ ｐｏｔａｔｏ」に対応するエントリ９１１を含む、クエリ補完テーブルの組を示す。この例では、チャンクサイズＣは、４に等しいと仮定している。他の実施形態では、チャンクサイズは、２、３、５、６、７、８、またはその他の任意の適切な値であってもよい。チャンクサイズＣは、経験的な情報に基づいて選択されてもよい。図１０に示すクエリ補完テーブルのうちの最初の３つ、５１６−１〜５１６−３は、それぞれ、部分クエリ「ｈ」、「ｈｏ」、「ｈｏｔ」についてのものである。次の２つのクエリ補完テーブル９１０−１および９１０−２は、それぞれ、部分クエリ長７および１０を有する、部分クエリ「ｈｏｔ ｐｏｔ」および「ｈｏｔ ｐｏｔａｔｏ」に対応する。図７のステップ７１０を再び参照すると、ステップ７１０によって部分的に形成されるループの各繰り返しで、部分クエリの長さは、最初、長さがＣ−１に達するまでは、１文字のステップで増加し、次に、部分クエリの長さは、履歴クエリの全長に達するまで、Ｃ文字のステップで増加する。
【００５８】
それぞれのチャンクされたクエリ補完テーブルのエントリ９１１は、エントリ９１１内のクエリ補完フィンガープリント９１２によって識別されるクエリ文字列の、（得点９１６によって表される）ランク付け値に従って順序付けされる。Ｃ文字未満を有する部分クエリについては、関連するクエリ補完テーブル５１６内のクエリの数は、予測として返すクエリの数を表してもよい、第１の値（例えば、１０または２０）である。一部の実施形態では、それぞれのチャンクされたクエリ補完テーブル９１０内のエントリ９１１の最大数（例えば、１０００〜１０，０００の数）は、第１の値よりもかなり大きい。それぞれのチャンクされたクエリ補完テーブル９１０は、通常のクエリ補完テーブルの数十〜数百倍の場所を要してもよい。したがって、それぞれのチャンクされたクエリ補完テーブル９１０は、含まれるエントリ数（ｐ）が、チャンクされたクエリ補完テーブルに一致するプレフィックス部分を有する、許可された履歴クエリのすべて、またはほとんどすべてに対応する数であって、同時に、ユーザが指定した部分クエリに対する、予測クエリのリストを生成するために、過度の待ち時間が発生するほど長くないような数となるように、サイズが決定される。
【００５９】
クエリ補完テーブル５１６、９１０およびフィンガープリント−テーブルマップ５１０が、履歴クエリの組から生成された後は、これらの同じデータ構造（またはそのコピー）が、ユーザが入力した部分クエリに対応する、クエリの予測された組を識別するために使用される。図９に示すように、ユーザが入力した部分クエリは、最初に、部分クエリ９０２全体に対してまたは部分クエリのプレフィックス部分９０４に対して（部分クエリの長さによって決定される）、ハッシュ関数５１４を適用することによって、クエリフィンガープリント５１５または９０８にマッピングされる。クエリフィンガープリント５１５または９０４は、次に、フィンガープリント−テーブルマップ５１０内のクエリフィンガープリントのルックアップを実行することによって、クエリ補完テーブル５１６または９１０にマッピングされる。最後に、最大Ｎ個の予測クエリの、順序付けされた組が、識別されたクエリ補完テーブルから抽出される。部分クエリの長さがチャンクサイズ未満の場合、予測クエリの順序付けされた組は、識別されたクエリ補完テーブル内の上位Ｎ個のクエリである。部分クエリの長さがチャンクサイズ以上である場合、識別されたクエリ補完テーブルは、部分クエリのサフィックスに一致する上位Ｎ個の項目について検索される。クエリ補完テーブル９１０内のエントリは、ランクの大きい順に順序付けされているため、一致するエントリを探す検索プロセスは、最上部から開始されて、返すべき所望の数（Ｎ）の予測が取得されるまで（例えば、１０個）、またはクエリ補完テーブル９１０の末尾に到達するまで、継続される。「一致」は、部分クエリのサフィックス９０６が、エントリ９１１内のサフィックス９１４の対応する部分と同じ場合に、存在する。例えば、図１０を参照すると、１文字のサフィックス＜ｐ＞は、サフィックス＜ｐｏｔ＞および＜ｐａｌ＞を有する、エントリ９１１−３および９１１−４にそれぞれ一致する。長さ０を有する空のサフィックス（ヌル文字列とも呼ばれる）は、クエリ補完テーブル内のすべてのエントリに一致し、したがって、部分クエリのサフィックス部分がヌル文字列の場合、テーブル内の上位Ｎ項目が、予測クエリとして返される。
【００６０】
上に述べたように、部分ＵＲＬに対応する、予測されたＵＲＬの順序付けされた組を識別するためのデータ構造およびプロセスは、ユーザが入力した部分クエリに対応する、予測クエリの順序付けされた組を識別するための、上記のデータ構造およびプロセスと同様である。ＵＲＬとクエリ文字列とは異なる用途を有してもよいが、両方とも、ユーザによる部分入力の後で値が予測することができる文字または記号の列として取り扱われてもよい。一部の実施形態では、ＵＲＬ補完テーブル１２３４（図１２）およびＵＲＬフィンガープリント−テーブルマップ１２３６（図１２）の組の構築に使用される、「履歴ＵＲＬ」の組は、特定のユーザによって、あるいは、ユーザの組またはコミュニティによって入力されたＵＲＬを含んでもよい。別の実施形態では、ＵＲＬ補完テーブルおよびＵＲＬフィンガープリント−テーブルマップの組の構築に使用される、「履歴ＵＲＬ」の組は、文書データベース（検索エンジンの文書データベースなど）に記憶された文書のＵＲＬを含んでもよい。
【００６１】
図１１は、本発明の一部の実施形態による、ブラウザおよびツールバーを使用する場合のユーザへの表示を示す。ブラウザ１１０２は、部分クエリ＜ｈｏｔ＞の入力を示すテキスト入力ボックス１１０６を含む、ツールバー１１０４を含む。部分クエリの検出、および、クエリサーバからの予測クエリの最終的な受信に応答して、予測が、ユーザによる選択が可能となるように、表示領域１１０８内に表示される。同様に、図示されていないが、アドレスバー１１１０内への部分ＵＲＬのユーザ入力の検出に応答して、予測されたＵＲＬの順序付けされた組が、ユーザによる選択が可能となるように、アドレスバー１１１０のすぐ下または隣の表示領域（図示せず）内に表示されてもよい。
【００６２】
図１２を参照すると、上記の方法およびデータ構造を実装する検索エンジン１２０２の実施形態は、１つまたは複数の処理ユニット（ＣＰＵ）１２０４と、１つまたは複数のネットワークまたはその他の通信インタフェース１２０６と、メモリ１２０８と、これらの構成要素を相互接続するための１つまたは複数の通信バス１２１０とを含む。検索エンジン１２０２は、任意選択として、ディスプレイ装置１２１４とキーボード１２１６とを備えるユーザインタフェース１２１２を含んでもよい。メモリ１２０８は、高速ランダムアクセスメモリを含んでもよく、さらに、１つまたは複数の、磁気または光記憶ディスクのような不揮発性メモリも含んでもよい。メモリ１２０８は、ＣＰＵ１２０４から離れた場所に配置された大容量記憶装置を含んでもよい。メモリ１２０８は、以下の要素、あるいは、そのような要素のサブセットまたはスーパーセットを記憶してもよい。
・さまざまな基本システムサービスを処理するための、およびハードウェア依存タスクを実行するための手続きを含む、オペレーティングシステム１２１８。
・インターネット、その他のワイドエリアネットワーク、ローカルエリアネットワーク、メトロポリタンエリアネットワークなどの、１つまたは複数の通信インタフェース１２１６（有線または無線）を介して、検索エンジン１２０２を他のコンピュータに接続するために使用されるネットワーク通信モジュール（または命令）１２２０。
・完全なクエリまたは部分クエリを受信して、検索結果と、予測クエリと、予測された検索結果とを返す、クエリサーバ２１０。
・部分クエリを受信して、クエリまたはＵＲＬの予測の順序付けされた組を返す、予測サーバ２１２。
【００６３】
一部の実施形態では、クエリサーバ２１０は、以下の要素、またはそのような要素のサブセットを含む。情報を受信および送信するためのクライアント通信モジュール２１６と、完全な検索クエリを受信して応答するための、クエリ受信・処理および応答モジュール２１８と、完全な検索クエリを受信して応答するための、部分クエリ受信・処理および応答モジュール２２０と、複数のユーザのそれぞれのユーザプロファイル１２２８を含むユーザ情報データベース１２２６からのユーザ情報にアクセスするための、ユーザ情報および処理モジュール２２２と、以前に発行されたクエリに関する情報を記憶するためのクエリログ２２４と、ＵＲＬログまたはデータベース２２５。一部の実施形態では、クエリサーバ２１０は、これらのモジュールのサブセットを含む。一部の実施形態では、クエリサーバ２１０は、追加のモジュールを含む。
【００６４】
一部の実施形態では、予測サーバ２１２は、以下の要素、あるいは、そのような要素のサブセットまたはスーパーセットを含む。
・部分クエリを受信するための、クエリ受信モジュール（または命令）１２３０。
・クエリ補完テーブル５１６、９１０およびクエリフィンガープリント−テーブルマップ５１０を生成するための、クエリ／ＵＲＬ補完テーブルビルダ（または命令）１２３２；一部の実施形態では、クエリ／ＵＲＬ補完テーブルビルダ１２２３は、さらに、ＵＲＬ補完テーブル１２３４およびＵＲＬフィンガープリント−テーブルマップ１２３６も生成する。
・予測クエリまたはＵＲＬの組を取得するための、予測モジュール（または命令）１２３８。
【００６５】
一部の実施形態では、予測サーバ２１２は、さらに、以下のうちの１つまたは複数も含む。
・特定のユーザプロファイル情報に少なくとも部分的に基づいて予測クエリの組を選択するための、パーソナライズモジュール（または命令）１２４０。
・特定のクエリに関連付けられた概念を判定するための、概念モジュール（または命令）１２４２。
・ユーザのコミュニティに関連付けられた特性の組を判定するための、コミュニティ特性モジュール（または命令）１２４４。
・受信されたクエリまたはクエリタームの代替のスペリングを識別するための、スペリングモジュール（または命令）１２４６。
・さまざまな記号言語要素のための表音表示を提供する、言語辞書１２４８。
【００６６】
一部の実施形態では、ユーザ情報処理モジュール２２２、パーソナライズモジュール１２４０、概念モジュール１２４２、コミュニティ特性モジュール１２４４、およびスペルモジュール１２４６のうちの、１つまたは複数は実装されない。実装された場合、ユーザ情報処理モジュール２２２のユーザプロファイル１２２８は、予測クエリまたはＵＲＬを選択または順序付けするために適した情報を含んでもよい。例えば、ユーザプロファイル１２２８は、特定のユーザにとって関心のある情報のカテゴリを識別してもよい。ユーザプロファイル１２２８は、さらに、ユーザが属している、またはユーザが関連している、ユーザのコミュニティに関連付けられた情報も含んでもよい。ユーザ情報処理モジュール２２２は、個人情報をコミュニティ情報とマージして、ユーザプロファイル１２２８を生成してもよい。
【００６７】
実装された場合、概念モジュール１２４２は、履歴クエリを、ユーザプロファイル１２２８内の情報と照合するために適した情報の概念またはカテゴリにマッピングする。同様に、概念モジュール１２４２は、例えば、履歴ＵＲＬに対応する文書のコンテンツ内の情報の主要な概念、主題、またはカテゴリの組を判定することによって、履歴ＵＲＬを情報の概念またはカテゴリにマッピングするように構成されてもよい。概念モジュール１２４２によって識別される概念、主題、またはカテゴリ情報は、クエリ補完テーブルまたはＵＲＬ補完テーブルのエントリ内に、または、クエリ／ＵＲＬ補完テーブルによって識別されるクエリレコードまたはＵＲＬレコード内に記憶されてもよい。部分クエリまたはＵＲＬを処理する場合、予測クエリまたはＵＲＬの組は順序付けし直されてもよく、それにより、概念、主題、またはカテゴリ情報が、要求中のユーザのユーザプロファイル内の情報に一致する予測クエリまたはＵＲＬは、概念またはカテゴリ情報が、要求中のユーザのユーザプロファイル内の情報に一致しない予測クエリまたはＵＲＬよりも、予測クエリまたはＵＲＬのリスト内で上位に配置されてもよい。
【００６８】
別の実施形態では、概念モジュール１２４２は、部分クエリ内の１つまたは複数のタームを、それらのタームの概念またはカテゴリマッピングに従って、１つまたは複数の置換タームにマッピングするように構成されてもよい。予測クエリの順序付けされた組が、１つまたは複数の置換タームを含む部分クエリに対して生成され、次に、それらの予測クエリは、別個に、または、ユーザによって入力されたとおりの部分クエリを使用して生成された結果とマージされて、ユーザに送信される。
【００６９】
図１２は、一実施形態における検索エンジン１２０２の内部構造を示す。一部の他の実施形態では、検索エンジン１２０２は、スループットと信頼性を向上するために、複数のサーバを使用して実装されてもよいことが理解されるべきである。例えば、クエリログ２２４は、別個のサーバ上に実装されてもよく、このサーバは、検索エンジン１２０２のサーバである他のサーバと通信を行い、連携して動作する。別の例として、クエリ／ＵＲＬ補完テーブルビルダ１２３２、および／または、言語辞書１２４８は、独立したサーバまたはコンピューティング装置（例えば、図２の、順序付け組ビルダ２４２および言語辞書２４４）内に実装されてもよい。
【００７０】
本明細書における説明は、検索要求者から離れた場所に配置された文書とともに使用するように設計された検索エンジンに関して行ったが、本明細書で開示された概念は、他の検索環境に等しく適用可能であることが理解されるべきである。例えば、本明細書で説明されたのと同様の技術が、クエリまたは検索の実行対象となる任意のタイプの情報リポジトリ（例えば、アドレス帳、製品情報データベース、ファイルサーバ、ウェブサイトなど）に対するクエリに適用されてもよい。したがって、「検索エンジン」という用語は、そのようなすべての用途を包含するように広く解釈されるべきである。
【００７１】
図１３を参照すると、上記の方法を実装するクライアントシステム１３００の実施形態は、１つまたは複数の処理ユニット（ＣＰＵ）１３０２と、１つまたは複数のネットワークまたはその他の通信インタフェース１３０４と、メモリ１３０６と、これらの構成要素を相互接続するための１つまたは複数の通信バス１３０８とを含む。検索エンジン１３００は、任意選択として、ディスプレイ装置１３１２および／またはキーボード１３１４を備えるユーザインタフェース１３１０を含んでもよい。メモリ１３０６は、高速ランダムアクセスメモリを含んでもよく、さらに、１つまたは複数の、磁気または光記憶ディスクのような不揮発性メモリも含んでもよい。メモリ１３０６は、ＣＰＵ１３０２から離れた場所に配置された大容量記憶装置を含んでもよい。メモリ１３０６は、以下を記憶してもよい。
・さまざまな基本システムサービスを処理するための、およびハードウェア依存タスクを実行するための手続きを含む、オペレーティングシステム１３１６。
・１つまたは複数の通信ネットワークインタフェース１３０４と、インターネット、その他のワイドエリアネットワーク、ローカルエリアネットワーク、メトロポリタンエリアネットワークなどの、１つまたは複数の通信ネットワークとを介して、クライアントシステム１３００を他のコンピュータに接続するために使用されるネットワーク通信モジュール（または命令）１３１８。
・検索クエリの入力のためにユーザとインタフェースし、検索結果を表示するための、ブラウザまたはツール１３２０。
・検索アシスタント１３２２。
【００７２】
一部の実施形態では、検索アシスタント１３２２は、ブラウザ／ツール１３２０から分離しており、他の実施形態では、検索アシスタントは、ブラウザ／ツール１３２０内に組み込まれている。
【００７３】
検索アシスタント１３２２は、以下の要素、またはそのような要素のサブセットを含んでもよい。検索クエリの入力を監視し、検索エンジンに送信する部分クエリを選択するための入力および選択監視モジュール（または命令）１３２４と、部分検索クエリおよび最終検索クエリを検索エンジンに送信するための送信モジュール（または命令）１３２６と、予測クエリを受信するための予測クエリ受信モジュール（または命令）１３２８と、予測された検索結果を受信するための、予測された検索結果受信モジュール（または命令）１３３０と、予測および結果を表示するための表示モジュール（または命令）１３３２と、検索結果を受信するための、任意選択の検索結果受信モジュール（または命令）１３３４。最終的な（すなわち、完全な）クエリの送信、完全なクエリに対する検索結果の受信、およびそのような結果の表示は、ブラウザ／ツール１３２０、検索アシスタント１３２２、またはそれらの組み合わせによって処理されてもよい。検索アシスタント１３２２は、さらに、部分的および完全なＵＲＬを処理するための、対応する機能の組も提供してもよく、それらのＵＲＬは、上記と同じ要素によって、または類似した要素の組によって処理されてもよい。検索アシスタント１３２２は、多くの方法で実装されてもよい。例えば、検索アシスタント１３２２は、ブラウザの一部として、ツールバーの一部として、デスクトップアプリケーションの一部として、または、（ジャバスクリプト（Ｊａｖａ（登録商標）Ｓｃｒｉｐｔ）などの）実行可能命令を使用してウェブページ上に実装されてもよい。少なくとも、検索アシスタントは、部分クエリ情報を検索システムに送信する。検索アシスタントは、さらに、予測された結果の表示と、表示された予測結果のユーザによる選択とを可能にしてもよい。
【００７４】
図１２および図１３では別個のモジュールまたは構成要素として示されているが、さまざまなモジュールまたは構成要素は、検索エンジンまたはクライアントのいずれかの内部に、配置または共同配置されてもよい。例えば、一部の実施形態では、予測サーバ３１２および／または様々なクエリ補完テーブル５１２および／または９１０の部分は、クライアントシステム２０２上に存在するか、あるいは、検索アシスタント２０４の部分を形成する。例えば、一部の実施形態では、最も人気のある検索についての、クエリ補完テーブルおよびフィンガープリント−テーブルマップは、クライアントシステム２０２に定期的にダウンロードされてもよく、それにより、少なくとも部分的に入力されたクエリまたはＵＲＬについて、完全なクライアントベースのクエリまたはＵＲＬ入力予測が提供されてもよい。
【００７５】
別の実施形態では、検索アシスタント２０４は、ユーザの以前の検索およびＵＲＬ入力に少なくとも部分的に基づいて、検索またはＵＲＬ予測を行うための予測サーバ３１２のローカルバージョンを含んでもよい。代わりとして、またはそれに加えて、ローカル予測サーバ３１２は、検索エンジンまたはリモート予測サーバからダウンロードされたデータに基づいて予測を生成してもよい。さらに、クライアントアシスタント２０４は、ローカルに生成された予測の組とリモートで生成された予測の組とを、ユーザに提示するためにマージしてもよい。結果は、例えば、２つの組を交互配置することによって（by interleaving the two sets）、または、ユーザによって以前に発行されたクエリにバイアスをかけて、それらのクエリが、予測クエリの組み合わせリストの最上位の方に配置または挿入される傾向があるようにしながら、それらの組をマージすることによってなど、いくつかの方法のうちのいずれかでマージされてもよい。一部の実施形態では、クライアントアシスタント２０４は、ユーザにとって重要と見なされるクエリを、予測の組の中に挿入する。例えば、ユーザによって頻繁に発行されるが、検索エンジンから取得された組の中に含まれていないクエリが、予測の中に挿入されてもよい。
【００７６】
上述のテクニックは、フィンガープリント−テーブルマップ５１０が生成されるプロセスを変更することによって、アルファベット文字体系に主として基づく言語以外の言語に適合させられてもよい。例えば、上述のテクニックは、表語文字（logograms）（語の部分または語全体を表す記号）、表意文字（ideograms）（抽象的概念を図式的に表す記号）、表音文字（phonetics）（アルファベットおよび音節文字表において使用される書記素におけるような、特定の音を表す記号）、および意味−表音複合文字（semantic-phonetic compounds）（記号の意味を表すかまたは示唆する意味要素と、発音を示すかまたは示唆する音声要素とを含む記号）などの、記号またはピクトグラムを有する言語に適用されてもよい。本明細書での目的のために、アルファベットではない記号またはピクトグラム、すなわち文字は、一般に、「表意文字（ideographs）」と呼ぶ。
【００７７】
主として非アルファベットの言語に上述のテクニックを適合させるための、一部の実施形態を示すために、日本語が使用される。日本語は、文字体系の混合を使用し、漢字、仮名、ローマ字、アラビア数字、および漢数字を含む。漢字は、いくつかの源に由来する「文字」である。一部の漢字は中国語に由来し（通常、２つ以上の発音を有し、発音は意味または意味論に基づく）、一部は中国語から採用されたものであり（通常、「標準の」発音を有する）、一部は日本語のためにのみ作られたものである。仮名は、平仮名（主として、日本語固有の語またはかなり昔に中国語から借用された語を表すために使用される）および片仮名（主として、外来語または擬音語を書くため、あるいは、テキストに「魅力的な」外観を与えるために使用される）という、２つの日本語音節文字表（Japanese syllabaries）の表音文字である。一部の例では、漢字表現は、特定の活用を示すための、および／または、発音を補助するための、１つまたは複数の送り仮名（trailing Kana characters）を含む。ローマ字は、ローマ字アルファベットの文字である。
【００７８】
平仮名および片仮名のそれぞれは、４６文字を含み、大部分が、母音と、母音−子音の組み合わせとからなる。日本語テキストは、一般に、１つまたは複数の漢字文字についての仮名音声表示を入力し、次に、それが漢字表現に変換されることによって、コンピュータ内に入力される。一入力方法によれば、（コンピュータキーボードからの）ローマ字文字の列が、中間テキスト入力領域内に入力されるか、または表示される。仮名文字を生成する各ローマ字文字の列が認識されるにつれて、中間テキスト入力領域内で、仮名文字が、表示されたローマ字文字に取って代わるか、または表示される。例えば、ローマ字列「ｔｉ」をタイプすると、平仮名「ち」が生成される。所望の数の仮名文字が入力された後で、ユーザは、仮名表現を、所望のテキスト領域内に直接配置してもよく、あるいは、ユーザ始動の操作によって、仮名表現のすべてまたは部分を漢字表現に選択的に変換してもよい。例えば、ローマ字列「ｔｉ」に続いて「ｋｅ」をタイプすると、英語「ｓａｌｍｏｎ」の仮名表現である、平仮名「さけ」が生成される。この仮名文字列は、「スペースバー」の押下、またはファンクションキーの押下などの、ユーザ始動の操作によって、「ｓａｌｍｏｎ」の漢字表現、つまり「鮭」に変換されてもよい。一部の例では、仮名から漢字への変換は、自動的に試みられる。しかしながら、多くの場合、変換にはユーザの何らかの介入が必要とされる。仮名による同じ音声表示が、複数の漢字表現にマッピングされる場合があるため、ユーザは、一般に、複数の漢字表現から選択する必要がある。例えば、（ローマ字文字の列「ｈｏ」およびそれに続く「ｓｉ」によって生成される）表音文字列「ほし」は、「端」（ｔｉｐまたはｅｎｄを意味する）、「橋」（ｂｒｉｄｇｅを意味する）、および「箸」（ｃｈｏｐｓｔｉｃｋｓを意味する）という、３つの漢字表現と整合性がある。その上、１つの漢字表現は、複数の音声表示を有する場合がある。例えば、「鮭」（ｓａｌｍｏｎを意味する）は、「さけ」（ローマ字文字の列「ｔｉ」およびそれに続く「ｋｅ」によって生成される）と、「しやけ」（ローマ字文字の列「ｓｉ」、「ｙａ」、および「ｋｅ」によって生成される）という音声表示を、少なくとも有する。
【００７９】
クエリを入力するユーザは、一般に、クエリ入力領域内に表音文字の列を入力することによって、各クエリタームを入力する。表音文字列は、通常、クエリが形成されるにつれて、表意文字に変換される。クエリは、通常、１つまたは複数の表意文字、および／または、１つまたは複数の表音文字を、所望の順序で含む。予測サーバは、１つまたは複数の表意文字からなる部分クエリに基づいて検索クエリを予測するだけでなく、ユーザが音声表示を入力するにつれて、表意文字の部分表音文字入力を使用して予測を行うことが望ましい。したがって、そして、他の組み合わせに加えて、０以上の表意文字とそれに続く１つまたは複数の表音文字とからなる部分クエリ入力に対して、予測が行われる。一部の実施形態では、これらの予測は、フィンガープリント−テーブルマップの作成に使用される図７のプロセスを、言語の特定の文字体系を考慮に入れて修正することによって達成されてもよい。修正されたプロセスは、１つまたは複数の表音文字による表意文字の入力を考慮する。図１４を参照すると、表意文字と表音文字との両方を含み、表意文字と音声表示との間に複数のマッピングが存在してもよい言語文字体系を考慮した、フィンガープリント−テーブルマップの作成のためのプロセスが示されている。当業者は、図１４に示す方法が、他の言語に拡張されてもよいことを容易に認識するであろう。
【００８０】
処理対象の言語によるクエリを有する、許可された履歴クエリのリスト（例えば、図５の、許可された履歴クエリのリスト５０６）から、クエリが選択される（１４０２）。一部の実施形態では、この許可された履歴クエリのリストは、図５を参照した説明に従って生成される。最初のクエリ単位が識別される（１４０４）。クエリ単位は、いくつかの方法で決定されてもよい。一部の実施形態では、クエリ単位は、語または概念を表す、認識された順序での、１つまたは複数の漢字文字（および、活用または発音のために使用される適切な平仮名）からなる。一部の例では、さまざまな語または概念を表す漢字文字は、区切り文字（例えば、空白文字）なしで、漢字文字の１つの文字列として表される。一部の例では、クエリ単位は、１つの漢字文字である。一部の例では、クエリ単位は、１つまたは複数の漢字、および／または、１つまたは複数の表音文字である。一部の実施形態では、表意文字が識別される前に、前処理が適用される（例えば、「ｈｔｔｐ：／／」の除去）。任意の以前のクエリ単位と現在のクエリ単位、現在のクエリ単位に対応する完全なクエリ、およびクエリの頻度を示すエントリが、テーブル内に作成される（１４０６）。他の実施形態では、ランク付けのために使用されるその他の情報が記憶される（例えば、日付／時刻値、または、２つ以上の要因に基づいて計算されたランク付け得点）。
【００８１】
現在のクエリ単位が表意文字である場合、表意文字と整合性がある音声表示が識別される（１４０８）。一実施形態では、表意文字と整合性がある、少なくとも１つの可能な音声表示を返すために、辞書（例えば、図２の、言語辞書２４２）が調べられる。以前の文字に現在の文字を追加することによって、完全な音声表示を構築するために表音文字が入力されると、それら表音文字の増加加算（the incremental addition）を表すインクリメンタルクエリ文字列が、各音声表示から判定される（１４１０）。例えば、現在のクエリ単位として「鮭」が識別されている場合、音声表示のうちの１つは（上述のように）「さけ」である。音声表示「さけ」は、２つの表音文字（すなわち、「さ」および「け」）を含むため、第１のインクリメンタルクエリ文字列は、第１の表音文字からなる「さ」となり、第２のインクリメンタルクエリ文字列は、第１および第２の文字からなる「さけ」となる。各インクリメンタルクエリ文字列（および、任意の以前の表意文字およびクエリ単位（存在する場合）を含む）、インクリメンタルクエリ文字列に対応する完全なクエリ、およびクエリの頻度についてのエントリが、テーブル内に作成される（１４１２）。一部の例では、クエリ単位は、２つ以上の表意文字、あるいは、１つまたは複数の表意文字と、それに続く１つまたは複数の表音文字とを含む。各インクリメンタルクエリ文字列が構築されるにつれて、表音文字の完全な列が、それらの対応する表意文字によって置き換えられる。例えば、クエリ単位が「認める」（すなわち、ａｃｋｎｏｗｌｅｄｇｅを意味し、仮名文字「める」は活用語尾を提供する）である場合、１つの可能な完全な表音文字列は「みとめる」である（ここで、「みと」は、漢字「認」の仮名表示である）。インクリメンタルクエリ文字列が構築されるにつれて（例えば、「み」および「みと」）、表音文字の特定の列が認識された場合（例えば、「みと」）、その特定の列は適切な表意文字（例えば、「認」）によって置き換えられ、後続のインクリメンタルクエリ文字列（例えば、「認め」および「認める」）のために使用される。
【００８２】
クエリが完全に処理されていない場合（１４１４−ｎｏ）、次のクエリ単位が識別されて（１４１６）、上記のように処理される。現在のクエリが完全に処理された場合（１４１４−ｙｅｓ）、処理のためにまだ残されているクエリがさらにあるならば、（１４１８−ｎｏ）、別のクエリが選択されて、上記のように処理される。プロセスは、処理されるべきすべてのクエリが処理されるまで（１４１８−ｙｅｓ）継続される。
【００８３】
上述のプロセスは、図１５および図１６を参照することによって、よりよく理解することができる。例示的クエリ文字列１５０２は、第１の表意文字１５０４（すなわち、ｓａｌｍｏｎを表す漢字「鮭」）と、第２の表意文字１５０６（すなわち、Ｊａｐａｎを表す漢字「日本」）とを有するクエリを表す。第１の表意文字１５０４は、第１の音声表示１５０８（すなわち、「ｓａｋｅ」と発音される「さけ」）と、第２の音声表示１５１０（すなわち、「ｓｈａ−ｋｅ」と発音される「しゃけ」）とを有する。同様に、第２の表意文字１５０６は、第１の音声表示１５１２（すなわち、「ｎｉｈｏｎ」と発音される「にほん」）と、第２の音声表示１５１４（すなわち、「ｎｉｐｐｏｎ」と発音される「にっぽん」とを有する。
【００８４】
図１６は、図１５のクエリ文字列１５０２を処理するための一方法を示す。最初に、クエリ文字列１５０２の第１のクエリ単位が識別され（すなわち、「鮭」）、部分クエリ単位１６０６と、完全なクエリ１６０８と、クエリ頻度１６１０とを示す、対応するエントリ１６０２が、テーブル１６０４内に作成される。一部の実施形態では、クエリのランク付けの基となる、クエリに関連付けられたその他のまたは追加の情報が含まれてもよい。「鮭」の音声表示が識別され（すなわち、「さけ」および「しゃけ」）、インクリメンタルクエリ文字列が判定されて、対応するエントリがテーブル１６０４内に作成される。例えば、第１の音声表示「さけ」は、インクリメンタル文字列「さ」および「さけ」を含む。したがって、インクリメンタルクエリ文字列「さ」に対応するエントリ１６１２が作成され、インクリメンタルクエリ文字列「さけ」に対応するエントリ１６１４が作成される。第２の音声表示に関連付けられたインクリメンタルクエリ文字列についてのエントリも作成される（例えば、１６１６、１６１８、および１６２０）。次に、次のクエリ単位が識別され（すなわち、「日本」）、両方の表意文字を含む（そして、第１の表意文字の音声表示は何も含まない）対応するエントリ１６２２が、テーブル１６０４内に作成される。最後に、「日本」の音声表示が判定されて、対応するエントリが作成される（例えば、エントリ１６２４）。上記のプロセスは、クエリ単位が１つまたは２つ以上の表意文字を含む場合にも、同様に適用されることに注意されたい。（例えば、表意文字の末尾に追加された）表音文字がクエリ内に見つかった場合、その表音文字は、見つかったときに部分クエリ内に含められる（そして、対応するエントリがテーブル１６０４内に作成される）。上記のプロセスは、入力が部分的に入力されたＵＲＬである場合も、同様に実施される。ＵＲＬは、事前定義された区切り文字（例えば、「＞」および「／」）を含み、空白文字を含まない、クエリタームの列と同等である。
【００８５】
様々な所望のクエリ補完テーブルおよびフィンガープリント−テーブルマップが、図７および図８を参照して上述したように、クエリの処理中または処理後に作成されてもよい。
【００８６】
クエリの表意文字を実現するために入力される様々な表音文字列を考慮に入れることにより、音声表示の列が完成する前に予測が行われてもよい。０以上の表意文字と１つまたは複数の表音文字とを含む、検索要求者から受信された部分クエリから、クエリ補完テーブルが識別される。
【００８７】
本発明のさまざまな実施形態を、英語および日本語を使用して説明したが、本明細書で説明した概念を他の言語に拡張する方法を、当業者は容易に認識するであろう。例えば、入力文字の可能性のある列は、許可された履歴クエリと、それらの可能性のある入力文字列に基づいて作成された、様々なクエリ補完テーブルと、フィンガープリント−テーブルマップとから決定されてもよい。
【００８８】
さまざまな図面のうちの一部は、いくつかの論理ステージを特定の順序で示すが、順序に依存しないステージは、順序付けし直されてもよく、その他のステージは、組み合わされるか、または切り離されてもよい。一部の再順序付けまたはその他のグループ化については具体的に述べたが、その他については、当業者にとって明白であり、したがって代替方法の網羅的なリストは示していない。さらに、ステージは、ハードウェア、ファームウェア、ソフトウェア、またはそれらの任意の組み合わせで実装されてもよいことが認識されるべきである。
【００８９】
以上の記載は、説明の目的のために、特定の実施形態に関して行った。しかし、上述の具体的な説明は、開示された厳密な形態で本発明が網羅されたり限定されたりすることを意図するものではない。上記の教示を考慮すれば多くの変更および変形が可能である。実施形態は、本発明の原理とその実際的な適用例とを最もよく説明するために、そしてそれにより、当業者が、本発明およびさまざまな実施形態を、企図された特定の使用に適したさまざまな変更とともに、最もよく利用できるようにするために、選択され説明されたものである。
【特許請求の範囲】
【請求項１】
表意文字と表音文字とを有する言語のための、クエリ補完を提案するための方法であって、
０以上の表意文字と、それに続く少なくとも１つの表音文字とを含む部分クエリを、検索要求者から受信するステップと、
ランク付け基準に従って順序付けされた予測クエリの組の１つを、前記部分クエリから予測するステップであって、前記組は表意文字を含む、ステップと
順序付けされた予測クエリの前記組を、前記検索要求者に伝えるステップとを含む方法。
【請求項２】
表意文字と表音文字とを有する言語のための、クエリ補完を提案するための方法であって、
完全なクエリの部分を含む部分クエリを、検索要求者から受信するステップと、
ランク付け基準に従って順序付けされた予測クエリの組を、前記部分クエリから予測するステップであって、前記組は、１つ以上の表意文字を有する少なくとも１つの文字列を含む、ステップと、
順序付けされた予測クエリの前記組を、前記検索要求者に伝えるステップとを含む方法。
【請求項３】
前記部分クエリは、少なくとも１つの表音文字を含む、請求項２に記載の方法。
【請求項４】
前記部分クエリは、表意文字および表音文字の両方を含む、請求項２に記載の方法。
【請求項５】
前記部分クエリは、少なくとも１つの表意文字を表す少なくとも１つの不完全な表音文字列を含み、
前記予測するステップは、前記不完全な表音文字列と整合性がある少なくとも１つまたは複数の表意文字を予測するステップを含む、請求項２に記載の方法。
【請求項６】
予測クエリの前記組の中に、ユーザのコミュニティによって発行されたクエリを含めるステップをさらに含む、請求項２に記載の方法。
【請求項７】
予測クエリの前記組を、ユーザのコミュニティによって発行されたクエリから作成するステップをさらに含む、請求項２に記載の方法。
【請求項８】
予測クエリの前記組は、前記検索要求者によって以前に発行されていない少なくとも１つのクエリを含む、請求項２に記載の方法。
【請求項９】
前記組は、検索クエリと、少なくとも１つのＵＲＬとの両方を含む、請求項２に記載の方法。
【請求項１０】
前記予測するステップは、前記部分クエリに対応する２つ以上の組を識別するステップと、前記組をマージするステップとを含む、請求項２に記載の方法。
【請求項１１】
交互配置方式で前記組をマージするステップをさらに含む、請求項１０に記載の方法。
【請求項１２】
少なくとも、前記組のうちの第１の組はクライアント上で生成され、前記組のうちの第２の組はサーバ上で生成される、請求項１０に記載の方法。
【請求項１３】
入力を受信するステップであって、前記入力は、順序付けされた予測クエリの前記組の中から選択されるクエリを識別する、ステップと、
前記受信したクエリに関連する検索結果を生成するステップとを含む、請求項２に記載の方法。
【請求項１４】
前記予測クエリのうちの少なくとも１つに関連する検索結果を生成するステップと、
前記検索結果を前記要求者に伝えるステップとを含む、請求項２に記載の方法。
【請求項１５】
前記受信したクエリ情報から、関連するクエリ情報を判定するステップと、
前記関連するクエリ情報に関連する、少なくとも１つの予測クエリを識別するステップと、
前記関連するクエリ情報に関連する前記少なくとも１つの予測クエリを、前記サブセット内に含めるステップとをさらに含む、請求項２に記載の方法。
【請求項１６】
前記予測するステップは、前記予測クエリの日付／時刻値に従って、前記予測クエリを順序付けするステップを含む、請求項２に記載の方法。
【請求項１７】
ユーザに関連付けられた特性に基づいて前記組を修正するステップをさらに含む、請求項２に記載の方法。
【請求項１８】
前記組を前記検索要求者に伝えるステップと、
所定の期間内に、前記検索要求者から、前記組の中で送信されたクエリに対応する選択が受信されないことを判定するステップと、
前記ランク付け基準に従って順序付けされた予測クエリの後続の組を、前記検索要求者に送信するステップとをさらに含む、請求項２に記載の方法。
【請求項１９】
前記組を前記検索要求者に伝えるステップと、
予測クエリの後続の組に対する要求を、前記検索要求者から受信するステップと、
予測クエリの後続の組を識別するステップと、
前記ランク付け基準に従って順序付けされた予測クエリの前記後続の組を、前記検索要求者に送信するステップとをさらに含む、請求項２に記載の方法。
【請求項２０】
前記部分クエリを受信するステップの前に、ユーザのコミュニティによって以前に発行された、履歴クエリの組を識別するステップであって、履歴クエリの前記組の中の各クエリは、発行頻度を有し、少なくとも１つの表意文字を含む、ステップと、
前記部分クエリを受信するステップの前に、履歴クエリの前記識別された組から、複数の順序付けされたサブセットを生成するステップであって、各順序付けされたサブセットは、履歴クエリの前記識別された組からの１つまたは複数の履歴クエリが、それぞれの発行頻度に従って順序付けされたものを含む、ステップと、を含む請求項２に記載の方法。
【請求項２１】
前記生成するステップは、
複数の履歴クエリからの１つまたは複数の表意文字の文字列を、１つまたは複数の表音文字の文字列を含む１つまたは複数の表示にマッピングするステップを含む、請求項２０に記載の方法。
【請求項２２】
前記生成するステップは、複数の履歴クエリからの１つまたは複数の表意文字の文字列を、１つまたは複数の表示にマッピングするステップを含み、少なくとも１つのマッピングは、少なくとも１つの表意文字と、１つまたは複数の表音文字の文字列とを含む、請求項２０に記載の方法。
【請求項２３】
ユーザのコミュニティによって以前に発行された履歴クエリの組を識別するステップであって、履歴クエリの前記組の中の各クエリは、発行頻度を有し、少なくとも１つの表意文字を含む、ステップと、
履歴クエリの前記識別された組から、複数の順序付けされたサブセットを生成するステップであって、各順序付けされたサブセットは、履歴クエリの前記識別された組からの１つまたは複数の履歴クエリが、それぞれの発行頻度に従って順序付けされたものを含む、ステップと、を含む請求項２に記載の方法。
【請求項２４】
前記生成するステップは、
複数の履歴クエリからの１つまたは複数の表意文字の文字列を、１つまたは複数の表音文字の文字列を含む１つまたは複数の表示にマッピングするステップを含む、請求項２３に記載の方法。
【請求項２５】
前記部分クエリを受信するステップの前に、複数の組を識別するステップであって、各組は、部分クエリ単位に関連付けられ、ユーザのコミュニティによって以前に発行された複数のクエリを含み、各クエリは、それぞれのランク付け値を有する、ステップと、
前記部分クエリを受信するステップの前に、前記複数の前記組の少なくとも部分について、前記組の中の前記クエリを、前記それぞれのランク付け値に従って順序付けするステップとを含み、
前記予測するステップは、前記複数の組の中から第１の組を識別するステップを含み、前記選択される組は前記部分クエリに対応する、請求項２に記載の方法。
【請求項２６】
前記予測するステップは、第２の組を識別するステップと、前記第１の組および前記第２の組をマージするステップとを含む、請求項２５に記載の方法。
【請求項２７】
前記予測するステップは、
第１のメモリから前記第１の組を識別するステップと、
第２のメモリから前記第２の組を識別するステップとをさらに含む、請求項２６に記載の方法。
【請求項２８】
表意文字と表音文字とを有する言語のための、クエリ補完を提案するためのシステムであって、
完全なクエリの部分を含む部分クエリを、検索要求者から受信するための、クエリ処理モジュールと、
ランク付け基準に従って順序付けされた予測クエリの少なくとも１つの組であって、前記組は、１つまたは複数の表意文字の文字列を有するクエリを少なくとも含む、組と、
前記ランク付け基準に従って順序付けされた予測クエリの前記組を、前記部分クエリから予測するための、予測モジュールと、
順序付けされた予測クエリの前記組を、前記検索要求者に伝えるための、通信モジュールとを備えるシステム。
【請求項２９】
前記部分クエリは、少なくとも１つの表音文字を含む、請求項２８に記載のシステム。
【請求項３０】
前記部分クエリは、表意文字および表音文字の両方を含む、請求項２８に記載のシステム。
【請求項３１】
前記部分クエリは、少なくとも１つの表意文字を表す少なくとも１つの不完全な表音文字列を含み、
予測クエリの前記組の中の少なくとも１つの予測クエリは、前記不完全な表音文字列と整合性がある少なくとも１つまたは複数の表意文字を含む、請求項２８に記載のシステム。
【請求項３２】
予測クエリの前記組は、ユーザのコミュニティによって発行されたクエリを含む、請求項２８に記載のシステム。
【請求項３３】
予測クエリの前記組は、前記検索要求者によって以前に発行されていない少なくとも１つのクエリを含む、請求項２８に記載のシステム。
【請求項３４】
予測クエリの前記組は、検索クエリと、少なくとも１つのＵＲＬとの両方を含む、請求項２８に記載のシステム。
【請求項３５】
ランク付け基準に従って順序付けされた予測クエリの少なくとも第２の組をさらに含み、前記第２の組は、１つまたは複数の表意文字の文字列を有する少なくとも１つのクエリを含み、
前記予測モジュールは、予測クエリの少なくとも前記第１の組と前記第２の組とを識別して、前記２つの組をマージするようにさらに構成される、請求項２８に記載のシステム。
【請求項３６】
前記予測モジュールは、前記第１の組と前記第２の組とを交互配置方式でマージするようにさらに構成される、請求項３５に記載のシステム。
【請求項３７】
前記第１の組は、前記第２の組から離れた場所に配置される、請求項３５に記載のシステム。
【請求項３８】
入力を受信するための受信モジュールであって、前記入力が、順序付けされた予測クエリの前記組の中から選択されるクエリを識別する、受信モジュールと、
前記受信したクエリに関連する検索結果を生成するための、クエリサーバとをさらに備える、請求項２８に記載のシステム。
【請求項３９】
前記クエリサーバは、前記予測クエリのうちの少なくとも１つに関連する検索結果を生成し、前記検索結果を前記要求者に伝えるようにさらに構成される、請求項２８に記載のシステム。
【請求項４０】
前記受信したクエリ情報から、関連するクエリ情報を判定するための概念モジュールをさらに含み、
前記サブセットは、前記関連するクエリ情報に関連する少なくとも１つの予測クエリを含む、請求項２８に記載のシステム。
【請求項４１】
前記予測モジュールは、前記予測クエリの日付／時刻値に従って、前記予測クエリを順序付けするようにさらに構成される、請求項２８に記載のシステム。
【請求項４２】
ユーザに関連付けられた特性に基づいた前記組の修正をさらに含む、請求項２８に記載のシステム。
【請求項４３】
前記予測モジュールは、
前記組を前記検索要求者に伝え、
予測クエリの後続の組に対する要求を、前記検索要求者から受信し、
予測クエリの後続の組を識別し、
前記ランク付け基準に従って順序付けされた予測クエリの前記後続の組を、前記検索要求者に送信するようにさらに構成される、請求項２８に記載のシステム。
【請求項４４】
前記予測モジュールは、さらに、
前記部分クエリを受信する前に、ユーザのコミュニティによって以前に発行された履歴クエリの組を識別するように構成され、履歴クエリの前記組の中の各クエリは、発行頻度を有し、少なくとも１つの表意文字を含み、
前記部分クエリを受信する前に、履歴クエリの前記識別された組から、複数の順序付けされたサブセットを生成するように構成され、各順序付けされたサブセットは、履歴クエリの前記識別された組からの１つまたは複数の履歴クエリが、それぞれの発行頻度に従って順序付けされたものを含む、請求項２８に記載のシステム。
【請求項４５】
前記予測モジュールは、
複数の履歴クエリからの１つまたは複数の表意文字の文字列を、１つまたは複数の表音文字の文字列を含む１つまたは複数の表示にマッピングするようにさらに構成される、請求項４４に記載のシステム。
【請求項４６】
前記予測モジュールは、複数の履歴クエリからの１つまたは複数の表意文字の文字列を、１つまたは複数の表示にマッピングするようにさらに構成され、少なくとも１つのマッピングは、少なくとも１つの表意文字と、１つまたは複数の表音文字の文字列とを含む、請求項４４に記載のシステム。
【請求項４７】
前記予測モジュールは、
ユーザのコミュニティによって以前に発行された履歴クエリの組を識別するように構成され、履歴クエリの前記組の中の各クエリは、発行頻度を有し、少なくとも１つの表意文字を含み、
履歴クエリの前記識別された組から、複数の順序付けされたサブセットを生成するように構成され、各順序付けされたサブセットは、履歴クエリの前記識別された組からの１つまたは複数の履歴クエリが、それぞれの発行頻度に従って順序付けされたものを含む、請求項２８に記載のシステム。
【請求項４８】
前記予測モジュールは、複数の履歴クエリからの１つまたは複数の表意文字の文字列を、１つまたは複数の表音文字の文字列を含む１つまたは複数の表示にマッピングするようにさらに構成される、請求項４７に記載のシステム。
【請求項４９】
前記予測モジュールは、さらに、
前記部分クエリを受信する前に、複数の組を識別するように構成され、各組は、部分クエリ単位に関連付けられ、ユーザのコミュニティによって以前に発行された複数のクエリを含み、各クエリは、それぞれのランク付け値を有し、
前記部分クエリを受信する前に、前記複数の組の少なくとも部分について、前記組の中の前記クエリを、前記それぞれのランク付け値に従って順序付けするように構成され、
前記複数の組の中から第１の組を予測するように構成され、前記選択される組は前記部分クエリに対応する、請求項２８に記載のシステム。
【請求項５０】
前記予測モジュールは、第２の組を予測し、前記第１の組と前記第２の組とをマージするようにさらに構成される、請求項４９に記載のシステム。
【請求項５１】
前記予測モジュールは、
第１のメモリから前記第１の組を識別し、
第２のメモリから前記第２の組を識別するようにさらに構成される、請求項５０に記載のシステム。
【請求項５２】
コンピュータシステムとともに使用するためのコンピュータプログラム製品であって、
完全なクエリの部分を含む部分クエリを、検索要求者から受信するための命令と、
ランク付け基準に従って順序付けされた予測クエリの組を、前記部分クエリから予測するための命令であって、前記組は、１つまたは複数の表意文字を有する少なくとも１つの文字列を含む、命令と、
順序付けされた予測クエリの前記組を、前記検索要求者に伝えるための命令とを含む、コンピュータプログラム製品。
【請求項５３】
前記部分クエリは、少なくとも１つの表音文字を含む、請求項５２に記載のコンピュータプログラム製品。
【請求項５４】
前記部分クエリは、表意文字および表音文字の両方を含む、請求項５２に記載のコンピュータプログラム製品。
【請求項５５】
前記部分クエリは、少なくとも１つの表意文字を表す少なくとも１つの不完全な表音文字列を含み、
前記予測のための前記命令は、前記不完全な表音文字列と整合性がある少なくとも１つまたは複数の表意文字を予測するための命令をさらに含む、請求項５２に記載のコンピュータプログラム製品。
【請求項５６】
予測クエリの前記組の中に、ユーザのコミュニティによって発行されたクエリを含めるための命令をさらに含む、請求項５２に記載のコンピュータプログラム製品。
【請求項５７】
ユーザのコミュニティによって発行されたクエリから、予測クエリの前記組を作成するための命令をさらに含む、請求項５２に記載のコンピュータプログラム製品。
【請求項５８】
予測クエリの前記組は、前記要求者によって以前に発行されていない少なくとも１つのクエリを含む、請求項５２に記載のコンピュータプログラム製品。
【請求項５９】
前記組は、検索クエリと、少なくとも１つのＵＲＬとの両方を含む、請求項５２に記載のコンピュータプログラム製品。
【請求項６０】
予測のための前記命令は、前記部分クエリに対応する２つ以上の組を識別するため命令、及び前記組をマージするための命令をさらに含む、請求項５２に記載のコンピュータプログラム製品。
【請求項６１】
前記組を交互配置方式でマージするための命令をさらに含む、請求項６０に記載のコンピュータプログラム製品。
【請求項６２】
少なくとも、前記組のうちの第１の組はクライアント上で生成され、前記組のうちの第２の組はサーバ上で生成される、請求項６０に記載のコンピュータプログラム製品。
【請求項６３】
入力を受信するための命令であって、前記入力は、順序付けされた予測クエリの前記組の中から選択されるクエリを識別する、命令と、
前記受信したクエリに関連する検索結果を生成するための命令とを含む、請求項５２に記載のコンピュータプログラム。
【請求項６４】
前記予測クエリのうちの少なくとも１つに関連する検索結果を生成するための命令と、
前記検索結果を前記要求者に伝えるための命令とを含む、請求項５２に記載のコンピュータプログラム製品。
【請求項６５】
前記受信したクエリ情報から、関連するクエリ情報を判定するための命令と、
前記関連するクエリ情報に関連する少なくとも１つの予測クエリを識別するための命令と、
前記関連するクエリ情報に関連する前記少なくとも１つの予測クエリを、前記サブセット内に含めるための命令と、をさらに含む、請求項５２に記載のコンピュータプログラム製品。
【請求項６６】
予測のための前記命令は、前記予測クエリの日付／時刻値に従って、前記予測クエリを順序付けすることをさらに含む、請求項５２に記載のコンピュータプログラム製品。
【請求項６７】
ユーザに関連付けられた特性に基づいて前記組を修正するための命令をさらに含む、請求項５２に記載のコンピュータプログラム製品。
【請求項６８】
前記組を前記検索要求者に伝えるための命令と、
所定の期間内に、前記検索要求者から、前記組の送信されたクエリに対応する選択が受信されないことを判定するための命令と、
前記ランク付け基準に従って順序付けされた予測クエリの後続の組を前記検索要求者に送信するための命令と、をさらに含む、請求項５２に記載のコンピュータプログラム製品。
【請求項６９】
前記組を前記検索要求者に伝えるための命令と、
予測クエリの後続の組に対する要求を、前記検索要求者から受信するための命令と、
予測クエリの後続の組を識別するための命令と、
前記ランク付け基準に従って順序付けされた予測クエリの前記後続の組を、前記検索要求者に送信するための命令と、をさらに含む、請求項５２に記載のコンピュータプログラム製品。
【請求項７０】
前記部分クエリを受信する前に、ユーザのコミュニティによって以前に発行された履歴クエリの組を識別するための命令であって、履歴クエリの前記組の中の各クエリは、発行頻度を有し、少なくとも１つの表意文字を含む、命令と
前記部分クエリを受信する前に、履歴クエリの前記識別された組から、複数の順序付けされたサブセットを生成するための命令であって、各順序付けされたサブセットは、履歴クエリの前記識別された組からの１つまたは複数の履歴クエリが、それぞれの発行頻度に従って順序付けされたものを含む、命令と、を含む、請求項５２に記載のコンピュータプログラム製品。
【請求項７１】
生成するための前記命令は、複数の履歴クエリからの１つまたは複数の表意文字の文字列を、１つまたは複数の表音文字の文字列を含む１つまたは複数の表示にマッピングするための命令をさらに含む、請求項７０に記載のコンピュータプログラム製品。
【請求項７２】
生成するための前記命令は、複数の履歴クエリからの１つまたは複数の表意文字の文字列を、１つまたは複数の表示にマッピングするための命令をさらに含み、少なくとも１つのマッピングは、少なくとも１つの表意文字と、１つまたは複数の表音文字の文字列とを含む、請求項７０に記載のコンピュータプログラム製品。
【請求項７３】
ユーザのコミュニティによって以前に発行された履歴クエリの組を識別するための命令であって、履歴クエリの前記組の中の各クエリは、発行頻度を有し、少なくとも１つの表意文字を含む、命令と、
履歴クエリの前記識別された組から、複数の順序付けされたサブセットを生成するための命令であって、各順序付けされたサブセットは、履歴クエリの前記識別された組からの１つまたは複数の履歴クエリが、それぞれの発行頻度に従って順序付けされたものを含む、命令と、を含む、請求項５２に記載のコンピュータプログラム製品。
【請求項７４】
生成するための前記命令は、複数の履歴クエリからの１つまたは複数の表意文字の文字列を、１つまたは複数の表音文字の文字列を含む１つまたは複数の表示にマッピングするための命令をさらに含む、請求項７４に記載のコンピュータプログラム製品。
【請求項７５】
前記部分クエリを受信する前に、複数の組を識別するための命令であって、各組は、部分クエリ単位に関連付けられ、ユーザのコミュニティによって以前に発行された複数のクエリを含み、各クエリは、それぞれのランク付け値を有する、命令と、
前記部分クエリを受信する前に、前記複数の前記組の少なくとも部分について、前記組の中の前記クエリを、前記それぞれのランク付け値に従って順序付けするための命令と、を含み、
予測するための前記命令は、前記複数の組の中から第１の組を識別することをさらに含み、前記選択される組は前記部分クエリに対応する、請求項５２に記載のコンピュータプログラム製品。
【請求項７６】
予測するための前記命令は、第２の組を識別し、前記第１の組と前記第２の組とをマージするための命令をさらに含む、請求項７５に記載のコンピュータプログラム製品。
【請求項７７】
予測するための前記命令は、
クライアント上で前記第１の組を識別するための命令と、
サーバ上で前記第２の組を識別するための命令とをさらに含む、請求項７６に記載のコンピュータプログラム製品。
【請求項７８】
表意文字と表音文字とを有する言語のための、クエリ補完を提案するためのシステムであって、
部分クエリを検索要求者から受信するための手段であって、部分クエリは完全なクエリの部分を含む、手段と、
ランク付け基準に従って順序付けされた予測クエリの組を、前記部分クエリから予測するための手段であって、前記組は、１つまたは複数の表意文字を有する少なくとも１つの文字列を含む、手段と、
順序付けされた予測クエリの前記組を、前記検索要求者に伝えるための手段とを備えるシステム。
【請求項１】
表意文字と表音文字とを有する言語のための、クエリ補完を提案するための方法であって、
０以上の表意文字と、それに続く少なくとも１つの表音文字とを含む部分クエリを、検索要求者から受信するステップと、
ランク付け基準に従って順序付けされた予測クエリの組の１つを、前記部分クエリから予測するステップであって、前記組は表意文字を含む、ステップと
順序付けされた予測クエリの前記組を、前記検索要求者に伝えるステップとを含む方法。
【請求項２】
表意文字と表音文字とを有する言語のための、クエリ補完を提案するための方法であって、
完全なクエリの部分を含む部分クエリを、検索要求者から受信するステップと、
ランク付け基準に従って順序付けされた予測クエリの組を、前記部分クエリから予測するステップであって、前記組は、１つ以上の表意文字を有する少なくとも１つの文字列を含む、ステップと、
順序付けされた予測クエリの前記組を、前記検索要求者に伝えるステップとを含む方法。
【請求項３】
前記部分クエリは、少なくとも１つの表音文字を含む、請求項２に記載の方法。
【請求項４】
前記部分クエリは、表意文字および表音文字の両方を含む、請求項２に記載の方法。
【請求項５】
前記部分クエリは、少なくとも１つの表意文字を表す少なくとも１つの不完全な表音文字列を含み、
前記予測するステップは、前記不完全な表音文字列と整合性がある少なくとも１つまたは複数の表意文字を予測するステップを含む、請求項２に記載の方法。
【請求項６】
予測クエリの前記組の中に、ユーザのコミュニティによって発行されたクエリを含めるステップをさらに含む、請求項２に記載の方法。
【請求項７】
予測クエリの前記組を、ユーザのコミュニティによって発行されたクエリから作成するステップをさらに含む、請求項２に記載の方法。
【請求項８】
予測クエリの前記組は、前記検索要求者によって以前に発行されていない少なくとも１つのクエリを含む、請求項２に記載の方法。
【請求項９】
前記組は、検索クエリと、少なくとも１つのＵＲＬとの両方を含む、請求項２に記載の方法。
【請求項１０】
前記予測するステップは、前記部分クエリに対応する２つ以上の組を識別するステップと、前記組をマージするステップとを含む、請求項２に記載の方法。
【請求項１１】
交互配置方式で前記組をマージするステップをさらに含む、請求項１０に記載の方法。
【請求項１２】
少なくとも、前記組のうちの第１の組はクライアント上で生成され、前記組のうちの第２の組はサーバ上で生成される、請求項１０に記載の方法。
【請求項１３】
入力を受信するステップであって、前記入力は、順序付けされた予測クエリの前記組の中から選択されるクエリを識別する、ステップと、
前記受信したクエリに関連する検索結果を生成するステップとを含む、請求項２に記載の方法。
【請求項１４】
前記予測クエリのうちの少なくとも１つに関連する検索結果を生成するステップと、
前記検索結果を前記要求者に伝えるステップとを含む、請求項２に記載の方法。
【請求項１５】
前記受信したクエリ情報から、関連するクエリ情報を判定するステップと、
前記関連するクエリ情報に関連する、少なくとも１つの予測クエリを識別するステップと、
前記関連するクエリ情報に関連する前記少なくとも１つの予測クエリを、前記サブセット内に含めるステップとをさらに含む、請求項２に記載の方法。
【請求項１６】
前記予測するステップは、前記予測クエリの日付／時刻値に従って、前記予測クエリを順序付けするステップを含む、請求項２に記載の方法。
【請求項１７】
ユーザに関連付けられた特性に基づいて前記組を修正するステップをさらに含む、請求項２に記載の方法。
【請求項１８】
前記組を前記検索要求者に伝えるステップと、
所定の期間内に、前記検索要求者から、前記組の中で送信されたクエリに対応する選択が受信されないことを判定するステップと、
前記ランク付け基準に従って順序付けされた予測クエリの後続の組を、前記検索要求者に送信するステップとをさらに含む、請求項２に記載の方法。
【請求項１９】
前記組を前記検索要求者に伝えるステップと、
予測クエリの後続の組に対する要求を、前記検索要求者から受信するステップと、
予測クエリの後続の組を識別するステップと、
前記ランク付け基準に従って順序付けされた予測クエリの前記後続の組を、前記検索要求者に送信するステップとをさらに含む、請求項２に記載の方法。
【請求項２０】
前記部分クエリを受信するステップの前に、ユーザのコミュニティによって以前に発行された、履歴クエリの組を識別するステップであって、履歴クエリの前記組の中の各クエリは、発行頻度を有し、少なくとも１つの表意文字を含む、ステップと、
前記部分クエリを受信するステップの前に、履歴クエリの前記識別された組から、複数の順序付けされたサブセットを生成するステップであって、各順序付けされたサブセットは、履歴クエリの前記識別された組からの１つまたは複数の履歴クエリが、それぞれの発行頻度に従って順序付けされたものを含む、ステップと、を含む請求項２に記載の方法。
【請求項２１】
前記生成するステップは、
複数の履歴クエリからの１つまたは複数の表意文字の文字列を、１つまたは複数の表音文字の文字列を含む１つまたは複数の表示にマッピングするステップを含む、請求項２０に記載の方法。
【請求項２２】
前記生成するステップは、複数の履歴クエリからの１つまたは複数の表意文字の文字列を、１つまたは複数の表示にマッピングするステップを含み、少なくとも１つのマッピングは、少なくとも１つの表意文字と、１つまたは複数の表音文字の文字列とを含む、請求項２０に記載の方法。
【請求項２３】
ユーザのコミュニティによって以前に発行された履歴クエリの組を識別するステップであって、履歴クエリの前記組の中の各クエリは、発行頻度を有し、少なくとも１つの表意文字を含む、ステップと、
履歴クエリの前記識別された組から、複数の順序付けされたサブセットを生成するステップであって、各順序付けされたサブセットは、履歴クエリの前記識別された組からの１つまたは複数の履歴クエリが、それぞれの発行頻度に従って順序付けされたものを含む、ステップと、を含む請求項２に記載の方法。
【請求項２４】
前記生成するステップは、
複数の履歴クエリからの１つまたは複数の表意文字の文字列を、１つまたは複数の表音文字の文字列を含む１つまたは複数の表示にマッピングするステップを含む、請求項２３に記載の方法。
【請求項２５】
前記部分クエリを受信するステップの前に、複数の組を識別するステップであって、各組は、部分クエリ単位に関連付けられ、ユーザのコミュニティによって以前に発行された複数のクエリを含み、各クエリは、それぞれのランク付け値を有する、ステップと、
前記部分クエリを受信するステップの前に、前記複数の前記組の少なくとも部分について、前記組の中の前記クエリを、前記それぞれのランク付け値に従って順序付けするステップとを含み、
前記予測するステップは、前記複数の組の中から第１の組を識別するステップを含み、前記選択される組は前記部分クエリに対応する、請求項２に記載の方法。
【請求項２６】
前記予測するステップは、第２の組を識別するステップと、前記第１の組および前記第２の組をマージするステップとを含む、請求項２５に記載の方法。
【請求項２７】
前記予測するステップは、
第１のメモリから前記第１の組を識別するステップと、
第２のメモリから前記第２の組を識別するステップとをさらに含む、請求項２６に記載の方法。
【請求項２８】
表意文字と表音文字とを有する言語のための、クエリ補完を提案するためのシステムであって、
完全なクエリの部分を含む部分クエリを、検索要求者から受信するための、クエリ処理モジュールと、
ランク付け基準に従って順序付けされた予測クエリの少なくとも１つの組であって、前記組は、１つまたは複数の表意文字の文字列を有するクエリを少なくとも含む、組と、
前記ランク付け基準に従って順序付けされた予測クエリの前記組を、前記部分クエリから予測するための、予測モジュールと、
順序付けされた予測クエリの前記組を、前記検索要求者に伝えるための、通信モジュールとを備えるシステム。
【請求項２９】
前記部分クエリは、少なくとも１つの表音文字を含む、請求項２８に記載のシステム。
【請求項３０】
前記部分クエリは、表意文字および表音文字の両方を含む、請求項２８に記載のシステム。
【請求項３１】
前記部分クエリは、少なくとも１つの表意文字を表す少なくとも１つの不完全な表音文字列を含み、
予測クエリの前記組の中の少なくとも１つの予測クエリは、前記不完全な表音文字列と整合性がある少なくとも１つまたは複数の表意文字を含む、請求項２８に記載のシステム。
【請求項３２】
予測クエリの前記組は、ユーザのコミュニティによって発行されたクエリを含む、請求項２８に記載のシステム。
【請求項３３】
予測クエリの前記組は、前記検索要求者によって以前に発行されていない少なくとも１つのクエリを含む、請求項２８に記載のシステム。
【請求項３４】
予測クエリの前記組は、検索クエリと、少なくとも１つのＵＲＬとの両方を含む、請求項２８に記載のシステム。
【請求項３５】
ランク付け基準に従って順序付けされた予測クエリの少なくとも第２の組をさらに含み、前記第２の組は、１つまたは複数の表意文字の文字列を有する少なくとも１つのクエリを含み、
前記予測モジュールは、予測クエリの少なくとも前記第１の組と前記第２の組とを識別して、前記２つの組をマージするようにさらに構成される、請求項２８に記載のシステム。
【請求項３６】
前記予測モジュールは、前記第１の組と前記第２の組とを交互配置方式でマージするようにさらに構成される、請求項３５に記載のシステム。
【請求項３７】
前記第１の組は、前記第２の組から離れた場所に配置される、請求項３５に記載のシステム。
【請求項３８】
入力を受信するための受信モジュールであって、前記入力が、順序付けされた予測クエリの前記組の中から選択されるクエリを識別する、受信モジュールと、
前記受信したクエリに関連する検索結果を生成するための、クエリサーバとをさらに備える、請求項２８に記載のシステム。
【請求項３９】
前記クエリサーバは、前記予測クエリのうちの少なくとも１つに関連する検索結果を生成し、前記検索結果を前記要求者に伝えるようにさらに構成される、請求項２８に記載のシステム。
【請求項４０】
前記受信したクエリ情報から、関連するクエリ情報を判定するための概念モジュールをさらに含み、
前記サブセットは、前記関連するクエリ情報に関連する少なくとも１つの予測クエリを含む、請求項２８に記載のシステム。
【請求項４１】
前記予測モジュールは、前記予測クエリの日付／時刻値に従って、前記予測クエリを順序付けするようにさらに構成される、請求項２８に記載のシステム。
【請求項４２】
ユーザに関連付けられた特性に基づいた前記組の修正をさらに含む、請求項２８に記載のシステム。
【請求項４３】
前記予測モジュールは、
前記組を前記検索要求者に伝え、
予測クエリの後続の組に対する要求を、前記検索要求者から受信し、
予測クエリの後続の組を識別し、
前記ランク付け基準に従って順序付けされた予測クエリの前記後続の組を、前記検索要求者に送信するようにさらに構成される、請求項２８に記載のシステム。
【請求項４４】
前記予測モジュールは、さらに、
前記部分クエリを受信する前に、ユーザのコミュニティによって以前に発行された履歴クエリの組を識別するように構成され、履歴クエリの前記組の中の各クエリは、発行頻度を有し、少なくとも１つの表意文字を含み、
前記部分クエリを受信する前に、履歴クエリの前記識別された組から、複数の順序付けされたサブセットを生成するように構成され、各順序付けされたサブセットは、履歴クエリの前記識別された組からの１つまたは複数の履歴クエリが、それぞれの発行頻度に従って順序付けされたものを含む、請求項２８に記載のシステム。
【請求項４５】
前記予測モジュールは、
複数の履歴クエリからの１つまたは複数の表意文字の文字列を、１つまたは複数の表音文字の文字列を含む１つまたは複数の表示にマッピングするようにさらに構成される、請求項４４に記載のシステム。
【請求項４６】
前記予測モジュールは、複数の履歴クエリからの１つまたは複数の表意文字の文字列を、１つまたは複数の表示にマッピングするようにさらに構成され、少なくとも１つのマッピングは、少なくとも１つの表意文字と、１つまたは複数の表音文字の文字列とを含む、請求項４４に記載のシステム。
【請求項４７】
前記予測モジュールは、
ユーザのコミュニティによって以前に発行された履歴クエリの組を識別するように構成され、履歴クエリの前記組の中の各クエリは、発行頻度を有し、少なくとも１つの表意文字を含み、
履歴クエリの前記識別された組から、複数の順序付けされたサブセットを生成するように構成され、各順序付けされたサブセットは、履歴クエリの前記識別された組からの１つまたは複数の履歴クエリが、それぞれの発行頻度に従って順序付けされたものを含む、請求項２８に記載のシステム。
【請求項４８】
前記予測モジュールは、複数の履歴クエリからの１つまたは複数の表意文字の文字列を、１つまたは複数の表音文字の文字列を含む１つまたは複数の表示にマッピングするようにさらに構成される、請求項４７に記載のシステム。
【請求項４９】
前記予測モジュールは、さらに、
前記部分クエリを受信する前に、複数の組を識別するように構成され、各組は、部分クエリ単位に関連付けられ、ユーザのコミュニティによって以前に発行された複数のクエリを含み、各クエリは、それぞれのランク付け値を有し、
前記部分クエリを受信する前に、前記複数の組の少なくとも部分について、前記組の中の前記クエリを、前記それぞれのランク付け値に従って順序付けするように構成され、
前記複数の組の中から第１の組を予測するように構成され、前記選択される組は前記部分クエリに対応する、請求項２８に記載のシステム。
【請求項５０】
前記予測モジュールは、第２の組を予測し、前記第１の組と前記第２の組とをマージするようにさらに構成される、請求項４９に記載のシステム。
【請求項５１】
前記予測モジュールは、
第１のメモリから前記第１の組を識別し、
第２のメモリから前記第２の組を識別するようにさらに構成される、請求項５０に記載のシステム。
【請求項５２】
コンピュータシステムとともに使用するためのコンピュータプログラム製品であって、
完全なクエリの部分を含む部分クエリを、検索要求者から受信するための命令と、
ランク付け基準に従って順序付けされた予測クエリの組を、前記部分クエリから予測するための命令であって、前記組は、１つまたは複数の表意文字を有する少なくとも１つの文字列を含む、命令と、
順序付けされた予測クエリの前記組を、前記検索要求者に伝えるための命令とを含む、コンピュータプログラム製品。
【請求項５３】
前記部分クエリは、少なくとも１つの表音文字を含む、請求項５２に記載のコンピュータプログラム製品。
【請求項５４】
前記部分クエリは、表意文字および表音文字の両方を含む、請求項５２に記載のコンピュータプログラム製品。
【請求項５５】
前記部分クエリは、少なくとも１つの表意文字を表す少なくとも１つの不完全な表音文字列を含み、
前記予測のための前記命令は、前記不完全な表音文字列と整合性がある少なくとも１つまたは複数の表意文字を予測するための命令をさらに含む、請求項５２に記載のコンピュータプログラム製品。
【請求項５６】
予測クエリの前記組の中に、ユーザのコミュニティによって発行されたクエリを含めるための命令をさらに含む、請求項５２に記載のコンピュータプログラム製品。
【請求項５７】
ユーザのコミュニティによって発行されたクエリから、予測クエリの前記組を作成するための命令をさらに含む、請求項５２に記載のコンピュータプログラム製品。
【請求項５８】
予測クエリの前記組は、前記要求者によって以前に発行されていない少なくとも１つのクエリを含む、請求項５２に記載のコンピュータプログラム製品。
【請求項５９】
前記組は、検索クエリと、少なくとも１つのＵＲＬとの両方を含む、請求項５２に記載のコンピュータプログラム製品。
【請求項６０】
予測のための前記命令は、前記部分クエリに対応する２つ以上の組を識別するため命令、及び前記組をマージするための命令をさらに含む、請求項５２に記載のコンピュータプログラム製品。
【請求項６１】
前記組を交互配置方式でマージするための命令をさらに含む、請求項６０に記載のコンピュータプログラム製品。
【請求項６２】
少なくとも、前記組のうちの第１の組はクライアント上で生成され、前記組のうちの第２の組はサーバ上で生成される、請求項６０に記載のコンピュータプログラム製品。
【請求項６３】
入力を受信するための命令であって、前記入力は、順序付けされた予測クエリの前記組の中から選択されるクエリを識別する、命令と、
前記受信したクエリに関連する検索結果を生成するための命令とを含む、請求項５２に記載のコンピュータプログラム。
【請求項６４】
前記予測クエリのうちの少なくとも１つに関連する検索結果を生成するための命令と、
前記検索結果を前記要求者に伝えるための命令とを含む、請求項５２に記載のコンピュータプログラム製品。
【請求項６５】
前記受信したクエリ情報から、関連するクエリ情報を判定するための命令と、
前記関連するクエリ情報に関連する少なくとも１つの予測クエリを識別するための命令と、
前記関連するクエリ情報に関連する前記少なくとも１つの予測クエリを、前記サブセット内に含めるための命令と、をさらに含む、請求項５２に記載のコンピュータプログラム製品。
【請求項６６】
予測のための前記命令は、前記予測クエリの日付／時刻値に従って、前記予測クエリを順序付けすることをさらに含む、請求項５２に記載のコンピュータプログラム製品。
【請求項６７】
ユーザに関連付けられた特性に基づいて前記組を修正するための命令をさらに含む、請求項５２に記載のコンピュータプログラム製品。
【請求項６８】
前記組を前記検索要求者に伝えるための命令と、
所定の期間内に、前記検索要求者から、前記組の送信されたクエリに対応する選択が受信されないことを判定するための命令と、
前記ランク付け基準に従って順序付けされた予測クエリの後続の組を前記検索要求者に送信するための命令と、をさらに含む、請求項５２に記載のコンピュータプログラム製品。
【請求項６９】
前記組を前記検索要求者に伝えるための命令と、
予測クエリの後続の組に対する要求を、前記検索要求者から受信するための命令と、
予測クエリの後続の組を識別するための命令と、
前記ランク付け基準に従って順序付けされた予測クエリの前記後続の組を、前記検索要求者に送信するための命令と、をさらに含む、請求項５２に記載のコンピュータプログラム製品。
【請求項７０】
前記部分クエリを受信する前に、ユーザのコミュニティによって以前に発行された履歴クエリの組を識別するための命令であって、履歴クエリの前記組の中の各クエリは、発行頻度を有し、少なくとも１つの表意文字を含む、命令と
前記部分クエリを受信する前に、履歴クエリの前記識別された組から、複数の順序付けされたサブセットを生成するための命令であって、各順序付けされたサブセットは、履歴クエリの前記識別された組からの１つまたは複数の履歴クエリが、それぞれの発行頻度に従って順序付けされたものを含む、命令と、を含む、請求項５２に記載のコンピュータプログラム製品。
【請求項７１】
生成するための前記命令は、複数の履歴クエリからの１つまたは複数の表意文字の文字列を、１つまたは複数の表音文字の文字列を含む１つまたは複数の表示にマッピングするための命令をさらに含む、請求項７０に記載のコンピュータプログラム製品。
【請求項７２】
生成するための前記命令は、複数の履歴クエリからの１つまたは複数の表意文字の文字列を、１つまたは複数の表示にマッピングするための命令をさらに含み、少なくとも１つのマッピングは、少なくとも１つの表意文字と、１つまたは複数の表音文字の文字列とを含む、請求項７０に記載のコンピュータプログラム製品。
【請求項７３】
ユーザのコミュニティによって以前に発行された履歴クエリの組を識別するための命令であって、履歴クエリの前記組の中の各クエリは、発行頻度を有し、少なくとも１つの表意文字を含む、命令と、
履歴クエリの前記識別された組から、複数の順序付けされたサブセットを生成するための命令であって、各順序付けされたサブセットは、履歴クエリの前記識別された組からの１つまたは複数の履歴クエリが、それぞれの発行頻度に従って順序付けされたものを含む、命令と、を含む、請求項５２に記載のコンピュータプログラム製品。
【請求項７４】
生成するための前記命令は、複数の履歴クエリからの１つまたは複数の表意文字の文字列を、１つまたは複数の表音文字の文字列を含む１つまたは複数の表示にマッピングするための命令をさらに含む、請求項７４に記載のコンピュータプログラム製品。
【請求項７５】
前記部分クエリを受信する前に、複数の組を識別するための命令であって、各組は、部分クエリ単位に関連付けられ、ユーザのコミュニティによって以前に発行された複数のクエリを含み、各クエリは、それぞれのランク付け値を有する、命令と、
前記部分クエリを受信する前に、前記複数の前記組の少なくとも部分について、前記組の中の前記クエリを、前記それぞれのランク付け値に従って順序付けするための命令と、を含み、
予測するための前記命令は、前記複数の組の中から第１の組を識別することをさらに含み、前記選択される組は前記部分クエリに対応する、請求項５２に記載のコンピュータプログラム製品。
【請求項７６】
予測するための前記命令は、第２の組を識別し、前記第１の組と前記第２の組とをマージするための命令をさらに含む、請求項７５に記載のコンピュータプログラム製品。
【請求項７７】
予測するための前記命令は、
クライアント上で前記第１の組を識別するための命令と、
サーバ上で前記第２の組を識別するための命令とをさらに含む、請求項７６に記載のコンピュータプログラム製品。
【請求項７８】
表意文字と表音文字とを有する言語のための、クエリ補完を提案するためのシステムであって、
部分クエリを検索要求者から受信するための手段であって、部分クエリは完全なクエリの部分を含む、手段と、
ランク付け基準に従って順序付けされた予測クエリの組を、前記部分クエリから予測するための手段であって、前記組は、１つまたは複数の表意文字を有する少なくとも１つの文字列を含む、手段と、
順序付けされた予測クエリの前記組を、前記検索要求者に伝えるための手段とを備えるシステム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【公開番号】特開２０１２−１０８９５９（Ｐ２０１２−１０８９５９Ａ）
【公開日】平成２４年６月７日（２０１２．６．７）
【国際特許分類】
【外国語出願】
【出願番号】特願２０１２−４６４９２（Ｐ２０１２−４６４９２）
【出願日】平成２４年３月２日（２０１２．３．２）
【分割の表示】特願２００７−５４１１８５（Ｐ２００７−５４１１８５）の分割
【原出願日】平成１７年１０月１１日（２００５．１０．１１）
【出願人】（５０２２０８３９７）グーグル インコーポレイテッド (161)
【Ｆターム（参考）】
【公開日】平成２４年６月７日（２０１２．６．７）
【国際特許分類】
【出願番号】特願２０１２−４６４９２（Ｐ２０１２−４６４９２）
【出願日】平成２４年３月２日（２０１２．３．２）
【分割の表示】特願２００７−５４１１８５（Ｐ２００７−５４１１８５）の分割
【原出願日】平成１７年１０月１１日（２００５．１０．１１）
【出願人】（５０２２０８３９７）グーグル インコーポレイテッド (161)
【Ｆターム（参考）】
[ Back to top ]