用於部分輸入的搜索查詢的自動完成和自動輸入法校正的製作方法

2023-05-19 05:41:46 2

專利名稱：用於部分輸入的搜索查詢的自動完成和自動輸入法校正的製作方法
技術領域：
所公開的實施例一般涉及用於定位在計算機網絡(例如計算機系統的分布式系 統)中的文檔的搜尋引擎，具體地，涉及用於通過預測用戶的請求而使期望的搜索加速的 系統和方法。
背景技術：
搜尋引擎提供了用於定位在大型文檔資料庫中的文檔的強大工具，所述文檔諸如 在全球資訊網(WWW)上的文檔或存儲在內聯網的計算機上的文檔。響應於由用戶提交的搜索查 詢而定位文檔。搜索查詢可以由一個或多個搜索詞語組成。在輸入查詢的一個方法中，用戶通過添加連續的搜索詞語直至輸入了所有搜索詞 語來輸入查詢。一旦用戶發信號已輸入了查詢的所有搜索詞語，則將查詢發送給搜尋引擎。 在下面描述的本發明的實施例使用輸入查詢的另一個方法。在這個新方法中，在用戶指示 完成查詢之前將部分查詢傳送給搜尋引擎。搜尋引擎生成向用戶展示的預測的查詢的列 表。用戶可以從預測的查詢的排序列表選擇，或者可以繼續輸入用戶指定的查詢。

發明內容
根據在下面描述的一些實施例，在伺服器處執行、用於處理查詢信息的方法包括 從搜索請求者接收部分搜索查詢，該搜索請求者位於遠離伺服器的位置。方法進一步包括 從多個先前提交的完整查詢獲取與部分搜索查詢相對應的預測的完整查詢的集合，其中先 前提交的完整查詢由用戶群體提交。預測的完整查詢的集合包括第一語言和第二語言完整 搜索查詢兩者。另外，方法包括根據排名標準對預測的完整查詢的集合進行排序，並且將排 序的集合的至少一個子集遞送給搜索請求者。根據一些實施例，在客戶端處執行、用於處理查詢信息的方法包括從搜索請求者 接收部分搜索查詢。方法進一步包括從多個先前提交的完整查詢獲取與部分搜索查詢相對 應的預測的完整查詢的集合，其中先前提交的完整查詢由用戶群體提交。預測的完整查詢 的集合包括第一語言和第二語言完整搜索查詢兩者，並且根據排名標準被排序。另外，方法 包括向搜索請求者顯示排序的集合的至少一個子集。根據一些實施例，用於構建用於處理查詢信息的數據結構的方法包括獲取先前提 交的完整第一語言查詢的集合，其中完整第一語言查詢由用戶群體先前提交。方法進一步 包括獲取先前提交的完整第二語言查詢的集合，其中完整第二語言查詢由用戶群體先前提 交。另外，方法包括將完整第一語言查詢的集合轉換為以使用第二語言的字符的表示形式 的完整第一語言查詢的集合，並且將完整第二語言查詢的集合和轉換的完整第一語言查詢 的集合存儲在一個或多個查詢完成數據表中。一個或多個查詢完成數據表形成能夠被用來 預測與部分第一語言查詢或部分第二語言查詢相對應的完整第一語言查詢和完整第二語 言查詢兩者的一個或多個數據結構。在一些實施例中，用於處理查詢信息的系統包括用於執行程序的一個或多個中央處理單元，以及用來存儲數據以及存儲由一個或多個中央處理單元執行的程序的存儲器。 程序包括用於從搜索請求者接收部分搜索查詢的指令，搜索請求者位於遠離伺服器的位 置。程序進一步包括用於從多個先前提交的完整查詢獲取與部分搜索查詢相對應的預測的 完整查詢的集合的指令，其中先前提交的完整查詢由用戶群體提交。預測的完整查詢的集 合包括第一語言和第二語言完整搜索查詢兩者。另外，程序進一步包括用於根據排名標準 對預測的完整查詢的集合進行排序，並且將排序的集合的至少一個子集遞送給搜索請求者 的指令。在一些實施例中，客戶端系統包括用於執行程序的一個或多個中央處理單元，以 及用來存儲數據以及存儲由一個或多個中央處理單元執行的程序的存儲器，程序包括用於 從搜索請求者接收部分搜索查詢的指令。程序進一步包括用於從多個先前提交的完整查詢 獲取與部分搜索查詢相對應的預測的完整查詢的集合的指令，其中先前提交的完整查詢由 用戶群體提交。預測的完整查詢的集合包括第一語言和第二語言完整搜索查詢兩者，並且 根據排名標準被排序。另外，程序進一步包括用於向搜索請求者顯示排序的集合的至少一 個子集的指令。在一些實施例中，計算機可讀存儲介質存儲用於由各個伺服器系統的一個或多個 處理器執行的一個或多個程序。一個或多個程序包括用於從搜索請求者接收部分搜索查詢 的指令，搜索請求者位於遠離伺服器的位置。一個或多個程序進一步包括用於從多個先前 提交的完整查詢獲取與部分搜索查詢相對應的預測的完整查詢的集合的指令，先前提交的 完整查詢由用戶群體提交。預測的完整查詢的集合包括第一語言和第二語言完整搜索查詢 兩者。另外，一個或多個程序包括用於根據排名標準對預測的完整查詢的集合進行排序，並 且將排序的集合的至少一個子集遞送給搜索請求者的指令。在一些實施例中，計算機可讀存儲介質存儲用於由各個客戶端設備或系統的一個 或多個處理器執行的一個或多個程序。一個或多個程序包括用於從搜索請求者接收部分搜 索查詢的指令。一個或多個程序進一步包括用於從多個先前提交的完整查詢獲取與部分搜 索查詢相對應的預測的完整查詢的集合的指令，先前提交的完整查詢由用戶群體提交。預 測的完整查詢的集合包括第一語言和第二語言完整搜索查詢兩者，並且根據排名標準被排 序。另外，一個或多個程序包括用於向搜索請求者顯示排序的集合的子集的指令。由於統一的解決方案在自動提供輸入法校正時支持不完整的朝鮮語字符輸入，故 其具有對朝鮮語查詢預測的特定應用。


作為結合附圖的本發明的各個方面的下列詳細描述的結果，將更清楚地理解本發明的前述實施例以及額外的實施例。在附圖的全部多個視圖中相同的參考數字指代對應的 部分。圖1是根據一些實施例的搜索系統的框圖。圖2是描述了根據一些實施例的與創建並使用數據結構相關聯的信息流的概念 圖。圖3A是根據一些實施例的部分查詢的處理的方法的流程圖。圖3B是根據一些實施例的由在客戶端系統或設備處的搜索助手執行的過程的流程圖。圖4A和4B描述了用於在朝鮮語字符和朝鮮語字符的羅馬化表示形式之間的轉換 的字符映射表。圖5是根據一些實施例的用於將一串朝鮮語字符轉換為羅馬化表示形式的過程 的流程圖。圖6描述了根據一些實施例的與輸入字符串相對應的預測的完整查詢的示例。圖7描述了根據一些實施例的用於處理歷史查詢的過程。圖8描述了根據一些實施例的與在歷史搜索查詢的集合中的完整搜索查詢的兩 個示例相對應的部分搜索查詢。圖9是根據一些實施例的用於識別與所接收的部分查詢相對應的查詢完成表的 過程的概念表示。圖10描述了根據一些實施例的兩個示例查詢完成表的部分。圖11是根據一些實施例的客戶端系統的框圖。圖12是根據一些實施例的伺服器系統的框圖。圖13描述了根據一些實施例的列出與用戶提供的部分查詢相對應的英語和朝鮮 語預測的完整查詢的web瀏覽器、在web瀏覽器中顯示的網頁或其它用戶界面的示意截屏。
具體實施例方式圖1圖示了適於本發明的實施例的實踐的系統100。在於2004年11月11日提交 的「Method and System for Autocompletion Using RankedResults(用於使用排名結果的自動完成的方法和系統)，，的共同未決、普通轉讓的美國專利申請序列號No. 10/987，295， 以及於 2004 年 11 月 12 日提交的 「Method and System for Autocompletion for LanguagesHaving Ideographs and Phonetic Characters (用於具有象形和語言字符的語言的自動完成的方法和系統)」的共同未決、普通轉讓的美國專利申請序列號 No. 10/987，769中提供了與分布式系統和其各種功能組件有關的額外詳情，在此通過引用 將所述申請的內容整體合併。系統100可以包括位於遠離搜尋引擎108的位置的一個或多 個客戶端系統或設備102。有時被稱為客戶端或客戶端設備的各個客戶端系統102可以是 臺式計算機、膝上型計算機、信息站、蜂窩電話、個人數字助理等。通信網絡106將客戶端系 統或設備102連接到搜尋引擎108。當用戶(在此也被稱為搜索請求者)在客戶端系統102 處輸入查詢時，在該用戶完成輸入完整查詢之前搜索助手104將該用戶的部分查詢的至少 部分傳送到搜尋引擎108。搜尋引擎108使用部分查詢的傳送部分來預測用戶的最終完整 查詢。這些預測被傳送回該用戶。如果預測中的一個是該用戶的預期查詢，則該用戶可以 在不必完成查詢的輸入的情況下選擇預測的查詢。如在此進一步描述的，搜索系統100和其功能組件已被調整，以便以統一的方式 處理多種語言的部分查詢。搜索系統100已被調整，以便在不考慮由搜索助手104傳送到 搜尋引擎108的部分查詢的語言編碼的情況下，基於在客戶端系統102處的用戶的實際輸 入來提供預測的查詢。例如在用戶使用在客戶端系統102處的不正確輸入法編輯器設置輸 入了部分查詢的情況下這尤其有用。搜尋引擎108包括查詢伺服器110，其具有接收並處理部分查詢以及將部分查詢轉送到預測伺服器112的模塊120。預測伺服器112負責生成與所接收的部分查詢相對應的預測的完整查詢的列表。預測伺服器112依賴於由排序集合構建器142在預處理階段構 造的數據結構。排序集合構建器142使用不同語言的查詢日誌124、126來構造數據結構。 圖2圖示了由排序集合構建器142執行的預處理的一個實施例。圖3A圖示了由預測服務 器112執行的處理的一個實施例。另外，在一些實施例中，查詢伺服器110接收完整搜索查 詢並且將完整搜索查詢轉送到查詢處理模塊114。 參見圖2，說明性地展示了兩個查詢日誌第一語言的查詢日誌201和第二語言的 查詢日誌202。查詢日誌201、202包含由搜尋引擎在一段時間內從用戶群體接收的各自語 言的先前提交的查詢的日誌。可選地，提交在查詢日誌201中的查詢的用戶群體可以與提 交在查詢日誌202中的查詢的用戶群體不同，在這種情況下前述「用戶群體」包括兩個或多 個用戶群體。在查詢日誌201、202中的每一個查詢條目可以包括元信息，諸如指示查詢被 提交的次數的頻率信息。查詢日誌201、202中的每一個可以由一個或多個特定語言過濾器 204,205過濾，例如以排除與詞語的一個或多個預定集合相匹配的查詢，所述預定集合諸如 可能被認為是令人反感的、文化敏感的等單詞。在第二語言的查詢日誌202中的查詢以其 現存形式被利用。然而，在250處將在第一語言的查詢日誌201中的查詢轉換為第二語言 的表示形式。第二語言的表示形式與由用戶在使用設置為第二語言的輸入法時試圖輸入第 一語言的查詢而生成的第二語言的字符相對應。例如，如在下面進一步描述的，一種語言諸 如朝鮮語的查詢可以由在字母數字鍵盤上的鍵擊來表示，所述鍵擊與使用被不正確地設置 為英語的輸入法編輯器來輸入朝鮮語查詢相對應。然而，在其它實施例中，第一語言不必是 朝鮮語，而替代地可以是日語、中文或大量其它語言中的任何語言。類似地，第二語言不必 是英語，而替代地可以是法語、德語、西班牙語、俄語或大量其它語言中的任何語言。過濾的 查詢日誌202和過濾的查詢日誌201的轉換的輸出由排序集合構建器208組合在一起並同 時利用。排序集合構建器208創建一個或多個組合數據結構，組合數據結構能夠被用來處 理兩種語言的部分查詢。 排序集合構建器208構造一個或多個查詢完成表212。如在下面進一步說明的，一 個或多個查詢完成表212被用於生成用於第一和第二語言兩者的預測。在查詢完成表212 中的每一個條目存儲查詢字符串和額外信息。額外信息包括可以基於在查詢日誌中的查詢 的頻率的排名分值、查詢由用戶群體中的用戶提交時的日期/時間值、和/或其它因素。關 於查詢的額外信息可選地包括指示完整搜索查詢的語言的值。在各個查詢完成表212中 的每一個條目表示與部分查詢相關聯的預測的完整查詢。如在下面參考圖9所描述的，在 一些實施例中，被接收的部分查詢被分成兩部分前綴部分和後綴部分。此外，在一些實施 例中，與同一前綴相關聯的一組預測的完整查詢被存儲在按頻率或分值排序的查詢完成表 212中。可選地，查詢完成表212由對應的部分搜索查詢的查詢指紋進行索引，其中每一個 部分搜索查詢的查詢指紋通過將哈希函數(或其它指紋函數)應用於部分搜索查詢或部分 搜索查詢的前綴來生成。可選地，查詢指紋被存儲在指紋到表的映射表210中用於快速查 找。 在一些實施例中，將第一語言(例如朝鮮語、日語、中文等)的預測的完整查詢以 使用第二語言(例如英語、西班牙語、法語、德語、俄語等)的字符的轉換的表示形式(例如 羅馬化表示形式)存儲在一個或多個查詢完成表212中。因此，在這些實施例中，排序集合構建器208將完整第二語言(例如英語)查詢的集合和以其轉換的表示形式的完整第一語 言(例如朝鮮語)查詢的集合存儲在一個或多個查詢完成表212中。然而，將在查詢完成 表212中的預測的完整查詢以在查詢日誌201中的原始查詢的語言向用戶表示並顯示。然 而，在其它實施例中，儘管第一語言的查詢被存儲在通過將哈希函數(或其它指紋函數)應 用於對應的部分搜索查詢的轉換的表示形式來識別的查詢完成表中，但是預測的完整查詢 以其原始語言被存儲在一個或多個查詢完成表212中。參見圖3A，在用戶輸入搜索查詢時，客戶端系統102監視用戶的輸入(308)。在用 戶(有時被稱為請求者)發信號完成搜索查詢之前，將用戶的查詢的至少部分從客戶端系 統發送到搜尋引擎304(310)。查詢的部分可以是幾個字符、一個搜索詞語或多於一個搜索 詞語。注意到，可以以第一語言或第二語言輸入部分查詢。搜尋引擎304接收部分搜索查詢用於處理(312)並且前進到對關於用戶的預期的 完整查詢進行預測(313)。首先，搜尋引擎304確定部分查詢是以第一語言還是以第二語言 編碼(314)。如果部分查詢以第一語言編碼，則搜尋引擎304在前進之前將部分查詢轉換為 第二語言的上述表示形式(316)。如果部分查詢以第二語言編碼，則搜尋引擎304可以直 接前進到處理部分查詢。搜尋引擎304然後應用哈希函數(或其它指紋函數)(318)來創 建指紋320。搜尋引擎304使用指紋320和指紋到表的映射表210來定位與部分查詢相對 應的查詢完成表212來執行查找操作(322)。查找操作包括對指紋到表的映射表210搜索 與部分查詢的指紋320相匹配的指紋。當找到匹配時，指紋到表的映射表210的對應條目 識別查詢完成表(或替選地，在具有關於多個部分查詢的條目的查詢完成表中的條目的集 合)。如在下面更詳細地描述的，查詢完成表212可以包括與部分查詢相匹配或相對應的多 個條目，以及指紋到表的映射表210被用來定位查詢完成表或這些條目的第一個(或最後 一個)。查找操作(322)產生與所接收的部分搜索查詢相對應的預測的完整查詢的集合。在查詢完成表中的每一個條目包括預測的完整查詢和諸如關於預測的完整查詢 的頻率或分值的其它信息。搜尋引擎304使用信息來構造完整查詢預測的排序集合(326)。 在一些實施例中，將集合按頻率或分值排序。搜尋引擎304然後將預測的完整查詢的至少 一個子集(328)返回給接收排序的預測的完整查詢(329)的客戶端。客戶端前進到顯示排 序的預測的完整查詢的至少一個子集(330)。注意到，由於部分查詢可以與在查詢完成表212中的任一語言的查詢條目潛在匹 配，故完整查詢預測的排序集合可以以任一語言。搜尋引擎304可以被配置為返回混合語 言預測的完整查詢或者可以被配置為選擇更可能預測部分查詢的那種語言。在搜尋引擎 304生成以除在部分查詢中編碼的語言外的語言形式的預測的完整查詢的情況下，預測的 完整查詢表示自動輸入法校正建議。如在上面參考圖2所注意的，在構建查詢完成表時，可以對來自用戶群體的歷史查詢日誌的查詢進行過濾。然而，額外的過濾可以由各種用戶組(例如，請求了這樣的過濾 的用戶)請求或者代表各種用戶組而被應用。因此，在一些實施例中，在對預測的完整查詢 進行排序(326)之前或者在將預測的完整查詢遞送給客戶端(328)之前，對預測的完整查 詢的集合進行過濾以移除與在一個或多個預定詞語集合中的一個或多個詞語相匹配的查 詢，如果存在這樣的查詢的話。例如，一個或多個預定詞語集合可以包括被認為是令人反感 的或文化敏感的等英語詞語和朝鮮語詞語。執行該方法的系統可以包括存儲在存儲器中的識別一個或多個預定詞語集合的一個或多個表(或其它數據結構)。在一些其它實施例中，遞送給客戶端(328)的預測的完整查詢的集合在客戶端處被過濾以移除與在一個或多 個預定詞語集合中的一個或多個詞語相匹配的查詢，如果存在這樣的查詢的話。可選地，多 個不同的過濾器可以被用於多個不同的用戶組。在一些實施例中，使用運行期間過濾(響 應於部分搜索查詢而執行)替代在查詢完成表的構建期間過濾。圖3B圖示了可以在客戶端系統102的搜索助手104中實現的實施例。搜索助手 104監視用戶將搜索查詢輸入到客戶端系統102上的文本輸入框中(352)。用戶的輸入可 以是一個或多個字符或者一個或多個單詞(例如短語的第一個單詞或前兩個單詞、或者第 一個單詞和開頭字母、複合詞語的短語的新單詞的字符或標誌)。搜索助手104可以識別兩 種不同類型的查詢。第一種，先於在用戶指示完成輸入字符串時，搜索助手104在輸入被識 別時接收或識別部分搜索查詢(如下所述)。第二種，搜索助手104在用戶選擇了展示的預 測或指示完成輸入字符串時接收或識別用戶輸入。當用戶輸入或選擇被識別為完整的用戶輸入時，該完整的用戶輸入被傳送到服務 器用於處理(354)。伺服器返回搜索結果的集合，該集合由搜索助手104或由諸如瀏覽器應 用的客戶端應用接收(356)。在一些實施例中，瀏覽器應用將搜索結果至少作為網頁的一部 分顯示。在一些其它實施例中，搜索助手104顯示搜索結果。替選地，完整的用戶輸入的傳 送(354)和對搜索結果的接收(356)可以由除搜索助手104外的機制來執行。例如，這些 操作可以由使用標準請求和響應協議的瀏覽器應用來執行。以多種方式，諸如當用戶在搜索查詢的輸入期間輸入了回車或等價字符、選擇了 在向用戶展示的圖形用戶界面(GUI)中的「查找」或「搜索」按鈕時，或者通過在搜索查詢 的輸入期間選擇向用戶展示的預測的查詢的集合中的一個，搜索助手104(或瀏覽器或其 它應用)可以將用戶輸入識別為完整的用戶輸入。本領域的技術人員將認識發信號搜索查 詢的最終輸入的多種方式。在用戶發信號完整的用戶輸入之前，部分搜索查詢可以被識別。例如，部分搜索查 詢通過檢測對在文本輸入框中的字符的輸入或刪除來識別。一旦部分搜索查詢被識別，該 部分搜索查詢即被傳送給伺服器(358)。響應於該部分搜索查詢，伺服器返回包括預測的完 整搜索查詢的預測。搜索助手104接收(360)並展示(例如顯示、表達等)預測(362)。在向用戶展示了預測的完整查詢(362)後，如果用戶確定預測中的一個與預期輸 入相匹配，則用戶可以選擇預測的完整搜索查詢中的一個。在一些情況中，預測可以向用戶 提供未被考慮的額外信息。例如，用戶可以心裡以一個查詢作為搜索策略的一部分，但是看 見預測的完整查詢促使用戶改變了輸入策略。一旦展示了集合(362)，再次監視用戶的輸入 (352)。如果用戶選擇了預測中的一個，則將用戶輸入作為完整查詢(在此也被稱為完整的 用戶輸入)傳送給伺服器(354)。在傳送請求後，再次監視用戶的輸入活動(352)。在一些實施例中，搜索助手104可以從伺服器預載額外的預測結果(額外的預測 結果中的每一個是預測的完整查詢的集合)(364)。預載的預測結果可以被用來提高對用戶 輸入作出響應的速度。例如，在用戶輸入時，搜索助手104可以預載除關於的 預測結果外的關於〈bana〉、……、以及的預測結果。如果用戶再輸入一個字符，例 如，來生成(部分搜索查詢)輸入，則可以在未將部分搜索查詢傳送到伺服器或 接收預測的情況下顯示關於的預測結果。
在一些實施例中，在客戶端處本地地緩存預測結果的一個或多個集合。在搜索請 求者修改當前查詢以反映以前的部分輸入(例如通過退格以移除一些字符)時，替代將部 分輸入發送給伺服器，從客戶端緩存檢索與以前的部分輸入相關聯的預測結果的集合併且 再次向用戶展示該集合。在一些實施例中，在接收關於最終輸入的搜索結果或文檔(356)後，或者在顯示 預測的完整搜索查詢(362)後，並且可選地預載了預測結果(364)，搜索助手104繼續監視 用戶輸入(352)直至用戶例如通過關閉包含搜索助手104的網頁來終止搜索助手104。在 一些其它實施例中，搜索助手104僅在文本輸入框1320(在下面參考圖13所論述的)被激 活時繼續監視用戶輸入(352)，以及在文本輸入框1320被失活時暫停監視。在一些實施例 中，當在用戶界面中的文本輸入框在瀏覽器應用的當前活動窗口或工具欄中顯示時，該文 本輸入框被激活，以及當文本輸入框不被顯示或者文本輸入框不在瀏覽器應用的活動窗口 或工具欄中時，該文本輸入框被失活。所描述的系統和技術具有關於解決以諸如朝鮮語、日語、中文以及許多其它語言 的語言形式的部分查詢的特定應用。或被稱為謗文的書面朝鮮語利用被組織成音節塊的字 符的音標字母。每一個音節塊由一個首部輔音、一個中部元音以及可選的尾部輔音組成。 存在19種可能的首部輔音，21種可能的元音以及27種可能的尾部輔音。在圖4A和4B中 示出了音節塊的可能的首部、中部以及尾部元素的列表。可以以不同的方式對朝鮮語文本 進行編碼，但是其常規以Unicode傳輸格式來表示，該Unicode傳輸格式使用不同的字符碼 來表示每一個音節塊組合即從ACOO到D7AF的11，172個預定的朝鮮語字符。常規使用 西方字母數字鍵盤布置來輸入朝鮮語文本，其中朝鮮語輔音和元音被映射到鍵盤上的字母 鍵。由於首部輔音需要一次鍵擊、中部元音和尾部輔音每一個需要一次或兩次鍵擊並且尾 部輔音是可選的，故單個朝鮮語音節塊字符需要在鍵盤上的兩次到五次之間的鍵擊。因此，在將部分查詢傳送到搜尋引擎304時用戶輸入朝鮮語查詢可能正在輸入不 完整的朝鮮語字符的中途。此外，用戶可能正使用不正確的輸入法設置來試圖輸入朝鮮語 或英語查詢。所描述的系統和技術提供了用於以下的統一的解決方案通過將部分朝鮮語查詢 轉換為羅馬化表示形式來提供朝鮮語和英語的預測的完整查詢。這些朝鮮語查詢的羅馬化 表示形式與通過用戶使用英語輸入法來試圖輸入朝鮮語查詢而生成的在羅馬化字母表中 的字符相對應。例如，朝鮮語查詢日誌可以包括諸如下列的朝鮮語單詞· 「 Sbl·^ 「 (mobile)(移動) "平言「(google)(谷歌)這些朝鮮語查詢的羅馬化表示形式將是以下 「 etl^ 「 (mobile)(移動)=>"ahqkdlf"·丨丨寧躉」(google)(谷歌)=>"rnrmf"換句話說，用戶在被設置為朝鮮語輸入法的鍵盤上鍵入"ahqkdlf"將輸入朝鮮 語的單詞『『mobile」。圖4A、4B和5圖示了在查詢中的朝鮮語字符串到羅馬化表示形式的轉換。為了實 現該轉換，為形成每一個音節塊字符的組分的每一個輔音或元音計算索引。對於以Unicode 表示的朝鮮語字符，所述字符被安排為
Unicode =(首部輔音*21*28) + (中部元音*28) +可選的尾部+OxACOO該計算可以由數個調節和分割來完成。一旦為每一個朝鮮語字符確定了索引，可 以緩存與輔音和元音索引相對應的英語字母。圖4A和4B示出了不同的朝鮮語輔音和元音 可以如何被映射到給定Unicode編碼的對應的羅馬化字符。圖5圖示了轉換可以如何被處 理。參見圖5，檢索在字符串(例如，完整或部分搜索查詢)中的下一個字符(502)。初始， 在字符串中的第一個字符表示最初的「下一個字符」。確定字符是否被編碼在朝鮮語字符的 音節塊表示形式的範圍內(504)。如果是(504-是)，則如上所述從該字符導出首部和中部 和尾部值(506)。然後根據圖4A和4B將所述值映射到羅馬化字符(508)。然後將羅馬化 字符附加到結果字符串(509)。另一方面，如果該字符不是作為音節塊字符(504-否)而是 作為單個輔音或元音(510-是)來編碼，則輔音或元音(被編碼為字母碼)再次根據在圖 4A和4B中闡明的映射被直接轉換為羅馬化表示形式(512)，以及然後被附加到結果字符串 的末尾(514)。如果該字符不以朝鮮語編碼(510-否)，由於假設該字符已經以羅馬化表示 形式，則可以將該字符直接附加到結果字符串(516)。過程迭代(518)直至到達字符串的末 尾。如上所述，將朝鮮語查詢在預處理階段轉換為羅馬化表示形式並且根據朝鮮語查 詢的羅馬化表示形式將其組織在數據結構中。通過將朝鮮語查詢轉換為羅馬化表示形式， 朝鮮語和英語預測的完整查詢均可以被一起存儲在用於預測伺服器的統一數據結構中。由 於英語查詢和朝鮮語查詢均使用羅馬化字母表來表示，所以相同的預測邏輯可以被利用來 生成英語預測和朝鮮語預測。在用戶將朝鮮語的部分查詢輸入到系統中時，朝鮮語部分查詢被轉換為其羅馬化 表示形式。然後如同任何英語部分查詢，對照關於部分查詢的數據結構核查該羅馬化表示 形式。由於朝鮮語字符由具有與在鍵盤上的原始鍵擊相同的順序的羅馬化字母表示，所以 不完整的朝鮮語查詢被正確地處理。基於該部分查詢來生成預測(即完整查詢)的列表。 顯而易見地，預測的完整查詢可以以朝鮮語或英語。因此，在一些情況下，與部分查詢相對 應的預測的完整查詢包括朝鮮語和英語完整查詢兩者。在用戶使用朝鮮語輸入法來不正確 地輸入了英語部分查詢的情況下，系統將認為羅馬化表示形式潛在地為英語查詢。例如，用 戶可能輸入下列查詢或下列的部分查詢
image see original document page 13由於該查詢未形成任何正確的音節塊，所以該查詢不會生成任何朝鮮語預測。然 而，關於該查詢的羅馬化表示形式為「mobile」，其將與包括英語單詞「mobile」的預測的完 整查詢相匹配，儘管用於部分查詢的語言編碼不正確。在用戶將英語的部分查詢輸入到系統中時，系統將常規地處理該部分查詢。將對 照數據結構核查該英語查詢並且生成預測的列表。此外，由於數據結構包括以羅馬化表示 形式的朝鮮語查詢，所以系統將自動識別由輸入法錯誤產生的朝鮮語預測。圖6示出了與部分查詢「ho 」 602相對應的預測的完整查詢的集合604的示例。 在該示例中，在完整查詢的集合604中的第一位置包括具有最高頻率值的查詢(例如 「hotmail」)，在該集合中的第二位置由具有下一最高頻率值的查詢(例如「hot dogs」)佔 據，等等。在該示例中，在給定的部分查詢和完整查詢之間的對應性由部分查詢在完整查詢的開頭部分的存在來確定(例如，字符「ho」在完整查詢「i^tmail」和「hotels in San Francisco」的開頭部分找到)。在其它實施例中，在給定的部分查詢和完整查詢之間的對應 性由部分查詢在位於完整查詢中的任何位置的搜索詞語的開頭部分的存在來確定，如由完 整查詢的集合606所圖示(例如，字符「ho」在「i^tmail」的開頭部分以及在「cheap hotels in Cape Town」中的第二搜索詞語的開頭部分找到)。為了創建查詢完成表212的集合，從歷史查詢日誌201、202選擇查詢(圖7，702)。 在一些實施例中，只有具有期望的元信息的查詢(例如，語言為英語的查詢)被處理。從 所選擇的查詢識別第一個部分查詢(704)。在一個實施例中，第一個部分查詢是所選擇的 查詢的第一個字符(即，對於查詢字符串「hot dog ingredients」來說為「h」)。在一些 實施例中，在識別部分查詢之前應用預處理(例如，將大寫字母轉換為小寫字母)。在表中 生成指示部分查詢、與部分查詢相對應的完整查詢和其頻率的條目。在其它實施例中，被 用於排名的其它信息(例如，基於完整查詢由用戶群體提交時的日期/時間值和/或其它 因素來計算的排名分值)被存儲。如果所識別的部分查詢未表示整個查詢，則查詢處理未 完成(708-否)。因此，識別下一個部分查詢(710)。在一些實施例中，下一個部分查詢通 過將下一個額外的字符添加到先前識別的部分查詢來識別(即，對於查詢字符串「hot dog ingredients」來說為「ho」)。繼續識別(710)和對查詢完成表的更新(706)的過程直至整 個查詢被處理(708-是)。如果尚未處理完所有的查詢(712-否)，則從歷史查詢日誌選擇 下一個查詢(702)並且對該查詢進行處理直至所有的查詢被處理(712-是)。在一些實施 例中，當將記錄項添加到查詢完成表時，記錄項被插入使得在表中的記錄項根據排名或分 值被排序。在另一個實施例中，所有查詢完成表在表構建過程的末尾被排序使得在每一個 查詢完成表中的記錄項根據在查詢完成表中的記錄項的排名或分值被排序。另外，一個或 多個查詢完成表可以被刪簡，使得表包含不超過預定數量的條目。如上所述，在一些實施例中，在將完整查詢插入查詢完成表中之前從歷史查詢日 志201、202過濾完整查詢(714)以排除與詞語的一個或多個預定集合相匹配的查詢，所述 預定集合諸如可能被認為是令人反感的、文化敏感的等單詞。可選地，提交在查詢日誌201 中的查詢的用戶群體可以與提交在查詢日誌202中的查詢的用戶群體不同，在這種情況下 前述「用戶群體」包括兩個或多個用戶群體。如果查詢被過濾並且因此從為用於插入到查 詢完成表中的候選的查詢的集合被移除，則從歷史查詢日誌201、202選擇下一個查詢(如 果存在的話)(702)。參見圖8，在表802中的804至812處圖示了查詢字符串「hot dogingredients」 的前五個字符的示例處理。在814至820處圖示了查詢字符串「hotmail」的前四個字符的 示例處理。在一些實施例中，關於給定的部分查詢的查詢完成表通過下述來創建從表識別 與給定的部分查詢相對應的n個最經常被提交的查詢並且將其以排名次序放置使得具有 最高排名(例如最高排名分值或頻率)的查詢位於列表的頂部。例如，關於部分查詢「hot」 的查詢完成表將包括完整查詢字符串808和818兩者。在排名基於頻率時，由於在818中的 查詢字符串的頻率(即300，000)大於在808中的查詢字符串的頻率(即100，000)，所以對 於「hotmail」的查詢字符串將出現在對於「hot dog ingredients」的查詢字符串的上方。 因此，在將預測的排序的集合返回給用戶時，首先展示具有被選擇的更高可能性的查詢。如
14上所述，其它值可以被用於對預測的完整查詢進行排名。在一些實施例中，來自用戶的簡檔 的個性化信息可以被用於對預測的完整查詢進行排名。參見圖9和10，在一些實施例中，通過將歷史查詢字符串分成諸如四(4)個字符的 預定大小C的「組塊(chunk) 」來減少查詢完成表212的數量。關於長度小於C的部分查詢 的查詢完成表212保留不變。對於長度為至少C的部分查詢，將部分查詢分成兩個部分前 綴部分和後綴部分。後綴部分的長度S等於部分查詢的長度(L)以C取模S = L modulo C。其中L為部分查詢的長度。前綴部分的長度P為部分查詢的長度減去後綴的長 度P = L-S。因此，例如，具有十(10)個字符的長度的部分查詢(例如「hot potato")在 組塊大小C為四(4)時將具有後綴長度S = 2以及前綴長度P = 8。在執行在圖7的步驟706中所示出的過程時，在圖9中概念地圖示了識別或創建 與部分查詢相對應的查詢完成表。圖9示意性地圖示了用於生成查詢完成表以及用於在處 理用戶輸入的部分查詢時進行查找兩者的過程。在部分查詢的長度小於一個「組塊」C的大 小時，例如通過使用哈希函數(或其它指紋函數)318將部分查詢映射到查詢指紋320 (圖 3A)。通過指紋到表的映射表210將指紋320映射到查詢完成表212。在部分查詢的長度為至少一個組塊C的大小時，將部分查詢902分解成前綴904 和後綴906，其長度如上所解釋的由組塊大小規制。例如通過將哈希函數318應用於前綴 904來為前綴904生成指紋908，並且然後通過指紋到表的映射表210將該指紋908映射到 「組塊化的」查詢完成表212。在一些實施例中，每一個組塊化的查詢完成表212是在更大 的查詢完成表中的條目的集合，而在其它實施例中，每一個組塊化的查詢完成表是分立的 數據結構。各個查詢完成表的每一個條目911包括為完整查詢的文本的查詢字符串，並且 還可以可選地包括用於對在查詢完成表212中的條目進行排序的分值916。組塊化的查詢 完成表的每一個條目包括對應的部分查詢的後綴914。在各個條目911中的後綴914具有 可以為從零至C-1的任何值的長度S，並且包括部分查詢的未被包括在前綴904中的零或多 個字符。在一些實施例中，在生成用於歷史查詢的查詢完成表條目911時，在每一個組塊化 的查詢完成表212中僅僅生成一個與該歷史查詢相對應的條目。特別地，該一個條目911 包含關於該歷史查詢的最長的可能的後綴，直至C-1個字符長。在其它實施例中，在每一個 組塊化的查詢完成表212中生成關於特定歷史查詢的直至C個條目，每一個條目用於每一 個不同的後綴。可選地，在各個查詢完成表212中的每一個條目包括指示與完整查詢913相關聯 的語言的語言值或指示符912。然而，在所有的查詢字符串913以其原始語言被存儲在查詢 完成表212中的實施例中可以省略語言值912。可選地，在各個查詢完成表212中的每一個條目包括用於將表條目與部分查詢前 綴的指紋進行匹配的查詢指紋918。然而，在一些實施例(例如，具有關於每一個不同的部 分查詢前綴的單獨的查詢完成表212的實施例)中，可以從查詢完成表212的條目省略指 紋 918。圖10示出了包含與歷史查詢「hot potato」相對應的條目911的一組查詢完成表。 該示例假設組塊大小C等於四。在其它實施例中，組塊大小可以是2、3、5、6、7、8或任何其 它適當的值。組塊大小C可以基於經驗信息來選擇。在圖10中示出的前三個查詢完成表
15212-1至212-3分別關於部分查詢「h」、「ho」和「hot」。下兩個查詢完成表212-4和212-5 分別與具有7和10的部分查詢長度的部分查詢「hot pot」(以「hot」為其前綴部分，並且 「pot」為其後綴部分)和「hot potato"(以「hot pota」為其前綴部分，並且「to」為其後 綴部分)相對應。以另一種方式敘述，查詢完成表212-4與以「hot」開始並且具有在4和 7之間的長度的所有部分查詢相對應；而查詢完成表212-5與以「hotpota」開始並且具有 在8和11之間的長度的所有部分查詢相對應。返回參見圖7，對於由操作710部分地形成的循環的每一次迭代，部分查詢的長度 最初增加了一個字符的步長，直至達到C-1的長度，並且然後部分查詢的長度增加了 C個字 符的步長，直至達到歷史查詢的全長。結果，在c = 4時，歷史查詢「hot potato」產生在分別 與具有1、2、3、4-7以及8-10個字符的長度的部分搜索查詢相對應的五個這樣的表(212-1 至212-5)中的查詢完成表條目(在圖10中示出)。根據在條目911中的查詢字符串913的排名值(由分值916表示)對每一個組塊 化的查詢完成表的條目911進行排序。對於具有小於C個字符的部分查詢，在查詢完成表 212中的查詢的數量是第一值(例如，10,20或在4和20之間的任何適當的值)，其可以表 示作為預測返回的查詢的數量。在一些實施例中，在每一個組塊化的查詢完成表910中的 條目911的最大數量(例如在1000和10，000之間的數量)顯著地大於第一值。每一個組 塊化的查詢完成表212可以替代數十或數百個普通的查詢完成表。因此，每一個組塊化的 查詢完成表212的大小被設置，以便包含與具有與組塊化的查詢完成表相對應的前綴部分 的所有或幾乎所有的核准的歷史查詢相對應的多(P)個條目，而不會達到在生成關於用戶 指定的部分查詢的預測的完整查詢的列表時產生過度時延的那樣的長度。在從歷史查詢的集合生成了查詢完成表212和指紋到表的映射表210之後，這些 相同的數據結構(或其副本)被用於識別與用戶輸入的部分查詢相對應的查詢的預測的集 合。如在圖9中所示，如由部分查詢的長度所確定的，首先通過將哈希函數(或其它指紋函 數)318應用於整個部分查詢902或部分查詢的前綴部分904，將用戶輸入的部分查詢映射 到查詢指紋320。然後通過在指紋到表的映射表210中執行對查詢指紋的查找，將查詢指紋 320映射到查詢完成表212。最後，從所識別的查詢完成表提取直至N個預測的查詢的排序 的集合。在部分查詢的長度小於組塊大小時，預測的查詢的排序的集合是在所識別的查詢 完成表中的前N個查詢。在部分查詢的長度等於或長於組塊大小時，在所識別的查詢完成 表中搜索與部分查詢的後綴相匹配的前N個項。由於在查詢完成表212中的條目以降低的 排名來排序，所以搜索匹配的條目的過程從頂部開始並且繼續直到獲取了待返回的期望數 量(N)(例如10)的預測，或者直到到達了查詢完成表212的末尾。在部分查詢的後綴906 與在條目911中的後綴914的對應部分相同時，存在「匹配」。例如，參見圖10，一個字母後 綴
分別與具有後綴和的條目911-3和911-4相匹配。具有長度零的空後 綴(也被稱為空字符串)與在查詢完成表中的所有條目相匹配，並且因此在部分查詢的後 綴部分為空字符串時，將在表中的前N個項作為預測的查詢返回。參見圖11，實現上述方法的客戶端系統102的實施例包括一個或多個處理單元 (CPU) 1102、一個或多個網絡或其它通信接口 1104、存儲器1106以及用於互連這些組件的 一個或多個通信總線1108。在一些實施例中，在客戶端系統102中包括更少和/或額外的 組件、模塊或功能。通信總線1108可以包括互連並控制系統組件間的通信的電路(有時被稱為晶片集)。客戶端102可以可選地包括用戶接口 1110。在一些實施例中，用戶接口 1110包括顯示設備1112和/或鍵盤1114，而用戶接口設備的其它配置也可以被使用。存 儲器1106可以包括高速隨機存取存儲器並且還可以包括非易失性存儲器，諸如一個或多 個磁或光存儲盤、快閃記憶體設備或其它非易失性固態存儲設備。高速隨機存取存儲器可以包括 諸如DRAM、SRAM、DDR RAM或其它隨機存取固態存儲設備的存儲設備。存儲器1106可以可 選地包括位於遠離CPU 1102的位置的海量存儲器。存儲器1106或替選地在存儲器1106 內的非易失性存儲設備包括計算機可讀存儲介質。存儲器1106存儲以下要素或這些要素 的子集，並且還可以包括額外的要素·作業系統1116，其包括用於處理各種基本系統服務和用於執行依賴硬體的任務 的程序；·網絡通信模塊(或指令)1118，其被用於經由一個或多個通信網絡接口 1104和 諸如網際網路、其它廣域網、區域網、城域網等的一個或多個通信網絡將客戶端系統102連接 到其它計算機； 客戶端應用1120 (例如網際網路瀏覽器應用)；客戶端應用可以包括用於以下的指 令與用戶進行交互以接收搜索查詢；將搜索查詢提交給伺服器或在線服務；以及顯示或 展示搜索結果；·網頁1122，其包括待在客戶端102上顯示或展示的網頁內容1124 ；與客戶端應 用1120協同的網頁實現用於展示網頁內容1124以及用於與客戶端102的用戶進行交互的 圖形用戶界面；·數據1136，其包括預測的完整搜索查詢；以及·搜索助手104。至少，搜索助手104將部分搜索查詢信息傳送給伺服器。搜索助手還可以使包括 預測的完整查詢的預測數據能夠被顯示，以及用戶能夠選擇所顯示的預測的完整搜索查 詢。在一些實施例中，搜索助手104包括以下要素或這樣的要素的子集輸入和選擇監視模 塊(或指令)1128，其用於監視對搜索查詢的輸入以及選擇部分搜索查詢用於傳送給服務 器；部分/完整輸入傳送模塊(或指令)1130，其用於將部分搜索查詢和(可選)完整搜索 查詢傳送給伺服器；預測數據接收模塊(或指令)1132，其用於接收預測的完整查詢；以及 預測數據顯示模塊(或指令)1134，其用於顯示預測的完整查詢的至少一個子集和任何額 外的信息。對最終(即完整)查詢的傳送、接收關於完整查詢的搜索結果以及顯示這樣的 結果可以由客戶端應用/瀏覽器1120、搜索助手104或其組合來處理。搜索助手104可以 以多種方式來實現。在一些實施例中，用於輸入查詢以及用於展示對查詢的響應的網頁1122還包括 例如Macromedia Flash對象或Microsoft Silverlight對象(兩者均與各自的瀏覽器插 件共同工作)的JavaScript或其它嵌入式代碼或者指令，所述代碼或指令用於幫助將部分 搜索查詢傳送給伺服器、用於接收並顯示預測的搜索查詢以及用於對預測的搜索查詢中的 任何查詢的用戶選擇作出響應。特別地，在一些實施例中，搜索助手104例如作為可執行的 功能被嵌入在網頁1122中、使用由客戶端102可執行的JavaScript (Sun Microsystems的 商標)或其它指令來實現。替選地，搜索助手104作為客戶端應用1120的一部分或作為由 客戶端102與客戶端應用1120協同來執行的客戶端應用1120的擴展、插件或工具欄來實現。在又其它實施例中，搜索助手104作為與客戶端應用1120分離的程序來實現。在一些實施例中，用於處理查詢信息的系統包括用於執行程序的一個或多個中央 處理單元以及用於存儲數據和用於存儲待由一個或多個中央處理單元執行的程序的存儲 器。存儲器存儲根據排名函數排序的由用戶群體先前提交的完整查詢的集合，該集合與部 分搜索查詢相對應並且包括英語和朝鮮語完整搜索查詢兩者。存儲器進一步存儲接收模 塊，其用於從搜索請求者接收部分搜索查詢；預測模塊，其用於將預測的完整查詢的集合與 部分搜索查詢相關聯；以及傳送模塊，其用於將集合的至少部分傳送給搜索請求者。圖12描述了實現上述方法的伺服器系統1200的示例。伺服器系統1200與圖1 中的搜尋引擎108和圖3A中的搜尋引擎304相對應。伺服器系統1200包括一個或多個處 理單元(CPU) 1202、一個或多個網絡或其它通信接口 1204、存儲器1206以及用於互連這些 組件的一個或多個通信總線1208。通信總線1208可以包括互連並控制系統組件間的通信 的電路(有時被稱為晶片集)。應當理解，在一些其它實施例中，伺服器系統1200可以使 用多個伺服器來實現以便提高其吞吐量和可靠性。例如，查詢日誌124和126可以在與在 伺服器系統1200中的伺服器中的其它伺服器相通信並且與之協同工作的不同的伺服器上 來實現。作為另一個示例，排序集合構建器208可以在分立的伺服器或計算設備中來實現。 因此，與作為在此所描述的實施例的結構性示意相比，圖12更意在作為對可以在一組服務 器中展示的各種特徵的功能性描述。被用來實現伺服器系統1200的伺服器的實際數量以 及如何在這些伺服器之間分配特徵將因實施方式而異，並且部分地取決於系統在高峰使用 期間以及在平均使用期間必須處理的數據業務量。存儲器1206可以包括高速隨機存取存儲器並且還可以包括非易失性存儲器，諸 如一個或多個磁或光存儲盤、快閃記憶體設備或其它非易失性固態存儲設備。高速隨機存取存儲 器可以包括諸如DRAM、SRAM、DDR RAM或其它隨機存取固態存儲設備的存儲設備。存儲器 1206可以可選地包括位於遠離CPU 1202的位置的海量存儲器。存儲器1206或替選地在存 儲器1206內的非易失性存儲設備包括計算機可讀存儲介質。存儲器1206存儲以下要素或 這些要素的子集，並且還可以包括額外的要素·作業系統1216，其包括用於處理各種基本系統服務和用於執行依賴硬體的任務 的程序；·網絡通信模塊(或指令)1218，其被用於經由一個或多個通信網絡接口 1204和 諸如網際網路、其它廣域網、區域網、城域網等的一個或多個通信網絡將伺服器系統1200連 接到其它計算機； 查詢伺服器110，其用於從客戶端接收部分搜索查詢和完整搜索查詢以及遞送響 應；以及 預測伺服器112，其用於從查詢伺服器110接收部分搜索查詢以及用於產生並遞 送響應。查詢伺服器110可以包括以下要素或這些要素的子集，並且還可以包括額外的要 素·客戶端通信模塊(或指令)116，其被用於與客戶端通信查詢和響應；·部分查詢接收、處理和響應模塊(或指令)120 ；以及· 一個或多個查詢日誌124和126，其包含與由用戶群體提交的查詢有關的信息。
查詢處理模塊(或指令)114從查詢伺服器110接收完整搜索查詢以及產生並遞 送響應。在一些實施例中，查詢處理模塊(或指令)包括包含信息的資料庫，該信息包括查 詢結果和例如與查詢結果相關聯的廣告的可選地額外的信息。預測伺服器112可以包括以下要素、這些要素的子集，並且還可以包括額外的要 素·部分查詢接收模塊(或指令)1222 ；·語言確定模塊(或指令)1224 ；·語言轉換模塊(或指令)1226 ；·哈希函數(或其它指紋函數)1228 ；
·用於查詢完成表查找的模塊(或指令)1230 ；·結果排序模塊(或指令)1232 ；·結果傳送模塊(或指令)1234 ；以及·預測資料庫1220，其可以包括一個或多個查詢完成表212以及一個或多個指紋 到表的映射表210 (在上面參考圖2所描述的)。排序集合構建器208可以可選地包括一個或多個過濾器204、205和/或語言轉換 模塊(或指令)250。儘管在此關於被設計為與位於遠離搜索請求者的位置的預測資料庫一起使用的 伺服器進行了論述，應當理解在此公開的概念同樣適用於其它搜索環境。例如，在此描述 的相同技術可以應用於針對任何類型的信息庫的查詢，其中針對所述信息庫運行查詢或搜 索。因此，應當寬泛地解釋術語「伺服器」以包括所有這樣的使用。儘管在圖11和12中被圖示為不同的模塊或組件，各種模塊或組件可以位於或共 同位於伺服器或客戶端內。例如，在一些實施例中，預測伺服器112和/或預測資料庫1220 的部分駐留於客戶端系統102上或者形成搜索助手104的一部分。例如，在一些實施例中， 可以將關於最受歡迎的搜索的哈希函數1228和一個或多個查詢完成表212和一個或多個 指紋到表的映射表210定期地下載到客戶端系統102，從而為至少一些部分搜索查詢提供 完全基於客戶端的處理。在另一個實施例中，搜索助手104可以包括預測伺服器112的本地版本，其用於至 少部分地基於經由用戶的在先查詢來進行完整搜索查詢預測。替選地或另外地，本地預測 伺服器可以基於從伺服器或遠程預測伺服器下載的數據來生成預測。此外，搜索助手104 可以將本地生成和遠程生成的預測集合合併來向用戶展示。可以以多種方式中的任何方式 來合併結果，例如通過交錯兩個集合或者通過合併集合同時偏向用戶先前提交的查詢使得 這些查詢易於接近預測的查詢的組合列表的頂部被放置或插入。在一些實施例中，搜索助 手104將認為對用戶重要的查詢插入預測的集合中。例如，可以將用戶經常提交但並未包 括在從伺服器獲取的集合中的查詢插入預測中。在諸如圖3A、3B、5、7和9中的流程圖中示出的操作和在本文檔中被描述為由客戶 端系統、伺服器、搜尋引擎等執行的其它操作與存儲在各個客戶端系統、伺服器或其它計算 機系統的計算機可讀存儲介質中的指令相對應。在圖11(存儲器1106)和圖12(存儲器 1206)中示出了這樣的計算機可讀存儲介質的示例。在本文檔中描述的軟體模塊、程序和/ 或可執行功能中的每一個與存儲在各個計算機可讀存儲介質中的指令相對應，並且與用於執行上述功能的指令集相對應。所識別的模塊、程序和/或功能(即指令集)不必作為獨 立的軟體程序、過程或模塊來實現，並且因此這些模塊的各種子集可以在各種實施例中被 組合或重新布置。圖13圖示了說明性客戶端系統的用戶界面。在該示例中，瀏覽器應用的窗口 1310 包括描述對部分查詢的輸入的文本輸入框1320。響應於檢測到部分查詢並且從預測 伺服器或搜尋引擎接收預測的完整查詢，在顯示區域1330中顯示預測的完整查詢的至少 一個子集以可能由客戶端系統的用戶選擇。如所述，在從文本輸入框1320伸出的下拉框 (對應於顯示區域1330)中展示預測的完整查詢。注意到，對部分查詢的輸入生成了 英語結果(預測的完整查詢)，即和〈ahead〉，以及朝鮮語結果。這是由於如上所述 該朝鮮語結果與羅馬化表示形式相對應。因此，如果就用戶而言部分查詢由於 輸入法錯誤(例如，使用英語字符輸入而不是朝鮮語或謗文文本輸入)而被錯誤地輸入，並 且預測結果包括用戶感興趣的朝鮮語查詢，則用戶可以通過選擇期望的朝鮮語查詢來避免 對部分查詢的重新輸入。儘管各個附圖中的某些附圖以特定順序圖示了多個邏輯階段，但是不依賴順序的 階段可以被重新排序以及其它階段可以被組合或分解。雖然特定提及了一些重新排序或 其它聚組，但是其它重新排序或聚組對本領域技術人員將是顯而易見的並且因此並未展示 替選方案的窮盡列表。此外，應當認識到，階段可以在硬體、固件、軟體或其任何組合中來實 現。為了解釋的目的，關於特定實施例描述了在前的描述。然而，在上面的說明性論述 並不意在窮舉或將本發明限制在所公開的精確形式。鑑於上述教導許多修改和變化是可能 的。選擇並描述了實施例以便最佳地解釋本發明的原理以及其實際應用，從而使本領域技 術人員能夠以適合於預期的特定用途的各種修改來最佳地利用本發明和各種實施例。
權利要求
一種用於處理查詢信息的方法，包括在伺服器處，從搜索請求者接收部分搜索查詢，所述搜索請求者位於遠離所述伺服器的位置；從多個先前提交的完整查詢獲取與所述部分搜索查詢相對應的預測的完整查詢的集合，所述先前提交的完整查詢由用戶群體提交；所述預測的完整查詢的集合包括第一語言和第二語言完整搜索查詢兩者；根據排名標準對所述預測的完整查詢的集合進行排序；以及將所排序的集合的至少一個子集遞送給所述搜索請求者。
2.如權利要求1所述的方法，其中所述第一語言是朝鮮語以及所述第二語言是英語。
3.如權利要求1所述的方法，其中，在所述部分搜索查詢包括部分輸入的第一語言搜 索查詢時，所述方法包括生成所述部分搜索查詢的羅馬化表示形式。
4.如權利要求1所述的方法，其中，在所接收的部分搜索查詢包括一個或多個第一語 言字符時，獲取預測的完整查詢的集合包括將所述部分搜索查詢轉換為所述部分搜索查詢的以所述第二語言的字符的表示形式；將哈希函數應用於所述部分搜索查詢的所述表示形式以產生哈希值；以及 使用所述哈希值來執行查找操作以獲取所述預測的完整查詢。
5.如權利要求1所述的方法，其中，在所接收的部分搜索查詢包括一個或多個完整的 第一語言字符和一個不完整的第一語言字符時，獲取預測的完整查詢的集合包括將所述部分搜索查詢轉換為所述部分搜索查詢的羅馬化表示形式；將哈希函數應用於所述部分搜索查詢的所述羅馬化表示形式以產生哈希值；以及使用所述哈希值來執行查找操作以獲取所述預測的完整查詢。
6.如權利要求1所述的方法，其中所接收的部分搜索查詢包括一個或多個完整的第一 語言字符和一個不完整的第一語言字符。
7.如權利要求1所述的方法，包括在所述遞送之前，對所述預測的完整查詢的集合進 行過濾，以如果存在與在一個或多個預定詞語集合中的一個或多個詞語相匹配的查詢，則 移除所述查詢。
8.一種用於處理查詢信息的方法，包括 在客戶端處，從搜索請求者接收部分搜索查詢；從多個先前提交的完整查詢獲取與所述部分搜索查詢相對應的預測的完整查詢的集 合，所述先前提交的完整查詢由用戶群體提交，其中所述預測的完整查詢的集合包括第一 語言和第二語言完整搜索查詢兩者，並且根據排名標準被排序；以及 向所述搜索請求者顯示所排序的集合的至少一個子集。
9.如權利要求8所述的方法，其中所述第一語言是朝鮮語以及所述第二語言是英語。
10.如權利要求8所述的方法，其中，在所述部分搜索查詢包括部分輸入的第一語言搜 索查詢時，所述方法包括生成所述部分第一語言搜索查詢的羅馬化表示形式。
11.如權利要求8所述的方法，其中所述獲取包括在所接收的部分搜索查詢包括一個 或多個第一語言字符時將所述部分搜索查詢轉換為所述部分搜索查詢的以所述第二語言的字符的表示形式；將哈希函數應用於所述部分搜索查詢的所述表示形式以產生哈希值；以及 使用所述哈希值來執行查找操作以獲取所述預測的完整查詢。
12.如權利要求8所述的方法，其中所述獲取包括在所接收的部分搜索查詢包括一個或多個完整的第一語言字符和一個不完整的第一 語言字符時，將所述部分搜索查詢轉換為所述部分搜索查詢的羅馬化表示形式，將哈希函 數應用於所述部分搜索查詢的所述羅馬化表示形式以產生哈希值，以及使用所述哈希值來 執行查找操作以獲取所述預測的完整查詢。
13.如權利要求8所述的方法，其中所接收的部分搜索查詢包括一個或多個完整的第 一語言字符和一個不完整的第一語言字符。
14.一種用於處理查詢信息的系統，包括一個或多個中央處理單元，所述一個或多個中央處理單元用於執行程序；以及 存儲器，所述存儲器用來存儲數據以及存儲由所述一個或多個中央處理單元執行的一 個或多個程序，所述一個或多個程序包括指令，所述指令用於從搜索請求者接收部分搜索查詢，所述搜索請求者位於遠離伺服器的位置； 從多個先前提交的完整查詢獲取與所述部分搜索查詢相對應的預測的完整查詢的集 合，所述先前提交的完整查詢由用戶群體提交；所述預測的完整查詢的集合包括第一語言 和與所述第一語言不同的第二語言兩者的完整搜索查詢；根據排名標準對所述預測的完整查詢的集合進行排序；以及 將所排序的集合的至少一個子集遞送給所述搜索請求者。
15.如權利要求14所述的系統，其中所述一個或多個程序包括用於生成包括部分輸入 的第一語言搜索查詢的各個部分搜索查詢的羅馬化表示形式的指令。
16.如權利要求14所述的系統，其中所述用於獲取預測的完整查詢的集合的指令包括 用於以下的指令將包括一個或多個第一語言字符的各個部分搜索查詢轉換為所述各個部分搜索查詢 的以所述第二語言的字符的表示形式；將哈希函數應用於所述部分搜索查詢的所述表示形式以產生哈希值；以及 使用所述哈希值來執行查找操作以獲取所述預測的完整查詢。
17.如權利要求14所述的系統，其中所述用於獲取預測的完整查詢的集合的指令包括 用於以下的指令將包括一個或多個完整的第一語言字符和一個不完整的第一語言字符的各個部分搜 索查詢轉換為所述各個部分搜索查詢的羅馬化表示形式；將哈希函數應用於所述各個部分搜索查詢的所述羅馬化表示形式以產生哈希值；以及 使用所述哈希值來執行查找操作以獲取所述預測的完整查詢。
18.如權利要求14所述的系統，其中所接收的部分搜索查詢包括一個或多個完整的第 一語言字符和一個不完整的第一語言字符。
19.如權利要求14所述的系統，其中所述用於獲取預測的完整查詢的集合的指令包括 用於以下的指令對所述預測的完整查詢的集合進行過濾，以如果存在與在一個或多個預定詞語集合中的一個或多個詞語相匹配的查詢，則移除所述查詢。
20.如權利要求14所述的系統，其中所述用於獲取預測的完整查詢的集合的指令包括 用於以下的指令將包括一個或多個朝鮮語字符的各個部分搜索查詢轉換為所述各個部分搜索查詢的 羅馬化表示形式；將哈希函數應用於所述部分搜索查詢的所述羅馬化表示形式以產生哈希值；以及 使用所述哈希值來執行查找操作以獲取所述預測的完整查詢。
21.如權利要求14所述的系統，其中所述用於獲取預測的完整查詢的集合的指令包括 用於以下的指令將包括一個或多個完整的朝鮮語字符和一個不完整的朝鮮語字符的各個部分搜索查 詢轉換為所述各個部分搜索查詢的羅馬化表示形式；將哈希函數應用於所述各個部分搜索查詢的所述羅馬化表示形式以產生哈希值；以及 使用所述哈希值來執行查找操作以獲取所述預測的完整查詢。
22.如權利要求14所述的系統，其中所接收的部分搜索查詢包括一個或多個完整的朝 鮮語字符和一個不完整的朝鮮語字符。
23.一種用於構建用於處理查詢信息的數據結構的方法，包括獲取先前提交的完整第一語言查詢的集合，所述完整第一語言查詢由用戶群體先前提交。獲取先前提交的完整第二語言查詢的集合，所述完整第二語言查詢由用戶群體先前提交。將所述完整第一語言查詢的集合轉換為以羅馬化表示形式的完整第二語言查詢的集 合；以及將所述完整第一語言查詢的集合和羅馬化的完整第二語言查詢的集合存儲在一個或 多個查詢完成數據表中；其中所述一個或多個查詢完成數據表形成能夠被用來預測與部分第一語言查詢或部 分第二語言查詢相對應的完整第一語言查詢和完整第二語言查詢兩者的一個或多個數據 結構。
24.如權利要求23所述的方法，包括對所述先前提交的完整第一語言查詢的集合和所 述先前提交的第二語言查詢的集合進行過濾以排除與預定詞語的一個或多個集合相匹配 的查詢。
25.如權利要求23所述的方法，其中所述第一語言是朝鮮語以及所述第二語言是英語。
26.一種客戶端系統，包括一個或多個中央處理單元，所述一個或多個中央處理單元用於執行程序；以及 存儲器，所述存儲器用來存儲數據以及存儲由所述一個或多個中央處理單元執行的一 個或多個程序，所述一個或多個程序包括指令，所述指令用於 從搜索請求者接收部分搜索查詢；從多個先前提交的完整查詢獲取與所述部分搜索查詢相對應的預測的完整查詢的集 合，所述先前提交的完整查詢由用戶群體提交，其中所述預測的完整查詢的集合包括第一語言和第二語言完整搜索查詢兩者，並且根據排名標準被排序；以及 向所述搜索請求者顯示所排序的集合的至少一個子集。
27.如權利要求26所述的客戶端系統，其中所述第一語言是朝鮮語以及所述第二語言是英語。
28.一種存儲用於由各個伺服器系統的一個或多個處理器執行的一個或多個程序的計 算機可讀存儲介質，所述一個或多個程序包括用於以下的指令從搜索請求者接收部分搜索查詢，所述搜索請求者位於遠離伺服器的位置； 從多個先前提交的完整查詢獲取與所述部分搜索查詢相對應的預測的完整查詢的集 合，所述先前提交的完整查詢由用戶群體提交；所述預測的完整查詢的集合包括第一語言 和第二語言完整搜索查詢兩者；根據排名標準對所述預測的完整查詢的集合進行排序；以及 將所排序的集合的至少一個子集遞送給所述搜索請求者。
29.如權利要求28所述的計算機可讀存儲介質，其中所述第一語言是朝鮮語以及所述『是英語。
30.一種存儲用於由各個客戶端設備或系統的一個或多個處理器執行的一個或多個程 序的計算機可讀存儲介質，所述一個或多個程序包括用於以下的指令從搜索請求者接收部分搜索查詢；從多個先前提交的完整查詢獲取與所述部分搜索查詢相對應的預測的完整查詢的集 合，所述先前提交的完整查詢由用戶群體提交，其中所述預測的完整查詢的集合包括第一 語言和第二語言完整搜索查詢兩者，並且根據排名標準被排序；以及 向所述搜索請求者顯示所排序的集合的至少一個子集。
31.如權利要求30所述的計算機可讀存儲介質，其中所述第一語言是朝鮮語以及所述『是英語。
全文摘要
用於處理查詢信息的方法包括從搜索請求者接收部分搜索查詢，以及從多個先前提交的完整查詢獲取與部分搜索查詢相對應的預測的完整查詢的集合，先前提交的完整查詢由用戶群體提交。預測的完整查詢的集合包括英語和朝鮮語完整搜索查詢兩者。根據排名標準對預測的完整查詢的集合進行排序，並且將排序的集合的至少一個子集發送給搜索請求者。部分搜索查詢可以是部分朝鮮語搜索查詢的羅馬化表示形式。
文檔編號G06F17/30GK101816000SQ200880110208
公開日2010年8月25日 申請日期2008年8月8日 優先權日2007年8月9日
發明者金度享 申請人:谷歌公司