用於為具有多個書寫系統的語言識別相關查詢的系統和方法

2023-07-20 17:29:11

專利名稱：用於為具有多個書寫系統的語言識別相關查詢的系統和方法
技術領域：
本發明一般地提供了用於識別與根據具有多個書寫系統(writing system)的語言(language)書寫的給定搜索査詢(search query)相關的 一個或多個查詢的方法和系統。更具體而言，本發明提供了用於接收根據 具有多個書寫系統的語言的一個或多個書寫系統的組合來書寫的搜索查詢 並且從查詢的候選集合(candidate set of queries)中識別一個或多個相關 查詢的方法和系統。
背景技術：
由於網際網路的出現和全球資訊網("web")上用戶可獲得的眾多網頁、 媒體內容、廣告等等，向用戶提供流線型的方法以從web獲得有關信息己
經成為一種需求。搜索系統和過程已經被開發出來滿足用戶獲得這種信息
的需求。這種技術的示例可通過Yahoo!、 Google和其他搜索提供商網站來 得到。
目前，用戶可以使用能夠接入廣域網(例如網際網路)的客戶端設備 (例如個人計算機(PC) 、 PDA、智慧型電話等等)來搜索和檢索出內容。 一般來說，用戶經由客戶端設備輸入查詢，並且搜索進程返回與查詢相關 的一個或多個內容項，例如連結、文檔、網頁、廣告，等等。響應於給定 查詢而返回的內容項可能與用戶實際在尋找的主題或題目緊密相關，也可 能完全無關。給定査詢的成功度可以基於所檢索出的內容項與給定查詢如 何緊密相關來衡量，它很大程度上可能取決於對搜索査詢的適當解釋。
查詢是由一個或多個單詞和短語構成的。但是，人類用戶輸入的查詢 經常無法恰當地描述給定用戶可能在尋找的內容。另外，用戶可能只擁有 關於其可能在尋找的內容的概括的或含糊的想法。例如，用戶可能希望利 用Yahoo!搜尋引擎對在電視上作廣告的產品進行搜索。用戶可能不知道產 品的名稱、製造商等等，並且可能只能概括性地描述產品。因此，用戶所 制定的査詢可能太寬泛了，從而導致所檢索出的內容項與用戶尋找的內容 完全無關。類似地，用戶所選擇的査詢詞語(query term)可能無法恰當地 描述產品，從而導致只檢索出少量內容項，或者甚至不檢索出任何內容 項。
已知當前的用於生成可能與給定查詢相關的査詢的候選集合的技術。 例如，用戶可輸入查詢"Apple MP3 player"，並且被呈現以一個或多個 相關查詢，例如"IPOD " 、 "Itunes "，等等。但是，搜索提供商面臨 著從查詢的候選集合中識別在含義上與給定查詢最有關或緊密相關的一個 或多個査詢的挑戰。另外，諸如日語之類的某些語言具有多個書寫系統， 這進一步增大了從查詢的候選集合中識別在含義上與給定查詢最有關或相 似的查詢的複雜度。例如，提交給搜尋引擎的單個日語查詢可能是根據諸 如漢字(Kanji)、片假名(Katakana)、平假名(hiragana) 、 JASCII、 ASCII等等之類的一個或多個日語書寫系統的不同組合來書寫的。根據日 語的漢字書寫系統書寫的査詢看起來可能完全不同於根據日語的片假名和
平假名書寫系統書寫的查詢，但是兩個查詢可能具有非常相似或相同的含 義。
此外，諸如Yahoo!、 MSN或Google之類的搜索提供商可利用競價市 場(bidding market)，通過該市場，廣告主(advertiser)可以為詞語出價 (bid)，以便使得一個或多個廣告響應於查詢而被顯示。例如， 一個或多 個廣告主可能希望顯示膝上型計算機的一個或多個廣告，並且相應地可為 "notebook computer (筆記本計算機)"出價。但是，詞語"notebook computer"可能是根據具有多個書寫系統的語言(例如日語)的一個或多 個書寫系統來書寫的。例如，詞語"notebook computer"可能是根據曰語 平假名書寫系統、日語片假名書寫系統等等來書寫的。
用戶可以向給定的搜索提供商(例如Yahoo!)提交包括根據日語片假 名書寫系統書寫的詞語"notebook computer"的查詢。具有相關聯的對片 假名詞語"notebook computer"的出價一個或多個廣告可被檢索出並顯示 給用戶。在競價市場中，與為片假名詞語"notebook computer"提供最大 出價的廣告主相關聯的廣告可以被顯示在網頁的最突出位置，例如，在被 排名的廣告列表中排名第一、顯示在給定的搜索結果頁面的頂部，等等。
如果用戶選擇了一個或多個所顯示的廣告，則搜索提供商可以例如通 過基於廣告主的出價向與所選擇的廣告相關聯的廣告主收取某一數額的貨 幣，來使用戶的選擇貨幣化。但是，僅僅檢索出和顯示具有相關聯的對一 個或多個詞語的出價的廣告，可能導致給定搜索提供商的收入大受損失。 例如，如果用戶輸入由未被一個或多個廣告主出價的詞語組成的查詢，則 搜索提供商可能無法向用戶返回任何廣告，從而導致搜索提供商的收入損 失，因為用戶將不能選擇任何結果。參考上述示例，如果用戶輸入的查詢 不包括片假名詞語"notebook computer"，而是包括平假名詞語"laptop computer (膝上型計算機)"，則搜索提供商可能不會顯示有適當針對性 的廣告，儘管片假名査詢"laptop computer"和平假名査詢"notebook computer"的含義是相似的。
雖然存在用於從査詢的候選集合中識別在含義上與給定查詢相同或相 似的一個或多個查詢的技術，但是現有技術限於根據單個書寫系統書寫的
語言。當前的技術因而無法支持對在含義上與根據具有多個書寫系統的語 言的一個或多個書寫系統書寫的原始查詢最有關或緊密相關的查詢的識 別。為了克服與現有技術相關聯的缺點，本發明提供了系統和方法，用於 從相關查詢的候選集合中識別與根據具有多個書寫系統的語言的一個或多 個書寫系統書寫的給定搜索查詢在含義上最相似的一個或多個查詢。

發明內容
本發明涉及用於識別與給定查詢相關的一個或多個査詢的方法和系 統。本發明的方法包括接收根據具有多個書寫系統的語言的一個或多個書 寫系統書寫的查詢。根據本發明的一個實施例，所接收的查詢包括根據一 個或多個日語書寫系統的組合來書寫的査詢，所述一個或多個日語書寫系
統包括日語平假名、片假名、假名、羅馬字、JAScn和漢字書寫系統。
識別與接收的查詢相關聯的、根據該具有多個書寫系統的語言的一個 或多個書寫系統書寫的查詢的候選集合。根據本發明的一個實施例，查詢
的候選集合包括如一個或多個査詢日誌(query log)中所指示的與接收的 査詢相關的一個或多個査詢。
該方法還包括為候選集合中的一個或多個查詢計算指示出該一個或多 個査詢與接收的查詢的相似性的得分。為候選集合中的一個或多個查詢計 算的得分指示出來自候選的給定査詢與接收的查詢在含義上的相似性。根 據本發明的一個實施例，計算得分包括在將每個査詢中的一個或多個字符 轉換成羅馬字符之後計算接收的查詢和從候選集合中選擇的查詢之間的字 符編輯距離(character edit distance)。根據本發明的另一個實施例，計算 得分包括在將每個査詢中的一個或多個字符轉換成羅馬字符並且從每個査 詢中去除空格字符之後計算接收的査詢和從候選集合中選擇的査詢之間的 字符編輯距離。根據本發明的另一個實施例，計算得分包括將接收的査詢 和從候選集合中選擇的查詢的字符轉換成羅馬字符，並且計算一 ("1")與下述商(quotient)之間的差接收的查詢和選擇的查詢中的 獨特空格分隔共現單詞(unique space-separated co-occurring words)的數目 與兩個査詢中的獨特空格分隔單詞的總數的商。
根據本發明的另一個實施例，計算得分包括識別某一數字是否是接收 的査詢和從候選集合中選擇的查詢所特有的。根據另一個實施例，計算得 分包括計算值一 ("1")與下述商之間的差接收的查詢和從候選集合 中選擇的查詢中的共現日語漢字字符的數目與接收的査詢和從候選集合中 選擇的査詢中的獨特日語漢字字符的總數的商。根據本發明的另一個實施 例，計算得分包括將接收的查詢和從候選集合中選擇的査詢的一個或多個 字符轉換成羅馬字符，並且計算這些査詢共有的羅馬字符的數目。根據本 發明的另一個實施例，計算得分包括識別接收的査詢或者從候選集合中選 擇的査詢是否包含非羅馬字符。根據本發明的另一個實施例，計算得分包 括在將每個查詢的日語漢字字符轉換成日語假名字符並且從每個查詢中 去除所有非日語字符之後，計算接收的査詢和從候選集合中選擇的查詢之 間的字符編輯距離。根據本發明的另一個實施例，計算得分包括計算在一 個或多個査詢日誌中從候選集合中選擇的查詢跟隨接收的查詢的頻率與在 一個或多個查詢日誌中接收的査詢的頻率的商。
該方法還包括從候選集合的査詢中選擇一個或多個査詢以便分發。根 據本發明的一個實施例，從候選集合中選擇以便分發的一個或多個查詢包 括具有超過給定閾值的得分的一個或多個查詢。被選擇以便分發的一個或 多個查詢可被分發。根據本發明的一個實施例，被選擇以便分發的查詢被 嵌入在一個或多個網頁中。
本發明還涉及一種用於識別與給定查詢相關的一個或多個査詢的系 統。本發明的系統包括搜尋引擎，該搜尋引擎可操作以用於接收根據具有 多個書寫系統的語言的一個或多個書寫系統書寫的査詢。根據本發明的一 個實施例，搜尋引擎可操作以用於接收根據一個或多個日語書寫系統書寫 的查詢。搜尋引擎還可操作以用於識別與接收的查詢相關聯的、根據該具 有多個書寫系統的語言的一個或多個書寫系統書寫的一個或多個査詢的候 選集合。根據本發明的一個實施例，搜尋引擎可操作以用於識別由如一個 或多個査詢日誌中所指示的與接收的查詢相關的一個或多個查詢組成的候 選集合。
轉換組件可操作以用於將接收的查詢和候選集合中的一個或多個査詢
轉換成一個或多個書面格式。根據本發明的一個實施例，轉換組件可操作 以用於將查詢轉換成根據一個或多個書寫系統的一個或多個書面格式。
相似性組件可操作以用於為候選集合中的一個或多個査詢計算指示出 該一個或多個查詢與接收的查詢的相似性的得分。相似性組件可操作以用 於計算指示出從候選集合中選擇的査詢與接收的查詢在含義上的相似性的 得分。根據本發明的一個實施例，相似性組件可操作以用於計算接收的查 詢和從候選集合中選擇的査詢之間的字符編輯距離。根據本發明的另一個 實施例，相似性組件可操作以用於計算一 ("1")與下述商之間的差 接收的查詢和從候選集合中選擇的査詢中的獨特空格分隔共現單詞的數目 與兩個查詢中的獨特空格分隔單詞的總數的商。根據本發明的另一個實施 例，相似性組件可操作以用於識別某一數字是否是接收的査詢或從候選集 合中選擇的査詢所特有的。
根據另一個實施例，相似性組件可操作以用於計算一 ("1")與下 述商之間的差接收的査詢和從候選集合中選擇的查詢中的共現日語漢字 字符的數目與兩個査詢中的獨特日語漢字字符的總數的商。根據本發明的 另一個實施例，相似性組件可操作以用於計算接收的查詢和從候選集合中 選擇的査詢共有的字符的數目。根據本發明的另一個實施例，相似性組件 可操作以用於識別接收的查詢或者從候選集合中選擇的査詢是否包含給定 書寫系統的一個或多個字符。根據本發明的另一個實施例，相似性組件可 操作以用於計算在一個或多個査詢日誌中從候選集合中選擇的査詢跟隨接 收的查詢的頻率與在這些査詢日誌中接收的查詢的頻率的商。


本發明在想要為示例性而非限制性的附圖中示出，在附圖中類似的標 號意圖指代類似或相應的部件，其中
圖1是給出根據本發明一個實施例用於識別根據具有多個書寫系統的 語言的一個或多個書寫系統的組合書寫的一個或多個相關查詢的系統的框 圖2是示出根據本發明一個實施例用於選擇根據具有多個書寫系統的
語言的一個或多個書寫系統的組合書寫的一個或多個相關查詢的方法的一
個實施例的流程圖3是示出根據本發明一個實施例用於計算根據具有多個書寫系統的 語言的一個或多個書寫系統書寫的兩個查詢之間的字符編輯距離的方法的 一個實施例的流程圖4是示出根據本發明一個實施例用於計算根據具有多個書寫系統的 語言的一個或多個書寫系統書寫的兩個査詢之間的字符編輯距離的另一個 實施例的流程圖5是示出根據本發明一個實施例用於計算根據具有多個書寫系統的 語言的一個或多個書寫系統書寫的兩個査詢之間的單詞編輯距離的方法的 一個實施例的流程圖6是示出根據本發明一個實施例用於識別在根據具有多個書寫系統 的語言的一個或多個書寫系統書寫的兩個查詢中出現的數字的差別的方法 的一個實施例的流程圖7是示出根據本發明一個實施例用於在只考慮一個書寫系統的字符 的情況下計算根據具有多個書寫系統的語言的一個或多個書寫系統書寫的 兩個查詢之間的字符編輯距離的方法的一個實施例的流程圖8是示出根據本發明一個實施例用於識別在根據具有多個書寫系統 的語言的一個或多個書寫系統書寫的兩個査詢的前綴中重疊的字符的數目 的方法的一個實施例的流程圖9是示出根據本發明一個實施例用於識別根據具有多個書寫系統的 語言的一個或多個書寫系統書寫的兩個査詢是否具有非羅馬字符的方法的 一個實施例的流程圖10是示出根據本發明一個實施例用於在根據具有多個書寫系統的 語言的一個或多個書寫系統書寫的兩個查詢都被轉換到給定書寫系統之後 計算這兩個査詢之間的字符編輯距離的方法的一個實施例的流程圖；以及
圖11是示出根據本發明一個實施例用於計算根據具有多個書寫系統 的語言的一個或多個書寫系統書寫的兩個査詢的查詢和短語替換概率的方 法的一個實施例的流程圖。
具體實施例方式
在以下描述中，參考了形成本說明書一部分的附圖，在附圖中以圖示 方式示出了可用來實現本發明的具體實施例。應當理解，在不脫離本發明 的範圍的情況下，可以利用其他實施例，並且可以進行結構上的改變。
圖1給出了繪出用於識別與根據具有多個書寫系統的語言的一個或多 個書寫系統書寫的給定查詢相關的一個或多個查詢的系統的一個實施例。
根據圖1的實施例，客戶端設備124a、 124b和124c可通信地耦合到網絡 122，該網絡122可包括與一個或多個區域網和/或廣域網(例如網際網路) 的連接。根據本發明的一個實施例，客戶端設備124a、 124b和124c是通 用個人計算機，其包括處理器、暫時性和永久性存儲設備、輸入/輸出子系 統和用於在構成通用個人計算機的組件之間提供通信路徑的總線。例如， 具512 MB的RAM、 40GB的硬碟驅動器存儲空間和到網絡的乙太網接口 的3.5 GHz Pentium 4個人計算機。其他客戶端設備被認為落在本發明的範 圍內，包括但不限於手持式設備、機頂終端、移動手持機、PDA，等等。
可通信地耦合到網絡122的客戶端設備124a、 124b和124c的用戶可 以向搜索提供商100提交包括一個或多個詞語的搜索査詢。用戶經由網絡 122向搜索提供商100提交的搜索查詢可包括根據具有多個書寫系統的語 言的一個或多個書寫系統書寫的一個或多個字符、詞語或短語。例如，客 戶端設備124a、 124b和124c的用戶可以制定包括日語漢字字符、日語片 假名字符和JASCII字符的查詢。類似地，客戶端設備124a、 124b和124c 的用戶可以制定包括日語羅馬字(Romaji)字符、日語平假名字符和數字 的查詢。例如，用戶可以提交根據日語片假名、平假名、漢字和ASCII書 寫系統書寫的以下查詢1 y 、7卜，O涙沢尻工y力。
客戶端設備124a、 124b和124c的用戶提交的可能包括根據具有多個 書寫系統的語言的一個或多個書寫系統書寫的字符和詞語的一個或多個搜 索查詢可以被搜索提供商100處的搜尋引擎107用來識別相關查詢的候選 集合。構成相關查詢的候選集合的一個或多個査詢可分別被維護在一個或 多個本地或遠程數據存儲102和108中，數據存儲102和108可操作以用
於維護可能與給定查詢相關的一個或多個查詢。根據本發明的一個實施
例，數據存儲102和108可操作以用於維護具有標識與一個或多個查詢或 詞語相關的一組査詢的條目的索引。數據存儲102和108所維護的索引可 以被補充有指示出相關的詞語或査詢的人類編輯信息。例如，數據存儲 102和108中的索引條目可包括根據日語片假名、平假名、漢字和ASCII
書寫系統書寫的查詢"i y y卜々o涙沢尻工y力"，以及根據一個或
多個日語書寫系統書寫的一個或多個相關査詢或詞語。
數據存儲102和108可實現為資料庫或能夠支持對一組或多組查詢的 檢索和存儲的任何其他類型的存儲結構，例如資料庫、CD-ROM、磁帶、 數字存儲庫、等等。數據存儲102和108中維護的查詢可包括根據具有多 個書寫系統的給定語言的一個或多個書寫系統書寫的査詢。例如，數據存 儲102和108中維護的查詢可包括根據日語漢字、平假名、片假名、 JASCII和羅馬字書寫系統書寫的查詢。
根據本發明的另一實施例，由搜尋引擎107識別的相關查詢的候選集 合可包括在統計上顯著地共現於一個或多個査詢日誌中的一個或多個有序 查詢對(sequential pair of queries)。搜尋引擎107可利用查詢日誌來識別 包括與從客戶端設備124a、 124b和124c接收的查詢相關的一個或多個查 詢的候選集合。用戶向搜索提供商100提交的可能根據具有多個書寫系統 的語言的一個或多個書寫系統書寫的多個查詢可被維護在查詢日誌組件 106中。査詢日誌組件106可實現為資料庫或能夠支持對根據一個或多個 書寫系統書寫的一個或多個查詢的存儲的類似存儲結構。
查詢日誌組件106可維護這樣的信息該信息標識出查詢被提供給搜 索提供商100的頻率。類似地，査詢日誌組件106可維護這樣的信息該 信息標識出給定査詢跟隨相關查詢的頻率。例如，在給定會話期間，進行 搜索的用戶可提交包括根據具有多個書寫系統的語言(例如日語)的一個 或多個書寫系統書寫的詞語"intellectual property (智慧財產權)"的查詢。
在同一會話期間，用戶可提交包括根據一個或多個日語書寫系統書寫的詞 語"patent attorney (專利代理人)"的查詢。查詢日誌組件106可維護標 識出在給定用戶的會話期間査詢"patent attorney"跟隨查詢"intellectualproperty"的頻率。
搜尋引擎107可利用由查詢日誌組件106維護的查詢日誌來識別候選 集合，該候選集合包括與從給定的客戶端設備124a、 124b和124c接收的 査詢在統計上顯著地相關的一個或多個查詢。如查詢日誌組件106中維護 的查詢日誌所指示的，被識別為與給定査詢相關的一個或多個査詢可用於 補充或生成相關查詢的候選集合。相關查詢的候選集合可包括根據具有多 個書寫系統的給定語言(例如日語)的一個或多個書寫系統書寫的查詢。 用於利用査詢日誌來識別與給定査詢相關的一個或多個查詢的示例性方法 在與本申請屬於同一申請人的題為"SYSTEM AND METHOD FOR DETERMINING ALTERNATE SEARCH QUERIES"的美國專利申請No. 11/200,851和題為"MODULAR OPTIMIZED DYNAMIC SETS"的美國臨 時申請No. 60/736,133中有所記載，特此通過引用將上述申請的公開內容 全部併入。
相似性組件104使用由搜尋引擎107識別出的候選集合來為相關查詢 的候選集合中的一個或多個查詢計算相似性得分(similarity score)。相似 性組件104可操作以用於從相關査詢的候選集合中選擇給定查詢Q'並為 Q'計算相似性得分，該相似性得分指示出Q'與從給定客戶端設備124a、 124b和124c接收的給定査詢Q的在含義上的相似性的強度。相似性組件 104可操作以用於根據這裡描述的方法為搜尋引擎107識別的相關查詢的 候選集合中的一個或多個查詢中的每一個計算相似性得分。
相似性組件104可利用轉換組件110來為搜尋引擎107識別的相關査 詢的候選集合中的每個査詢Q'計算相似性得分。根據本發明的一個實施 例，轉換組件110將給定查詢轉換成一個或多個書面格式(written format)。由轉換組件110生成的給定査詢Q'的一個或多個書面格式可被 遞送到相似性組件104，以幫助計算相似性得分。例如，相似性組件104 可針對從用戶接收的給定査詢Q和從相關查詢的候選集合中選擇的相關査 詢Q'執行許多比較來計算準確的相似性得分。但是，如前所述，相關査詢 的候選集合中的一個或多個查詢可能是根據具有多個書寫系統的給定語言 的一個或多個書寫系統來書寫的。類似地，從給定的客戶端設備124a、
124b和124c接收的查詢可能是根據具有多個書寫系統的給定語言的一個 或多個書寫系統書寫的。相似性組件104所執行的一個或多個比較可能要 求從用戶接收的查詢Q和從相關查詢的候選集合選擇的給定查詢Q'是根 據特定的書寫系統來表達的。例如，相似性組件104可能要求給定查詢Q 和相關查詢Q'的一個或多個JASCII字符被轉換成ASCII字符以便比較兩 個查詢。
為了比較可能根據不同的書寫系統書寫的査詢Q和查詢Q'，相似性 組件104可將給定的査詢遞送到轉換組件110。根據本發明的一個實施 例，轉換組件110可操作以用於識別與給定查詢相關聯的語言和書寫系 統，並將該查詢轉換成一個或多個替代的書面格式。由搜尋引擎107識別 的候選集合可包括根據具有多個書寫系統的給定語言的多種書寫系統書寫 的查詢，例如根據日語漢字、假名、JASCII和羅馬字書寫系統書寫的査 詢。轉換組件110可操作以用於識別出査詢是根據一個或多個日語書寫系 統書寫的並將該查詢轉換成一個或多個替代書寫系統。例如，轉換組件 110可操作以用於識別出査詢是根據日語片假名書寫系統書寫的並根據日 語羅馬字書寫系統來轉換該査詢。類似地，轉換組件110可操作以用於識 別出查詢包括一個或多個JASCII字符並將該一個或多個JASCII字符轉換 成ASCII字符，以幫助相似性組件104計算相似性得分。
根據本發明的一個實施例，由相似性組件104為相關查詢的候選集合 中的一個或多個查詢計算的相似性得分被分發組件116用於從候選集合中 選擇一個或多個査詢以便進行分發。基於相似性得分來選擇査詢使得可以 選擇與給定査詢Q在含義上最相似的查詢。例如，分發組件116可以從相 關査詢的候選集合中選擇具有超過給定閾值的相似性得分的一個或多個查 詢。類似地，分發組件可從候選集合中選擇具有最大相似性得分的W個查 詢。本領域的技術人員明白其他的用於利用相似性得分從候選集合中選擇 一個或多個査詢的技術。
分發組件116可分發從候選集合選擇的一個或多個査詢。根據本發明 的一個實施例，分發組件116經由網絡122將從候選集合選擇的査詢作為 "建議替代查詢"或"含義相似的查詢"顯示給用戶。作為前述內容的替
代或與前述內容相結合，分發組件116可操作以用於將該選擇的一個或多
個查詢遞送給搜尋引擎107，搜尋引擎107可將所選擇的查詢嵌入在搜索 結果網頁中，該搜索結果網頁可以被可通信地耦合到網絡122的客戶端設 備124a、 124b和124c的給定用戶所査看。
由相似性組件104為候選集合中的一個或多個查詢計算出的相似性得 分還可用於選擇一個或多個內容項(包括廣告)，以便響應於給定請求而 分發。根據本發明的一個實施例，廣告可被維護在上述數據存儲102和 108中，或被維護在一個或多個不同的數據存儲中(未示出)。 一個或多 個本地數據存儲102、遠程數據存儲108或不同的數據存儲可操作以用於 維護一個或多個廣告以及相關聯的對與廣告相對應的詞語的出價。例如， 給定的廣告主可能希望顯示針對筆記本計算機的給定廣告。廣告主因此可 為詞語"notebook computer"出價，並且識別出將要響應於包括詞語 "notebook computer"的査詢而顯示的廣告。當搜索提供商100接收到查 詢時，搜尋引擎107可搜索本地和遠程數據存儲102和108，或者一個或 多個不同的數據存儲，以判定是否有一個或多個廣告主為構成所接收的査 詢的一個或多個詞語提供了出價。如果識別出針對構成查詢的詞語的一個 或多個出價，那麼利用分發組件116，與對一個或多個詞語的出價相關聯 的廣告可被檢索出並在用戶的客戶端設備124a、 124b和124c上被顯示給 用戶。如果用戶選擇了所顯示的給定廣告，則與所選擇的廣告相關聯的廣 告主可以根據該廣告主的出價而被收取某一貨幣金額。
但是，廣告主可選擇為只根據具有多個書寫系統的語言的單個書寫系 統書寫的詞語出價。例如，廣告主可選擇為只根據日語平假名書寫系統書 寫的詞語出價。但是，如前所述，由客戶端設備124a、 124b和124c的用 戶提交的一個或多個搜索查詢可包括根據一個或多個書寫系統書寫的詞語 和短語。搜尋引擎107因而可利用具有超過給定閾值的相似性得分的查詢 來擴展響應於給定查詢而檢索出的廣告的範圍。根據本發明的一個實施 例，搜尋引擎107識別響應於構成具有超過給定閾值的相似性得分的一個 或多個査詢的詞語的一個或多個廣告。被識別為響應於構成具有超過給定 閾值的相似性得分的查詢的詞語的一個或多個廣告被選擇以便分發到一個
或多個客戶端設備124a、 124b和124c。
例如，客戶端設備124a、 124b和124c的用戶可制定根據日語漢字和 羅馬字書寫系統兩者書寫的日語詞語組成的搜索查詢Q。用戶可經由網絡 122將該査詢提交給搜索提供商100。搜尋引擎107可確定沒有廣告主為 用戶所利用的漢字和羅馬字詞語提供了出價。作為前述內容的替代或與前 述內容相結合，搜尋引擎107可確定顯示對應於與用戶所利用的漢字和羅 馬字詞語相關聯的出價的廣告將會產生很少的收入，或者甚至不產生收 入。但是，搜尋引擎107可利用構成從候選集合中選擇的具有超過給定閾 值的相似性得分的一個或多個査詢的詞語來識別具有相關聯的出價的一個 或多個詞語。類似，搜尋引擎107可利用構成從候選集合中選擇的具有超 過給定閾值的相似性得分的一個或多個查詢的詞語來識別具有超過給定閾 值的出價的一個或多個詞語。搜尋引擎107然後可利用具有相關聯的出價 的一個或多個詞語，或者具有相關聯的超過給定閾值的出價的一個或多個 詞語，來選擇響應於由用戶制定的搜索查詢Q的一個或多個廣告。
根據另一示例，假定從候選集合中選擇的具有超過給定閾值的相似性 得分的給定査詢Q'包括平假名詞語，而上述由用戶制定的查詢Q包括漢 字和羅馬字詞語。搜尋引擎可利用構成査詢Q'的一個或多個平假名詞語來 判定是否有一個或多個廣告主為構成查詢Q'的平假名詞語出了價。類似 地，搜尋引擎可判定是否有一個或多個廣告主為構成查詢Q'的一個或多個 平假名詞語提供了超過給定閾值的出價。搜尋引擎107可檢索出具有相關 聯的對構成查詢Q'的詞語的出價的一個或多個廣告，並將該一個或多個廣 告遞送到分發組件。根據本發明的一個實施例，搜尋引擎107檢索出具有 最大的相關聯的對於構成查詢Q'的一個或多個詞語的出價的一個或多個廣 告。分發組件116隨後可以將該一個或多個廣告遞送給提交了査詢Q的用 戶。
雖然上述實施例描述了對査詢的接收和處理，但是圖1所示的搜索提 供商100系統不限於接收查詢並計算査詢的相似性得分，而是還可用於為 構成一個或多個文本串的一個或多個詞語計算相似性得分。客戶端設備 124a、 124b和124c的用戶可向搜索提供商100遞送包括一個或多個詞語
的一個或多個文本串，包括但不限於根據具有多個書寫系統的語言的一個 或多個書寫系統書寫的短語、句子、段落和文檔。相應地，搜索提供商
100可將這一個或多個文本串的日誌記錄在一個或多個日誌文件中。搜索 提供商100可操作以用於從其日誌文件中識別出包括一個或多個項目的候 選集合，其中給定項目包括與由客戶端設備124a、 124b和124c的給定用 戶遞送的一個或多個詞語相關的一組或多組詞語。例如，候選集合中的給 定項目可包括短語或句子。類似地，候選集合中的給定項目可包括段落或 整個文檔。搜索提供商可為候選集合中的一個或多個項目計算相似性得 分，該相似性得分指示出一個項目與從客戶端設備124a、 124b和124c接 收的一個或多個詞語在含義上的相似性的強度。
圖2示出了用於從候選集合中選擇在含義上與給定査詢Q相關的一個 或多個查詢Q'的方法的一個實施例，其中查詢Q和Q'是根據具有多個書 寫系統的語言的一個或多個書寫系統書寫的。如圖2所示，從給定用戶接 收搜索查詢，步驟205。該査詢可以是從可通信地耦合到諸如網際網路之類 的網絡的客戶端設備接收的，並且可包括根據具有多個書寫系統的語言的 一個或多個書寫系統的組合來書寫的一個或多個詞語或短語。例如，從用 戶接收的查詢可包括根據漢字、片假名和平假名書寫系統書寫的日語詞 語。
識別由與用戶制定的給定査詢Q相關的査詢組成的候選集合，步驟 210。候選集合可由根據與用戶的查詢相關聯的語言的一個或多個書寫系 統書寫的査詢組成。例如，給定査詢Q可包括根據日語片假名書寫系統書 寫的詞語，例如査詢"歹夕亍y"。相關查詢的候選集合因而可以包括根 據一個或多個日語書寫系統的一個或多個組合書寫的一個或多個査詢。例 如，與上述平假名查詢"，夕亍y"相關的査詢的候選集合可包括羅馬字 査詢"rakuten"、漢字查詢"楽天"、平假名查詢"b〈TA/'，等等。
與給定查詢Q相關的查詢的候選集合可利用一個或多個查詢日誌來生 成。根據本發明的一個實施例，査詢日誌可標識在給定的査詢會話期間由 用戶制定的一個或多個查詢。例如，在給定的查詢會話期間，用戶可以制 定包括根據日語平假名和漢字書寫系統書寫的詞語的査詢。在同一查詢會
話期間，用戶還可制定包括根據日語片假名和羅馬字書寫系統書寫的詞語 的査詢。可以執行分析以判定兩個査詢是否在統計上顯著地共現於一個或
多個査詢日誌中。根據本發明的一個實施例，統計顯著性(statistical significance)閾值可用於選擇如一個或多個査詢日誌所指示的與給定查詢 Q最相關的一個或多個查詢。
可以利用如一個或多個査詢日誌所指示的被識別為在統計上顯著地與 給定查詢相關或者以超過給定閾值的統計顯著性與給定查詢相關的一個或 多個査詢來生成候選集合。構成相關查詢的候選集合的一個或多個查詢可 根據在以上標識出的通過引用全部併入的申請中描述的用於利用查詢日誌 來確定統計上顯著相關的査詢的方法來選擇。
從相關查詢的候選集合選擇給定查詢Q'，步驟215。根據圖2所示的 實施例，為所選擇的查詢Q'計算相似性得分，步驟220。為給定査詢Q'計 算相似性得分提供了指示出查詢Q'的含義與根據具有多個書寫系統的語言 的一個或多個書寫系統書寫的給定査詢Q的含義的相似性的強度的數值。 表A示出了可用於為給定査詢Q'計算相似性得分的式子的一個實施例。
表A中給出的式子可用於計算指示出給定查詢Q'與給定查詢Q在含 義上的相似性的強度的得分，所述給定査詢Q可以是根據一個或多個日語 書寫系統來書寫的，所述一個或多個日語書寫系統包括但不限於漢字、假 名、JASCII、假名、片假名、羅馬字和平假名。本領域的技術人員明白， 表A中所示的式子可以被修改，以支持為其他具有多個書寫系統的語言計 算相似性得分。
相似性得分(Q，) formula see original document page 22
表A
根據表A中給出的式子，Q表示根據一個或多個日語書寫系統書寫的 給定查詢。Q，表示從與查詢Q相關的查詢的候選集合中選擇的查詢。丄ew 是用於將所有日語字符轉換成羅馬字符之後計算Q和Q'之間的字符編輯
距離的函數。丄W"是用於在將所有日語字符轉換為羅馬字符並去除空格
後計算Q和Q'之間的字符編輯距離的函數。是在將所有日語字符轉 換成羅馬字符之後Q和Q'之間的單詞編輯距離。"&a是用於識別Q是否 包含任何未出現在Q'中的數字以及識別Q'是否包含任何未出現在Q中的 數字的函數。i^w力W是用於判定Q或Q'是否包含漢字字符並且在包含的 情況下識別Q和Q'之間的漢字不一致的函數。C^r是這樣一個函數，該函 數用於計算在每個查詢中的所有日語字符都已被轉換成羅馬字符之後，從 每個査詢的最左邊字符起直到第一個字符不一致為止，Q和Q'共同具有的 字符的數目。丄eW是用於計算在所有漢字字符都已被轉換成假名字符並且 所有的非日語字符都被去除之後Q和Q'之間的字符編輯距離的函數。 戶/^m7z是用於計算在用戶查詢會話的日誌中查詢Q'跟隨著查詢Q的査詢 替換概率的函數。表A中所示的相似性得分函數所利用的函數的示例在圖 3至圖11中示出。
執行檢查以判定是否已為候選集合中的一個或多個査詢計算相似性得 分，步驟225。如果候選集合中的一個或多個査詢不具有相關聯的相似性 得分，則從候選集合中選擇另外的査詢Q'，步驟215。或者，如果已經為 候選集合中的一個或多個查詢計算了相似性得分，則從候選集合中選擇給 定查詢Q'，步驟230。執行檢査以判定與從候選集合中選擇的查詢Q'相關 聯的相似性得分是否超過給定的相似性得分閾值，步驟235。根據本發明 的一個實施例，相似性得分閾值包括可用於執行與下述相似性得分的比較 的數值該相似性得分與給定查詢Q'相關聯。因為相似性得分指示出給定 查詢Q，與查詢Q在含義上的相似性的強度，因此對相似性得分閾值的使 用幫助了從候選集合中選擇在含義上與查詢Q最相似的一個或多個査詢。
如果與給定査詢Q'相關聯的相似性得分超過相似性得分閾值，則查詢 Q'被添加到分發集合，步驟245。根據本發明的一個實施例，分發集合包 括從候選集合中選擇的具有超過相似性得分閾值的相似性得分的一個或多 個查詢。如果與給定査詢Q'相關聯的相似性得分不超過相似性得分閾值， 則査詢Q'不被添加到分發集合，步驟240。
執行檢査以判定在候選集合中是否有另外的査詢需要分析，步驟
250。如果在候選中有一個或多個査詢需要分析，則從候選集合中選擇另 外的査詢Q，，步驟230。或者，在候選集合中的所有査詢都已被分析，並 且分發集合已被填充以超過相似性得分閾值的一個或多個查詢之後，分發 集合中的一個或多個查詢被分發，步驟255。
超過相似性得分閾值的查詢的分發集合中的一個或多個查詢可被遞送 給提交了査詢Q的用戶。根據本發明的一個實施例，分發集合中的一個或 多個查詢可在結果網頁中被顯示給用戶。例如，用戶可被呈現以網頁，該 網頁包括結果，例如指向響應於查詢Q的內容項的連結，以及構成分發集 合的在含義上與查詢Q最相似的一個或多個Q'查詢。遞送給給定用戶的 分發集合中的一個或多個査詢可根據相似性得分被顯示在排名列表中，以 向用戶指示出給定查詢Q，與查詢Q在含義上的相似性的相對強度。
圖3至11示出了表A中給出的可用於為從查詢的候選集合選擇的給 定查詢Q'計算相似性得分的函數的實施例。如前所述，在表A中示出並 在圖3至11中進一步描述的多個函數可用於計算指示出給定查詢Q'與根 據一個或多個日語書寫系統書寫的查詢Q在含義上的相似性的強度的相似 性得分。但是，本領域的技術人員明白，圖3至11所示的函數的實施例 是示例性的，而並不想要限於日語語言和書寫系統，並且可以被修改以支 持為其他具有多個書寫系統的語言計算相似性得分。本領域的技術人員還 明白，圖3至11所示的函數並不限於為包括與給定查詢相關的一個或多 個查詢的候選集合計算相似性得分，而是可用於為包括根據多個技術選擇 的一個或多個查詢的查詢候選集合計算相似性得分。此外，本領域的技術 人員明白，圖3至11所示的函數並不限於為包括一個或多個查詢的候選 集合計算相似性得分，而是可被修改以為包括但不限於短語、句子、段落 和文檔在內的一組或多組詞語計算相似性得分。
圖3示出了用於計算根據一個或多個日語書寫系統書寫的給定查詢Q 和從査詢的候選集合中選擇的查詢Q'之間的字符編輯距離的方法的一個實 施例。圖3中給出的方法示出了表A所示的相似性得分函數所利用的/evA: 函數的一個實施例。
將構成査詢Q的一個或多個字符轉換成羅馬字符，步驟305，其中查
詢Q可能是根據諸如漢字、片假名、平假名等等之類的一個或多個日語書 寫系統書寫的。從由一個或多個查詢組成的候選集合中選擇給定査詢Q'，
步驟310。從候選集合中選擇的查詢Q'可能是根據與查詢Q相關聯的語言 的一個或多個書寫系統來書寫的。例如，Q'可能是根據與查詢Q相同的書 寫系統書寫的，或者是根據諸如日語羅馬字書寫系統、曰語假名書寫系統 等等之類的一個或多個替代的日語書寫系統書寫的。執行檢查以判定構成 Q'的字符是否是羅馬字符形式的，步驟315。如果査詢Q'不是羅馬字符形 式的，則構成Q'的一個或多個字符被轉換成羅馬字符，步驟320。如果構 成Q'的一個或多個詞語已經是羅馬字符形式的，或者在Q'中的所有字符 都被轉換成羅馬字符形式之後，執行計算以識別查詢Q和查詢Q'之間的 字符編輯距離，步驟325。字符編輯距離值可以被提供給表A中示出的相 似性得分函數以為Q'計算相似性得分。
圖4示出了用於計算根據一個或多個日語書寫系統書寫的給定查詢Q 和從査詢的候選集合中選擇的査詢Q'之間的字符編輯距離的方法的一個實 施例。圖4中示出的實施例提供了表A所示的相似性得分函數所使用的 /ev^函數的一個實施例。
根據圖4所示的實施例，將根據諸如漢字、片假名、平假名等等之類 的一個或多個日語書寫系統書寫的查詢Q轉換成羅馬字符形式，步驟 405。然後，去除羅馬字符形式的查詢Q中出現的所有空格字符，步驟 408。例如，給定査詢Q可包括漢字詞語"電車男"。在轉換到羅馬字符 形式之後，査詢Q可包括詞語"densha otoko"，而在去除空格之後，查 詢Q可包括字符"denshaotoko"。
從包括一個或多個查詢的候選集合中選擇給定查詢Q'，步驟410。執 行檢查以判定Q'是否是羅馬字符形式的，步驟415。如果查詢Q'不是羅馬 字符形式的，則構成Q'的一個或多個字符被轉換成羅馬字符，步驟420。 如果構成Q，的字符已經是羅馬字符形式的，或者在構成查詢Q'的字符都 已被轉換成羅馬字符形式之後，查詢Q'內的所有空格被去除，步驟425。 然後，計算査詢Q和Q，的羅馬字符形式之間的字符編輯距離，步驟430。 所計算出的查詢Q和Q'之間的字符編輯距離可被表A中所示的相似性得
分函數用來為Q'計算相似性得分。
圖5示出了表A中所示的won/r函數的一個實施例。圖5中所示的
vvw會函數的實施例支持計算根據一個或多個日語書寫系統書寫的給定査
詢Q和從査詢的候選集合選擇的査詢Q'之間的單詞編輯距離。根據本發 明的一個實施例，給定査詢Q和查詢Q，之間的單詞編輯距離是值一
("1")與下述商之間的差Q和Q'中的獨特空格分隔共現單詞的數目 與Q和Q'兩者中的獨特空格分隔單詞的總數的商。
將構成根據一個或多個日語書寫系統書寫的給定査詢Q的字符轉換成 羅馬字符形式，步驟505。然後，從查詢的候選集合中選擇給定査詢Q'， 步驟506。執行檢査以判定査詢Q'是否是羅馬字符形式的，步驟508。如 果查詢Q'不是羅馬字符形式的，則構成Q'的字符被轉換成羅馬字符，步 驟510。如果構成査詢Q'的字符已經是羅馬字符形式的，或者在構成Q'的 字符已被轉換成羅馬字符形式之後，識別Q和Q'中的獨特空格分隔共現 單詞的數目，步驟515。計算Q和Q'中的獨特空格分隔共現單詞的數目與 Q和Q'兩者中的獨特空格分隔單詞的總數的商，步驟520。根據本發明的 一個實施例，獨特空格分隔共現單詞的數目包括在給定査詢Q和給定査詢 Q，兩者之中都出現的獨特單詞的數目。此外，Q和Q，兩者中的獨特空格分 隔單詞的總數包括給定査詢Q和査詢Q'中的獨特空格分隔單詞的總和。 計算值一 ("1")和計算出的商之間的差，步驟525，並將其賦予
"wordr"寄存器，步驟530。根據本發明的一個實施例，"wordr"寄存 器包括用於存儲給定數值的存儲設備。賦予"wordr"寄存器的值可被表A 中所示的相似性得分函數用來為查詢Q'計算相似性得分。
例如，羅馬字符形式的給定查詢Q可由詞語"kurumakemuri"組成。 類似地，羅馬字符形式的給定查詢Q'可由詞語"somkemuri"組成。Q和 Q，中的獨特空格分隔共現單詞的數目是一 ("1")，即單詞"kemuri"， 其中Q和Q，兩者中獨特空格分隔單詞的總數是三("3")，即單詞
"kuruma" 、 "sora"和"kemuri"。因此，Q和Q，中的獨特空格分隔共 現單詞的數目與Q和Q，兩者中的獨特空格分隔單詞的總數的商為1/3。此 外，一 與計算出的商之間的差是2/3。值2/3可被賦予"wordr"
寄存器，並且可被表A中所示的相似性得分函數用來為查詢Q'計算相似
性得分。
圖6示出了這樣一個方法的一個實施例，該方法用於判定與從查詢的 候選集合選擇的査詢Q'相比，某一數字是否是根據一個或多個日語書寫系 統書寫的給定查詢Q所特有的。圖6中給出的方法提供了表A所示的相似 性得分函數所使用的^'g^函數的一個實施例。
從由根據一個或多個書寫系統書寫的查詢組成的候選集合中選擇給定 查詢Q'，步驟605。執行檢查以判定給定查詢Q中的數字是否未出現在査 詢Q'中。例如，給定查詢Q可包含日語漢字數字"六十八"(對應於由 阿拉伯數字"68"所表達的值)，並且給定查詢Q'可包含日語漢字數字 "九十八"(對應於由阿拉伯數字"98"所表達的值)。在步驟610執行 的檢查因此確定日語漢字數字"六"是查詢Q所特有的，因為它未出現在 査詢Q'中。類似地，給定查詢Q可包括日語漢字字符和阿拉伯數字"楽 天2005"，並且給定查詢Q'可包括日語漢字字符和阿拉伯數字"楽天 2004"。在步驟610執行的檢査將會確定阿拉伯數字5是査詢Q所特有 的，因為它未出現在査詢Q'中。
如果某一數字被識別為出現在查詢Q中，但未出現在查詢Q'中，則 "digit"寄存器被設置到值一 ("1")，表明查詢Q包含不在査詢Q'中 的數字，步驟620。根據本發明的一個實施例，"digit"寄存器包括用於 存儲給定數值的存儲設備。
或者，如果Q'包含出現在查詢Q中的一個或多個數字中的每一個， 則執行額外的檢査以判定查詢Q'中的數字是否未出現在查詢Q中，步驟 615。如果查詢Q，包含未出現在查詢Q中的數字，則上述"digit"寄存器 被設置到值一 ("1")，表明査詢Q，包含Q，所特有的數字，步驟620。 或者，如果査詢Q包含Q'中的一個或多個數字中的每一個，則"digit"寄 存器被設置到零("0")，步驟625，表明查詢Q'中的一個或多個數字 出現查詢Q中，反之亦然。賦予"digit"寄存器的值零("0")或一 ("1")可被表A中所示的相似性得分函數用來為査詢Q，計算相似性得 分。
圖7給出了被表A中所示的相似性得分函數使用的^m力W函數的一個
實施例。接收可能根據一個或多個日語書寫系統書寫的給定查詢Q，步驟 705。執行檢査以判定査詢Q是否包含一個或多個日語漢字字符，步驟 710。如果查詢Q不包含任何漢字字符，則"kanjid"寄存器被設置到零 ("0")，步驟708，其中"kanjid"寄存器可包括用於存儲給定數值的 存儲設備。或者，如果査詢Q包含一個或多個漢字字符，則從查詢的候選 集合中選擇査詢Q'，步驟715。
執行檢査以判定從候選集合中選擇的查詢Q'是否包含一個或多個漢字 字符，步驟720。如果查詢Q，不包含任何漢字字符，則上述"kanjid"寄 存器被設置到零("0")，步驟708。相反，如果Q'包含一個或多個漢 字字符，則Q和Q'中的一個或多個非漢字字符被去除，步驟722。然後識 別查詢Q和查詢Q'中共現的獨特漢字字符的數目，步驟725。例如，如果 在去除非漢字字符後查詢Q由漢字字符"楽天巿場"組成，並且如果在去 除非漢字字符後查詢Q，由漢字字符"楽天"組成，則Q和Q'中的獨特共 現漢字字符的數目是二 ( "2")，即"楽天"。
然後識別Q和Q'兩者之中的獨特漢字字符的總數，步驟727。例如， 在由漢字字符"楽天巿場"組成的Q和由漢字字符"楽天"組成的Q'兩 者之中的獨特漢字字符的總數是六("6")，即來自查詢Q的獨特漢字 字符"楽天巿場"和來自查詢Q'的獨特漢字字符"楽天"。計算共現漢字 字符的數目與總獨特漢字字符的商，步驟730。將"kanjid"寄存器設置到 一 ("1")與計算出的商之間的差值，步驟735。 "kanjid"寄存器的值 可被表A中所示的相似性得分函數用來為Q'計算相似性得分。
圖8示出了用於識別根據一個或多個日語書寫系統書寫給定査詢Q和 從查詢的候選集合中選擇的查詢Q，的前綴中重疊的字符數目的方法的一個 實施例，該方法開始於比較每個査詢的最左邊字符，並且繼續到第一個字 符不一致為止。圖8中給出的方法示出了被表A中所示的相似性得分函數 利用的wr函數的一個實施例。
將根據一個或多個日語書寫系統書寫的給定査詢Q轉換成羅馬字符形 式，步驟805。從查詢的候選集合中選擇查詢Q'，步驟810。執行檢査以
判定構成査詢Q'的一個或多個字符是否是羅馬字符形式的，步驟815。如 果構成查詢Q'的一個或多個字符不是羅馬字符形式的，則將這些字符轉換 成羅馬字符，步驟820。如果構成Q，的字符已經是羅馬字符形式的，或者 在構成Q，的一個或多個字符已被轉換成羅馬字符形式之後，選擇查詢Q 和査詢Q'的第一羅馬字符，步驟825。
執行檢査以判定從査詢Q中選擇的第一字符和從査詢Q'中選擇的第 一字符是否匹配，步驟835。如果從Q和Q'選擇的第一字符不匹配，則處 理終止，步驟830。或者，如果選擇的字符匹配，則使字符匹配計數寄存 器遞增，步驟850，表明識別出查詢Q和查詢Q'的字符匹配。根據本發明 的一個實施例，字符匹配計數寄存器被初始化為值零("0")，並且在 來自查詢Q和査詢Q'的字符被識別為匹配時被遞增。
選擇來自Q和Q'的下一字符，步驟840，並且執行檢查以判定下一字 符是否匹配，步驟835。如果從Q和Q'選擇的字符不匹配，則字符匹配計 數寄存器不被遞增，並且處理結束，步驟830。當處理終止時，步驟 830，字符匹配計數寄存器中的值將指示出Q和Q'中匹配的字符的數目。 字符匹配計數寄存器中的值被表A中所示的相似性得分函數利用來為查詢 Q'計算相似性得分。
圖9示出了用於識別根據一個或多個日語書寫系統書寫的給定查詢Q 或者從査詢的候選集合中選擇的查詢Q'是否包含非羅馬字符的方法的一個 實施例。圖9給出的實施例示出了可被表A中所示的相似性得分函數使用 的y，腦e函數。
接收根據一個或多個日語書寫系統書寫的給定查詢Q，步驟905。執 行檢査以判定查詢Q是否包含一個或多個非羅馬字符，步驟910。如果查 詢Q包含一個或多個非羅馬字符，則"Japanese"寄存器被設置到值一 ("1")，步驟908。根據本發明的一個實施例，"Japanese"寄存器包 括用於存儲給定數值的存儲設備。
如果查詢Q不包含一個或多個非羅馬字符，則從包括一個或多個査詢 的候選集合中選擇査詢Q，，步驟915。執行檢查以判定查詢Q'是否包含一 個或多個非羅馬字符，步驟920。如果査詢Q'包含一個或多個非羅馬字
符，則"janapese"寄存器被設置到值("1")，步驟908。或者，如果 Q，僅包含非羅馬字符，則"Japanese"寄存器被設置到值零("0")，步 驟922，並且處理隨後終止，步驟925。 "Japanese"寄存器中維護的值可 被表A中所示的相似性得分函數利用來為查詢Q'計算相似性得分。
圖10示出了用於在所有漢字和非日語字符已被從每個相應的查詢中 去除之後確定給定査詢Q和查詢Q，之間的字符編輯距離的方法的一個實 施例。圖10給出的方法示出了可被表A中所示的相似性得分函數利用的 fevA函數的一個實施例。
如圖10所示，從查詢的候選集合中選擇給定査詢Q'，步驟1005。執 行檢査以判定根據一個或多個日語書寫系統書寫的查詢Q，或給定査詢Q 是否包含一個或多個漢字字符，步驟1010。如果查詢Q或査詢Q'包含一 個或多個漢字字符，則每個相應的查詢中的漢字字符被轉換成假名字符， 步驟1015。例如，查詢Q可由漢字字符和阿拉伯數字兩者組成，例如 "人200"。在將漢字字符轉換成假名字符之後，查詢Q可包括字符"t> ^ 200"。
如果查詢Q或査詢Q'都不包含漢字字符，或者在每個相應查詢中的 所有漢字字符都已被轉換成假名字符之後，執行額外的檢查以判定任一查 詢是否包含非日語字符，步驟1020。根據本發明的一個實施例，非日語字 符包括不是根據一個或多個日語書寫系統書寫的字符。例如，如果查詢Q 包括假名字符和阿拉伯數字，例如"！>i: 200"，則阿拉伯數字"200"可 包括非日語字符。
如果查詢Q或查詢Q'包含非日語字符，則非日語字符被去除，步驟 1025。參考上述示例，在從査詢Q去除非日語字符即阿拉伯數字"200" 之後，查詢Q可包括假名字符"t>ir"。如果查詢Q或査詢Q'都不包含 非日語字符，或者在所有非日語字符都已被去除之後，Q和Q，之間字符編 輯距離被計算，步驟1030。查詢Q和查詢Q'之間的字符編輯距離可被表 A中所示的相似性得分函數用來為Q'計算相似性得分。
圖11給出了被表A中所示的相似性得分函數利用的函數的一 個實施例。根據本發明的一個實施例，^"mz>z函數計算給定查詢Q'跟隨
給定查詢Q的査詢替換概率，並且也可用來計算短語P'跟隨給定短語P的 短語替換。例如，可以維護一個或多個査詢日誌，這一個或多個查詢曰志 標識出在査詢會話期間由給定用戶提交的一個或多個查詢和短語。查詢日 志例如可標識用戶提交的一個或多個查詢和短語的順序，以提供關於用戶
如何改進查詢Q、用戶如何改寫查詢Q、用戶如何利用具有多個書寫系統 的語言的一個或多個替代書寫系統來表達査詢Q等等的指示。査詢日誌還 可指示出一個或多個用戶提交一個或多個查詢或短語的頻率。
識別給定査詢Q出現在一個或多個查詢日誌中的頻率，步驟1105。 從查詢的候選集合中選擇給定査詢Q'，步驟1110。執行檢查以判定在一 個或多個查詢日誌中的任何一個中查詢Q'是否跟隨査詢Q，步驟115。根 據本發明的一個實施例，執行檢査以判定在針對給定用戶的査詢會話的查 詢日誌中査詢Q'是否跟隨查詢Q，其中査詢會話可包括在給定時間段期間 由用戶提交的一個或多個查詢。
如果在一個或多個查詢日誌中的任何一個之中查詢Q'都不跟隨査詢 Q，貝U "pl2min"寄存器被設置到零("0")，步驟1125，其中
"pl2min"寄存器可包括用於存儲給定數值的存儲設備。或者，如果查詢 Q'被識別為在一個或多個査詢日誌中跟隨Q，則識別在查詢日誌中查詢Q' 跟隨查詢Q的頻率，步驟1120。 "pl2min"寄存器被設置到在查詢日誌 中查詢Q'跟隨查詢Q的頻率與査詢日誌中查詢Q的頻率的商的值，步驟 1140。例如，如果査詢Q在査詢日誌中出現十二 ( "12")次並且在査詢 日誌中Q'跟隨查詢Q七("7")次，則"pl2min"寄存器可被設置到值
"7/12"。
本領域的技術人員明白，在圖3至11中示出並被表A中所示的相似 性得分函數所利用的函數並不限於日語語言，而是可被修改用於一個或多 個具有多個書寫系統的語言。本領域的技術人員還明白，表A中所示的相 似性得分函數可利用圖3至11所示的函數的一個或多個組合，以為根據 具有多個書寫系統的語言的一個或多個書寫系統書寫的給定査詢計算相似 性得分。
雖然己經結合優選實施例描述和示出了本發明，但是在不脫離本發明
的精神和範圍的情況下可以進行對於本領域的技術人員來說顯而易見的許 多變化和修改，本發明因而不限於以上闡述的方法或構造的確切細節，因 為這種變化和修改想要被包括在本發明的範圍之內。
權利要求
1. 一種用於識別與給定查詢相關的一個或多個查詢的方法，該方法包括接收根據具有多個書寫系統的語言的一個或多個書寫系統書寫的查詢；識別根據所述具有多個書寫系統的語言的一個或多個書寫系統書寫的查詢的候選集合；以及為所述候選集合中的一個或多個查詢計算指示出所述一個或多個查詢與接收的查詢的相似性的得分。
2. 如權利要求1所述的方法，其中，接收査詢包括接收根據一個或多 個日語書寫系統的組合書寫的査詢。
3. 如權利要求1所述的方法，其中，識別查詢的候選集合包括識別與 所述接收的查詢相關的一個或多個查詢的集合。
4. 如權利要求3所述的方法，其中，識別與接收的查詢相關的査詢的 候選集合包括識別如一個或多個查詢日誌中所指示的與所述接收的查詢相 關的一個或多個査詢。
5. 如權利要求1所述的方法，其中，接收查詢包括接收根據日語平假 名書寫系統書寫的査詢。
6. 如權利要求1所述的方法，其中，接收査詢包括接收根據日語片假 名書寫系統書寫的查詢。
7. 如權利要求1所述的方法，其中，接收査詢包括接收根據日語假名 書寫系統書寫的查詢。
8. 如權利要求1所述的方法，其中，接收查詢包括接收根據日語羅馬 字書寫系統書寫的查詢。
9. 如權利要求1所述的方法，其中，接收查詢包括接收根據曰語 JASCII書寫系統書寫的査詢。
10. 如權利要求1所述的方法，其中，接收查詢包括接收根據日語漢 字書寫系統書寫的查詢。
11. 如權利要求1所述的方法，其中，接收査詢包括接收構成短語的 詞語的集合。
12. 如權利要求1所述的方法，其中，為所述候選集合中的一個或多 個查詢計算得分包括計算指示出來自所述候選的給定查詢與所述接收的查 詢在含義上的相似性的得分。
13. 如權利要求1所述的方法，其中，計算得分包括將所述接收的查詢的一個或多個字符轉換成羅馬字符； 將從所述候選集合中選擇的査詢的一個或多個字符轉換成羅馬字符；以及計算所述接收的査詢和所述從所述候選集合中選擇的査詢之間的字符 編輯距離。
14. 如權利要求1所述的方法，其中，計算得分包括 將所述接收的査詢的一個或多個字符轉換成羅馬字符； 將從所述候選集合中選擇的査詢的一個或多個字符轉換成羅馬字符； 從所述接收的查詢和所述從所述候選集合中選擇的查詢中去除空格字符；以及計算所述接收的査詢和所述從所述候選集合中選擇的查詢之間的字符 編輯距離。
15. 如權利要求1所述的方法，其中，計算得分包括 將所述接收的查詢的一個或多個字符轉換成羅馬字符； 將從所述候選集合中選擇的查詢的一個或多個字符轉換成羅馬字符； 識別所述接收的查詢和所述選擇的査詢中的獨特空格分隔共現單詞的數目；識別所述接收的查詢和所述選擇的查詢兩者之中的獨特空格分隔單詞 的總數；計算所述獨特空格分隔共現單詞的數目與兩個查詢中的所述獨特空格 分隔單詞的總數的商；以及計算數值一 ("1")與計算出的商之間的差。
16. 如權利要求1所述的方法，其中，計算得分包括識別某一數字是 否是所述接收的査詢或者從所述候選集合中選擇的査詢所特有的。
17. 如權利要求1所述的方法，其中，計算得分包括識別所述接收的査詢和從所述候選集合中選擇的查詢中的共現日語漢 字字符的數目；識別所述接收的查詢和所述從所述候選集合中選擇的查詢中的獨特日 語漢字字符的總數；計算所述共現日語漢字字符的數目與所述獨特日語漢字字符的總數的 商；以及計算數值一 ("1")與計算出的商之間的差。
18. 如權利要求1所述的方法，其中，計算得分包括 將所述接收的查詢的一個或多個字符轉換成羅馬字符； 將從所述候選集合中選擇的查詢的一個或多個字符轉換成羅馬字符；以及計算所述接收的查詢和所述選擇的查詢共有的羅馬字符的數目。
19. 如權利要求1所述的方法，其中，計算得分包括識別所述接收的 查詢或者從所述候選集合中選擇的查詢是否包含非羅馬字符。
20. 如權利要求1所述的方法，其中，計算得分包括 將所述接收的查詢的一個或多個日語漢字字符轉換成日語假名字符； 將從所述候選集合中選擇的査詢的一個或多個日語漢字字符轉換成日語假名字符；從所述接收的査詢和所述從所述候選集合中選擇的査詢中去除所有非 日語字符；以及計算所述接收的查詢和所述從所述候選集合中選擇的査詢之間的字符 編輯距離。
21. 如權利要求1所述的方法，其中，計算得分包括計算在一個或多 個查詢日誌中從所述候選集合中選擇的查詢跟隨所述接收的査詢的頻率與 在所述一個或多個査詢日誌中所述接收的査詢的頻率的商。
22. 如權利要求1所述的方法，包括從所述候選集合的査詢中選擇一 個或多個査詢以便分發。
23. 如權利要求22所述的方法，其中，從所述候選集合的査詢中選擇 一個或多個査詢以便分發包括選擇具有超過給定閾值的得分的一個或多個 查詢。
24. 如權利要求1所述的方法，包括分發來自所述候選集合的具有超 過給定閾值的得分的一個或多個查詢。
25. 如權利要求24所述的方法，其中，分發來自所述候選集合的一個 或多個査詢包括將所述一個或多個查詢嵌入在網頁中。
26. —種用於識別與給定查詢相關的一個或多個查詢的系統，該系統 包括搜尋引擎，該搜尋引擎可操作以用於接收根據具有多個書寫系統的語言的一個或多個書寫系統書寫的 査詢，以及識別根據所述具有多個書寫系統的語言的一個或多個書寫系統書 寫的一個或多個查詢的候選集合；轉換組件，該轉換組件可操作以用於將接收的査詢和所述候選集合中 的所述一個或多個查詢轉換成一個或多個書面格式；以及相似性組件，該相似性組件可操作以用於為所述候選集合中的所述一 個或多個查詢計算指示出所述一個或多個查詢與所述接收的査詢的相似性 的得分。
27. 如權利要求26所述的系統，其中，所述搜尋引擎可操作以用於接 收根據一個或多個日語書寫系統書寫的查詢。
28. 如權利要求26所述的系統，其中，所述搜尋引擎可操作以用於識 別由與所述接收的査詢相關的一個或多個查詢組成的候選集合。
29. 如權利要求28所述的系統，其中，所述搜尋引擎可操作以用於搜 索一個或多個査詢日誌以識別與所述接收的査詢相關的査詢的一個或多個 查詢。
30. 如權利要求26所述的系統，其中，所述轉換組件可操作以用於將査詢轉換成根據一個或多個書寫系統的一個或多個書面格式。
31. 如權利要求26所述的系統，其中，所述相似性組件可操作以用於 計算指示出從所述候選集合中選擇的查詢與所述接收的查詢在含義上的相 似性的得分。
32. 如權利要求26所述的系統，其中，所述相似性組件可操作以用於 計算所述接收的査詢和從所述候選集合中選擇的查詢之間的字符編輯距 離。
33. 如權利要求26所述的系統，其中，所述相似性組件可操作以用於識別所述接收的查詢和所述選擇的査詢中的獨特空格分隔共現單詞的 數目；識別所述接收的査詢和所述選擇的查詢兩者之中的獨特空格分隔單詞 的總數；計算所述獨特空格分隔共現單詞的數目與兩個査詢中的所述獨特空格 分隔單詞的總數的商；以及計算數值一 ("1")與計算出的商之間的差。
34. 如權利要求26所述的系統，其中，所述相似性組件可操作以用於 識別某一數字是否是所述接收的査詢或者從所述候選集合中選擇的査詢所 特有的。
35. 如權利要求26所述的系統，其中，所述相似性組件可操作以用於識別所述接收的査詢和從所述候選集合中選擇的査詢中的共現日語漢 字字符的數目；識別所述接收的査詢和所述從所述候選集合中選擇的查詢中的獨特日 語漢字字符的總數；計算所述共現日語漢字字符的數目與所述獨特日語漢字字符的總數的 商；以及計算數值一 ("1")與計算出的商之間的差。
36. 如權利要求26所述的系統，其中，所述相似性組件可操作以用於 計算所述接收的査詢和從所述候選集合中選擇的查詢共有的字符的數目。
37. 如權利要求26所述的系統，其中，所述相似性組件可操作以用於 識別所述接收的査詢或者從所述候選集合中選擇的查詢是否包含給定書寫 系統的一個或多個字符。
38.如權利要求26所述的系統，其中，所述相似性組件可操作以用於 計算在一個或多個査詢日誌中從所述候選集合中選擇的查詢跟隨所述接收 的査詢的頻率與在所述一個或多個査詢日誌中所述接收的査詢的頻率的 商。
全文摘要
本發明涉及用於識別與給定查詢相關的一個或多個查詢的系統和方法。本發明的方法包括接收根據具有多個書寫系統的語言的一個或多個書寫系統書寫的查詢。識別根據該具有多個書寫系統的語言的一個或多個書寫系統書寫的查詢的候選集合。為候選集合中的一個或多個查詢計算指示出該一個或多個查詢與接收的查詢的相似性的得分。
文檔編號G06F17/30GK101390097SQ200780006965
公開日2009年3月18日 申請日期2007年2月27日 優先權日2006年2月28日
發明者凱文·巴茲, 班傑明·雷, 羅斯·瓊斯 申請人:雅虎公司